LevelDB的整體架構(gòu)是怎樣的

本文小編為大家詳細(xì)介紹“LevelDB的整體架構(gòu)是怎樣的”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“LevelDB的整體架構(gòu)是怎樣的”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識(shí)吧。

成都創(chuàng)新互聯(lián)一直通過網(wǎng)站建設(shè)和網(wǎng)站營(yíng)銷幫助企業(yè)獲得更多客戶資源。 以"深度挖掘，量身打造，注重實(shí)效"的一站式服務(wù)，以成都網(wǎng)站制作、網(wǎng)站建設(shè)、移動(dòng)互聯(lián)產(chǎn)品、網(wǎng)絡(luò)營(yíng)銷推廣服務(wù)為核心業(yè)務(wù)。十載網(wǎng)站制作的經(jīng)驗(yàn)，使用新網(wǎng)站建設(shè)技術(shù)，全新開發(fā)出的標(biāo)準(zhǔn)網(wǎng)站，不但價(jià)格便宜而且實(shí)用、靈活，特別適合中小公司網(wǎng)站制作。網(wǎng)站管理系統(tǒng)簡(jiǎn)單易用，維護(hù)方便，您可以完全操作網(wǎng)站資料，是中小公司快速網(wǎng)站建設(shè)的選擇。

一個(gè)比喻

LevelDB 有點(diǎn)類似于建筑，分為地基和地面兩部分，也就是磁盤和內(nèi)存，而地基又好比地殼結(jié)構(gòu)分了很多層級(jí)，不同層級(jí)的數(shù)據(jù)還會(huì)定期從上往下移動(dòng) —— 沉積作用。如果磁盤底層的冷數(shù)據(jù)被修改了，它又會(huì)再次進(jìn)入內(nèi)存，一段時(shí)間后又會(huì)被持久化刷回到磁盤文件的淺層，然后再慢慢往下移動(dòng)到底層，周而復(fù)始就好比地球水循環(huán)。

內(nèi)存結(jié)構(gòu)

LevelDB 的內(nèi)存中維護(hù)了 2 個(gè)跳躍列表，一個(gè)是只讀的 rtable，一個(gè)是可修改的 wtable。跳躍列表在我的另一本書《redis 深度歷險(xiǎn)》中有詳細(xì)講解，這里就不再細(xì)致重復(fù)說明。簡(jiǎn)單理解，跳躍列表就是一個(gè) Key 有序的 Set 集合，排序規(guī)則由全局的「比較器」決定，默認(rèn)是字典序。跳躍列表的查找和更新操作時(shí)間復(fù)雜度都是 Log(n)。

跳躍列表是由多個(gè)層次的鏈表構(gòu)成，其中最底層的鏈表存儲(chǔ)了所有的 Key，它們是有序的。普通鏈表并不支持快速二分查找，但是跳躍鏈表的特殊結(jié)構(gòu)可以讓最底層的鏈表以近似二分查找算法的效率定位到指定節(jié)點(diǎn)。簡(jiǎn)單理解就是跳躍列表同時(shí)具備了有序數(shù)組的快速定位能力和鏈表的高效增刪能力。但是它會(huì)付出一定的代價(jià)，在實(shí)現(xiàn)上有一定的復(fù)雜度。

如果跳躍列表只存 Key，那 Value 存哪里呢？答案是 Value 也存在跳躍列表的 Key 中。跳躍列表中存儲(chǔ)的 Key 比較特殊，它是一個(gè)復(fù)合結(jié)構(gòu)字符串，它同時(shí)包含了鍵值對(duì)的 Key 和 Value。

其中 sequence 為全局自增序列號(hào)，LevelDB 遇到一個(gè)修改操作，全局序列號(hào)自動(dòng)加一。LevelDB 中的 Key 存儲(chǔ)了多個(gè)版本的 Value。LevelDB 使用序列號(hào)來標(biāo)記鍵值對(duì)的版本，序列號(hào)越大，對(duì)應(yīng)的鍵值對(duì)越新。

type 為數(shù)據(jù)類型，標(biāo)記是 Put 還是 Delete 操作，只有兩個(gè)取值，0 表示 Delete，1 表示 Put。

internal_key = key + sequence + type
Key = internal_key_size + internal_key + value_size + value

如果是刪除操作，后面的 value_size 字段值 為 0，value 字段值是空的。我們要將 Delete 操作等價(jià)看成 Put 操作。同時(shí)為了節(jié)省存儲(chǔ)空間，internal_key_size 和 value_size 都要采用 varint 整數(shù)編碼

如果跳躍列表中同一個(gè) key 存在多個(gè)修改操作，也就是說有多個(gè)「復(fù)合 Key」，那么這幾個(gè)「復(fù)合 Key」 肯定會(huì)挨在一起按照 sequence 值排序的。當(dāng) Get 操作到來時(shí)，它會(huì)在跳躍列表中定位到 key 所在的位置，選擇這幾個(gè)同樣的 key 中 seq 最大的「復(fù)合 Key」，提取出其中的 value 值返回。

待 Put 和 Delete 操作日志寫到日志文件后，其鍵值對(duì)合并成「復(fù)合 Key」插入到 wtable 的指定位置中

待 wtable 的大小達(dá)到一個(gè)閾值，LevelDB 將它凝固成只讀的 rtable，同時(shí)生成一個(gè)新的 wtable 繼續(xù)接受寫操作。rtable 將會(huì)被異步線程刷到磁盤中。Get 操作會(huì)優(yōu)先查詢 wtable，如果找不到就去 rtable 中去找，rtable 如果還找不到，再去磁盤文件里去找。

因?yàn)?wtable 要支持多線程讀寫，所以訪問它是需要加鎖控制。而 rtable 是只讀的，它就不需要，但是它的存在時(shí)間很短，rtable 一旦生成，很快就會(huì)被異步線程序列化到磁盤上，然后就會(huì)被置空。但是異步線程序列化也需要耗費(fèi)一定的時(shí)間，如果 wtable 增長(zhǎng)過快，很快就被寫滿了，這時(shí)候 rtable 還沒有完成序列化，而wtable 急需變身怎么辦？這時(shí)寫線程就會(huì)阻塞等待異步線程序列化完成，這是 LevelDB 的卡頓點(diǎn)之一，也是未來 RocksDB 的優(yōu)化點(diǎn)。

圖中還有個(gè)日志文件，記錄了近期的寫操作日志。如果 LevelDB 遇到突發(fā)停機(jī)事故，沒有持久化的 wtable 和 rtable 數(shù)據(jù)就會(huì)丟失。這時(shí)就必須通過重放日志文件中的指令數(shù)據(jù)來恢復(fù)丟失的數(shù)據(jù)。注意到日志文件也是有兩份的，它和內(nèi)存的跳躍列表正好對(duì)應(yīng)起來。當(dāng) wtable 要變身時(shí)，日志文件也會(huì)跟著變身。待 rtable 落盤成功之后，只讀日志文件就可以被刪除了。

磁盤結(jié)構(gòu)

LevelDB 在磁盤上存儲(chǔ)了很多 sst 文件，sst 表示 Sorted String Table，文件里所有的 Key 都會(huì)有序的。每個(gè)文件都會(huì)對(duì)應(yīng)一個(gè)層級(jí)，每個(gè)層級(jí)都會(huì)有多個(gè)文件。底層的文件內(nèi)容來源于上一層，最終它們都會(huì)來源于 0 層文件，而 0 層的文件又來源于內(nèi)存里的 rtable 序列化。一個(gè) rtable 會(huì)被序列化為一個(gè)完整的 0 層文件。這就是我們前面所說的「下沉作用」

從內(nèi)存的 rtable 序列化成 0 層 sst 文件稱之為「Minor Compaction」，從 n 層 sst 文件下沉到 n+1 層 sst 文件稱之為「Major Compaction」。之所以這樣區(qū)分是因?yàn)?Minor 速度很快耗費(fèi)資源少，將 rtable 完整地序列化為一個(gè) sst 文件就完事了。而 Major 會(huì)涉及到多個(gè)文件之間的合并操作，耗費(fèi)資源多，速度慢。層級(jí)越深的文件總?cè)萘吭酱?，?LevelDB 源碼里有一個(gè)層級(jí)容量公式，容量和層級(jí)呈指數(shù)級(jí)關(guān)系。而通常每個(gè) sst 文件的大小都差不多，區(qū)別就成了每一層的文件數(shù)量不一樣。

capacity = level > 0 && 10^(level+1) M

每個(gè)文件里面的 Key 都是有序的，也就是說它內(nèi)部的 Key 取值會(huì)有一個(gè)確定的范圍。0 層文件和其它層文件有一個(gè)明顯的區(qū)別那就是其它層內(nèi)部的文件之間范圍不會(huì)重疊，它們按照 Key 的順序嚴(yán)格做了切分。而 0 層文件的內(nèi)容是直接從內(nèi)存 dump 下來的，所以 0 層的多個(gè)文件的 Key 取值范圍會(huì)有重疊。

當(dāng)內(nèi)存出現(xiàn)讀 miss 要去磁盤搜尋時(shí)，會(huì)首先從 0 層搜尋，如果搜不到再去更深層次搜尋。

如果是其它層級(jí)，搜尋速度會(huì)很快，因?yàn)榭梢愿鶕?jù) Key 的范圍快速確定它可能會(huì)位于哪個(gè)文件中。但是對(duì)于 0 層，因?yàn)槲募?Key 范圍會(huì)重疊，所以它可能存在于多個(gè)文件中，那就需要對(duì)這多個(gè)文件進(jìn)行搜尋。正因如此，LevelDB 限制了 0 層文件的數(shù)量，如果數(shù)量超出了默認(rèn)的 4 個(gè)，就需要「下沉」到 1 層，這個(gè)「下沉」操作就是 Major Compaction。

所有文件的 Key 取值范圍、層級(jí)和其它元信息會(huì)存儲(chǔ)在數(shù)據(jù)庫(kù)目錄里面的 MANIFEST 文件中。數(shù)據(jù)庫(kù)打開時(shí)，讀取一下這個(gè)文件就知道了所有文件的層級(jí)和 Key 取值范圍。

MANIFEST 文件也有版本號(hào)，它的版本號(hào)體現(xiàn)在文件名上如 MANIFEST-000361。每一次重新打開數(shù)據(jù)庫(kù)，都會(huì)生成一個(gè)新的 MANIFEST 文件，具有不同的版本號(hào)，然后還需要將老的 MANIFEST 文件刪除。

數(shù)據(jù)庫(kù)目錄中還有另外一個(gè)文件 CURRENT，它里面的內(nèi)容很簡(jiǎn)單，就是當(dāng)前 MANIFEST 的文件名。LevelDB 首先讀取 CURRENT 文件才知道哪個(gè) MANIFEST 文件是有效文件。在遇到斷電時(shí)，會(huì)存在一個(gè)小概率中間狀態(tài)，新舊 MANIFEST 文件共存于數(shù)據(jù)庫(kù)目錄中。

我們知道 LevelDB 的數(shù)據(jù)庫(kù)目錄不允許多進(jìn)程同時(shí)訪問，那它是如何防止其它進(jìn)程意外對(duì)這個(gè)目錄文件進(jìn)行讀寫操作呢？仔細(xì)觀察數(shù)據(jù)庫(kù)目錄，你還會(huì)發(fā)現(xiàn)一個(gè)名稱為 LOCK 的文件，它就是控制多進(jìn)程訪問數(shù)據(jù)庫(kù)的關(guān)鍵。當(dāng)一個(gè)進(jìn)程打開了數(shù)據(jù)庫(kù)時(shí)，會(huì)在這個(gè)文件上加上互斥文件鎖，進(jìn)程結(jié)束時(shí)，鎖就會(huì)自動(dòng)釋放。

還有最后一個(gè)不那么重要的操作日志文件 LOG，它記錄了數(shù)據(jù)庫(kù)的一系列關(guān)鍵性操作日志，例如每一次 Minor 和 Major Compaction 的相關(guān)信息。

多路歸并

Compaction 是比較耗費(fèi)資源的操作，為了不影響線上的讀寫操作，LevelDB 將 Compaction 工作交給一個(gè)單一的異步線程來完成。如果工作量巨大，這個(gè)單一的異步線程也會(huì)有點(diǎn)吃不消。當(dāng)異步線程吃不消的時(shí)候，線上內(nèi)存的讀寫操作也會(huì)收到影響。因?yàn)橹挥?rtable 沉到磁盤里了，wtable 才可以變身。只有 wtable 變身了，才會(huì)有新的 wtable 被創(chuàng)建來容納后續(xù)更多的鍵值對(duì)?？傊褪且画h(huán)套一環(huán)，環(huán)環(huán)相扣。

下面我們來研究一下 Compaction 。Minor Compaction 很好理解，就是內(nèi)容空間有限，所以需要將 rtable 中的數(shù)據(jù) dump 到磁盤 0 層文件。那為什么需要從 0 層文件 Compact 下沉到 1 層文件呢？因?yàn)?0 層文件如果過多，就會(huì)影響查找效率。前面我們提到 0 層文件之間的 Key 范圍會(huì)有重疊，所以單個(gè) Key 可能存在于多個(gè)文件中，IO 讀次數(shù)將會(huì)被文件的數(shù)量放大。通過 Major Compaction 可以減少 0 層文件的數(shù)量，提升讀效率。那是不是只需要下沉到 1 層文件就可以了呢？那 LevelDB 究竟是什么原因需要這么多層級(jí)呢？

假設(shè) LevelDB 只有 2 層（ 0 層和 1 層），那么時(shí)間一長(zhǎng)，1 層肯定會(huì)累計(jì)大量的文件。當(dāng) 0 層的文件需要下沉?xí)r，也就是 Major Compaction 要來了，假設(shè)只下沉一個(gè) 0 層文件，它不是簡(jiǎn)簡(jiǎn)單單地將文件元信息的層數(shù)從 0 改成 1 就可以了。它需要繼續(xù)保持 1 層文件的有序性，每個(gè)文件中的 Key 取值范圍要保持沒有重疊。它不能直接將 0 層文件中的鍵值對(duì)分散插入或者追加到 1 層的所有文件中，因?yàn)?sst 文件是緊湊存儲(chǔ)的，插入操作肯定涉及到磁盤塊的移動(dòng)。再說還有刪除操作，它需要干掉 1 層文件中的某些已刪除的鍵值對(duì)，避免它們持續(xù)占用空間。

那 LevelDB 究竟是怎么做的呢？它采用多路歸并算法，將相關(guān)的 0 層文件和 1 層 sst 文件作為輸入，進(jìn)行多路歸并，生成多個(gè)新的 1 層 sst 文件，再將老的 sst 文件干掉，同時(shí)還會(huì)生成新的 MANIFEST 文件。對(duì)于每個(gè) 0 層文件，它會(huì)根據(jù) Key 的取值范圍搜尋 1 層文件中和它的范圍有重疊部分的 sst 文件。如果 1 層文件數(shù)量過多，每次多路歸并涉及到的文件數(shù)量太多，歸并算法就會(huì)非常耗費(fèi)資源。所以 LevelDB 同樣也需要控制 1 層文件的數(shù)量，當(dāng) 1 層容量滿時(shí)，就會(huì)繼續(xù)下沉到 2 層、3 層、4 層等。

非 0 層的多路歸并資源消耗要少一些，因?yàn)閱蝹€(gè)文件的 Key 取值范圍有限，能覆蓋到下一層的文件數(shù)量有限，參與多路歸并的輸入文件就少了很多。但是這個(gè)邏輯有個(gè)漏洞，那就是上下層的文件數(shù)量有 10 倍的差距，按照平均范圍間隔來算，意味著上層平均一個(gè)文件的取值范圍會(huì)覆蓋到下一層的 10 個(gè)文件。所以說非 0 層的多路歸并資源消耗其實(shí)也不低，Major Compaction 就是一個(gè)比較消耗資源的操作。

讀到這里，這篇“LevelDB的整體架構(gòu)是怎樣的”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

本文名稱：LevelDB的整體架構(gòu)是怎樣的
本文網(wǎng)址：http://muchs.cn/article8/pidgop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供營(yíng)銷型網(wǎng)站建設(shè)、微信小程序、、企業(yè)網(wǎng)站制作、網(wǎng)站內(nèi)鏈、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)