Cacher is the code snippet organizer for pro developers

介绍

Elasticsearch 是一个分布式可扩展的实时搜索和分析引擎, 一个建立在全文搜索引擎 Apache Lucene(TM) 基础上的搜索引擎. 当然 Elasticsearch 并不仅仅是 Lucene 那么简单，它不仅包括了全文搜索功能，还可以进行以下工作:

• 分布式实时文件存储，并将每一个字段都编入索引，使其可以被搜索。
• 实时分析的分布式搜索引擎。
• 可以扩展到上百台服务器，处理 PB 级别的结构化或非结构化数据。

基本概念

先说 Elasticsearch 的文件存储，Elasticsearch 是面向文档型数据库，一条数据在这里就是一个文档，用 JSON 作为文档序列化的格式，比如下面这条用户数据：

{
    "name" :     "John",
    "sex" :      "Male",
    "age" :      25,
    "birthDate": "1990/05/01",
    "about" :    "I love to go rock climbing",
    "interests": [ "sports", "music" ]
}

用 Mysql 这样的数据库存储就会容易想到建立一张 User 表，有 balabala 的字段等，在 Elasticsearch 里这就是一个文档，当然这个文档会属于一个 User 的类型，各种各样的类型存在于一个索引当中。这里有一份简易的将 Elasticsearch 和关系型数据术语对照表:

关系数据库     ⇒ 数据库 ⇒ 表    ⇒ 行    ⇒ 列(Columns)

Elasticsearch  ⇒ 索引(Index)   ⇒ 类型(type)  ⇒ 文档(Docments)  ⇒ 字段(Fields)

一个 Elasticsearch 集群可以包含多个索引 (数据库)，也就是说其中包含了很多类型 (表)。这些类型中包含了很多的文档 (行)，然后每个文档中又包含了很多的字段 (列)。Elasticsearch 的交互，可以使用 Java API，也可以直接使用 HTTP 的 Restful API 方式，比如我们打算插入一条记录，可以简单发送一个 HTTP 的请求：

PUT /megacorp/employee/1  
{
    "name" :     "John",
    "sex" :      "Male",
    "age" :      25,
    "about" :    "I love to go rock climbing",
    "interests": [ "sports", "music" ]
}

更新，查询也是类似这样的操作，具体操作手册可以参见 Elasticsearch 权威指南

索引

Elasticsearch 最关键的就是提供强大的索引能力了，其实 InfoQ 的这篇时间序列数据库的秘密 (2)——索引写的非常好，我这里也是围绕这篇结合自己的理解进一步梳理下，也希望可以帮助大家更好的理解这篇文章。

Elasticsearch 索引的精髓：

一切设计都是为了提高搜索的性能

另一层意思：为了提高搜索的性能，难免会牺牲某些其他方面，比如插入 / 更新，否则其他数据库不用混了。前面看到往 Elasticsearch 里插入一条记录，其实就是直接 PUT 一个 json 的对象，这个对象有多个 fields，比如上面例子中的name, sex, age, about, interests，那么在插入这些数据到 Elasticsearch 的同时，Elasticsearch 还默默 1 的为这些字段建立索引 -- 倒排索引，因为 Elasticsearch 最核心功能是搜索。

Elasticsearch 是如何做到快速索引的

InfoQ 那篇文章里说 Elasticsearch 使用的倒排索引比关系型数据库的 B-Tree 索引快，为什么呢？

什么是 B-Tree 索引?

上大学读书时老师教过我们，二叉树查找效率是 logN，同时插入新的节点不必移动全部节点，所以用树型结构存储索引，能同时兼顾插入和查询的性能。因此在这个基础上，再结合磁盘的读取特性 (顺序读 / 随机读)，传统关系型数据库采用了 B-Tree/B+Tree 这样的数据结构：

为了提高查询的效率，减少磁盘寻道次数，将多个值作为一个数组通过连续区间存放，一次寻道读取多个数据，同时也降低树的高度。

什么是倒排索引?

继续上面的例子，假设有这么几条数据 (为了简单，去掉 about, interests 这两个 field):

| ID | Name | Age  |  Sex     |
| -- |:------------:| -----:| -----:| 
| 1  | Kate         | 24 | Female
| 2  | John         | 24 | Male
| 3  | Bill         | 29 | Male

ID 是 Elasticsearch 自建的文档 id，那么 Elasticsearch 建立的索引如下:

Name:

| Term | Posting List |
| -- |:----:|
| Kate | 1 |
| John | 2 |
| Bill | 3 |

Age:

| Term | Posting List |
| -- |:----:|
| 24 | [1,2] |
| 29 | 3 |

Sex:

| Term | Posting List |
| -- |:----:|
| Female | 1 |
| Male | [2,3] |

Posting List

Elasticsearch 分别为每个 field 都建立了一个倒排索引，Kate, John, 24, Female 这些叫 term，而 [1,2] 就是Posting List。Posting list 就是一个 int 的数组，存储了所有符合某个 term 的文档 id。

看到这里，不要认为就结束了，精彩的部分才刚开始...

通过 posting list 这种索引方式似乎可以很快进行查找，比如要找 age=24 的同学，爱回答问题的小明马上就举手回答：我知道，id 是 1，2 的同学。但是，如果这里有上千万的记录呢？如果是想通过 name 来查找呢？

Term Dictionary

Elasticsearch 为了能快速找到某个 term，将所有的 term 排个序，二分法查找 term，logN 的查找效率，就像通过字典查找一样，这就是Term Dictionary。现在再看起来，似乎和传统数据库通过 B-Tree 的方式类似啊，为什么说比 B-Tree 的查询快呢？

Term Index

B-Tree 通过减少磁盘寻道次数来提高查询性能，Elasticsearch 也是采用同样的思路，直接通过内存查找 term，不读磁盘，但是如果 term 太多，term dictionary 也会很大，放内存不现实，于是有了Term Index，就像字典里的索引页一样，A 开头的有哪些 term，分别在哪页，可以理解 term index 是一颗树：

这棵树不会包含所有的 term，它包含的是 term 的一些前缀。通过 term index 可以快速地定位到 term dictionary 的某个 offset，然后从这个位置再往后顺序查找。

所以 term index 不需要存下所有的 term，而仅仅是他们的一些前缀与 Term Dictionary 的 block 之间的映射关系，再结合 FST(Finite State Transducers) 的压缩技术，可以使 term index 缓存到内存中。从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘随机读的次数。

这时候爱提问的小明又举手了:"那个 FST 是神马东东啊?"

一看就知道小明是一个上大学读书的时候跟我一样不认真听课的孩子，数据结构老师一定讲过什么是 FST。但没办法，我也忘了，这里再补下课：

FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

假设我们现在要将 mop, moth, pop, star, stop and top(term index 里的 term 前缀) 映射到序号：0，1，2，3，4，5(term dictionary 的 block 位置)。最简单的做法就是定义个 Map<string, integer="">，大家找到自己的位置对应入座就好了，但从内存占用少的角度想想，有没有更优的办法呢？答案就是：FST(理论依据在此，但我相信 99% 的人不会认真看完的)

⭕️表示一种状态

--> 表示状态的变化过程，上面的字母 / 数字表示状态变化和权重

将单词分成单个字母通过⭕️和 --> 表示出来，0 权重不显示。如果⭕️后面出现分支，就标记权重，最后整条路径上的权重加起来就是这个单词对应的序号。

FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.

FST 以字节的方式存储所有的 term，这种压缩方式可以有效的缩减存储空间，使得 term index 足以放进内存，但这种方式也会导致查找时需要更多的 CPU 资源。

后面的更精彩，看累了的同学可以喝杯咖啡……

压缩技巧

Elasticsearch 里除了上面说到用 FST 压缩 term index 外，对 posting list 也有压缩技巧。
小明喝完咖啡又举手了:"posting list 不是已经只存储文档 id 了吗？还需要压缩？"

嗯，我们再看回最开始的例子，如果 Elasticsearch 需要对同学的性别进行索引 (这时传统关系型数据库已经哭晕在厕所……)，会怎样？如果有上千万个同学，而世界上只有男 / 女这样两个性别，每个 posting list 都会有至少百万个文档 id。 Elasticsearch 是如何有效的对这些文档 id 压缩的呢？

Frame Of Reference

增量编码压缩，将大数变小数，按字节存储

首先，Elasticsearch 要求 posting list 是有序的 (为了提高搜索的性能，再任性的要求也得满足)，这样做的一个好处是方便压缩，看下面这个图例：

如果数学不是体育老师教的话，还是比较容易看出来这种压缩技巧的。

原理就是通过增量，将原来的大数变成小数仅存储增量值，再精打细算按 bit 排好队，最后通过字节存储，而不是大大咧咧的尽管是 2 也是用 int(4 个字节) 来存储。

Roaring bitmaps

说到 Roaring bitmaps，就必须先从 bitmap 说起。Bitmap 是一种数据结构，假设有某个 posting list：

[1,3,4,7,10]

对应的 bitmap 就是：

[1,0,1,1,0,0,1,0,0,1]

非常直观，用 0/1 表示某个值是否存在，比如 10 这个值就对应第 10 位，对应的 bit 值是 1，这样用一个字节就可以代表 8 个文档 id，旧版本 (5.0 之前) 的 Lucene 就是用这样的方式来压缩的，但这样的压缩方式仍然不够高效，如果有 1 亿个文档，那么需要 12.5MB 的存储空间，这仅仅是对应一个索引字段(我们往往会有很多个索引字段)。于是有人想出了 Roaring bitmaps 这样更高效的数据结构。

Bitmap 的缺点是存储空间随着文档个数线性增长，Roaring bitmaps 需要打破这个魔咒就一定要用到某些指数特性：

将 posting list 按照 65535 为界限分块，比如第一块所包含的文档 id 范围在 0~65535 之间，第二块的 id 范围是 65536~131071，以此类推。再用 <商，余数> 的组合表示每一组 id，这样每组里的 id 范围都在 0~65535 内了，剩下的就好办了，既然每组 id 不会变得无限大，那么我们就可以通过最有效的方式对这里的 id 存储。

细心的小明这时候又举手了:"为什么是以 65535 为界限?"

程序员的世界里除了 1024 外，65535 也是一个经典值，因为它 = 2^16-1，正好是用 2 个字节能表示的最大数，一个 short 的存储单位，注意到上图里的最后一行 “If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value”，如果是大块，用节省点用 bitset 存，小块就豪爽点，2 个字节我也不计较了，用一个 short[] 存着方便。

那为什么用 4096 来区分大块还是小块呢？

个人理解：都说程序员的世界是二进制的，4096*2bytes ＝ 8192bytes < 1KB, 磁盘一次寻道可以顺序把一个小块的内容都读出来，再大一位就超过 1KB 了，需要两次读。

联合索引

上面说了半天都是单 field 索引，如果多个 field 索引的联合查询，倒排索引如何满足快速查询的要求呢？

• 利用跳表 (Skip list) 的数据结构快速做 “与” 运算，或者
• 利用上面提到的 bitset 按位 “与”

先看看跳表的数据结构：

将一个有序链表 level0，挑出其中几个元素到 level1 及 level2，每个 level 越往上，选出来的指针元素越少，查找时依次从高 level 往低查找，比如 55，先找到 level2 的 31，再找到 level1 的 47，最后找到 55，一共 3 次查找，查找效率和 2 叉树的效率相当，但也是用了一定的空间冗余来换取的。

假设有下面三个 posting list 需要联合索引：

如果使用跳表，对最短的 posting list 中的每个 id，逐个在另外两个 posting list 中查找看是否存在，最后得到交集的结果。

如果使用 bitset，就很直观了，直接按位与，得到的结果就是最后的交集。

总结和思考

Elasticsearch 的索引思路:

将磁盘里的东西尽量搬进内存，减少磁盘随机读取次数 (同时也利用磁盘顺序读特性)，结合各种奇技淫巧的压缩算法，用及其苛刻的态度使用内存。

所以，对于使用 Elasticsearch 进行索引时需要注意:

• 不需要索引的字段，一定要明确定义出来，因为默认是自动建索引的
• 同样的道理，对于 String 类型的字段，不需要 analysis 的也需要明确定义出来，因为默认也是会 analysis 的
• 选择有规律的 ID 很重要，随机性太大的 ID(比如 java 的 UUID) 不利于查询

关于最后一点，个人认为有多个因素:

其中一个 (也许不是最重要的) 因素: 上面看到的压缩算法，都是对 Posting list 里的大量 ID 进行压缩的，那如果 ID 是顺序的，或者是有公共前缀等具有一定规律性的 ID，压缩比会比较高；

另外一个因素: 可能是最影响查询性能的，应该是最后通过 Posting list 里的 ID 到磁盘中查找 Document 信息的那步，因为 Elasticsearch 是分 Segment 存储的，根据 ID 这个大范围的 Term 定位到 Segment 的效率直接影响了最后查询的性能，如果 ID 是有规律的，可以快速跳过不包含该 ID 的 Segment，从而减少不必要的磁盘读次数，具体可以参考这篇如何选择一个高效的全局 ID 方案 (评论也很精彩)

转：http://blog.pengqiuyuan.com/ji-chu-jie-shao-ji-suo-yin-yuan-li-fen-xi/