從零手寫Java版本的LSM Tree （八）：LSM Tree 主程序實現

🔥 推薦一個高質量的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支持開源！

第8章：LSM Tree 主程序實現

核心架構設計

LSM Tree主程序是整個存儲引擎的控制中心，它協調MemTable、SSTable、WAL和壓縮策略等組件的工作。

主要組件結構

package com.brianxiadong.lsmtree;import java.io.File;
import java.io.IOException;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;/*** LSM Tree 主要實現類* 整合MemTable、SSTable和壓縮策略*/
public class LSMTree implements AutoCloseable {private final String dataDir;                        // 數據存儲目錄private final int memTableMaxSize;                   // MemTable最大容量private final ReadWriteLock lock;                    // 讀寫鎖，保證并發安全// 內存組件：活躍和不可變MemTableprivate volatile MemTable activeMemTable;           // 當前活躍的MemTableprivate final List<MemTable> immutableMemTables;    // 不可變MemTable列表// 磁盤組件：SSTable文件列表private final List<SSTable> ssTables;               // 所有SSTable文件// 后臺任務：壓縮執行器和策略private final ExecutorService compactionExecutor;   // 壓縮任務線程池private final CompactionStrategy compactionStrategy; // 壓縮策略// WAL (Write-Ahead Log) 寫前日志private final WriteAheadLog wal;                    // WAL實例// LSM Tree構造器：初始化所有組件public LSMTree(String dataDir, int memTableMaxSize) throws IOException {this.dataDir = dataDir;                          // 設置數據目錄this.memTableMaxSize = memTableMaxSize;          // 設置MemTable大小限制this.lock = new ReentrantReadWriteLock();        // 初始化讀寫鎖// 確保數據目錄存在createDirectoryIfNotExists(dataDir);// 初始化內存組件this.activeMemTable = new MemTable(memTableMaxSize);  // 創建活躍MemTablethis.immutableMemTables = new ArrayList<>();     // 初始化不可變MemTable列表this.ssTables = new ArrayList<>();              // 初始化SSTable列表// 初始化壓縮策略（最多4個文件觸發壓縮，層級倍數為10）this.compactionStrategy = new CompactionStrategy(dataDir, 4, 10);// 初始化WAL寫前日志this.wal = new WriteAheadLog(dataDir + "/wal.log");// 啟動后臺壓縮線程（單線程，避免并發沖突）this.compactionExecutor = Executors.newSingleThreadExecutor(r -> {Thread t = new Thread(r, "LSMTree-Compaction"); // 設置線程名t.setDaemon(true);                           // 設為守護線程return t;});// 系統啟動時恢復已有數據recover();// 注意：后臺壓縮任務暫時禁用，避免測試時的線程問題// startBackgroundCompaction();}
}

架構設計解析：LSM Tree的核心設計采用分層存儲架構。內存層包括活躍MemTable（接收新寫入）和不可變MemTable（準備刷盤）。磁盤層包含多個SSTable文件，按時間順序組織。讀寫鎖確保并發安全：讀操作可以并發，但寫操作是獨占的。WAL確保數據持久性，壓縮策略管理SSTable的合并優化。這種設計在高寫入性能和數據一致性之間取得了最佳平衡。

數據寫入流程

寫入操作實現

/*** 插入鍵值對*/
public void put(String key, String value) throws IOException {if (key == null || value == null) {               // 參數合法性檢查throw new IllegalArgumentException("Key and value cannot be null");}lock.writeLock().lock();                          // 獲取寫鎖，確保線程安全try {// 步驟1: 先寫WAL確保持久性（WAL-first原則）wal.append(WriteAheadLog.LogEntry.put(key, value)); // 記錄PUT操作到WAL// 步驟2: 寫入活躍MemTable（內存操作，速度快）activeMemTable.put(key, value);               // 更新內存中的數據// 步驟3: 檢查是否需要刷盤（MemTable容量控制）if (activeMemTable.shouldFlush()) {           // 檢查是否達到刷盤條件flushMemTable();                          // 觸發MemTable刷盤}} finally {lock.writeLock().unlock();                    // 釋放寫鎖}
}

寫入流程解析：LSM Tree的寫入操作遵循嚴格的"WAL-first"原則，確保數據的持久性和一致性。首先將操作記錄到WAL，即使系統崩潰也能恢復。然后更新活躍MemTable，這是一個純內存操作，速度極快。最后檢查是否需要刷盤，當MemTable達到容量限制時觸發刷盤，保持內存使用可控。整個過程在寫鎖保護下執行，確保并發安全。

刪除操作實現

/*** 刪除鍵*/
public void delete(String key) throws IOException {if (key == null) {                               // 參數合法性檢查throw new IllegalArgumentException("Key cannot be null");}lock.writeLock().lock();                          // 獲取寫鎖，確保線程安全try {// 步驟1: 先寫WAL記錄刪除操作（確保刪除操作持久化）wal.append(WriteAheadLog.LogEntry.delete(key)); // 記錄DELETE操作到WAL// 步驟2: 在活躍MemTable中標記刪除（邏輯刪除，插入墓碑標記）activeMemTable.delete(key);                   // 創建刪除標記而非物理刪除// 步驟3: 檢查是否需要刷盤（刪除操作也會增加MemTable大小）if (activeMemTable.shouldFlush()) {           // 檢查是否達到刷盤條件flushMemTable();                          // 觸發MemTable刷盤}} finally {lock.writeLock().unlock();                    // 釋放寫鎖}
}

刪除操作解析：LSM Tree的刪除操作采用"邏輯刪除"策略，不立即物理刪除數據，而是插入一個墓碑標記（tombstone）。這種設計保持了LSM Tree的不可變性原則，避免了復雜的磁盤文件修改。刪除標記會在后續的壓縮過程中與原數據一起被清理。同樣遵循WAL-first原則，確保刪除操作的持久性。

MemTable刷盤機制

/*** 刷新MemTable到磁盤*/
private void flushMemTable() throws IOException {if (activeMemTable.isEmpty()) {                   // 檢查MemTable是否為空return;                                       // 空表無需刷盤}// 步驟1: 將活躍MemTable轉為不可變（freeze操作）immutableMemTables.add(activeMemTable);           // 添加到不可變列表activeMemTable = new MemTable(memTableMaxSize);   // 創建新的活躍MemTable// 步驟2: 同步刷盤不可變MemTable（避免死鎖問題）flushImmutableMemTable();                         // 立即執行刷盤操作
}/*** 刷新不可變MemTable到SSTable（調用前必須已獲取寫鎖）*/
private void flushImmutableMemTable() throws IOException {if (immutableMemTables.isEmpty()) {               // 檢查是否有不可變MemTablereturn;                                       // 無數據需要刷盤}// 步驟1: 獲取第一個不可變MemTableMemTable memTable = immutableMemTables.remove(0); // 移除并獲取MemTableList<KeyValue> entries = memTable.getAllEntries(); // 獲取所有鍵值對if (!entries.isEmpty()) {                         // 確保有數據需要寫入// 步驟2: 排序數據（SSTable要求有序存儲）entries.sort(KeyValue::compareTo);           // 按key字典序排序// 步驟3: 創建SSTable文件（Level 0文件，直接從MemTable刷入）String fileName = String.format("%s/sstable_level0_%d.db",dataDir, System.currentTimeMillis()); // 生成唯一文件名SSTable newSSTable = new SSTable(fileName, entries); // 創建SSTable文件ssTables.add(newSSTable);                     // 添加到SSTable列表// 步驟4: 清理WAL（數據已持久化，可以清理WAL）wal.checkpoint();                             // 執行WAL檢查點}
}

刷盤機制解析：MemTable刷盤是LSM Tree內存到磁盤轉換的關鍵過程。首先將活躍MemTable"凍結"為不可變狀態，立即創建新的活躍MemTable接收新寫入，確保寫入不被阻塞。然后將不可變MemTable的數據排序后寫入SSTable文件，文件命名包含層級和時間戳信息。最后執行WAL檢查點，清理已持久化的WAL記錄。這種設計確保了數據的有序性和系統的高可用性。

數據讀取流程

讀取操作實現

/*** 查詢鍵值*/
public String get(String key) {if (key == null) {                               // 參數合法性檢查throw new IllegalArgumentException("Key cannot be null");}lock.readLock().lock();                          // 獲取讀鎖（允許并發讀取）try {// 步驟1: 優先查詢活躍MemTable（最新數據）String value = activeMemTable.get(key);      // 從活躍MemTable查找if (value != null) {                         // 找到數據return value;                            // 直接返回（可能是刪除標記）}// 步驟2: 查詢不可變MemTable（按時間倒序，新數據優先）for (int i = immutableMemTables.size() - 1; i >= 0; i--) {value = immutableMemTables.get(i).get(key); // 從不可變MemTable查找if (value != null) {                     // 找到數據return value;                        // 返回找到的值}}// 步驟3: 查詢SSTable（按創建時間倒序，新文件優先）List<SSTable> sortedSSTables = new ArrayList<>(ssTables); // 創建副本避免并發修改sortedSSTables.sort((a, b) -> Long.compare(b.getCreationTime(), a.getCreationTime())); // 時間倒序for (SSTable ssTable : sortedSSTables) {     // 遍歷所有SSTablevalue = ssTable.get(key);                // 從SSTable查找if (value != null) {                     // 找到數據return value;                        // 返回找到的值}}return null;                                 // 所有地方都沒找到，返回null} finally {lock.readLock().unlock();                    // 釋放讀鎖}
}

讀取流程解析：LSM Tree的讀取操作采用分層查找策略，嚴格按照數據新舊程度查找，確保返回最新版本的數據。查找順序是：活躍MemTable → 不可變MemTable → SSTable文件。每個層級都按時間倒序查找，新數據優先。使用讀鎖允許多個讀操作并發執行，提高讀取性能。如果在任何層級找到數據就立即返回，這種"短路"機制減少了不必要的查找開銷。

系統恢復機制

從磁盤恢復數據

/*** 從WAL和SSTable恢復數據*/
private void recover() throws IOException {// 步驟1: 恢復SSTable文件File dir = new File(dataDir);                    // 獲取數據目錄File[] files = dir.listFiles((d, name) -> name.endsWith(".db")); // 過濾.db文件if (files != null) {                             // 確保目錄存在且有文件// 按文件修改時間排序（確保加載順序一致）Arrays.sort(files, (a, b) -> Long.compare(a.lastModified(), b.lastModified()));for (File file : files) {                    // 遍歷所有SSTable文件SSTable ssTable = new SSTable(file.getAbsolutePath()); // 加載SSTablessTables.add(ssTable);                   // 添加到SSTable列表}}// 步驟2: 從WAL恢復未刷盤的數據List<WriteAheadLog.LogEntry> entries = wal.recover(); // 讀取WAL條目for (WriteAheadLog.LogEntry entry : entries) {   // 遍歷所有WAL條目if (entry.getOperation() == WriteAheadLog.Operation.PUT) {// 重放PUT操作activeMemTable.put(entry.getKey(), entry.getValue());} else if (entry.getOperation() == WriteAheadLog.Operation.DELETE) {// 重放DELETE操作activeMemTable.delete(entry.getKey());}}
}

恢復機制解析：系統恢復是LSM Tree確保數據一致性的關鍵機制。首先掃描數據目錄中的所有SSTable文件，按修改時間排序后加載，確保文件的層級關系正確。然后從WAL中恢復所有未刷盤的操作，重新應用到活躍MemTable中。這種兩階段恢復確保了即使系統崩潰，也能完整恢復所有已提交的數據。恢復過程是冪等的，多次執行結果一致。

強制刷盤和資源清理

/*** 強制刷盤*/
public void flush() throws IOException {lock.writeLock().lock();                          // 獲取寫鎖try {// 步驟1: 刷新活躍MemTableif (!activeMemTable.isEmpty()) {              // 檢查活躍MemTable是否有數據flushMemTable();                          // 執行刷盤操作}// 步驟2: 刷新所有剩余的不可變MemTablewhile (!immutableMemTables.isEmpty()) {       // 循環處理所有不可變MemTableflushImmutableMemTable();                 // 刷盤每個不可變MemTable}} finally {lock.writeLock().unlock();                    // 釋放寫鎖}
}/*** 關閉LSM Tree*/
public void close() throws IOException {// 步驟1: 刷盤所有內存數據flush();                                          // 確保所有數據持久化// 步驟2: 關閉WALwal.close();                                      // 關閉寫前日志// 步驟3: 立即關閉線程池，不等待compactionExecutor.shutdownNow();                 // 強制關閉壓縮線程
}/*** 創建目錄*/
private void createDirectoryIfNotExists(String path) throws IOException {File dir = new File(path);                        // 創建File對象if (!dir.exists() && !dir.mkdirs()) {            // 檢查目錄是否存在，不存在則創建throw new IOException("Failed to create directory: " + path); // 創建失敗拋異常}
}

資源管理解析：強制刷盤操作確保所有內存數據都被持久化，這在系統關閉或數據備份時非常重要。關閉操作按照嚴格的順序執行：先刷盤數據，再關閉WAL，最后關閉后臺線程。這種順序確保了數據的完整性和系統的優雅退出。目錄創建是一個基礎的文件系統操作，確保數據存儲路徑的可用性。

統計信息和監控

/*** 獲取統計信息*/
public LSMTreeStats getStats() {lock.readLock().lock();                          // 獲取讀鎖try {return new LSMTreeStats(activeMemTable.size(),               // 活躍MemTable大小immutableMemTables.size(),           // 不可變MemTable數量ssTables.size());                    // SSTable文件數量} finally {lock.readLock().unlock();                    // 釋放讀鎖}
}/*** LSM Tree 統計信息*/
public static class LSMTreeStats {private final int activeMemTableSize;            // 活躍MemTable條目數private final int immutableMemTableCount;        // 不可變MemTable數量private final int ssTableCount;                  // SSTable文件數量public LSMTreeStats(int activeMemTableSize, int immutableMemTableCount, int ssTableCount) {this.activeMemTableSize = activeMemTableSize;     // 設置活躍MemTable大小this.immutableMemTableCount = immutableMemTableCount; // 設置不可變MemTable數量this.ssTableCount = ssTableCount;                 // 設置SSTable數量}public int getActiveMemTableSize() {             // 獲取活躍MemTable大小return activeMemTableSize;}public int getImmutableMemTableCount() {         // 獲取不可變MemTable數量return immutableMemTableCount;}public int getSsTableCount() {                   // 獲取SSTable數量return ssTableCount;}@Overridepublic String toString() {                       // 格式化輸出統計信息return String.format("LSMTreeStats{activeMemTable=%d, immutableMemTables=%d, ssTables=%d}",activeMemTableSize, immutableMemTableCount, ssTableCount);}
}

統計監控解析：統計信息對于監控LSM Tree的健康狀態和性能調優非常重要。活躍MemTable大小反映當前內存使用情況，不可變MemTable數量顯示待刷盤的數據量，SSTable數量體現磁盤文件的數量。這些指標幫助運維人員了解系統負載，判斷是否需要調整參數或觸發壓縮操作。統計操作使用讀鎖，不會阻塞正常的讀寫操作。

壓縮策略集成

雖然代碼中暫時禁用了后臺壓縮任務，但壓縮策略已經集成到系統中：

/*** 啟動后臺壓縮任務*/
private void startBackgroundCompaction() {compactionExecutor.submit(() -> {                 // 提交后臺任務while (!Thread.currentThread().isInterrupted()) { // 循環直到線程中斷try {Thread.sleep(30000);                 // 每30秒檢查一次if (compactionStrategy.needsCompaction(ssTables)) { // 檢查是否需要壓縮performCompaction();              // 執行壓縮操作}} catch (InterruptedException e) {Thread.currentThread().interrupt();   // 恢復中斷狀態break;                               // 退出循環} catch (Exception e) {e.printStackTrace();                 // 記錄異常（實際項目中應使用日志）}}});
}/*** 執行壓縮操作*/
private void performCompaction() throws IOException {lock.writeLock().lock();                          // 獲取寫鎖（壓縮需要修改SSTable列表）try {List<SSTable> newSSTables = compactionStrategy.compact(ssTables); // 執行壓縮ssTables.clear();                             // 清空原SSTable列表ssTables.addAll(newSSTables);                 // 添加壓縮后的SSTable} finally {lock.writeLock().unlock();                    // 釋放寫鎖}
}