數(shù)據(jù)庫索引技術(shù)之Lsm樹

作者： fasionchan 2021-11-12 05:00:00

由于數(shù)據(jù)在寫入時(shí)，自動(dòng)切分成一個(gè)個(gè)文件。數(shù)據(jù)庫需要在后臺(tái)對(duì)文件進(jìn)行合并，以減少文件數(shù)，進(jìn)而加快查詢。如果待合并文件里的數(shù)據(jù)是有序的，我們就可以采用歸并排序算法來提高合并效率。

[[434628]]

上次我們分享了采用哈希索引實(shí)現(xiàn)的存儲(chǔ)引擎，它總是將寫操作不斷追加到數(shù)據(jù)文件，就跟寫日志一樣。這種日志結(jié)構(gòu)式的存儲(chǔ)引擎，數(shù)據(jù)記錄順序由寫入時(shí)間決定，同一鍵的舊記錄由新記錄取代。

SSTable

雖然這看起來會(huì)違背順序?qū)懙脑瓌t，但也有辦法解決，我們稍后介紹。

現(xiàn)在，我們將數(shù)據(jù)文件格式改成這樣：①文件中的所有記錄，按照鍵( key )來排序;②排序保證了每個(gè)鍵只在文件中出現(xiàn)一次，不會(huì)有重復(fù)的舊記錄。姑且將這種格式叫做排序字符串表( sorted string table )簡(jiǎn)稱 SSTable 。

相比普通日志結(jié)構(gòu)式的數(shù)據(jù)文件，SSTable 有幾個(gè)明顯優(yōu)勢(shì)：

高效合并

如果您學(xué)過歸并排序算法，應(yīng)該知道合并兩個(gè)有序序列是一個(gè) 既簡(jiǎn)單又高效的操作：

逐個(gè)遍歷待合并文件，將最小的鍵拷貝到輸出文件即可。如果同一個(gè)鍵在多個(gè)文件中出現(xiàn)，則以寫入時(shí)間比較新的記錄為準(zhǔn)，其他均可丟棄。合并后得到的 SSTable 文件，數(shù)據(jù)也是按鍵排好順序的，而且重復(fù)鍵均已去重。

SSTable 文件保存某段時(shí)間內(nèi)寫入的數(shù)據(jù)，一個(gè) SSTable 數(shù)據(jù)跟另一個(gè)比較，要么較新，要么較舊。因此可以用這個(gè)特性進(jìn)行去重，重復(fù)鍵以較新的 SSTable 為準(zhǔn)。

合并時(shí)則必須保證 SSTable 是相鄰的，否則就亂套了。假設(shè)有三個(gè) SSTable ，按時(shí)段依次是 A 、B 、C ，其中 C 最新。如果先將 A 和 C 合并得到 X ，就無法再跟 B 合并了。因?yàn)?X 中的數(shù)據(jù)有的來自 A ，有的來自 C ，不好判斷是比 C 新還是比 C 舊。

合并操作非常高效，算法時(shí)間復(fù)雜度是，基本等同于將數(shù)據(jù)從源文件拷貝到目標(biāo)文件即可。

讀取待合并文件時(shí)是順序讀，寫結(jié)果文件時(shí)又是順序?qū)? ，對(duì)磁盤非常友好。文件系統(tǒng)可以先預(yù)讀待合并數(shù)據(jù)，然后緩存起來;又可以收集待寫入數(shù)據(jù)，然后再批量寫;磁盤 IO 操作便顯著減少。

合并過程對(duì)內(nèi)存要求極低，就算文件遠(yuǎn)遠(yuǎn)大于可用的物理內(nèi)存也毫不礙事。

稀疏索引

您可能會(huì)這么想，既然 SSTable 數(shù)據(jù)是有序的，查詢時(shí)是否可以用二分查找法進(jìn)行搜索呢?

雖然二分查找法的時(shí)間復(fù)雜度是，但對(duì)磁盤操作來說還不夠好。由于磁盤非常慢，IO 操作應(yīng)該盡可能地減少，最好是只執(zhí)行一次 IO 就能拿到數(shù)據(jù)。但二分查找需要執(zhí)行次 IO 操作，而且每次讀取的位置都不一樣，對(duì)磁盤很不友好。

既然不能用二分查找法直接搜索磁盤數(shù)據(jù)，那就只能在內(nèi)存中維護(hù)數(shù)據(jù)索引了。

由于磁盤中的 SSTable 是按鍵排序的，我們可以采用排序樹(比如紅黑樹)來組織索引，這樣可以支持范圍查詢。舉個(gè)例子，查詢鍵在 A 和 B 之間的數(shù)據(jù)，可以先通過排序樹索引，找到第一個(gè)大于等于 A 的數(shù)據(jù)的偏移量;再從該位置開始逐個(gè)讀取，直到數(shù)據(jù)鍵大于 B 。

實(shí)際上，內(nèi)存索引沒有必要包含全部的鍵，每隔一定距離挑一個(gè)鍵即可：

如上圖，索引只包含部分鍵，大概呈均勻分布。當(dāng)我們查詢 bananas 時(shí)，我們查找內(nèi)存中的索引，并沒有找到該鍵。盡管如此，我們可以確定 bananas 落在 banalize 和 bandboxy 這兩個(gè)鍵之間。

因此，只要從 banalize 鍵偏移量開始，不斷遍歷數(shù)據(jù)即可。如果當(dāng)前 SSTable 包含 bananas ，那我們遍歷少量數(shù)據(jù)后即可找到;如果不包含 bananas ，我們遍歷到第一個(gè)比 bananas 大的鍵后即可停止。

稀疏索引一般每隔若干 KB 數(shù)據(jù)才維護(hù)一個(gè)索引項(xiàng)，內(nèi)存使用量大大降低，但查詢時(shí)卻要讀取更多數(shù)據(jù)。

好在磁盤數(shù)據(jù)是按塊讀取的，就算數(shù)據(jù)不夠一個(gè)塊，也得整塊讀取;而且由于磁盤尋址的因素，讀一塊和若干塊的時(shí)間差別其實(shí)很小。因此，就算查詢時(shí)需要多讀一些數(shù)據(jù)，對(duì)性能也不會(huì)產(chǎn)生太大的負(fù)面影響。

節(jié)省磁盤帶寬

由于查詢時(shí)可能需要掃描兩個(gè)索引項(xiàng)之間的全部數(shù)據(jù)記錄(如上圖陰影部分)，因此可以將它們組織成邏輯數(shù)據(jù)塊，壓縮之后再寫到磁盤，索引條目則指向每個(gè)壓縮塊的開頭。

由于相鄰數(shù)據(jù)條目通常比較相像，至少他們的鍵都有相同的前綴，因此壓縮后的尺寸能顯著降低。這一方面節(jié)約了磁盤空間，另一方面則降低了磁盤 IO 帶寬。

雖然壓縮、解壓縮需要消耗一定的 CPU 資源，好在 CPU 通常不是存儲(chǔ)系統(tǒng)的主要瓶頸，磁盤 IO 才是。

因此，壓縮是一種典型的以時(shí)間換空間的技術(shù)選擇，通過犧牲 CPU 資源來緩解帶寬資源。在 Web 領(lǐng)域，服務(wù)器也經(jīng)常對(duì)數(shù)據(jù)進(jìn)行壓縮，以節(jié)約帶寬資源，縮短傳輸時(shí)間。

LSM樹

SSTable 查詢表現(xiàn)不錯(cuò)，但數(shù)據(jù)庫寫操作肯定是亂序的，怎樣才能將數(shù)據(jù)排序保存呢?

在磁盤中維護(hù)排序結(jié)構(gòu)倒也可行，B樹( b-tree )就可以做到，但太復(fù)雜了。

如果是在內(nèi)存里，事情就簡(jiǎn)單多了。眾所周知，我們有很多數(shù)據(jù)結(jié)構(gòu)可供選擇，比如紅黑樹( red-black tree )和 AVL樹。這些數(shù)據(jù)結(jié)構(gòu)在亂序插入的前提下，也能支持有序遍歷。

這樣一來，我們可以這么設(shè)計(jì)：

寫操作到達(dá)后，將其保存到內(nèi)存中的平衡樹結(jié)構(gòu)(比如紅黑樹)。這棵在內(nèi)存中維護(hù)的平衡樹稱為 memtable 。

當(dāng) memtable 數(shù)據(jù)增長達(dá)到一定閾值(通常是若干 MB )，就將其轉(zhuǎn)成 SSTable 文件并寫到磁盤。由于 memtable 平衡樹數(shù)據(jù)是按鍵排序，轉(zhuǎn)寫過程很高效——中序遍歷數(shù)據(jù)并順序?qū)懙酱疟P即可。

雖然 memtable 轉(zhuǎn)寫效率很高，還是會(huì)阻塞數(shù)據(jù)庫寫操作，不管時(shí)間多短。為了不阻塞寫操作，我們可以分配一個(gè)新的 memtable 來寫，然后在后臺(tái)慢慢轉(zhuǎn)寫舊的 memtable (如圖陰影部分)。

那么，數(shù)據(jù)庫讀操作又該如何處理呢?您可能已經(jīng)想到答案了：我們需要先查詢 memtable ，然后再查詢 SSTable 。再啰嗦一句， SSTable 必須從數(shù)據(jù)最新的那個(gè)開始，逐個(gè)查詢。

那隨著時(shí)間推移，SSTable 中應(yīng)該會(huì)有不少被覆寫或者刪除的無效記錄。這時(shí)，數(shù)據(jù)庫可以在后臺(tái)對(duì) SSTable 進(jìn)行合并，以去除無效記錄，節(jié)約磁盤空間。于此同時(shí)，合并操作也可以減低 SSTable 個(gè)數(shù)，提高查詢效率。

操作日志

這個(gè)方案看起來不錯(cuò)，但您可能也發(fā)現(xiàn)一個(gè)問題：如果數(shù)據(jù)庫掛掉了，保存在 memtable 中的寫操作不就丟了嗎?

為了解決這個(gè)問題，我們可以在磁盤中維護(hù)一個(gè)日志文件，來記錄寫操作。每個(gè)寫操作除了保存到 memtable 外，還要追加寫到日志文件。這樣就算 memtable 因故障丟失了，也可以通過重放日志文件來重建。

注意到，日志文件中的數(shù)據(jù)是按寫入時(shí)間排序的，而不是按照數(shù)據(jù)鍵排序的。不過不要緊，因?yàn)槿罩疚募皇菫榱斯收蠒r(shí)可以重建 memtable ，一旦 memtable 持久化到 SSTable，對(duì)應(yīng)的日志文件就可以安全釋放了。

查詢優(yōu)化

LSM樹查詢一個(gè)不存在的鍵可能很慢，因?yàn)閿?shù)據(jù)庫要檢查所有 SSTable ，才能確定待查鍵不存在。如果 SSTable 文件數(shù)量很多，查詢效率肯定要大打折扣。

為了優(yōu)化這類查詢，數(shù)據(jù)庫通常會(huì)額外維護(hù)一個(gè) 布隆過濾器 ( bloom filter )。這樣一來，查詢時(shí)先檢查布隆過濾器，如果確定待查鍵不存在，就不必檢查 memtable 和 SSTable 了。

布隆過濾器可以大致維護(hù)一個(gè)集合，而且非常節(jié)約內(nèi)存。您可以將它當(dāng)作一個(gè)特殊實(shí)現(xiàn)的集合，可以查詢一個(gè)元素是否在集合內(nèi)。大致的意思是布隆過濾器可能會(huì)誤判——查詢存在而實(shí)際上不存在。但如果查詢不存在，就一定是不存在的，不會(huì)誤判。