Elasticsearch索引結(jié)構(gòu)與算法解析
提到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)文章!
相關(guān)文章
Java中的Web MVC簡(jiǎn)介_動(dòng)力節(jié)點(diǎn)Java學(xué)院整理
MVC模型是一種架構(gòu)型的模式,本身不引入新功能,只是幫助我們將開發(fā)的結(jié)構(gòu)組織的更加合理,使展示與模型分離、流程控制邏輯、業(yè)務(wù)邏輯調(diào)用與展示邏輯分離2017-09-09詳解java中面向?qū)ο笤O(shè)計(jì)模式類與類的關(guān)系
這篇文章主要介紹了java面向?qū)ο笤O(shè)計(jì)模式中類與類之間的關(guān)系,下面小編和大家一起來學(xué)習(xí)一下吧2019-05-05SpringMVC中DispatcherServlet的HandlerMapping詳解
這篇文章主要介紹了SpringMVC中DispatcherServlet的HandlerMapping詳解,上回說的Handler,我們說是處理特定請(qǐng)求的,也就是說,不是所有的請(qǐng)求都能處理,那么問題來了,我們?cè)踔滥膫€(gè)請(qǐng)求是由哪個(gè)Handler處理的呢,需要的朋友可以參考下2023-10-10Java鏈表數(shù)據(jù)結(jié)構(gòu)及其簡(jiǎn)單使用方法解析
這篇文章主要介紹了Java鏈表數(shù)據(jù)結(jié)構(gòu)及其簡(jiǎn)單使用方法解析,文章圍繞主題展開詳細(xì)的內(nèi)容介紹,具有一定的參考價(jià)值,需要的小伙伴可以參考一下2022-07-07