ElasticSearch实战 搜索技术基本知识

Elasticsearch的数据分区
一般来说，搜索引擎有两种数据分区方式，即基于文档的分区方式和基于词条的分区方式。Elasticsearch使用的是基于文档的分区方式。

基于文档的分区(Document Based Partitioning)指的是每个文档只存一个分区，每个分区持有整个文档集的一个子集。这里说的分区是指一个功能完整的倒排索引。

基于文档的分区的优点汇总如下：

(1) 每个分区都可以独立地处理查询。

(2) 可以非常方便地添加以文档为单位的索引信息。

(3) 在搜索过程中网络开销很小，每个节点可以分别独立地执行搜索，执行完之后只需返回文档的ID和评分信息即可。而呈现给用户的结果集是在执行分布式搜索的节点上执行合并操作实现的。

基于文档的分区的缺点也是很明显，如果查询需要在所有的分区上执行，则它将执行O(K×N)次磁盘操作(K是词条term的数量，N是分区的数量)。

从实用性角度来看，基于文档的分区方式已经被证明是一个构建大型的分布式信息检索系统的行之有效的方法。因此Elasticsearch使用的是基于文档的分区方式。

基于词条的分区(Term Based Partitioning)指的是每个分区拥有一部分词条，词条里面包含了与该词条相关的整个index的文档数据。

目前也有一些基于词条分区的搜索引擎系统，如Riak Search有、Lucandra和Solandra。

基于词条的分区的优点汇总如下：

(1) 部分分区执行查询。一般来说，用户只需要在很小的部分分区上执行查询就可以了。举个例子，假如用户有3个term词条的查询，则Elasticsearch在搜索时将至多命中3个分区。如果足够幸运，这3个term词条都保存同一个分区中，那么用户只需访问一个分区即可。在搜索的背后，用户无需知道Elasticsearch中实际的分区数量。

(2) 时间复杂度低。一般而言，当对应K个term词条的查询时，用户只需执行O(K)次磁盘查询即可。

基于词条的分区的缺点汇总如下：

(1) 最主要的问题是Lucene Segment概念里面有很多固有的结果都将失去。

对于比较复杂的查询，搜索过程中的网络开销将变得非常高，并且可能使得系统可用性大大降低，特别是注入前置搜索或模糊搜索的场景。

(2) 获取每个文档的信息将会变得非常困难。由于是按词条分区存储的，如果用户想获取文档的一部分数据做进一步的控制，或获取每个文档的这些数据，都将变得非常困难，因为这种分区方式使得文档的数据被分割到了不同的地方，所以实现注入评分、自定义评分等都将变得难以实现。

搜索过程解析
对已知文档的搜索
如果被搜索的文档(不论是单个文档，还是批量文档)能够从主分片或任意一个副本分片中被检索到，则与索引文档过程相同，对已知文档的搜索也会用到路由算法，elasticsearch中的路由算法如下所示：

shard = hash(routing) % number_of_primary_shards

下图为例，展示在主分片上搜索一个文档的必要步骤。

(1) 客户端给主节点1发送文档的Get请求，此时主节点1就成为协同节点。主节点使用路由算法算出文档所在的主分片；随后协同节点将请求转发给主分片所在的节点2，当然，也可以基于轮询算法转发给副本分片。

(2) 主节点1根据文档的ID确认文档属于分片R0.分片R0对应的副本分片在三个节点上都有。此时，主节点1转发请求到节点2。

(3) 节点2在本地分片进行搜索，并将目标文档信息作为结果返给主节点1。

对于读请求，为了在各节点间负载均衡，请求节点一般会为每个请求选择不同的分片，一般采用轮询算法循环在所有副本分片中进行请求。

对未知文档的搜索
除对已知文档的搜索外，大部分请求实际上是不知道查询条件会命中哪些文档的。这些被查询条件命中的文档可能位于elasticsearch集群中的任意位置上。因此，搜索请求的执行不得不去询问每个索引的每一个分片。

在elasticsearch中，搜索过程分为查询阶段(query phase)和获取阶段(fetch phase)。

在查询阶段，查询请求会广播到索引中的每一个主分片和备份中，每一个分片都会在本地执行搜索，并在本地各建立一个优先级队列(priority queue)。该优先级队列是一份根据文档相关度指标进行排序的列表，列表的长度由from和size两个分页参数决定。

查询阶段可以再细分成3个小的子阶段：

(1) 客户端发送一个检索请求给某节点A，此时节点A会创建一个空的优先级队列，并配置号分页参数from和size。

(2) 节点A将搜索请求发送给该索引中的每一个分片，每个分片在本地执行搜索，并将结果添加到本地优先级队列中。

(3) 每个分片返回本地优先级序列中所记录的ID与sort值，并发送给节点A。节点A将这些值合并到自己的优先级队列中，并做出全局的排序。

在获取阶段，主要是基于上一阶段找到所要搜索文档数据的具体位置，将文档数据内容取回并返回给客户端。

在elasticsearch中，默认的搜索类型就是上面介绍的Query then Fetch。上述描述运作方式就是Query then Fetch。Query then Fetch有可能会出现打分偏离的情形，幸好，elastic search还提供了一个称为“DFS Query then Fetch”的搜索方式，它和Query then Fetch基本相同，但是它会执行一个预查询来计算整体文档的frequency。其处理过程如下所示：

(1) 预查询每个分片，询问Term和Document Frequency等信息。

(2) 发送查询请求到每个分片。

(3) 找到各个分片中所有匹配的文档，并使用全局的Term/Document Frequency信息进行打分。在执行过程中依然需要对结果构建一个优先队列，如排序等。

(4) 返回关于结果的元数据到请求节点。需要指出的是，此时实际文档还没有发送到请求节点，发送的只是分数。

(5) 请求节点将来自所有分片的分数合并起来，并在请求节点上进行排序，文档被按照查询要求进行选择。最终，实际文档从它们各自所在的独立的分片上被检索出来，结果被返回给读者。

对词条的搜索
回顾elasticsearch分别为每个文档的字段建立了一个倒排索引。

当要搜索中文词1时，通过倒排索引可以获悉，与待搜索中文词1的文档是中文网页1、中文网页2和中文网页3.

当词条数据较少时，可以顺利遍历词条获取结果，但如果词条由成千上万个，elasticsearch为了能快速找到某个词条，它对所有的词条都进行了排序，随后使用二分法查找词条，其查找效率为log(N)。这个过程就像查找字典一样，因此排序词条的集合也称为Term Dictionary。

为了提高查询性能，Elasticsearch直接通过内存查找词条，而非从磁盘中读取。但当词条太多时，显然Term Dictionary也会很大，此时全部放在内存有些不现实，于是引入了Term Index。

Term Index就像字典中的索引页，其中的内容如字母A开头的有哪些词条，这些词条分别在哪页。通过Term Index，Elastinsearch可以快速地定位到Term Dictionary地某个OffSet(位置偏移)，然后从这个位置再往后顺序查找。

前面提及了单个词条地搜索方法，而在实际应用中，更常见地往往是多个词条拼接成地“联合查询”，那么Elasticsearch是如何基于倒排索引实现快速查询地呢？

核心思想是利用跳表快速做“与”计算，还有一种方法是利用BitSet(位图)按位“与”运算。

先来看跳表快速做“与”运算地方式，首先介绍跳表，如下图所示：

跳表由多级链表组成，上一级是下一级元素地子集，因此上一级往往数据较少。在查找时，数据从上级向下级逐级查找/如查找数据36，从第三级中找到元素11，从第二级中到数据32，从第三级中的数据32之后查找到36，总共用了3次查找。

那么跳表是如何用在多词条索引中地呢？

通过倒排索引，每个词条都会有一个命中地文档ID列表(如果能命中地话)，此时，我们可以找到这些文档ID列表中最短地那一个。接下来，用最短的文档ID列表中的ID逐个在其他文档ID列表中进行查找，都能找到的ID即为多个词条的交集结果。

再来看BitSet按位“与”运算的方式。

BitSet中的每一位只有两个可能取值，即0或1。如果数据存在，则对应的标记置为1，否则置为0。

因此，将词条的文档ID列表转化为位图后，将多个词条对应的位图取“与”运算，即可得到交集结果。

索引原理解析
近实时搜索的实现
文档被索引动作和搜索该文档动作之间是有延迟的，因此，新的文档需要在几分钟后方可被搜索到，但这依然不够快，其根本原因在于磁盘。

在elasticsearch中，当提交一个新的段到磁盘时需要执行fsync操作，以确保段被物理地写入磁盘，即使断电数据也不会丢失。不过，fsync很消耗资源，因为它不能在每个文档被索引时都触发。

位于Elasticsearch和磁盘间地时文件系统缓存。内存索引缓存中的文档被写入新段的过程的资源消耗很低；之后文档会被同步到磁盘，这个操作的资源消耗很高。而一个文件一旦被缓存，它就可以被打开和读取。因此，elasticsearch利用了这一特性。

Lucene允许新段在写入后被打开，以便让段中包含的文档可被搜索，而不用执行一次全量提交。这是一种比提交更轻量的过程，可以经常操作，且不会影响性能。

在elasticsearch中，这种写入打开一个新段的轻量级过程，叫做refresh。在默认清空下，每个分片每秒自动刷新一次。这就是认为Elasticsearch是近实时搜索，但不是实时搜索的原因，即文档的改动不会立即被搜索，但是会在一秒内可见。

倒排索引的压缩
Elasticsearch为每个文档中的字段分别建立了一个倒排索引。

随着文档的不断增加，倒排索引中的词条和词条对应的文档ID列表会不断增大，从而影响Elasticsearch的性能。

Elasticsearch对词条采用了Term Dictionary和Term Index的方式来简化词条的存储和查找；同事，Elasticsearch对词条对应的文档ID列表进行了必要的处理。

Elasticsearch是如何处理这些文档ID列表的呢？答案很简单，即通过增量编码压缩，将大数变小数。按字节压缩。

为了有效进行压缩，词条对应的文档ID列表是有序排序的。所谓增量编码，就是将原来的大数变小数，仅存储增量值，示例如下：

假如原有的文档ID列表为：10 23 34 66 100 178

增量编码后文档ID列表为：10 13 11 32 34 78

所谓按字节存储，即查看增量编码后的数字可以用几位字节存储，而非全部用int(4字节)存储，从而达到压缩和节省内存的目的。当然，为了节省更多的内存，还可以对增量编码后的文档ID列表进行分组，再分别计算每一个存储需要的字节数。

数据刷新方式
在Elasticsearch中，有两种数据刷新操作：Refresh和Flush。

Refresh
当我们索引文档是，文档是存储在内存中的，默认1s后会进入文件系统缓存。Refresh操作本质上是对Lucense Index Reader调用了ReOPen操作，即对此时索引中的数据进行更新，使文档可以被用户搜索到。

不过，此时文档还未存储到磁盘上，如果Elasticsearch的服务器宕机了，那么这部分数据就会丢失。如果要对这部分数据进行持久化，则需要调用消耗较大的Luncene Commit操作。因此，Elasticsearch采用可以频繁调用轻量级的ReOpen操作来达到近实时搜索的效果。

Flush
虽然Elasticsearch采用了可以频繁调用轻量级的ReOpen操作来达到近实时搜索的效果，但数据终究是要持久化的。

Elasticsearch在写入文档时，会写一份translog日志，基于translog日志可以恢复那些丢失的文档，在出现程序故障或磁盘异常时，保障数据的安全。

Flush可高效地触发Lucene Commit，同时清空translog日志，使数据在Lucene层面持久化。