LSM-Tree (日志结构合并树)
LSM-Tree（日志结构合并树）是一种高效处理写操作的存储结构，广泛应用于NoSQL数据库如LevelDB和RocksDB。其核心思想是将随机写入转换为顺序写入，提升吞吐量。以下是其原理及Java实现示例：
### **LSM-Tree 原理**
1. **结构组成**：
- **MemTable**：内存中的有序结构（如跳表），用于快速写入。
- **Immutable MemTable**：MemTable写满后转为只读，准备刷盘。
- **SSTable（Sorted String Table）**：磁盘上的有序文件，由MemTable刷入生成，多个SSTable分层存储。
2. **写入流程**：
- 数据先写入MemTable。
- MemTable满后转为Immutable MemTable，异步刷入磁盘生成SSTable。
- 磁盘SSTable按层级组织，通过合并（Compaction）消除冗余数据。
3. **读取流程**：
- 依次查找MemTable、Immutable MemTable和各层SSTable。
- 使用布隆过滤器减少无效磁盘访问。
4. **合并（Compaction）**：
- 合并多个SSTable，保留最新数据，减少文件数量，提升读取效率。
---
### **Java 示例代码**
```java
import java.io.*;
import java.util.*;
import java.util.concurrent.ConcurrentSkipListMap;
public class LSMTree {
private ConcurrentSkipListMap<String, String> memTable = new ConcurrentSkipListMap<>();
private ConcurrentSkipListMap<String, String> immutableMemTable = null;
private List<File> sstables = new ArrayList<>();
private static final int MAX_MEMTABLE_SIZE = 1000;
// 写入数据
public synchronized void put(String key, String value) {
memTable.put(key, value);
if (memTable.size() >= MAX_MEMTABLE_SIZE) {
switchMemTable();
}
}
// 切换MemTable并刷盘
private void switchMemTable() {
immutableMemTable = memTable;
memTable = new ConcurrentSkipListMap<>();
flushToSSTable(immutableMemTable);
immutableMemTable = null;
}
// 将数据写入SSTable文件
private void flushToSSTable(ConcurrentSkipListMap<String, String> data) {
String filename = "sstable_" + System.currentTimeMillis() + ".txt";
File file = new File(filename);
try (BufferedWriter writer = new BufferedWriter(new FileWriter(file))) {
for (Map.Entry<String, String> entry : data.entrySet()) {
writer.write(entry.getKey() + "," + entry.getValue());
writer.newLine();
}
sstables.add(file);
} catch (IOException e) {
e.printStackTrace();
}
}
// 读取数据
public String get(String key) {
String value = memTable.get(key);
if (value != null) return value;
if (immutableMemTable != null) {
value = immutableMemTable.get(key);
if (value != null) return value;
}
// 从最新SSTable开始查找
for (int i = sstables.size() - 1; i >= 0; i--) {
value = searchInSSTable(sstables.get(i), key);
if (value != null) return value;
}
return null;
}
// 在SSTable中查找键
private String searchInSSTable(File file, String key) {
try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
String line;
while ((line = reader.readLine()) != null) {
String[] parts = line.split(",", 2);
if (parts[0].equals(key)) {
return parts.length > 1 ? parts[1] : null;
}
}
} catch (IOException e) {
e.printStackTrace();
}
return null;
}
// 合并SSTable文件
public void compact() {
if (sstables.size() < 2) return;
List<File> oldFiles = new ArrayList<>(sstables);
sstables.clear();
TreeMap<String, String> mergedData = new TreeMap<>();
// 按旧到新顺序合并，保留最新值
for (File file : oldFiles) {
try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
String line;
while ((line = reader.readLine()) != null) {
String[] parts = line.split(",", 2);
String key = parts[0];
String value = parts.length > 1 ? parts[1] : null;
mergedData.put(key, value);
}
} catch (IOException e) {
e.printStackTrace();
}
}
// 写入新文件并清理旧文件
String filename = "sstable_merged_" + System.currentTimeMillis() + ".txt";
File mergedFile = new File(filename);
try (BufferedWriter writer = new BufferedWriter(new FileWriter(mergedFile))) {
for (Map.Entry<String, String> entry : mergedData.entrySet()) {
writer.write(entry.getKey() + "," + entry.getValue());
writer.newLine();
}
sstables.add(mergedFile);
for (File f : oldFiles) {
f.delete();
}
} catch (IOException e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
LSMTree lsm = new LSMTree();
// 示例操作
lsm.put("key1", "value1");
lsm.put("key2", "value2");
System.out.println(lsm.get("key1")); // 输出 value1
}
}
```
### **代码说明**
1. **写入优化**：使用跳表（`ConcurrentSkipListMap`）作为MemTable，写满后转为Immutable并刷盘。
2. **读取流程**：依次检查内存表和SSTable文件，确保获取最新数据。
3. **合并策略**：简单合并所有SSTable，生成新文件并删除旧文件，保留最新键值。
### **优化方向**
- **分层存储**：引入层级结构，每层数据量逐层递增，合并策略更精细。
- **布隆过滤器**：快速判断键是否存在于SSTable，减少IO。
- **索引优化**：为SSTable维护内存索引，加速查找。
LSM-Tree通过顺序写入和定期合并，在高写入场景下表现优异，适合日志系统、时序数据库等应用。