知識庫 / Spring RSS 訂閱

1. 概述

現代數據庫系統通過利用複雜的存儲引擎，來保證可靠性、一致性、高吞吐量等一系列能力。

在本教程中，我們將深入研究 Apache Cassandra 使用的存儲引擎的內部機制，該引擎專門為高寫入負載工作負載設計，同時還能保持良好的讀取性能。

2. 級聯日誌合併樹 (LSMT)

Apache Cassandra 利用基於兩級聯日誌合併樹的數據結構進行存儲。 在高層級上，這種 LSM 樹包含兩個類似樹狀的組件：一個內存緩存組件 (C₀) 和一個磁盤組件 (C₁)：

直接從內存讀取和寫入數據通常比從磁盤更快。 因此，出於設計目的，所有請求首先命中 C₀，然後再訪問 C₁。 此外，一個 同步操作會定期將 C0 中的數據持久化到 C1 中。 從而，它通過減少 I/O 操作， 有效地利用網絡帶寬。

在後續部分，我們將更深入地瞭解 Apache Cassandra 中兩級 LSM 樹的 C₀ 和 C₁ 數據結構，通常被稱為 MemTable 和 SSTable。

3. MemTable

正如其名稱所示，MemTable 是一種駐留在內存中的數據結構，例如具有自平衡二叉搜索樹特性的紅黑樹。因此，所有讀寫操作，即搜索、插入、更新和刪除，都可以實現 O(log n) 的時間複雜度。

作為一種內存中的可變數據結構，MemTable 使所有寫入操作具有順序性，並允許進行快速寫入操作。 此外，由於物理內存的典型限制，如有限容量和易變性，我們需要將 MemTable 中的數據持久化到磁盤：

當 MemTable 的大小達到一個閾值時，所有讀寫請求都會切換到新的 MemTable，而舊的 MemTable 在將其刷新到磁盤後會被丟棄。

到目前為止，一切順利！我們可以高效地處理大量的寫入操作。但是，如果節點在刷新操作之前崩潰呢？答案很簡單——我們將丟失尚未刷新到磁盤的數據。

在下一部分，我們將看到 Apache Cassandra 如何通過使用 Write-Ahead Logs (WAL) 的概念來解決這個問題。

4. 提交日誌 (Commit Log)

Apache Cassandra 延遲持久化操作，即從內存將數據寫入磁盤。因此，意外節點或進程崩潰可能導致數據丟失。

持久性是任何現代數據庫系統都必須具備的能力，Apache Cassandra也不例外。它通過確保所有寫入操作都寫入名為“提交日誌”的只追加文件來保證持久性。 隨後，它使用 MemTable 作為寫入路徑中的寫回緩存：

請注意，只追加操作速度快，因為它們避免了對磁盤上的隨機尋道。因此，提交日誌在不影響寫入性能的情況下，提供了持久性能力。此外，Apache Cassandra 僅在崩潰恢復場景中引用提交日誌，而常規的讀取請求不會訪問提交日誌。

5. SSTable

排序字符串表 (SSTable) 是 Apache Cassandra 存儲引擎中使用的 LSM 樹的磁盤駐留組件。它得名於 Google BigTable 數據庫中首次使用的類似數據結構，表明數據以排序格式可訪問。通常，每個從 MemTable 中生成的 flush 操作都會生成 SSTable 中的一個不可變段。

讓我們嘗試可視化一個包含動物數量的各種數據（例如，動物園中飼養的動物數量）的 SSTable 的樣子：

雖然段條按照鍵進行排序，但相同的鍵可能存在於多個段條中。因此，如果我們必須查找特定鍵，則需要從最新的段條開始搜索，並在找到結果時立即返回結果。

採用這種策略，最近寫入的鍵的讀取操作將非常快速。但是，在最壞的情況下，算法的執行時間複雜度為 O(N*log(K))，其中 N 是段條的總數，K 是段條的大小。由於 K 是一個常數，因此我們可以説總體時間複雜度為 O(N)，這效率不高。

在接下來的幾個部分中，我們將學習 Apache Cassandra 如何優化對 SSTable 的讀取操作。

6. 稀疏索引

Apache Cassandra 維護一個稀疏索引，以限制其在查找鍵時需要掃描的段數。

每個稀疏索引條目包含一個段的首成員，以及其在磁盤上的頁偏移位置。此外，索引以內存中的 B-Tree 數據結構的形式維護，以便我們可以在 O(log(K)) 時間複雜度內搜索索引中的偏移量。

假設我們要搜索鍵“beer”。我們首先會搜索所有在稀疏索引中出現在“beer”之前的所有鍵。之後，使用偏移值，我們只會在有限數量的段中進行查找。在這種情況下，我們將查找第四個段，該段的第一個鍵是“alligator”：

另一方面，如果我們搜索一個不存在的鍵，例如“kangaroo”，我們必須徒勞地遍歷所有段。因此，我們意識到使用稀疏索引可以最大限度地優化搜索。

此外，我們還應注意，SSTable 允許相同的鍵在不同的段中存在。因此，隨着時間的推移，相同的鍵將發生越來越多的更新，從而在稀疏索引中也會產生重複的鍵。

在後續部分中，我們將學習如何使用布隆過濾器和壓縮來解決 Apache Cassandra 解決這兩個問題的辦法。

7. Bloom 過濾器

Apache Cassandra 通過使用一種概率數據結構——Bloom 過濾器來優化讀取查詢。簡單來説，它通過首先使用 Bloom 過濾器進行鍵的成員資格檢查來優化搜索。

因此，通過為每個 SSTable 的片段附加 Bloom 過濾器，我們可以獲得顯著的讀取查詢優化，尤其是在片段中不存在的鍵時：

由於 Bloom 過濾器是概率數據結構，因此即使對於缺失的鍵，我們也可能收到“Maybe” (可能) 的響應。但是，如果收到“No” (否) 的響應，我們可以確信該鍵確實不存在。

儘管它們存在侷限性，我們可以通過為它們分配更大的存儲空間來提高 Bloom 過濾器的準確性。

8. 數據壓縮（Compaction）

儘管使用了布隆過濾器和稀疏索引，但讀取查詢的性能會隨着時間的推移而下降。這是因為每個 MemTable 刷新操作後，包含不同版本密鑰的片段數量很可能會增加。

為了解決這個問題，Apache Cassandra 運行一個後台的壓縮進程，它將較小的排序片段合併為較大的片段，同時僅保留每個密鑰的最新值。因此，壓縮進程同時提供更快讀取和更少存儲空間的兩大益處。

讓我們看看在現有 SSTable 上一次壓縮運行的情況：

我們注意到壓縮操作通過僅保留最新版本來回收了一些空間。例如，像“elephant”和“tiger”這樣的舊版本密鑰不再存在，從而釋放了磁盤空間。

此外，壓縮進程還允許硬刪除密鑰。雖然刪除操作會標記密鑰為墓碑，但實際刪除操作會延遲到壓縮期間。

9. 結論

在本文中，我們深入研究了 Apache Cassandra 的存儲引擎內部組件。在此過程中，我們學習了諸如 LSM 樹、MemTable 和 SSTable 等高級數據結構概念。此外，我們還學習了使用預寫入日誌、布隆過濾器、稀疏索引和合並等優化技術。