The Anatomy of a Large-Scale Hypertextual Web

wangfans

我们的压缩编码每个命中用到两个字节(byte)。有两种命中：特殊命中（fancy hit）和普通命中（plain hit）。特殊命中包括在URL，标题，锚文本和meta标签上的命中。其他的都是普通命中。一个普通的命中包括一个表示大小写的比特(bit)，字体大小，和12个bit表示的单词在文件中的位置（所有比4095大的位置都被标示为4096）。字体在文档中的相对大小用3个比特表示（实际上只用到7个值，因为111标示一个特殊命中）。

wangfans

一个特殊命中包含一个大小写比特，字体大小设置为7用来表示它是一个特殊命中，4个比特用来表示特殊命中的类型，8个比特表示位置。对于锚命中，表示位置的8个比特被分成两部分，4个比特表示在锚文本中的位置，4个比特为锚文本所在docID的哈希（hash）值。由于一个词并没有那么多的锚文本，所以短语搜索受到一些限制。我们期望能更新锚命中的存储方式能让位置和docID哈希值能有更大的范围。我们使用在一个文档中的相对字体大小是因为在搜索时，你并不希望对于内容相同的不同文档，仅仅因为一个文档字体比较大而有更高的评级（rank）。

wangfans

   命中列表的长度存在命中的前面。为了节省空间，命中列表的长度在正向索引中与wordID结合，在反向索引中与docID结合。这样就将长度分别限制在8个比特和5个比特（有一些技巧可以从wordID中借用8个比特）。如果长度超过了这个范围，会在这些比特中使用转义码，在接下来的两个字节(byte)里才存放真正的长度。

wangfans

4.2.6 正向索引
正向索引实际上已经部分排序。它被存放在一系列的桶（barrels）里面（我们用了64个）。每个桶保存了一定范围内的wordID。如果一个文档包含了属于某个桶的单词，它的docID将被记录在桶里面，后面接着一个wordID的列表和相应的命中列表。这种结构需要一点多余空间，因为存储了重复的docID，由于桶的数量很小，所以存储空间的差别很小，但是它能在排序器（sorter）建立最终索引的时候大大节省时间并降低了程序复杂度。更进一步，我们并没有存储完整的wordID，而是存储每个wordID相对于其对应的桶里面最小wordID的差距。这样我们只用到了24个比特，从而为命中列表长度（hit list length）留出了8个比特。

wangfans

4.2.7 反向索引
反向索引与正向索引有着相同的桶，但是它们是先经过排序器处理过的。对每一个合法的wordID，词典包含了一个指向对应的桶的指针。它指向一个docID的列表和相应的命中列表。这个文档列表显示了有这个单词出现的所有文档。

wangfans

一个重要的事情是如何对这个文档列表排序。一个简单的方法是按照docID排序。在多个单词的查询中，这种方法可以快速地完成两个文档列表的归并。另一种方案是按照这个词在文档中出现的评分(ranking)排序。这种方式使得单个词的查询相当简单，并且多词查询的返回结果也很可能接近开头。但是，归并要困难得多。而且，开发也会困难得多，因为每次评分函数变动就需要重新建立整个索引。我们综合了两种方案，设计了两个倒排桶集合——一个集合只包括标题和锚命中，另一个集合包含所有的命中。这样我们首先检查第一个桶集合，如果没有足够的匹配再检查那个大一点的

wangfans

4.3抓取网页

运行网络爬虫是一项很有挑战性的任务。这里不光涉及到巧妙的性能和可靠性问题，更重要的，还有社会问题。抓取是一个很脆弱的应用，因为它需要与成百上千各种各样的web服务器和域名服务器交互，这些都不在系统的控制范围之内。

wangfans

为了抓取几亿网页，Google有一个快速的分布式爬虫系统。一个单独的URL服务器（URLserver）为多个爬虫(crawler,一般是3个)提供URL列表。URL服务器和爬虫都用Python实现。每个爬虫同时打开大概300个连接。这样才能保证足够快地抓取速度。在高峰时期，系统通过4个爬虫每秒钟爬取100个网页。这大概有600K每秒的数据传输。一个主要的性能压力在DNS查询。每个爬虫都维护一个自己的DNS缓存，这样在它抓取网页之前就不再需要每次都做DNS查询。几百个连接可能处于不同的状态：查询DNS，连接主机，发送请求，接受响应。这些因素使得爬虫成为系统里一个复杂的模块。它用异步IO来管理事件，用一些队列来管理页面抓取的状态。

wangfans

事实证明，爬虫连接了50多万个服务器，产生了几千万条日志信息，会带来大量的电子邮件和电话。因为很多人在网上，他们并不知道爬虫是什么，因为这是他们第一次见到。几乎每天，我们都会收到这样的电子邮件：“哇，你看了好多我站上的页面，你觉得怎么样？”也有很多人并不知道爬虫禁用协议（robots exclusion protocol），他们认为可以通过在页面上声明“本页面受版权保护，拒绝索引”就可以保护页面，不用说，网络爬虫很难理解这样的话。而且，由于涉及到大量的数据，一些意想不到的事情总会发生。

wangfans

比如，我们的系统试图去抓取一个在线游戏。这导致了游戏中出现大量的垃圾消息！这个问题被证实是很容易解决的。但是往往我们在下载了几千万个页面之后这个问题才被发现。因为网络页面和服务器总是在变化中，在爬虫正式运行在大部分的互联网站点之前是不可能进行测试的。不变的是，总有一些奇怪的错误只会在一个页面里面出现，并且导致爬虫崩溃，或者更坏，导致不可预测的或者错误的行为。需要访问大量互联网站点的系统需要设计得很健壮并且小心地测试。因为大量像爬虫这样的系统持续导致问题，所以需要大量的人力专门阅读电子邮件，处理新出现遇到的问题。