Lucene列式存儲格式DocValues詳解

DocValues是在Lucene4.0引入的新特性，屬于正向索引。它存儲文檔編號到字段值正向關(guān)系的索引，意在取代FieldCache在搜索時所發(fā)揮的作用，消除搜索時需要加載倒排索引構(gòu)建FieldCache而引起的性能問題。相當于將FieldCache的構(gòu)建下推至索引時，以空間換時間，從而獲得更高的搜索性能。倒排索引是搜索的核心，而正向索引則為搜索結(jié)果的排序和統(tǒng)計等搜索結(jié)果加工過程提供了有力幫助。

倒排索引，也稱反向索引，它是通過Term（字段值）召回相關(guān)的文檔編號。DocValues則通過文檔編碼號召回字段值。

簡單理解DocValues的話，它是一個以DocID為鍵，以Value為值的Map。它存儲DocID到文檔的正向關(guān)系，在排序或者統(tǒng)計計算時，通過DocID可以迅速取字段的值進行二次計算。

DocValues存儲結(jié)構(gòu)

開始之前，有必要先來看一下DocValues存儲上的一些細節(jié)，如針對不同的數(shù)據(jù)特點采用不同的壓縮方案，根據(jù)數(shù)據(jù)集分布情況選擇合適的存儲格式。整個DocValues索引文件中雖說只是存儲了DocID與Values之間的映射關(guān)系，但需要支持的數(shù)據(jù)類型繁多。當然必不可少是DocID和Values，此外為了能維護二者之間的關(guān)系還需要Address信息。針對多值的情況，則有TermsDict以及TermsIndex兩種數(shù)據(jù)，Values還包含Numeric和Binary兩種類型。

Numeric存儲格式

構(gòu)建DocValues過程中有多處數(shù)據(jù)集的數(shù)據(jù)是數(shù)值類型的，Lucene也針對各種數(shù)值集的數(shù)據(jù)特征有多種壓縮方式。除了DocIDSet之外，還有如下幾種方式，但是它們的原理都是一樣的，其它都是變種。

DocValues文件構(gòu)建過程有多種類型的數(shù)據(jù)需要存儲，其中很大一部分是數(shù)值類型的數(shù)據(jù)，它們用到的壓縮類型主要為兩種：DirectWriter，DirectMonotonicWriter。DocIDs雖然也是數(shù)值，但因它特殊而重要的存在地位，Lucene對它做了單獨的優(yōu)化。

DirectWriter

DirectWriter是Lucene為整型數(shù)組重編碼成字節(jié)數(shù)組的工具，它的底層包含一系列編碼器，將整型數(shù)組的所有元素按固定位長度的位存儲。它按Bit存儲，預(yù)留長度過長會浪費空間，短了會因為截斷導(dǎo)致錯誤。因此需要在數(shù)組中查找最大值，由它的長度作為存儲的長度。

假設(shè)有一組數(shù)據(jù){3,16,7,12}，它們會用二進制表示是{101,?10000,?111,?1100}。占用有效位最長的是10000（5個bit），因此需要用5個bits來表示一個數(shù)值，得到如下結(jié)果。

需要注意的是，DirectWriter存儲的最小單位是bit，為了充分使用Byte中每個bit會出現(xiàn)如下圖情況，相當于把byte[]的位展開了成bit[]。

DirectWriter的Buffer是限制內(nèi)存使用，避免OOM的手段，Lucene默認Buffer大小是1024Bytes。它包含壓縮的long[]和壓縮后的byte[]，它們兩者占用內(nèi)存不大于1024字節(jié)，一旦達到限制條件會將Buffer的數(shù)據(jù)編碼輸出。

DirectWriter用重編碼方式進行數(shù)組壓縮的功能，它在整個數(shù)組的所有元素都不大的情況下能帶來不錯的壓縮效果。

DirectMonotonicWriter

DirectMonotonicWriter是DirectWriter的擴展結(jié)構(gòu)，它在DirectWriter之上加入分組的功能。數(shù)據(jù)分片是為了讓每個分片內(nèi)的數(shù)據(jù)分布平穩(wěn)，即標準差比較小、數(shù)據(jù)波動幅度更平緩。

它不是通用方案，它僅適用于單調(diào)遞增的數(shù)組。它通過計算兩者之間的增量，讓所有元素迅速縮小。所以這是非常適合存儲文件地址之類比較連續(xù)的數(shù)據(jù)。比如{100,102,103,105}，最終會變成{100,2,1,2}。如果將第一個元素存到.dvm文件，則變成{0,2,1,2}，僅需要一個字節(jié)即可。

StartFP是數(shù)據(jù)寫入在.dvd文件的起始位置，BLOCK_SHIFT決定每個Block的大小，BlockIdx指向具體的Block位置。 每個Block都是一個獨立的DirectWriter，它們有各自的元數(shù)據(jù)信息。每個Block內(nèi)部是一個DirectWriter結(jié)構(gòu)，這里沒有展開來。

DirectMonotonicWriter的每個Block實現(xiàn)上是由DirectWriter編碼，它還為每個Block創(chuàng)建索引并且保存在.dvm文件中。寫入過程會記錄整個Block的平均值和最小值。

使用DirectMonotonicWriter的前提是數(shù)據(jù)必須從小到大排序的，在增長平緩情況下能夠達到非常不錯的壓縮效果。

GCD-Compression

GCD-Compression是DirectWriter擴展，底層結(jié)構(gòu)與DirectWriter完全一樣，只是寫入的值是加工過的。GCD與DirectMonotonicWriter不一樣，實質(zhì)上它算不上是擴展，只是將數(shù)據(jù)寫入之前做一次預(yù)計算，核心工作還是由DirectWriter完成的。下面還會提及Table-Compression，它跟GCD的原理完全一樣，就是計算方式不同。

Lucene為了保證此計算可逆在.dvm記下方程的兩個參數(shù)（gcd和min）的值。需要先求出整個數(shù)組的最大公約數(shù)，通過公式將所有元素縮小。比如，{9,6,12,33}，它的最大公約數(shù)是3，最小值是6，將數(shù)組縮小之后得{1,0,2,9}。原數(shù)組用DirectWriter存儲需要3個字節(jié)，縮小后僅需要2個字節(jié)，顯然這種方式可以有效縮小每個元素的大小從而獲得更高壓縮比。尤其在數(shù)據(jù)集比較大，分布離散的數(shù)據(jù)集，NumericField的值恰好滿足這些特點。

IndexedDISI存儲格式

存儲格式是根據(jù)數(shù)據(jù)集的分布而設(shè)定的存儲方案，對于DocIDSet這種特殊的結(jié)構(gòu)，Lucene設(shè)計了IndexedDISI結(jié)構(gòu)，它充分利用了數(shù)據(jù)集的稀稠性特點。

IndexedDISI按65535的倍數(shù)為界將DocIDSet分組，故第n組的所有DocIDs必須在65535*(n-1)~65535*n范圍內(nèi)。當有些文檔的字段無值時，便會出現(xiàn)某些組DocID的數(shù)量不滿65535，當它小于4096時，Lucene將它視為稀疏結(jié)構(gòu)用short[]存儲；反之則是稠密結(jié)構(gòu)用BitSet存儲。當然所有的DocID都存在，則稱為全量，那也沒必要存儲DocIDSet了，僅寫一個Flag來表示即可。

BitSet的存儲空間復(fù)雜度由它的最大值唯一決定，那么數(shù)據(jù)集比較小而最大值比較大時，這種方案存儲代價會比較高的。而對short[]它的存儲復(fù)雜度是隨數(shù)量的增長呈正相關(guān)，而4096這個數(shù)值是BitSet與short[]存儲復(fù)雜度的分水嶺。小于則是稀疏的short[]結(jié)構(gòu)，否則則是稠密的BitSet結(jié)構(gòu)。

注：這里畫的示意圖并不準確，因為每個Block可能是稀疏的，也可能是稠密的。這里僅是為了表示稀疏和稠密的Block的結(jié)構(gòu)，并不代表真正的存儲結(jié)構(gòu)。最后一個Block用于代表沒有更多的文檔，這里的Times表示第N個Block。

需要注意的是DocIDSet的所有DocID都存在時，DocIDSet可以省略，通過在Meta文件寫入一個Flag值表示全量。因此這種情況不需要在data文件上寫入任何內(nèi)容。最終在.dvm文件會是如上圖所示情景，此時.dvd不需要再記錄DocIDSet的相關(guān)信息。

DocValues類型

Lucene當前版本（Lucene 7.5）DocValues共支持五種字段的值類型，且針對每種字段值的類型有不同的編碼策略，以適應(yīng)它們的數(shù)據(jù)特征。DocValues如今還不支持分詞字段類型，將來可能會支持。

不管是哪種字段值類型，Lucene都是用.dvd文件存儲DocValues的數(shù)據(jù)；用.dvm文件存儲DocValues的元數(shù)據(jù)，用于解析數(shù)據(jù)文件。每種字段類型都涉及到這樣的一對文件，下面我們挖掘一下每種類型的存儲結(jié)構(gòu)。

與Lucene其它的索引文件不一樣的是，Lucene的文檔基本沒有介紹DocValues索引文件的存儲結(jié)構(gòu)，所以我們需要通過源代碼來勾繪它的結(jié)構(gòu)示意圖。如Document有多個DocValues字段的話，每個字段的數(shù)據(jù)文件將是存儲在同一個索引文件.dvd上，同樣元數(shù)據(jù)文件也是。

所有的DocValues類型中，.dvm文件的結(jié)構(gòu)遠比.dvd文件復(fù)雜。.dvm記錄整個DocValues字段的各種元數(shù)據(jù)，通過.dvm文件才能將.dvd的數(shù)據(jù)還原。Lucene將DocValues的DocIDSet和Values分開存儲在.dvd文件上，而且兩者之間并沒有強關(guān)聯(lián)，全憑.dvm來維護它們之間的關(guān)系。 雖然在字段層面上.dvd文件的大體結(jié)構(gòu).dvm相差不多，而且走進字段內(nèi)部結(jié)構(gòu)會有天壤之別。

Solr已經(jīng)弱化了DocValues值的類型，對用戶完全屏蔽的DocValues的具體類型。實際上它在Lucene是強類型，每種類型的存儲結(jié)構(gòu)也不盡相同。

1. Numeric

Numeric是針對數(shù)值的DocValues類型，它僅能處理單值的字段。NumericField/SortedNumericField都沒有直接支持浮點型，但我們可以通過重編碼的方式將Float轉(zhuǎn)成Integer，將Double轉(zhuǎn)成Long的方式曲線達成支持浮點型的目標。

Numeric類型的結(jié)構(gòu)比較簡單，畫出來的結(jié)構(gòu)示意如下：

Type是DocValues，這里值為Lucene70DocValuesFormat.NUMERIC。

第一個StartFP存儲IndexedDISI在.dvd文件起始位置的地址。當DocIDSet為空或者全量時，Lucene不需要記錄IndexedDISI，僅在.dvm寫入StartFP特殊標記的值，隨后的Length為-1（表示.dvd文件中沒有IndexedDISI，它原意是指IndexedDISI在占用.dvd多大空間）。

當字段唯一值個數(shù)不超256個時，會觸發(fā)Table-Compressed壓縮。一旦啟用Table-Compressed壓縮，Lucene將會把所有值去重并排序之后寫入.dvm文件。而后，.dvd文件的Values部分內(nèi)容改記為每個值在排序之后的新次序。

優(yōu)化后Values的每個元素都不會大于256，直接采用DirectWriter編碼寫在.dvm文件中。那么它下標與Value即是Table的數(shù)據(jù)結(jié)構(gòu)了，在寫Values的時候，將Value通過這個Table獲取下標寫入.dvd文件完成DocIDSet與Values的映射。更多細節(jié)內(nèi)容可參考Lucene官方文檔介紹的Table-Compressed壓縮方式。

如果Values沒條件啟用Table-Compressed壓縮，它將會是以GCD-Compressed方式壓縮，所以它會在.dvm文件記下DirectWriter編碼成多少個Bit，最小值以及GCD值。

2. SortedNumeric

SortedNumeric是Numeric類型的升級版，它支持多值。如果所有文檔都不超過1個值時，它們的存儲結(jié)構(gòu)基本類似（就是在Numeric結(jié)構(gòu)的后面加一個NumDocsWithField來說明字段有多個文檔）。只不過此時會在.dvm文件后加NumDocsWithField來標明是否為多值字段。

SortedNumeric的存儲結(jié)構(gòu)僅比Numeric多了NumDocsWithFields和Addresses。由于IndexedDISI與Values分開存儲的，從示意圖上可以知道它們之前沒有直接關(guān)系。對于單值的情況，DocValues將DocID和Value寫入順序相同，即是IndexedDISI的第n個DocID對應(yīng)第n個Value。

但是在多值場景下，這種方式就失去它的功能了。因為Document的值的個數(shù)無法確定，因此需要額外記錄每個文檔有幾個值。這就是圖中Addresses部分的內(nèi)容，它采用DirectMonotonicWriter編碼，它的結(jié)構(gòu)跟DirectMonotoincWriter的完全一樣。

Addresses有什么用呢？ Address是銜接DocId與Values映射的橋梁，通過Address能讓DocID快速找到DocID對應(yīng)的Values，它可能有多個Values，可能是Numeric類型，也可能是Binary。對于Numeric而言，由于它的長度是已知的（NumBitsRequired)，所以它記錄的Values的個數(shù)。而對于Binary而言，它的長度是未知的，所以它需要記錄每個值的長度。

3. Binary

Binary類型支持byte[]的DocValues，它的長度不能超過32766 Bytes且必須是單值。實際上StringField字段類型有值長度的要求，Binary作為StringField對應(yīng)的DocValues類型，跟StringField有相同的要求。

Binary類型的結(jié)構(gòu)與SortedNumeric類似，比較簡單。將.dvd文件存儲結(jié)構(gòu)展示如下圖:

Binary的記錄的Addresses與SortedNumeric略有不同，SortedNumeric記的是每個文檔有幾個值，而Binary則是記每個Term的長度。

4. Sorted

Sorted是實現(xiàn)了排序的Binary類型，它也是單值，此外它先預(yù)將byte[]排序之后再寫到文件。它在Values部分記錄的并不是真正的Value，而是記錄Value的次序（ordinal，去重排序后的下標），這是與Binary的不同之處。OrdinalValues是Value的次序，基于DirectWriter編碼存儲。

如果是SingleDocs（文檔數(shù)<=1）的情況下，元數(shù)據(jù)中OrdinalValues的NumerOfBitsPerOrd,StartFP和Length三個值均為零。此時也表示.dvd也沒記錄OrdinalValues的信息。

Sorted出現(xiàn)兩個新的結(jié)構(gòu)TermsDict和TermsIndex，故名思義TermsDict是Terms字典，作為字典是不會有重復(fù)的詞元的；TermsIndex是TermsDict索引。它們的意義在于TermsDict是去重之后存儲的，所以它在一定程序上能夠節(jié)減空間開銷；另外排序之后Values與IndexedDISI存儲在.dvd文件中下標不一致，需要額外映射表來串聯(lián)它們的關(guān)系。

TermsIndex并不是TermsDict的元數(shù)據(jù)，它會同時出現(xiàn)在.dvm和.dvd兩個文件中。

TermsDict算是實現(xiàn)了映射表的作用，TermsDict每個Term的下標等同于Ordinal，因此通過Ordinal便能獲取TermsDict的位置了。

TermsDict

TermsDict采用了分組存儲的方式，每1024個文檔為一個組。分組存儲的好處是方便構(gòu)建索引，其次能夠?qū)崿F(xiàn)起到壓縮前綴的作用。如下圖，每個Block只有第一元素是直接存儲的，之后每個元素都跟前一元素共享共同前綴（如果有的話）。通常來說，Term的長度不會太長，所以Lucene在這里又做了一個小優(yōu)化，一個字節(jié)的前4個位來存儲共同前綴的長度，后4個位存儲后綴的長度。如果4位表示不了，則會以VInt的格式寫在后面。

每1024個Term構(gòu)成一個Block，每個Block會在Addresses中記文件地址索引，Addresses采用DirectMonotonicWriter編碼。而DirectMonotonicWriter也會將1024個Address打成Packed，每個Packed也會它記的文件地址索引，不過是記在.dvm文件上。需要注意的是這里的Terms是TermsDict，Term不重復(fù)。dvm文件的Addresses索引是為了讓Lucene能夠成功解析.dvd文件的Terms的，并不是讓我們用它來檢索的。

TermsIndex

TermsIndex結(jié)構(gòu)與TermsDict基本一樣，它將Terms中每個Block的第一個Term寫到.dvd文件中，將它的位置寫在Addresses中，所以還會按Addresses的Block生成一個索引記在.dvm文件。

5. SortedSet

SortedSet是支持多值且有序的Binary類型，它是Sorted類型的加強版。單值是采用Sorted結(jié)構(gòu)，多值的結(jié)構(gòu)如下圖所示。結(jié)構(gòu)上跟Sorted非常相似，只是多加一個Addresses結(jié)構(gòu)記錄每個Doc有多少個值，跟SortedNumeric的做法一樣。

結(jié)語

在Lucene的官方文檔中，關(guān)于DocValues的介紹可謂是少之又少，所以只能通過剖析代碼來理解它的實現(xiàn)細節(jié)。本文先梳理了DocValues所涉及到的幾種編碼方式，而后介紹了各種數(shù)據(jù)類型的結(jié)構(gòu)，從Numeric到Binary，從單值到多值。借助此文，希望能讓你領(lǐng)略DocValues設(shè)計全貌，洞悉每種類型的設(shè)計異同。

本文轉(zhuǎn)載自微信公眾號【Nosql漫談】。

NoSQL數(shù)據(jù)庫

版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔相應(yīng)法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網(wǎng)站將在24小時內(nèi)刪除侵權(quán)內(nèi)容。