作者：京东物流 李洪吉
提到 ES，大多数爱好者想到的都是搜索引擎，但是明确一点，ES 不等同于搜索引擎。不管是谷歌、百度、必应、搜狗为代表的自然语言处理 (NLP)、爬虫、网页处理、大数据处理的全文搜索引擎，还是有明确搜索目的的搜索行为，如各大电商网站、OA、站内搜索、视频网站的垂直搜索引擎，他们或多或少都使用到了 ES。
作为搜索引擎的一部分，ES 自然具有速度快、结果准确、结果丰富等特点，那么 ES 是如何达到 “搜索引擎” 级别的查询效率呢？首先是索引，其次是压缩算法，接下来我们就一起了解下 ES 的索引结构和压缩算法
1 结构
1.1 Mysql
Mysql 下的 data 目录存放的文件就是 mysql 相关数据，mysql 文件夹对应的就是数据库 mysql。
其中表 columns_priv 对应了 3 个文件：columns_priv.frm、columns_priv.MYD、columns_priv.MYI。
.frm：表结构；.MYD：myisam 存储引擎原数据；.MYI：myisam 存储引擎索引；.ibd：innodb 存储引擎数据
1.2 Elasticsearch
cfe 为索引文，cfs 为数据文件，cfe 文件保存 Lucene 各文件在.cfs 文件的位置信息
cfs、cfe 在 segment 还很小的时候，将 segment 的所有文件都存在在 cfs 中，在 cfs 逐渐变大时，大小超过 shard 的 10%，则会拆分为其他文件，如 tim、dvd、fdt 等文件
1.3 存储结构
倒排索引结构分为倒排表、词项字典、词项索引
倒排表包含某个词项的所有 id 的数据存储了在.doc 文件中
词项字典包含了 index field 的所有经过处理之后的词项数据，最终存储在.tim 文件中
1.4 结构对比
我们以某商城的手机为例，左侧为 es 倒排索引结构，右侧为原始数据。左侧图示只是为了展示倒排索引结构，并不是说 es 中倒排表就是简单的数组
以上面结构对比示例图为例，假如共有 10 亿条数据需要存储在 ES 中 (上图右)，分词后存储的倒排表 (上图左) 大概包含分词 term 以及对应的 id 数组等，在 10 亿条数据中，分词 “小米” 相关的数据有 100 万条，也就是说分词 “小米” 对应的数组 Posting List 长度是 100 万
id 是 int 类型的有序主键，分词 “小米” 在数组 Posting List 中 100 万 int 类型数字总长度 = 100 万?每个 int 占 4 字节 = 400 万 Byte≈4MB。1 个分词占 4MB 空间，假如 10 亿条数据有 500 万个分词，总空间 = 4MB?500 万 = 2 千万 MB，磁盘空间直接爆炸
2 算法
分词对应的数组 Posting List 实际就是一个个有序数组，而有序数值数组是比较容易进行压缩处理的，而且一般来说压缩效益也不错，如果能对其进行压缩是能够大大节约空间资源的
ES 中倒排索引的压缩算法主要有 FOR 算法 (Frame Of Reference) 和 RBM 算法 (RoaringBitMap)
2.1 FOR
FOR 算法的核心思想是用减法来削减数值大小，从而达到降低空间存储。 假设 V (n) 表示数组中第 n 个字段的值，那么经过 FOR 算法压缩的数值 V (n)=V (n)-V (n-1)。也就是说存储的是后一位减去前一位的差值。存储是也不再按照 int 来计算了，而是看这个数组的最大值需要占用多少 bit 来计算
我们按照差值计算的方式来保存数据，初始值为 1，2 与 1 的差值为 1，3 与 2 的差值为 1…… 最终我们就将原始 Posting List 数据转化为 100 万个 1，每个 1 我们可以用 1bit 来记录，总空间 = 1bit?100 万 = 100 万 bit，相比原有 400 万 Byte=3200bit，空间压缩了 32 倍
在实际生产中，不可能出现一个 term 的 Posting List 是这种差值均为 1 的情况，所以我们以通用示例举例。假如原数据为 [73，300，302，332，343，372], 数组中 6 个数字占据总空间为 24 字节。按照差值方式记录，数组转化为 [73,227,2,30,11,29], 最大数字为 227，大于 2 的 7 次方 128，小于 2 的 8 次方 256，所以每个数字可以使用 8bit 即 1Byte 来保存，占据总空间为 1Byte*6 + 1Byte=7Byte
在此基础上，我们将差值数组按照密集度划分为 [73,227] 和 [2,30,11,29]，其中 [73,227] 中最大值 227 介于 2 的 7 次方和 2 的 8 次方之间，所以用 8bit=1Byte 作为切割分段，[2,30,11,29] 中最大数 30 介于 2 的 4 次方和 2 的 5 次方之间，所以用 5bit 作为切割分段。
数组 [73,227] 占据总空间为 8bit?2 个 = 16bit=2Byte
数组 [2,30,11,29] 占据总空间为 5bit?4 个 = 20bit=3Byte
为什么 20bit=3Byte 呢？因为 8bit=1Byte，小于 8bit 也会占据 1 个字节空间，所以 17bit 到 24bit 均为 3Byte
所以，最终占据总空间 = 1+2+1+3=7Byte
疑问一：既然原数组 [73，300，302，332，343，372] 要按照密集度拆分为 [73,227] 和 [2,30,11,29] 两个数组，那为什么不继续往下拆分，直接拆分到每个数字是一个数组，这样使用 bit 记录时占据总空间会更少？
答：如果继续拆分数组，空间确实会使用更少，但是，之前我们提到搜索引擎速度快的方式有两种：高效的压缩算法和快速的编码解码速度，单个数字存储确实压缩了空间，但是我们无法再通过解码的方式将源数据还原
疑问二：为什么源数据使用差值记录占据 6Byte，拆分数组后占据 7Byte，拆分后占据空间不变，有时候甚至会变大，为什么？
答：数据量小的情况下确实会出现该情况，因为我们需要拆分数组并记录拆分数组的长度（如上面示例中的 8bit 和 5bit），在原数据存储空间基础上还要存储拆分长度，所以数据量小的情况下会出现比直接存储占据空间大的情况。但是不管是搜索引擎还是 Elasticsearch 更多处理的是海量数据，数据量越多，差值数组拆分的方式节省空间越明显
2.2 RBM
我们已经了解了 FOR 压缩算法，算法核心是将 PostingList 按照差值密集度转化成两个差值数组。在这里我们要考虑一种情况就是：在大数据中，10 亿条数据分词 500 万个，如果分词 “小米” 所在 PostList 比较分散且差值很大，此时使用 FOR 算法效果就会大打折扣。所以稀疏的数组，不适合使用 FOR 算法
在这里我们以 [1000，62101，131385，132052，191173，196658] 为例，如果按照 FOR 算法，转化成的差值数组为 [1000，61101，69284，667，59121，5485] 密集度很低。我们采用 RBM 算法
源数据 PostingList 是由 int 类型组成的数组，int 类型 = 4Byte=32bit，最大值 = 2 的 32 次方 – 1=4294967295≈43 亿。当数据较大且稀疏时，我们将 32bit 拆分为 16bit 和 16bit，16bit 最大值 = 65535，前 16bit 存放商，后 16bit 存放余数，所以商和余数都不会超过 65535. 我们将源数组的值除以 65536，得到的商和余数分别存放在前 16bit 和后 16bit。
以数字 196658 为例，转化为 2 进制，前 16 位 = 3，后 16 位 = 50
得到的结果以 K-V 存放。Key 最大值为 16bit，所以以 short [] 数组存放，Value 以 Container 存放。
由于源数组为有序数组，所以按照高低 16 位转化后，商和余数都是从小到大排列
通过看 Container 源码，我们可以看到 Container 有 3 种：ArrayContainer、BitmapContainer、RunContainer。
- ArrayContainer 本质为集合，所以随着数组中数量越多，占用空间越多，呈正向增长。
当数组种数量为 4096 时，占据总空间 = 4096 个?16bit (即 2Byte)?1024=8KB
当数组种数量为 65536 时，占据总空间 = 65536 个?16bit (即 2Byte)?1024=128KB
- BitmapContainer 位图，核心就是将原有存储数值转化成该数值在哪个位置上存在
由于余数最大值为 65535，所以我们需要 65536 位位图，数值是多少，在位图上对应的位置就是多少。数值等于 4096，则位图上 4096 位值为 1；数值等于 65535，则位图上 65535 位值为 1。每个位置上的数都占用 8KB 空间（8KB=65536bit）
- RunContainer 用法相对狭隘，这种类型是 Lucene 5 之后新增的类型，主要应用在连续数字的存储商，比如倒排表中存储的数组为 [1,2,3…100W] 这样的连续数组，如果使用 RunContainer，只需存储开头和结尾两个数字：1 和 100W，即占用 8 个字节。这种存储方式的优缺点都很明显，它严重收到数字连续性的影响，连续的数字越多，它存储的效率就越高
- 如果数组是如下形式 [1,2,3,4,5,100,101,102,999,1000,1001] 就会被拆分为三段：[1,5],[100,102],[999,1001]
至于每次存储采用什么容器，需要进行一下判定，比如 ArrayContainer，当存储的元素少于 4096 个时，他会比 BitmapContainer 占用更少空间，而当大于 4096 个元素时，采用 ArrayContainer 所需要的空间就会大于 8kb，那么采用 BitmapContainer 就会占用更少空间
3 总结
ES 在处理海量数据时通过其独到的结构和压缩算法，将索引效率尽可能的提升。虽然在实际业务处理中我们极少遇到海量数据处理的情况，但是通过了解 ES 的原理，能够帮我们开阔下视野，了解数字之美，算法之美。
© 著作权归作者所有
