隨著應(yīng)用程序處理的數(shù)據(jù)量不斷增長(zhǎng)，擴(kuò)展存儲(chǔ)變得愈發(fā)具有挑戰(zhàn)性。每個(gè)數(shù)據(jù)庫(kù)系統(tǒng)都有自己的方案。為了從這些方案中做出正確的選擇，了解它們是至關(guān)重要的。

每個(gè)應(yīng)用程序在讀寫(xiě)負(fù)載平衡、一致性、延遲和訪問(wèn)模式方面各不相同。熟悉數(shù)據(jù)庫(kù)和底層存儲(chǔ)能幫助你進(jìn)行架構(gòu)決策、解釋系統(tǒng)行為、排除故障以及根據(jù)具體情況調(diào)優(yōu)。

[[265061]]

優(yōu)化一個(gè)系統(tǒng)不可能做到面面俱到。我們當(dāng)然希望有一個(gè)數(shù)據(jù)結(jié)構(gòu)既能保證***的讀寫(xiě)性能，又不需要任何存儲(chǔ)開(kāi)銷(xiāo)，但顯然，這是不存在的。

本文深入討論了大多數(shù)現(xiàn)代數(shù)據(jù)庫(kù)中使用的兩種存儲(chǔ)系統(tǒng)設(shè)計(jì) —— 讀優(yōu)化 B-Tree [1] 和寫(xiě)優(yōu)化 LSM(log-structured merge)-Tree [5] —— 并描述了它們的用例和優(yōu)缺權(quán)衡。

B-Tree

B-Tree 是一種流行的讀優(yōu)化索引數(shù)據(jù)結(jié)構(gòu)，是二叉樹(shù)的泛化。它有許多變種，并且被用于多種數(shù)據(jù)庫(kù)(包括 MySQL InnoDB [4]、PostgreSQL [7])甚至文件系統(tǒng)(HFS+ [8]、HTrees ext4 [9])。B-Tree 中的 B 代表原始數(shù)據(jù)結(jié)構(gòu)的作者 Bayer，或是他當(dāng)時(shí)就職的公司 Boeing。

在搜索二叉樹(shù)中，每個(gè)節(jié)點(diǎn)都有兩個(gè)孩子(稱(chēng)為左右孩子)。左子樹(shù)的節(jié)點(diǎn)值小于當(dāng)前節(jié)點(diǎn)值，右子樹(shù)反之。為了保持樹(shù)的深度最小，搜索二叉樹(shù)必須是平衡的：當(dāng)隨機(jī)順序的值被添加到樹(shù)中時(shí)，如果不加調(diào)整，終會(huì)導(dǎo)致樹(shù)的傾斜。

一種平衡二叉樹(shù)的方法是所謂的旋轉(zhuǎn)：重新排列節(jié)點(diǎn)，將較深子樹(shù)的父節(jié)點(diǎn)向下推到其子節(jié)點(diǎn)下方，并將該子節(jié)點(diǎn)拉上來(lái)，將其放在原父節(jié)點(diǎn)的位置。圖 1 是平衡二叉樹(shù)中的旋轉(zhuǎn)示例。在左側(cè)添加節(jié)點(diǎn) 2 后，二叉樹(shù)失去平衡。為了使該樹(shù)平衡，將其以節(jié)點(diǎn) 3 為軸旋轉(zhuǎn)(樹(shù)圍繞它旋轉(zhuǎn))。然后節(jié)點(diǎn) 5(旋轉(zhuǎn)前是根節(jié)點(diǎn)和節(jié)點(diǎn) 3 的父節(jié)點(diǎn))成為其子節(jié)點(diǎn)。旋轉(zhuǎn)完成后，左側(cè)子樹(shù)的深度減少 1，右側(cè)子樹(shù)的深度增加 1。樹(shù)的***深度已經(jīng)減小。

二叉樹(shù)是最有用的內(nèi)存數(shù)據(jù)結(jié)構(gòu)。然而由于平衡(保持所有子樹(shù)的深度最小)和低出度(每個(gè)節(jié)點(diǎn)最多兩個(gè)子節(jié)點(diǎn))，它們?cè)诖疟P(pán)上水土不服。B-Tree 允許每個(gè)節(jié)點(diǎn)存儲(chǔ)兩個(gè)以上的指針，并通過(guò)將節(jié)點(diǎn)大小與頁(yè)面大小(例如，4 KB)進(jìn)行匹配來(lái)與塊設(shè)備協(xié)同工作。今天的一些實(shí)現(xiàn)將使用更大的節(jié)點(diǎn)大小，跨越多個(gè)頁(yè)面。

B-Tree 有以下幾個(gè)性質(zhì)：

• 有序。這允許順序掃描并簡(jiǎn)化查找。

• 自平衡。在插入和刪除時(shí)不需要平衡樹(shù)：當(dāng) B-Tree 節(jié)點(diǎn)已滿(mǎn)時(shí)，它被分成兩部分，并且當(dāng)相鄰節(jié)點(diǎn)的利用率低于某個(gè)閾值時(shí)，合并這兩個(gè)節(jié)點(diǎn)。這也意味著各葉子節(jié)點(diǎn)與根節(jié)點(diǎn)的距離相等，并且在查找過(guò)程中定位的步數(shù)是相同的。

• 對(duì)數(shù)級(jí)查找時(shí)間復(fù)雜度。查找時(shí)間是非常重要的，這使得 B-Tree 成為數(shù)據(jù)庫(kù)索引的理想選擇。

• 易變。插入、更新、刪除(包括因此導(dǎo)致的拆分和合并)過(guò)程在磁盤(pán)上進(jìn)行。為了使就地更新成為可能，需要一定的空間開(kāi)銷(xiāo)。B-Tree 可以作為聚集索引，實(shí)際數(shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)上，也可以作為非聚集索引，稱(chēng)為一個(gè)堆文件。

本文討論的 B+Tree [3] 是一種經(jīng)常用于數(shù)據(jù)庫(kù)存儲(chǔ)的 B-Tree 現(xiàn)代變種。B+Tree 與原始 B-Tree [1] 的不同之處在于：(1)它采用額外鏈接的葉節(jié)點(diǎn)存儲(chǔ)值;(2)值不能存儲(chǔ)在內(nèi)部節(jié)點(diǎn)上。

剖析 B-Tree

我們先來(lái)仔細(xì)看看 B-Tree 的結(jié)構(gòu)，如圖 2 所示。B-Tree 的節(jié)點(diǎn)有幾種類(lèi)型：根節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)。根節(jié)點(diǎn)(頂部)是沒(méi)有雙親的節(jié)點(diǎn)(即，它不是任何節(jié)點(diǎn)的子節(jié)點(diǎn))。內(nèi)部節(jié)點(diǎn)(中間)有雙親和孩子節(jié)點(diǎn);他們將根節(jié)點(diǎn)和葉子節(jié)點(diǎn)連接起來(lái)。葉子節(jié)點(diǎn)(底部)持有數(shù)據(jù)并且沒(méi)有孩子節(jié)點(diǎn)。圖 2 描繪了分支因子為 4(4 個(gè)指針，內(nèi)部節(jié)點(diǎn)中有 3 個(gè)鍵，葉上有 4 個(gè)鍵/值對(duì))的 B-Tree。

B-Tree 的特性如下：

• 分支因子 —— 指向子節(jié)點(diǎn)的指針數(shù)(N)。除指針外，根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)還持有 N-1 個(gè)鍵。

• 利用率 —— 節(jié)點(diǎn)當(dāng)前持有的指向子節(jié)點(diǎn)的指針數(shù)量與可用***值之比。例如，若某樹(shù)分支因子是 N，且其中某節(jié)點(diǎn)當(dāng)前持有 N/2 個(gè)指針，則該節(jié)點(diǎn)利用率為 50%。

• 高度 —— B-Tree 的數(shù)量級(jí)，表示在查找過(guò)程中必須經(jīng)過(guò)多少指針。

樹(shù)中的每個(gè)非葉節(jié)點(diǎn)最多可持有 N 個(gè)鍵(索引條目)，這些鍵將樹(shù)分為 N+1 個(gè)子樹(shù)，這些子樹(shù)可以通過(guò)相應(yīng)的指針定位。項(xiàng) Ki 中的指針 i 指向某子樹(shù)，該子樹(shù)中包含所有 Ki-1 <= K目標(biāo) < Ki(其中 K 是一組鍵)的索引項(xiàng)。首尾指針是特殊的，它們指向的子樹(shù)中所有的項(xiàng)都小于等于最左子節(jié)點(diǎn)的 K0 或大于最右子節(jié)點(diǎn)的 KN-1。葉子節(jié)點(diǎn)同時(shí)持有其同級(jí)前后節(jié)點(diǎn)的指針，形成兄弟節(jié)點(diǎn)間的雙向鏈表。所有節(jié)點(diǎn)中的鍵總是有序的。

查找

進(jìn)行查找時(shí)，將從根節(jié)點(diǎn)開(kāi)始搜索，并經(jīng)過(guò)內(nèi)部節(jié)點(diǎn)遞歸向下到葉子節(jié)點(diǎn)層。在每層中，通過(guò)指向子節(jié)點(diǎn)的指針將搜索范圍縮小到某子樹(shù)(包含搜索目標(biāo)值的子樹(shù))。圖 3 展示了 B-Tree 的一次從根到葉的搜索過(guò)程，指針在兩個(gè)鍵之間，其中一個(gè)大于(或等于)搜索目標(biāo)，另一個(gè)小于搜索目標(biāo)。進(jìn)行點(diǎn)查詢(xún)時(shí)，搜索將在定位到葉子節(jié)點(diǎn)后完成。進(jìn)行范圍掃描時(shí)，遍歷所找到的葉子節(jié)點(diǎn)的鍵和值，然后遍歷范圍內(nèi)的兄弟葉子節(jié)點(diǎn)。

在復(fù)雜度方面，B-Tree 保證查詢(xún)的時(shí)間復(fù)雜度為 log(n)，因?yàn)椴檎乙粋€(gè)節(jié)點(diǎn)中的鍵使用二分查找，如圖 4 所示。二進(jìn)制搜索可以通俗的解釋為在字典中查找以某字母開(kāi)頭的單詞，字典中所有單詞都按字母順序排序。首先你翻開(kāi)正好在字典中間的一頁(yè)。如果要查找的單詞字母順序小于(在前面)當(dāng)前頁(yè)，你繼續(xù)在字典的左半邊查找;否則就繼續(xù)在右半邊查找。你繼續(xù)像這樣將剩余的頁(yè)碼范圍分為一半，選擇一邊，直到找到期望的字母。每一步都將搜索范圍減半，因此查找的時(shí)間復(fù)雜度為對(duì)數(shù)級(jí)。 B-Tree 節(jié)點(diǎn)上的鍵是有序的，且使用二分查找算法進(jìn)行匹配，因此 B-Tree 的搜索復(fù)雜度是對(duì)數(shù)級(jí)的。這也說(shuō)明了保持樹(shù)的高利用率和統(tǒng)一訪問(wèn)的重要性。

插入、更新、刪除

進(jìn)行插入時(shí)，***步是定位目標(biāo)葉子節(jié)點(diǎn)。此過(guò)程使用前序搜索算法。在定位目標(biāo)葉子節(jié)點(diǎn)后，鍵和值將被添加至該節(jié)點(diǎn)。如果該節(jié)點(diǎn)沒(méi)有足夠的可用空間，這種情況稱(chēng)為溢出，則將葉子節(jié)點(diǎn)分割成兩部分。這是通過(guò)分配一個(gè)新的葉子節(jié)點(diǎn)，將一半元素移動(dòng)到新節(jié)點(diǎn)并將一個(gè)指向這個(gè)新節(jié)點(diǎn)的指針添加到父節(jié)點(diǎn)來(lái)完成的。如果父節(jié)點(diǎn)沒(méi)有足夠的空間，則也會(huì)在父節(jié)點(diǎn)上進(jìn)行分割。操作一直持續(xù)到根節(jié)點(diǎn)為止。當(dāng)根節(jié)點(diǎn)溢出時(shí)，其內(nèi)容在新分配的節(jié)點(diǎn)之間被分割，根節(jié)點(diǎn)本身被覆蓋以避免重定位。這也意味著樹(shù)(及其高度)總是通過(guò)分裂根節(jié)點(diǎn)而增長(zhǎng)。

LSM-Tree

結(jié)構(gòu)化日志合并樹(shù)是一個(gè)不可變的基于磁盤(pán)的寫(xiě)優(yōu)化數(shù)據(jù)結(jié)構(gòu)。它適用于寫(xiě)入比查詢(xún)操作更頻繁的場(chǎng)景。LSM-Tree 已經(jīng)獲得了更多的關(guān)注，因?yàn)樗梢员苊怆S機(jī)插入，更新和刪除。

剖析 LSM-Tree

為了允許連續(xù)寫(xiě)入，LSM-Tree 在內(nèi)存中的表(通常使用支持查找的時(shí)間復(fù)雜度為對(duì)數(shù)級(jí)的數(shù)據(jù)結(jié)構(gòu)，例如二叉搜索樹(shù)或跳躍表)中批量寫(xiě)入和更新，當(dāng)其大小達(dá)到閾值時(shí)將它寫(xiě)在磁盤(pán)上(這個(gè)操作稱(chēng)為刷新)。檢索數(shù)據(jù)時(shí)需要搜索樹(shù)所有磁盤(pán)中的部分，檢查內(nèi)存中的表，合并它們的內(nèi)容，然后再返回結(jié)果。圖 5 展示了 LSM-Tree 的結(jié)構(gòu)：用于寫(xiě)入的基于內(nèi)存的表。只要內(nèi)存表體積達(dá)到一定程度，內(nèi)存表就會(huì)被寫(xiě)入磁盤(pán)。進(jìn)行讀取時(shí)，同時(shí)讀取磁盤(pán)和內(nèi)存表，通過(guò)一個(gè)合并操作來(lái)整合數(shù)據(jù)。

有序串行表

因?yàn)?SSTable(有序串行表)的簡(jiǎn)單性(易于寫(xiě)入，搜索和讀取)與合并性能(合并期間，掃描源 SSTable，合并結(jié)果的寫(xiě)入是順序的)，多數(shù)現(xiàn)代的 LSM-Tree 實(shí)現(xiàn)(例如 RocksDB 和 Apache Cassandra)都選用 SSTable 作為硬盤(pán)表。

SSTable 是一種基于硬盤(pán)的有序不可變的數(shù)據(jù)結(jié)構(gòu)。從結(jié)構(gòu)上來(lái)看，SSTable 可以分為兩部分：數(shù)據(jù)塊和索引塊，如圖 6 所示。數(shù)據(jù)塊包含以鍵為順序?qū)懭氲奈ㄒ绘I值對(duì)。索引塊包含映射到數(shù)據(jù)塊指針的鍵，指針指向?qū)嶋H記錄的位置。為了快速搜索，索引一般使用優(yōu)化的結(jié)構(gòu)實(shí)現(xiàn)，例如 B-Tree 或用于點(diǎn)查詢(xún)的哈希表。SSTable 中的每一個(gè)值都有一個(gè)時(shí)間戳與之對(duì)應(yīng)。時(shí)間戳記錄了插入、更新(這兩者一般不做區(qū)分)和刪除時(shí)間。

SSTable 具有以下優(yōu)點(diǎn)：

• 通過(guò)查詢(xún)主鍵索引可以實(shí)現(xiàn)快速的點(diǎn)查詢(xún)(例如，通過(guò)鍵尋找值)。

• 只需要順序讀取數(shù)據(jù)塊上的鍵值對(duì)就可以實(shí)現(xiàn)掃描(例如，遍歷制定范圍內(nèi)的鍵值對(duì))。

SSTable 代表一段時(shí)間內(nèi)所有數(shù)據(jù)庫(kù)操作的快照，因?yàn)?SSTable 是通過(guò)對(duì)內(nèi)存表的刷新操作創(chuàng)建的，該表充當(dāng)此時(shí)段內(nèi)對(duì)數(shù)據(jù)庫(kù)狀態(tài)的緩沖區(qū)。

查詢(xún)

檢索數(shù)據(jù)需要搜索硬盤(pán)上的所有 SSTable，檢查內(nèi)存表，并且合并它們的內(nèi)容后返回結(jié)果。要搜索的數(shù)據(jù)可以存儲(chǔ)在多個(gè) SSTable 中，因此合并步驟是必須的。

合并步驟也是確保刪除和更新正常工作所必需的。在 LSM-Tree 中，通過(guò)插入占位符(通常稱(chēng)為墓碑)來(lái)指定哪個(gè)鍵被標(biāo)記為刪除。同樣的，更新操作只是提交一個(gè)帶較晚時(shí)間戳的記錄。在讀取期間，被標(biāo)記刪除的記錄被跳過(guò)，不會(huì)返回給客戶(hù)端。更新操作與之類(lèi)似：在具有相同鍵的兩個(gè)記錄中，只返回具有較晚時(shí)間戳的記錄。圖 7 展示了一次合并操作，用于對(duì)在不同表中存儲(chǔ)的同一個(gè)鍵的數(shù)據(jù)進(jìn)行整合：如圖，Alex 記錄中時(shí)間戳是 100，隨后更新了新的電話(huà)，時(shí)間戳為 200;John 記錄被刪除。另外兩項(xiàng)沒(méi)有改變，因?yàn)樗鼈儧](méi)有被覆蓋。

為了減少搜索 SSTable ，防止為了查找某個(gè)鍵而搜索每個(gè) SSTable，許多存儲(chǔ)系統(tǒng)采用一個(gè)被稱(chēng)為布隆過(guò)濾器 [10] 的數(shù)據(jù)結(jié)構(gòu)。這是一個(gè)概率數(shù)據(jù)結(jié)構(gòu)，可用于測(cè)試某個(gè)元素是否屬于某集合。它有可能產(chǎn)生錯(cuò)誤的肯定(即，判斷元素是集合的成員，但實(shí)際上并不是)，但不能產(chǎn)生錯(cuò)誤的否定(即，如果返回否定結(jié)果，則元素一定不是集合的成員)。換句話(huà)說(shuō)，布隆過(guò)濾器用于判斷鍵“可能在 SSTable 中”或“絕對(duì)不在 SSTable 中”。在搜索過(guò)程中，將會(huì)跳過(guò)布隆過(guò)濾器返回否定結(jié)果的 SSTable。

LSM-Tree 的維護(hù)

由于 SSTable 是不可變的，因此它們會(huì)按順序?qū)懭?，并且不存在用于修改的預(yù)留空白空間。這就意味著插入、更新或刪除操作將需要重寫(xiě)整個(gè)文件。所有修改數(shù)據(jù)庫(kù)狀態(tài)的操作都在內(nèi)存表中“批處理”。隨著時(shí)間的推移，磁盤(pán)表的數(shù)量將增加(同一個(gè)鍵的數(shù)據(jù)位于幾個(gè)不同文件，同一記錄有多個(gè)不同的版本，被刪除的冗余記錄)，讀取操作的開(kāi)銷(xiāo)將變得越來(lái)越大。

為了降低讀取開(kāi)銷(xiāo)，整合被刪除記錄占用的空間并減少磁盤(pán)表的數(shù)量，LSM-Tree 需要一個(gè)壓縮操作，從磁盤(pán)讀取完整的 SSTable 并合并它們。由于 SSTable 是以鍵排序的，因此其壓縮工作和歸并排序類(lèi)似，是非常高效的操作：從多個(gè)源有序序列中讀取記錄，進(jìn)行合并后的輸出馬上追加到結(jié)果文件中，則結(jié)果文件也是有序的。歸并排序的一個(gè)優(yōu)點(diǎn)是，即使合并內(nèi)存吃不消的大文件，它依舊可以高效地工作。結(jié)果表保留了原始 SSTable 的順序。

在此過(guò)程中，被合并的 SSTable 被丟棄并替換為其“壓縮”后的版本，如圖 8 所示。壓縮多個(gè) SSTable 并將它們合并為一個(gè)。某些數(shù)據(jù)庫(kù)系統(tǒng)在邏輯層面上按大小把不同的表分為不同級(jí)別，分組到相同的“級(jí)別”，并在特定級(jí)別的表足夠多時(shí)開(kāi)始合并操作。壓縮后，SSTable 的數(shù)量減少，提高查詢(xún)效率。

原子性與持久性

為了減少 I/O 操作并使它們順序執(zhí)行，無(wú)論是 B-Tree 還是 LSM-Tree 都在實(shí)際更新之前，先在內(nèi)存中進(jìn)行批量操作。這意味著，在故障情況時(shí)，數(shù)據(jù)完整性、原子性(將一系列操作賦予原子性，將它們視為一個(gè)操作，要么全部執(zhí)行要么全不執(zhí)行)、持久性(當(dāng)進(jìn)程崩潰或電源失效時(shí)，可以確保數(shù)據(jù)已經(jīng)到達(dá)持久性存儲(chǔ)設(shè)備)得不到保證。

為了解決這個(gè)問(wèn)題，大多數(shù)現(xiàn)代存儲(chǔ)系統(tǒng)采用 WAL(預(yù)寫(xiě)日志)。WAL 的核心思想是，所有數(shù)據(jù)庫(kù)狀態(tài)改變都先持久化進(jìn)硬盤(pán)中的只追加日志中。如果進(jìn)程在工作中崩潰，將會(huì)重映日志以確保沒(méi)有數(shù)據(jù)丟失且所有更改都滿(mǎn)足原子性。

在 B-Tree 中，使用 WAL 可以理解為僅在寫(xiě)入操作被記錄后才將其寫(xiě)入數(shù)據(jù)文件。通常，B-Tree 存儲(chǔ)系統(tǒng)的日志尺寸相對(duì)較?。褐灰獙⒏膽?yīng)用于持久存儲(chǔ)，它們就可以被棄用。WAL 還可以作為運(yùn)行時(shí)操作的備份：任何未應(yīng)用于數(shù)據(jù)頁(yè)的更改都可以根據(jù)日志記錄重做。

在 LSM-Tree 中，WAL 用于保存處于內(nèi)存表但尚未完全刷新到磁盤(pán)上的更改。只要內(nèi)存表被刷新完畢并置換，便可以在新創(chuàng)建的 SSTable 中進(jìn)行讀取操作，則 WAL 中從內(nèi)存表刷新到硬盤(pán)上的那部分更改就可以丟棄了。

總結(jié)

B-Tree 和 LSM-Tree 數(shù)據(jù)結(jié)構(gòu)***的差異之一是它們優(yōu)化的目的以及優(yōu)化的效果。

我們來(lái)對(duì)比一下 B-Tree 和 LSM-Tree 之間的特性。總的來(lái)說(shuō)，B-Tree 具有以下特性：

• 它是可變的，它允許通過(guò)一些空間開(kāi)銷(xiāo)和更多的寫(xiě)入路徑來(lái)進(jìn)行就地更新，因而它不需要文件重寫(xiě)或多源合并。

• 它是讀優(yōu)化的，這意味著它不需要從多個(gè)源數(shù)據(jù)中讀取(也不需要合并)，因而簡(jiǎn)化了讀取路徑。

• 寫(xiě)操作可能引起級(jí)聯(lián)節(jié)點(diǎn)分裂，這使得寫(xiě)操作開(kāi)銷(xiāo)較高。

• 它針對(duì)分頁(yè)環(huán)境(塊存儲(chǔ))進(jìn)行了優(yōu)化，杜絕了字節(jié)定位操作。

• 碎片化, 由頻繁更新造成的碎片化可能需要額外的維護(hù)和塊重寫(xiě)。然而對(duì) B-Tree 的維護(hù)一般要比 LSM-Tree 要少。

• 并發(fā)訪問(wèn)讀寫(xiě)隔離，這涉及鎖存器與鎖鏈。

LSM-Tree 具有以下特性：

• 它是不可變的。SSTable 一旦被寫(xiě)入硬盤(pán)就不會(huì)再改變。壓縮操作被用于整合占用空間，刪除條目，合并在不同數(shù)據(jù)文件中的同鍵數(shù)據(jù)。作為壓縮操作的一部分，在成功合并后，源 SSTable 將被棄用并刪除。這種不可變性給我們帶來(lái)了另一個(gè)有用的特性，刷新后的表可以被并發(fā)訪問(wèn)。

• 它是寫(xiě)優(yōu)化的，這意味著寫(xiě)入操作將進(jìn)入緩沖，隨后順序刷新到硬盤(pán)上，可能支持基于硬盤(pán)的空間局部性。

• 讀取操作可能需要訪問(wèn)多個(gè)數(shù)據(jù)源，因?yàn)樵诓煌瑫r(shí)間寫(xiě)入的同一個(gè)鍵的數(shù)據(jù)有可能位于不同的數(shù)據(jù)文件中。必須經(jīng)過(guò)合并過(guò)程才能將記錄返回給客戶(hù)端。

• 需要維護(hù) / 壓縮，因?yàn)榫彌_中的寫(xiě)入操作被刷新到硬盤(pán)上。

評(píng)估存儲(chǔ)系統(tǒng)

開(kāi)發(fā)存儲(chǔ)系統(tǒng)總要面對(duì)類(lèi)似的挑戰(zhàn)，考慮類(lèi)似的因素。決定優(yōu)化方向會(huì)對(duì)結(jié)果產(chǎn)生很大影響。你可以在寫(xiě)入過(guò)程中花費(fèi)更多時(shí)間來(lái)布局結(jié)構(gòu)以實(shí)現(xiàn)更高效的讀取，為就地更新預(yù)留空間，也可以緩沖數(shù)據(jù)確保順序?qū)懭胍蕴岣邔?xiě)入速度。但是，一次完成這一切是不可能的。理想中的存儲(chǔ)系統(tǒng)應(yīng)該具有***的讀取成本，***的寫(xiě)入成本，并且沒(méi)有額外開(kāi)銷(xiāo)。但實(shí)際上，數(shù)據(jù)結(jié)構(gòu)只能在多個(gè)因素之間權(quán)衡。理解這些取舍是重要的。

來(lái)自哈佛 DASlab(數(shù)據(jù)系統(tǒng)實(shí)驗(yàn)室)的研究人員總結(jié)了數(shù)據(jù)庫(kù)系統(tǒng)優(yōu)化方向的關(guān)鍵三點(diǎn)：讀取開(kāi)銷(xiāo)、更新開(kāi)銷(xiāo)和內(nèi)存開(kāi)銷(xiāo)(或簡(jiǎn)稱(chēng)為 RUM)。對(duì)于數(shù)據(jù)結(jié)構(gòu)、訪問(wèn)方法、甚至適用于某些工作負(fù)載的選擇應(yīng)該了解哪些參數(shù)對(duì)你的用例最為重要，因?yàn)樗惴ㄊ轻槍?duì)特定用例量身定制的。

RUM 假說(shuō) [2] 為上述的兩種開(kāi)銷(xiāo)設(shè)置了上限，同時(shí)為第三種設(shè)置了下限。例如，B-Tree 以提高寫(xiě)入開(kāi)銷(xiāo)、預(yù)留空間(同時(shí)也造成了內(nèi)存開(kāi)銷(xiāo))為代價(jià)進(jìn)行讀優(yōu)化。LSM-Tree 以讀取時(shí)必須進(jìn)行多硬盤(pán)表訪問(wèn)的高讀取開(kāi)銷(xiāo)換取低寫(xiě)入開(kāi)銷(xiāo)。在處于競(jìng)爭(zhēng)三角形的三個(gè)參數(shù)中，一方面的改進(jìn)可能就意味著另一方面的讓步。圖 9 對(duì) RUM 假說(shuō)進(jìn)行了說(shuō)明。

B-Tree 優(yōu)化讀取性能：索引的布局方式可以最小化遍歷樹(shù)的磁盤(pán)訪問(wèn)需求。通過(guò)訪問(wèn)一個(gè)索引文件就可以定位數(shù)據(jù)。這是通過(guò)持續(xù)更新索引文件來(lái)實(shí)現(xiàn)的，但這也增加了由于節(jié)點(diǎn)拆分和合并，重定位以及碎片、不平衡相關(guān)的維護(hù)造成的額外寫(xiě)入開(kāi)銷(xiāo)。為了平穩(wěn)更新成本并減少分割次數(shù)，B-Tree 在所有級(jí)別的節(jié)點(diǎn)上都預(yù)留有額外的空間。這有助于在節(jié)點(diǎn)飽和之前延遲寫(xiě)入開(kāi)銷(xiāo)的增長(zhǎng)。簡(jiǎn)而言之，B-Tree 犧牲更新和內(nèi)存性能以獲得更好的讀取性能。

LSM-Tree 優(yōu)化寫(xiě)入性能。無(wú)論是更新還是刪除都需要在磁盤(pán)上定位數(shù)據(jù)(B-Tree 也一樣)，并且它通過(guò)在內(nèi)存表中緩存所有插入，更新和刪除操作來(lái)保證順序?qū)懭搿＿@是以較高的維護(hù)成本和壓縮需求(這是唯一的緩解不斷增長(zhǎng)的讀取開(kāi)銷(xiāo)和減少磁盤(pán)表的數(shù)量的方式)和更高的讀取成本(因?yàn)閿?shù)據(jù)必須從多個(gè)源讀取并合并)為代價(jià)的。同時(shí)，LSM-Tree 通過(guò)不保留任何預(yù)留空間來(lái)減少內(nèi)存開(kāi)銷(xiāo)(不同于 B-Tree 節(jié)點(diǎn)，其平均利用率為 70%，包含就地更新所需的開(kāi)銷(xiāo))，因?yàn)楦叩睦寐屎妥罱K文件的不變性，LSM-Tree 支持塊壓縮。簡(jiǎn)而言之，LSM-Tree 犧牲讀取性能，提高維護(hù)成本來(lái)獲得更好的寫(xiě)入性能和更低的內(nèi)存占用。

有的數(shù)據(jù)結(jié)構(gòu)可針對(duì)每個(gè)期望的屬性進(jìn)行優(yōu)化。使用自適應(yīng)數(shù)據(jù)結(jié)構(gòu)可以以更高維護(hù)成本獲得更好的讀取性能。添加有助于遍歷的元數(shù)據(jù)(如分散層疊)將會(huì)影響寫(xiě)入時(shí)間并占用更多空間，但可以提高讀取性能。使用壓縮優(yōu)化內(nèi)存使用率(例如，Gorilla 壓縮 [6] 、delta 編碼等諸多算法)會(huì)增加一些開(kāi)銷(xiāo)，用于在寫(xiě)入時(shí)壓縮數(shù)據(jù)并在讀取時(shí)解壓縮數(shù)據(jù)。有時(shí)候，你可以犧牲功能來(lái)提高效率。例如，堆文件和散列索引由于文件格式簡(jiǎn)單，可以保證很好的性能和較小的空間開(kāi)銷(xiāo)，而作為代價(jià)，它們不支持除點(diǎn)查詢(xún)以外的其他功能。你還可以通過(guò)使用近似數(shù)據(jù)結(jié)構(gòu)(如布隆過(guò)濾器、HyperLogLog、Count-Min sketch 等)來(lái)為了空間與效率犧牲精度。

三種可變參數(shù) —— 讀取，更新和內(nèi)存開(kāi)銷(xiāo) —— 可以幫助你評(píng)估數(shù)據(jù)庫(kù)并深入了解最適合的工作負(fù)載。它們都非常直觀，將存儲(chǔ)系統(tǒng)按其分類(lèi)很容易，猜測(cè)它是如何執(zhí)行的，然后通過(guò)大量測(cè)試驗(yàn)證你的假設(shè)。

當(dāng)然，評(píng)估存儲(chǔ)系統(tǒng)時(shí)還有一些其他重要因素需要考慮，例如維護(hù)開(kāi)銷(xiāo)，易用性，系統(tǒng)要求，頻繁增刪的適應(yīng)性，訪問(wèn)模式等。RUM 假說(shuō)只是幫助發(fā)展直觀感覺(jué)并提供初始方向的一條經(jīng)驗(yàn)法則。了解你的工作部件是構(gòu)建可擴(kuò)展后端的***步。

一些因素可能因?qū)嵤┒?，甚至兩個(gè)使用類(lèi)似存儲(chǔ)設(shè)計(jì)原則的數(shù)據(jù)庫(kù)可能會(huì)有不同表現(xiàn)。數(shù)據(jù)庫(kù)是包含許多可插拔模塊的復(fù)雜系統(tǒng)，是許多應(yīng)用程序的重要組成部分。這些信息將幫助你窺探數(shù)據(jù)庫(kù)的底層，并且了解底層數(shù)據(jù)結(jié)構(gòu)和其內(nèi)部行為之間的差異，從而決定哪個(gè)是最適合你的。