🔥 推薦一個高質量的Java LSM Tree開源項目！
https://github.com/brianxiadong/java-lsm-tree
java-lsm-tree 是一個從零實現的Log-Structured Merge Tree，專為高并發寫入場景設計。
核心亮點：
? 極致性能：寫入速度超過40萬ops/秒，完爆傳統B+樹
🏗? 完整架構：MemTable跳表 + SSTable + WAL + 布隆過濾器 + 多級壓縮
📚 深度教程：12章詳細教程，從基礎概念到生產優化，每行代碼都有注釋
🔒 并發安全：讀寫鎖機制，支持高并發場景
💾 數據可靠：WAL寫前日志確保崩潰恢復，零數據丟失
適合誰？

• 想深入理解LSM Tree原理的開發者
• 需要高寫入性能存儲引擎的項目
• 準備數據庫/存儲系統面試的同學
• 對分布式存儲感興趣的工程師
  ? 給個Star支持開源！

第4章：SSTable 磁盤存儲

什么是SSTable？

SSTable (Sorted String Table) 是LSM Tree中存儲在磁盤上的不可變有序文件。當MemTable達到大小閾值時，會將其內容刷盤生成SSTable文件。

SSTable 核心特性

1. 不可變性 (Immutability)

• 一旦寫入完成，SSTable文件永不修改
• 更新操作通過新的SSTable體現
• 刪除操作通過墓碑標記實現

2. 有序性 (Sorted)

• 所有鍵值對key的字典序排列
• 支持高效的二分查找
• 便于合并操作

3. 自包含性 (Self-contained)

• 包含布隆過濾器用于快速過濾
• 包含索引信息加速查找
• 包含元數據信息

關于布隆過濾器，大家先簡單認為用來判斷數據存在不存在即可，下一小節會詳細進行講解。

文件格式設計

我們的SSTable采用簡化的文件格式：

┌─────────────────────────────────────────────────────────────┐
│                    SSTable 文件結構                         │
├─────────────────────────────────────────────────────────────┤
│  [條目數量: 4字節]                                           │
├─────────────────────────────────────────────────────────────┤
│  [數據條目區域]                                             │
│    條目1: key|value|timestamp|deleted                       │
│    條目2: key|value|timestamp|deleted                       │
│    ...                                                      │
│    條目N: key|value|timestamp|deleted                       │
├─────────────────────────────────────────────────────────────┤
│  [布隆過濾器區域]                                           │
│    過濾器數據                                               │
└─────────────────────────────────────────────────────────────┘

SSTable 實現解析

讓我們深入分析SSTable的實現：

package com.brianxiadong.lsmtree;import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;/*** Sorted String Table (SSTable) 實現* 磁盤上的有序不可變文件*/
public class SSTable {// 文件路徑：SSTable存儲在磁盤上的位置private final String filePath;// 布隆過濾器：用于快速判斷鍵是否可能存在private final BloomFilter bloomFilter;// 創建時間：用于壓縮時的文件排序private final long creationTime;// 構造函數：從有序數據創建SSTablepublic SSTable(String filePath, List<KeyValue> sortedData) throws IOException {this.filePath = filePath;                           // 設置文件路徑this.creationTime = System.currentTimeMillis();    // 記錄創建時間// 創建布隆過濾器，估算條目數和假陽性率this.bloomFilter = new BloomFilter(sortedData.size(), 0.01);// 將數據持久化到磁盤文件writeToFile(sortedData);}/*** 從文件路徑加載已存在的SSTable*/public SSTable(String filePath) throws IOException {this.filePath = filePath;                                           // 設置文件路徑this.creationTime = Files.getLastModifiedTime(Paths.get(filePath)) // 獲取文件修改時間作為創建時間.toMillis();this.bloomFilter = new BloomFilter(1000, 0.01);                    // 創建臨時布隆過濾器// 重新構建布隆過濾器rebuildBloomFilter();}
}

代碼解釋: 這個SSTable類是LSM Tree持久化存儲的核心。它包含三個關鍵組件：文件路徑用于磁盤存儲，布隆過濾器用于快速過濾不存在的鍵，有序數據列表用于內存中的快速訪問。構造函數會自動創建布隆過濾器并將數據寫入磁盤。

核心方法分析

1. 寫入文件 (writeToFile)

/*** 將排序數據寫入文件*/
private void writeToFile(List<KeyValue> sortedData) throws IOException {// 使用DataOutputStream進行二進制寫入，性能更好try (DataOutputStream dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(filePath)))) {// 寫入條目數量dos.writeInt(sortedData.size());                    // 寫入整數類型的條目數// 寫入所有數據條目for (KeyValue kv : sortedData) {// 添加到布隆過濾器bloomFilter.add(kv.getKey());                   // 添加鍵到過濾器// 寫入數據：key, deleted, value(如果不是刪除), timestampdos.writeUTF(kv.getKey());                      // 寫入鍵（UTF-8編碼）dos.writeBoolean(kv.isDeleted());               // 寫入刪除標記if (!kv.isDeleted()) {                          // 如果不是刪除操作dos.writeUTF(kv.getValue());                // 寫入值}dos.writeLong(kv.getTimestamp());               // 寫入時間戳}}// try-with-resources自動關閉DataOutputStream
}

代碼解釋: 寫入過程采用順序寫入策略，這是磁盤I/O的最優模式。文件格式簡單明了：首先是條目數量，然后是所有數據條目，最后是布隆過濾器。使用管道符（|）分隔字段，便于解析。BufferedWriter提供緩沖以提高寫入性能。

寫入過程分析:

1. 順序寫入: 充分利用磁盤順序寫入的高性能
2. 文本格式: 便于調試和人工檢查
3. 完整性: 包含所有必要的元數據

2. 重建布隆過濾器 (rebuildBloomFilter)

/*** 重新構建布隆過濾器*/
private void rebuildBloomFilter() throws IOException {// 使用DataInputStream讀取二進制文件try (DataInputStream dis = new DataInputStream(new BufferedInputStream(new FileInputStream(filePath)))) {int totalEntries = dis.readInt();                   // 讀取條目總數// 遍歷所有條目，將鍵添加到布隆過濾器for (int i = 0; i < totalEntries; i++) {String key = dis.readUTF();                     // 讀取鍵boolean deleted = dis.readBoolean();            // 讀取刪除標記if (!deleted) {                                 // 如果不是刪除操作dis.readUTF();                              // 跳過value，只讀取鍵用于布隆過濾器}dis.readLong();                                 // 跳過timestamp// 添加到布隆過濾器bloomFilter.add(key);                           // 將鍵添加到過濾器}}// try-with-resources自動關閉DataInputStream
}

代碼解釋: 加載過程是寫入的逆向操作。先讀取條目數量以便預估內存需求，然后逐行解析數據條目，最后恢復布隆過濾器。如果布隆過濾器數據損壞，會自動重建，增強了系統的容錯性。解析使用split方法按管道符分割字段。

3. 查詢操作 (get)

/*** 查詢鍵值 - 簡化實現，順序搜索*/
public String get(String key) {// 首先檢查布隆過濾器if (!bloomFilter.mightContain(key)) {return null;                                        // 布隆過濾器說不存在，直接返回null}// 布隆過濾器說可能存在，讀取文件進行查找try (DataInputStream dis = new DataInputStream(new BufferedInputStream(new FileInputStream(filePath)))) {int totalEntries = dis.readInt();                   // 讀取條目總數// 順序搜索所有條目for (int i = 0; i < totalEntries; i++) {String currentKey = dis.readUTF();              // 讀取當前鍵boolean deleted = dis.readBoolean();            // 讀取刪除標記String value = null;                            // 初始化值if (!deleted) {                                 // 如果不是刪除操作value = dis.readUTF();                      // 讀取值}long timestamp = dis.readLong();                // 讀取時間戳// 檢查是否找到目標鍵if (currentKey.equals(key)) {return deleted ? null : value;              // 如果是刪除標記返回null，否則返回值}// 由于數據有序，如果當前鍵大于目標鍵，則不存在if (currentKey.compareTo(key) > 0) {break;                                      // 提前退出循環}}} catch (IOException e) {e.printStackTrace();                                // 打印異常信息}return null;                                            // 未找到，返回null
}

代碼解釋: 查詢操作采用兩階段策略：首先用布隆過濾器快速過濾不存在的鍵，這能避免大部分無效的磁盤訪問。如果布隆過濾器表示鍵可能存在，再進行文件掃描。由于數據有序存儲，當遇到比目標鍵大的鍵時可以提前退出。這種實現雖然是順序查找，但在實際應用中由于布隆過濾器的過濾效果，大多數查詢都不需要訪問磁盤。

4. 獲取所有條目 (getAllEntries)

/*** 獲取所有鍵值對（用于合并）*/
public List<KeyValue> getAllEntries() throws IOException {List<KeyValue> entries = new ArrayList<>();            // 創建結果列表// 讀取文件中的所有數據try (DataInputStream dis = new DataInputStream(new BufferedInputStream(new FileInputStream(filePath)))) {int totalEntries = dis.readInt();                   // 讀取條目總數// 讀取所有條目for (int i = 0; i < totalEntries; i++) {String key = dis.readUTF();                     // 讀取鍵boolean deleted = dis.readBoolean();            // 讀取刪除標記String value = null;                            // 初始化值if (!deleted) {                                 // 如果不是刪除操作value = dis.readUTF();                      // 讀取值}long timestamp = dis.readLong();                // 讀取時間戳// 創建KeyValue對象并添加到列表entries.add(new KeyValue(key, value, timestamp, deleted));}}return entries;                                         // 返回所有條目
}/*** 刪除SSTable文件*/
public void delete() throws IOException {Files.deleteIfExists(Paths.get(filePath));              // 刪除文件，如果存在的話
}// Getter方法
public String getFilePath() {return filePath;                                        // 返回文件路徑
}public long getCreationTime() {return creationTime;                                    // 返回創建時間
}

代碼解釋: getAllEntries方法用于壓縮過程中讀取SSTable的所有數據。它按順序讀取文件中的所有條目，重建KeyValue對象。delete方法提供文件清理功能，在壓縮完成后刪除舊的SSTable文件。Getter方法提供對文件路徑和創建時間的訪問，用于壓縮策略中的文件排序。

小結

SSTable是LSM Tree的持久化存儲層，具有以下關鍵特性：

1. 不可變性: 確保數據一致性和線程安全
2. 有序性: 支持高效查找和范圍查詢
3. 自包含: 包含布隆過濾器和索引信息
4. 優化: 多種性能優化技術

---

思考題

1. 為什么SSTable要設計為不可變的？
2. 布隆過濾器如何提升SSTable的查詢性能？
3. 如何在保持性能的同時減少SSTable的磁盤占用？