提到ES，大多數(shù)愛好者想到的都是搜索引擎，但是明確一點(diǎn)，ES不等同于搜索引擎。不管是谷歌、百度、必應(yīng)、搜狗為代表的自然語言處理(NLP)、爬蟲、網(wǎng)頁處理、大數(shù)據(jù)處理的全文搜索引擎，還是有明確搜索目的的搜索行為，如各大電商網(wǎng)站、OA、站內(nèi)搜索、視頻網(wǎng)站的垂直搜索引擎，他們或多或少都使用到了ES。

?作為搜索引擎的一部分，ES自然具有速度快、結(jié)果準(zhǔn)確、結(jié)果豐富等特點(diǎn)，那么ES是如何達(dá)到“搜索引擎”級(jí)別的查詢效率呢？首先是索引，其次是壓縮算法，接下來我們就一起了解下ES的索引結(jié)構(gòu)和壓縮算法

1 結(jié)構(gòu)

1.1 Mysql

Mysql下的data目錄存放的文件就是mysql相關(guān)數(shù)據(jù)，mysql文件夾對(duì)應(yīng)的就是數(shù)據(jù)庫mysql。

其中表columns_priv對(duì)應(yīng)了3個(gè)文件：columns_priv.frm、columns_priv.MYD、columns_priv.MYI。

.frm：表結(jié)構(gòu)；.MYD：myisam存儲(chǔ)引擎原數(shù)據(jù)；.MYI：myisam存儲(chǔ)引擎索引；.ibd：innodb存儲(chǔ)引擎數(shù)據(jù)

1.2 Elasticsearch

cfe為索引文，cfs 為數(shù)據(jù)文件，cfe文件保存Lucene各文件在.cfs文件的位置信息

cfs、cfe 在segment還很小的時(shí)候，將segment的所有文件都存在在cfs中，在cfs逐漸變大時(shí)，大小超過shard的10%，則會(huì)拆分為其他文件，如tim、dvd、fdt等文件

1.3 存儲(chǔ)結(jié)構(gòu)

倒排索引結(jié)構(gòu)分為倒排表、詞項(xiàng)字典、詞項(xiàng)索引

倒排表包含某個(gè)詞項(xiàng)的所有id的數(shù)據(jù)存儲(chǔ)了在.doc文件中

詞項(xiàng)字典包含了index field的所有經(jīng)過處理之后的詞項(xiàng)數(shù)據(jù)，最終存儲(chǔ)在.tim文件中

1.4 結(jié)構(gòu)對(duì)比

我們以某商城的手機(jī)為例，左側(cè)為es倒排索引結(jié)構(gòu)，右側(cè)為原始數(shù)據(jù)。左側(cè)圖示只是為了展示倒排索引結(jié)構(gòu)，并不是說es中倒排表就是簡(jiǎn)單的數(shù)組

以上面結(jié)構(gòu)對(duì)比示例圖為例，假如共有10億條數(shù)據(jù)需要存儲(chǔ)在ES中(上圖右)，分詞后存儲(chǔ)的倒排表(上圖左)大概包含分詞term以及對(duì)應(yīng)的id數(shù)組等，在10億條數(shù)據(jù)中，分詞“小米”相關(guān)的數(shù)據(jù)有100萬條，也就是說分詞“小米”對(duì)應(yīng)的數(shù)組Posting List長度是100萬

id是int類型的有序主鍵，分詞“小米”在數(shù)組Posting List中100萬int類型數(shù)字總長度=100萬?每個(gè)int占4字節(jié)=400萬Byte≈4MB。1個(gè)分詞占4MB空間,假如10億條數(shù)據(jù)有500萬個(gè)分詞，總空間=4MB?500萬=2千萬MB，磁盤空間直接爆炸

2 算法

分詞對(duì)應(yīng)的數(shù)組Posting List實(shí)際就是一個(gè)個(gè)有序數(shù)組，而有序數(shù)值數(shù)組是比較容易進(jìn)行壓縮處理的，而且一般來說壓縮效益也不錯(cuò)，如果能對(duì)其進(jìn)行壓縮是能夠大大節(jié)約空間資源的

ES中倒排索引的壓縮算法主要有FOR算法(Frame Of Reference)和RBM算法(RoaringBitMap)

2.1 FOR

FOR算法的核心思想是用減法來削減數(shù)值大小，從而達(dá)到降低空間存儲(chǔ)。 假設(shè)V(n)表示數(shù)組中第n個(gè)字段的值，那么經(jīng)過FOR算法壓縮的數(shù)值V(n)=V(n)-V(n-1)。也就是說存儲(chǔ)的是后一位減去前一位的差值。存儲(chǔ)是也不再按照int來計(jì)算了，而是看這個(gè)數(shù)組的最大值需要占用多少bit來計(jì)算

我們按照差值計(jì)算的方式來保存數(shù)據(jù)，初始值為1，2與1的差值為1，3與2的差值為1……最終我們就將原始Posting List數(shù)據(jù)轉(zhuǎn)化為100萬個(gè)1，每個(gè)1我們可以用1bit來記錄，總空間=1bit?100萬=100萬bit，相比原有400萬Byte=3200bit，空間壓縮了32倍

在實(shí)際生產(chǎn)中，不可能出現(xiàn)一個(gè)term的Posting List是這種差值均為1的情況，所以我們以通用示例舉例。假如原數(shù)據(jù)為[73，300，302，332，343，372],數(shù)組中6個(gè)數(shù)字占據(jù)總空間為24字節(jié)。按照差值方式記錄，數(shù)組轉(zhuǎn)化為[73,227,2,30,11,29],最大數(shù)字為227，大于2的7次方128，小于2的8次方256，所以每個(gè)數(shù)字可以使用8bit即1Byte來保存，占據(jù)總空間為1Byte*6 + 1Byte=7Byte

在此基礎(chǔ)上，我們將差值數(shù)組按照密集度劃分為[73,227]和[2,30,11,29]，其中[73,227]中最大值227介于2的7次方和2的8次方之間，所以用8bit=1Byte作為切割分段，[2,30,11,29]中最大數(shù)30介于2的4次方和2的5次方之間，所以用5bit作為切割分段。

數(shù)組[73,227]占據(jù)總空間為8bit?2個(gè)=16bit=2Byte

數(shù)組[2,30,11,29]占據(jù)總空間為5bit?4個(gè)=20bit=3Byte

為什么20bit=3Byte呢？因?yàn)?bit=1Byte，小于8bit也會(huì)占據(jù)1個(gè)字節(jié)空間，所以17bit到24bit均為3Byte

所以，最終占據(jù)總空間=1+2+1+3=7Byte

疑問一：既然原數(shù)組[73，300，302，332，343，372]要按照密集度拆分為[73,227]和[2,30,11,29]兩個(gè)數(shù)組，那為什么不繼續(xù)往下拆分，直接拆分到每個(gè)數(shù)字是一個(gè)數(shù)組，這樣使用bit記錄時(shí)占據(jù)總空間會(huì)更少？

答：如果繼續(xù)拆分?jǐn)?shù)組，空間確實(shí)會(huì)使用更少，但是，之前我們提到搜索引擎速度快的方式有兩種：高效的壓縮算法和快速的編碼解碼速度，單個(gè)數(shù)字存儲(chǔ)確實(shí)壓縮了空間，但是我們無法再通過解碼的方式將源數(shù)據(jù)還原

疑問二：為什么源數(shù)據(jù)使用差值記錄占據(jù)6Byte，拆分?jǐn)?shù)組后占據(jù)7Byte，拆分后占據(jù)空間不變，有時(shí)候甚至?xí)兇?，為什么?/p>

答：數(shù)據(jù)量小的情況下確實(shí)會(huì)出現(xiàn)該情況，因?yàn)槲覀冃枰鸱謹(jǐn)?shù)組并記錄拆分?jǐn)?shù)組的長度（如上面示例中的8bit和5bit），在原數(shù)據(jù)存儲(chǔ)空間基礎(chǔ)上還要存儲(chǔ)拆分長度，所以數(shù)據(jù)量小的情況下會(huì)出現(xiàn)比直接存儲(chǔ)占據(jù)空間大的情況。但是不管是搜索引擎還是Elasticsearch更多處理的是海量數(shù)據(jù)，數(shù)據(jù)量越多，差值數(shù)組拆分的方式節(jié)省空間越明顯

2.2 RBM

我們已經(jīng)了解了FOR壓縮算法，算法核心是將PostingList按照差值密集度轉(zhuǎn)化成兩個(gè)差值數(shù)組。在這里我們要考慮一種情況就是：在大數(shù)據(jù)中，10億條數(shù)據(jù)分詞500萬個(gè)，如果分詞“小米”所在PostList比較分散且差值很大，此時(shí)使用FOR算法效果就會(huì)大打折扣。所以稀疏的數(shù)組，不適合使用FOR算法

在這里我們以[1000，62101，131385，132052，191173，196658]為例，如果按照FOR算法，轉(zhuǎn)化成的差值數(shù)組為[1000，61101，69284，667，59121，5485]密集度很低。我們采用RBM算法

源數(shù)據(jù)PostingList是由int類型組成的數(shù)組，int類型=4Byte=32bit，最大值=2的32次方-1=4294967295≈43億。當(dāng)數(shù)據(jù)較大且稀疏時(shí)，我們將32bit拆分為16bit和16bit，16bit最大值=65535，前16bit存放商，后16bit存放余數(shù)，所以商和余數(shù)都不會(huì)超過65535.我們將源數(shù)組的值除以65536，得到的商和余數(shù)分別存放在前16bit和后16bit。

以數(shù)字196658為例，轉(zhuǎn)化為2進(jìn)制，前16位=3，后16位=50

得到的結(jié)果以K-V存放。Key最大值為16bit，所以以short[]數(shù)組存放，Value以Container存放。

由于源數(shù)組為有序數(shù)組，所以按照高低16位轉(zhuǎn)化后，商和余數(shù)都是從小到大排列

通過看Container源碼，我們可以看到Container有3種：ArrayContainer、BitmapContainer、RunContainer。

• ArrayContainer本質(zhì)為集合，所以隨著數(shù)組中數(shù)量越多，占用空間越多，呈正向增長。

當(dāng)數(shù)組種數(shù)量為4096時(shí)，占據(jù)總空間=4096個(gè)?16bit(即2Byte)?1024=8KB

當(dāng)數(shù)組種數(shù)量為65536時(shí)，占據(jù)總空間=65536個(gè)?16bit(即2Byte)?1024=128KB

• BitmapContainer位圖，核心就是將原有存儲(chǔ)數(shù)值轉(zhuǎn)化成該數(shù)值在哪個(gè)位置上存在

由于余數(shù)最大值為65535，所以我們需要65536位位圖，數(shù)值是多少，在位圖上對(duì)應(yīng)的位置就是多少。數(shù)值等于4096，則位圖上4096位值為1；數(shù)值等于65535，則位圖上65535位值為1。每個(gè)位置上的數(shù)都占用8KB空間（8KB=65536bit）

• RunContainer用法相對(duì)狹隘，這種類型是Lucene 5之后新增的類型，主要應(yīng)用在連續(xù)數(shù)字的存儲(chǔ)商，比如倒排表中存儲(chǔ)的數(shù)組為 [1,2,3…100W] 這樣的連續(xù)數(shù)組，如果使用RunContainer，只需存儲(chǔ)開頭和結(jié)尾兩個(gè)數(shù)字：1和100W，即占用8個(gè)字節(jié)。這種存儲(chǔ)方式的優(yōu)缺點(diǎn)都很明顯，它嚴(yán)重收到數(shù)字連續(xù)性的影響，連續(xù)的數(shù)字越多，它存儲(chǔ)的效率就越高
• 如果數(shù)組是如下形式 [1,2,3,4,5,100,101,102,999,1000,1001] 就會(huì)被拆分為三段：[1,5],[100,102],[999,1001]

至于每次存儲(chǔ)采用什么容器，需要進(jìn)行一下判定，比如ArrayContainer，當(dāng)存儲(chǔ)的元素少于4096個(gè)時(shí)，他會(huì)比BitmapContainer占用更少空間，而當(dāng)大于4096個(gè)元素時(shí)，采用ArrayContainer所需要的空間就會(huì)大于8kb，那么采用BitmapContainer就會(huì)占用更少空間

3 總結(jié)

ES在處理海量數(shù)據(jù)時(shí)通過其獨(dú)到的結(jié)構(gòu)和壓縮算法，將索引效率盡可能的提升。雖然在實(shí)際業(yè)務(wù)處理中我們極少遇到海量數(shù)據(jù)處理的情況，但是通過了解ES的原理，能夠幫我們開闊下視野，了解數(shù)字之美，算法之美。

以上就是Elasticsearch索引結(jié)構(gòu)與算法解析的詳細(xì)內(nèi)容，更多關(guān)于Elasticsearch索引與算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論