谷歌怎么这么快？

有哪些技术和编程决策可以让Google能够如此快速地为查询提供服务？

每当我搜索某些东西(每天几次中的一次)时,我总是惊讶于他们如何在接近或不到1秒的时间内提供结果.他们可以采用哪种配置和算法来实现这一目标？

旁注:有点压倒性的想法,即使我要放置桌面应用程序并在我的机器上使用它可能也不会像谷歌快一半.继续学习我说.

---

以下是一些很棒的答案和指示:

谷歌平台

地图减少

算法精心制作

硬件 - 集群农场和大量廉价计算机

缓存和负载平衡

谷歌文件系统

HenryR.. 47

磁盘访问会导致延迟被终止.因此,有理由相信用于回答查询的所有数据都保存在内存中.这意味着成千上万的服务器,每个服务器复制许多分片中的一个.因此,搜索的关键路径不太可能击中他们的任何旗舰分布式系统技术GFS,MapReduce或BigTable.这些将用于粗略地处理爬虫结果.

关于搜索的一个方便的事情是,不需要具有强烈一致的结果或完全最新的数据,因此不会阻止Google响应查询,因为更新的搜索结果已经可用.

因此,可能的架构非常简单:前端服务器处理查询,对其进行规范化(可能通过删除停用词等),然后将其分发给拥有该部分查询空间的任何副本子集(另一种架构是分割通过网页获取数据,以便每个查询都需要联系每个副本集中的一个.可能会查询许多复制品,并且最快的响应会获胜.每个副本都有一个索引映射查询(或单个查询术语)到文档,它们可以用来非常快速地在内存中查找结果.如果从不同的源返回不同的结果,前端服务器可以在它吐出html时对它们进行排名.

请注意,这可能与谷歌的实际操作有很大不同 - 他们将设计这个系统的生命,因此在奇怪的区域可能有更多的缓存,奇怪的索引和某种时髦的负载平衡方案以及其他可能的差异.

1> HenryR..：

---

磁盘访问会导致延迟被终止.因此,有理由相信用于回答查询的所有数据都保存在内存中.这意味着成千上万的服务器,每个服务器复制许多分片中的一个.因此,搜索的关键路径不太可能击中他们的任何旗舰分布式系统技术GFS,MapReduce或BigTable.这些将用于粗略地处理爬虫结果.

关于搜索的一个方便的事情是,不需要具有强烈一致的结果或完全最新的数据,因此不会阻止Google响应查询,因为更新的搜索结果已经可用.

因此,可能的架构非常简单:前端服务器处理查询,对其进行规范化(可能通过删除停用词等),然后将其分发给拥有该部分查询空间的任何副本子集(另一种架构是分割通过网页获取数据,以便每个查询都需要联系每个副本集中的一个.可能会查询许多复制品,并且最快的响应会获胜.每个副本都有一个索引映射查询(或单个查询术语)到文档,它们可以用来非常快速地在内存中查找结果.如果从不同的源返回不同的结果,前端服务器可以在它吐出html时对它们进行排名.

请注意,这可能与谷歌的实际操作有很大不同 - 他们将设计这个系统的生命,因此在奇怪的区域可能有更多的缓存,奇怪的索引和某种时髦的负载平衡方案以及其他可能的差异.

2> Vasil..：

---

将它放在一个答案中有点太多了. http://en.wikipedia.org/wiki/Google_platform

3> Konrad Rudol..：

---

我离开的一个事实发现有趣的是,谷歌实际上是由生物信息学运行的('凯,我发现这很有趣,因为我是生物信息......).让我解释.

早期的生物信息学面临着以极快的速度搜索巨大字符串中的小文本的挑战.对我们来说,"巨大的弦"当然是DNA.通常不是单个DNA,而是来自不同物种/个体的几个DNA的数据库.小文本是蛋白质或它们的遗传对应物,基因.计算生物学家的大部分首要工作仅限于发现基因之间的同源性.这样做是为了通过注意与已知基因的相似性来建立新发现的基因的功能.

现在,这些DNA字符串确实非常大,并且(有损!)搜索必须非常有效地完成.因此,大多数现代字符串查找理论都是在计算生物学的背景下发展起来的.

然而,很久以前,传统的文本搜索已经筋疲力尽.需要一种新方法,允许在次线性时间内搜索大字符串,即不查看每个单个字符.发现这可以通过预处理大字符串并在其上构建特殊的索引数据结构来解决.已经提出了许多不同的这种数据结构.每个都有自己的优点和缺点,但有一个特别值得注意的是因为它允许在恒定时间内查找.现在,在谷歌运营的数量级上,这已不再严格,因为必须考虑服务器之间的负载平衡,预处理和其他一些复杂的东西.

但实质上,所谓的q-gram索引允许在恒定时间内进行查找.唯一的缺点:数据结构变得非常大.本质上,为了允许查找最多q个字符的字符串(因此名称),它需要一个表,每个可能的q个字母组合都有一个字段(即q ^S,其中S是字母表的大小)比方说36(= 26 + 10)).此外,索引字符串中的每个字母位置必须有一个字段(对于每个网站,在谷歌的情况下).

为了缓解庞大的规模,谷歌可能会使用多个索引(事实上,他们这样做,以提供诸如拼写校正服务).最顶层的不会在字符级别上工作,而是在字级上工作.这减少了q,但它使S无限大,因此它们必须使用散列和碰撞表来处理无数个不同的单词.

在下一个级别,这些散列的单词将指向其他索引数据结构,这些结构反过来将散列指向网站的字符.

简而言之,这些q -gram索引数据结构可以说是谷歌搜索算法最核心的部分.不幸的是,没有好的非技术性论文解释q -gram索引是如何工作的.我所知道的唯一一本包含对这样一个索引如何运作的描述的出版物是......唉,我的学士论文.

---

我在生物信息学领域工作了5年,之后是搜索引擎 - 而且q-gram并不像你想象的那么重要.Google所做的那种查找的基本数据结构(在非常非常基础的层面上)是倒排索引.

4> Jorge Ferrei..：

---

以下是一些很棒的答案和指示:

谷歌平台

地图减少

算法精心制作

硬件 - 集群农场和大量廉价计算机

缓存和负载平衡

谷歌文件系统