LSM 树

LSM 树架构总览

MemTable 与刷盘

写入先追加到 WAL（用于崩溃恢复），再插入内存有序结构（MemTable）。MemTable 达到大小阈值后被封存（不可变），后台异步刷盘生成 SSTable。

写路径

1. 将 (key, value, seq_num) 追加到 WAL
2. 将 (key, value) 插入 MemTable（红黑树/跳表，O(log n)）
3. 当 MemTable 大小 >= 阈值：冻结为 ImmutableMemTable，开启新 MemTable
4. 后台线程：排序 ImmutableMemTable → 写 SSTable 文件 → 截断对应 WAL

读路径（点查）

1. 查 MemTable（内存，O(log n)）
2. 查 ImmutableMemTable
3. 按层级（L0 → L1 → ...）：先查布隆过滤器；若可能存在，二分查找 SSTable 索引

// MemTable simulation: in-memory sorted map
// Supports put(key, value) and del(key) with tombstones
// flush() outputs sorted SSTable (skip tombstones)
class MemTable {
    map<string, string> data; // key -> value or "" for tombstone
    static const string TOMBSTONE;
public:
    void put(const string& k, const string& v) { data[k] = v; }
    void del(const string& k) { data[k] = TOMBSTONE; }
    void flush() {
        for (auto& [k, v] : data) {
            if (v != TOMBSTONE) cout << k << ':' << v << '\n';
        }
    }
};
const string MemTable::TOMBSTONE = "__DEL__";

应用场景

• RocksDB——write_buffer_size（默认 64 MB）控制刷盘阈值
• Apache Cassandra——CommitLog（WAL）+ 每个列族一个 memtable
• LevelDB——Google 的原始 LSM 实现

删除：删除操作写入墓碑标记（tombstone）。墓碑在 Compaction 中传播，直到所有包含该 key 的旧 SSTable 被清除为止。过早清除墓碑会导致「复活」bug。

Compaction（合并压缩）

定期合并重叠的 SSTable，回收墓碑和重复 key 占用的空间，并降低读放大。两种主要策略：分层 Compaction（RocksDB 默认）和分级 Compaction（Cassandra）。

Compaction 策略

关键指标

• 读放大：每次点读需检查的 SSTable 数（分层 ≈ log N 层）
• 写放大：写入磁盘的字节数 / 用户写入字节数（分层约 10–30×）
• 空间放大：磁盘总用量 / 有效数据量（分级最高 2×，分层约 1.1×）

// LSM compaction: merge k sorted SSTables
// Each SSTable is a list of (key, seqno, value) sorted by key then seqno desc.
// Output: for each key, keep only the latest (highest seqno) value; skip tombstones.

struct Entry { string key, value; int seq; };

vector<Entry> compact(vector<vector<Entry>>& tables) {
    // k-way merge with priority queue
    using T = tuple<string,int,int,int>; // (key, -seq, table_idx, entry_idx)
    priority_queue<T, vector<T>, greater<T>> pq;
    for (int i = 0; i < (int)tables.size(); i++)
        if (!tables[i].empty())
            pq.push({tables[i][0].key, -tables[i][0].seq, i, 0});

    vector<Entry> result;
    string lastKey;
    while (!pq.empty()) {
        auto [key, negSeq, ti, ei] = pq.top(); pq.pop();
        int seq = -negSeq;
        if (key != lastKey) {
            lastKey = key;
            if (tables[ti][ei].value != "__DEL__")
                result.push_back(tables[ti][ei]);
        }
        if (ei + 1 < (int)tables[ti].size())
            pq.push({tables[ti][ei+1].key, -tables[ti][ei+1].seq, ti, ei+1});
    }
    return result;
}

应用场景

• RocksDB——默认分层；FIFO 和 Universal（分级）可选
• Cassandra——默认 STCS；读密集型用 LCS；时序数据用 TWCS
• ScyllaDB——ICS（增量 Compaction）以平滑 I/O

WAL 截断：SSTable 成功刷盘并 fsync 后，对应的 WAL 段才可安全删除。这是截断 WAL 的唯一安全时机。