Lucene DocValues索引檔案詳解

文章目錄

• • • 一、 DocValues存儲結構
    • • 1. Numeric存儲格式
      • • 1.1. DirectWriter
        • 1.2. DirectMonotonicWriter
        • 1.3. GCD-Compression
      • 2. IndexedDISI存儲格式
    • 二、DocValues類型
    • • 1. Numeric
      • 2. SortedNumeric
      • 3. Binary
      • 4. Sorted
      • • 1. TermsDict
        • 2. TermsIndex
      • 5. SortedSet
    • 三、結語

DocValues是在Lucene4.0引入的新特性，又稱正向索引。它存儲文檔編号到字段值正向關系的索引，意在取代FieldCache在搜尋時發揮重要作用，消除搜尋時需要加載反向索引建構FieldCache引起性能影響。相當于将FieldCache的建構下推至索引時，并犧牲少量的磁盤空間提升搜尋體驗，将搜尋時間轉移為索引時間，擷取更高效搜尋性能提升。反向索引是搜尋的核心，而正向索引則是搜尋結果的排序和統計等在搜尋結果加工給出了很多可能性。

反向索引，也稱反向索引，它是通過Term（字段值）召回相關的文檔編号。DocValues則通過文檔編碼号召回字段值。

可以簡單的了解DocValues的話，它就是鍵是DocID，值是Value的Map。它存儲DocID到文檔的正向關系，在排序或者統計計算時，通過DocID可以迅速取字段的值進行二次計算。

一、 DocValues存儲結構

開始之前，有必要先來看一下DocValues存儲上的一些細節，諸如針對不同的資料有特定壓縮方案；根據資料集分布情況選擇合适的存儲格式。整個DocValues索引檔案中雖然說隻是存儲了DocID與Values之間的映射關系，但實際上需要存儲的資料類型繁多。當然必不可少是DocID和Values，此外為了能維護二者之間的關系還需要Address。針對多值的情況，則有TermsDict以及TermsIndex兩種資料。Values還Numeric和Binary兩種類型，如此看來整個DocValues内有乾坤，絕非易事。

1. Numeric存儲格式

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

DocValues檔案結建過程有多種類型的需要存儲，其中很大一部分是數值類型的資料，它們用到一些壓縮類型主要是有以下兩種。（DocIDs雖然也是數值類資料，但是它非常特殊，是以Lucene采用特殊方案）

1.1. DirectWriter

DirectWriter是Lucene為整型數組重編碼成位元組數組的工具，它的底層一系列非常底層的編碼器，将整型數組的所有元素按固定位長度的位存儲。它按Bit存儲，預留長度過長會浪費空間，短了會因為截斷導緻錯誤。是以需要在數組中查找最大值，由它的長度作為存儲的長度。

假設有一組資料

{3,16,7,12}

，它們會用二進制表示是{

101

,

10000

,

111

,

1100

}。占用有效位最長的是

10000

（5個bit），是以需要用

5個bits

來表示一個數值，得到如下結果。

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

DirectWriter的Buffer是限制記憶體使用，避免OOM的手段，Lucene預設Buffer大小是1024Bytes。它包壓縮的long[]和壓縮後的byte[]，它們兩者占用記憶體不大于1024位元組，一旦達到限制條件會将Buffer的資料編碼輸出。

DirectWriter用重編碼方式進行數組實作壓縮的功能，它在整個數組的所有元素都不大情況能有不錯的壓縮效果，這也留出了可擴充的空間。

1.2. DirectMonotonicWriter

DirectMonotonicWriter是DirectWriter的擴充結構，它在DirectWriter之上加入分組的功能。資料分片是為了，讓每個片内的資料分布平穩，即是标準差比較小、資料波動幅度更平緩。

它不是通用方案，它僅适用于單調遞增的資料組，即是它隻能用于從小到大排序的的數組。它通過計算兩者之間的增量，讓所有元素迅速縮小。是以這是非常适合存儲檔案位址之類比較連續的資料。比如

{100,102,103,105}

，最終會變成

{100,2,1,2}

。如果将第一個元素存到.dvm檔案，則變成

{0,2,1,2}

，僅需要一個位元組即可。

StartFP是資料寫入在.dvd檔案的起始位置，BLOCK_SHIFT是決定每個Block的大小，BlockIdx指向具體的Block位置。

每個Block都是一個獨立的DirectWriter，它們自己中繼資料資訊。每個Block内部是一個DirectWriter結構，這裡沒有展開來。

DirectMonotonicWriter的每個Block實作上交由是DirectWriter編碼，它還為每個Block建立索引儲存在.dvm檔案中。此外，需要記錄下面公式中的參數AvgInc表示整個Block的平均值，和Block的最小值Min。

計算公式是：（AvgInc是Values增量的數學平均值）

a v g I n c = 1 n ∑ n = 1 n ( v a l u e s n − v a l u e s n − 1 ) − v a l u e s 0 = v a l u e s n − 2 × v a l u e s 0 n v a l n = v a l u e n − a v g I n c × n − v a l u e s 0 avgInc = \frac{1}{n}\sum_{n=1}^n(values_n - values_{n-1}) - values_0 \\ = \frac{values_n - 2 \times values_0 }{n} \\ val_n = value_n -avgInc \times n - values_0 avgInc=n1​n=1∑n​(valuesn​−valuesn−1​)−values0​=nvaluesn​−2×values0​​valn​=valuen​−avgInc×n−values0​

使用DirectMonotonicWriter的前提是資料必須從小到大排序的，在增長平緩情況下能夠達到非常良好的壓縮效果。

1.3. GCD-Compression

GCD-Compression是DirectWriter擴充，底層結構與DirectWriter完全一樣，隻是寫入的值是加工過的。GCD與DirectMonotonicWriter不一樣，實質上它算不上是擴充，隻是将資料寫入之前做一次預計算，實際上還是DirectWriter在工作。（下面還會提及Table-Compression，它跟GCD的原理完全一樣，就是計算公式不同）

Lucene為了保證此計算可逆在.dvm記下方程的兩個參數（gcd和min）的值。GCD的是最大公約數，先求出整個數組的最大公約數，通過公式将所有元素縮小。比如，

{9,6,12,33}

，它的最大公約數是

3

，最小值是

6

，将數組縮小之後得

{1,0,2,9}

。原數組用DirectWriter存儲需要3個位元組，縮小後僅需要2個位元組，顯然這種方式可以有效縮小每個元素的大小進而獲得更高壓縮比。尤其在資料集比較大，分布離散的資料集，NumericField的值恰好滿足這些特點。

2. IndexedDISI存儲格式

存儲格式是根據資料集的分布而設定的存儲方案，對于DocIDSet這種特殊的結構，Lucene設計了IndexedDISI結構（在Lucene源碼中，由IndexedDISI實作的功能，是以我們用它來命名DocIDSet的存儲結構）。它通過資料集的稀稠性的特點，選用對應的存儲結構。

IndexedDISI按65535的倍數為界将DocIDSet分組，故第n組的所有DocIDs必須在

65535*(n-1) —— 65535*n

範圍内。當有些文檔的字段無值時，便會出現某些組DocID的數量不滿65535，當它小于4096時，Lucene将它視為稀疏結構用

short[]

存儲；反之則是稠密結構用

BitSet

存儲。當然所有的DocID都存在，則稱為全量，那也沒必要存儲DocIDSet了，僅寫一個Flag來表示即可。

BitSet的存儲特點是其存儲空間複雜度由它的最大值唯一決定，那麼資料集比較小而最大值比較大時，這種方案存儲代價會比較高的。而對short[]它的存儲複雜度是随數量的增長呈正相關，而4096這個數值是BitSet與short[]存儲複雜度的分水嶺。小于則是稀疏結構，反之是稠密結構。

PS：這裡畫的示意圖并不準确，因為每個Block都可能是稀疏的，也可能是稠密的。這裡僅是為了表示稀疏和稠密的Block的結構，并不代表真正的存儲結構。最後一個Block用于代表沒有更多的文檔，這裡的Times表示第N個Block。

需要注意的是DocIDSet的所有DocID都存在時，DocIDSet可以省略，通過在Meta檔案寫入一個Flag形式表示全量。是以這種情況不需要在data檔案上寫入任何内容。最終在.dvm檔案會是如上圖所示情景，此時.dvd不需要再記錄DocIDSet的相關資訊。

二、DocValues類型

Lucene目前版本（Lucene7.5）DocValues共支援五種字段的值類型，且針對每種字段值的類型有不同的編碼政策，以适應它們的特征發揮更好的性能。DocValues如今還不支援分詞字段類型，将來可能會支援（具體可以關注一下SOLR-8362）。

不管是哪種字段值類型，Lucene都是用

.dvd

檔案存儲DocValues的資料；用

.dvm

檔案存儲DocValues的中繼資料，用于解析資料檔案。每種字段類型都有這對檔案，下面我們就挖掘每種類型的存儲結構。

與Lucene其它的索引檔案不一樣的是，Lucene的文檔基本沒有介紹DocValues索引檔案的存儲結構，是以我們需要通過源代碼來勾繪它的結構示示意圖。如Document有多個DocValues字段的話，每個字段的資料檔案将是存儲在同一個索引檔案.dvd上，同樣中繼資料檔案也是。

所有的DocValues類型中，.dvm檔案的結構遠比.dvd檔案複雜。.dvm記錄整個DocValues字段的各種中繼資料，通過.dvm檔案才能将.dvd的資料還原。Lucene将DocValues的DocIDSet和Values分開存儲在.dvd檔案上，而且兩者之間并沒有強關聯，全憑.dvm來維護它們之間的關系。

雖然在字段層面上.dvd檔案的大體結構.dvm相差不多，而且走進字段内部結構會有天壤之别。

Solr已經弱化了DocValues值的類型，對使用者完全屏蔽的DocValues的具體類型。實際上它在Lucene是強類型，每種類型的存儲結構也不盡相同。

1. Numeric

Numeric是針對數值的DocValues類型，它僅能處理單值的字段。NumericField/SortedNumericField都沒有直接支援浮點型，但我們可以通過重編碼的方式将Float轉成Integer，将Double轉成Long的方式曲線達到支援浮點型的目标。

Numeric類型的結構比較簡單，畫出來的結構示意如下：

1. Type是DocValues，這裡值為

   Lucene70DocValuesFormat.NUMERIC

   。
2. 第一個StartFP存儲IndexedDISI在.dvd檔案起始位置的位址。當DocIDSet為空或者全量時，Lucene不需要記錄IndexedDISI，會在.dvm寫入StartFP特殊标記的值，随後的Length為-1（表示不需要讀.dvd檔案）。它原意是指IndexedDISI在占用.dvd多大空間。

當字段出現唯一值個數不超256個時，會觸發Table-Compreesed的壓縮。一旦啟用Table-Compressed壓縮，Lucene将會所有值去重和排序之後寫入.dvm檔案。然後.dvd檔案的

Values

部分内容改記為錄每個值在排序之後的次序。

優化後Values的每個元素都不會大于256，直接采用DirectWriter編碼寫在.dvm檔案中。那麼它下标與Value即是Table的資料結構了，在寫Values的時候，将Value通過這個Table擷取下标寫入.dvd檔案完成DocIDSet與Values的映射。更多細節内容可參考Lucene官方文檔介紹的Table-Compressed壓縮方式。

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

2. SortedNumeric

SortedNumeric是Numeric類型的更新版，它支援多值。如果所有文檔都不超過1個值時，它們存儲結構基本雷同（就是在Numer結構的最後加一個NumDocsWithField來說明字段有多個文檔）。隻不過此時會.dvm檔案後加值NumDocsWithField來判定是否多值字段。

SortedNumeric的存儲結構僅比Numeric多了

NumDocsWithFields

和

Addresses

。由于IndexedDISI與Values分開存儲的，從示意圖上可以知道它們之前沒有直接關系。對于單值的情況，DocValues将DocID和Value寫入順序相同，即是IndexedDISI的第n個DocID對應第n個Value。

但是在多值場景下，這種方式就失去它的功能了。因為無法Document的值的個數無法确定，是以需要額外記錄每個文檔有幾個值。這就是圖中

Addresses

部分的内容，它采用DirectMonotonicWriter編碼，它的結構跟DirectMonotoincWriter的完全一樣。

Addresses有什麼用呢？

Address是DocId與Values映射的橋梁，通過Address能讓DocID快速找到DocID對應的Values，它可能有多個Values，可能是Numeric類型，也可能是Binary。對于Numeric而言，由于它的長度是已知的（NumBitsRequired)，是以它記錄的Values的個數。而對于Binary而言，它的長度是未知的，是以它是需要記錄每個值的長度。

Lucene官方文檔上指出SortedNumeric有序的，這裡的有序是指單個文檔内多個Numeric值之間有序。這裡跟Sorted/SortedSet的有序含義不太一樣，雖然都是指Values有序，Numeric是說文檔有序；而Sorted/SortedSet由于它們有TermsDict是以可以做到整個Segment範圍内有序。

3. Binary

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

Binary類型的結構與SortedNumeric類似，比較簡單。将.dvd檔案存儲結構展示如下圖:

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

4. Sorted

Sorted是實作了排序的Binary類型，它也是單值，此外它先預将byte[]排序之後再寫到檔案。然後它在

Values

部分記錄的并不是真正的Value，而是記錄Value的次序（ordinal，去重排序後的下标），這與Binary不一樣的地方。

OrdinalValues

是Value的次序，直接DirectWriter編碼存儲的。

如果是SingleDocs（文檔數<=1）的情況下，中繼資料中OrdinalValues的NumerOfBitsPerOrd,StartFP和Length三個值均為零。此時也表示.dvd也沒記錄OrdinalValues的資訊。

Sorted出現兩個新的結構TermsDict和TermsIndex，故名思義TermsDict是Terms字典，作為字典是不會有重複的詞元的；TermsIndex是TermsDict索引。它們的意義在于TermsDict是去重之後存儲的，是以它在一定程式上能夠節減空間開銷；另外排序之後Values與IndexedDISI存儲在.dvd檔案中下标不一緻，需要額外映射表來串聯它們的關系。

TermsIndex并不是TermsDict的中繼資料，它會同時出現在.dvm和.dvd兩個檔案中。

TermsDict算是實作了映射表的作用，TermsDict每個Term的下标等同于Ordinal，是以通過Ordinal便能定會TermsDict的位置了。

1. TermsDict

TermsDict的結構比較複雜，它按每1024個文檔劃分為一個組，分組存儲。當然分組存儲的好處是友善建構索引，其次能夠實作起到壓縮字首的作用。如圖，每個Block隻有第一進制素是直接存儲的，之後每個元素都跟前一進制素共享共同字首（如果有的話）。通常來說，Term的長度不會太長，是以Lucene在這裡又做了一個小優化，一個位元組的前4個位來存儲共同字首的長度，後4個位存儲字尾的長度。如果4位表示不了，則會以VInt的格式寫在後面。

這裡比較有意思是每1024個Term是Block，每個Block會在Addresses記檔案位址索引，Addresses采用DirectMonotonicWriter編碼。而DirectMonotonicWriter也會将1024個Address打成Packed，每個Packed也會它記的檔案位址索引，不過是記在.dvm檔案上。需要注意的是這裡Terms是TermsDict，是沒有重複的Term的。是以在多大數量的TermsDict，它的

Terms' Addrs

索引會有意義呢？

當然，.dvm檔案的Addresses索引是為了讓Lucene能夠成功解析.dvd檔案的Terms的。并不是讓我們用它來檢索，盡管DocValuesField是檢索的能力，也提供檢索的API。

2. TermsIndex

TermsIndex結構與TermsDict基本一樣，它将Terms中每個Block的第一個Term寫到.dvd檔案中，将它的位置寫在Addresses中，是以還會按Addresses的Block生成一個索引記在.dvm檔案。

5. SortedSet

最後SortedSet支援多值且有序的Binary類型，它是Sorted類型的加強版。單值是采用Sorted結構，多值的結構如下。結構上跟Sorted非常相似，隻是多加一個Addresses結構記錄每個Doc有多少個值，跟SortedNumeric的作法一樣。

TermsDict和TermsIndex兩結構則是與Sorted類型完全一樣，準确的說，整個結構使用的存儲結構都是前面出現過并介紹了的，是以這裡就不一一展開介紹了。

三、結語

這裡主要是讨論了Numeric和DocIDSet的編碼方式，以及剖析了五種DocValues類型的存儲結構。屬于探索Lucene存儲結構之美的系列文章，探索Lucene的DocValues存儲結構之美。關于DocValues應用場景，請閱讀《Lucene DocValues詳解》。