第五章 5.4 PageRank算法改进 Improvement for PageRank Algorithm

PR算法的复杂度规模是log(n)，n是网页的数量。网页权值在算法执行过程中是一个振荡收敛的过程，这其中有两个主要矛盾：1.节点的数量巨大，内存成为瓶颈之一。2.巨大的2维矩阵每次计算消耗时间巨大，时间效率上也是瓶颈；其中大部分网页的权值比较低，而且都是浮点数计算。

改进思路一：迭代计算的次数和矩阵的规模（链接的个数）有一定的比例关系，例如322M个链接需要52.5次迭代，161M个链接需要45次迭代。可以省略算法中矩阵中作减法操作的时间。

改进思路二：分而治之，对一个独立域名下的网页权值独立计算。比如http://www.zju.edu.cn下的子域名在爬虫抓取数据的过程中独立地计算相对网页权值，记作PR-R。然后再以域名为单位，做全局域名之间的权值计算，得出域名对应的权值PR-T。所以，最后域名下各个页面的权值等于PR-R×PR-T。

改进思路三：采用加速收敛的方法。每次迭代都会得到一个n维偏移向量p，但是取偏移为p^k（k>1）作为此次迭代的偏移向量。

改进思路四：减少计算量。对大量的权值低于一定限值的网页，计算过程中忽略其链接产生的权值分配。

第五章 5.3 影响排名的其他因素 Other Factors

域名中以gov，edu，org结尾的网站应该具有较高的网页权值。Gov是政府网站后缀，edu是教育机构，org指非盈利的组织。

搜索引擎的基本设计思路是若干个结果去覆盖相应用户需求，其中可能有大量不相关的内容存在，如果使得比较优质的结果保留下来，并且能使得后面使用的用户能方便地搜索到？点击率成了重要的判断数据。因此，上一节中提到的得分公式变为Score(A) = PageRank(A) × β + ∑M’ * i * j + CTR。这样一来，保证了优质的结果能长期占据搜索结果第一页的位置。

其中，CTR的数据来源由两部分组成：

1) 搜索列表页面中的点击记录。

2) Toolbar（Google）跟踪到的用户访问网页的频率，以及这些目标网页中链接的点击记录。

如果同一个网站多个页面都占据了第一页的结果，会造成搜索结果的不公正，需要对同一个网站的其他页面乘以一个衰减系数，调整第一页排名网站的构成。

对于排名优化的作弊网站，需要跟踪其在搜索引擎中得到流量的表现情况。如果作弊程度严重的，给予一定惩罚。

第四章 4.3 分词原理 Chinese Word Parsing Algorithm

对索引网页信息的预处理包括网页分析和倒排文件索引两个部分，中文自动分次是网页分析的前提。文档由被称作特征项的索引词组成，网页分析是将一个文档表示 为特征项的过程。在提取特征项时，中文又面临了与英文处理不同的问题。中文信息和英文信息有一个明显的差别：英语单词之间用空格分隔；而在中文文本中，词 与词之间没有天然的分隔符，中文词汇大多是由两个或两个以上的汉字组成的，并且语句是连续书写的。这就要求在对中文文本进行自动分析前，先将整句切割成小 的词汇单元，即中文分词（或中文切词)。

用具体例子来说明，就是如何把“我的笔记本”这样连续书写的语句切分为“我”，“的”和“笔记本”三个词汇单元。 在检索和文档分类系统中，自动切词系统的速度影响整个系统的效率。中文信息的检索主要有两种：基于字的检索和基于词的检索。基于单字的检索系统建立单字索 引。在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索结果。而基于词汇的检索系统对词汇建立索引，检索词汇时一次命中。

1、算法介绍

自动分词的基本方法有：基于字符串匹配的分词方法和基于统计的分词方法。

基于字符串匹配的分词方法

这种方法又称为机械分词方法，它是按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方长度优先匹配的情况，可以分为最大或最长匹配，和最小或最短匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：

1) 正向最大匹配；

2) 逆向最大匹配；

3) 最少切分（使每一句中切分出来的词数最小）

还可将上述各种方法相互组合，例如，可以将正向最大匹配方法和你想最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245（这可能是因为汉语的中心语靠后的特点）。对于机械分词方法，可以建立一个一般的模型，形式地表示为ASM(d,a,m)，即Automatic Segmentation Model，其中，

d：匹配方向，+表示正向，-表示逆向；

a：每次匹配失败后增加或减少字串长度（

m：最大或最小匹配标志，+为最大匹配，-为最小匹配。

例如，ASM(+, -, +)就是正向减字最大匹配法（Maximum Match based approach, MM），ASM(-, -, +)就是逆向减字最大匹配法(简记为RMM方法)，等等。对于现代汉语来说，只有m=+是实用的方法。

2、基于统计的分词方法

从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。计算汉字X和Y的互现信息公式为：

其中P(X, Y)是汉字X、Y的相邻共现概率，P(X)、P(Y)分别是X、Y在语聊中出现的概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 词汇切分算法最重要的指标是准确，在兼顾准确性的情况下也要考虑时间复杂性。下面具体介绍正向减字最大匹配法。

2、正向减字最大匹配法

正向减字最大匹配法切分的过程是从自然语言的中文语句中提取出设定的长短字串，与词典比较，如果在辞典中，就算一个有意义的词串，并用分隔符分隔输出，否则缩短字串，在词典中重新查找（辞典是预先定义好的）。

算法要求为：

输入：中文词典，待切分的文本d，d中有若干被标点符号分割的句子s1，设定的最大词长MaxLen。

输出：每个句子sl被切为若干长度不超过MaxLen的字符串，并用分隔符分开，记为s2，所有s2的连接构成d切分之后的文本。

算法思想:事先将网页预处理成每行是一个句子的纯文本格式。从d中逐句提取，对于每个句子s1从左向右以MaxLen为界选出候选字串w，如果w在词典中，处理下一个长为MaxLen的候选字段：否则，将w最邮编一个字去掉，继续与辞典比较：s1切分完之后，构成词的字符串或者此时w已经为单字，用分隔符隔开输出给s2。从s1中减去w，继续处理后续的字串。s1处理结束。

设文本含有句子的书目为m，句子的平均长度为k，辞典的条目为n。实际中m和k远远小于n，整个算法复杂度中起决定作用的步骤在于n相关的语句。因此算法的时间复杂度为O(mklogn)。

第五章 5.2 得分规则 An Simple Scoring Rule

出现关键词频度初始得分表

同一位置频度	1	2-3	4-7	8	9	>10
得分m	2	4	8	8	3	1

出现的位置初始得分表

位置	标题	段首	段尾	其余正文	URL	其他
得分比i	0.9	0.6	0.6	0.3	0.4	0.2

网页更新频度得分表

距查询的时间	一天	一天至三天	三天以后
得分比j	1.1	1.0	0.9

容易得出网页A的得分简单的计算公式

Score(A) = PageRank × β + ∑m × i × j

其中β是衰减系数，降低PageRank对最后排名的影响。

但是这么做有一个明显的缺陷，一个内容比较长的网页比一个内容比较短的网页在排序过程中有绝对的优势，即m的取值不够恰当，并且实际中并非重复出现的关键词就意味着高的相关度。那么如果做呢？我们需要根据网页的长度，对关键词的次数进行归一化， 也就是用关键词的次数除以网页的总字数。我们把这个商称为“关键词的频率”，或者“单文本词汇频率”（Term Frequency)，比如，在某个一共有一千词的网页中keyword_1和keyword_2分别出现了12次和5次，那么它们的词频就分别是 0.012和 0.005。 我们将这两个个数相加，其和 0.017 就是相应网页和查询keyword_1和keyword_2相关性的一个简单的度量。概括地讲，如果一个查询包含关键词 w1,w2,...,wN, 它们在一篇特定网页中的词频分别是: TF1, TF2, ..., TFN。 （TF: term frequency)。 那么，这个查询和该网页的相关性M就是:TF1 + TF2 + ... + TFN。于是，得分规则变为Score(A) = PageRank × β + ∑M × i × j。

现在看来的得分公式还是有一个比较大的缺陷，直觉告诉我们相关性实质上是文章主题的相关性体现，从关键词的词频为主要入口还是有欠考虑到同时出现这些关键词之间的文章怎么突出他们之间的得分差异。如果一个关键词只在很少的网页中出现，通过它就容易限定搜索目标，它的权重也就应该大。反之如果一个词在大量网页中出现，我们看到它仍然不很清楚要找什么内容，因此它的权重应该小。概括地讲，假定一个关键词 w 在 Dw 个网页中出现过，那么 Dw 越大，w 产生的相关性权重越小，反之亦然。在信息检索中，使用最多的权重是“逆文本频率指数” （Inverse document frequency 缩写为IDF），它的公式为log(D/Dw)其中D是全部网页数。于是上述相关性计算个公式就由词频的简单求和变成了加权求和，即M’ = TF1*IDF1 + TF2*IDF2 ＋... + TFN*IDFN。因此，得分计算公式改进为：Score(A) = PageRank × β +∑M’ × i × j。

第五章 5.1 网页等级算法全面阐释 Analysis of PageRank Algorithm

互联网发展早期的搜索引擎，对web页面的排序，是根据搜索的词组（短语）在页面中的出现次数，并用页面长度和html标签的重要性提示等进行权重修订。链接流行度技术通过其它文档链接到当前页面链入数量来决定当前页的重要性，这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。PageRank计算页面的重要性，对每个链入赋以不同的权值，链接提供页面的越重要则此链接入越高。当前页的重要性，是由其它页面的重要性决定的。一个网页的重要性是一种内在的主观事情,这取决于读者兴趣,知识和态度. 但仍有许多可说是客观的相对重要性的网页. 简单地介绍如何给网页评级,有效衡量人们对网页的兴趣和重视程度。

PageRank的数学定义:

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中：PR(A):页面A的网页级别,
PR(Ti)：页面Ti的网页级别，页面Ti链向页面A，
C(Ti)：页面Ti链出的链接数量，
d：阻尼系数，取值在0.85－0.95之间，一般取值为0.85，此因素直接影响迭代计算PageRank过程中的收敛速度

由此可见，1）这个算法不以站点排序，页面网页级别由一个个独立的页面决定；2）页面的网页级别由链向它的页面的网页级别决定，但每个链入页面的贡献的值 是不同的。如果Ti页面中链出越多，它对当前页面A的贡献就越小。A的链入页面越多，其网页级别也越高；3）阻尼系数的使用，减少了其它页面对当前页面A 的排序贡献。

公式的来历：Google公司的创始人Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型，来解释上述算法。他们把用户点击链接的行为，视为一种不关心内容的随机行为。而用户点击页面内的链接的概率，完全由页面上 链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼 系数d的引入，是因为用户不可能无限的点击链接，常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率，（1－d）则就是页面本身所具有的 网页级别。PageRank的计算是封闭流通模型，所有页面的网页级别之和等于网页初始级别的和。

容易从PageRank的数学定义得出一个恒等表达式：

p = A p

其中p表示网页级别向量，A是链接矩阵。

求网页等级的问题转化为求A的特征向量，于是可以用迭代的方法求出。

给定任意一个初始向量S，不妨设为A，PageRank的计算可以如下

R₀ = S

Loop:

R_i+1 = A R_i

d = ||R_i||₁ - ||R_i+1||₁

R_i+1 = R_i+1 + dE

δ = ||R_i+1 - R_i||₁

while δ > ε

参数d表示迭代的收敛速度，一般取值为0.85。因为链接矩阵巨大，所以改进该算法的瓶颈在于无法用空间换取效率的做法，只有在精度和效率之间作折衷。

第五章 排序规则 Ranking Rules

用户输入查询关键词的时候需要对结果集作排序，如何排序这些网页使得最佳的结果呈现在前二十条结果中呢？主要因素有网页等级，关键词位置、关键词出现频率，用户点击日志等。

第四章 4.2 倒排索引基本原理 Principle of Inverted Index

Trie是效率最高的索引形式，下图表示由文本到的前缀树的创建过程。

插入操作的时间复杂度O(l)，其中l = max(length of word)；

查询的操作的时间复杂度O(l)；

删除操作的复杂度为O(n)，其中n = length of dictionary

Trie有消耗了大量内存且难以分块的缺点，同时伴随着I/O和瓶颈，一般来说用分块的倒排索引来解决内存不足问题，最后对分块的索引块做一次归并。倒排索引一般分成两个文件来存储，其中一个称为位置文件，纪录了词出现的文档和位置信息；另外一个是词典文件，纪录索引文本出现过的词，按照字符的顺序来存储。其中每个词有个指针，表示对应了第一个文件中的那个纪录。这样的结构保证了检索的时候词典能被保存在内存中，进一步的意义在于，检索词出现在哪些文档中以及位置能被迅速地找到。用一个例子来说明，有个这样的句子该怎么索引？
Tom lives in Guangzhou, I live in Guangzhou too.
分析过后剩下为
tom live guangzhou I live guangzhou
从词的角度出发一共有五个词，可以得出这样的一张词表

name	position	frequency
tom	1	1
live	5,22	2
guangzhou	10,27	2
i	20	1

文本的内容经过分析之后抽取出的内容见上表，即索引文件的内容，可以加对表的内容压缩存储优化，通常只对位置字段做差分压缩，最后将内容按照存储格式存储起来。

归并两个索引需要归并排序词典文件和合并位置文件：如果词典中的词不相同，连接相应的位置文件内容；如果词相同，连接相应位置条目的内容。一次归并操作的时间复杂度为O(n1 + n2)，其中n1和n2分别为索引词典的长度。索引器的效率一般在4Mb/min到1Gb/min之间，其中20%-30%的时间在做归并操作。对于归并操作没有很好的理论精确地得出最优的归并方式，本人采用词典长度接近的优先归并的方式，类似哈夫曼编码规则的顺序来归并，并取得了约10%的性能升。

第四章 4.1 准备工作 Prepare for Indexing

网页的内容经过爬虫爬取之后，按照不同的类型进行分析，成为相对“清洁”的文本之后就可以开始建立全文索引了。分析的过程包括大小写转换，过滤标点符号、没有意义的虚词和网页的格式代码。可以把分析看成是一个过滤的过程。

第三章 3.4 缓存 Search Engine Caching

缓存优化的核心思想是从避免无谓和重复的CPU计算、I/O调度来提高查询器的吞吐量。传统的缓存有两级：一是对结果集的缓存，纪录了查询的关键词和返回结果。如果相同的关键词被再次访问将得到快速地响应，同时过滤导致重复查询的计算量，提高系统的吞吐量。另外一个是对倒排索引的缓存，索引通常只保留最近、频繁被访问的索引段在内存中。这样的两级体系的优点在Rank-Preserving Two-Level Caching for Scalable Search Engines一文中做了详细地分析。
要介绍的是三级缓存结构:
第一级是结果缓存
查询分析器在内存和磁盘保存了大量的查询结果。分析所有的访问日志可以确定所有高频查询的关键词结果，然后保存起来。
第二级为集合缓存
一般查询的关键词为一些词的组合，例如：查询的关键词为A B C（检索的逻辑为AND），包含关键词A、B的各自命中文档列表都很大，而包含C的文档很少，不在一个数量级上，于是对A、B的交集结果进行缓存，并跟踪这些缓存数据在集群中的分布。这样的优化是针对大于等于三个词的情况，一般意义上看是在第一级缓存基础上的提升。
第三级为索引列表缓存
内存总是有限的，无法导入整个索引表，于是总是把最近/频繁访问到的索引置于内存中。
参考文献：Three-Level Caching for Efficient Query Processing in Large Web Search Engines

第三章 3.3 排队系统的优化 Application of Queueing Theory

排队系统的优化在集群计算中有着举足轻重的地位。此类优化问题分为两类：系统的最优设计和最优控制，前者称为静态最优问题，目的在于是系统达到最大效益，或者说在一定指标下是系统最为经济；后者为动态最优问题，是指对一给定的系统，如何运营可使给定的目标函数达到最优。
只对静态优化分析，对动态优化超出了目前以有的固定俗成的分析方法。
一般情形下，提高服务水平可减少用户等待的费用，却常常增加了服务器等硬件的投入成本。因此优化的目标之一就是使两者的费用之和为最小，并确定达到最优目标值的服务水平。假定在稳定状态下，个中费用都是按照单位时间来考虑的。一般来说，服务费用是比较容易估计出来，而用户的等待费用需要按不同的情况来分析。在处理方法上，一般根据变量的类型是离散还是连续，相应地采用边际分析方法或微分法，对教为复杂的优化问题需要用非线性规划或动态规划等方法。一般的套路从简单的模型开始一步步去逼近，直到得出对系统解释和最后的结果拟合得较好的模型。

第三章 3.2 文件共享入门简介 Introduction of File Sharing System

1) Remote sync (rsync) 是一种简单的文件共享实现方式。集群中的每个节点都至少有一份数据复本，复本间使用rsync进行同步。因为节点需要的数据就在本地，所以这种方法具有很高的可用性，不会出现单点失效现象。适合的场景：数据量很小，而且更新不频繁，可以采用这种方式。索引文件可以使用用这样的方式。
2) Network File System (NFS) 本身只是网络文件共享的标准，使用RPC进行通信。存储节点通过NFS将自己本地的文件输出，其他节点则把存储节点输出的文件系统装载到本地文件系统。NFS方式的存在两个很大的缺点：性能差：因为所有的文件访问都必须经过网络和NFS服务器，所以在访问流量比较大的情况下，网络带宽和NFS服务器都会成为系统的瓶颈。 单点失效：如果NFS服务器的系统失效或者网络失效都会使得其他节点无法得到数据.
3) Global File System（GFS）包含服务端和客户端的通信协议的实时文件系统，用锁机制实现共享数据更新控制，可以将物理上分离的存储设备虚拟为一个存储而且能平衡访问负载。
4) Intermezzo 属于较新的文件系统，吸收原有的文件系统的设计理念加入了很多智能的处理技术，比如日志更新，数据自动备份，镜像整合等。
最后登场的是这个时代的集大成者Lustre 本人对它的理解仅限于它提供的文档。

已经有位访客

第三章 3.1 I/O调度方式 Choose I/O Schedule

Completely Fair Queuing 机制和其字面的意思一致，完全公平的调度形式。每个进程产生的I/O请求都会被分配一个序号，进程之间的I/O请求队列独立，每次执行相同序号的请求。算法的实现，cfq会先考虑进程的优先级（0-20），从高的优先进程选择执行序号比较优先的I/O请求。Analysis and Simulation of a Fair Queueing Algorithm论述了该调度方法的诸多优点。
Anticipatory Scheduler 预估调度可能发生的时间，避免大量的I/O阻塞在一个队列中。Anticipatory scheduling: A disk scheduling framework to overcome deceptive idleness in synchronous I/O做了详细的阐述。
Deadline 赋予调度请求一个截止时间戳，时间截至优先级根据算法来从新计算。
NOOP 按照FIFO规则管理调度队列。
调度的调优是分布式文件系统性能最重要的先决因素，实际中应该能适时动态改变调度方式，以达到最佳性能。

第二章 2.2 宏观看爬虫 Key Points of Spider

Web上的信息具有异质性和动态性，由于受时间和存储、带宽的限制，不可能把所有的网页都搜集起来，一个好的搜集策略是有限搜集重要的网页。对于网页的重要程度的评定，要依据搜集信息所针对的不同应用而定，从而信息的搜集可以采取不同的策略。而目前这个问题尚无定论，一般按照如下几种指标来共同确定网页的重要性：
1）网页的入度大，也就是被引用的次数多；
2）该网页的父网页入度大；
3）网页有多个镜像ip；
4）网页的目录深度小，用户比较容易达到；
5）网页内容有较高的信息熵；
6）网页的更新频度比较高；
搜索引擎开始工作的时候，以上的参数都无法知道，这是一个渐进的优化过程。重要的页面不一定就是优先抓取的对象，还需要综合考虑其他的影响性能的参数，逐步调优。

第一章 1.2 声明 Declaration

本文的主旨是提供学习的基本导向，并对一些重要的技术细节进行剖析，舍去很多拖沓的描述，力图给读者深度和广度全面的理解web搜索的基本机制。
/**********本文并不申明为权威工程应用指南************/

第二章 2.1 书籍推荐 Spidering Hacks

标题其实一本经典的爬虫学习书，历史地、全面地介绍了spider。

第一章 1.1 兴趣的开始 Game Is Now Beginning

Web上数十亿张网页，认真地在网络上乱逛发现最大的需求是：哪里有好东西？我们能用它们来做什么？每个人对他们自己认为的有效信息有不同的看法，且大多数人当他们一旦找到好东西的时候，总是有一些创造性的电子。在某些web的角落，鼓励用有趣的方式来重新组织和运用这些资讯，而这些不平凡的资讯组合不容怀疑地向前流动，他们相信信息时代的到临。让我们开始漫长的学习历程吧！

第四章 索引 Full Text Indexing

在学习搜索引擎技术之前最好有一定的知识储备，Modern Information Retrieval 是本经典IR的教材，本文默认读者已经具有相应的基础。
数据需要分不同的类型进行相应处理，一般的网页内容文本大致可以分为四部分：
Keyword：　不做分析，逐字/词建索引并存储．例如URL，文件系统路径，日期，人名，社会保险帐号，电话号码等。举了本地搜索的例子，可以把系统路径名作为关键词．
UnIndexed：　不做分析也不做索引，但是值存储在索引中。这种一般是提供搜索结果的可显示内容。这些内容我们通常不需要去搜索（URL或者是数据库的主值）,只是在索引中存储原始的值。于是这里不适合存储大量的信息。
UnStored：　和UnIndexed相反，对这类field做分析和索引，但是不在索引中存储。通常是不需要在其原始的形式中检索信息，比如web页面的body部分，或者一些不大重要的文本。
Text：　分析，索引，存储索引。意味着将对这部分进行索引。
当然不局限于这几种，实际应用中可以扩展设计出更多的数据类别。设计的原则可以归结为：经常需要被检索的内容或者说网页的实质内容要建立相应的索引（和词典的功能类似），提供有效的信息组织形式并减少冗余。
索引和查询的底层实现是搜索引擎的核心：
1）尽可能对字段进行索引来提高查询速度，但过多的索引会对索引表表的更新操作变慢，而对结果过多的排序条件，实际上往往也是性能的杀手之一。
2)索引器的merge_factor提供了归并几个索引的功能，参数的合理设置直接影响了索引器的性能。
3）20%/80%原则：查的结果多并不等于质量好，尤其对于返回结果集很大，如何优化这头几十条结果的质量往往才是最重要的。
4)尽可能缩小减缩的结果集相对于单个应用来说，因为即使对于大型分布式文件系统，对结果集的随机访问也是一个非常消耗资源的操作。

第三章 并行分布式文件系统 Parallel Distributed File System

搜索的引擎的存储规模至少都是TB级别，如何有效地管理和组织这些资源呢？并且在极短的时间内得出结果？MapReduce: Simplified Data Processing on Large Clusters 给出了很好的分析。

分布式文件系统的实施必须实现两种临界资源的接口，一个是文件名到命名空间的映射表，另外一个是块表对应到结点机器列表。其中命名空间表示的是文件名到一组机器的映射，具体hash函数可能需要看命名空间的规模，其实就是一个Map过程；其中块表到机器列表的对应，实际是一个Reduce过程，分块存储到控制下的机器群（inodes），换句化说是slave-master的架构，通信的方式越底层的协议执行起来效率越高。具体实现可以参照hadoop。
当然需要考虑的还有很多的细节问题，比如inode机器的turn up 和 turn down，实时地识别这些出现的新机器，关掉的机器也自动地从列表中删除；备份数据个数的选择，备份之间的负载平衡；inode的配置文件的维护；对于终端的用户来说，文件系统虚拟化；

第二章 爬虫 Spider

简单地说，爬虫负责按照url列表爬取网页的内容，实际中需要针对不同的协议设计爬虫程序并优化。写一个优秀的爬虫不是件容易的事情，仅列举部分设计必须考虑到的问题。
1.严格按照robots.txt 来爬取内容，优先按照sitemap来抓取。
2.控制抓取的深度，量力而行。这个和人吃饭一次吃多少的道理是一样的。
3.网络上动态网页数量巨大，而爬虫一般是多线程的，如果爬虫对一个domain爬取的频率过高可能导致服务器无法相应；如何克服，如何让爬虫相对比较智能地平衡网络负载，运算负载，存储负载？
4.不要试图去解析页面中的脚本代码，可能是恶意的程序，也可能是有bug的代码，在本地运行会将计算的消耗提升到不可预期的程度。
5.如何节约带宽，需要检测到网页的更新，请求head信息以获取更新状态。
6.如何把计算网页权重结合到爬虫程序中？因为爬取的过程中还是相当的cpu资源没有被占用，IO和网络是爬虫效率的最大瓶颈。在连接结构还存储在内存中的时候就完成一部分的权值计算能提升爬虫机器的运行效率。

第一章 概述 Summarization of Search Engine Architecture

搜索引擎的架构是编写一个搜索引擎所需要考虑的第一个问题，The Anatomy of a Large-Scale Hypertextual Web Search Engine 一文对此问题做了全面的阐述。最大的功能模块可以分为：爬虫、存储、索引和web服务。爬虫负责不间断地爬取目标网站的内容，维护一张url的列表，并按照不重复的原则周期性工作；存储需要把过滤掉html tag的内容存储到本地，当然有很多内容是直接过滤的，比如js代码、影音流、图片等；然后对存储下来的内容进行批量索引，最终所有的索引内容需要合并到同一个索引中；那么有了一个建好的倒排索引，配合后台的查询语句，就可以开始web服务了，对于被检索的keyword，根据pagerank再结合内容的匹配程度，将结果呈现出来。对于用户来说，整个过程是透明的，只需要一个输入就可以得到所有可能的结果。

序 Search Technology Prefix

涉及搜索引擎大概有一年多，把自己经历过的一些技术问题分享出来，其中包括一些体会，希望后人能少走些弯路。