概念篇

项目二：基于 LSM-tree 的 NoSQL KV 存储引擎 —— 零基础超详细教程

零基础友好可运行代码逐行精讲

项目二：基于 LSM-tree 的 NoSQL KV 存储引擎 —— 零基础超详细教程

这篇教程怎么用

笔记写给完全零基础的你。我们假设你没写过任何代码，没听过 LSM-tree，甚至不知道"存储引擎"四个字是什么意思。没关系，这篇教程从"通讯录"讲起，一步一步带你把这个项目吃透。读完之后，你不仅能自己敲出代码，还能在面试里把面试官问倒。

我们先把话说清楚。这个项目是简历上的第二个项目，目标是投大厂的存储岗或者数据库内核岗实习。这类岗位最看重什么？不是你背了多少八股文，而是你能不能把"一个写请求从进来到落盘"这件事讲得明明白白。

所以这篇教程的讲法比较特别：

  1. 任何一个概念，我们都先讲"最笨的做法"，看它怎么失败，再引出聪明的做法。
  2. 任何一个术语，第一次出现时都给出英文全称和中文解释。
  3. 任何一段代码，我们都逐行讲，每一行是什么意思、为什么这么写。
  4. 例子全是生活化的：抖音点赞、小红书评论、微信步数、DeepSeek 历史对话、游戏存档。

你可以慢，但不要跳。每一部分都是后一部分的地基。

第〇部分：KV 存储到底是什么

从通讯录讲起

打开你手机里的通讯录。你搜"老妈"，跳出来一个电话号码。你搜"老王"，跳出来另一个电话号码。

我们把这件事抽象一下：

一个 key 配一个 value，合起来叫一个 key-value pair（键值对，简称 KV 对）。你查通讯录，本质就是拿着 key 换 value。就这么简单，这就是 KV 存储的全部本质。

再换一个例子。假设我们在做一个小系统，存学生的成绩：

这就是一个最朴素的 KV 存储：你给我学号，我还你这个人是谁、考了多少分。

大厂的真实场景

你可能会问：就这？这有什么好做的？我们来看真实世界的场景，你会发现 KV 存储无处不在。

比如抖音。你刷到一个视频，点了个赞。抖音的服务器要记下来：用户12345 点赞了视频v888、v889、v900。怎么存？最自然的存法就是：

又比如微信步数。你的手机每几分钟上报一次步数。微信要存：

再比如 DeepSeek 的历史对话。你点开左侧某个会话，要加载整段聊天记录。存的可能是：

还有游戏存档。key 是"player:9527:save:slot1"，value 是一大块存档数据，等级、背包、地图进度全在里面。

看出来了吗？这些场景有一个共同点：查询永远是"拿着一个确定的 key，取回它对应的 value"。没有人会说"把点赞数大于 100 并且注册时间早于去年的用户和小红书评论表做个关联查询"。没有这种事。

NoSQL 是什么意思

这里要引出第一个大词：NoSQL。

我们先用一句话说清它要反对的对象：关系数据库（Relational Database），比如 MySQL。关系数据库把数据放在一张张"表"里，表有行有列，表和表之间可以用 JOIN（连接）操作拼起来查。它很强大，但也很重。

NoSQL 字面上是"Not Only SQL"（不仅仅是 SQL），你可以理解成"我们不要表、不要 JOIN、不要复杂的查询语言，我们只要最简单最快的存取"。

一个 KV 存储引擎，对外只提供三个动作，记住这三个词，面试必考：

  1. get(key)：给我这个 key 对应的 value。
  2. put(key, value)：把这个 key 和这个 value 存进去。如果 key 已存在，就覆盖旧值。
  3. delete(key)：把这个 key 删掉。

没有表，没有 JOIN，没有 WHERE 条件，没有排序查询。就这三个动作。听起来很弱对吧？但正因为动作少，引擎内部可以针对这三个动作优化到极致，单机每秒扛几十万次写入。这就是"少即是多"。

为什么大厂要自己造 KV 引擎

现成的 MySQL 不能用吗？能，但不合适。MySQL 为了支持复杂的 SQL 查询，内部做了很多 KV 场景根本用不到的事情，这些全是开销。抖音一天新增的点赞记录是百亿级别的，用 MySQL 硬扛，机器数量要翻好几倍，成本爆炸。

所以业界专门做了一类"KV 存储引擎"。你不需要现在就会用它们，但名字一定要能说出来，面试时提到这些名字，面试官就知道你了解生态：

  1. Redis：内存 KV 存储，数据主要放内存里，快如闪电，常用来做缓存。
  2. LevelDB：Google 开源的单机 KV 存储引擎，就是我们这个项目要对标的东西，它的核心就是 LSM-tree。
  3. RocksDB：Facebook（现在叫 Meta）基于 LevelDB 改造的高性能版本，工业界用得最广，很多大厂的数据库底层都是它。

我们这个项目，说白了就是"自己动手写一个简化版的 LevelDB"。你把这句话写在简历上，懂行的面试官眼睛会亮一下。

本部分小结

下一部分，我们从零开始造它。先造一个最笨的版本，然后看它怎么死。

第一部分：最朴素的存储为什么不行

这一部分是整个项目的"灵魂发源地"。LSM-tree 这个听起来很高大上的东西，本质上就是为了解决两个朴素方案的致命缺陷而被逼出来的。你一定要体会这个"被逼出来"的过程。

方案一：全放内存哈希表

最直觉的想法来了。既然就是"拿 key 换 value"，那我们用哈希表（Hash Table）不就行了？

哈希表你可以理解成一本"按拼音排好的词典"：给它一个词，它几乎一瞬间就能翻到那一页。用专业一点的话说，它的查找时间复杂度（Time Complexity，衡量算法随数据量增长变慢的程度的指标）是 O(1)，读作"大 O 一"，意思是"不管数据有一万条还是十亿条，查一次花的时间基本不变"。

我们用 C++ 写一下这个最笨的版本。别慌，每一行我们都会讲。

C++
#include <string>             // 引入字符串类型 string
#include <unordered_map>      // 引入哈希表类型 unordered_map

class NaiveKV {               // 定义一个类（class），类就是"一种我们自己发明的数据类型"，把数据和操作打包在一起
private:
    std::unordered_map<std::string, std::string> table_;  // 哈希表：key 是字符串，value 也是字符串
public:
    void put(const std::string& key, const std::string& value) {
        table_[key] = value;  // 把 key -> value 塞进哈希表，已存在就覆盖
    }

    bool get(const std::string& key, std::string& value) {
        auto it = table_.find(key);   // 在哈希表里找 key，auto 意思是"类型让编译器自己猜"
        if (it == table_.end()) {     // end() 表示"找到了表尾还没找到"，也就是不存在
            return false;             // 没找到，返回 false
        }
        value = it->second;           // it->second 是找到的那个 value（it->first 是 key）
        return true;                  // 找到了，返回 true
    }

    void del(const std::string& key) {
        table_.erase(key);            // 从哈希表里删掉这个 key
    }
};

逐行过一遍要点：

  1. #include <string>：C++ 里要用"字符串"这种类型，必须先引入它的定义，就像用微波炉前先插上电源。
  2. class NaiveKV：class（类）是 C++ 的核心语法，意思是"我发明一种新类型，它里面装了一些数据（这里是 table_），还配了几个操作数据的函数（put/get/del）"。之后我们可以写 NaiveKV db; 来造一个具体的对象（object，类的实例）。
  3. std::unordered_map<std::string, std::string> table_;：这一行声明了一个哈希表。std:: 是命名空间前缀，表示"这是标准库里的东西"。unordered_map 就是 C++ 标准库提供的哈希表。两个 <std::string> 分别说明 key 和 value 都是字符串。table_ 末尾的下划线是习惯写法，表示"这是类的内部成员，外人别碰"。
  4. void put(...)：定义一个函数。void 意思是"这个函数不返回任何结果"。参数里的 const std::string& key 有两层讲究：& 表示引用（reference），意思是"不把字符串复制一份，直接传原件，省得拷贝浪费时间"；const 表示"我保证在这个函数里不修改它"。这是 C++ 里传字符串的标准姿势，面试可能问。
  5. table_[key] = value;：哈希表的写入语法，方括号里放 key。
  6. auto it = table_.find(key);：find 返回一个迭代器（iterator，可以理解为"指向表里某个格子的指针"）。auto 让编译器自动推断类型，不用我们写一长串类型名。
  7. it->second：迭代器指向一个"格子"，格子里有 key（first）和 value（second）两半。

好，这个版本能用吗？能，而且飞快。每秒上百万次读写不在话下。但是，它有一个致命的缺陷：

断电就全没了。

哈希表存在内存（RAM, Random Access Memory，随机存取存储器）里。内存的特点是：快，但断电后数据全部蒸发。想象一下，抖音用这台机器存点赞记录，机房租用的服务器跳闸重启了一下，全国人民今天的点赞全没了。这是事故，是要上新闻的。

所以第一个朴素方案失败了。它引出了存储系统的头号刚需：持久化（Persistence）—— 数据必须写到断电也不会丢的地方去。

断电不会丢的地方是哪里？磁盘（Disk）。包括机械硬盘（HDD, Hard Disk Drive）和固态硬盘（SSD, Solid State Drive）。程序关了、机器重启了，磁盘上的文件还在。

方案二：每次 put 都直接改文件

好，那我们持久化。第二个朴素想法：每次 put，就把 key 和 value 写进磁盘上的一个文件里。

听起来问题解决了一半。但马上有一个细节冒出来：写进文件的什么位置？

如果是个新 key，追加到文件末尾就行。但如果这个 key 已经存在了呢？比如"学号51"原来存的是"小明，数学135分"，现在老师改分了，要改成"138分"。我们得找到文件里原来那条记录的位置，把旧内容改掉。

这就叫随机写（Random Write）：写到文件的一个不确定的、要靠"找"才能确定的位置。与之相对的是顺序写（Sequential Write）：永远往文件末尾追加，写到哪算哪。

这两种写法，速度差别有多大？这里用具体数字钉死，这组数字你以后在面试里可以直接报：

差了大约 100 倍。 在机械硬盘上甚至能差到几百上千倍。SSD 会好一些，但随机写（尤其是大量小块随机写）依然比顺序写慢很多，而且还会加速 SSD 磨损。

为什么随机写这么慢？用机械硬盘讲最直观：磁盘里面有一个盘片在转，有一个磁头像唱片机的唱针一样架在上面。顺序写就是磁头不动，盘片转一圈，数据像流水一样写过去。随机写是每写一小块，磁头都要"咔哒"一声挪到另一个位置，这个物理移动要花毫秒（millisecond，千分之一秒）级别的时间。写 1 万次，就要挪 1 万次。时间都花在"挪"上了。

好，现在算一笔账。抖音假设一天新增 100 亿条点赞记录。如果我们用"方案二"的随机写，每条都要在磁盘上找到旧位置改写，按 1 MB/s 的速度，一台机器一天最多写几千万条，得堆几千台机器。而顺序写 100 MB/s，几十台机器就够了。这中间是真金白银的服务器成本差距。

所以第二个朴素方案也失败了。它失败在"每次写入都要随机定位、就地修改"。

全文之魂：把一切写都变成顺序追加

两个方案失败的教训摆在一起：

  1. 方案一教训：数据必须落磁盘，内存靠不住。
  2. 方案二教训：落磁盘可以，但千万别随机写，要顺序写。

那么，有没有一种设计，能让"所有的磁盘写入"都变成"往文件末尾追加"的顺序写？

有的。这就是 LSM-tree 的核心思想，也是这篇教程的"全文之魂"。我把它写成一句话，你可以抄在笔记本上：

永远不在磁盘上就地修改任何数据。每一次写入、每一次修改、每一次删除，都变成一次"往某个文件末尾追加一条新记录"的顺序写。

这句话乍一听很反直觉。你可能立刻会冒出一堆问题：

  1. 不改旧数据？那同一个 key 写两次，磁盘上岂不是有两条记录？是的，确实有两条。后面靠 Compaction（合并压缩）清理。
  2. 那删除怎么做？不能就地删，难道……写一个"这条已删除"的标记追加进去？完全正确，这叫墓碑（Tombstone），第五部分细讲。
  3. 数据东一条西一条地追加，读的时候怎么找？问得好，这就是 LSM 要用一整套结构（MemTable、SSTable、布隆过滤器）去解决的问题。

你看，后面要学的所有东西，全是为了把"顺序追加"这一个思想落地而发明的配套工具。这就是 LSM-tree（Log-Structured Merge-tree，日志结构合并树）。名字里的"Log-Structured"（日志结构）说的就是"像记日志一样只追加"，"Merge"（合并）说的是"定期收拾这些追加出来的碎片"。

本部分小结

下一部分，我们解决第一个配套问题：程序崩了怎么办？数据写到一半断电了怎么办？答案是 WAL。

第二部分：WAL，写前日志

先抛问题：内存和磁盘之间的"危险空窗期"

回忆一下上一部分的核心思想：写要快，所以数据先写进内存里的结构（后面叫 MemTable），攒一批再一次性顺序刷到磁盘。这个设计很美好，但有一个致命的空窗期：

假设用户调用 put("user:12345:likes", "[v888]")。引擎把这条记录写进了内存。内存写入成功了，引擎回复用户"OK，存好了"。

就在这时，机房断电。内存里的数据蒸发。用户明明收到了"OK"，数据却没了。

这在存储系统里是绝对不能接受的。你回复了"OK"，就是立了字据，数据就必须在。那怎么办？最笨的做法是：每次 put 都立刻把整个内存结构刷到磁盘。但这又回到了"频繁小块写磁盘"的老路，快不起来。

类比：记账先记流水本

解决办法来自一个古老的行业：记账。

假设你是清朝的账房先生。铺子里一天几百笔生意。你有两个本子：

现在假设：下午铺子失火，总账本和流水本抢出来了，但你脑子里的"谁刚付了钱"全忘了。有关系吗？没有。因为每一笔生意都先落在流水本上，照着流水本重新誊一遍，总账就能恢复原样。

WAL（Write-Ahead Log，写前日志）就是那个流水本。它的规矩只有一条：

任何修改，先追加到 WAL 文件（磁盘上，顺序写），再改内存。

注意它完美符合"全文之魂"：WAL 只追加，从不修改，是纯顺序写，100 MB/s 那种快。

WAL 文件长什么样

WAL 就是一个普通文件，里面一条一条排着操作记录。比如：

C++
PUT user:12345:likes [v888]
PUT user:67890:steps:2026-10-16 8342
DEL user:11111:likes
PUT conv:abc123 [你:你好; AI:你好呀]

每一行就是一次操作：动作（PUT 或 DEL）+ key + value。追加一行，磁盘上就多一行。真实的实现里会用二进制格式并带上校验和（Checksum，一段用来验证数据没损坏的指纹），但思想完全一样。

完整流程：一次 put 的"三步走"

我们把一次 put 从头到尾走一遍，假设用户写入 put("学号51", "小明，数学135分")：

  1. 第一步：引擎把这行操作追加到 WAL 文件末尾，并且确保它真的落盘了（这里有一个细节，操作系统为了快会先把写攒在缓冲区里，我们要调用一个"强制落盘"的指令，C++ 里是 flush 或更底层的 fsync，把它逼到磁盘上）。
  2. 第二步：把这条记录写进内存的 MemTable（第三部分的主角，先记住名字）。
  3. 第三步：回复用户"OK"。

注意顺序：先 WAL，后内存。这就是"写前"两个字的含义——在修改任何东西之前，先把日志写好。

为什么"先写日志再写内存"来得及

你可能会嘀咕：写内存不是纳秒（nanosecond，十亿分之一秒）级别的事吗，先写磁盘再写内存，会不会"日志写了但内存还没写就崩了"？

会的，但没关系。崩溃恢复时我们只认 WAL。WAL 里有这条记录，恢复时就把它重放进内存。也就是说，内存里的内容随时可以用 WAL 重建，WAL 才是唯一的"真相来源"。内存崩没了？WAL 重放一遍，MemTable 原样回来。

反过来，如果顺序颠倒，先写内存再写 WAL，那么"内存写了、WAL 还没写"的间隙断电，这条数据就永远丢了。所以顺序绝不能反。这是存储系统的一条铁律。

崩溃恢复完整走一遍

我们演一遍崩溃恢复的完整剧本：

  1. 白天，引擎正常跑。WAL 文件里攒了 5 万行操作记录，MemTable 里也有对应的 5 万条数据。
  2. 下午三点，断电。MemTable 蒸发，WAL 在磁盘上安然无恙。
  3. 三点零五分，机器重启，引擎启动。启动时它做的第一件事就是：打开 WAL 文件，从头到尾一行一行读，每读到一行就在新建立的 MemTable 里重放（replay）一次——读到 PUT 就插入，读到 DEL 就标记删除。
  4. 5 万行重放完，MemTable 恢复到了断电前一模一样的状态。引擎开门营业。

整个过程对用户完全透明。用户甚至不知道机器崩过。

WAL 的代码长这样

我们看一段极简的 WAL 写入代码：

C++
#include <fstream>   // 引入文件流，用来读写文件
#include <string>

class Wal {
private:
    std::ofstream file_;   // ofstream = output file stream，输出文件流，专门用来往文件里写东西
public:
    explicit Wal(const std::string& path) {
        // explicit 是"禁止隐式转换"的意思，先不管细节，记住这是好习惯
        file_.open(path, std::ios::app);  // ios::app = append，追加模式：永远写在文件末尾，绝不覆盖旧内容
    }

    void append(const std::string& op, const std::string& key, const std::string& value) {
        file_ << op << " " << key << " " << value << "\n";  // 把一行记录写进文件，像往流水本上加一行
        file_.flush();  // 强制把缓冲区的内容立刻推到磁盘，防止"以为写了其实还在内存缓冲区里"
    }
};

逐行讲：

  1. std::ofstream file_;：声明一个"输出文件流"对象。你可以把它想象成一支对着文件写字的笔。
  2. file_.open(path, std::ios::app);：打开文件。关键在 std::ios::app（append，追加）。这个标志位告诉操作系统："我写的内容一律追加到文件末尾。"这就从代码层面保证了 WAL 是纯顺序写。如果不加这个标志，默认行为是"从头开始写，旧内容被覆盖"，流水本就被毁了。
  3. file_ << op << " " << key << ...：<< 在 C++ 里除了是数学符号，还可以表示"往流里送数据"。这一行就是把 op、空格、key、空格、value、换行符依次送进文件。
  4. file_.flush();：这一行至关重要。操作系统为了效率，会把你的写先攒在内存缓冲区里，攒够一批才真正写盘。如果不 flush，断电时缓冲区里没来得及落盘的那几行就丢了。flush 就是"别攒了，现在就写"。（真实项目里会用更强力的 fsync 确保写到物理介质，面试时提一嘴是加分项。）

WAL 什么时候可以扔掉

WAL 不能无限长。回忆记账的类比：流水本誊到总账之后就可以撕掉。同理，当 MemTable 里的数据真正刷成了磁盘上的 SSTable（第四部分讲），这些数据的持久化就由 SSTable 接管了，对应的 WAL 就可以删掉。所以 WAL 的生命周期是：随 MemTable 出生，随 MemTable 落盘而死。

本部分小结

下一部分，我们进内存，看看 MemTable 用什么结构存数据，以及那个著名的"跳表"是怎么回事。

第三部分：MemTable 与跳表

MemTable 是什么

WAL 保证了"崩了能恢复"，但数据平时在内存里住在哪？答案是 MemTable（Memory Table，内存表）。

MemTable 就是一块内存里的数据结构，负责接待所有新写入的数据。但它有一个和普通哈希表不一样的硬性要求：里面的数据必须按 key 有序排列。

为什么要有序？先记住结论：因为 MemTable 攒满之后要整个刷到磁盘上变成 SSTable（第四部分），而 SSTable 要求数据有序，有序才能二分查找（Binary Search，在有序数据里每次砍掉一半候选范围的查找方法）。所以 MemTable 从数据进来的第一刻起就保持有序，落盘时直接按顺序倒出去，一行都不用整理。

那么问题变成：内存里"既能快速插入、又能保持有序"的结构，用什么？

候选一：有序数组，为什么不行

最直觉的想法：数组（Array，一块连续的内存，元素紧挨着排）。比如存学号，按从小到大排：51、52、53、57、60。

查找很快，二分查找，O(log n)。但插入呢？假设要插入"54"，它得排在 53 和 57 之间。数组中间没有空位，怎么办？把 57、60 全体往后挪一格。挪数据是 O(n) 的操作，n 是数据条数。MemTable 里有几十万条数据时，每插一条就挪几十万个元素，写入直接卡死。有序数组，淘汰。

候选二：有序链表，插入快了但查找慢了

第二种想法：链表（Linked List）。链表的每个元素（叫节点，Node）除了装数据，还装一个"指向下一个节点的指针"。指针（Pointer）就是"记录着另一个东西在内存里地址"的变量，像一张写着门牌号的纸条。

链表的插入很快：找到位置，把前后两根指针改一下，O(1)。但查找是灾难：链表不支持二分，因为第 n 个节点在哪没法直接算出来，只能从头一个挨一个地爬。找"学号60000"可能要从头爬 6 万步。O(n)，淘汰。

跳表登场：给链表修"快车道"

现在轮到主角了：跳表（Skip List）。它的想法朴素得可爱：链表查找慢，是因为只能一层一层爬。那我们给它修几层快车道，让它能跳着走。

我们一步一步搭出来。

第一层（最底层）：就是一条普通的有序链表。假设存了 8 个 key：

C++
1 -> 3 -> 7 -> 9 -> 12 -> 15 -> 19 -> 21

第二层：从底层抽一些节点出来（比如每隔一个抽一个），再拉一条链，这就是快车道：

C++
1 --------> 7 --------> 12 --------> 19
1 -> 3 -> 7 -> 9 -> 12 -> 15 -> 19 -> 21

第三层：再抽，更稀疏，更快：

C++
1 ------------------> 12
1 --------> 7 --------> 12 --------> 19
1 -> 3 -> 7 -> 9 -> 12 -> 15 -> 19 -> 21

这就是一个三层跳表。越上层越稀疏，车越快；最底层是全量数据。

查找像坐高铁：用具体数字走一遍

假设我们要找 key = 15。过程是这样的，你跟着手指在图上走：

  1. 从最顶层的头节点 1 出发。顶层下一个节点是 12，12 比 15 小，可以坐。于是我们到了 12。
  2. 在顶层，12 的下一个节点没有了（到头了）。不能前进了，下一层。
  3. 在第二层，从 12 出发，下一个是 19，19 比 15 大，坐过了，不能走。下一层。
  4. 到了最底层，从 12 出发，下一个就是 15。找到了！

数一数：我们一共比较了 4 次左右。如果在纯链表上从 1 爬到 15，要爬 5 步以上，而且数据越多差距越夸张。跳表的查找复杂度是 O(log n)，和二分查找同级别。有了一百万条数据，纯链表平均要爬 50 万步，跳表只要大约 20 步。

这就是"先坐高铁到大站，再换慢车到小站"。每一层都是一条链表，但越往上站越少，跳得越远。

插入怎么做：抛硬币决定楼层

插入新节点时，先像查找一样找到它该待的位置，插进最底层。然后抛硬币：正面，就给它盖第二层；再抛，又是正面，盖第三层；直到抛出反面为止。这样每个节点有 1/2 概率有第二层，1/4 概率有第三层，以此类推。长期来看，楼层分布自然就稀疏合理了，不需要任何全局调整。这是跳表最优雅的地方：用随机性代替复杂的平衡操作。

为什么不用红黑树

面试官可能问：内存里有名气的有序结构多了，红黑树（Red-Black Tree，一种能自我保持平衡的二叉查找树，C++ 的 std::map 底层就是它）为什么不用？

点到为止的回答：红黑树为了保持平衡，插入时要"旋转"树的结构，这些旋转会同时牵动多个节点。在多线程（Multithreading，多个执行流同时干活）环境下，要给这些节点上锁，锁的粒度不好控制，容易成为性能瓶颈。而跳表的插入只影响少数几个节点的指针，用无锁（lock-free）编程技巧就能做到很高的并发度。LevelDB 和 Redis 的有序集合都选了跳表，就是这个原因。面试答到这里就够了，不用展开。

MemTable 写满了怎么办：冻结

内存是有限的。MemTable 不能无限吃下去。我们给它设一个大小上限，比如 4MB（LevelDB 的默认值就是这个量级）。

当 MemTable 攒到 4MB，怎么办？直接拒绝写入吗？不行，用户的写不能停。

做法是"冻结"：把这个写满的 MemTable 原地封存，它从此刻起变成 Immutable MemTable（不可变内存表）——Immutable 就是"不可修改的"意思，它不再接受任何新写入，只等着被后台线程刷到磁盘。同时，引擎立刻新建一个空的 MemTable，继续接待新写入。

你可以类比成餐厅的叫号小票：一本小票撕满了，先钉起来交给后厨（后台刷盘），柜台上立刻换一本新的接着撕（新 MemTable 接着写）。顾客（用户）完全无感。

这个设计里有两个重要推论，先记下来，第八部分会用到：

  1. 同一时刻，最多只有一个可写的 MemTable，但可能有若干个 Immutable MemTable 排队等刷盘。
  2. 因为 Immutable MemTable 不会再变，后台线程刷它的时候不需要加锁，前台写入完全不受刷盘影响。读写不互相卡，这是 LSM 写快的一个小秘诀。

跳表节点代码逐行讲

我们看一个跳表节点的极简定义：

C++
#include <string>
#include <vector>     // 引入 vector，可变长数组

struct Node {                          // struct 和 class 几乎一样，默认成员公开，常用来定义"纯数据"的类型
    std::string key;                   // 这个节点存的 key
    std::string value;                 // 这个节点存的 value
    std::vector<Node*> forward;        // forward[i] 是"第 i 层的下一个节点"的指针

    Node(const std::string& k, const std::string& v, int level)
        : key(k), value(v), forward(level, nullptr) {}  // 构造函数：创建节点时初始化所有成员
};

逐行讲：

  1. struct Node { ... };：定义一个叫 Node 的类型。以后每写一个 key，就 new 一个 Node 出来。
  2. std::string key; / std::string value;：节点里装的货。
  3. std::vector<Node*> forward;：这是全段最需要解释的一行。vector 是 C++ 的可变长数组，可以理解成"一个会自动扩容的列表"。Node* 里的星号表示指针，也就是说 forward 是一个"装着一堆指向其他 Node 的指针"的列表。forward[0] 是这个节点在第 0 层（最底层）指向的下一个节点，forward[1] 是第 1 层的下一个节点，以此类推。一个节点有几层楼，这个列表就有几个元素。
  4. Node(const std::string& k, ...)：构造函数（Constructor），创建对象时自动执行的初始化函数。冒号后面那串 : key(k), value(v), forward(level, nullptr) 叫初始化列表，意思是"用 k 初始化 key，用 v 初始化 value，把 forward 建成一个有 level 个元素的列表，每个元素先填 nullptr"。nullptr 是空指针，表示"暂时谁也不指向"。

本部分小结

下一部分，Immutable MemTable 刷到磁盘之后变成什么？SSTable。我们终于要上磁盘了。

第四部分：SSTable，排序字符串表

落盘后的文件长什么样

Immutable MemTable 攒满了，后台线程把它刷到磁盘。刷出来的文件就叫 SSTable（Sorted String Table，排序字符串表）。名字翻译过来就是"一个按 key 排好序的字符串表"，它的内容就是一堆排好序的 KV 对。

因为 MemTable 里本来就是有序的（跳表嘛），刷盘就是"从最小的 key 开始，一个接一个写到文件里"。这又是一整段从头到尾的顺序写。看到了吗，又符合全文之魂。

一个 SSTable 文件的内部结构，我们拆开看。它主要分两大部分：

第一部分是数据区。数据区切成一个个数据块（Data Block），每块几 KB，比如 4KB。块里面就是按 key 排好序的 KV 对，一条挨一条：

C++
数据块1: 学号01→张三 | 学号02→李四 | ... | 学号50→王五
数据块2: 学号51→小明，数学135分 | 学号52→小红 | ...
数据块3: ...

第二部分是索引区，放在文件末尾。索引块（Index Block）里存的是"每个数据块从哪个 key 开始、在文件的第几个字节"。像书的目录：

C++
索引块: 学号01 → 块1在文件第0字节 | 学号51 → 块2在文件第4096字节 | ...

在 SSTable 里查一个 key：三步走

假设 SSTable 里有 100 万条数据，我们要查"学号51"。流程是：

  1. 第一步：读索引块（它很小，通常还能缓存在内存里）。在索引里二分查找，发现"学号51"落在"块2"的范围内。
  2. 第二步：按索引说的位置，直接跳到文件第 4096 字节，把块2（4KB）整块读进内存。注意，我们只读了这一个块，没有碰其他 99% 的数据。
  3. 第三步：在块2里再二分查找，找到"学号51 → 小明，数学135分"。

整个过程只发生了一次磁盘读（读块2那一下）。100 万条数据里定位一条，只读 4KB。这就是"有序"的威力。

为什么有序这么重要：再钉一次数字

如果 SSTable 里数据是无序的，查一个 key 就得从头扫到尾。100 万条数据，哪怕一条只占 50 字节，也是 50MB 的顺序扫描，按 100MB/s 算要 0.5 秒。用户在抖音点开点赞列表等 0.5 秒才转圈完？体验直接崩。

有了有序加索引加二分：一次 4KB 的磁盘读，几十微秒（microsecond，百万分之一秒）的事。从"半秒"到"几十微秒"，差了一万倍。这就是为什么 MemTable 从第一天起就要保持有序——所有的有序，都是为了这一刻。

SSTable 是不可变的

记住 SSTable 的一条铁律：一旦写完，永不修改。它是个只读文件。想改数据？没门，你只能往更新的 SSTable 里写一条新记录。这条铁律带来两个大好处：

  1. 实现简单。不用考虑"边读边改"的并发问题，读 SSTable 完全不用加锁。
  2. 缓存友好。文件不变，读过的块可以放心缓存在内存里，下次直接命中。

那旧数据、重复数据、已删除的数据怎么办？全都交给下一部分的主角：Compaction。

第五部分：Compaction，合并压缩

碎纸片问题

我们推演一下系统跑一个月之后的样子。每写满一个 4MB 的 MemTable 就产出一个 SSTable 文件。一天产出 100 个，一个月就是 3000 个 SSTable 文件躺在磁盘上。

这带来两个大麻烦：

  1. 读变慢。查一个 key，最坏情况要把 3000 个文件挨个问一遍"你这里有吗"。本来读一次磁盘的事，变成读 3000 次。
  2. 空间浪费。同一个 key 可能改了 10 次，10 个旧版本全留着。删掉的数据也还躺在文件里占地方。

类比一下：你有个坏习惯，每天把待办事项随手写在碎纸片上，扔抽屉里。一个月后抽屉里 3000 张碎纸片，找一张"上周三要交的作业"得翻一下午。

装订成册：Compaction 做的事

解决办法就是定期整理：把若干张碎纸片拿出来，装订成一本册子，旧的碎纸片扔掉。这就是 Compaction（合并压缩）。

Compaction 具体做三件事，每一件都要讲透：

第一件事：合并排序。把几个 SSTable 文件读出来，它们各自内部是有序的，把它们像洗牌一样归并（Merge）成一个更大的、依然有序的 SSTable。K 个有序序列合并成一个有序序列，有个经典算法叫多路归并（K-way Merge），每一轮从 K 个序列的当前最小值里挑最小的那个输出。

第二件事：去重，只留最新版本。合并时如果发现同一个 key 在多个文件里出现，只保留最新的那条（LSM 里每条记录带一个递增的序列号（Sequence Number），谁大谁新），旧版本直接扔掉。

第三件事：扔掉墓碑。下面细讲。

墓碑：删除的反直觉真相

现在回答第一部分埋下的问题：不能就地修改，那 delete 怎么做？

答案是反直觉的，请你瞪大眼睛：删除一个 key，不是把它擦掉，而是写入一条特殊的"删除标记"。 这个标记就叫墓碑（Tombstone，墓碑）。

为什么？因为旧数据躺在旧的 SSTable 里，而 SSTable 不可修改，够不着。我们唯一能做的就是追加。所以我们追加一条记录："学号51，已删除"。这条墓碑像新数据一样走完整条流水线：进 WAL、进 MemTable、刷成 SSTable。

那么读的时候怎么办？查"学号51"，引擎从新到旧找，先碰到墓碑，一看"哦，这个 key 被删了"，立刻返回"不存在"。哪怕更老的 SSTable 里还躺着"学号51→小明"的旧数据，也没关系，墓碑说了算。

墓碑自己也不能永远留着，不然删除的东西还是占空间。所以 Compaction 的第三件事就是：合并时遇到墓碑，如果这个 key 在更老的层里已经没有任何副本了，就把墓碑和所有旧版本一起物理删除。到这里，"学号51"才真正地、从磁盘上消失了。

所以一次 delete 的完整生命是：写墓碑 → 读时被墓碑挡住 → Compaction 时连墓碑带旧数据一起清理。面试很爱考"LSM 怎么删除数据"，你就把这三步背给他听。

多层结构：L0、L1、L2

如果所有 SSTable 都堆在一层，Compaction 一次要合并全部文件，动静太大。所以 LSM 把 SSTable 分成多个层级（Level）：

数据的生命轨迹就是：出生在 MemTable，刷到 L0，然后通过一次次 Compaction 慢慢往下沉，L0 到 L1，L1 到 L2，越沉越老、越稳定。

写放大：LSM 的代价

天下没有免费的午餐。LSM 写入快，代价就藏在 Compaction 里。

算一笔账：你调用一次 put，写入 1KB 数据。这 1KB 先是进了 MemTable、刷到 L0（写了 1 次）。后来 L0 满，它和几个文件合并进 L1，你的这 1KB 又被读出来、写进去（写了第 2 次）。再后来 L1 到 L2，又写一遍（第 3 次）。一路沉到最底层，这 1KB 数据可能被实际写入磁盘好几次。

这个现象叫写放大（Write Amplification）：用户写一次，磁盘实际写了 N 次。N 通常在几到几十之间，取决于层数和合并策略。

写放大是 LSM 结构的固有代价。它换来的是用户写入路径上的极致顺序化。公平的交易：前台用户感觉飞快，后台线程默默承担反复搬运的成本。记住这句话，第七部分总结时还要用。

本部分小结

下一部分，我们解决"读的时候要翻好几层，能不能少翻点"的问题。主角是布隆过滤器，一个精巧到让人拍案的小结构。

第六部分：布隆过滤器

先抛问题：查一个不存在的 key 有多贵

场景来了。恶意用户或者爬虫疯狂调用 get("不存在的key")。我们的引擎怎么办？

按现在的设计，get 的查找路径是：先查 MemTable，再查 Immutable MemTable，再一层层查 SSTable（L0、L1、L2……）。每一层 SSTable 都要做一次"读索引、读数据块"的磁盘 I/O（Input/Output，输入输出，这里指磁盘读写）。假设有 5 层，就是 5 次磁盘 I/O。最后结论：不存在。

白白读了 5 次磁盘，就为了说"没有"。磁盘 I/O 是系统里最贵的操作，一次几微秒到几毫秒。如果有人恶意刷不存在的 key，磁盘直接被打爆。这叫"读穿透"，是真实线上系统天天要防的事。

类比：小区门口的访客名单

解决办法的类比非常生活化。你去小区找朋友，门口保安有个访客登记名单：

这个名单就是布隆过滤器（Bloom Filter，布隆过滤器，1970 年一个叫 Bloom 的人发明的）。它的规矩是：

  1. 名单说"没有"，那就一定没有。放心掉头。
  2. 名单说"有"，那不一定真有，得进去确认一下。

每个 SSTable 配一个布隆过滤器，存在内存里，几 KB 大小。查 key 之前先问它，它说没有就跳过这个文件，磁盘碰都不碰。

原理：位数组 + 哈希函数

布隆过滤器的结构简单到难以置信，就两样东西：

  1. 一个位数组（Bit Array）：一排格子，每个格子只能是 0 或 1。全部初始化为 0。
  2. 几个哈希函数（Hash Function）：哈希函数就是"随便给它一个字符串，它吐出一个数字"的机器，同一个字符串永远吐出同一个数字。

规则：插入一个 key 时，用每个哈希函数各算出一个数字，把数字对数组长度取余，得到一个格子位置，把那个格子置为 1。查询时同样算出这些位置，如果所有位置都是 1，说"可能有"；只要有一个位置是 0，说"一定没有"。

手算小例子：8 位数组 + 2 个哈希函数

我们用一个超小的例子手算一遍。位数组只有 8 格（编号 0 到 7），两个哈希函数 h1 和 h2。

初始状态：

C++
位置:  0  1  2  3  4  5  6  7
值:    0  0  0  0  0  0  0  0

插入 "alice"。假设 h1("alice") = 10，10 对 8 取余得 2；h2("alice") = 15，15 对 8 取余得 7。把位置 2 和位置 7 置为 1：

C++
位置:  0  1  2  3  4  5  6  7
值:    0  0  1  0  0  0  0  1

插入 "bob"。假设 h1("bob") = 3，余 3；h2("bob") = 12，余 4。把位置 3 和位置 4 置为 1：

C++
位置:  0  1  2  3  4  5  6  7
值:    0  0  1  1  1  0  0  1

现在查询 "carol"。假设 h1("carol") = 20，余 4；h2("carol") = 41，余 1。检查位置 4 和位置 1：位置 4 是 1，但位置 1 是 0。有一个是 0，结论：carol 一定不存在。直接返回，不碰磁盘。你看，carol 确实没被插入过，判断正确。

再来一个会出错的查询，查 "dave"。假设 h1("dave") = 26，余 2；h2("dave") = 31，余 7。检查位置 2 和位置 7：都是 1。结论：dave "可能存在"。但 dave 根本没插入过！位置 2 和 7 是被 alice 点亮的，dave 只是凑巧撞上了。这就是误判。

假阳性，以及为什么没有假阴性

上面 dave 的情况叫假阳性（False Positive）：实际不存在，但过滤器说"可能存在"。

为什么会这样？因为格子是共享的。dave 撞上的格子是 alice 点亮的。数组越小、插入的元素越多，格子被点亮得越多，撞上别人格子的概率就越大。所以假阳性率可以通过"加大数组 + 调整哈希函数个数"压低，工程上常用配置能把假阳性率压到 1% 以下。1% 的误判率意味着：100 次"不存在"的查询里，99 次直接挡掉，只有 1 次白读一次磁盘。完全可以接受。

另一个方向，假阴性（False Negative，实际存在却说"不存在"），布隆过滤器永远不会有。为什么？因为如果 carol 真的被插入过，插入时它自己的格子一定被点亮过，而这些格子只会从 0 变 1，永远不会变回 0（布隆过滤器不支持删除，就是因为不能关格子）。所以查询时必然全是 1，必然报"可能有"。

一句话总结，面试直接背：布隆过滤器可能有假阳性，绝不会有假阴性。说没有，就一定没有；说有，要去确认。

它省掉的磁盘 I/O

回到 LSM 的场景。每个 SSTable 文件配一个布隆过滤器，存在内存。假设 5 层共 50 个文件，查一个不存在的 key：

从 50 次磁盘 I/O 压到大约 1 次。这就是工程里"小结构解决大问题"的典范。

极简代码

C++
#include <bitset>   // 引入 bitset，一个固定长度的位数组
#include <string>

class BloomFilter {
private:
    std::bitset<1024> bits_;   // 1024 格的位数组，编译期就定死长度
public:
    void add(const std::string& key) {
        size_t h1 = std::hash<std::string>{}(key);              // 第一个哈希函数：标准库自带的 hash
        size_t h2 = h1 * 1315423911 + 7;                        // 第二个"哈希函数"：用第一个的结果搅一搅，凑合用
        bits_.set(h1 % 1024);   // 把 h1 对 1024 取余得到的位置置为 1
        bits_.set(h2 % 1024);   // 把 h2 算出的位置也置为 1
    }

    bool maybeContains(const std::string& key) const {
        size_t h1 = std::hash<std::string>{}(key);
        size_t h2 = h1 * 1315423911 + 7;
        return bits_.test(h1 % 1024) && bits_.test(h2 % 1024);  // 两个位置都是 1 才返回 true
    }
};

逐行讲：

  1. std::bitset<1024> bits_;：bitset 是 C++ 标准库的位数组，1024 表示 1024 个格子，每个格子一个 bit。1024 bit 只有 128 字节，却能为上百个 key 服务，这就是布隆过滤器省内存的原因。
  2. std::hash<std::string>{}(key)：标准库提供的哈希函数，给它一个字符串，吐出一个大整数。{} 是临时造一个哈希器对象，然后立刻调用它。
  3. h1 * 1315423911 + 7：我们需要两个哈希函数，但手里只有一个，怎么办？用一个常见的小技巧：把 h1 乘上一个大质数再加个偏移，搅出来的数就当第二个哈希值用。真实实现会用更讲究的搅法，思想一样。
  4. bits_.set(...)：把指定位置置为 1。bits_.test(...)：读取指定位置是 0 还是 1。
  5. &&：逻辑与，"两个条件都成立才返回 true"。正好对应"所有位置都是 1 才说可能有"。

本部分小结

下一部分，我们退后一步，把 LSM 和它的老对手 B+ 树放在一起对比。这是面试必考题。

第七部分：LSM vs B+ 树

先认识一下对手

B+ 树（B+ Tree）是关系数据库世界的霸主，MySQL 的 InnoDB 存储引擎底层就是它。你不用会写它，但要知道它的基本形态：一棵又矮又胖的树，所有数据存在最底层的叶子节点上，叶子节点之间用链表串起来，查找从树根往下走，最多走三四层就能找到任何一条记录。

B+ 树的特点是"就地更新"：改一条数据，就找到它所在的那个叶子页（Page，磁盘读写的最小单位，通常 4KB 或 16KB），直接在那个页里改。

读与写的性格对比

现在我们有两个选手了，把它们的性格摆出来。

B+ 树的性格：读快，写慢。

  1. 读为什么快：数据整整齐齐住在树上，查任何 key 都是从树根往下走固定的三四层，路径短而确定。读性能极好。
  2. 写为什么慢：因为就地更新。改一条数据就要定位到具体的页、把那个页读出来、改了再写回去，这是随机写。回忆第一部分的数字：随机写大约 1 MB/s，顺序写大约 100 MB/s。写入量一大，B+ 树就被随机写拖死。

LSM 的性格反过来：写快，读慢。

  1. 写为什么快：所有写入都是"追加 WAL + 写内存跳表"，磁盘上只有顺序写。写入吞吐（Throughput，单位时间能处理多少请求）能甩开 B+ 树几条街。
  2. 读为什么慢：一个 key 可能躺在 MemTable，可能躺在 Immutable MemTable，可能躺在 L0 到 Ln 的任何一个 SSTable 里。读要按从新到旧的顺序一层层找，有布隆过滤器帮忙挡掉大部分，但本质上是"多处可能，得挨个排除"，比 B+ 树的"一步到位"慢。

各自适合什么场景

用场景来记，比背结论管用。

第一种场景：抖音点赞记录。全国人民每秒产生几十万条点赞，写多读少，而且绝大多数读是"读最近的"（你只会看自己今天赞了什么，不会去翻三年前的）。这种"疯狂写入"的场景，LSM 完胜。Cassandra、HBase、RocksDB 这些写密集系统全是 LSM 家族。

第二种场景：银行余额。你卡里有多少钱，查的时候必须毫秒级返回一个精确数字，写少读多，而且每次查询都关乎钱，路径必须短而稳。这种"精确点查"的场景，B+ 树完胜。所以银行核心系统至今是关系数据库的天下。

第三种场景：混合型。比如 DeepSeek 的历史对话，写入频繁（每发一条消息就是一次写），读取也频繁（每次点开会话都要加载）。真实系统会做折中，很多现代数据库干脆两种结构都用，或者用 LSM 打底再配各种缓存优化读。

一句话总结

面试时如果被问"LSM 和 B+ 树的本质区别是什么"，你可以把这句话甩出去：

LSM 用 Compaction 的后台成本，换来了写入时的顺序化；B+ 树用写入时的随机化，换来了读取时的确定性。

说人话：LSM 是"先随便写，后台慢慢收拾"；B+ 树是"写的时候就收拾整齐，读的时候一步到位"。一个把成本付在后台，一个把成本付在前台。没有绝对的好坏，只有适不适合你的读写比例。

第八部分：项目整体架构 + 读写路径完整走一遍

到这一部分，所有零件都造好了：WAL、MemTable、Immutable MemTable、SSTable、多层结构、布隆过滤器、Compaction。现在把它们拼装成一台完整的机器。

整体架构图（ASCII）

C++
                        ┌─────────────────────────────────────┐
                        │              你的程序                 │
                        │      put(key, value)  get(key)      │
                        └──────────────┬──────────────────────┘
                                       │
                    ┌──────────────────┼──────────────────┐
                    │                  │                  │
                    ▼                  │                  ▼
            ┌──────────────┐           │          ┌──────────────┐
   磁盘     │  WAL 文件     │           │  内存    │  MemTable     │
            │ (顺序追加)    │           │          │  (跳表, 可写) │
            └──────────────┘           │          └──────┬───────┘
                                       │                 │ 写满4MB
                                       │                 ▼
                                       │          ┌──────────────┐
                                       │          │ Immutable    │
                                       │          │ MemTable(冻结)│
                                       │          └──────┬───────┘
                                       │                 │ 后台刷盘
                                       ▼                 ▼
   磁盘  ┌─────────────────────────────────────────────────────┐
         │  L0: [SSTable] [SSTable] [SSTable]  (可有重叠)        │
         │              │ 满4个就 Compaction                     │
         │              ▼                                        │
         │  L1: [SSTable] [SSTable] ...        (不重叠, 10倍大)  │
         │              ▼                                        │
         │  L2: [SSTable] [SSTable] [SSTable] ...                │
         │  每个 SSTable 在内存里配一个 Bloom Filter               │
         └─────────────────────────────────────────────────────┘
                                       ▲
                              ┌────────┴────────┐
                              │  后台 Compaction │
                              │  线程: 定期合并   │
                              └─────────────────┘

put 的旅程：一条数据的完整一生

我们以 put("user:12345:likes", "[v888,v889]") 为例，把这条数据从生到死的每一步走一遍。

第一步：进 WAL。引擎把这行操作追加到 WAL 文件末尾，flush 落盘。从此这条数据有了"不死之身"，天塌下来都能恢复。

第二步：进 MemTable。引擎在内存跳表里插入这条记录。插入完成，回复用户"OK"。注意，到目前为止磁盘上只发生了一次顺序追加，没有任何随机写。快的原因全在这里。

第三步：MemTable 写满。假设几天后 MemTable 攒到 4MB，它被冻结成 Immutable MemTable，新的空 MemTable 上岗。我们的点赞记录躺在冻结表里，不再变化。

第四步：刷盘成 SSTable。后台线程把 Immutable MemTable 按 key 顺序写成一个新的 SSTable 文件，放进 L0，同时给它在内存里建一个布隆过滤器。旧的 WAL 此刻寿终正寝，删除——它的使命（保护这批数据直到落盘）完成了。

第五步：L0 满了，触发 Compaction。假设 L0 攒了 4 个文件，达到上限。后台 Compaction 线程把这 4 个文件读出来，多路归并，扔掉重复旧版本和墓碑，写成若干个新的、互不重叠的 SSTable，放进 L1。我们的点赞记录跟着搬了一次家。之后它还可能继续往 L2、L3 沉，每沉一次就又被重写一次——这就是写放大在现实中的样子。

get 的旅程：一次查询的完整排查

现在用户调用 get("user:12345:likes")。引擎按"从新到旧"的顺序排查，因为新数据覆盖旧数据，谁先找到谁说了算：

第一站：MemTable。在跳表里找。找到了？直接返回，收工。这是最快的情况，纯内存操作。

第二站：Immutable MemTable。还没刷盘的那批，同样在内存里找。

第三站：L0 的 SSTable。注意 L0 文件之间有重叠，所以 L0 的每个文件都可能含有这个 key，要挨个问。但每个文件先问布隆过滤器：过滤器说"没有"，跳过，零磁盘 I/O；说"可能有"，才去读索引、读数据块确认。

第四站及以后：L1、L2……。从这里开始，同层文件互不重叠，所以每一层最多只有一个文件可能含有这个 key。先定位到那个候选文件，问它的布隆过滤器，再决定是否读盘。

假设我们的点赞记录最终在 L1 的某个 SSTable 里被找到：引擎读索引块、二分、读数据块、找到 value，返回给用户。如果一路找到最底层都没有，返回"不存在"。

把两条路径放在一起看

现在回头看，整个设计的巧妙之处就出来了：

这就是 LSM-tree 的全貌。每个零件都不复杂，但拼在一起就是工业界最能打的写密集存储结构。

本部分小结

下一部分，实战环节：简历怎么写，面试怎么答。

第九部分：简历怎么写 + 面试怎么答

简历项目描述（可直接用，按自己实现的情况微调）

笔记基于 LSM-tree 的高性能 KV 存储引擎（个人项目，C++） - 参考 LevelDB 设计，独立实现了一个支持 get / put / delete 的单机 KV 存储引擎。 - 写入路径采用 WAL 写前日志保证崩溃可恢复，配合内存跳表（Skip List）实现 MemTable，写满后冻结为 Immutable MemTable 并由后台线程刷盘为 SSTable，全流程磁盘写入均为顺序追加。 - SSTable 采用"数据块 + 索引块"结构，支持二分查找定位；实现 L0/L1/L2 多层结构与多路归并 Compaction，完成版本去重与墓碑清理。 - 为每个 SSTable 实现内存布隆过滤器（Bloom Filter），将不存在 key 的查询磁盘 I/O 从逐层扫描降低为接近零次。 - 使用压测工具对比验证：顺序写吞吐显著高于随机写方案，理解了写放大等 LSM 固有代价。

写简历的三个提醒：

  1. 数字要真实。如果你压测过，就写真实数字，比如"单机顺序写吞吐达到 XX 万 ops/s（operations per second，每秒操作数）"。没测过就写"显著高于"，别编。面试官一追问就穿帮。
  2. 每句话都要能展开。简历上每个词都是面试的钩子，这篇教程就是每个钩子后面的答案。
  3. 关联生态。面试时主动提"我对标的是 LevelDB，工业界 RocksDB 也是这个思路"，显得你不是闭门造车。

面试高频十问

第一问：为什么 LSM 写快？ 答案要点：所有磁盘写入都是顺序追加。WAL 是追加，SSTable 刷盘是一次性顺序写出，Compaction 也是批量顺序读写。机械硬盘上顺序写约 100 MB/s，随机写约 1 MB/s，差约 100 倍。LSM 把每一次用户写入都翻译成了顺序写，所以快。B+ 树就地更新是随机写，所以写入一大就扛不住。

第二问：那 LSM 读慢怎么办？ 答案要点：三个手段。第一，从新到旧地查，数据越新越可能在内存（MemTable）里直接命中。第二，每个 SSTable 配布隆过滤器，不存在就直接跳过，不碰磁盘。第三，通过 Compaction 控制层数和文件数，把"要查的地方"控制在个位数。工程上还会加块缓存（Block Cache）缓存热点数据块。

第三问：WAL 为什么先写？反过来行不行？ 答案要点：不行。先写内存再写 WAL，中间断电就丢数据，而且内存已经回了"OK"，数据丢了没法交代。WAL 是唯一真相来源，内存随时可以靠重放 WAL 重建，所以必须先写 WAL。这叫写前日志，"写前"两个字就是顺序。

第四问：MemTable 为什么用跳表不用红黑树？ 答案要点：都能 O(log n)。选跳表的核心原因是并发友好：跳表插入只改少数几个节点的指针，容易做无锁或细粒度锁；红黑树插入要旋转，牵动多个节点，多线程下锁难做。另外跳表实现简单很多。LevelDB、Redis 的有序集合都用跳表。

第五问：LSM 怎么做删除？ 答案要点：写墓碑（Tombstone）。因为 SSTable 不可修改，够不着旧数据，只能追加一条"已删除"标记。读时从新到旧先碰到墓碑就返回不存在。Compaction 合并时，确认更老的层里没有这个 key 的副本了，就把墓碑和旧数据一起物理删除。

第六问：布隆过滤器会误判吗？ 答案要点：会，但只有假阳性，没有假阴性。说"不存在"就真不存在，因为插入时点亮的位永远不会熄灭；说"可能存在"要去确认，因为可能撞上别人点亮的位。假阳性率靠位数组大小和哈希函数个数控制，工程上压到 1% 以下。它换来的是：不存在 key 的查询几乎零磁盘 I/O。

第七问：Compaction 怎么挑选要合并的文件？ 答案要点：常见的触发条件和挑选策略有几种。L0 文件个数超阈值就触发，因为 L0 文件有重叠、查起来贵，优先收拾它。往深层合并时，常按"大小比例"策略：挑一个文件，看它和其他文件的重叠程度、合并后能清理多少垃圾，优先合并收益大的。实际系统（如 RocksDB）还会考虑每层总大小是否超过配额的 10 倍阶梯。答出"L0 按文件数、深层按大小和重叠度"就有深度了。

第八问：什么是写放大？怎么缓解？ 答案要点：用户写一次，数据在 Compaction 中被反复读写在多层之间搬运，磁盘实际写了好几次，这个倍数就是写放大。缓解思路：减少层数、调大每层容量、优化文件选择策略让每次合并清理更多垃圾；或者换 Compaction 策略（比如 Tiered，分层制，合并次数少但读放大更高，这是另一种取舍，能说出来是大加分项）。

第九问：崩溃恢复流程是什么？ 答案要点：重启后先检查 WAL 文件。从头逐行读出操作记录，在新建的 MemTable 里重放（PUT 插入、DEL 写墓碑），重放完 MemTable 就恢复到崩溃前状态，然后正常营业。已经刷成 SSTable 的数据对应的旧 WAL 在刷盘时已删除，不会重复恢复。

第十问：你这个项目和 LevelDB / RocksDB 差在哪？ 答案要点：诚实承认差距，但展示出知道差距在哪。我的是教学简化版；工业级还多了很多东西：块缓存、Snappy 压缩（一种快速压缩算法）、更精细的 Compaction 策略、多版本并发控制（MVCC, Multi-Version Concurrency Control，让读写互不阻塞的机制）、快照（Snapshot，某一时刻的数据视图）等。但核心骨架——WAL、MemTable、SSTable、多层 Compaction、布隆过滤器——是同一个。这句话说完，面试官就知道你骨架真的懂了。

收尾：怎么把这篇教程变成你的项目

教程读完了，知识是你的了，但项目还不是。把它变成真项目的路径：

  1. 第一步：照着这篇教程，自己把每个模块敲一遍。先写 WAL，再写跳表，再写 SSTable 读写，最后串起来。每敲完一块就写个小程序测它。
  2. 第二步：写压测。自己造 100 万条随机 KV，分别测"顺序写"和"模拟随机写"的吞吐，把真实数字测出来。这组数字会出现在你的简历和面试里。
  3. 第三步：读一点 LevelDB 源码。不用全读，就读 WAL 和 SSTable 的格式部分，你会发现"哦，原来工业界就是这么做的"，信心暴涨。

到这一步，你就不是"背过一个项目"的人，而是"真懂 LSM 的人"。这两类人，面试官聊五分钟就能分出来。

祝面试顺利。

<!--DOC_END-->

本教程为零基础实战讲义 · 代码均可本地编译运行 · 动手敲一遍胜过读十遍