-
密集并行（Embarrassingly parallel）
无状态（Stateless） -查询只是一次性的
大量的只读（Read-only）操作 -
需要很大的存储-索引库的数据甚至比网页的数据还多
-
需要很多的计算-即使我们可以将很多东西预处理，对大量的查询操作而言，我们的任务量仍然很重。
-
需要极短的响应时间-考虑一下打开个百度用一天？
-
系统的设计目标：能耗小、性能比高 （尽可能用便宜，普通的设备）
便宜的 PC集群 -
软件的可靠性–追求便宜就不一定可靠了，但是可靠性又必须得到保证，某个设备宕机系统仍然可以运行。
容错（Fault tolerance） -
解决方案：高度的复制（High degree of replication）–数据冗余，放在不同的地方。
Google：英文含义，“体现了整合网上海量信息的远大目标”。
Google将数以千计的低成本计算机联网到一起，制造出了一部超高速搜索引擎。超过80亿索引页面、超过10亿索引图像、超过80种语言、112 个国际域名 (2008年的统计数据）下面红线是Google的市场占有量。
Implemented in C and C++ on Solaris and Linux
（1）采集数据
（2）建立索引
命中表是前向索引和倒排索引的核心部分。
- 前向索引：每篇文档都有一个对于它的所有词的前向索引。
- 每个文档包含很多词，每个词都有其对应的wordID，按照wordID分到桶里，也就是说桶将词表分成好多份，保存在他范围内的所有词信息。
- 前向索引是以文档为主的索引，我们使用sorter建立倒排索引，利用桶里放置的词直接对每个word ID的词进行排序，就能生成倒排索引。
（3）提供检索服务
- 网页分成几个域比较重要，包括title，anchor等。因此barrels分为两类，短桶存放比较重要的域的词，长桶存放所有的词。
（4）数据结构
优化的数据结构，使得海量文档可以较低的开销被抓取、索引和检索
- 文件系统BigFiles
- 网页库（Repository）
- 文档索引（Document index）
- 词典（Lexicon）
- 命中表（Hit lists）
- 前向索引（Forward index）
- 倒排索引（Inverted index）
操作系统提供的文件系统通常不能满足搜索引擎的要求，Google用了很多时间来开发自己的BigFiles文件系统
- 在建在多个文件系统之上，以64位整数进行寻址的虚拟文件系统
- 文件系统之间的分配由系统自动完成
- 一般操作系统不提供足够的描述符号，所以BigFiles文件系统要自己处理文件描述符的分配与回收
- BigFiles文件系统还直接支持文件的压缩功能
网页库（Repository）包含了每个网页的完整HTML文档，每个网页都是用zlib进行压缩的（压缩要综合考虑存储和速度）
文档索引按照一定的次序来保存关于每个文档的信息，它是按docID组织的，每个条目包含
- 指向repository中文档的指针
- 文档校验和（checksum）
- 统计信息
- 当前文档统计信息
- URL指针
• 如果该网页已经被抓取下来了，则它还包含一个指针，指向一个可变宽度、被称为docinfo的文件，该文件中包含文档的URL及标题
• 如果该网页未被抓取，指针只是指向一个仅仅包含URL的URLlist
在设计时，要考虑压缩数据结果以减少存储
- 不同搜索引擎采用的词典不一样，在Google中，词典可以驻留在内存中，占大约256M内存，包含14,000,000个单词（一些稀有的单词没有加入到词典中）
- 由两部分组成
其一是通过空格分隔的单词表（a list of the words, concatenated together but separated by nulls）
其二是由指针组成的散列表（ a hash table of pointers ）–每个单词映射到一个wordID。 - 为了提高性能，除了基本词典，每个索引器（indexer）还维护一个额外的文件，因为我们有多个机器，每个机器都要独立维护一个词典。
命中表的每一项包含某词在某文档中的出现信息：
位置
字体大小
大小写信息等
描述子类型（ descriptor type ），如title、anchor等
anchor的表示最特殊，用4bit表示值，这个值其实是document ID的hash值，因为anchor是自己外链包含的文本，这个文本不是对当前网页重要，而是对指向网页比较重要，因此这个docid是链接链向网页的docID，此时的位置也不是词的位置，而是表示这是第几个链接（超出16个链接就不计了）
前向索引是文档到词的索引，每个桶容纳一定范围内的wordID，如果一个文档包含的单词（用wordID表示）属于某个桶的话，那么该桶首先记录该文档的docID，紧接其后的是文档中的一串单词、对应于这些单词的命中列表。
提高文档检索的速度，要建立词到文档的索引，即倒排索引。倒排索引也包含与前向索引一样的存储桶（无论是前向还是倒排，命中表都在桶里，命中表都是核心）
（5）Google检索算法
（1）单个检索词的查询排序
- 对每个词提取命中列表（Hitlist）
- 每个命中可以是以下几种类型之一：题目，锚文本， URL，大字体，小字体等
- 每个命中类型赋予一定的权重，类型－权重构成一个权重的矢量（weight vector）
- 每个类型命中个数被计算，并构成频率矢量（count vector）
- 两个矢量的点积（dot product）用来计算IR（Information Retrieval）的得分（内容相关度）
- IR分数与PageRank（网页重要性）结合起来计算最后的得分
（2）多个检索词的查询排序
- 与单个检索词的排序类似，只是必须分析相近性（proximity） 匹配词越接近，权重越高
- 每个邻近关系被赋予1到10的权重，从“词组关系”到“毫无关系”
- 对每个类型的命中和相近度计算出现的次数
（3）扩展性与关键的优化技术
采用高可扩展的集群架构，当时（1998年）：
大约2400万文档，在一个星期内索引完成
索引了大约5亿多个超链
4个crawlers每秒抓取100个文档
- 每个crawler维护一个自己的 DNS查找缓存
- 用flex来产生 词法分析器（lexical analyzer）以解析文档
- 并行化索引
- 词典的内存管理（In-memory lexicon）
- 网页库的压缩（Compression of repository）
- 对命中表（hitlists）的编码压缩可节省很大的存储空间
- 索引器优化的很好，比crawler略快，因此crawler是瓶颈
- 文档索引批量更新（updated in bulk）
- 关键的数据结果放在本地硬盘
- 全局化的架构设计，尽可能避免磁盘扫描
-
系统设计
存储和计算的配置
分布式系统的挑战：可扩展性（Scalability）、可靠性（Reliability）、安全（Security）、协商（Consensus） -
编程模型：关于管理的资源的简单的、全局视图
- 文件系统是建立在廉价通用主机平台上的，文件系统必须能够一直监视自己的状态并从灾难中恢复过来
- 文件系统存储着许多大文件。数目大概是几百万个，大小为100M或者更大，几G
- 需要支持两种类型的读取方式：大规模流读取方式和小规模随机读取方式。在大规模流读取中，一个操作通常会从一个连续的文件区域中读取几百K或者更多的数据。随机读取则可能在任意位置读取几K的数据
- 写的方式和读的方式也类似。大量的数据通常以追加的方式添加到文件最后，因为这些数据一次写入后通常就不再更改了（改一般也是批量更改）
- 系统必须能够保证多个客户端能并发地对同一个文件进行追加记录
- 稳定的高带宽比低延时更重要。大多数应用程序，需要在高传输速率下，大块地操作数据。
（1）简介与典型应用
一个成熟的Apache开源项目；
提供文本索引和搜索的Java 类库/包；
也有C/Python语言接口；
http://lucene.apache.org
（2）得分算法-类向量空间模型
不同之处在于
- 对于查询的向量构造，权重种使用了权重，而不是tf因子。
- idf的计算公式也有点不太一样，首先用的是，并且给分母+1。tf因子开根号。
- 表示查询所在的域的长度，或者简单理解为某篇文档中查询范围内词汇的数量
- 和值与文档无关，不影响排名
- 是人为赋予的经验值，缺省为1.0
- 因此排名因子：
单位长度的文档包含的关键词个数的平方根
（3）BooleanQuery的得分公式:多个词
BooleanQuery是一种复合式查询，支持多种不同查询词的逻辑组合，
BooleanQuery例子
＋俄罗斯 恐怖 事件 －美国
＋（俄罗斯 美国) 恐怖 事件
可以对不同的查询词赋予不同的boost值表示该查询词在整个BooleanQuery中的重要程度
例如: 俄罗斯3.0 恐怖2.0 事件1.0
- Nutch的创始人Doug Cutting，也是Lucene和Hadoop的创始者
- Nutch 1.2是基于Lucene的开源搜索引擎，增加了面向web的处理模块
crawler
链接图（link graph） • 链接分析 • 锚文本
HTML和其他文档格式的识别和解析
语言、字符集的识别和处理
扩展的索引和检索功能 - Nutch 1.2版本之后，从搜索引擎演化为网络爬虫，进行分布式多任务抓取和分析存储。
- Solr是基于Lucene的搜索系统，提供索引和搜索服务
他对停止词的处理别具一格，不会直接把所有的停止词去掉，比如都是停止词，但是连起来还是蛮有用的，所以Nutch选择将停止词和附近的词连起来组成新的词，以防漏掉重要信息。
- 页面包含的匹配的检索词的个数
- 匹配词的邻近程度
- 词在页面的位置
- 词在某些tag的位置，如
- 指向该页面的锚文本
- 在页面中出现的检索词的频率，以及检索词在整个集合中出现的频率（TF*IDF）
- 链接分析：哪些页面指向该页面
- 点击分析：该页面被访问的频率
- 网页的“崭新”程度
设计复杂的公式将以上各因素综合起来