Google大牛Jeff Dean在ACM的Web搜索和数据挖掘研讨会上的演讲

Google大牛Jeff Dean在WSDM(ACM的Web搜索和数据挖掘研讨会)2009上面的演讲 转自武汉理工UP研发中心

深印象的是,这十年间Google对性能细节的关注,以及他们敏捷的开发模式。

Jeff 给出了从1999年到2009年Google如何成长的几个例子。他们现在拥有1千倍的查询次数。他们现在拥有1千倍的处理能力(机器数量乘以他们的速 度)。而且他们把更新的延迟降低了1万倍,送过去需要数月才能监测到一个Web页面的变化,到现在几分钟即可更新页面的搜索结果。

最后这 一点非常令人印象深刻。Google现在可以非常迅速地监测到很多Web页面的变化,计算这个页面的近似静态排名,并把索引的更新发布出去。对许多页面来 说,搜索结果可以在页面变化数分钟后更新。要做到这点需要解决几个困难的问题–重复抓取的频率和重要度,PageRank的快速近似计算,一个允许快速 更新索引的架构–看来这些问题他们都解决了。

他们的性能改进也令人惊讶,现在显示每个页面的时间是200ms以下。Jeff提到从几年前起,现在绝大多数的索引是完全保存在内存中的。也就是说现在每个查询不是由几十个机器,而是由上千个机器处理的,Jeff说这是值得的,这令每个搜索者可以立即就看到搜索结果。

Google 对细节的注意是可圈可点的。Jeff描述了他们这些年创造和使用过的几种索引压缩技术。他讲到他们如何最后决定了一种格式,4×3的位置信息有序地组合在 一起(By Tiny:原文是a format that grouped four delta of positions together in order,这句我不确定翻译的准确性,因为我没有看明白),这样就可以把压缩过程中需要的移位操作次数降到最低。Jeff说道,他们总是很注意他们的数 据在磁盘上的组织方式,把他们需要快速流读取的数据总是放置在硬盘的外圈,而冷门数据,或者短读取的数据放在磁盘的内圈。他们为没有校验的内存写自己的错 误恢复软件。他们写了自己的硬盘规划器。他们不断地修改Linux内核去满足他们的需求。我们先是设计自己的没有外壳的服务器,然后切换到现成的标准的服 务器,现在他们又转向设计自己的没有外壳的定制服务器了。

Google的敏捷同样令人难忘。Jeff说10年间,他们已经进行过7次主要 的架构升级。这些变化通常牵扯到完全不同的索引格式,或者全新的存储系统例如GFS和BigTable。在一些切换中,他们甚至做到了,在新的数据中心运 行着新的代码,旧的数据中心运行这旧的代码,并在这些数据中心间切换用户的访问。每天,搜索用户持续地接受用户体现方面细微的变化,测试新的代码。 Google的切换安静而快速,用户不会注意到任何变化。

原始的计算能力的地位已经摇摇欲坠了–现在可以用数千个机器为一个请求服务 –虽然这一切看起来那么不可思议。Jeff说,Google机器翻译模型翻译一个句子的时候,会对一个数T的模型进行上百万词的查找。他接着 说,Google的目标是不管你使用什么语言,让你可以读懂任何语言描述的任何信息。这需要的运算量难以计算,看起来这么巨大的运算量可能令所有其他人都 只能战战兢兢的呼喊Google(Tiny:原文The amount of processing required is difficult to fathom, yet it seems the kind of computational mountain that might cause others to falter calls out to Googlers.,说不好这句)。

——云时代的分割线——

Geeking with Greg还提到了,Michael Bendersky该演讲的笔记,下面也大略翻译如下:

1999年到 – 2009年规模的变化

  • 100倍文档数
  • 10000倍查询数(这里Geeking with Greg和Michael Bendersky的数据有出入)
  • 更新速度快了1万倍
  • 查询延迟从小于1秒到大于0.2秒,快了5倍

10倍增长的时候设计的搜索引擎,100倍增长时重新了系统。然后,他粗略描述了从90年代后期开始抓取和索引发生的变化。下面是一些要点。

90年代后期

  • 批量抓取系统,抓到“足够”的页面后停止。
  • 批量索引和Unix工具协同工作。减少了机器失效和数据不一致性。
  • 原始的97索引格式就是简单的字节对齐的系统,包含编码的字段和词频信息。这需要大量的磁盘访问。

之后不久

  • 迁移到新的基于块的变长索引格式,附带高频词跳表。这令索引尺寸小了30%,而且解码更快。
  • 加入结果和文档摘要的缓存服务器。
  • 2001年前期,他们迁移到一个内存索引架构,索引服务器()可以直接和前端服务器沟通。
  • 索引按文档分割而不是按词分割。

最近和当前

  • 从头开始内部设计:机架设计,Pc级主板,Linux,内部软件(GFS,BigTable,等等)
  • 用MapReduce架构来构建索引
  • 2004年他们迁移到一个层级系统来处理索引,这个系统构建在基于GFS的索引之上(现在只有“根级服务器”处理来自Web服务器的请求)
  • 快速索引更新
  • 2007年他们加入超级根服务器,跟所有的垂直信息索引服务器通讯,构建全能搜索(Universal Search)服务。

Google如何实验排序的改变
目标: 要易于通过实验验证。

  1. 从一个新的排名思想开始
  2. 用MapReduce,BigTable等快速生成实验所需数据
  3. 离线运行,并在(1)人工指定的不同类型的查询 (2) 在随机的查询,上看与现有排名算法的差异(不考虑延迟)
  4. 重复…
  5. 在一个小的随机的访问样本中实验(要考虑延迟!)
  6. 重新实现/调节实现,重新计算数据,要令计算全部数据的时间可行,并把所有需要的其他的数据加入到索引

未来的挑战

  • 跨语言检索 – 质量和架构可伸缩性
  • 检索隐私的,半公开的,共享的以及完全公开的文档
  • 自动构建高效的满足不同需求的信息检索系统

文章录入:kushaoping    责任编辑:kushaoping   原文地址:http://up.whut.edu.cn/Article/ShowArticle.asp?ArticleID=231