我们如何设计文档搜索系统？
How can we design system for document search?
我最近被问到一个系统设计问题，我需要 "design system for document search" 我首先想到的是弹性搜索是如何工作的。所以我想出了用于支持文本搜索的倒排索引方法。倒排索引对每个词都有一条记录。每条记录都有该术语出现的文档列表。文档由整数文档 ID 标识。文档 ID 列表按升序排序。
所以我在下面说了一些事情，但我不确定这是否应该以分布式方式工作，因为我们可能有很多文档需要索引，所以我们需要一些负载平衡器，并且我们需要以某种方式进行分区倒排索引或数据。意思是一个将上传文档的过程，然后是什么过程将它标记化（它只是一台机器还是一堆机器）。基本上想了解使用适当的组件设计这样的系统的正确方法是什么。我们应该如何在系统设计面试中谈论这个？这个问题面试应该接触哪些东西？
我们应该使用正确的组件设计分布式文档搜索系统的正确方法是什么。
好的...这是一个庞大的主题。实际上，elasticsearch 正是为此而做的。但是 google 也是。从 elasticSearch 到 google 搜索存在技术差距。
如果您选择个人实施，它仍然是可能的……但是要像 elasticsearch 一样高效，还有大量工作要做。快速回答是：使用 elasticsearch。
你可能很好奇或者出于某种原因你可能需要自己写。那么它是如何工作的：
TFIDF和余弦距离
正如您首先指定的那样，您将标记化
然后您将标记化的文本表示为向量，然后测量文本和搜索词之间的 angular 距离。
假设在您的语言中只有 3 个单词 "foo, bar, bird"
所以带有 "foo bar bird" 的文本可以用 vector3[1,1,1] 表示
的文本
A) "foo foo foo foo bird" 将是 [4,0,1]
另一个
B) "foo bar" [1,1,0]
如果您搜索由 [0,1,0] 表示的 "bar"，您将查找具有最小 angular 距离的文本，如果您计算 angular 你的搜索和 B 之间的距离我认为这是 90°，比 A 低。
实际上语言超过 3 个单词，因此您将计算更多维度的向量中的距离，因为 1 个世界 = 1 个维度:)
TFIDF 代表词频逆文档频率。
这通过该词在所有文档中的频率的倒数来评估文档中词的频率。它的作用是指出文档中的重要词。
让我们解释一下：
- "that, in a the"等词无处不在，不重要
- 在你所有的文本中，"corpus" 这个词出现的频率是我不知道 0.0001%
- 在特定文本中被引用 5 次的频率为 0.1%
- 那么它在语料库中很少见，但相比之下在你的文本中却很重要
- 所以当您搜索 "corpus" 时，您想要的是首先获取出现 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++
在 google 他们以向量占用太多 space 的情况结束，他们需要将它们存储在多台机器上，所以他们发明了 GFS，这是一个分布式文件系统。
多维向量之间的余弦距离计算很耗时，所以我会在GPU上计算，因为GPU对矩阵和向量的浮点运算效率很高。
实际上，重新实现所有这些有点疯狂，希望您有充分的理由这样做，例如一个非常好的商业模式:)
我可能会使用 kubernetes docker 和 mesos 来虚拟化我所有的组件。如果需要大容量，我会寻找类似于 GFS 的东西。
https://en.wikipedia.org/wiki/Comparison_of_distributed_file_systems
您需要取回文本，因此我将使用任何可扩展为任何语言的 NIO 网络服务器。我将使用 nginx 来为静态页面提供服务，并使用 netty 或 vertx 之类的东西来进行搜索，然后将 link 的答案构建到文本中（这取决于你想在一秒钟内为多少用户提供服务）
如果我打算索引比维基百科更大的东西，那么所有这些。如果我打算发明比 elasticsearch 更好的东西（艰巨的任务祝你好运）
例如维基百科，这不到 1T 文本。
终于
如果您使用 elasticsearch 在一周内完成，您可能需要 2 周并投入生产。如果自己做，至少需要1个高级开发人员ad 一名数据科学家一名建筑师，大约一年或更长时间，具体取决于您要索引的文本量。我忍不住问自己 "what is it for".
实际上，如果您阅读lucene 的代码源，您就会确切地知道您需要什么。他们做到了，lucene是elasticsearch的引擎
Twitter 正在使用 Lucene 进行实时搜索
我最近被问到一个系统设计问题，我需要 "design system for document search" 我首先想到的是弹性搜索是如何工作的。所以我想出了用于支持文本搜索的倒排索引方法。倒排索引对每个词都有一条记录。每条记录都有该术语出现的文档列表。文档由整数文档 ID 标识。文档 ID 列表按升序排序。
所以我在下面说了一些事情，但我不确定这是否应该以分布式方式工作，因为我们可能有很多文档需要索引，所以我们需要一些负载平衡器，并且我们需要以某种方式进行分区倒排索引或数据。意思是一个将上传文档的过程，然后是什么过程将它标记化（它只是一台机器还是一堆机器）。基本上想了解使用适当的组件设计这样的系统的正确方法是什么。我们应该如何在系统设计面试中谈论这个？这个问题面试应该接触哪些东西？
我们应该使用正确的组件设计分布式文档搜索系统的正确方法是什么。
好的...这是一个庞大的主题。实际上，elasticsearch 正是为此而做的。但是 google 也是。从 elasticSearch 到 google 搜索存在技术差距。
如果您选择个人实施，它仍然是可能的……但是要像 elasticsearch 一样高效，还有大量工作要做。快速回答是：使用 elasticsearch。
你可能很好奇或者出于某种原因你可能需要自己写。那么它是如何工作的：
TFIDF和余弦距离
正如您首先指定的那样，您将标记化 然后您将标记化的文本表示为向量，然后测量文本和搜索词之间的 angular 距离。
假设在您的语言中只有 3 个单词 "foo, bar, bird" 所以带有 "foo bar bird" 的文本可以用 vector3[1,1,1] 表示
的文本A) "foo foo foo foo bird" 将是 [4,0,1] 另一个
B) "foo bar" [1,1,0]
如果您搜索由 [0,1,0] 表示的 "bar"，您将查找具有最小 angular 距离的文本，如果您计算 angular 你的搜索和 B 之间的距离我认为这是 90°，比 A 低。
实际上语言超过 3 个单词，因此您将计算更多维度的向量中的距离，因为 1 个世界 = 1 个维度:)
TFIDF 代表词频逆文档频率。 这通过该词在所有文档中的频率的倒数来评估文档中词的频率。它的作用是指出文档中的重要词。
让我们解释一下：
- "that, in a the"等词无处不在，不重要
- 在你所有的文本中，"corpus" 这个词出现的频率是我不知道 0.0001%
- 在特定文本中被引用 5 次的频率为 0.1%
- 那么它在语料库中很少见，但相比之下在你的文本中却很重要
- 所以当您搜索 "corpus" 时，您想要的是首先获取出现 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++
在 google 他们以向量占用太多 space 的情况结束，他们需要将它们存储在多台机器上，所以他们发明了 GFS，这是一个分布式文件系统。
多维向量之间的余弦距离计算很耗时，所以我会在GPU上计算，因为GPU对矩阵和向量的浮点运算效率很高。
实际上，重新实现所有这些有点疯狂，希望您有充分的理由这样做，例如一个非常好的商业模式:)
我可能会使用 kubernetes docker 和 mesos 来虚拟化我所有的组件。如果需要大容量，我会寻找类似于 GFS 的东西。 https://en.wikipedia.org/wiki/Comparison_of_distributed_file_systems
您需要取回文本，因此我将使用任何可扩展为任何语言的 NIO 网络服务器。我将使用 nginx 来为静态页面提供服务，并使用 netty 或 vertx 之类的东西来进行搜索，然后将 link 的答案构建到文本中（这取决于你想在一秒钟内为多少用户提供服务）
如果我打算索引比维基百科更大的东西，那么所有这些。如果我打算发明比 elasticsearch 更好的东西（艰巨的任务祝你好运）
例如维基百科，这不到 1T 文本。
终于
如果您使用 elasticsearch 在一周内完成，您可能需要 2 周并投入生产。如果自己做，至少需要1个高级开发人员ad 一名数据科学家一名建筑师，大约一年或更长时间，具体取决于您要索引的文本量。我忍不住问自己 "what is it for".
实际上，如果您阅读lucene 的代码源，您就会确切地知道您需要什么。他们做到了，lucene是elasticsearch的引擎
Twitter 正在使用 Lucene 进行实时搜索