我們將深入探討日志結(jié)構(gòu)合并樹(shù)，也稱(chēng)為L(zhǎng)SM Tree：這是許多高度可擴(kuò)展的NoSQL分布式鍵值型數(shù)據(jù)庫(kù)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，例如Amazon的DynamoDB、Cassandra和ScyllaDB。這些數(shù)據(jù)庫(kù)的設(shè)計(jì)被認(rèn)為支持比傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)更高的寫(xiě)入速率。我們將看到LSM Tree如何使它們能夠?qū)崿F(xiàn)宣稱(chēng)的寫(xiě)入速度，并以及如何促進(jìn)讀取。

在開(kāi)始之前

首先，我們需要一些背景信息。典型的數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)由多個(gè)組件組成，每個(gè)組件負(fù)責(zé)處理數(shù)據(jù)存儲(chǔ)、檢索和管理的不同方面。

其中一個(gè)組件是存儲(chǔ)引擎，它負(fù)責(zé)提供可靠的接口，以從/向底層存儲(chǔ)設(shè)備高效讀寫(xiě)數(shù)據(jù)。

存儲(chǔ)引擎的性能在選擇數(shù)據(jù)庫(kù)時(shí)非常重要，因?yàn)樗亲罱咏谑褂玫拇鎯?chǔ)設(shè)備的組件。

用于實(shí)現(xiàn)存儲(chǔ)引擎的兩種流行數(shù)據(jù)結(jié)構(gòu)是B+樹(shù)和LSM樹(shù)。在本文中，我們將覆蓋LSM樹(shù)。

LSM Tree 深度解析

LSM Tree并不是一個(gè)完整的單一數(shù)據(jù)結(jié)構(gòu)，而是結(jié)合了多個(gè)數(shù)據(jù)結(jié)構(gòu)，利用存儲(chǔ)層次結(jié)構(gòu)中不同存儲(chǔ)設(shè)備的響應(yīng)時(shí)間。

由于是追加寫(xiě)入，它提供了高寫(xiě)入速率，同時(shí)通過(guò)在RAM中維護(hù)的索引仍然提供低成本的讀取。

與基于B+樹(shù)的存儲(chǔ)引擎相比，它執(zhí)行原地更新，但在LSM Tree中沒(méi)有原地更新，這有助于避免隨機(jī)I/O。在我們深入研究之前，讓我們?cè)敿?xì)討論在寫(xiě)入密集工作負(fù)載中使用基于B+樹(shù)的數(shù)據(jù)庫(kù)存儲(chǔ)引擎的缺點(diǎn)。

大多數(shù)傳統(tǒng)的關(guān)系型/SQL數(shù)據(jù)庫(kù)使用基于B+樹(shù)的存儲(chǔ)引擎。在這些數(shù)據(jù)庫(kù)中，每次寫(xiě)入都必須執(zhí)行不僅是記錄的請(qǐng)求寫(xiě)入，還必須執(zhí)行對(duì)B+樹(shù)不變式的任何所需的元數(shù)據(jù)更新，這涉及在B+樹(shù)結(jié)構(gòu)中移動(dòng)/拆分/合并節(jié)點(diǎn)。

解剖LSM Tree

LSM Trees凸顯了磁盤(pán)上的隨機(jī)I/O存在大量寫(xiě)入開(kāi)銷(xiāo)的問(wèn)題，而順序?qū)懭雱t更快，因?yàn)榇疟P(pán)寫(xiě)入頭緊挨著上一個(gè)記錄的位置，且旋轉(zhuǎn)和尋道延遲最小。

“Log-structured”這個(gè)術(shù)語(yǔ)意味著數(shù)據(jù)結(jié)構(gòu)像追加日志一樣被組織。

“merge”這個(gè)術(shù)語(yǔ)指的是用于管理結(jié)構(gòu)中數(shù)據(jù)的算法。其名稱(chēng)中的“tree”一詞來(lái)自于數(shù)據(jù)被組織成多個(gè)級(jí)別，類(lèi)似于典型計(jì)算機(jī)中存儲(chǔ)層次結(jié)構(gòu)中的設(shè)備，其中頂層設(shè)備包含較小的數(shù)據(jù)子集，訪問(wèn)速度更快，而較低級(jí)別包含較大的數(shù)據(jù)段，訪問(wèn)速度較慢。

在最基本的設(shè)置中，LSM Tree由兩個(gè)數(shù)據(jù)結(jié)構(gòu)組成，充分利用RAM和持久磁盤(pán)的優(yōu)勢(shì)：LSM樹(shù)被優(yōu)化用于快速寫(xiě)入。

1. Memtable

LSM樹(shù)的工作方式不同。寫(xiě)入在內(nèi)存中按到達(dá)的順序進(jìn)行批處理，存儲(chǔ)在稱(chēng)為Mem table的結(jié)構(gòu)中。Mem table按對(duì)象-鍵對(duì)進(jìn)行排序，通常實(shí)現(xiàn)為平衡二叉樹(shù)。

當(dāng)Mem table達(dá)到一定大小時(shí)，它將被刷新到磁盤(pán)作為不可變的有序字符串表。一個(gè)SS table以有序序列存儲(chǔ)鍵值對(duì)。這些寫(xiě)入都是順序I/O，在任何存儲(chǔ)介質(zhì)上都很快。

2.SS Tables

新的SS表成為L(zhǎng)SM樹(shù)的最新段。隨著更多數(shù)據(jù)的到來(lái)，越來(lái)越多的這些不可變SS表被創(chuàng)建并添加到LSM樹(shù)中，每個(gè)都代表傳入更改的小時(shí)間段。

由于SS表是不可變的，對(duì)現(xiàn)有對(duì)象鍵的更新不會(huì)覆蓋舊的SS表。相反，將在最新的SS表中添加新條目，這將取代舊的SS表中對(duì)象鍵的任何條目。

LSM Tree上的操作

1.刪除

刪除對(duì)象需要特殊處理，因?yàn)槲覀儫o(wú)法標(biāo)記SS表中的任何內(nèi)容為已刪除。

為執(zhí)行刪除操作，它會(huì)在對(duì)象鍵的最新SS表上添加一個(gè)稱(chēng)為墓碑的標(biāo)記。當(dāng)我們?cè)谧x取時(shí)遇到墓碑時(shí)，我們知道該對(duì)象已被刪除。是的，刪除會(huì)占用額外的空間。

2. 讀取

為了響應(yīng)讀取請(qǐng)求，我們首先嘗試在Mem table中查找鍵，然后在LSM樹(shù)中的最新訪問(wèn)表中查找，然后在下一個(gè)SS表中查找，依此類(lèi)推。由于SS表是有序的，查找可以有效進(jìn)行。

SS表的積累產(chǎn)生了兩個(gè)問(wèn)題。隨著SS表數(shù)量的增加，查找鍵將需要越來(lái)越長(zhǎng)的時(shí)間。隨著SS表的累積，隨著鍵的更新和墓碑的添加，舊條目變得越來(lái)越多。這些會(huì)占用寶貴的磁盤(pán)空間。

為了解決這些問(wèn)題，后臺(tái)運(yùn)行定期的合并和壓縮過(guò)程，以合并SS表并丟棄過(guò)時(shí)或已刪除的值。這可以回收磁盤(pán)空間并限制讀取時(shí)必須查找的SS表數(shù)量。由于SS表是有序的，因此這個(gè)合并和壓縮過(guò)程是簡(jiǎn)單而高效的。該方法類(lèi)似于歸并排序算法的合并階段。

3. 寫(xiě)入

LSM樹(shù)會(huì)在內(nèi)存中緩沖傳入的寫(xiě)入。當(dāng)緩沖區(qū)填滿(mǎn)時(shí)，我們對(duì)其進(jìn)行排序并將其刷新到磁盤(pán)作為不可變的SS表。

隨著更多的緩沖區(qū)刷新到磁盤(pán)，這會(huì)為讀取創(chuàng)建問(wèn)題，因?yàn)槊總€(gè)讀取都必須搜索這些SS表以執(zhí)行查找。

為了限制每個(gè)讀取時(shí)必須搜索的SS表數(shù)量，LSM樹(shù)會(huì)在后臺(tái)合并SS表并進(jìn)行壓縮。

4. 壓縮策略

讓我們更仔細(xì)地看看壓縮過(guò)程。當(dāng)合并SS表時(shí)，它們會(huì)被組織成級(jí)別。這是LSM樹(shù)名稱(chēng)中“樹(shù)”的部分發(fā)揮作用的地方。

有不同的策略來(lái)確定何時(shí)以及如何合并和壓縮SS表。有兩種廣泛的策略：大小分層壓縮和級(jí)別壓縮。大小分層壓縮針對(duì)寫(xiě)入吞吐量進(jìn)行了優(yōu)化，而級(jí)別壓縮則更多地針對(duì)讀取進(jìn)行了優(yōu)化。

壓縮可以使SS表數(shù)量保持在可管理的水平。SS表被組織成級(jí)別，每個(gè)級(jí)別的SS表隨著來(lái)自上一級(jí)別的SS表的出現(xiàn)而呈指數(shù)增長(zhǎng)。

壓縮會(huì)消耗大量I/O。錯(cuò)誤調(diào)整的壓縮可能會(huì)使系統(tǒng)餓死，并減慢讀取和寫(xiě)入速度。

LSM Tree 的增強(qiáng)

最后，讓我們了解一些生產(chǎn)系統(tǒng)中LSM樹(shù)的標(biāo)準(zhǔn)優(yōu)化。

為了查找鍵，它會(huì)在每個(gè)級(jí)別的SS表上執(zhí)行搜索。盡管在排序數(shù)據(jù)上搜索很快，但在所有這些SS表上進(jìn)行搜索會(huì)消耗大量I/O。

許多系統(tǒng)在內(nèi)存中保留一個(gè)摘要表，其中包含每個(gè)級(jí)別的每個(gè)磁盤(pán)塊的最小/最大范圍。這允許系統(tǒng)跳過(guò)那些鍵不在范圍內(nèi)的磁盤(pán)塊上的搜索，從而節(jié)省大量隨機(jī)I/O。

另一個(gè)可能昂貴的問(wèn)題是查找不存在的鍵。這將需要查找所有級(jí)別的所有合格塊。大多數(shù)系統(tǒng)在每個(gè)級(jí)別上保留了一個(gè)Bloom過(guò)濾器。

Bloom過(guò)濾器是一種空間高效的數(shù)據(jù)結(jié)構(gòu)，如果鍵不存在，則返回確定的“不存在”，如果鍵可能存在，則返回“可能存在”。這允許系統(tǒng)跳過(guò)一個(gè)級(jí)別，如果鍵在那里不存在，從而大大減少了需要的隨機(jī)I/O數(shù)量。

LSM Tree 的缺點(diǎn)

• LSM樹(shù)的主要缺點(diǎn)是壓縮的成本，它影響讀取和寫(xiě)入性能。由于涉及數(shù)據(jù)的壓縮/解壓縮、復(fù)制和比較，壓縮是LSM樹(shù)中資源占用最高的階段。
• 所選的壓縮策略必須試圖最小化讀取放大、寫(xiě)入放大和空間放大。
• LSM樹(shù)的另一個(gè)缺點(diǎn)是執(zhí)行讀取在最壞情況下會(huì)變慢。由于是追加方式，讀取必須在最低級(jí)別的SSTable中進(jìn)行搜索。這涉及到尋找的文件I/O，這會(huì)導(dǎo)致讀取變慢。