ElasticSearch探索之路（四）索引原理：倒排索引、列式存储、Fielddata、索引压缩、联合索引
文章目錄
- 倒排索引
- Term dictionary與Term index
- 列式存儲——Doc Values
- Fielddata
- 索引壓縮
- FOR編碼
- Roaring Bitmaps
- 聯(lián)合索引
倒排索引
例如，假設我們有兩個文檔，每個文檔的 content 域包含如下內容：
為了創(chuàng)建倒排索引，首先我們需要借助分詞器，將每個文檔的 content 域拆分成單獨的詞（我們稱它為 詞條 或 tokens、term ），創(chuàng)建一個包含所有不重復詞條的排序列表，然后列出每個詞條出現在哪個文檔。
Term Doc_1 Doc_2 ------------------------- Quick | | X The | X | brown | X | X dog | X | dogs | | X fox | X | foxes | | X in | | X jumped | X | lazy | X | X leap | | X over | X | X quick | X | summer | | X the | X | ------------------------如果我們想搜索 quick brown ，我們只需要查找包含每個詞條的文檔：
Term Doc_1 Doc_2 ------------------------- brown | X | X quick | X | ------------------------ Total | 2 | 1這里我們匹配到了兩個文檔（為了節(jié)省空間，這里返回的只是文檔ID，最后再通過文檔id去查詢到具體文檔。）。對于搜索引擎來說，用戶總希望能夠先看到相關度更高的結果，因此實際使用時我們通過一些算法來進行權重計算，將查詢的結果按照權重降序返回。
Term dictionary與Term index
Elasticsearch為了能夠快速的在倒排索引中找到某個term，他會按照字典序對所有的term進行排序，再通過二分查找來找到term，這就是Term Dictionary，但即使有了Term Dictionary，O(logN)的磁盤讀寫仍然是影響性能的一大問題。
B-Tree通過減少磁盤尋道次數來提高查詢性能，Elasticsearch也是采用同樣的思路，直接通過內存查找term，不讀磁盤，但是如果term太多，term dictionary也會很大，放內存不現實，于是有了Term Index，從下圖可以看出，Term Index其實就是一個Trie樹（前綴樹）
Term index這棵樹不會包含所有的term，它包含的是term的一些前綴。通過term index可以快速地定位到term dictionary的某個offset，然后從這個位置再往后順序查找。
查找流程為什么Elasticsearch/Lucene檢索比mysql快呢？
Mysql只有term dictionary這一層，是以b-tree排序的方式存儲在磁盤上的。檢索一個term需要若干次的random access的磁盤操作。而Lucene在term dictionary的基礎上添加了term index來加速檢索，term index以樹的形式緩存在內存中。從term index查到對應的term dictionary的block位置之后，再去磁盤上找term，大大減少了磁盤的random access次數。
列式存儲——Doc Values
Doc values的存在是因為倒排索引只對某些操作是高效的。 倒排索引的優(yōu)勢在于查找包含某個項的文檔，而對于從另外一個方向的相反操作并不高效，即：確定哪些項是否存在單個文檔里，聚合需要這種次級的訪問模式。
以排序來舉例——雖然倒排索引的檢索性能非常快，但是在字段值排序時卻不是理想的結構。
- 在搜索的時候，我們能通過搜索關鍵詞快速得到結果集。
- 當排序的時候，我們需要倒排索引里面某個字段值的集合。換句話說，我們需要轉置倒排索引。
轉置 結構經常被稱作 列式存儲 。它將所有單字段的值存儲在單數據列中，這使得對其進行操作是十分高效的，例如排序、聚合等操作。
在Elasticsearch中，Doc Values就是一種列式存儲結構，在索引時與倒排索引同時生成。也就是說Doc Values和倒排索引一樣，基于 Segement生成并且是不可變的。同時Doc Values和倒排索引一樣序列化到磁盤。
Doc Values常被應用到以下場景：
- 對一個字段進行排序
- 對一個字段進行聚合
- 某些過濾，比如地理位置過濾
- 某些與字段相關的腳本計算
下面舉一個例子，來講講它是如何運作的
假設存在以下倒排索引
Term Doc_1 Doc_2 Doc_3 ------------------------------------ brown | X | X | dog | X | | X dogs | | X | X ------------------------------------那么其生成的DocValues如下（實際存儲時不會存儲doc_id，值所在的順位即為doc_id）
Doc_id Values ------------------ Doc_1 | brown | Doc_1 | dog | Doc_2 | brown | Doc_2 | dogs | Doc_3 | dog | Doc_3 | dogs | ------------------假設我們需要計算出brown出現的次數
GET /my_index/_search {"query":{"match":{"body":"brown"}},"aggs":{"popular_terms":{"terms":{"field":"body"}}},"size" : 0 }下面來分析上述請求在ES中是如何來進行查詢的：
但是doc_values仍存在一些問題，其不支持analyzed類型的字段，因為這些字段在進行文本分析時可能會被分詞處理，從而導致doc_values將其存儲為多行記錄。但是在我們實際使用時，為什么仍然能對analyzed的字段進行聚合操作呢？這時就需要介紹一下Fielddata
Fielddata
doc values不生成分析的字符串，那為什么這些字段仍然可以使用聚合呢？是因為使用了fielddata的數據結構。與doc values不同，fielddata構建和管理100%在內存中，常駐于JVM內存堆。
從歷史上看，fielddata 是所有字段的默認設置。但是Elasticsearch已遷移到doc values以減少 OOM 的幾率。分析的字符串是仍然使用fielddata的最后一塊陣地。 最終目標是建立一個序列化的數據結構類似于doc values ，可以處理高維度的分析字符串，逐步淘汰 fielddata。
它的一些特性如下
- 延遲加載。如果你從來沒有聚合一個分析字符串，就不會加載fielddata到內存中，其是在查詢時候構建的。
- 基于字段加載。 只有很活躍地使用字段才會增加fielddata的負擔。
- 會加載索引中（針對該特定字段的） 所有的文檔，而不管查詢是否命中。邏輯是這樣：如果查詢會訪問文檔 X、Y 和 Z，那很有可能會在下一個查詢中訪問其他文檔。
- 如果空間不足，使用最久未使用（LRU）算法移除fielddata。
因此，在聚合字符串字段之前，請評估情況：
- 這是一個not_analyzed字段嗎？如果是，可以通過doc values節(jié)省內存 。
- 否則，這是一個analyzed字段，它將使用fielddata并加載到內存中。這個字段因為N-grams有一個非常大的基數？如果是，這對于內存來說極度不友好。
索引壓縮
FOR編碼
在Elasticsearch中，為了能夠更方便的計算交集和并集，它要求倒排索引是有序的，而這個特點同時也帶來了一個額外的好處，我們可以使用增量編碼來壓縮倒排索引，也就是FOR（Frame of Reference）編碼
增量編碼壓縮，將大數變小數，按字節(jié)存儲
FOR編碼分為三個步驟
- 增量編碼
- 增量分區(qū)
- 位壓縮
如下圖所示，如果我們的倒排索引中存儲的文檔id為[73, 300, 302, 332, 343, 372]，那么經過增量編碼后的結果則為[73, 227, 2, 30, 11, 29]。這種壓縮的好處在哪里呢？我們通過增量將原本的大數變成了小數，使得所有的增量都在0～255之間，因此每一個值就只需要使用一個字節(jié)就可以存儲，而不會使用int或者bigint，大大的節(jié)約了空間。
接著，第二步我們將這些增量分到不同的區(qū)塊中（Lucene底層用了256個區(qū)塊，下面為了方便展示之用了兩個）。
第三步，我們計算出每組數據中最大的那個數所占用的bit位數，例如下圖中區(qū)塊1最大的為227，所以只占用8個bit位，所以三個數總共占用3 * 8bits即3字節(jié)。而區(qū)塊2最大為29，只占用5個bit位，因此這三個數總共占用3 * 5bits即差不多2字節(jié)。通過這種方法，將原本6個整數從24字節(jié)壓縮到了5字節(jié)，效果十分出色。
ROF編碼實例Roaring Bitmaps
FOR編碼對于倒排索引來說效果很好，但對于需要存儲在內存中的過濾器緩存等不太合適，兩者之間有很多不同之處：
- 由于我們僅僅緩存那些經常使用的過濾器，因此它的壓縮率并不需要像倒排索引那么高（倒排索引需要對每個詞都進行編碼）。
- 緩存過濾器的目的就是為了加速處理效率，因此它必須要比重新執(zhí)行過濾器要快，因此使用一個好的數據結構和算法非常重要。
- 緩存的過濾器存儲在內存之中，而倒排索引通常存儲在磁盤中。
基于以上的不同，對于緩存來說FOR編碼并不適用，因此我們還需要考慮其他的一些選擇。
- 整數數組：數組可能是我們馬上能想到的最簡單的實現方式，我們將文檔id存儲在數組中，這樣就使得我們的迭代變得非常簡單，但是這種方法的內存利用率又十分低下，因為每個文檔都需要4個字節(jié)。
- Bitmaps：在數據分布密集的下，位圖是一個很好的選擇。它本質上就是一個數組，其中每一個文檔id占據一個位，用0和1來標記文檔是否存在。這種方法大大節(jié)約了內存，將一個文檔從4字節(jié)降低到了一個位，但是一旦數據分布稀疏，此時的位圖性能將大打折扣，因為無論數據量多少，位圖的大小都是由數據的上下區(qū)間來決定的。
- Roaring Bitmaps：Roaring Bitmaps即是對位圖的一種優(yōu)化，它會根據16位最高位將倒排索引劃分為多塊，如第一個塊將對0到65535之間的值進行編碼，第二個塊將在65536和131071之間進行編碼。在每一個塊中，我們再對低16位進行編碼，如果它的值小于4096在使用數組，否則就使用位圖。由于我們編碼的時候只會對低16位進行編碼，因此在這里數組每個元素只需要2個字節(jié)
為什么要使用4096作為數組和位圖選取的閾值呢？
下面是官方給出的數據報告，在一個塊中只有文檔數量超過4096，位圖的內存優(yōu)勢才會凸顯出來
位圖與數組內存利用對比這就是Roaring Bitmaps高效率的原因，它基于兩種完全不同的方案來進行編碼，并根據內存效率來動態(tài)決定使用哪一種方案。
官方也給出了幾種方案的性能測試
迭代性能 跳過性能——稀疏集 跳過性能——密集集 內存占用 構造時間從上述對比可以看出，沒有一種方法是完美的，但是以下兩種方法的巨大劣勢使得它們不會被選擇
- 數組：性能很好，但是內存占用巨大。
- Bitmaps：數據稀疏分布的時候內存和性能都會大打折扣。
因此在綜合考量下，Elasticsearch還是選擇使用Roaring Bitmaps，并且在很多大家了解的開源大數據框架中，也都使用了這一結構，如Hive、Spark、Kylin、Druid等。
聯(lián)合索引
如果多個字段索引的聯(lián)合查詢，倒排索引如何滿足快速查詢的要求呢？
- 跳表：同時遍歷多個字段的倒排索引，互相skip。
- 位圖：對多個過濾器分別求出位圖，對這幾個位圖做AND操作。
Elasticsearch支持以上兩種的聯(lián)合索引方式，如果查詢的過濾器緩存到了內存中（以位圖的形式），那么合并就是兩個位圖的AND。如果查詢的過濾器沒有緩存，那么就用跳表的方式去遍歷兩個硬盤中的倒排索引。
假設有下面三個倒排索引需要聯(lián)合索引：
假設有三個倒排索引- 如果使用跳表，則對最短的倒排索引中的每一個id，逐個在另外兩個倒排索引中查看是否存在，來判斷是否存在交集。
- 如果使用位圖，則直接將幾個位圖按位與運算，最終得到的結果就是最后的交集。
總結
以上是生活随笔為你收集整理的ElasticSearch探索之路（四）索引原理：倒排索引、列式存储、Fielddata、索引压缩、联合索引的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ElasticSearch探索之路（三）
- 下一篇： ElasticSearch探索之路（五）