SLM-DB:B+樹索引和LSM架構結合的嘗試

語言: CN / TW / HK

記得本科大三(20年初)通過Leveldb第一次接觸到LSM的時候,就在思考是否可以將LSM結構與B+樹索引相結合,畢竟一個是write-friendly,一個是read-friendly,但當時光想著寫Leveldb的大作業,就把這個事情拋在腦後。最近讀到了這篇文章 SLM-DB: Single-Level Key-Value Store with Persistent Memor y,算是對我當時想法的一種實現。

這篇文章僅僅作為讀書筆記使用,有興趣的同學最好還是去親自看看論文,裡面的一些idea確實非常精彩。

概要:

本文主要提出了一種新kv儲存模型:Single-Level Merge DB(SLM-DB),它使用了最近較為新穎的PM(persistent memory)技術,並且同時汲取了B+樹索引以及LSM-tree結構的優點,使得其有非常好的讀寫效能,並且在讀寫放大上也有良好的表現。SLM-DB基於LevelDB(1.20)開發,實驗結果表明,SLM-DB相比LevelDB有著1.07-1.96倍的讀效能以及1.56-2.22倍的寫效能。

前情提要:

  1. B+樹索引

B+樹索引是關係型資料庫中常見的索引選擇,利用它可以很快的定位一個tuple所在的table。但是它也有一個問題,就是維護起來的成本偏高,在使用過過程中通常伴隨著多次少量的random write以及為了維護樹平衡性而進行的寫放大。

所以,B+樹索引對於read有著非常良好的效能,但是在維護上(寫上)的開銷其實並不算小。

2. LSM樹

LSM樹結構被廣泛地在鍵值對儲存引擎中使用,比如bigtable,RocksDB,LevelDB等等。它有一個對於磁碟(或者說外存)來說非常好的特性:它的寫永遠是順序的。所以它對於 write intensive的工作就非常地友好。 但是有得必有失,這個世界就是這麼地平衡,這位老兄在讀上的表現確實有點拉跨,因為它的讀也是順序的,這就導致它在讀取資料時必須要一個檔案一個檔案地找。同時它的讀寫放大也非常嚴重(寫放大最壞有50,讀放大最壞可以來到340左右)。

SLM-DB的設計與實現

  1. 整體架構

如上圖所示,SLM-DB使用PM去儲存LevelDB本身的memtable,Immutable部分,這樣做的好處是可以省去WAL(write ahead log)的開銷,同時對於系統崩潰有更好的容錯能力。而sstable和manifest檔案則和LevelDB設計的一樣儲存在磁碟中,但值得注意的是,正如它的名字Single-Level-Memory DB一樣,這裡的 Level只有一層 了。

另外視力正常的同學肯定還注意到在PM中還儲存了一個叫compaction log和global B+Tree索引的東西。其中compaction log的主要功能是在用作compaction過程的容錯,至於只有一層檔案如何進行compaction,這個我們先按下不表;而B+樹索引就很簡單,他儲存的是key值以及對於的指標(kv對所在的sstable的table id以及相應的offset),用來快速定位一個kv對。

介紹完了總體架構之後,我會從B+樹index和LSM架構的結合使用,GC問題以及合併問題入手講解SLM-DB的執行過程。

2. B+樹與LSM

回憶LevelDB的Put()過程,首先kv對並不會直接被寫入disk上的sstable中,而是被加入被稱為memtable的buffer pool中。在SLM-DB中也是如此,只有當memtable滿足了落盤條件時(比如說大小超過了規定的size),它才會變成immutable table,然後其中的kv對才會被落盤。

只有當檔案被刷盤後,key以及指標才會被加入到B+樹索引中。

SLM-DB具體是這麼做的,它啟動了兩個執行緒,一個負責資料落盤的執行緒A,另一個負責B+樹索引維護的執行緒B。

執行緒A會建立一個檔案,然後把imm中的kv不斷地刷盤,在刷盤結束之後,它會把這個檔案的所有kv資訊寫入到一個queue中,隨後執行緒B就不斷從這個queue中讀取資訊,然後用這些資訊去維護B+樹索引。注意我這裡用的是維護而不是插入,因為這個kv對可能是新的kv,也可能是對舊kv對的更新(這是就要在B+樹索引中修改此key對應的指標),也可能是刪除操作(這時需要在B+樹中刪除相應葉子節點)。當queue為空時,說明整個flush過程結束,此時就可以將sstable的元資訊append到MANIFEST檔案中,隨後便可以刪除Immutable table。

3. Selective Compaction

現在問題來了,單層的sstable 檔案怎麼做compaction?

首先我們說一下我們為什麼要做compaction。LSM結構是append only的,也就是說對於更新或者是刪除操作來說,原先的資料並不會被刪除,我們只是往其中加入新的資料並保證新的資料在舊的資料前面,這樣新的資料會比原先資料更早地被搜尋到,所以每次搜尋都可以保證資料都是最新的(這也是為什麼它的寫非常塊)。但是這樣做時間一長,我們的sstable 檔案中必然充滿了大量的garbage(無用的資訊),這對於提高磁碟空間利用率非常不利,我們就需要做Garbage collection(GC),這個過程在LevelDB中是由Compaction操作來完成的。其次就是我們對於range query效能的需求,如果資料的分佈過於隨機,那麼我們在進行range query的時候的效能將非常接近於random read,這是不可以忍受的,所以我們需要適當地對資料進行compaction,保持其一定地區域性有序性。

但在SLM中,只有一層,要怎麼compaction呢?這裡文章提出了一種成為selective compaction的策略。

具體的做法是在SLM中維護一個叫做CCL(compaction candidate list)的東西,裡面包含了可能會進行compaction的sstable檔案。當CCL裡面的檔案數太多,或者說對於某個sstable有了大量的訪問,或是sstable 檔案叢集發生改變時(比如發生了flush),後臺compaction執行緒就會啟動,開始進行compaction操作。

這個後臺compaction執行緒會選擇CCL裡面的一部分sstable(並不是全部,但是具體多少文章也沒有說),對於裡面的每一個sstable s,計算s和其他CCL中其他sstable 檔案t的 overlapping ratio。計算公式如下

其中s的key range為[S1........Sp], t的key range為[T1......Tq].

然後這些s 會與其重合率最高的 t相合並,生成一個新的檔案。整個合併過程也有上文中提到的兩個執行緒AB來完成,執行緒A負責新檔案的建立以及merge sort,完成之後把新檔案地kv加入到一個queue中,隨後去進行其他檔案的compaction。而執行緒B則會不斷地從這個queue中讀取kv對,並對B+樹進行相應的修改。

3. 1 CCL的入選條件

好了,有了compaction的操作過程之後,那麼問題就是什麼樣的檔案有資格被選入CCL?這是我認為整篇文章最為精彩的部分。文章中給出了三種入選的表中

  • 有效key的比例

這一點非常容易理解,如果說一個sstable中有效的key的比例過低,那麼說明裡面的garbage過多,可以用compaction去free掉那些被佔用的空間。SLM通過維護一個sstable的live key ratio值來做到這一點。

  • 葉子節點掃描

這東西有一點抽象,但我認為非常精彩。具體來說就是這樣的:

在一個後臺compaction結束之後,都會喚醒一個scan操作,去掃描一定數量(具體多少文章沒說)的B+樹索引的葉子節點。在掃描過程中,我們記錄出現的不同的sstable檔案的數量,如果這個檔案數量超過了某個值,我們就把這些檔案加入到CCL中去。

這個設計非常巧妙:連續掃描B+樹索引的葉子節點,說明這些Key應該是緊密相連的,如果掃描結束後出現的unique sstable檔案數量較少,則在直覺上(文章沒有給出數學證明)可以說明這些資料的連續性尚可,但是如果unique sstable的檔案數量很大,則必然說明這些連續的key的連續性稀爛,則可以進行compaction來維護他們的連續性。

  • range query的連續性

這個操作依然抽象,但也依然精彩,其實它和上面的葉子節點掃描有異曲同工之妙。具體操作如下:

在進行range query時,我們把range再切分成一個個sub range,每個sub range都含有相同數量的key。在進行query時,我們追蹤每一個subquery,並儲存每個sub query最終查詢了多少個sstable,並取其中最大的那個,記為M。如果這個M大於一個給定的threshold,我們就把這些sstable加入到CCL中去。這對於提升SLM的range query非常有效。

SLM-DB的具體kv儲存操作

  1. Put

put一個kv時,先寫入記憶體中的memtable,此時B+樹索引不需要有任何改動。隨後再memtable滿時進行刷盤,並將其中的kv對都在B+樹索引中進行維護。

2. Get

首先在memtable中尋找這個key-value,如果找到,直接返回,如果沒有找到,則利用B+樹索引去sstable中尋找kv對。

3. range query

range query會遇到一個問題:range中的key可能部分存在在memtable,部分存在於sstable中。SLM-DB是這麼做的:

使用兩個iterator 併發的去遍歷b+樹索引以及memtable,最後把得到的結果進行一個merge作為最終結果返回個使用者。