时间戳

首页 > 解决方案 > 我们如何设计文档搜索系统？

full-text-search - 我们如何设计文档搜索系统？

问题描述

最近有人问我一个系统设计问题，我需要“设计文档搜索系统”，我首先想到的是弹性搜索的工作原理。所以我想出了用于支持文本搜索的倒排索引方法。倒排索引对每个术语都有一个记录。每条记录都有出现该术语的文档列表。文档由整数文档 ID 标识。文档 ID 列表按升序排序。

所以我在下面说了一些话，但我不确定这是否应该以分布式方式工作，因为我们可能有很多文档要索引，所以我们需要一些负载平衡器，并且我们需要以某种方式对倒排索引或数据进行分区。意思是一个将上传文档的过程，然后是什么过程将它标记化（它只是一台机器还是一堆机器）。基本上想了解用适当的组件设计这样的系统的正确方法是什么。我们应该如何在系统设计面试中谈论这个？对于这个问题，我们在面试中应该接触哪些内容？

在此处输入图像描述

我们应该用正确的组件设计分布式文档搜索系统的正确方法是什么？

标签： full-text-searchinformation-retrievalsystem-designinverted-index

解决方案

好的...这是一个广泛的主题。实际上，elasticsearch 正是为此而做的。但是谷歌也是。从 elasticSearch 到 google 搜索存在技术差距。

如果您进行个人实施，它仍然是可能的……但是要像弹性搜索一样高效，还有很多工作要做。快速回答是：使用弹性搜索。

您可能很好奇，或者出于某种原因您可能需要自己编写它。那么它是如何工作的：

TFIDF 和余弦距离

正如您首先指定的那样，您将进行标记，然后将标记化的文本表示为向量，然后测量文本和搜索词之间的角距离。

假设您的语言中只有 3 个单词“foo, bar, bird”，因此带有“foo bar bird”的文本可以用 vector3[1,1,1] 表示

A） “foo foo foo foo bird”将是 [4,0,1] 另一个

B） “富吧”[1,1,0]

如果您搜索由 [0,1,0] 表示的“bar”，您将查找具有最小角距离的文本，如果您计算搜索和 BI 之间的角距离，则认为这是 90°，即低于 A。

实际上，语言超过 3 个单词，因此您将在更多维度的向量中计算距离，因为 1 个世界 = 1 个维度 :)

TFIDF 代表词频逆文档频率。这通过该单词在所有文档中的频率的倒数来评估文档中单词的频率。它的作用是指出文档中的重要单词。

让我们解释一下：

  • “that, in a the”等词无处不在，所以它们并不重要
  • 在你所有的文本中，“语料库”这个词的频率我不知道 0.0001%
  • 在特定文本中被引用 5 次 hand 的频率为 0.1%
  • 那么它在语料库中非常罕见，但相比之下在您的文本中非常重要
  • 因此，当您搜索“语料库”时，您想要首先获取它出现 4 次的文本。
  • 因此，您将拥有一个相对出现频率的向量，而不是出现次数的向量，例如 [0.2,1,0.0005]

https://en.wikipedia.org/wiki/Tf%E2%80%93idf

最后我给你一个小惊喜：这就是 elasticsearch 得分背后的原因https://www.elastic.co/guide/en/elasticsearch/guide/current/scoring-theory.html

此外，elasticsearch 将为您提供复制可扩展性、分布以及您梦寐以求的任何东西。

仍然有理由不使用 elasticsearch ：

  • 研究目的
  • 您实际上编写了另一个搜索引擎，例如duckduck go（为什么不）
  • 你很好奇

缩放和分配部分

在https://en.wikipedia.org/wiki/Apache_Lucene之前阅读 lucene

它在很大程度上取决于要索引的文本量和单词。

如果它代表 1M 的文本，您不需要分发它。如果你索引像维基百科这样的大东西，你将需要一个分布式倒排索引（维基百科使用弹性搜索作为搜索框）

foo 在文本 A,B,C,R 中， 所以我将对索引进行分区

我将使用带有单词的分布式缓存作为键和指向向量的指针列表作为值。我会将值存储在内存映射文件中。搜索引擎是必须快速的东西，所以如果你自己做这件事，你会减少外部库。您将使用 c++

在谷歌，他们以向量占用大量空间以致需要将它们存储在多台机器中的情况结束，因此他们发明了 GFS，这是一个分布式文件系统。

多维向量之间的余弦距离计算非常耗时，所以我将在 GPU 中进行计算，因为 GPU 对矩阵和向量的浮点运算非常有效。

实际上，重新实现所有这些期望你有充分的理由这样做有点疯狂，例如一个非常好的商业模式:)

我可能会使用 kubernetes docker 和 mesos 来虚拟化我的所有组件。如果需要大容量，我会寻找类似于 GFS 的东西。 https://en.wikipedia.org/wiki/Comparison_of_distributed_file_systems

您需要取回文本，因此我将使用任何可以以任何语言扩展的 NIO 网络服务器。我将使用 nginx 来提供静态页面和类似 netty 或 vertx 的东西来获取搜索，然后构建文本链接的答案（这取决于你想在一秒钟内服务多少用户）

如果我打算索引比维基百科更大的东西，所有这些。如果我打算发明比弹性搜索更好的东西（艰巨的任务祝你好运）

例如维基百科，这少于 1T 的文本。

最后

如果您在一周内使用 elasticsearch 完成此操作，则可能需要 2 周并投入生产。如果您自己做，您将需要至少 1 名高级开发人员和一名数据科学家、一名架构师，并且需要一年或更长时间，具体取决于您要索引的文本量。我忍不住问自己“它是为了什么”。

实际上，如果您阅读 lucene 的代码源，您将确切地知道您需要什么。他们做到了，lucene是elasticsearch的引擎。

Twitter 正在使用 Lucene 进行实时搜索

推荐阅读