一区二区三区三上|欧美在线视频五区|国产午夜无码在线观看视频|亚洲国产裸体网站|无码成年人影视|亚洲AV亚洲AV|成人开心激情五月|欧美性爱内射视频|超碰人人干人人上|一区二区无码三区亚洲人区久久精品

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

TiDB底層存儲結(jié)構(gòu)LSM樹原理介紹

OSC開源社區(qū) ? 來源:OSCHINA 社區(qū) ? 2023-01-13 10:00 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

來源| OSCHINA 社區(qū)

作者 | 京東云開發(fā)者-京東物流 劉家存

隨著數(shù)據(jù)量的增大,傳統(tǒng)關(guān)系型數(shù)據(jù)庫越來越不能滿足對于海量數(shù)據(jù)存儲的需求。對于分布式關(guān)系型數(shù)據(jù)庫,我們了解其底層存儲結(jié)構(gòu)是非常重要的。本文將介紹下分布式關(guān)系型數(shù)據(jù)庫 TiDB 所采用的底層存儲結(jié)構(gòu) LSM 樹的原理。

1 LSM 樹介紹

LSM 樹(Log-Structured-Merge-Tree) 日志結(jié)構(gòu)合并樹由 Patrick O’Neil 等人在論文《The Log-Structured Merge Tree》(https://www.cs.umb.edu/~poneil/lsmtree.pdf) 中提出,它實際上不是一棵樹,而是 2 個或者多個不同層次的樹或類似樹的結(jié)構(gòu)的集合。 LSM 樹的核心特點是利用順序?qū)憗硖岣邔懶阅?,代價就是會稍微降低讀性能(讀放大),寫入量增大(寫放大)和占用空間增大(空間放大)。 LSM 樹主要被用于 NoSql 數(shù)據(jù)庫中,如 HBase、RocksDB、LevelDB 等,知名的分布式關(guān)系型數(shù)據(jù)庫 TiDB 的 kv 存儲引擎 TiKV 底層存儲就是用的上面所說的 RocksDB,也就是用的 LSM 樹。

2 LSM 樹算法大概思路

LSM 樹由兩個或多個樹狀的結(jié)構(gòu)組成。
這一節(jié)我們以兩個樹狀的結(jié)構(gòu)構(gòu)成的簡單的雙層 LSM 樹舉例,來簡單說下 LSM 樹大概思路,讓大家對 LSM 樹實現(xiàn)有個整體的認(rèn)識。 022e5ad6-929a-11ed-bfe3-dac502259ad0.png 原論文中的圖

2.1 數(shù)據(jù)結(jié)構(gòu)

雙層 LSM 樹有一個較小的層,該層完全駐留在內(nèi)存中,作為 C0 樹(或 C0 層),以及駐留在磁盤上的較大層,稱為 C1 樹。
盡管 C1 層駐留在磁盤上,但 C1 中經(jīng)常引用的節(jié)點將保留在內(nèi)存緩沖區(qū)中,因此 C1 經(jīng)常引用的節(jié)點也可以被視為內(nèi)存駐留節(jié)點。

2.2 寫入

寫入時,首先將記錄行寫入順序日志文件 WAL 中,然后再將此記錄行的索引項插入到內(nèi)存駐留的 C0 樹中,然后通過異步任務(wù)及時遷移到磁盤上的 C1 樹中。

2.3 讀取

任何搜索索引項將首先在 C0 中查找,在 C0 中未找到,然后再在 C1 中查找。
如果存在崩潰恢復(fù),還需要讀取恢復(fù)崩潰前未從磁盤中取出的索引項。

2.4 Compact 過程

將索引條目插入駐留在內(nèi)存中的 C0 樹的操作沒有 I/O 成本,然而,與磁盤相比,容納 C0 組件的內(nèi)存容量成本較高,這對其大小施加了限制。達(dá)到一定大小后,我們就需要將數(shù)據(jù)遷移到下一層。
我們需要一種有效的方法將記錄項遷移到駐留在成本較低的磁盤介質(zhì)上的 C1 樹中。為了實現(xiàn)這一點,當(dāng)插入達(dá)到或接近每一層分配的最大值的閾值大小,將進(jìn)行一個滾動合并(Compact)過程,用于從 C0 樹中刪除一些連續(xù)的記錄項,并將其合并到 C1 中。
Compact 目前有兩種策略,size-tiered 策略,leveled 策略,我們將在下面的內(nèi)容里詳細(xì)介紹這兩種策略。

2.5 崩潰恢復(fù)

在 C0 樹中的項遷移到駐留在磁盤上的 C1 樹之前,存在一定的延遲(延遲),為了保證機(jī)器崩潰后 C0 樹中的數(shù)據(jù)不丟失,在生成每個新的歷史記錄行時,首先將用于恢復(fù)此插入的日志記錄寫入以常規(guī)方式創(chuàng)建的順序日志文件 WAL 中,然后再寫入 C0 中。

3 LSM 樹的組成

LSM 樹有三個重要組成部分,MemTable,Immutable MemTable,SSTable (Sorted String Table),如下圖。 023be3cc-929a-11ed-bfe3-dac502259ad0.png 這張經(jīng)典圖片來自 Flink PMC 的 Stefan Richter 在 Flink Forward 2018 演講的 PPT 這幾個組成部分分別對應(yīng) LSM 樹的不同層次,不同層級間數(shù)據(jù)轉(zhuǎn)移見下圖。這節(jié)就是介紹 LSM 樹抽象的不同層的樹狀數(shù)據(jù)結(jié)構(gòu)的某個具體實現(xiàn)方式。 025eda1c-929a-11ed-bfe3-dac502259ad0.png

3.1 MemTable

MemTable 是在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu),用于保存最近更新的數(shù)據(jù),會按照 Key 有序地組織這些數(shù)據(jù)。LSM 樹對于具體如何組織有序地組織數(shù)據(jù)并沒有明確的數(shù)據(jù)結(jié)構(gòu)定義,例如你可以任意選擇紅黑樹、跳表等數(shù)據(jù)結(jié)構(gòu)來保證內(nèi)存中 key 的有序。

3.2 Immutable MemTable

為了使內(nèi)存數(shù)據(jù)持久化到磁盤時不阻塞數(shù)據(jù)的更新操作,在 MemTable 變?yōu)?SSTable 中間加了一個 Immutable MemTable。
當(dāng) MemTable 達(dá)到一定大小后,會轉(zhuǎn)化成 Immutable MemTable,并加入到 Immutable MemTable 隊列尾部,然后會有任務(wù)從 Immutable MemTable 隊列頭部取出 Immutable MemTable 并持久化磁盤里。

3.3 SSTable(Sorted String Table)

有序鍵值對集合,是 LSM 樹組在磁盤中的數(shù)據(jù)結(jié)構(gòu)。
其文件結(jié)構(gòu)基本思路就是先劃分為數(shù)據(jù)塊 (類似于 mysql 中的頁),然后再為數(shù)據(jù)塊建立索引,索引項放在文件末尾,并用布隆過濾器優(yōu)化查找。

4 LSM 樹的 Compact 策略

當(dāng)某層數(shù)據(jù)量大小達(dá)到我們預(yù)設(shè)的閾值后,我們就會通過 Compact 策略將其轉(zhuǎn)化到下一層。 在介紹 Compact 策略前,我們先想想如果讓我們自己設(shè)計 Compact 策略,對于以下幾個問題,我們該如何選擇。

對于某一層的樹,我們用單個文件還是多個文件進(jìn)行實現(xiàn)?

如果是多個文件,那同一層 SSTable 的 key 范圍是有序還是重合?有序方便讀,重合方便寫。

每層 SSTable 的大小以及不同層之間文件大小是否相等。

每層 SSTable 的數(shù)量。如果同一層 key 范圍是重合的,則數(shù)量越多,讀的效率越低。

不同的選擇會造成不同的讀寫策略,基于以上 3 個問題,又帶來了 3 個概念:

讀放大:讀取數(shù)據(jù)時實際讀取的數(shù)據(jù)量大于真正的數(shù)據(jù)量。例如在 LSM 樹中可能需要在所有層次的樹中查看當(dāng)前 key 是否存在。

寫放大:寫入數(shù)據(jù)時實際寫入的數(shù)據(jù)量大于真正的數(shù)據(jù)量。例如在 LSM 樹中寫入時可能觸發(fā) Compact 操作,導(dǎo)致實際寫入的數(shù)據(jù)量遠(yuǎn)大于數(shù)據(jù)的大小。

空間放大:數(shù)據(jù)實際占用的磁盤空間比數(shù)據(jù)的真正大小更多。LSM 樹中同一 key 在不同層次里或者同一層次的不同 SSTable 里可能會重復(fù)。

不同的策略實際就是圍繞這三個概念之間做出權(quán)衡和取舍,我們主要介紹兩種基本策略:size-tiered 策略和 leveled 策略,這兩個策略對于以上 3 個概念做了不同的取舍。

4.1 size-tiered 策略

0275bbba-929a-11ed-bfe3-dac502259ad0.png

4.1.1 算法

size-tiered 策略每層 SSTable 的大小相近。

當(dāng)每一層 SSTable 的數(shù)量達(dá)到 N 后,則觸發(fā) Compact 操作合并這些 SSTable,并將合并后的結(jié)果寫入到一個更大的 SStable。

新的更大的 SStable 將直接放到下一層 SStable 的隊尾。所以同一層不同 SStable key 范圍重合,查找時要從后向前掃描,且最壞情況下可能會掃描同一層所有 SStable ,這增大了讀放大的問題 (之所以說增大,是因為 LSM 樹不同層之間也有讀放大問題)。

4.1.2 總結(jié)

由此可以看出 size-tiered 策略幾個特點:

每層 SSTable 的數(shù)量相近。

當(dāng)層數(shù)達(dá)到一定數(shù)量時,最底層的單個 SSTable 的大小會變得非常大。

不但不同層之間,哪怕同一層不同 SSTable 之間,key 也可能會出現(xiàn)重復(fù)??臻g放大比較嚴(yán)重。只有當(dāng)該層的 SSTable 執(zhí)行 compact 操作才會消除這些 key 的冗余記錄。

讀操作時,需要同時讀取同一層所有 SSTable ,讀放大嚴(yán)重。

4.2 leveled 策略

02938ee2-929a-11ed-bfe3-dac502259ad0.png

4.2.1 算法

leveled 策略和 size-tiered 策略不同的是,它限制 SSTable 文件的大小,每一層不同 SSTable 文件 key 范圍不重疊且后面的最小 key 大于前一個文件的最大 key

當(dāng)每一層 SSTable 的總大小達(dá)到閾值 N 后,則觸發(fā) Compact 操作。

首先會隨機(jī)選擇一個 SSTable 合并到下層,由于下一層 key 是全局有序的,這就要求 leveled 策略 Compact 操作時需要當(dāng)前 SSTable 和下一層里和當(dāng)前 SSTable key 存在范圍重疊的所有 SSTable 進(jìn)行合并。最壞情況下可能下一層所有 SSTable 都參與合并,這就增大了寫放大問題 (之所以說增大,是因為 LSM 樹不同層之間 Compact 也有寫放大問題)。

4.2.2 總結(jié)

由此可以看出 leveled 策略幾個特點:

不會出現(xiàn)非常大的 SSTable 文件。

每一層不同 SSTable 文件 key 范圍不重疊。相對于 size-tiered 策略讀放大更小。

Compact 操作時,需要同時和下一層 SSTable 一起合并,寫放大嚴(yán)重。

5 LSM 樹的插入、修改、刪除

從 LSM 樹的名字,Log-Structured-Merge-Tree 日志結(jié)構(gòu)合并樹中我們大概就能知道 LSM 樹的插入、修改、刪除的方法了 —— 順序追加而非修改 (對磁盤操作而言)。

LSM 樹的插入、修改、刪除都是在 L0 層的樹里插入、修改、刪除一條記錄,并記錄記錄項的時間戳,由于只需要取最新的內(nèi)容即可,所以不需要操作后面層次的樹。

歷史的插入、修改、刪除的記錄會在每次 Compact 操作時被后面的記錄覆蓋。

6 LSM 樹的查找

由于后面的操作會覆蓋前面的操作,所以查找只需從 L0 層往下查,直到查到某個 key 的記錄就可以了,之前的記錄不需要再查了。

對于 size-tiered 策略,同一層 SSTable 需要從后向前遍歷,直到找到符合的索引項。

在查找過程中也會使用其他一些手段進(jìn)行優(yōu)化,例如增加緩存、布隆過濾器等。

7 LSM 樹和 B+ 樹的比較

不考慮寫日志等操作,插入、修改、刪除一條記錄 B+ 樹需要先找到數(shù)據(jù)位置,可能需要多次磁盤 IO;LSM 樹不需要磁盤 IO,單次插入耗時短,所以其寫入的最大吞吐量是高于 B+ 樹的。

LSM 樹后面的 Compact 操作也會操作這條數(shù)據(jù)幾次,總的寫入量是大于 B+ 樹的,但可以通過將 Compact 操作放到業(yè)務(wù)低峰時來降低這個劣勢的影響。

查找時, LSM 樹需要遍歷所有層次的樹,查找效率上要低于 B+ 樹,但 LSM 樹寫入時節(jié)省的磁盤資源占用,可以一定程度上彌補(bǔ)讀效率上的差距。

8 總結(jié)

LSM 樹特點:順序?qū)懭?、Compact 操作、讀、寫和空間放大。
LSM 樹適用場景:對于寫操作吞吐量要求很高、讀操作吞吐量要就較高的場景,目前主要在 NoSql 數(shù)據(jù)庫中用的比較多。

審核編輯:湯梓紅

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 算法
    +關(guān)注

    關(guān)注

    23

    文章

    4710

    瀏覽量

    95409
  • 數(shù)據(jù)庫
    +關(guān)注

    關(guān)注

    7

    文章

    3927

    瀏覽量

    66262
  • 數(shù)據(jù)結(jié)構(gòu)

    關(guān)注

    3

    文章

    573

    瀏覽量

    40756
  • 存儲結(jié)構(gòu)
    +關(guān)注

    關(guān)注

    0

    文章

    21

    瀏覽量

    9838
  • 底層存儲
    +關(guān)注

    關(guān)注

    0

    文章

    2

    瀏覽量

    5428

原文標(biāo)題:TiDB底層存儲結(jié)構(gòu)LSM樹原理介紹

文章出處:【微信號:OSC開源社區(qū),微信公眾號:OSC開源社區(qū)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。

收藏 人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評論

    相關(guān)推薦
    熱點推薦

    的遞歸結(jié)構(gòu)存儲結(jié)構(gòu)分析

    的遞歸結(jié)構(gòu) 從一張圖中解釋什么是 這張圖,主要講解關(guān)于cart這個單詞的所有的可能組合,按照常理,需要先考慮三個字母的排列,然后對三個字母進(jìn)行拆分,直到最后一個節(jié)點,這個過程就類似于
    的頭像 發(fā)表于 10-16 14:33 ?4607次閱讀
    <b class='flag-5'>樹</b>的遞歸<b class='flag-5'>結(jié)構(gòu)</b>和<b class='flag-5'>樹</b>的<b class='flag-5'>存儲</b><b class='flag-5'>結(jié)構(gòu)</b>分析

    MySQL數(shù)據(jù)庫索引的底層是怎么實現(xiàn)的

    二叉,B,B+這4種數(shù)據(jù)結(jié)構(gòu),以及為啥選用B+作為mysql數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)。首先看下這
    發(fā)表于 07-28 15:30

    Hypertable底層存儲結(jié)構(gòu)分析

    通過分析Hypertable 的源代碼,描述了CellStore 存儲結(jié)構(gòu),介紹其讀寫流程,總結(jié)了該結(jié)構(gòu)存在的缺陷,并提出了優(yōu)化思路。優(yōu)化步驟主要包括:將關(guān)鍵字?jǐn)?shù)據(jù)進(jìn)行合并,建立關(guān)鍵字
    發(fā)表于 05-12 16:37 ?27次下載
    Hypertable<b class='flag-5'>底層</b><b class='flag-5'>存儲</b><b class='flag-5'>結(jié)構(gòu)</b>分析

    決策介紹

    關(guān)于決策介紹,是一些很基礎(chǔ)的介紹,不過是英文介紹。
    發(fā)表于 09-18 14:55 ?0次下載

    基于KD和R的多維索引結(jié)構(gòu)

    針對云存儲系統(tǒng)大多基于鍵值對 key,value模型存儲數(shù)據(jù),多維查詢需要對整個數(shù)據(jù)集進(jìn)行完全掃描,查詢效率較低的問題,提出了一種基于KD和R的多維索引
    發(fā)表于 01-25 15:13 ?0次下載
    基于KD<b class='flag-5'>樹</b>和R<b class='flag-5'>樹</b>的多維索引<b class='flag-5'>結(jié)構(gòu)</b>

    Linux 內(nèi)核里的數(shù)據(jù)結(jié)構(gòu)關(guān)鍵:基數(shù)

    基數(shù)是一種 壓縮的字典compressed trie ,而字典是實現(xiàn)了關(guān)聯(lián)數(shù)組接口并允許以 鍵值對 方式存儲值的一種數(shù)據(jù)結(jié)構(gòu)。這里的鍵
    發(fā)表于 04-28 16:04 ?982次閱讀

    如何存儲Merkle

    Merkle 是一種型數(shù)據(jù)結(jié)構(gòu),其葉子節(jié)點是數(shù)據(jù)塊的 hash 值,而非葉子節(jié)點是其對應(yīng)子節(jié)點 hash 值串聯(lián)后字符串的 hash 值。利用 Merkle ,能夠在只有部分?jǐn)?shù)據(jù)
    發(fā)表于 11-06 11:11 ?2709次閱讀

    新數(shù)據(jù)結(jié)構(gòu)”的詳細(xì)介紹

    ,咱們今天要嘮啥了。 之前給大家介紹了鏈表,棧,哈希表 等數(shù)據(jù)結(jié)構(gòu) 今天咱們來看一種新的數(shù)據(jù)結(jié)構(gòu),。 PS:本篇文章內(nèi)容較基礎(chǔ),對于沒有學(xué)過數(shù)據(jù)結(jié)
    的頭像 發(fā)表于 05-25 15:28 ?2537次閱讀
    新數(shù)據(jù)<b class='flag-5'>結(jié)構(gòu)</b>“<b class='flag-5'>樹</b>”的詳細(xì)<b class='flag-5'>介紹</b>

    數(shù)據(jù)結(jié)構(gòu)字典的實現(xiàn)

    什么是字典字典,是一種空間換時間的數(shù)據(jù)結(jié)構(gòu),又稱Trie、前綴,是一種樹形結(jié)構(gòu)(字典
    的頭像 發(fā)表于 09-07 15:03 ?2369次閱讀
    數(shù)據(jù)<b class='flag-5'>結(jié)構(gòu)</b>字典<b class='flag-5'>樹</b>的實現(xiàn)

    數(shù)據(jù)結(jié)構(gòu)LSM tree核心實現(xiàn)講解

    LSM tree (log-structured merge-tree) 是一種對頻繁寫操作非常友好的數(shù)據(jù)結(jié)構(gòu),同時兼顧了查詢效率。LSM tree 是許多 key-value 型或日志型數(shù)據(jù)庫所依
    的頭像 發(fā)表于 09-30 14:19 ?2623次閱讀

    TiDB Operator自動化部署運(yùn)維工具

    tidb-operator.zip
    發(fā)表于 04-28 09:15 ?0次下載
    <b class='flag-5'>TiDB</b> Operator自動化部署運(yùn)維工具

    存儲系統(tǒng)中的算法:LSM設(shè)計原理

    的,而 LevelDB 的核心是一個叫做 LSM (Log Structured Merge Tree)的結(jié)構(gòu)
    的頭像 發(fā)表于 11-03 11:32 ?1273次閱讀

    安全連接 TiDB/Mysql編程案例分析

    為了安全起見,Tidb Cloud Serverless Tier 貌似只支持安全連接。
    發(fā)表于 03-17 09:36 ?529次閱讀

    redis數(shù)據(jù)結(jié)構(gòu)底層實現(xiàn)

    Redis是一種內(nèi)存鍵值數(shù)據(jù)庫,常用于緩存、消息隊列、實時數(shù)據(jù)分析等場景。它的高性能得益于其精心設(shè)計的數(shù)據(jù)結(jié)構(gòu)底層實現(xiàn)。本文將詳細(xì)介紹Redis常用的數(shù)據(jù)結(jié)構(gòu)和它們的
    的頭像 發(fā)表于 12-05 10:14 ?871次閱讀

    時鐘是什么?介紹兩種時鐘樹結(jié)構(gòu)

    今天來聊一聊時鐘。首先我先講一下我所理解的時鐘是什么,然后介紹兩種時鐘樹結(jié)構(gòu)。
    的頭像 發(fā)表于 12-06 15:23 ?2579次閱讀