Neil Zhu，简书ID Not_GOD，University AI 创始人 & Chief Scientist，致力于推进世界人工智能化进程。制定并实施 UAI 中长期增长战略和目标，带领团队快速成长为人工智能领域最专业的力量。
作为行业领导者，他和UAI一起在2014年创建了TASA（中国最早的人工智能社团）, DL Center（深度学习知识中心全球价值网络），AI growth（行业智库培训）等，为中国的人工智能人才建设输送了大量的血液和养分。此外，他还参与或者举办过各类国际性的人工智能峰会和活动，产生了巨大的影响力，书写了60万字的人工智能精品技术内容，生产翻译了全球第一本深度学习入门书《神经网络与深度学习》，生产的内容被大量的专业垂直公众号和媒体转载与连载。曾经受邀为国内顶尖大学制定人工智能学习规划和教授人工智能前沿课程，均受学生和老师好评。

Jeff Dean讲述构建大规模信息检索系统的挑战

stanford information search课程报告slides的扩充和展开

为何参与到检索系统的工作中

检索系统面临着科学和工程中的重要挑战，在其中出现大量的有趣却又仍未解决的问题。

这个领域横跨众多计算机科学的子领域，诸如架构、分布式系统、算法、压缩、信息检索、机器学习、UI等。

比起其他系统，检索系统可以扩展得非常大。

而且一个很小的团队就可与你建立起一个让众多人使用的系统。

检索系统的维度

必须平衡各种工程上的冲突：

• 索引的文档的数量
• 美妙的查询
• 索引新鲜度
• 查询延迟
• 为每个文档保持信息
• 打分／检索算法的复杂性／代价

工程上难度基本上等于这些参数的乘积

所有这些都会影响到最终的性能（性能／dollar）

1999 vs. 2014

持续性的改变

参数随着时间变化而改变：通常会按照比较大的数量级进行增长。

在X时的正确的设计到了10X或者100X时就变成重大的错误了：为～10X的增长而设计，而要计划在~100X之前重写。

连续的演变：在过去的10年中有7次重大的更新，通常这些改变不会让用户意识到。

剩下的部分

• Google 搜索系统的演变：几代爬虫、索引、服务系统；支撑架构的简略描述；跟很多很多人一起完成
• 有趣的方向和挑战

Google Circa 1997

索引划分的方式：

1. by doc: 每个shard有保存文档子集的index
   优点：每个shard可以独立地处理查询；比较容易保存额外的文档信息；网络负载（请求和响应）小
   劣势：查询必须在每个shard进行；在N个shard上对Kword查询需要O(K*N)次磁盘查询
2. by word:对所有文档shard存储一个word的子集
   优点：K word 查询 => 由至多K个shard进行处理；对K word查询只需要O(K)磁盘查询
   缺点：需要更多的带宽：对于每个匹配的文档的每个word的数据需要被搜集到一个地方；更难获得关于每篇文档的信息

在我们的计算环境中，by doc更加合理一些

基本原理

文档被分配了小整数id（docids）：如果对于更高质量或者更加重要的文档更好
索引服务器：给定查询返回排序的列表，形式为（score，docid，...）；通过docid进行划分；索引shard被复制；代价O(# queries * # docs in index)
文档服务器：给定(docid, query)产生(title, snippet)；从docid映射到磁盘上的全文本；同样使用docid进行划分；代价是O(# queries)

Corkboards 1999

caching

Cache服务器：cache索引结果和文档的片段；hit rate通常是30-60%：依赖于索引更新的频率，查询负载，个性化的层次，etc
好处：性能！机器可以花费10s来做100s或者1000s的工作；降低查询命中的延迟：命中cache的查询更应该更加热门和昂贵（相同的word，很多闻文档需要进行计算……）
注意：当索引更新或者cache冲洗的时候会出现很大的延迟高峰／容量下降

Crawling（Circa 1998-1999）

简单的批爬取系统：从一些URL开始，爬取页面，抽取链接，添加进queue，当你拥有足够多的页面时停止
考虑因素：不要对任何网站太过粗暴；提升未爬取网页的优先级：不断对变化的图计算PageRank；维护一个高效的未爬取URL队列：保存在一个服务器的划分集合中
处理机器失败

Indexing(circa 1998-1999)

简单的批索引系统：基于简单的unix工具；没有真正的checkpointing，所以机器故障会让人头疼；没有对原始数据的校验和，所以硬件的bit错误会导致问题：
内存对手编程：（programming with adversarial memory）使得我们开发出来一种文件抽象，存储了小记录的校验和，并可以在记录毁坏后跳过和重新同步

Index更新（circa 1998-1999）

基本上一个月进行一次更新：等到网络性能很低时；让一些副本下线；复制新的索引到这些副本上；在更新后的索引上开始新的frontend指向（pointing）和从这里服务一些流量。
索引服务器磁盘：disk的外面部分给予更多的带宽：复制新的索引到disk的内部（同时仍在服务索引）；重启去使用新的索引；去除旧索引；重新拷贝新的索引到disk上更快的部分；去除掉新索引的第一个副本；内部部分现在可以自由地进行高性能数据结构的改造。

Google数据中心（2000）

增加索引大小和查询容量

在｀99 ｀00 ｀01……索引的大小巨大增加：从～50M到1000M page
同时流量也发生巨大增长：每月约20%的增长；Yahoo在2000年7月翻番
索引服务器的性能巨大：不断地部署更多的机器，但是需要约10-30%的基于软件的更新

暗示

shard响应时间受到：必须完成的disk查找的数量；从disk中读出来的数据量
大的性能提升会由更好的disk调度和索引编码的提升完成。

index encoding circa 1997-1999

原始的编码非常简单：
word ＝> docid+nhits:32b || hit: 16b || hit: 16b ||... || docid+nhits: 32b || hit: 16b

• hit: 位置加上属性（字体，名称，等等）
• 最终对大的位置列表使用了跳表这样的数据结构

简单，字节排列格式：解码很容易，但是不是很紧致；需要大量的disk带宽

编码技术

Bit-level：

• N个1接一个0
• Gamma：log_2(N) in unary, then floor(log2(N))
• Rice_k: floor(N/2^k) in unary, then N mod 2^K in K bits: 特例时Golomb编码其中base是2
• Huffman-Int: 如Gamma一样，除了log_2(N)是huffman编码的而不是w/ Unary

字节排列编码：可变的：每个字节7bits后接1bit：0-127:1 byte；128-4095: 2 bytes

基于block的索引格式

基于block，可变长形式降低了空间和CPU的占用：
word ＝> skip table(if large) || Block 0 || Block 1 || ... || Block N

Block格式（N个文档和H命中）：

降低了约30%的索引大小，并且提升了编码的速度

Ever-Wider sharding

当索引大小增加时，使得shard的响应时间保持在一个较低的水平
但是查询的代价随着shard的数目提高了：通常超过1个磁盘查询
当副本的数据增加时，总共的内存的需求量提升：最终，拥有足够的内存来保存整个索引的副本在内存中：急剧地改变了许多设计参数

2001年早期，In-memory索引

很多正面影响：

• 吞吐量的大提升
• 延迟大下降：特别在尾部：代价高的查询（之前需要GB的磁盘I/O）变得更快速。例如［“circle of life”］

一些问题：（page 34）