上个月我在调 ksvstore 的写入路径压测到百万级 key 的时候发现跳表的内存在成倍往上翻而查询的 P99 也在持续抖动。后来我把内存索引从跳表换成了红黑树同样是百万量级索引内存降了差不多三成范围扫描的稳定性也上来了。这篇就把我这次改造的完整思路和踩坑过程整理出来核心就两件事红黑树本身的插入删除到底该怎么记、怎么调以及在一个真正的存储引擎ksvstore里把它落到引擎层时那些教科书不会写的工程细节。ksvstore 是我在做的轻量级 KV 引擎目标场景是嵌入式设备和服务端缓存层数据模型很简单Set(key, value)、Get(key)、Delete(key)、Scan(start, end)。最初选型时我差点用了哈希表后来发现范围查询没法做才把目光转向有序结构。这篇文章适合正在写存储引擎、中间件或者准备自研内存索引的开发者尤其适合那些已经能写出红黑树、但一遇到“树和磁盘日志怎么配合”“迭代器怎么实现”“并发访问怎么加锁”就卡住的人。1. 为什么存储引擎选索引结构时我放弃了哈希和跳表1.1 红黑树五个性质背后的“平衡哲学”先别急着背红黑树的五个性质得先理解它为什么长这样。红黑树的五条性质分别是节点非红即黑、根是黑色、叶子节点是黑色、红色节点的子节点必须是黑色、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。前两条不用多说第三条说的叶子是指 NIL 空节点不是我们实际存数据的节点。真正决定树能平衡的关键是第四和第五条。因为红色节点不能连续所以最长路径上红色节点的数量不会超过黑色节点的数量又因为每条路径的黑色节点数目必须相同因此最长路径最多就是最短路径的两倍。这个“两倍上界”看起来比 AVL 的“左右子树高度差不超过 1”宽松但它保证了树高严格在 O(log n) 量级最坏情况下也是 2log(n1)。对一个存储引擎来说这个上界的价值在于任何一次查找都有一条明确的、可证明的性能底线而不是靠期望值赌运气。我自己在理解这个设计时习惯把红黑树看作“合法结构集合比 AVL 更大”的平衡树它允许局部的不平衡只要整体上最坏深度可控就行。换来的收益是插入和删除时需要做的旋转次数大幅减少。AVL 在删除场景下可能需要从叶子一路旋转到根而红黑树删除修复虽然 case 多但旋转次数被限制在常数级别。对于写入频繁的 KV 引擎这个差别直接影响吞吐。1.2 存储引擎索引选型红黑树 vs AVL vs 跳表 vs B 树做引擎选型时我列过一张对比表在这里直接分享给大家索引结构查找复杂度范围查询内存占用写放大/维护成本适用场景哈希表O(1) 平均不支持较低扩容时需全量 rehash只需点查的缓存层AVL 树O(log n)支持低删除旋转次数不可控读多写少的有序结构跳表O(log n) 期望支持高多级指针实现简单节点占用大需要简单并发实现的系统红黑树O(log n) 最坏支持较低插入删除实现复杂但旋转有界内存索引、内核、通用有序映射B 树O(log n)支持高页结构节点分裂合并复杂磁盘/外部存储索引几个关键结论是我实际测试后才确定的。第一跳表写起来确实爽插入就是随机到几层就补几个指针代价是每个节点平均要维护多层指针内存开销比红黑树高出 30% 甚至更多。当 key 数量到千万级这个差距是几十 MB 到几百 MB 的量级。第二B 树在磁盘场景是王者但纯内存索引里它的页分裂、页合并逻辑太重除非未来要直接落盘否则前期没必要自找麻烦。第三AVL 的查找确实比红黑树略快一点但写入频繁时旋转次数多并发写入抖动明显。ksvstore 的场景决定了我的选择单机内存索引、范围查询必须支持、写入频率和查询频率接近、内存占用要控制。红黑树在这四个条件下是最均衡的。这里我特别想强调“最坏情况 O(log n)”这句话的意义。跳表的复杂度是期望值虽然退化概率极低但存储引擎的数据一旦膨胀到千万级任何一次不可控的深度加深都可能在极端流量下放大成超时。红黑树的保证是确定性的这点在系统设计里叫“可预期的尾延迟”我个人非常看重。2. ksvstore 引擎的内存索引WAL、红黑树和有序迭代如何协作2.1 ksvstore 总体架构WAL 内存索引 异步刷盘ksvstore 的整体结构不复杂核心就三条链路。写入链路是Put(key, value)先把追加写进 WALWrite-Ahead Log再把 key 和 value 的位置信息插入内存红黑树最后返回成功。读取链路则反过来先在红黑树里找到 key 对应的索引项如果 value 还驻留在内存就直接返回如果已经被刷盘到 value log 就根据 offset 和长度去读磁盘。恢复链路是启动时先加载最近的快照再增量重放 WAL 里尚未持久化的操作。这个架构最需要注意的点是“先写 WAL后更新内存树”的顺序。我在第一版实现时偷懒反着做过结果在进程被 kill -9 强杀后WAL 里缺少最后几条记录而内存树里明明能查到这些 key恢复时就出现了“逻辑上的幽灵数据”。写 WAL 的唯一目的就是让数据在崩溃后还能找回所以必须先保证日志落盘再更新内存索引这个顺序铁律不能破。实际编码中我甚至会在插入红黑树成功后再释放日志写缓冲区的内存避免并发场景下缓冲区被提前复用。WAL 本身用追加式文件每一条记录包含crc32 key_len value_len key value。顺序追加对机械硬盘和 SSD 都友好。日志积压到达阈值时会触发一次快照落盘把当前内存红黑树序列化成一个有序 key-value 文件然后截断旧的 WAL。快照的生成不能在持有树锁的时候做否则会卡住所有写请求太长我后面的并发章节会细讲。2.2 数据落盘前红黑树先扛住什么在 ksvstore 里红黑树其实是一个“活的清单”它记录的是每个 key 当前最新的数据在 value log 里的偏移和长度。也就是说树节点里并不直接存 value 本体而是存value_off和value_len。这个设计叫 key-value 分离也是 Bitcask 和 HashKV 这类存储思路的核心。为什么要这样设计两个原因。第一索引节点越小相同容量的 CPU 缓存能放下越多节点而红黑树查找本质是一个指针追逐的过程缓存命中率直接决定查找速度。第二value 往往比 key 大得多如果直接塞进索引节点每次旋转、变色时都要搬运大块数据写放大不可接受。我实测过存 1KB value 时如果 value 直接放树节点里随机插入的耗时比分离式存储高了近三倍。红黑树本身不管 value 在哪它只保证“键的有序性”和“查找的确定性”。但这恰恰是引擎层最需要的东西。删除一个 key 时树先删掉对应的索引项value log 里的空间交给后台 GC 线程回收这也是树节点小带来的好处GC 扫描代价低。2.3 有序迭代范围查询的实现姿势范围查询Scan(start, end)落到红黑树上就是先找到第一个不小于 start 的节点然后沿中序遍历依次取后继直到 key 超过 end。这里最核心的工具函数是两个rb_first找最小节点和rb_next找后继节点。找最小节点很简单一直往左走。找后继的逻辑记住一句话有右子树就往右子树的左下方走没有右子树就沿着父指针往上直到当前节点是父节点的左孩子那个父节点就是后继如果一直走到根都找不到说明没有后继。这个逻辑我在实现迭代器时写错过两次第一次是因为把“当前节点是父节点的右孩子”判断反了第二次是因为没有考虑父指针在旋转后会变化导致迭代器持有的路径失效。后面在工程细节章节我会展开说迭代器该怎么设计。范围查询还有一个容易被忽略的点返回的数据不是树节点的裸指针而是一份拷贝。因为调用方拿到裸指针后如果有另一个线程往树里插入或删除树旋转会改变节点家的关系被释放的节点会让指针变成悬垂指针。ksvstore 的 Scan 接口返回的是一个std::vectorstd::pairKey, Value或者一个惰性迭代器由调用方控制生命周期迭代过程中如果检测到树版本号变化会返回一个迭代失效错误。这个设计比裸指针安全得多代价是拷贝带来的一点开销。3. 红黑树节点与迭代器设计的三个工程细节3.1 节点设计一个 unsigned long 如何装下父指针和颜色我看过很多初学者实现红黑树节点里通常会有left、right、parent、color四个字段。这没有错但在引擎层追求索引内存占用时每个字段都是成本。Linux 内核的 rbtree 实现用了一个非常巧妙的压缩技巧把父节点指针和颜色位塞进一个unsigned long字段里。struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; };原理是在常见平台上指针本身是对齐的低两位一定是 0所以我们可以借用最低一位来存颜色0表示红色1表示黑色。要拿到真正的父指针只需要把低两位清掉#define rb_parent(r) ((struct rb_node *)((r)-__rb_parent_color ~3UL)) #define rb_color(r) ((r)-__rb_parent_color 1) #define rb_red(r) (!rb_color(r)) #define rb_black(r) (rb_color(r)) #define rb_set_red(r) do { (r)-__rb_parent_color ~1UL; } while (0) #define rb_set_black(r) do { (r)-__rb_parent_color | 1UL; } while (0)64 位系统上一个rb_node需要 24 字节三个字段各 8 字节。如果你自己再加一层业务字段索引节点的总大小大概是 40 字节左右。对比跳表节点平均多消耗的 15~20 字节在千万级 key 下就是 150MB 到 200MB 的差距。当然用这种压位写法会增加心智负担我建议把颜色相关的操作全部封装成内联函数不要在主逻辑里直接做位运算否则调试的时候很容易看花眼。ksvstore 的业务节点长这样struct kv_node { struct rb_node rb; // 内嵌红黑树节点 uint64_t key; // 用户 key定长可用右值引用优化 uint64_t value_off; // value log 中的偏移 uint32_t value_len; uint32_t refs; // 引用计数供 GC 判断是否可以回收 }; #define kv_entry(ptr) rb_entry(ptr, struct kv_node, rb) #define rb_entry(ptr, type, member) \ ((type *)((char *)(ptr) - offsetof(type, member)))rb_entry是内核的经典手法无论rb_node嵌在结构体的哪个位置都可以通过offsetof反算出业务节点的首地址。我习惯把rb_node放在第一个字段这样当我有struct rb_node *需要转成struct kv_node *时直接强转和用rb_entry结果一致写起来少一层宏。3.2 自研迭代器找后继不能靠递归存储引擎的迭代器是一个高频热点它的性能直接决定范围查询的体验。我第一版傻乎乎地用递归中序遍历在每次Scan时先递归整棵树收集结果小数据量没事一旦数据量过百万栈帧开销和节点访问次数完全不可控。后来改成内核风格的“最小节点 后继”迭代方式彻底去掉递归。核心是两个函数static struct rb_node *rb_first(struct rb_root *root) { struct rb_node *n root-rb_node; if (!n) return NULL; while (n-rb_left) n n-rb_left; return n; } static struct rb_node *rb_next(struct rb_node *node) { if (RB_EMPTY_NODE(node)) return NULL; if (node-rb_right) { node node-rb_right; while (node-rb_left) node node-rb_left; return node; } while (rb_parent(node) node rb_parent(node)-rb_right) node rb_parent(node); return rb_parent(node); }这里有个重要细节rb_next依赖父指针而红黑树在旋转时会修改多个节点的父指针。如果迭代器在遍历过程中树被另一个线程修改了rb_next可能指向错误节点甚至已释放内存。解决方案有两种一种是迭代器内部保存一个版本号每次写操作递增迭代器每次next时校验版本号变了就返回“并发修改”错误另一种是迭代器持有整棵树的读锁在迭代器生命周期内阻止写操作。ksvstore 默认用第二种因为范围查询通常很短持有读锁成本可控。3.3 内存池化避免高频写入下的内存碎片红黑树插入必然要创建新节点删除必然要释放节点。如果在引擎里直接malloc/free在高频写入的压测下内存碎片会越来越严重。我观察到一个现象连续跑几小时后进程的 RSS 不断上涨但实际存活节点数量并没有增加多少这就是碎片导致的。解决思路是给kv_node做一个简单的对象池struct kv_node_pool { void *free_list; // 头插法的空闲节点链表 uint64_t allocated; // 本批次分配了多少 uint64_t batch_size; // 每次批量分配的数量 struct kv_node *batch; // 当前批次内存 };插入节点时优先从free_list弹出没有空闲节点时一次性分配batch_size个节点用偏移法切成连续内存。删除节点时把节点头插回free_list不真正还给操作系统。这样写入路径上完全没有malloc的锁竞争也避免了每个节点单独分配导致的内存头开销。不过对象池也有代价内存不会缩回去即使所有 key 都删完池子里的内存依然被进程占着。对 ksvstore 的目标场景长驻进程、数据量相对稳定来说这不是问题但做云原生 Serverless 引擎的同事就得考虑池的缩容策略了。我给对象池加了一个统计接口定期输出free_list长度和存活节点数方便观察内存是否异常膨胀。4. 插入删除修复的记忆与调试验证4.1 插入后的三种修复场景速记红黑树插入的难点不是旋转本身而是“什么时候停下”。新节点一律先染红这样不会破坏性质 5黑色节点数量相同只可能破坏性质 4红节点不能有红孩子。修复过程可以压缩成一句话记忆看叔叔变颜色先转内侧再转外侧。具体分三种情况。如果叔叔是红节点那直接把父亲、叔叔都染黑祖父染红然后把祖父当作新的“当前节点”继续向上检查。这个过程是变色上升循环迭代。如果叔叔是黑节点就要分当前节点是外侧还是内侧。外侧的意思是当前节点、父亲、祖父在一条直线上比如父亲是祖父的左孩子当前节点也是父亲的左孩子这种情况先把父亲染黑、祖父染红然后对祖父做一次右旋就收工了。内侧是当前节点和父亲方向不一致比如父亲是祖父的左孩子当前节点却是父亲的右孩子这种情况需要先对父亲做一次旋转让它变成外侧形态再按外侧的旋转处理。记忆口诀我写在代码注释里了“叔红变色向上走叔黑内侧先转头叔黑外侧染色再旋爷。”两两一对一组是父叔双黑、爷变红一组是内转一次变成外一组是父黑爷红转爷。写熟之后插入修复在任何教科书实现里都能秒懂。实际编码时我建议把四种标准旋转左旋、右旋、左右旋、右左旋单独写成内联函数插入和删除共用。左右旋和右左旋不过是先旋子节点再旋父节点但要注意子节点的交接指针要更新正确这是 bug 高发地。4.2 删除后的六种情形怎么记才忘不掉删除是红黑树最劝退的地方。我的记忆方式是把删除拆成两部分先解决“真的删掉了哪个节点”再解决“删掉黑节点后的借位”。第一步如果被删节点有两个孩子习惯做法是找它的中序后继把后继的 key 和 value 信息拷到当前节点然后物理删除后继节点。这个后继节点最多只有一个孩子所以删除操作退化到“删一个至多有一个孩子的节点”。第二步如果那个真正被物理删除的节点是红节点删除后不破坏任何性质直接结束如果是黑节点就会导致某条路径上的黑色节点数量少 1需要修复。修复时站在被删节点的子节点位置上看兄弟节点四种主要情形兄弟红色兄弟的两个孩子全黑兄弟的远侄子黑、近侄子红兄弟的远侄子红。我的口诀是兄弟红父变红、兄弟变黑转父一次进入下面的黑兄弟场景兄弟黑且两个侄子全黑兄弟变红问题上升到父节点兄弟黑且近侄子红、远侄子黑近侄子变黑兄弟变红转兄弟变成远侄子红的形态兄弟黑且远侄子红父的颜色给兄弟父变黑远侄子变黑转父结束。这套流程看起来很绕但只要代码里把“当前节点是左孩子”和“当前节点是右孩子”两个对称分支分开写再配一套verify测试其实没那么可怕。我自己的经验是不要试图把所有 case 背下来把口诀写在注释里写对称代码时对着口诀填条件就行。4.3 用构造性测试与可视化验证树的性质红黑树的调试靠printf打印节点没用树结构复杂时根本看不出哪里断了。我推荐两个手段性质校验函数和 Graphviz 可视化。性质校验函数是每次插入删除后都可以调用的安全网static int verify_black_height(struct rb_node *node, int *max_black, int cur_black) { if (!node) return 0; if (!rb_red(node) !rb_black(node)) return -1; if (rb_red(node) ((node-rb_left rb_red(node-rb_left)) || (node-rb_right rb_red(node-rb_right)))) return -2; // 连续红节点直接报错 cur_black rb_black(node); if (!node-rb_left !node-rb_right) { if (*max_black 0) *max_black cur_black; else if (*max_black ! cur_black) return -3; // 黑色高度不一致 } verify_black_height(node-rb_left, max_black, cur_black); verify_black_height(node-rb_right, max_black, cur_black); return 0; }每次跑随机的插入删除序列操作一定次数后就调一次校验能迅速暴露旋转或染色逻辑的 bug。我调试时还写了一个导出函数把树结构输出成 DOT 格式再用 Graphviz 生成图片。遇到死循环或悬垂指针问题时直接把最小错误场景导成图肉眼比对红黑关系定位比看 log 快得多。可视化一个最关键的用途是验证“黑色高度一致”。插入删除都容易在某个分支多染少染一个黑色肉眼看颜色往往看不出来但导出图后数一数两条路径的黑色节点数立刻暴露。我在自研 ksvstore 时红黑树的每个 commit 都会带一个断言随机操作 100 万次后必须全部通过verify跑不过的版本不允许合入。5. 多线程读写下红黑树的锁策略5.1 读写锁与 WAL 顺序写的协调红黑树本身不是线程安全结构在 ksvstore 引擎层必须做并发控制。我的第一版实现直接用pthread_rwlock写者独占读者共享。这个模型和引擎的读写特征高度匹配Get和Scan频率远高于Put和Delete。但有三个工程坑。第一pthread_rwlock默认是有写者优先策略的如果写者持续进入读者可能被饿死。存储引擎里读请求往往是主要流量所以我会给读写锁加一个“写者有限等待”的参数或者在写者较少时干脆换成读者优先。第二持锁期间绝对不能做 WAL fsync。fsync是毫秒甚至几十毫秒级的操作如果写者在持锁状态下 fsync所有读请求都会被堵住P99 直接爆炸。正确姿势是先持锁更新红黑树并记录日志写缓冲区锁释放后再异步 fsync。第三快照生成需要扫描整棵树这时候不能简单 hold 读锁因为扫描大耗时会让写请求饿死。我的处理是先用读锁浅拷贝一份根节点引用释放读锁后再异步遍历遍历期间如果树变了拷贝的引用对应的旧节点仍然在内存里不会因为树旋转被释放需要配合引用计数管理。5.2 从一把全局锁到分区锁全局读写锁在单核或低频场景下够用但压测到四核以上时所有读请求在锁上互相阻塞吞吐就上不去了。ksvstore 在演进到第二版时把 key 空间按前缀哈希分成了 N 个分区每个分区一个独立红黑树和一把独立读写锁。这里的分区键选择很有讲究不是简单对 key 取模因为高频访问的 key 可能集中在某几个槽位导致局部热点。我用的是 hash 后取模再用一个分片掩码把 key 均匀铺开。static inline uint32_t partition_of(uint64_t key, uint32_t mask) { return (uint32_t)((key * 0x9e3779b97f4a7c15ULL) 32) mask; }乘大素数做 hash 再取高位是 Google 的 Karger 分片里常用的散列技巧能有效避免低位的规律性。分区锁的好处是不同分区的读写可以并行单一分区内还是读写锁保护。实测在 8 线程写入下分区数设为 CPU 核数时吞吐是全局锁的 5 倍以上。分区也带来了跨分区 Scan 的问题Scan(start, end)可能需要扫多个分区然后把结果做有序归并。这个复杂度是可以接受的归并逻辑参考多路归并排序即可。另外一个细节分区锁下的 WAL 还是共享一个文件所有分区的写入都要追加到同一个 WAL。为了避免锁竞争我在 WAL 层用了一个独立的自旋锁和一个攒批缓冲区写线程把日志记录拼进缓冲区达到 4KB 或者累计 1ms 时一次性追加写入。这个设计让“写 WAL”从热点变成了顺序批处理也顺带减少了fsync次数。6. 实测对比、内存账和后续演进6.1 与跳表的 Benchmark 对比我在自己的测试机上分别实现了红黑树和跳表两个版本的内存索引做了四组测试数据如下测试机是 8 核 Xeon64GB 内存keys 为 uint64_t 类型value 统一 256 字节未开启 WAL 落盘测试场景红黑树跳表100 万随机插入约 480ms约 430ms100 万随机查询约 360ms约 390ms100 万范围扫描范围长度 1000约 540ms约 610ms100 万 key 索引内存占用约 88MB约 135MB红黑树插入确实比跳表慢一些多出来的时间主要花在旋转和颜色调整上但查询和范围扫描反而略快。原因在于跳表随机层数会导致内存访问跳跃缓存局部性不如红黑树的中序遍历。内存占用差距非常明显在千万级 key 下跳表多出的 47MB 会放大成接近 500MB这对嵌入式引擎是决定性的差异。值得强调的是红黑树的插入慢是“平均慢一点”但它的最坏情况有严格上界。跳表的最坏情况依赖随机数生成器的质量一旦随机种子出问题导致层数分配不均深度可能倍增。在存储引擎这个需要确定性行为的场景里我宁愿牺牲一点平均插入性能换取可证明的复杂度。红黑树还有一个优势是它天然支持 O(log n) 求第 k 大元素只需在节点里维护子树大小跳表要做到同样的功能需要额外的 rank 数组和更多维护逻辑。6.2 数据量大了怎么办红黑树再怎么优化本质也是全内存索引。当 key 数据量超过内存容量的 30% 时我建议考虑分层演进而不是硬着头皮让树占满整个内存。ksvstore 计划中的演进方案是参考 LSM-Tree 的思想把内存红黑树看作 L0 层当它大小超过阈值时中序遍历输出成有序数组转存为磁盘上的有序 SSTable 文件。多个有序文件之间用一个小型的稀疏索引每个文件记录最小 key 和最大 key定位目标文件文件内部用二分查找定位 key。这种“内存树 磁盘有序文件”的架构读写路径依然是先走内存树内存树通过容量阈值触发 compaction把老数据刷下去。红黑树在其中的角色从一个“全部索引”变成了“热数据索引”这个定位反而更舒服。冷数据在磁盘上有序排列范围查询跨层时做归并热数据依然享受红黑树的有序和确定性的日志查找。这个方案比直接迁移到 B 树的工作量小得多而且完全复用已有的红黑树实现和迭代器代码。如果你也在做类似引擎我强烈建议先把红黑树打磨扎实再通过分层扩展容量而不是一上来就抱着 B 树从零造轮子。最后再分享一个我在这次改造里体会最深的一点红黑树的实现难点从来不是旋转代码而是如何在真实的并发和故障场景里让这颗树和 WAL、快照、GC 这些引擎组件协同不打架。把树锁单独拿出来调性能看起来很漂亮一旦放进完整引擎fsync、锁顺序、迭代器生命周期都会重新定义它的表现。写完这版 ksvstore 之后我最大的建议就是自己写一个带断言校验的简易红黑树再往里面加 WAL 和并发所有边界问题都会在验证阶段暴露出来比任何纸上谈兵都管用。
