天天看點

分布式專題——詳解Google levelDB底層原理

本文始發于個人公衆号:TechFlow,原創不易,求個關注

今天是分布式專題的第10篇文章,我們繼續來聊聊LSMT這個資料結構。

LSMT是一個在分布式系統當中應用非常廣泛,并且原理直覺簡單的資料結構。在上一篇文章當中我們進行了詳細的讨論,有所遺忘或者是新關注的同學可以點選下方的連結回顧一下上一講的内容。

分布式——吞吐量巨強、Hbase的承載者 LSMT

leveldb簡介

上一篇的内容我們介紹的算是最基礎版本的LSMT,在這一篇當中,我們來具體看下levelDB這個經典的KV資料庫引擎當中LSMT的使用以及優化。

leveldb,既然是叫做db,顯然和資料庫有關。和一般的關系型資料庫不同,它内部的資料全部以KV也就是key-value形式存儲,并且不支援結構化的SQL進行資料查詢,隻支援api調用。也就是說它就是一個典型的我們常說的noSQL資料引擎庫。它最早由google開發并且開源,Facebook在此基礎上進行優化,推出了更普及的RocksDB,後來包括TiDB等多種分布式noSQL資料庫的底層都是基于leveldb。

如果上面這些名詞你都沒聽說過,也沒有關系,對于這些庫而言,上手去用容易,但是了解原理難。搞懂了原理再實際上手去用,除了更加簡單之外,也會有更多的體會。

leveldb架構

這是一張leveldb的架構圖,比之前介紹的裸的LSMT的架構圖要複雜一些,但是核心本質是一樣的,我們一個一個來看。

首先上層是MemTable,和Immutable MemTable。MemTable我們都知道,其實本質上就是一個存放在記憶體當中的資料結構。可以是SkipList也可以是紅黑樹或者是其他的平衡樹(在leveldb當中,使用的是SkipList),我們隻需要确定,它是存儲在記憶體當中的。Immutable MemTable其實也是MemTable,前面的Immutable是不可修改的意思。之前我們說過,當MemTable當中的内容超過某個門檻值的時候,我們需要将其中的内容寫成一個SSTable的檔案。這個ImmuTable MemTable就是在這個時候用的。

當一個MemTable在開始執行持久化之前,會先轉化成ImmuTable MemTable,可以認為是加上了不可修改的限制。另外,會再建立一個新的MemTable,用于維持服務。之後再将ImmuTable MemTable寫入進SSTable檔案。

打個比方,MemTable就好像是收銀台裡的收銀櫃,當我們一個門店開張,顯然需要有收銀櫃存放顧客付的錢。當收銀櫃快滿的時候,我們需要将裡面的錢存入銀行。但是裡面的錢不少,并且還有顧客在源源不斷地付錢,我們讓它停一會會帶來損失。是以我們把整個收銀櫃一起拿走,為了安全,我們在外面加上一把鎖,鎖起來連同收銀櫃送到銀行。但是收銀台不能沒有收銀櫃啊,是以我們還需要拿出一個新的收銀櫃給收銀台去收錢。

在這個例子當中,一開始負責收錢的收銀櫃就是MemTable,加了鎖之後變成了Immutable MemTable。也許不是非常恰當,但是對照一下,應該很容易了解。

其次是.log檔案,這個很好了解,之前的LSMT當中也有這個檔案,用來存儲發生變更的資料。類似于資料庫當中的binlog,用來在系統發生故障重新開機時恢複資料。

接着我們來看SSTable,在原始的LSMT當中SSTable是順序存儲的,是以我們在查詢資料的時候才是依次查詢,當發現第一個SSTable當中沒有我們要查詢的内容的時候,就往下查詢下一個檔案。而在leveldb當中,SSTable是按照層級存儲的,第一層是level0,第二層是level1,以此類推,層級逐漸增高。這也是leveldb得名的原因。

我們之前介紹過SSTable的本質是一個key-value的序清單,并且其中的key是有序的。既然SSTable當中的key是有序的,那麼顯然就有最大值和最小值。我們把最大值和最小值記錄下來就可以在查詢的時候快速判斷,我們要查詢的key它可能在哪些SSTable當中,進而節省時間,加快效率。

這個記錄SSTable檔案當中的最小key和最大key的檔案就是manifest,除了最小最大key之外,還會記錄SSTable屬于哪個level,檔案名稱等資訊。我們可以對照下下圖當做一個參考:

最後是Current檔案,從名字上來看,Current像是一個指針的名字。的确,Current是一個指針。因為在實際運作當中manifest檔案不止一個,因為伴随着我們的壓縮等操作,都會産生新的manifest。我們需要一個指針記錄下來目前最新的manifest檔案是哪一個,友善查找。而且manifest當中的資料量并不小,是以我們不能全部都存放在記憶體當中,放在檔案裡用一個指針引用是最佳選擇。

leveldb的增删改查

leveldb的寫入

leveldb當中的寫、删、改操作和裸的LSMT基本一樣,分成以下幾個步驟。

首先,會将變更的資料寫入.log檔案當中。這是為了持久化資料,放置系統當機導緻資料丢失。

當寫入.log檔案成功之後,寫入MemTable。由于leveldb中的MemTable采用SkipList實作,是以寫入速度也會很快,大約是

分布式專題——詳解Google levelDB底層原理

的複雜度。如果MemTable容量達到或者超過門檻值,會觸發進一步寫入SSTable的操作。在這個寫入當中,首先會将MemTable轉化成Immutable MemTable,之後會建立一個空的MemTable應對後續的請求,當dump指令下達之後,會将Immutable MemTable寫入成SSTable檔案進行存儲。

以上的流程和LSMT大同小異,隻有一些細微的差別。另外嚴格說起來leveldb不支援修改操作,可以轉化成插入一條新資料,或者是先删除舊資料再插入,這兩者本質上是一樣的,會在後續資料壓縮的過程當中進行合并。

leveldb的讀取

leveldb的讀操作和LSMT稍稍有所差別,我們結合下面這張圖來詳細看下。

首先,當我們執行查找指令的時候,我們首先會在MemTable和Immutable MemTable當中進行查找。這一點很容易了解,因為MemTable和Immutable MemTable都是完善的資料結構,支援快速查找。有些同學可能會覺得奇怪,Immutable MemTable不是寫入檔案當中了麼,怎麼還能進行查找。這是因為當MemTable轉化成Immutable MemTable之後到寫入磁盤會有一個等待時間,并不是立即執行的。在執行寫入之前,Immutable MemTable當中可能都會有資料殘留,需要進行查找是必要的。

如果在MemTable和Immutable MemTable當中都沒有找到,那麼我們則會讀取磁盤中的資料進行查找。

和裸的LSMT按照順序一個一個查找SSTable不同,leveldb會首先讀取manifest檔案,根據manifest檔案當中記錄的key的範圍來找到可能出現的SSTable檔案。

對于同一個key來說,可能同時出現在不同level的SSTable當中,但是由于leveldb在寫入SSTable的時候遵循越晚寫入的資料越新的原則。也就是說level序号越小的資料越新,是以如果找到了多個值,那麼優先傳回上層的結果。

整個leveldb的讀寫可以看得出來是在原本LSMT的基本上加入的優化,并沒有太多難以了解的東西,還是比較簡明直接的。在一些場景當中,我們的記憶體資源比較充足,并且對于查找有一定的要求,我們可以将manifest緩存在記憶體當中,這樣可以減少讀取manifest檔案的時間,起到加速的作用。但是同時,也帶來了維護緩存的成本,這一點會在之後介紹緩存的文章當中詳細介紹。

leveldb的壓縮政策

最後,我們來看下leveldb的壓縮政策,這也是leveldb的精髓。

Google有一篇Bigtable: A Distributed Storage System for Structured Data的論文, 這一篇論文可以認為是leveldb的理論基礎。在BigTable的論文當中,提到了三種壓縮政策。

第一種政策叫做minor Compaction,這一種政策非常簡單,就是簡單地把MemTable中的資料導入到SSTable。

第二種政策叫做major Compaction,這種政策中會合并不同層級的SSTable檔案,也就是說major Compaction會減少level的數量。

最後一種政策叫做full Compaction,這一種政策會将所有的SSTable檔案合并。

在leveldb當中,實作了前面兩種壓縮政策,minor Compaction和major Compaction,下面我們來詳細研究一下。

minor Compaction

minor Compaction很簡單,剛才說過了其實就是将MemTable也就是SkipList當中的資料寫入到磁盤生成SSTable檔案。

我們之前的文章當中介紹過SkipList,它的本質是一個有序的連結清單。而我們想要生成的SSTable也剛好是有序的。是以我們隻需要依次周遊寫入即可。對SkipList感興趣或者是想要複習的同學可以點選下方的連結回顧一下:

分布式——SkipList跳躍連結清單【含代碼】

根據越晚生成的SSTable level序号越小,層級越高的原則,我們最新生成的SSTable是level0。之後我們要記錄這個新生成的SSTable當中的索引,完成寫入操作。需要注意的是,在這個過程當中,我們不會對資料進行删除操作。原因也很簡單,因為我們并不知道要删除的資料究竟在哪個level下的SSTable裡,找到并删除會帶來大量的耗時。是以我們依舊會原封不動地記錄下來,等待後續的合并再處理這些删除。

另外,在檔案的末尾部分會将key值的資訊以索引的形式存儲。由于我們讀取檔案的時候是倒序讀取的,是以優先會讀取到這些索引資訊。我們就可以根據讀取到的索引資訊快速鎖定SSTable當中的資料而不用讀取整個檔案了。

major Compaction

接下來我們來看major Compaction。這也是leveldb分層機制的核心,不然的話插入SSTable也隻會都是level0,層次結構就無從談起了。

在詳細介紹之前,我們需要先弄清楚一個洞見。對于leveldb當中其他level的SSTable檔案而言,都是通過major Compaction生成的。我們可以保證同一層的SSTable沒有重疊的元素,但是level0不同,level0當中的SSTable是通過minor Compaction生成的,是以是可能會有重疊的。

leveldb當中觸發major Compaction的情況并不止一種,除了最常提到的Size Compaction之外還有兩種,一種是manual Compaction,還有一種是seek Compaction。下面來簡單介紹一下。

manual Compaction很好了解,就是人工手動觸發,通過接口調用人為地去觸發它執行Compaction。size Compaction相當于平衡操作,當系統發現某一層的SSTable數量超過門檻值的時候會觸發。最後一種是seek Compaction,這一種比較機智,leveldb會記錄每一層level中每一個SSTable檔案的miss rate。就是當發現某一個檔案當中的資料總是miss,而在下一層的檔案當中查找到了值,這個時候leveldb就會認為這個檔案不配待在這一層,将它和下一層的資料進行合并,以減少IO消耗。

當然以上三種觸發Compaction的情況當中,最常出現的還是size Compaction,就是當leveldb發現某一層的SSTable資料或者是大小超過門檻值的時候,會執行Compaction操作。

在major Compaction當中,假設leveldb選擇的是level i的檔案進行合并。這個時候需要分情況讨論,如果i=0,也就是說我們要合并的是level 0的資料。由于剛才提到的,level 0當中不同檔案的資料是存在重疊的,這個時候需要将所有key值有重疊的檔案都納入到待合并的集合當中來。在挑選待合并集合的時候,leveldb會記錄上一次觸發壓縮時的最大key值,這一次會選擇大于這個key值的檔案開始執行壓縮。

也就是說leveldb設計了一種輪流機制,保證level當中的每一個檔案都有被合并的機會。

當我們level i的檔案選擇結束之後,接下來就要從level i+1當中選擇檔案進行合并了。選擇的标準也很簡單,我們會将所有和待合并集合中key值有重疊的檔案全部挑選出來進行合并。

合并的過程本質上是一個多路歸并的過程,如下圖所示:

由于所有檔案當中的key值都是有序的,我們都從它們的頭部開始。對于每一個key我們都會進行判斷,是應該保留還是丢棄。判斷的邏輯也很簡單,對于某一個key而言,如果這個key在更低級的level中出現過,那麼說明有更新的value存在,我們需要進行抛棄。

當Compaction完成之後,所有參與歸并的檔案都已經沒有用處了,可以進行删除。

從本質上來說這個歸并過程和裸的LSMT原理是一樣的,隻是增加了層次結構而已。

到這裡還沒有結束,還記得我們有一個記錄所有SSTable索引的manifest檔案嗎?不論哪一種Compaction的發生,都會改變整個level的結構,是以我們需要在每一次Compaction之後,都會生成一個新的manifest檔案,然後将此次Compaction帶來的檔案變動記錄進去。最後,将Current指向新生成的manifest。

這樣,我們整個過程就串起來了。

總結

我們回顧一下整個流程,會發現雖然增删改查以及Compaction的操作增加了許多細節,但是底層的架構其實還是LSMT那一套。因為核心的原理是一樣的,是以和純LSMT一樣,leveldb當中的SSTable同樣可以使用布隆過濾器來進行優化,除此之外,還有cache的靈活使用,可以進一步提升查詢的效率。

另外,需要注意的是,leveldb嚴格說起來隻是資料庫引擎,并不是真正的資料庫系統。基于leveldb我們可以開發出比較完善的資料庫系統,但它本身隻提供底層最核心增删改查服務的基礎。除了基礎功能之外,一個成熟的資料庫系統還需要開發大量的細節以及做大量的優化。目前為止基于leveldb開發的資料庫引擎很多,但完整的資料庫系統非常少,畢竟這需要長久時間開發和積累。

如果我們簡單把分布式系統分成分布式計算系統和分布式存儲系統的話,會發現分布式存儲系統的精華占了大半。而分布式存儲系統又可以簡單認為是底層的資料結構加上上層解決分布式帶來的一緻性等問題的共識協定。而分布式存儲系統當中常用的底層資料結構無非也就那麼幾種,是以說我們對于這些資料結構的了解和學習是以後深入了解分布式系統的基礎。而一個合格且優秀的系統架構師,解決業務場景當中的分布式問題是常态,而解決問題的能力的核心,其實就在于對這些底層基礎知識的了解和運用。

今天的文章就是這些,如果覺得有所收獲,請順手點個關注或者轉發吧,你們的舉手之勞對我來說很重要。