KV 存储引擎

本章导读

传统数据库用 B-Tree 索引，读写都需要随机 I/O。Bitcask 的洞察：如果所有写入都是追加（append-only），那么写操作就是顺序 I/O——磁盘最快的操作模式。读取通过内存哈希索引直接定位文件偏移，也是 O(1)。代价是需要定期压缩（合并旧数据），但压缩可以在后台异步进行。

54.1 设计思想

Bitcask 模型的核心组件：

// 架构概览
//
// ┌─────────────────────────────────────┐
// │         内存哈希索引                  │
// │   key → (file_offset, value_size)   │
// └──────────────┬──────────────────────┘
//                │ 定位
// ┌──────────────▼──────────────────────┐
// │         追加写日志文件                │
// │  [rec1][rec2][rec3]...[recN]        │
// │  ← 旧数据（可能被覆盖）  新数据 →    │
// └─────────────────────────────────────┘
//
// 写入：追加到文件末尾 + 更新内存索引
// 读取：查内存索引 → 定位文件偏移 → 读取值
// 删除：写入墓碑记录（tombstone）
// 恢复：重放日志，重建内存索引

54.2 日志记录格式

每条记录的二进制格式：

// 记录格式（文本简化版，实际用二进制）：
// [4字节: 键长度][4字节: 值长度][1字节: 标志][键][值]
// 标志: 0=正常, 1=删除(tombstone)

// 简化实现：用文本格式（每行一条记录）
// 格式: "PUT key value" 或 "DEL key"
// 用 \t 分隔字段

func encodeRecord(string op, string key, string value) as string
    return op + "\t" + key + "\t" + value + "\n"
end

func decodeRecord(string line) as array<string>
    return string.split(line, "\t")
end

54.3 put：写入

class KvStore
    string dataFile
    dict<string, string> index   // 内存索引：key → value

    func open(string path)
        dataFile = path
        index = dict<string, string>()
        recover()
    end

    func put(string key, string value)
        // 1. 追加写入日志文件
        string record = encodeRecord("PUT", key, value)
        file.appendText(dataFile, record)

        // 2. 更新内存索引
        index[key] = value
    end
end

// 使用
KvStore db = KvStore()
db.open("kv_data.log")
db.put("name", "xlang")
db.put("version", "6.0")
db.put("name", "xlang-demo6")   // 覆盖旧值

put 的时间复杂度：O(1) 追加写 + O(1) 哈希表更新。无论数据量多大，写入速度恒定。

54.4 get：读取

func get(string key) as string
    if index.has(key) then
        return index[key]
    end
    return ""   // 不存在返回空串
end

func has(string key) as bool
    return index.has(key)
end

// 测试
assert db.get("name") == "xlang-demo6"   // 最新值
assert db.get("version") == "6.0"
assert db.get("missing") == ""           // 不存在

读取完全在内存中完成——O(1) 哈希查找。这是 Bitcask 的核心优势：读性能与数据量无关。

54.5 delete：删除

func delete(string key)
    if not index.has(key) then return end

    // 1. 写入墓碑记录
    string record = encodeRecord("DEL", key, "")
    file.appendText(dataFile, record)

    // 2. 从内存索引移除
    index.remove(key)
end

// 测试
db.delete("version")
assert db.get("version") == ""
assert not db.has("version")

删除不是"从文件中擦除"——而是追加一条 DEL 记录。恢复时，DEL 记录会覆盖之前的 PUT。这保证了日志的追加写语义不被破坏。

54.6 崩溃恢复

启动时重放日志，重建内存索引：

func recover()
    if not file.exists(dataFile) then return end

    string content = file.readText(dataFile)
    list<string> lines = string.splitLines(content)

    int i = 0
    while i < lines.len()
        string line = lines[i]
        if line.len() == 0 then
            i += 1
            // 跳过空行
        else
            array<string> parts = decodeRecord(line)
            if parts.len() >= 2 then
                string op = parts[0]
                string key = parts[1]
                if op == "PUT" and parts.len() >= 3 then
                    index[key] = parts[2]
                elif op == "DEL" then
                    index.remove(key)
                end
            end
            i += 1
        end
    end

    println("恢复完成: " + index.len().toString() + " 个键")
end

重放是幂等的：同一日志重放多次结果相同。最后一条 PUT/DEL 决定最终状态。

54.7 压缩（Compaction）

日志文件会不断增长（旧版本、已删除的数据仍占空间）。压缩将有效数据重写为新文件：

func compact()
    string tmpFile = dataFile + ".tmp"

    // 将当前有效数据写入临时文件
    string content = ""
    list<string> keys = index.keys()
    int i = 0
    while i < keys.len()
        string key = keys[i]
        content += encodeRecord("PUT", key, index[key])
        i += 1
    end
    file.writeText(tmpFile, content)

    // 原子替换：删除旧文件，重命名新文件
    file.delete(dataFile)
    file.rename(tmpFile, dataFile)

    println("压缩完成: 日志缩减为 " + keys.len().toString() + " 条记录")
end

// 定期压缩（如每 1000 次写入后）
int writeCount = 0
func putWithCompact(string key, string value)
    put(key, value)
    writeCount += 1
    if writeCount >= 1000 then
        compact()
        writeCount = 0
    end
end

压缩的效果：如果同一个 key 被 PUT 了 100 次，日志中有 100 条记录，压缩后只剩 1 条（最新值）。

54.8 TTL 过期

为键设置生存时间：

class KvStoreTtl
    dict<string, string> index
    dict<string, int64> expiry   // key → 过期时间戳

    func putTtl(string key, string value, int ttlMs)
        index[key] = value
        expiry[key] = time.now() + ttlMs
        // 日志中记录过期时间
        string record = "PUT\t" + key + "\t" + value + "\t" + expiry[key].toString() + "\n"
        file.appendText(dataFile, record)
    end

    func get(string key) as string
        if not index.has(key) then return "" end
        // 检查是否过期
        if expiry.has(key) and time.now() > expiry[key] then
            index.remove(key)
            expiry.remove(key)
            delete(key)   // 写入墓碑
            return ""
        end
        return index[key]
    end

    // 后台清理过期键
    func cleanExpired()
        int64 now = time.now()
        list<string> keys = expiry.keys()
        int i = 0
        while i < keys.len()
            if now > expiry[keys[i]] then
                delete(keys[i])
            end
            i += 1
        end
    end
end

54.9 完整实现

// kv.xl — 完整测试
KvStore db = KvStore()
db.open("test_kv.log")

// 基本操作
db.put("user:1", "alice")
db.put("user:2", "bob")
db.put("user:3", "charlie")
db.put("user:2", "bob_updated")

assert db.get("user:1") == "alice"
assert db.get("user:2") == "bob_updated"
assert db.get("user:3") == "charlie"

// 删除
db.delete("user:3")
assert db.get("user:3") == ""

// 模拟重启——重新打开
KvStore db2 = KvStore()
db2.open("test_kv.log")
assert db2.get("user:1") == "alice"
assert db2.get("user:2") == "bob_updated"
assert db2.get("user:3") == ""   // 已删除

// 压缩
db2.compact()

// 压缩后验证
KvStore db3 = KvStore()
db3.open("test_kv.log")
assert db3.get("user:1") == "alice"
assert db3.get("user:2") == "bob_updated"

println("所有测试通过！")

// 清理
file.delete("test_kv.log")

54.10 性能测试

// 写入性能
int64 start = time.now()
int i = 0
while i < 10000
    db.put("key:" + i.toString(), "value:" + i.toString())
    i += 1
end
int64 writeMs = time.now() - start
println("10000 次写入: " + writeMs.toString() + " ms")

// 读取性能
start = time.now()
i = 0
while i < 10000
    string v = db.get("key:" + i.toString())
    i += 1
end
int64 readMs = time.now() - start
println("10000 次读取: " + readMs.toString() + " ms")

// 典型结果（SSD）：
// 10000 次写入: ~50 ms（追加写，顺序 I/O）
// 10000 次读取: ~2 ms（纯内存哈希查找）

深入细节

⚠️ 常见错误

本章小结

复习题

1. 为什么追加写比随机写快？这对 HDD 和 SSD 分别意味着什么？
2. 删除操作为什么不能直接从文件中擦除数据？
3. 墓碑记录（tombstone）的作用是什么？压缩时如何处理？
4. 恢复时为什么必须按顺序重放所有记录？
5. Bitcask 的内存限制是什么？10 亿个键需要多少内存？
6. 压缩期间如何保证不丢失新写入的数据？
7. TTL 的惰性检查和主动清理各有什么优缺点？
8. 如果值中包含换行符，文本格式会出什么问题？如何解决？

编程练习