歡迎光臨
每天分享高質量文章

LSM-Tree 與 RocksDB

(點擊上方公眾號,可快速關註)


來源:MRRiddler ,

blog.mrriddler.com/2017/05/30/LSM-Tree%E4%B8%8ERocksDB/

冥冥之中,接觸到了不同於關係資料庫的NoSQL Key-Value儲存引擎RocksDB,懵懵懂懂、充滿好奇,google一點,滿眼皆是LSM-Tree,頭暈眼花、若即若離,便有了這篇文章,一起與大家分享這趟探險之旅。

LSM-Tree(Log-Structured-Merge-Tree)

LSM從命名上看,容易望文生義成一個具體的資料結構,一個tree。但LSM並不是一個具體的資料結構,也不是一個tree。LSM是一個資料結構的概念,是一個資料結構的設計思想。實際上,要是給LSM的命名斷句,Log和Structured這兩個詞是合併在一起的,LSM-Tree應該斷句成Log-Structured、Merge、Tree三個詞彙,這三個詞彙分別對應以下三點LSM的關鍵性質:

  • 將資料形成Log-Structured:在將資料寫入LSM記憶體結構之前,先記錄log。這樣LSM就可以將有易失性的記憶體看做永久性儲存器。並且信任記憶體上的資料,等到記憶體容量達到threshold再集體寫入磁盤。將資料形成Log-Structured,也是將整體儲存結構轉換成了“記憶體(in-memory)”儲存結構。

  • 將所有磁盤上資料不組織成一個整體索引結構,而組織成有序的檔案集:因為磁盤隨機讀寫比順序讀寫慢3個數量級,LSM儘量將磁盤讀寫轉換成順序讀寫。將磁盤上的資料組織成B樹這樣的一個整體索引結構,雖然查找很高效,但是面對隨機讀寫,由於大量尋道導致其性能不佳。而LSM用了一種很有趣的方法,將所有資料不組織成一個整體索引結構,而組織成有序的檔案集。每次LSM面對磁盤寫,將資料寫入一個或幾個新生成的檔案,順序寫入且不能修改其他檔案,這樣就將隨機讀寫轉換成了順序讀寫。LSM將一次性集體寫入的檔案作為一個level,磁盤上劃分多level,level與level之間互相隔離。這就形成了,以寫入資料時間線形成的邏輯上、而非物理上的層級結構,這也就是為什麼LSM被命名為”tree“,但不是“tree”。

  • 將資料按key排序,在合併不同file、level上的資料時類似merge-join:如果一直保持生成新的檔案,不僅寫入會造成冗餘空間,而且也會大量降低讀的性能。所以要高效的、周期性合併不同file、level。而如果資料是亂序的,根本做不到高效合併。所以LSM要將資料按key排序,在合併不同file、level上的資料時類似merge-join。

很明顯,LSM犧牲了一部分讀的性能和增加了合併的開銷,換取了高效的寫性能。那LSM為什麼要這麼做?實際上,這就關係到對於磁盤寫已經沒有什麼優化手段了,而對於磁盤讀,不論硬體還是軟體上都有優化的空間。通過多種優化後,讀性能雖然仍是下降,但可以控制在可接受範圍內。實際上,用於磁盤上的資料結構不同於用於記憶體上的資料結構,用於記憶體上的資料結構性能的瓶頸就在搜索複雜度,而用於磁盤上的資料結構性能的瓶頸在磁盤IO,甚至是磁盤IO的樣式。

LSM近年來已被廣泛使用起來,還有將B家族樹和LSM結合起來使用的,像HBase、SQLite4、MongoDB、Cassandra、LevelDB,還有接下來的主角RocksDB,這些當家資料儲存花旦,都或多或少支持、使用起LSM了。

RocksDB

RocksDB是Facebook在LevelDB基礎上用C++寫的Key-Value儲存引擎。其Key和Value都是二進制流。並對閃存(flash)有更友好的優化。先來聊一聊RocksDB的整體結構,然後再聊一聊RocksDB中的一些有意思的抽象,最後聊一聊RocksDB記憶體上、磁盤上的具體結構。在RocksDB中,將記憶體結構中的資料寫入磁盤結構叫做flush,而不同file、level之間merge叫做compaction。

Architecture

RocksDB如上文所說是基於LSM做儲存。RocksDB在記憶體中的結構叫做memtable,用於形成Log-Structured的file叫做logfile,磁盤上的file結構叫做sstfile,用於記錄對file更改的log叫做manifest。

Column-Family

為儲存的資料邏輯分族,將不同family互相隔離,分開配置、儲存。column family共享logfile,而不共享memtable和sstfile,這使得column family有以下兩點特點:

  • 多個column family仍然能保持事務的原子性。

  • 單獨增加、修改、刪除一個column family內的資料性能提升。

Filter

RocksDB有一些奇思妙想的filter,這些filter根據特定條件生成,通過資料的key就可以判斷資料是否確定或可能被特定條件排除掉。有些filter可以用來對讀優化,有些也可以用來管理資料的生命周期等。

Bloom-Filter

bloom filter就是一個能提高讀性能的filter。通過演算法可以生成一個key set對應的bloom filter。這個bloom filter可以判斷出任意key可能存在或者肯定不存在key set中。每個sstfile在生成的時候,都會創建一個或多個對應的bloom filter,當在讀資料的時候,可以快速判斷出資料是否可能在sstfile中。在做range scan和prefix查找的時候,bloom filter也能幫上忙。

Time-To-Live(TTL)

RocksDB還支持為存入的資料設置上最長生命周期。RocksDB會為有TTL的資料創建一個filter。這種filter叫做compaction filter,當進行compaction的時候,生命周期結束的資料將會被排除。很明顯,這個TTL不是絕對時間,RocksDB會在絕對時間過後的一段時間內刪除資料。

Memtable

RocksDB在記憶體上的結構由memtable組成,具體預設使用SkipList,當然,外部也可以指定其他資料結構。不過,SkipList做為用多個線性結構模仿出層級結構的“樹狀“資料結構,能提供常數級順序訪問和對數級隨機訪問,並且在併發環境相對於其他樹狀資料結構,減輕了鎖開銷,運用在這裡再合適不過了。

Flush

為了減小鎖開銷,將寫入memtable和flush分離,RocksDB會使用多個memtable,並且把flush這件事抽象為task-pipeline,也就是job、job queue、worker抽象。將要flush的memtable先轉換成immutable memtable,代表其不可寫了,並將immutable memtable加入flush pipeline,等待後臺執行緒去flush。而同時新的memtable生成取代immutable memtable等待資料寫入。在將immutable memtable flush的過程中,值得一提的是會做inline-compaction,這是將immutbale memtable提前進行資料合併的優化,如果在這個memtable創建到flush的周期中,資料被加入然後刪除,在這一步就可以compact掉,這對短生命周期的資料有很大的寫優化。

SSTFile(SSTTable)

RocksDB在磁盤上的file結構sstfile由block作為基本單位組成,一個sstfile結構如下:

[data block 1]

[data block 2]

[data block N]

[meta block 1: filter block]                 

[meta block 2: stats block]                   

[meta block 3: compression dictionary block]  

[meta block K: future extended block] 

[metaindex block]

[index block]

[Footer]                              

其中data block就是資料物體block,meta block為元資料block。metaindex block和index block分別是對meta block和data block的索引block。metaindex block和index block都以blockhandle結構作為指向所索引block的指標。blockhandle包含所索引block的offset和size。metaindex block將所索引的meta block的名字作為key。而index block將所索引的data block前一block的最大key值與所索引data block的最小key值的中間任意值作為key。

filter block記錄的就是針對此sstfile生效的一系列filter。stats block也就是properties block,它以key-value形式記錄了此sstfile的一些屬性。sstfile組成的block有可能被壓縮(compression),不同level也可能使用不同的compression方式。compression dictionary block記錄了適用於compression此sstfile block的庫。footer添加了一些位元組填充,和記錄了指向metaindex block、index block的blockhandle結構指標。這說明sstfile如果要遍歷block,會逆序遍歷,從footer開始。

Compaction

RocksDB會在後臺多執行緒compact。RocksDB有兩種compact style:

  • Universal Style Compaction:這種style去compact就如上文LSM所聊的,將磁盤上資料完全按照寫入時間線去組織,只將相鄰時間段內寫入磁盤上的資料compact,很像在合併互不重疊(overlapping)的時間段。這種style可以compact出新的file或者level。很明顯,不同時間段內的資料會有重疊的key,會有冗餘空間。

  • Level Style Compaction:這種style去compact不會將磁盤上資料完全按照寫入時間線去組織。而為了防止同一level多個file中相同key資料的冗餘,這種style要保證同一level不存在有相同key的資料。若將Ln level中的file1 要compact到Ln+1level,要將Ln+1level中所有包含重疊file1資料key的檔案一起compact,最後將這些file compact成Ln+1level中的一個新file。這種style還會造成一種效果,就是同一level的file按key值排序。雖然Level Style Compaction減少了冗餘空間,但是,對於讀資料來說,Universal Style Compaction更加遵守區域性性,所以Level Style Compaction讀性能更差一點。

也就說,Universal Style Compaction重讀輕空間,Level Style Compaction重空間輕讀。RocksDB將後者作為default style,關於這兩種style如何選擇(pick)level、file去compact,這裡就不整體敘述了,基本是file、level的數量或大小達到一個ratio的threshold就會triger compact,關於Universal Style的選擇在這裡,關於Level Style的選擇在這裡。挑個有趣的聊下,Level Style如何pick file去compact?RocksDB還不能提供一個universal策略去pick,不過以下幾個option可以選擇:

  • 優先選擇key分佈範圍集中的file去compact:file中資料key如果分佈集中,就會有更少的重疊file在下一level,就會有更少的compact開銷。用kOldestSmallestSeqFirst設置優先compactkey分佈範圍集中的file。

  • 優先選擇冷資料file去compact:經常修改的熱資料如果經常compact,只會浪費開銷。設想下,剛剛插入的一組資料,馬上又刪除,如果插入後就進行compact,本應該刪除的資料又占了兩倍的冗餘空間。用kOldestLargestSeqFirst設置優先compact冷資料file。

  • 優先選擇被刪除資料多的file去compact:被刪除的資料如果早被compact的話,可以減少冗餘空間,用kByCompensatedSize設置優先compact被刪除資料多的file。

SSTFile-Indexing

如果RocksDB使用的是Level Style Compaction,那麼還可以在查找資料時做更多優化。Level Style Compaction保證同一level不存在有相同key的資料,且file按key值排序。首先,對於有序結構搜索,可以使用二分查找。其次,如果在某一level中都查找不到key,那麼在下一level中查找的時候,可以用查找到的最後一個file的key範圍排除下一level的很多file,比如如下結構:

                                         file 1                                file 2

                                      +———-+                          +———-+

level 1:                              | 100, 200 |                          | 300, 400 |

                                      +———-+                          +———-+

           file 1     file 2      file 3      file 4       file 5       file 6       file 7      

         +——–+ +——–+ +———+ +———-+ +———-+ +———-+ +———-+

level 2: | 40, 50 | | 60, 70 | | 95, 110 | | 150, 160 | | 210, 230 | | 290, 300 | | 310, 320 | 

         +——–+ +——–+ +———+ +———-+ +———-+ +———-+ +———-+

如果要查找80,在level 1中file1沒有查找到,那麼在level2中可以排除file3以後的file。這種排除和level結構有點像區間樹。基於此思想,在level compact的時候,可以為file添加一系列指向下一level file的指標,加快查找速度。

Manifest

因為檔案系統的操作不能保證原子性,所以RocksDB對file的更改也會記錄log,就記錄在manifest里。實際上,可以將manifest看做,記錄的是RocksDB的狀態。manifest記錄的內容就成了RocksDB按時間排序的一系列狀態,如果,將每個狀態看做RocksDB某個時間點的快照,manifest就是RocksDB的動圖GIF。

Cache

沒有cache的儲存引擎是不完整的,RocksDB有兩種cache,block cache和table cache。先來聊聊block cache。block cache快取的單位就是sstfile的data block,這種cache有兩種演算法,經典的LRU和clock,任由你選擇。除了data block,用於索引和提高讀性能的index block和filter block更是重點快取物件,但RocksDB並不會把這倆放在block cache中,RocksDB會單獨照顧好這倆,基本不用外部操心。而table cache快取的是sstfile的file descriptor,實際上,操作系統通過file descriptor用取用計數的方式來管理file結構體和其背後的資源。也就是說,table cache快取的是操作系統用來操作sstfile的file結構體和其背後資源,更多關於file descriptor結構,推薦這篇文章

http://cuckootan.me/2015/04/18/Linux/行程打開及讀寫檔案的過程/

Tips

以下是使用RocksDB的一些建議:

  • RocksDB執行緒模型是單句柄對多執行緒。

  • Get、Put、Delete等操作不需要操心資料同步問題,而Iterator和WriteBatch需要同步控制。

  • WriteBatch類似於事務,提供將一個或多個資料庫操作抽象為單位的能力,此單位是原子性的,但並不會互相隔離從而併發控制,也不會檢測出異常並恢復。

本篇聊了很多RocksDB的設計思想。然而畢竟大多數工程師都是面嚮應用,不會去搞個儲存引擎。這裡就總結幾條從LSM、RocksDB等儲存引擎中學到的有關讀寫IO的技巧,理解了大有裨益。

  • 相對於計算、記憶體讀取,磁盤IO慢不知多少數量級。

  • 相對於執行一次磁盤IO,磁盤IO的資料量多少不重要,也就說開始、結束一次磁盤IO更費時。儘量集中對磁盤進行IO。

  • 相對於磁盤隨機讀寫,磁盤順序讀寫快上3個數量級。

  • 讀寫分離,減少併發鎖的性能開銷。

取用

  • LSM

    https://www.zhihu.com/question/19887265

  • LSM論文

    http://www.cs.umb.edu/~poneil/lsmtree.pdf

  • RocksDB Blog

    http://rocksdb.org/blog/

  • RocksDB Wiki

    https://github.com/facebook/rocksdb/wiki

看完本文有收穫?請轉發分享給更多人

關註「ImportNew」,看技術乾貨

赞(0)

分享創造快樂