Elasticsearch 简介
Elasticsearch 是一个分布式、高扩展、高实时的搜索与数据分析引擎。Elasticsearch 建立在全文搜索引擎 Apache Lucene™ 基础上，通过 Lucene 的倒排索引技术实现比关系型数据库更快的过滤，从而很方便的使大量数据具有搜索、分析和探索的能力。
毫无疑问，Elasticsearch的底层核心是倒排索引。 Elasticsearch通过扩展服务器集群的方式，将数据以文档的形式，FST压缩的方式，分布式实时存储；同时为文件每一个字段添加倒排索引，通过倒排索引以及skip list 和 bitset 三种数据结构实现实时分布式分析和快速搜索的功能。
Elasticsearch 数据存储
先说Elasticsearch的文件存储，Elasticsearch是面向文档型数据库，一条数据在这里就是一个文档，用JSON作为文档序列化的格式，比如下面这条学生数据：
{
"stuName":"Rose",
"age":18,
"gender":"Male",
"resume":"I am gooding at studying",
"tuition":26800.00,
"hobbies":["sleep","games"],
"address":{
"province":"JiangSu",
"city":"NanJing",
"district":"YuHua"
}
}
如果用传统的关系型数据库比如说mysql来存储上述这条数据时，我们能够想到的是去建立一张student表，表中有stuName，age，tuition，hobbies，address字段等，而在Elasticsearch里这就是一个记录student类型的文档，所有的字段类型都存在于这个文档的索引里。这里有一份简易的将Elasticsearch和关系型数据术语对照表:
image.png
Elasticsearch和传统的数据库一样，索引、类型、文档、字段都是一对多的关系。Elasticsearch数据交互可以通过HTTP的Restful请求方式直接请求，也可以通过java API请求。值得注意的是，Elasticsearch主要用来查询，因为其每一个字段都有倒排索引这种需要大量的储存空间，我刚开始接触Elasticsearch的事实增删改，如果不实用shell脚本的话，要一条一条的执行，增删改的效率很低，不如传统的数据库。事实上，现在市场的主流就是Elasticsearch与传统数据库公用，Elasticsearch用来查询，传统的用来增删改，Elasticsearch连接数据库和客户端搜索引擎的桥梁。
倒排索引
Elasticsearch倒排索引的精髓：
倒排索引压缩储存空间，减少磁盘读取次数；严格储存结构，节省搜索时间。
简单的来说，Elasticsearch将磁盘里的东西尽量搬进内存，减少磁盘随机读取次数(同时也利用磁盘顺序读特性)，结合各种奇技淫巧的压缩算法，用极其苛刻的态度使用内存。
Elasticsearch能够通过倒排索引来达到实时、高效的搜索是怎么实现的呢？下面我从时间和空间的概念来谈谈倒排索引的原理。
倒排索引的空间结构是什么样的？
首先根据上述例子拿出stuName，age，gender字段的来说：
student类型的文档上层school对应着一个索引的index为1：
PUT http://192.168.152.129:9200/school
1
student类型的文档对应着一个index：
| ID | stuName | age | gender |
|---|---|---|---|
| 1 | Rose | 24 | Male |
| 2 | John | 24 | Female |
| 3 | Bill | 29 | Female |
stuName:
| stuName | Posting List |
|---|---|
| Rose | 1 |
| John | 2 |
| Bill | 3 |
age:
| Term | Posting List |
|---|---|
| 24 | [1,2] |
| 29 | 3 |
gender:
| Term | Posting List |
|---|---|
| Female | 1 |
| Male | [2,3] |
如上所述，student所在的school索引index，student每个文档dictionary，student的每个字段Posting List都建立了索引。用一张图表示如下：
image.png
Posting List
Posting List是Elasticsearch中为每个字段field自动提供的索引集合，比方说24,29 这些叫做 term，而 [1,2] 就是 posting list。Posting list 就是一个 int 的数组，存储了所有符合某个 term 的文档 id。
Term Dictionary
Elasticsearch中为了能够快速的找到某个term，也就是我们经常用某个字段来快速查询，为了实现这一功能，Term Dictionary就产生了。Term Dictionary的实现底层就是B+Tree，使用二分法进行查询term， logN 次磁盘查找效率，就像字典查询一样，首字母是什么，就先检索什么，然后再看第二个字母是什么，检索第二个字母，…，一直到检索到这个term为止。
Term Index
由于磁盘随机读的存在，就必须将一部分数据存在缓存内存中，但是Term Dictionary磁盘存储空间的巨大，又不能将Term Dictionary完整的放到内存里。因此就有了Term Index，它就像字典里一个更大的章节一样，每个大的章节再对应着多个小的章节Term Dictionary，这样就能实现速的找到某个term。
Term Index、Term Dictionary和Posting List个关系
如下图 所示：“A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, 和 “inn” 这些单词是如何储存在Elasticsearch里的呢？Term Index就像一棵倒挂的树一样，它就是这棵树的根节点，也就是这本字典；Term Dicitionary是根节点的子节点，存放着“t”、“A”、“i”，也就是所储存单词的前缀；然后Posting List就是相同前缀的单词（term）集合，里面装着我们要检索的单词（term）。因此通过 term index能够快速精确的检索到我们所需要的term
image.png
如下图所示，关系型数据库如Mysql 只有 term dictionary 这一层，是以 b-tree 排序的方式存储在磁盘上的。检索一个 term 需要若干次的 random access 的磁盘操作。而 Elasticsearch 在 term dictionary 的基础上添加了 term index 来加速检索，term index 以树的形式缓存在内存中。从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access 次数。
image.png
倒排索引的时间概念是怎么节省的？
B-Tree+整体分区快速查找
上面说到Elasticsearch中的 term dictionary不同于关系型数据库的term dicitionary的结构B-Tree那样，将所存储的数据按照某种规则进行排序储存于磁盘里，然后通过二分法去查找某个term，这样能够达到log N的查询效率；而Elasticsearch中先把 term dictionary分为相同大小的块，然后递归去把每个块分成相同大小的块，进行快速查找。
举个例子，对于1-16这组数据进行快速查找其中的某个值：
B-Tree二分法：
image.png
如图所示B-Tree二分法查找7这个数，需要4次方能查出来。同样的查找1和16也需要4次才能查找出来。
B-Tree+整体分区法：
image.png
如图所示B-Tree+整体分区法查找7的时候，只需3次就能找到，相当于“三分法”一样比二分法更加的有效率，但是如果数据每次“三分”时都处于中间，那就无形的增加了判断次数（这种做法，拿要检索的值7和中间块的两头6和11比较），但是这只是极少的数据而已，在海量的数据面前，这数据更是微不足道，所以根据二八定律，它基本上能满足搜索更快的需求。这种是将块或者区域作为一个整体的思想来实现快速搜索，有一点像希尔排序一样，虽然检索效率不稳定，但是能够解决大部分的数据效率问题，就等于实现了整个数据的效率问题。
更为重要的是，Elasticsearch中不仅term dictionary实现了倒排索引，而且term index也采用了这种倒排索引，这就相当于又套了一层B-Tree+整体分区法，效率提高了一个档次。
FST增量压缩技术
上面说过，term index 在内存中是以 FST（finite state transducers）的形式保存的，其特点是非常节省内存。Term dictionary 在磁盘上是以分 block 的方式保存的，一个 block 内部利用公共前缀压缩，比如都是 Ab 开头的单词就可以把 Ab 省去。这样 term dictionary 可以比 b-tree 更节约磁盘空间。那么什么是FTS呢？
FST的含义：
FSTs are finite-state machines that map a term (byte sequence) to an arbitrary output.
简单的来说，就是用更小的内存空间来储存更多的数据；这就是FST增量压缩技术的核心思想。那么Elasticsearch是如何使用FST来节省空间，达到快速检索的功能了？
FST有两个优点：（1）空间占用小。通过对词典中单词前缀和后缀的重复利用，压缩了存储空间；（2）查询速度快。O(len(str))的查询时间复杂度。
下面简单描述下FST的构造过程。我们对“cat”、 “deep”、 “do”、 “dog” 、“dogs”这5个单词进行插入构建FST（注：必须已排序）
（1）插入“cat”
插入cat，每个字母形成一条边，其中t边指向终点。
cat.png
（2）插入“deep”
与前一个单词“cat”进行最大前缀匹配，发现没有匹配则直接插入，P边指向终点。
deep.png
（3）插入“do”
与前一个单词“deep”进行最大前缀匹配，发现是d，则在d边后增加新边o，o边指向终点。
do.png
（4）插入“dog”
与前一个单词“do”进行最大前缀匹配，发现是do，则在o边后增加新边g，g边指向终点。
dog.png
（5）插入“dogs”
与前一个单词“dog”进行最大前缀匹配，发现是dog，则在g后增加新边s，s边指向终点。
dogs.png
最终，我们得到了如上一个有向无环图。利用该结构可以很方便的进行查询，如给定一个term “dog”，我们可以通过上述结构很方便的查询存不存在，甚至我们在构建过程中可以将单词与某一数字、单词进行关联，从而实现key-value的映射。
字节bitmaps存储
之前说过，使用我们要储存term的前缀放入term dictionary似乎就是更小的空间；然而并不是，FST的所用的更小空间实际上是一个byte类型的数组，也就是所谓的字节数组，为了实现这种储存方式，Elasticsearch的倒排索引，将每一个term对应的posting list和其对应的term dictionary都采用short类型的数组建立索引，比如说mop, moth, pop, star, stop and top(term index里的term前缀)映射到序号：0，1，2，3，4，5(term dictionary的block位置)。这就相当于Map<string, integer>的键值对的方式，来实现更小的空间储存。
简单的posting list 和bitmaps对应关系如下：
image.png
字节数组分区bitset存储
似乎按字节数组那样储存就已经是最小了，答案显然是错误的；倒排索引提供了一种针对特殊field,比如性别、状态这种只有极少的值，如果按照字节数组来存储，当有海量数据时，那么每一种值对应的term,bitmaps所储存的字节数组也会非常的大，那么该如何储存呢？Elasticsearch posting list倒排索引采用了字节数组分区存储；以0-65535为一个区，65536-131071为下一个区，以此类推，再用再用<商，余数>的组合表示每一组索引id，这样每组里的id范围都在0~65535内了。65535是short类型储存的最大值，正好是用2个字节能表示的最大数。
简单的posting list 和bitset对应关系如下：
image.png
与其保存 100 个 0，占用 100 个 bit。还不如保存 0 一次，然后声明这个 0 重复了 100 遍。这就是bitset的核心所在。
倒排索引规定：
If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value
上述规定posting list的数组长度超过4kb时采用字节数组分区bitset存储，低于4kb时采用字节bitmaps存储。这里的4kb 刚好是磁盘每次随机读取的一个块block的字节大小，更是linux系统规定内存每次读取最小的内存单位。
联合索引查询
传统关系型数据库的做法：
image.png
如上图所示，mysql怎么做到联合查询的呢？实际上是通过mysql的连接查询来实现的，那么连接查询是怎么查询的，首先拿出第一张表里的每一条数据，逐一到第二张表一条一条数据逐一的对照，不论对照是否匹配，都要进行匹配，上述是mysql连接查询的4种方式：内连接、左连接、右连接和全连接的结果，可以看出它们每一种都要匹配6*16=96次，才能得出结果。
此外，对于关系型数据库 mysql 来说，如果你给 age 和 gender 两个字段都建立了索引，查询的时候只会选择其中最为严格的索引来使用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉，并且很多种情况比如包含NULL值的列、组合索引组合不当和like 前缀出现通配符等会导致索引失效，这样就大大的降低了检索效率。那么要如何才能联合使用两个索引呢？有两种办法：
使用 skip list 数据结构。同时遍历 gender 和 age 的 posting list，互相 skip；
使用 bitset 数据结构，对 gender 和 age 两个 filter 分别求出 bitset，对两个 bitset 做 “位与” 操作。
skip list
skip list数据结构核心是将一个有序链表level0，挑出其中几个元素到level1及level2，每个level越往上，选出来的指针元素越少，查找时依次从高level往低查找。也就是说每一个链表都有一个指针，每个指针都只要移动一次完整的遍历链表即可，这样比传统的数据库mysql 联表查询一条一条的遍历另一张表的效率要快很多。
比如以下3个posting list,互相 skip过程:
image.png
执行整个过程如下：
Next -> 2
Advance(2) -> 13
Advance(13) -> 13
Already on 13
Advance(13) -> 13 MATCH!!!
Next -> 17
Advance(17) -> 22
Advance(22) -> 98
Advance(98) -> 98
Advance(98) -> 98 MATCH!!!
最后得出的交集是 [13,98]，所需的时间比完整遍历三个 posting list 要快得多。但是前提是每个 list 需要指出 Advance 这个操作，快速移动指向的位置。
此外当得出这个结果交集的时候，Elasticsearch 还进行了以下方式对内存数据进行压缩，减少读取磁盘速度，提高效率。
image.png
对我们要查询的结果进行增量压缩，也就是posting list每一个结果都对应一个int类型的数值，那么第一个采用原值去储存，第二个采用第二个值与第一个值的差来储存，这样就能将posting list中大的值变的相对小一点，然后就可以用更小的空间去存储。
bitset 按位与
如果查询的数据是用bitset方式存储，那么就太过简单了，只要按位与，就能查询到两个结果的交集。
网友评论