LSM树（Log-Structured Merge-Tree）是Google Bigtable、LevelDB、RocksDB等高性能键值存储的核心数据结构。与传统B+树就地更新不同，LSM树将写操作转化为顺序追加日志，通过后台合并（Compaction）将数据从内存逐级下沉到磁盘，在写密集型场景中实现卓越的吞吐量。本文用Java实现一个简化版LSM树，涵盖MemTable、不可变表、SSTable分层与压缩策略。
核心原理
写放大与读放大的权衡
- 写放大（Write Amplification）：一次逻辑写操作导致的实际物理写次数。B+树的写放大通常为10-100，而LSM树通过顺序写可将写放大控制在5-30。
- 读放大（Read Amplification）：一次逻辑读操作需要访问的磁盘页数。LSM树需要查询多层SSTable，读放大高于B+树。
- 空间放大（Space Amplification）：存储相同数据实际占用的空间比例。LSM树因保留多版本数据，空间放大通常为1.1-1.3。
LSM树三层架构
- MemTable：内存中的有序数据结构（通常用跳表或红黑树），所有写入先进入MemTable。
- Immutable MemTable：MemTable写满后转为只读，后台线程将其刷写到磁盘成为SSTable。
- SSTable层级（Levels）：磁盘上按层组织的不重叠有序文件集合。Level 0允许键范围重叠，Level 1+要求层内键范围不重叠。
压缩（Compaction）策略
- Leveled Compaction（LevelDB/RocksDB默认）：每层总大小有上限，当某层超过上限时，选择一个文件与下一层重叠的文件合并。层间大小比通常为10。
- Tiered Compaction：每层可包含多个重叠文件，合并时才将所有文件统一排序。写放大更低但读放大更高。
- FIFO Compaction：仅保留最近N个文件，适用于时序数据。
完整Java实现
import java.io.*;
import java.nio.file.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;
/**
* 简化版LSM树实现
* 包含：MemTable（TreeMap）、SSTable分层、Leveled Compaction、布隆过滤器
*/
public class LSMTree {
// 配置参数
private final int memTableSizeLimit; // MemTable大小阈值（条数）
private final int levelSizeMultiplier; // 层间大小倍数
private final int baseLevelSize; // Level 1目标大小（条数）
private final String dataDir; // 数据目录
// 内存组件
private TreeMap<String, String> memTable; // 活跃MemTable
private TreeMap<String, String> immutableMemTable; // 不可变MemTable（刷盘中）
// 磁盘组件：Level -> 文件列表
private List<List<SSTable>> levels;
// 并发控制
private final ReadWriteLock lock = new ReentrantReadWriteLock();
private final ExecutorService compactionExecutor = Executors.newSingleThreadExecutor();
// 元数据
private int nextSSTableId = 0;
public LSMTree(String dataDir, int memTableSizeLimit,
int levelSizeMultiplier, int baseLevelSize) {
this.dataDir = dataDir;
this.memTableSizeLimit = memTableSizeLimit;
this.levelSizeMultiplier = levelSizeMultiplier;
this.baseLevelSize = baseLevelSize;
this.memTable = new TreeMap<>();
this.immutableMemTable = null;
this.levels = new ArrayList<>();
// 初始化层结构
for (int i = 0; i < 7; i++) {
levels.add(new ArrayList<>());
}
// 创建数据目录
try {
Files.createDirectories(Paths.get(dataDir));
} catch (IOException e) {
throw new RuntimeException("无法创建数据目录", e);
}
// 从磁盘恢复
recoverFromDisk();
}
/**
* 插入/更新键值对
*/
public void put(String key, String value) {
lock.writeLock().lock();
try {
memTable.put(key, value);
// 检查是否需要刷盘
if (memTable.size() >= memTableSizeLimit) {
flushMemTable();
}
} finally {
lock.writeLock().unlock();
}
}
/**
* 查询键值
*/
public String get(String key) {
lock.readLock().lock();
try {
// 1. 查询MemTable
if (memTable.containsKey(key)) {
return memTable.get(key);
}
// 2. 查询Immutable MemTable
if (immutableMemTable != null && immutableMemTable.containsKey(key)) {
return immutableMemTable.get(key);
}
// 3. 从Level 0开始逐层查询SSTable（新层优先）
for (int level = 0; level < levels.size(); level++) {
List<SSTable> tables = levels.get(level);
// 逆序查询：后写入的SSTable优先
for (int i = tables.size() - 1; i >= 0; i--) {
SSTable table = tables.get(i);
if (!table.mightContain(key)) continue; // 布隆过滤器过滤
String value = table.get(key);
if (value != null) return value;
}
}
return null; // 未找到
} finally {
lock.readLock().unlock();
}
}
/**
* 删除键（通过写入墓碑标记）
*/
public void delete(String key) {
put(key, "\0TOMBSTONE\0"); // 特殊墓碑值
}
/**
* 范围查询：[startKey, endKey)
*/
public List<Map.Entry<String, String>> rangeQuery(String startKey, String endKey) {
lock.readLock().lock();
try {
TreeMap<String, String> result = new TreeMap<>();
// 合并MemTable数据
for (Map.Entry<String, String> e : memTable.subMap(startKey, endKey).entrySet()) {
result.put(e.getKey(), e.getValue());
}
if (immutableMemTable != null) {
for (Map.Entry<String, String> e : immutableMemTable.subMap(startKey, endKey).entrySet()) {
if (!result.containsKey(e.getKey())) {
result.put(e.getKey(), e.getValue());
}
}
}
// 合并各层SSTable数据
for (List<SSTable> tables : levels) {
for (SSTable table : tables) {
if (table.getMaxKey().compareTo(startKey) < 0 ||
table.getMinKey().compareTo(endKey) >= 0) {
continue; // 键范围不相交
}
for (Map.Entry<String, String> e : table.range(startKey, endKey)) {
if (!result.containsKey(e.getKey())) {
result.put(e.getKey(), e.getValue());
}
}
}
}
// 过滤墓碑
List<Map.Entry<String, String>> filtered = new ArrayList<>();
for (Map.Entry<String, String> e : result.entrySet()) {
if (!"\0TOMBSTONE\0".equals(e.getValue())) {
filtered.add(e);
}
}
return filtered;
} finally {
lock.readLock().unlock();
}
}
/**
* 将MemTable转为Immutable并触发刷盘
*/
private void flushMemTable() {
if (immutableMemTable != null) {
return; // 已有immutable，等待刷盘完成
}
immutableMemTable = memTable;
memTable = new TreeMap<>();
// 异步刷盘
final TreeMap<String, String> toFlush = immutableMemTable;
compactionExecutor.submit(() -> {
try {
writeSSTable(toFlush, 0);
} catch (IOException e) {
e.printStackTrace();
} finally {
lock.writeLock().lock();
try {
immutableMemTable = null;
} finally {
lock.writeLock().unlock();
}
}
});
}
/**
* 将有序数据写入SSTable文件
*/
private void writeSSTable(TreeMap<String, String> data, int level) throws IOException {
if (data.isEmpty()) return;
String filename = String.format("%s/sst_%d_level%d.sst", dataDir, nextSSTableId++, level);
SSTable table = new SSTable(filename, data);
table.writeToDisk();
lock.writeLock().lock();
try {
levels.get(level).add(table);
// 检查是否需要压缩
scheduleCompaction(level);
} finally {
lock.writeLock().unlock();
}
}
/**
* 触发层级压缩
*/
private void scheduleCompaction(int level) {
int targetSize = baseLevelSize * (int) Math.pow(levelSizeMultiplier, level);
List<SSTable> tables = levels.get(level);
if (tables.size() * memTableSizeLimit > targetSize && level < levels.size() - 1) {
compactionExecutor.submit(() -> {
try {
compactLevel(level);
} catch (IOException e) {
e.printStackTrace();
}
});
}
}
/**
* Leveled Compaction：将Level L的数据合并到Level L+1
*/
private void compactLevel(int level) throws IOException {
lock.writeLock().lock();
List<SSTable> currentLevel;
try {
currentLevel = new ArrayList<>(levels.get(level));
levels.get(level).clear();
} finally {
lock.writeLock().unlock();
}
if (currentLevel.isEmpty()) return;
// 合并所有数据
TreeMap<String, String> merged = new TreeMap<>();
for (SSTable table : currentLevel) {
for (Map.Entry<String, String> e : table.allEntries()) {
merged.put(e.getKey(), e.getValue());
}
table.deleteFile();
}
// 分割为多个SSTable写入下一层
int entriesPerFile = baseLevelSize;
TreeMap<String, String> batch = new TreeMap<>();
for (Map.Entry<String, String> e : merged.entrySet()) {
batch.put(e.getKey(), e.getValue());
if (batch.size() >= entriesPerFile) {
writeSSTable(batch, level + 1);
batch = new TreeMap<>();
}
}
if (!batch.isEmpty()) {
writeSSTable(batch, level + 1);
}
// 递归检查下一层
scheduleCompaction(level + 1);
}
/**
* 从磁盘恢复SSTable
*/
private void recoverFromDisk() {
File dir = new File(dataDir);
File[] files = dir.listFiles((d, name) -> name.endsWith(".sst"));
if (files == null) return;
for (File f : files) {
String name = f.getName();
try {
int level = Integer.parseInt(name.substring(name.lastIndexOf("level") + 5, name.lastIndexOf('.')));
SSTable table = SSTable.loadFromDisk(f.getAbsolutePath());
while (levels.size() <= level) levels.add(new ArrayList<>());
levels.get(level).add(table);
} catch (Exception e) {
e.printStackTrace();
}
}
}
/**
* 关闭LSM树，确保所有数据刷盘
*/
public void close() {
compactionExecutor.shutdown();
try {
compactionExecutor.awaitTermination(30, TimeUnit.SECONDS);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
/**
* SSTable：不可变的磁盘有序键值文件
*/
static class SSTable {
private String filename;
private String minKey, maxKey;
private int entryCount;
private SimpleBloomFilter bloomFilter;
private TreeMap<String, String> data; // 内存缓存（简化版，生产环境应分块索引）
public SSTable(String filename, TreeMap<String, String> data) {
this.filename = filename;
this.data = data;
this.entryCount = data.size();
if (!data.isEmpty()) {
this.minKey = data.firstKey();
this.maxKey = data.lastKey();
}
this.bloomFilter = new SimpleBloomFilter(entryCount, 0.01);
for (String k : data.keySet()) {
bloomFilter.add(k);
}
}
public void writeToDisk() throws IOException {
try (DataOutputStream dos = new DataOutputStream(
new BufferedOutputStream(new FileOutputStream(filename)))) {
// 写布隆过滤器位图长度和位图
byte[] bfBytes = bloomFilter.toBytes();
dos.writeInt(bfBytes.length);
dos.write(bfBytes);
// 写条目数
dos.writeInt(entryCount);
// 写键值对
for (Map.Entry<String, String> e : data.entrySet()) {
dos.writeUTF(e.getKey());
dos.writeUTF(e.getValue());
}
// 写元数据
dos.writeUTF(minKey != null ? minKey : "");
dos.writeUTF(maxKey != null ? maxKey : "");
}
}
public static SSTable loadFromDisk(String filename) throws IOException {
try (DataInputStream dis = new DataInputStream(
new BufferedInputStream(new FileInputStream(filename)))) {
// 读布隆过滤器
int bfLen = dis.readInt();
byte[] bfBytes = new byte[bfLen];
dis.readFully(bfBytes);
SimpleBloomFilter bf = SimpleBloomFilter.fromBytes(bfBytes);
// 读数据
int count = dis.readInt();
TreeMap<String, String> data = new TreeMap<>();
for (int i = 0; i < count; i++) {
data.put(dis.readUTF(), dis.readUTF());
}
SSTable table = new SSTable(filename, data);
table.bloomFilter = bf;
table.minKey = dis.readUTF();
table.maxKey = dis.readUTF();
return table;
}
}
public String get(String key) {
return data.get(key);
}
public boolean mightContain(String key) {
return bloomFilter.mightContain(key);
}
public List<Map.Entry<String, String>> range(String start, String end) {
return new ArrayList<>(data.subMap(start, end).entrySet());
}
public Set<Map.Entry<String, String>> allEntries() {
return data.entrySet();
}
public String getMinKey() { return minKey; }
public String getMaxKey() { return maxKey; }
public void deleteFile() {
new File(filename).delete();
}
}
/**
* 简化布隆过滤器
*/
static class SimpleBloomFilter {
private BitSet bits;
private int numHashFunctions;
private int bitSize;
public SimpleBloomFilter(int expectedInsertions, double fpp) {
this.bitSize = optimalNumOfBits(expectedInsertions, fpp);
this.numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
this.bits = new BitSet(bitSize);
}
private SimpleBloomFilter(BitSet bits, int numHash, int bitSize) {
this.bits = bits;
this.numHashFunctions = numHash;
this.bitSize = bitSize;
}
public void add(String key) {
long hash64 = hash(key);
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int combinedHash = hash1 + i * hash2;
if (combinedHash < 0) combinedHash = ~combinedHash;
bits.set(combinedHash % bitSize);
}
}
public boolean mightContain(String key) {
long hash64 = hash(key);
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int combinedHash = hash1 + i * hash2;
if (combinedHash < 0) combinedHash = ~combinedHash;
if (!bits.get(combinedHash % bitSize)) return false;
}
return true;
}
private static long hash(String key) {
// FNV-1a 64-bit hash
long hash = 0xcbf29ce484222325L;
for (byte b : key.getBytes()) {
hash ^= b & 0xff;
hash *= 0x100000001b3L;
}
return hash;
}
private static int optimalNumOfBits(long n, double p) {
return Math.max(1, (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2))));
}
private static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
public byte[] toBytes() {
return bits.toByteArray();
}
public static SimpleBloomFilter fromBytes(byte[] bytes) {
BitSet bs = BitSet.valueOf(bytes);
// 简化：无法恢复numHash和bitSize，使用默认值
return new SimpleBloomFilter(bs, 3, Math.max(bs.size(), 1));
}
}
/**
* 主函数：演示LSM树的读写与压缩
*/
public static void main(String[] args) {
String dbPath = "/tmp/lsm_test_db";
// 清理旧数据
try {
Files.walk(Paths.get(dbPath))
.sorted(Comparator.reverseOrder())
.map(Path::toFile)
.forEach(File::delete);
} catch (IOException e) { /* ignore */ }
LSMTree lsm = new LSMTree(dbPath, 10, 4, 20);
System.out.println("=== LSM树读写演示 ===");
// 写入数据
System.out.println("\n--- 写入100条数据 ---");
for (int i = 0; i < 100; i++) {
lsm.put("key" + String.format("%03d", i), "value" + i);
}
// 查询
System.out.println("\n--- 点查询 ---");
System.out.println("key005: " + lsm.get("key005"));
System.out.println("key050: " + lsm.get("key050"));
System.out.println("key999: " + lsm.get("key999")); // 不存在
// 更新
System.out.println("\n--- 更新key005 ---");
lsm.put("key005", "updated_value");
System.out.println("key005 after update: " + lsm.get("key005"));
// 删除
System.out.println("\n--- 删除key010 ---");
lsm.delete("key010");
System.out.println("key010 after delete: " + lsm.get("key010"));
// 范围查询
System.out.println("\n--- 范围查询 [key005, key015) ---");
List<Map.Entry<String, String>> range = lsm.rangeQuery("key005", "key015");
for (Map.Entry<String, String> e : range) {
System.out.println(" " + e.getKey() + " -> " + e.getValue());
}
// 大量写入触发压缩
System.out.println("\n--- 大量写入触发压缩 ---");
for (int i = 100; i < 500; i++) {
lsm.put("key" + String.format("%03d", i), "value" + i);
}
// 等待压缩完成
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
// 验证数据完整性
System.out.println("\n--- 数据完整性验证 ---");
int correct = 0, missing = 0;
for (int i = 0; i < 500; i++) {
String key = "key" + String.format("%03d", i);
String expected = (i == 10) ? null : (i == 5 ? "updated_value" : "value" + i);
String actual = lsm.get(key);
if (Objects.equals(expected, actual)) {
correct++;
} else {
missing++;
if (missing <= 3) {
System.out.println(" Mismatch: " + key + " expected=" + expected + " actual=" + actual);
}
}
}
System.out.printf("验证结果: %d 正确, %d 错误%n", correct, missing);
// 显示层级统计
System.out.println("\n--- SSTable层级统计 ---");
for (int i = 0; i < lsm.levels.size(); i++) {
List<SSTable> tables = lsm.levels.get(i);
if (!tables.isEmpty()) {
int totalEntries = tables.stream().mapToInt(t -> t.entryCount).sum();
System.out.printf("Level %d: %d 个文件, %d 条数据%n", i, tables.size(), totalEntries);
}
}
lsm.close();
}
}
关键设计解析
MemTable到SSTable的转换
当MemTable达到容量阈值时，通过原子交换将活跃表转为不可变表，立即创建新的空MemTable继续服务写请求。不可变表由后台线程异步刷写到磁盘，避免阻塞前端写入。这种”双缓冲”设计是LSM树实现高吞吐的核心机制。
布隆过滤器的层内优化
每层SSTable都配备布隆过滤器，读操作时先用O(1)的过滤器查询排除不可能包含目标键的文件，避免大量无效的磁盘I/O。当误报率设置为1%时，对不存在键的查询可减少约99%的文件访问。
Leveled Compaction的数学原理
设层间大小比为r=10，当Level L的数据量超过r^L·baseSize时触发压缩。通过归纳法可证明：最坏情况下写放大约为r·L/(r-1) ≈ 11（L=6层），读放大最多为L+1=7次SSTable查询。这种对数级复杂度使LSM树在超大规模数据集上仍保持可接受的读写性能。
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 写入 | O(log n) 内存操作 | O(memTableSize) |
| 点查询 | O(log n + L·log B) | O(1) |
| 范围查询 | O(log n + k + L·(log B + k/B)) | O(k) |
| 压缩 | O(M·log M) | O(M) |
其中n为MemTable大小，L为层数，B为SSTable块大小，M为合并数据量，k为返回结果数。
扩展方向
- 跳表MemTable：用ConcurrentSkipListMap替代TreeMap，提升并发写入性能。
- 块压缩：对SSTable数据块使用Snappy/Zstd压缩，减少磁盘占用。
- 分层压缩策略：根据工作负载动态切换Leveled/Tiered/FIFO压缩。
- WAL日志：添加预写日志保证崩溃恢复，避免MemTable数据丢失。
- 迭代器实现：支持高效的范围扫描与快照读取。
