如何用可忽略的延迟返回巨大的数据库中的查询？

Question

例如，当在Google中搜索某些内容时，结果会在即时返回。

我了解Google用算法等分类和索引页面，但是我认为对每个可能的查询的结果索引（并且结果是个性化的，这使得这更加不可行）是不可行的吗？

此外，Google硬件中的硬件延迟难道不是很大吗？即使Google中的数据都存储在TB/S SSD中，我想硬件延迟将是巨大的，鉴于要处理的数据量庞大。

MapReduce有助于解决这个问题吗？

编辑：好的，所以我知道可以在内存中缓存流行的搜索。但是，不受欢迎的搜索呢？即使是我进行的最晦涩的搜索，我认为据报道搜索量超过5秒。这怎么可能？

Answer 1

好吧，我不确定是否是MapReduce解决了问题，但是肯定不会单独使用MapReduce来解决您提出的所有这些问题。但这是要考虑的重要事情，这使得 可行的 在不同机器中所有这些数据的查询中的查询延迟如此之低：

1. 分布式计算：通过分发并不意味着这些索引只是简单地分布在不同的机器中，实际上它们沿不同的群集复制，这允许许多用户执行不同检索时间的不同查询（是的，庞大的公司可以负担得起这么多的费用机器）；
2. 缓存：缓存可大大减少执行时间，无论是爬行步骤，检索页面还是为结果的排名和驱逐；
3. 大量调整：以上所有和非常有效的算法/解决方案只有在实施也有效的情况下才能有效。有很多（硬编码）的优化，例如参考，压缩，缓存的局部性；所有这些通常都适用于处理的不同部分。

考虑到这一点，让我们尝试解决您的问题：

但是我认为每个可能的查询的结果都不可可

是的，这将是，实际上是不可行的 每个可能的查询. 。世界上有无限数量的术语（即使您假设只能输入正确拼写的术语），并且从这些术语中也有指数级的查询数量 n -> inf 条款（（2^n）。那做了什么？缓存。但是，如果有很多查询/结果，哪些结果要缓存？缓存政策。最常见/流行/相关的用户查询是缓存的查询。

Google硬件中的硬件延迟不会巨大吗？即使Google中的数据都存储在TB/S SSD中

如今，借助如此高度发达的处理器，人们倾向于认为必须在几秒钟（或更少）内完成的每项可能完成的任务，并处理如此多的数据，必须由具有多个内核和大量内存的极强大的处理器处理。但是，一件事 裁决 市场是金钱，投资者对浪费不感兴趣。那做了什么？

偏好实际上是为了拥有很多机器，每台机器都使用简单/可访问的处理器（就成本而言），这降低了建立众多群集的价格。是的，它确实有效。如果您考虑简单的测量，主瓶颈总是归结为磁盘 表现. 。但是，一旦有很多机器，就可以负担得起将物品加载到主内存中，而不是在硬盘上工作。

存储卡是 昂贵的 对我们来说，仅仅是人类，但对于一次购买许多此类卡的企业来说，它们非常便宜。由于它的成本不高，因此根据需要有很多内存来加载索引并保持缓存并不是问题。而且，由于机器太多，因此无需超快速处理器，因为您可以将查询引导到不同的地方，并且有许多机器负责参加的机器 特定地理区域, ，这允许更多 专门 数据缓存，甚至更好的响应时间。

MapReduce有助于解决这个问题吗？

尽管我认为使用或不使用MapReduce是Google内部的限制信息，但我并没有对此表示敬意。但是，Google实施了MapReduce（这肯定是 不是 Hadoop）必须具有许多优化，许多涉及上述方面。因此，MapReduce的体系结构可能有助于指导计算如何物理分布，但是还有许多其他要点可以证明查询时间的速度合理。

好的，所以我知道可以在内存中缓存流行的搜索。但是，不受欢迎的搜索呢？

下图显示了如何 种类 发生查询。您会看到有三种主要的搜索类型，每个搜索都持有大约1/3的查询体积（曲线以下区域）。该情节显示了权力法，并加强了较小的查询是最受欢迎的事实。第二三分之一的查询仍然可以处理，因为它们容纳了几句话。但是一组所谓的 晦涩的查询, 通常由未经经验的用户的查询组成，不是查询中可忽略的一部分。

并有新的解决方案的空间。由于不仅是一个或两个查询（但其中三分之一），它们必须有 相关的 结果。如果您输入某物 太晦涩了 在Google搜索中，返回结果列表并不需要更长的时间，但是很可能会向您展示某些内容 推断 你想说的。或者它可能只是说明没有具有这样的术语的文档 - 甚至将您的搜索切成32个单词（在这里只是在我的随机测试中发生在我身上）。

有数十种应用启发式方法，可能要么忽略某些单词，要么试图将查询分解为较小的询问，并收集最多的查询 受欢迎的 结果。所有这些解决方案都可以量身定制和调整以尊重 可行的等待时间 例如，一秒钟？ ：d

Answer 2

MapReduce与实时的任何事物无关。它是一个面向批处理的处理框架，适用于某些离线任务，例如ETL和索引构建。 Google现在已经从MapReduce转移了大多数工作，甚至Hadoop生态系统也在做同样的工作。

低延迟的答案通常是将预先计算的索引保持在内存中。任何接触磁盘的东西都很难快速和扩展。这就是新一代基于Hadoop的SQL引擎喜欢的方式 黑斑羚 与基于MapReduce的基础架构相比，要获得如此多的速度 蜂巢, ， 例如。

搜索基础架构不能缓存每个查询的结果。但是，它肯定可以缓存中间结果，或者可以为顶级查询而进行更完整的结果。有了一点缓存，您可以为所有查询的少数族裔提供结果。

搜索也分为跨服务器。因此，一台机器可以将其委派给每个结果的一部分，然后将它们组合在一起。

您也可以通过一定程度的近似值摆脱。 Google并没有形成一千页的搜索结果；它只需要获得关于正确的第一页即可。

请记住Google有 百万 全球计算机。您的疑问将在您附近的地理位置上到达数据中心，这仅为您的地理位置。这切断了大部分延迟，这是网络，而不是在数据中心处理时间。

Answer 3

MapReduce不用于搜索。它是很久以前用来构建索引的。但这是一个批处理处理框架，大多数网络都不会一直在改变，因此较新的体系结构都是 增加的 而不是面向批处理。

在Google中进行的搜索将在很大程度上工作于Lucene和Lucene搜索中的作品，除了很多微调的额外权重和优化。但是，他们将使用某种形式的 倒立索引. 。换句话说，他们确实 不是 输入搜索查询时（即使没有缓存）搜索几个Terabytes。他们可能根本不看实际文件。但是他们使用的是一个查找表，该表列出了哪些文档匹配您的查询术语（带有词干，拼写错误，同义词等，都已预处理）。他们可能取回 列表 在每个单词的前10000个文档中（10k整数 - 只有几个kb！），并从中计算出最佳匹配。只有在这些列表中没有好的匹配项时，它们才会扩展到下一个这样的块等。

通用单词的查询很容易缓存；通过预处理，您可以构建前10K结果的列表，然后根据用户配置文件重新读取它们。通过计算“确切”答案，没有什么可获得的。查看前10K的结果可能就足够了；没有正确的答案；而且，如果错过了位置10001位置的更好结果，则没有人知道或注意到（或关心）。它很可能已经在预处理中排名，并且不会将其列入最终向用户展示的前十名（或者前三名，用户实际上是查看的）

另一方面，罕见的术语也不是一件挑战 - 其中一个列表仅包含一些匹配的文档，您可以立即丢弃所有其他文件。

我建议阅读本文：

大型高文本网络搜索引擎的解剖结构
谢尔盖·布林和劳伦斯页面
加利福尼亚州斯坦福大学斯坦福大学计算机科学系94305
http://infolab.stanford.edu/~backrub/google.html

是的，那是写这篇文章的Google创始人。这不是最新的状态，但它已经很大程度上了。