LSMTree-創(chuàng)新互聯(lián)

LSM Tree 的存儲(chǔ)模型，包括 Tidb，HBase等

創(chuàng)新互聯(lián)2013年至今，是專(zhuān)業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目做網(wǎng)站、網(wǎng)站建設(shè)網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個(gè)夢(mèng)想脫穎而出為使命，1280元和順做網(wǎng)站,已為上家服務(wù),為和順各地企業(yè)和個(gè)人服務(wù),聯(lián)系電話(huà):028-86922220特點(diǎn)

通過(guò)將大量的隨機(jī)寫(xiě)轉(zhuǎn)換為順序?qū)?，從而極大地提升了數(shù)據(jù)寫(xiě)入的性能，雖然與此同時(shí)犧牲了部分讀的性能。

只適合存儲(chǔ) key 值有序且寫(xiě)入大于讀取的數(shù)據(jù)，或者讀取操作通常是 key 值連續(xù)的數(shù)據(jù)。

存儲(chǔ)模型

WAL

在設(shè)計(jì)數(shù)據(jù)庫(kù)的時(shí)候經(jīng)常被使用，當(dāng)插入數(shù)據(jù)時(shí)，先順序?qū)懭?WAL 文件中，之后插入到內(nèi)存中的 MemTable 中。
1.保證了數(shù)據(jù)的持久化，不會(huì)丟失數(shù)據(jù)，并且都是順序?qū)懀俣群芸臁?br />2.當(dāng)程序掛掉重啟時(shí)，可以從 WAL 文件中重新恢復(fù)內(nèi)存中的 MemTable。

MemTable

MemTable 對(duì)應(yīng)的就是 WAL 文件在內(nèi)存中的存儲(chǔ)結(jié)構(gòu)，通常用 跳躍表SkipList 來(lái)實(shí)現(xiàn)。MemTable 提供了 k-v 數(shù)據(jù)的寫(xiě)入、刪除以及讀取的操作接口。其內(nèi)部將 k-v 對(duì)按照 key 值有序存儲(chǔ)，這樣方便之后快速序列化到 SSTable 文件中，仍然保持?jǐn)?shù)據(jù)的有序性。

為了維持有序性在內(nèi)存里面可以采用紅黑樹(shù)或者跳躍表相關(guān)的數(shù)據(jù)結(jié)構(gòu)。

Immutable Memtable

在內(nèi)存中只讀的 MemTable，由于內(nèi)存是有限的，通常我們會(huì)設(shè)置一個(gè)閥值，當(dāng) MemTable 占用的內(nèi)存達(dá)到閥值后就自動(dòng)轉(zhuǎn)換為 Immutable Memtable，Immutable Memtable 是只讀不寫(xiě)的，系統(tǒng)此時(shí)會(huì)生成新的 MemTable 供寫(xiě)操作繼續(xù)寫(xiě)入。

之所以要使用 Immutable Memtable，就是為了避免將Immutable MemTable 中的內(nèi)容序列化到磁盤(pán)中時(shí)會(huì)阻塞寫(xiě)操作。

為什么LSM不直接順序?qū)懭氪疟P(pán)，而是需要在內(nèi)存中緩沖一下？
單條寫(xiě)的性能肯定沒(méi)有批量寫(xiě)來(lái)的塊。例如kafka給我們的感覺(jué)是寫(xiě)入后就落地，但其實(shí)并不是，可以根據(jù)條數(shù)或者時(shí)間比如200ms刷入磁盤(pán)一次，這樣能大大提升寫(xiě)入效率。此外在LSM中，在磁盤(pán)緩沖的另一個(gè)好處是，針對(duì)新增的數(shù)據(jù)，可以直接查詢(xún)返回，能夠避免一定的IO操作。

SSTable（Sorted String Table）

SSTable 就是Immutable MemTable 中的數(shù)據(jù)在磁盤(pán)上的有序存儲(chǔ)，其內(nèi)部數(shù)據(jù)是根據(jù) key 從小到大排列的。通常為了加快查找的速度，需要在 SSTable 中加入數(shù)據(jù)索引，可以快讀定位到指定的 k-v 數(shù)據(jù)。

SSTable 通常采用的分級(jí)的結(jié)構(gòu)（默認(rèn)至多 6 層）。Immutable MemTable 中的數(shù)據(jù)達(dá)到指定閥值后會(huì)在 Level 0 層創(chuàng)建一個(gè)新的 SSTable。每一層的數(shù)據(jù)達(dá)到一定閾值后會(huì)挑選一部分 SST 合并到下一層（舊的文件刪除），每一層的數(shù)據(jù)是上一層的 10 倍（因此 90% 的數(shù)據(jù)存儲(chǔ)在最后一層）。
SSTable 中的 k-v 數(shù)據(jù)都是有序的，相當(dāng)于是多路歸并排序（Merge sort），合并操作相當(dāng)快速。

L0層的SSTable是沒(méi)有進(jìn)行合并的，所以這里的key range在多個(gè)SSTable中可能會(huì)出現(xiàn)重疊，在層數(shù)大于0層之后的SSTable，不存在重疊key。

（Minor/Major Compaction：
Minor Compaction：Memtable到SSTable層；
Major Compaction：當(dāng)每層的磁盤(pán)上的SSTable的體積超過(guò)一定的大小或者個(gè)數(shù)，也會(huì)周期的進(jìn)行合并。清除掉被標(biāo)記刪除掉的數(shù)據(jù)以及多版本數(shù)據(jù)的合并，避免浪費(fèi)空間）

更新

更新操作其實(shí)并不真正存在，和寫(xiě)入一個(gè) k-v 數(shù)據(jù)沒(méi)有什么不同，只是在讀取的時(shí)候，會(huì)從 Level0 層的 SSTable 文件開(kāi)始查找數(shù)據(jù)，數(shù)據(jù)在上層的 SSTable 文件中必然比下層的文件中要新，所以總能讀取到最新的那條數(shù)據(jù)。也就是說(shuō)此時(shí)在整個(gè) LSM Tree 中可能會(huì)同時(shí)存在多個(gè) key 值相同的數(shù)據(jù)，只有在之后合并 SSTable 文件的時(shí)候，才會(huì)將舊的值刪除。

刪除

刪除一條記錄的操作比較特殊，并不立即將數(shù)據(jù)從文件中刪除，而是記錄下對(duì)這個(gè) key 的刪除操作標(biāo)記，同插入操作相同，插入操作插入的是 k-v 值，而刪除操作插入的是 k-del 標(biāo)記，只有當(dāng)合并 SSTable 文件時(shí)才會(huì)真正的刪除。

合并Compaction（size-tiered和leveled）

當(dāng)數(shù)據(jù)不斷從 Immutable Memtable 序列化到磁盤(pán)上的 SSTable 文件中時(shí)，SSTable 文件的數(shù)量就不斷增加，而且其中可能有很多更新和刪除操作并不立即對(duì)文件進(jìn)行操作，而只是存儲(chǔ)一個(gè)操作記錄，這就造成了整個(gè) LSM Tree 中可能有大量相同 key 值的數(shù)據(jù)，占據(jù)了磁盤(pán)空間。為了節(jié)省磁盤(pán)空間占用，控制 SSTable 文件數(shù)量，需要將多個(gè) SSTable 文件進(jìn)行合并，生成一個(gè)新的 SSTable 文件。

1）讀放大:讀取數(shù)據(jù)時(shí)實(shí)際讀取的數(shù)據(jù)量大于真正的數(shù)據(jù)量。例如在LSM樹(shù)中需要先在MemTable查看當(dāng)前key是否存在，不存在繼續(xù)從SSTable中尋找。
2）寫(xiě)放大:寫(xiě)入數(shù)據(jù)時(shí)實(shí)際寫(xiě)入的數(shù)據(jù)量大于真正的數(shù)據(jù)量。例如在LSM樹(shù)中寫(xiě)入時(shí)可能觸發(fā)Compact操作，導(dǎo)致實(shí)際寫(xiě)入的數(shù)據(jù)量遠(yuǎn)大于該key的數(shù)據(jù)量。
3）空間放大:數(shù)據(jù)實(shí)際占用的磁盤(pán)空間比數(shù)據(jù)的真正大小 大更多。冗余存儲(chǔ)，對(duì)于一個(gè)key來(lái)說(shuō)，只有最新的那條記錄是有效的，而之前的記錄都是可以被清理回收的。

1) size-tiered 策略

保證每層SSTable的大小相近，同時(shí)限制每一層SSTable的數(shù)量。如上圖，每層限制SSTable為N，當(dāng)每層SSTable達(dá)到N后，則觸發(fā)Compact操作合并這些SSTable，并將合并后的結(jié)果寫(xiě)入到下一層成為一個(gè)更大的sstable。

由此可以看出，當(dāng)層數(shù)達(dá)到一定數(shù)量時(shí)，最底層的單個(gè)SSTable的大小會(huì)變得非常大。并且size-tiered策略會(huì)導(dǎo)致空間放大比較嚴(yán)重。即使對(duì)于同一層的SSTable，每個(gè)key的記錄是可能存在多份的，只有當(dāng)該層的SSTable執(zhí)行compact操作才會(huì)消除這些key的冗余記錄。

2) leveled策略

每一層的總大小固定，從上到下逐漸變大
采用分層思想，每一層限制總文件的大小。
將每一層切分成多個(gè)大小相近的SSTable。這些SSTable是這一層是全局有序的。
知乎-LSM樹(shù)詳解

讀取

LSM Tree 的讀取效率并不高，當(dāng)需要讀取指定 key 的數(shù)據(jù)時(shí)，

1. 先在內(nèi)存中的 MemTable 和 Immutable MemTable 中查找，查詢(xún)到就返回。
2. 如果沒(méi)有找到，則從 Level 0 層開(kāi)始依次下沉，直到把所有的Level層查詢(xún)一遍得到最終結(jié)果，如果查找失敗，說(shuō)明整個(gè) LSM Tree 中都不存在這個(gè) key 的數(shù)據(jù)。如果中間在任何一個(gè)地方找到這個(gè) key 的數(shù)據(jù)，那么按照這個(gè)路徑找到的數(shù)據(jù)都是最新的。

在每一層的 SSTable 文件的 key 值范圍是不重復(fù)的，所以只需要查找其中一個(gè) SSTable 文件即可確定指定 key 的數(shù)據(jù)是否存在于這一層中。Level 0 層比較特殊，因?yàn)閿?shù)據(jù)是 Immutable MemTable 直接寫(xiě)入此層的，所以 Level 0 層的 SSTable 文件的 key 值范圍可能存在重復(fù)，查找數(shù)據(jù)時(shí)有可能需要查找多個(gè)文件。

優(yōu)化讀取

因?yàn)檫@樣的讀取效率非常差，通常會(huì)進(jìn)行一些優(yōu)化，例如 LevelDB 中的 Mainfest 文件，這個(gè)文件記錄了 SSTable 文件的一些關(guān)鍵信息，例如 Level 層數(shù)，文件名，最小 key 值，大 key 值等，這個(gè)文件通常不會(huì)太大，可以放入內(nèi)存中，可以幫助快速定位到要查詢(xún)的 SSTable 文件，避免頻繁讀取。
另外一個(gè)經(jīng)常使用的方法是布隆解析器(Bloom filter)，布隆解析器是一個(gè)使用內(nèi)存判斷文件是否包含一個(gè)關(guān)鍵字的有效方法。對(duì)每一個(gè) SSTable 添加 Bloom Filter。
壓縮
SSTable 是可以啟用壓縮功能的，并且這種壓縮不是將整個(gè) SSTable 一起壓縮，而是根據(jù) locality 將數(shù)據(jù)分組，每個(gè)組分別壓縮，這樣的好處當(dāng)讀取數(shù)據(jù)的時(shí)候，我們不需要解壓縮整個(gè)文件而是解壓縮部分 Group 就可以讀取。
緩存
因?yàn)镾STable在寫(xiě)入磁盤(pán)后，除了Compaction之外，是不會(huì)變化的，所以我可以將Scan的Block進(jìn)行緩存，從而提高檢索的效率
合并

B+Tree VS LSM-Tree 數(shù)據(jù)拆分

LSM-Tree的設(shè)計(jì)思路是，將數(shù)據(jù)拆分為幾百M(fèi)大小的Segments（SSTable），并是順序?qū)懭搿?br />B+Tree則是將數(shù)據(jù)拆分為固定大小的Block或Page, 一般是4KB大小，和磁盤(pán)一個(gè)扇區(qū)的大小對(duì)應(yīng)，Page是讀寫(xiě)的最小單位。

更新

在數(shù)據(jù)的更新和刪除方面，B+Tree可以做到原地更新和刪除，這種方式對(duì)數(shù)據(jù)庫(kù)事務(wù)支持更加友好，因?yàn)橐粋€(gè)key只會(huì)出現(xiàn)一個(gè)Page頁(yè)里面。
LSM-Tree只能追加寫(xiě)，并且在L0層key的rang會(huì)重疊，所以對(duì)事務(wù)支持較弱，只能在Segment Compaction的時(shí)候進(jìn)行真正地更新和刪除。

讀寫(xiě)

LSM-Tree的優(yōu)點(diǎn)是支持高吞吐的寫(xiě)（可認(rèn)為是O（1）），這個(gè)特點(diǎn)在分布式系統(tǒng)上更為看重，當(dāng)然針對(duì)讀取普通的LSM-Tree結(jié)構(gòu)，讀取是O（N）的復(fù)雜度，在使用索引或者緩存優(yōu)化后的也可以達(dá)到O（logN）的復(fù)雜度。
而B(niǎo)+tree的優(yōu)點(diǎn)是支持高效的讀（穩(wěn)定的O（logN）），但是在大規(guī)模的寫(xiě)請(qǐng)求下（復(fù)雜度O(LogN)），效率會(huì)變得比較低，因?yàn)殡S著insert的操作，為了維護(hù)B+樹(shù)結(jié)構(gòu)，節(jié)點(diǎn)會(huì)不斷的分裂和合并。操作磁盤(pán)的隨機(jī)讀寫(xiě)概率會(huì)變大，故導(dǎo)致性能降低。

基于LSM-Tree分層存儲(chǔ)能夠做到寫(xiě)的高吞吐，帶來(lái)的副作用是整個(gè)系統(tǒng)必須頻繁的進(jìn)行compaction，寫(xiě)入量越大，Compaction的過(guò)程越頻繁。而compaction是一個(gè)compare & merge的過(guò)程，非常消耗CPU和存儲(chǔ)IO，在高吞吐的寫(xiě)入情形下，大量的compaction操作占用大量系統(tǒng)資源，必然帶來(lái)整個(gè)系統(tǒng)性能斷崖式下跌，對(duì)應(yīng)用系統(tǒng)產(chǎn)生巨大影響，當(dāng)然我們可以禁用自動(dòng)Major Compaction，在每天系統(tǒng)低峰期定期觸發(fā)合并，來(lái)避免這個(gè)問(wèn)題。

總結(jié)

LSM Tree 的思想非常實(shí)用，將隨機(jī)寫(xiě)轉(zhuǎn)換為順序?qū)憗?lái)大幅提高寫(xiě)入操作的性能，但是犧牲了部分讀的性能。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱(chēng)：LSMTree-創(chuàng)新互聯(lián)
分享地址：http://www.muchs.cn/article16/cdeddg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站收錄、域名注冊(cè)、網(wǎng)站維護(hù)、網(wǎng)站內(nèi)鏈、網(wǎng)站設(shè)計(jì)公司、定制網(wǎng)站

廣告

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