MongoDB的索引代碼實現--BtreeBasedAccessMethod

前言

學習開源軟件的最好的辦法就是閱讀代碼，MongoDB整個代碼庫有接近90萬行代碼，DB核心層大概50萬行，代碼量確實非常多。本文作為MongoDB代碼導讀的第一篇，從Index部分上入手分析代碼實現。
為何從索引部分開始介紹，首先代碼量較少，總共5000多行，且相對其他模塊來說比較獨立；其次索引對數據庫的優化至關重要，了解其實現，對日後的運維優化和索引自身的限製約定都具有實際意義。畢竟文檔上的描述還是沒有代碼來的準確。本文沒有逐行的去分析源碼，一來工作量太大，二來也沒有辦法完全揣測出作者的意圖，莫不如隻描述大概，剩下的留給閱讀者自己思考。

代碼導讀

代碼集中在src/db/index目錄下，裏麵並沒有涉及具體的btree數據結構，而是描述了一些操作方法，索引解析等。MongoDB的代碼實現上涉及到了比較多的設計模式，比如Builder，Combination，Strategy，Factory等。如圖，這部分代碼主要采用的是Combination和Adapter模式，整個代碼都圍繞著BtreeBasedAccessMethod。

index_descriptor.h[cpp]

構造函數和初始化成員

_magic_code，通過magic檢查一定程度上避免內存錯誤，野指針等造成的數據錯亂。
_collection，所屬的Collection
_infoObj，配置管理信息
_numFields，索引字段數量，大於一個就是聯合索引
_keyPattern，索引匹配串
_parentNS，namespace
_isIdIndex，ID索引，如果索引字段隻是_id則認為是IDIndex
_indexName，索引的名字，用戶可以指定
_sparse，是否是稀疏索引，稀疏索引不包含NULL字段
_unique，是否是唯一索引
_indexNamespace，索引的namespace，parentNs.$name
_version，數據結構版本號，0和1兩個，參看btree_key_generator.h[cpp]
_cachedEntry，看到再說

areIndexOptionsEquivalent

檢查是否是稀疏索引，是否是_ID索引，並且是否是唯一索引，注釋裏也說明了，不關心ID索引的排序順序，因為升序或者降序，對查詢來說，都是等價的，最後比較Options，注意version和ns是不比較的，background是創建時的參數，創建後就不再有意義

index_cursor.h

定義了一些遊標接口方法，並聲明了Yield邏輯，注釋寫的很清晰：

/**
 * Yielding semantics:
 * If the entry that a cursor points at is not deleted during a yield, the cursor will
 * point at that entry after a restore.
 * An entry inserted during a yield may or may not be returned by an in-progress scan.
 * An entry deleted during a yield may or may not be returned by an in-progress scan.
 * An entry modified during a yield may or may not be returned by an in-progress scan.
 * An entry that is not inserted or deleted during a yield will be returned, and only once.
 * If the index returns entries in a given order (Btree), this order will be mantained even
 * if the entry corresponding to a saved position is deleted during a yield.
 */

如果遊標指向的元素在Yield期間沒有被刪除，那麼在恢複後仍然指向這個位置。在Yield時，插入，刪除，或者修改的元素，是否會被遊標發現是不確定的。

因為考慮的效率問題，遊標可能會Cache一批數據，這部分數據不會與原始的數據同步。同樣，Yield時沒有加入或者刪除的元素，都會被返回，且隻返回一次。

元素的返回順序應該按照指定的順序返回（升序或者降序），甚至是在Yield期間，指向的元素被刪除了也要維持原有的順序返回。

index_access_method.h[cpp]

操作接口，CRUD方法，注意是非線程安全的。對調用者來說，需要考慮底層的所以結構，接口的行為是不透明的。注釋比較簡單，不翻譯了：

/** 
 * An IndexAccessMethod is the interface through which all the mutation, lookup, and
 * traversal of index entries is done. The class is designed so that the underlying index
 * data structure is opaque to the caller.
 *
 * IndexAccessMethods for existing indices are obtained through the system catalog.
 *
 * We assume the caller has whatever locks required.  This interface is not thread safe.
 *
 */

btree_based_access_method.h[cpp]

繼承自IndexAccessMethod，聲明getKeys，交給由子類實現，是個Adapter模式。

insert
通過getKeys獲得doc的所有key，然後進行迭代修改Index，修改成功後，會對numInserted++，計數，統計本次操作修改索引次數。如果遇到失敗情況，則要清理所有之前已經寫入的數據，保證操作的原子性，即使失敗，也要保證恢複到操作之前的數據狀態（索引結構可能會發生變化，但是數據集合是等價的）。另外，background build index，可能會重複插入索引，因為doc數據可能會在磁盤上移動，也就是會被重複掃描到。

remove
remove比insert就簡單多了，因為remove是不可能失敗的

find
找到後返回RecordID

update
對比先後兩個對象，計算出diff，包括需要刪除的和需要增加的，然後批量提交修改。注意，這裏可能會失敗，但是失敗後索引沒有再回滾到之前的數據集合。並且是先刪除後增加，極端情況下會導致索引錯誤。思考：如果是先增加後刪除，是不是更合適一點？

btree_based_bulk_access_method.h[cpp]

隻支持insert的bulk操作，insert的數據先保存在一個外部存儲裏，最大內存使用10MB大小，commit時再全部讀出處理。

btree_key_generator.h[cpp]

該對象封裝了一套解析解析算法，目的是解析出obj中的索引key，MongoDB相比較於傳統的DB係統，在索引創建上支持Array結構，Array數據內容會根據索引擴展出來。

例如：

索引Pattern：{a: 1, b: 1}
被索引OBJ：{a: [1, 2, 3], b: 2}，
解析出來的IndexKeys：{'': 1, '': 2}{'': 2, '': 2}{'': 3, '': 2}

特別說明的是，隻支持並列的一個數組索引，如果是多個數據都想被索引，會失敗。因為會造成索引數量的不可控(A*B)。

實際上，MongoDB這裏提供了兩個版本的算法，V0和V1，2.0以後的MongoDB默認采用了V1，V0與WT存儲引擎上還有寫兼容性問題，參見：SERVER-16893
所以，MongoDB現在隻在mmap上支持V0算法，相關的檢驗代碼：

catalog_index.cpp

if (v == 0 && !getGlobalEnvironment()->getGlobalStorageEngine()->isMmapV1()) {
    return Status( ErrorCodes::CannotCreateIndex,
                  str::stream() 
                  << "use of v0 indexes is only allowed with the " 
                  << "mmapv1 storage engine");
}

V1和V0的不同點也集中在數組的處理上，V0版本，過於簡單，很多數組結構索引解析出來的結果不完整，主要體現在了NULL的處理。
例如：

Pattern	Obj	V0	V1
{'a.b.c':1}	{a:[1,2,{b:{c:[3,4]}}]}	[{:3 }{:4}]	[{:null}{:3}{:4}]
{'a':1,'a.b':1}	{a:[{b:1}]}	[{:[{b:1} ],:1}]	[{:{b:1},:1}]
{a:1,a:1}	{a:[1,2]}	[{:1,:[ 1,2]}{:2,:[1,2]}]	[{:1,:1}{:2,:2}]

更多的數據測試可以參考btree_key_generator_test.cpp中的測試case。

雖然官方在ReleaseNote裏說明：V1版本的索引更快，更節省空間，但實際上是V0版本算法漏洞太多。參見ReleaseNote 2.0

其他

index目錄下還包含了FTS，GEO相關的代碼沒有說明，FTS部分等閱讀到了在說，畢竟使用的場景不多；GEO部分涉及到了一些地理運算，圖形學運算，雖然不複雜，後麵作為GEO的專題討論。餘下的代碼，主要邏輯在BtreeKeyGenerator部分，尤其是V1算法，讀者可以再認真學習下。

最後更新：2017-04-01 13:37:07

MongoDB的索引代碼實現--BtreeBasedAccessMethod

MongoDB的索引代碼實現--BtreeBasedAccessMethod

前言

代碼導讀

index_descriptor.h[cpp]

index_cursor.h

index_access_method.h[cpp]

btree_based_access_method.h[cpp]

btree_based_bulk_access_method.h[cpp]

btree_key_generator.h[cpp]

其他

上一篇： PostgreSQL 如何比較兩個表的定義是否一致

下一篇： PostgreSQL 為什麼不要濫用unlogged table & hash index

相關內容

熱門內容

最新內容