作者：京东物流 李洪吉
提到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的原理，可能帮咱们宽阔下视线，理解数字之美，算法之美。