闲大赋

Appearance

有状态高可用：LSM存储引擎示例

About 2582 wordsAbout 9 min

架构新书

2026-10-30

10.5 持久化例子:LSM的存储引擎

本节以一个简化的Java版本的版本LSM数据引擎实现来说明如何实现WAL和快照。例子代码可以如下克隆

git clone https://gitee.com/distributed-system-arc/lsm-java

如果运行单元测试

mvn test

也可以运行性能测试，了解LSM-Tree的读写性能

mvn clean package
java -jar jmh/target/jmh.jar PutTest GetTest

LSM-Tree(Log-Structured Merge-Tree)日志结构合并树，此存储引擎专门用于写多读少的业务场景，典型的在NOSQL中实现：RocksDB、LevelDB、SlateDB，Cassandra、Clickhouse，TiKV、InfluxDB，Prometheus TSDB等，Apache Doris和Apache IOT也是基于LSM变种实现。

注：例子参考了https://github.com/brianxiadong/java-lsm-tree 以及 https://skyzh.github.io/mini-lsm/00-overview.html的rust实现

注：SlateDB作者也是DDIA第二版的作者

10.5.1 LSM 介绍

LSM-Tree（Log-Structured Merge-Tree，日志结构合并树）是一种面向写优化的存储结构，核心思想是把随机写转化为顺序写，通过immutable Memtable缓冲和快照的分层合并来获得极高的写入吞吐。在执行PUT操作时候它不会修改内存或者快照的的数据，而是顺序添加。当执行Get操作时候，它只需要读取到内存或者快照中的最新数据即可。当删除数据时候，顺序添加一个Value为空的键值对。

它的架构如下图

LSM-Tree的各个组件说明如下，每个组件都是为了高速写入而设计：

  • MemTable :内存有序表（本例子使用ConcurrentSkipListMap实现），新数据写到内存，并记录到预写日志里。
  • WAL: 写入操作先追加到 WAL，防止宕机丢数据，采用顺序 IO有极高的性能。
  • Immutable MemTable : 系统检测到当前的MemTable容量超过一定阈值，将生成空的MemTable代替当前使用的 MemTable。 MemTable转为Immutable MemTable 后不再接受操作。等待后台线程刷新到磁盘。刷新成功后，删除此Immutable Memtable以及对应的WAL。可以理解Immutable MemTable 是一个生成快照前的缓冲区。
  • SSTable（Sorted String Table）：后台线程定时检测到有Immutable MemTable，并成对应的一个SSTable文件。文件包含了MemTable内存Key-Value序列化数据。
  • SSTable合并：SSTable文件个数达到一定数量，将合并生成一个新的SSTable文件。SSTable采用分层管理，每一层的多个SSTable文件会再次合并生成一个下一层的新的SSTable。如下MemTable合并生成SSTable-0-L0（这里L0指的是第一层），SSTable-1-L0等多个第一层文件，后台程序将检查此层文件，达到个数阈值，比如4个L0层文件后，将合并生成L1层SSTable。限于篇幅，本文不介绍SSTable合并。可以参考本书例子源码LSMTree.performCompaction

如果没有Immutable MemTable而是直接使用MemTable生成快照，必须停止操作影响存储引擎的性能

下面代码片段展示了MemTable对象，重要的字段如下

  • data，用于内存中Key—Value 读写。这里使用ConcurrentSkipListMap是因为 快照文件里，需要保证Key的有序。
  • log，预写日志，PUT或者Del操作，需要调用此类记录操作内容
public class MemTable {
    private final ConcurrentSkipListMap<String, KeyValue> data;
    private final int maxSize;
    private volatile int currentSize;
    private WriteAheadLog log

    public MemTable(int maxSize) {
        this.data = new ConcurrentSkipListMap<>();
        this.maxSize = maxSize;
        this.currentSize = 0;
    }
    public void put(String key, String value) {
        wal.append(WriteAheadLog.LogEntry.put(key, value));
        KeyValue kv = new KeyValue(key, value);
        data.put(key, kv);
    }
    public void delete(String key){...}
    public String get(String key){}
  }

LSM-Tree是存储引擎，负责了数据的读取和更新，以及快照等操作。

public class LSMTree implements AutoCloseable {
    private final String dataDir;
    private final int memTableMaxSize;
    // 内存数据
    private  MemTable activeMemTable;
    private  List<MemTable> immutableMemTables = new CopyOnWriteArrayList<>();
    
    // 磁盘数据
    private  List<SSTable> ssTables = new CopyOnWriteArrayList<>();
    
    ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(3);
    public LSMTree(String dataDir, int memTableMaxSize){
        this.dataDir = dataDir;
        this.memTableMaxSize = memTableMaxSize;
        
        // 初始化目录
        createDirectoryIfNotExists(dataDir);
        //恢复数据，获得最大一个wal日志编号
        Integer index = recover();
        WriteAheadLog wal  = new WriteAheadLog(dataDir ,index+1);
        // 初始化组件
        this.activeMemTable = new MemTable(memTableMaxSize,wal);
        // 初始化压缩策略
        this.compactionStrategy = new CompactionStrategy(dataDir, 4, 10);
    }
    
    public String get(String key){...}
    public void put(String key, String value)(...)
    public void recover(){...}
  • dataDir: 日志和快照的存储目录
  • memTableMaxSize： MemTable的容量，以字符为单位计算。
  • activeMemTable：当前使用的MemTable
  • immutableMemTables：不可变的MemTable存放在此，等待快照到磁盘上
  • ssTables： 多个快照文件对应的类。
  • scheduler：定时调度器，用于定时生成快照文件，合并快照文件，以及检测MemTable容量

10.5.2 LSM读和写

当对LSM-Tree进行写操作的时候，流程如下

  1. 获得当前激活的MemTable
  2. 执行Memtable.put操作，即调用ConcurrentSkipListMap.put
  3. 记录WAL日志，比如命令set name xiandafu 的WAL日志内容是set|name|xiandafu|时间戳\r\n
  4. 如果是删除操作，则添加一个值为空的数据，比如set name ""

如下代码片段显示LSMTree.put

public void put(String key, String value) throws IOException {
    if (key == null || value == null) {
        throw new IllegalArgumentException("Key and value cannot be null");
    }
    activeMemTable.put(key, value);
}

当对LSM-Tree进行读操作的时候，则有可能需要从前激活的Memtable和冻结的Memtable中查询，如果未查询到，则需要按照SSTable层次，依次查询SSTable。在构建SSTable时候，构建了一个布隆过滤器索引。因此不需要遍历整个文件

  1. 从当前MemTable中查询，如果查询到非空值，则返回。如果查询到空值，表示已经删除
  2. 如果从Memtable未查询到，则按照时间倒序遍历Immutable MemTable。
  3. 如果Immutable MemTable 未查询到，则从文件SSTable中，逐级查找。先查找层级一的所有SSTable文件，然后层级二的所有SSTable文件等
  4. SSTable文件包含此文件所有的Key的索引信息，使用的是布隆过滤器，用于判断Key是否存在此文件中。如果返回存在，则在遍历此文件。

查询SSTable时候，需要注意是

  • 布隆过滤器能快速判断Key一定不存在和可能存在，如果不存在，则需要查询下一个SSTable文件。
  • 由于存储采用的是有序排序，因此能帮助快速判断此Key是否在此文件中。
// 1. 首先查询活跃MemTable
String value = activeMemTable.get(key);
if (value != null) {
    return value;
}

// 2. 查询不可变MemTable（按时间倒序）
for (int i = immutableMemTables.size() - 1; i >= 0; i--) {
    value = immutableMemTables.get(i).get(key);
    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) {
    value = ssTable.get(key);
    if (value != null) {
        return value;
    }
}

10.5.3 WAL

类WriteAheadLog负责顺序记录操作日志，每一个MemTable对应一个WAL，当一个MemTable的生成SSTable后，此WAL文件可以删除。

public class WriteAheadLog {
    //日志文件名称
    private  String filePath;
    //wal的索引
    private  Integer index;
    BufferedWriter writer;

    public WriteAheadLog(String filePath,Integer indexLog) throws IOException {
        this.filePath = filePath;
        this.index = indexLog;
        FileOutputStream fos = new FileOutputStream(getFile(),true);
        //强制刷新到磁盘
        fos.getChannel().force(false);
        writer = new BufferedWriter(new OutputStreamWriter(fos, StandardCharsets.UTF_8));
    }

    /**
     * 追加日志条目
     */
    public void append(LogEntry entry) throws IOException {
        writer.write(entry.toString());
        writer.newLine();
        writer.flush();

    }
    public List<LogEntry> recover() throws IOException{}
    
}
  • 构造方法：创建一个只追加，且强制刷新到磁盘的日志文件。如果存储模型允许丢失少量数据，就不需要强制刷盘，比如Redis默认是1秒刷一次。
  • append： 添加一条日志，日志之间使用回车换行符号隔开
  • recover：用于从wal日志中恢复数据。
ist<LogEntry> entries = new ArrayList<>();
File file = /*日志文件*/
try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
    String line;
    while ((line = reader.readLine()) != null) {
        LogEntry entry = LogEntry.fromString(line);
        if (entry != null) {
            entries.add(entry);
        }
    }
}
return entries

10.5. 4 后台线程

后台有3个线程，用于执行从MemeTable到SSTable的转化

  • startInactiveMemTable，定时检测LSMTree.activeMemTable容量，如果超过阈值，则使用新的Memtable代替，原来的MemTable将添加到LSMTree.immutableMemTables列表中
  • flushImmutableMemTable。定时将immutableMemTables列表中的最早的MemTable刷新到磁盘上,生成SSTable
  • startBackgroundCompaction：将多个磁盘上的SSTable文件定时合并
protected  void startBackGroud(){
    //memetable->inactiveMemtable
    this.scheduler.scheduleAtFixedRate(new Runnable() {
        @Override
        public void run() {
            startInactiveMemTable();
        }
    },10,1, TimeUnit.SECONDS);
    //inactiveMemtable->sstables
    this.scheduler.scheduleAtFixedRate(new Runnable() {
        @Override
        public void run() {
            flushImmutableMemTable();
        }
    },15,10, TimeUnit.SECONDS);
    // sstable compaction
    this.scheduler.scheduleAtFixedRate(new Runnable() {
        @Override
        public void run() {
            startBackgroundCompaction();
        }
    },30,60, TimeUnit.SECONDS);

}

10.5.5 SSTable

LSM生成的多个个快照文件的类对应了SSTable，记录在LSMTree.ssTables中。SSTable对象记录文件位置，同时还在数据写入磁盘后，构造了一个布隆过滤器。用于在SSTable中快速查找Key是否存在

public class SSTable {
    private final String filePath;
    private final BloomFilter bloomFilter;
    private final long creationTime;

    public 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);
    }
    //数据写入磁盘
    private void writeToFile(List<KeyValue> sortedData){}
    //查找key，首先查找BloomFilter，如果返回true，在遍历文件
    public String get(String key) {}

其查找方法先使用布隆过滤器，然后遍历文件内容查找

public String get(String key) {
    // 首先检查布隆过滤器
    if (!bloomFilter.mightContain(key)) {
        return null;
    }

    try (DataInputStream dis = new DataInputStream(
            new BufferedInputStream(new FileInputStream(filePath)))) {
           //遍历文件查找，此时性能最差
    }

10.5.6 故障恢复

当LSM重启后，需要依次读取快照文件和预习日志文件，构成LSMTree。参考LSMTree.recover方法

private Integer recover() throws IOException {
    // 恢复SSTable
    File dir = new File(dataDir);
    File[] sstFiles = dir.listFiles((d, name) -> name.endsWith(".db"));

    if (sstFiles != null&&sstFiles.length!=0) {
        Arrays.sort(sstFiles, (a, b) -> Long.compare(a.lastModified(), b.lastModified()));

        for (File file : sstFiles) {
            SSTable ssTable = new SSTable(file.getAbsolutePath());
            ssTables.add(ssTable);
        }
    }
   // 恢复wal
    File[] walFiles = dir.listFiles((d, name) -> name.endsWith(".log"));
    Integer index = 0;
    if (walFiles != null&&walFiles.length!=0) {
        Arrays.sort(walFiles, (a, b) -> Long.compare(a.lastModified(), b.lastModified()));
        for(int i=0;i<walFiles.length;i++){
            File walFile = walFiles[i];
            //wal_xxx.log
             index = Integer.parseInt(walFile.getName()
                    .substring(4,walFile.getName().length()-4));
            WriteAheadLog writeAheadLog = new WriteAheadLog(dataDir,index);
            MemTable memTable = new MemTable(memTableMaxSize,writeAheadLog);
            memTable.recover();
            this.immutableMemTables.add(memTable);
        }
    
    
    }
    return index;

}

10.5.7 性能

在我的Mac Pro 6核机器上，按照写读操作占比20%、50%，80%进行测试，参考GetPutMixedTest

Benchmark                       (putMix)   Mode  Cnt       Score   Error  Units
GetPutMixedTest.getOrPutRandom        20  thrpt    2  451408.434          ops/s
GetPutMixedTest.getOrPutRandom        50  thrpt    2  161078.750          ops/s
GetPutMixedTest.getOrPutRandom        80  thrpt    2  105165.865          ops/s

可见在读写混合操作里，如果是写占比20%，吞吐量为45万TPS。如果是写占比80%，吞吐量是10万TPS

悲观情况下，如果完全从磁盘中读取数据，参考GetFromSSTableTest，当文件存储1万条数据时候，TPS为2805。当文件里存储10万条数据，TPS下降到322。

Benchmark                      (max)   Mode  Cnt      Score   Error  Units
GetFromSSTableTest.getRandom    1024  thrpt    2  30555.159          ops/s
GetFromSSTableTest.getRandom   10240  thrpt    2   2805.760          ops/s
GetFromSSTableTest.getRandom  102400  thrpt    2    322.453          ops/s

知行合一

Beetl Since 2010-2025 京ICP备13011864号-1