1. 为什么KV存储永远绕不开“网络数据结构”这对组合先从一个我踩过的坑说起。之前在维护一个内部配置中心底层就是典型的KV存储。业务方反馈说高峰期单节点延迟从2毫秒飙到接近100毫秒我一开始以为是磁盘IO问题结果iostat一看磁盘根本没怎么忙。后来用perf抓热点发现大量CPU时间消耗在系统调用和调度器上细看才发现是网络事件处理模型太老了——一个连接一个线程连接数一上来线程上下文切换就把CPU吃光了。那次之后我彻底明白了一个道理KV存储的性能不是某一段的事而是网络、并发模型、数据结构的全链路问题。你说单次GET查询底层红黑树只花了几百纳秒这没有任何意义因为请求从网卡进来要经过协议解析、线程调度、锁竞争最后才轮到红黑树。整条链路里任何一环掉链子端到端延迟都会崩盘。这也是为什么标题会把“epoll、ntyco、io_uring”和“数组、红黑树、哈希、跳表、B树”放在一起。前者决定请求怎么高效地进来、怎么被并发处理后者决定数据怎么在内存里被高效地读写。两条线各自展开都够写一本书但落地到一个真实的KV存储项目里他们必须被放在一起权衡。本文就按我实际做项目的思路把这两条线串起来讲。先说清楚适用范围。这篇文章面向的是想自己动手做一个高性能KV存储或者正在读类似项目源码、想知道“为什么选这个不选那个”的开发者。你需要有一点C语言基础和基本的操作系统概念知道进程、线程、锁大概是怎么回事就够了。更底层的细节我会在讲原理时一并补上。整体来看一个高性能KV存储可以拆成三层层级职责本文涉及的核心内容网络接入层接收连接、读取请求、回写响应epoll 事件循环、协程调度、io_uring 提交与收割处理模型层决定请求怎么被并发处理锁怎么规避reactor 模式、协程化改造、无锁化设计存储引擎层决定数据在内存/磁盘里怎么组织哈希表、跳表、B树、红黑树、数组三层之间是连锁关系。网络层如果用 epoll 状态机的写法那么存储层选红黑树还是跳表影响的是单次查询的耗时但如果网络层换成协程阻塞操作的成本变低了存储层就可以更大胆地用一些“慢但简单”的结构。反过来存储层如果选用B树做磁盘持久化网络层的IO模型也必须支持异步写盘否则刷盘会把事件循环卡死。每层架构都限制了其他层可以怎么选这就是所谓全链路设计。2. 网络接入层的三代演进epoll、协程化网络库、io_uring网络层是KV存储的入口。所有性能问题第一刀都要砍在这里。2.1 从阻塞IO到epoll为什么“一个线程一个连接”扛不住最早期的写法是阻塞IO来一个连接就创建一个线程去处理C10K问题就是这么来的——1万个连接就是1万个线程线程切换一秒几十万次CPU全耗在上下文切换上。你数据库里的B树再好查询只要10微秒结果线程调度延迟1毫秒全白干。epoll的出现就是为了解决“大量连接但同时活跃的很少”这个场景。它的核心理念是把连接的管理交给内核内核只通知你哪些fd真的可读可写了。应用层不再傻等而是用一个线程循环调用epoll_wait拿到一批就绪的fd挨个处理。这就是经典的reactor模式。我在自己项目里用的就是这种结构简化后大概是// 事件循环核心伪代码 while (1) { int n epoll_wait(epfd, events, MAX_EVENTS, -1); for (int i 0; i n; i) { if (events[i].events EPOLLIN) { handle_read(events[i].data.fd); // 读取请求 } if (events[i].events EPOLLOUT) { handle_write(events[i].data.fd); // 回写响应 } } }这个写法能把单机撑到几万连接每连接的处理成本从线程级别降到事件级别。但代价是代码变得非常碎片化一个完整的业务逻辑被拆成“可读”“可写”“超时”几个回调读半包、写半包、状态机各种判断堆在一起。我早期写的时候一百行能做完的逻辑拆成状态机之后写了四百多行还特别容易漏边界。2.2 ntyco这类协程网络库让回调地狱退回同步写法解决“epoll回调碎片化”的方案就是协程化网络库ntYco是其中比较典型的一个代表。它的核心思想说起来很简单底层还是epoll那套事件驱动但把每个连接包装成一个协程阻塞操作比如读一个还没来全的请求就让出CPU等事件来了再切回来。对于写应用的人来说代码可以回到同步阻塞的写法// 协程版读请求看起来像阻塞读实际底层是异步的 nty_recv(co, fd, buf, sizeof(buf)); // 数据没来就主动让出CPU来了之后再从这里继续为什么这种模式对KV存储重要因为KV存储的逻辑天然是“请求—响应”式的读一个key就查一遍存储写一个key就更新一遍。用状态机去拆这种天然串行的逻辑是反人类的。协程保留了串行的心智模型又拿到了epoll的高并发能力代价只是保存切换时的上下文寄存器、栈。和线程切换相比协程切换的成本低一到两个数量级因为不需要陷入内核态。在ntYco这类库里核心是两件事setjmp/longjmp或者ucontext做上下文切换加一个全局的epoll循环做事件收集。每个协程的栈可以是分配出来的一小块内存用mmap预分配好切换时只需要改栈指针代价大概几百纳秒到一微秒量级。相比线程切换动辄几微秒还特权级往返优势很明显。2.3 io_uring把“系统调用”这件事本身优化掉epoll和协程解决了并发模型问题但每次read、write、epoll_wait还是得进内核。数据从网卡到应用层内存要经历中断、软中断、内核拷贝、用户态拷贝每一步都有开销。io_uring想解决的是更深一层的问题大幅降低系统调用次数让内核和应用共享一组环形缓冲区来提交请求和收割结果。这张表对比了三代网络模型的本质差异维度epollepoll 协程ntYco模式io_uring并发模型事件驱动 回调事件驱动 协程化同步写法事件驱动 异步提交收割系统调用次数高每请求多次中封装后减少部分极低批量提交/批量收割编程模型碎片化回调同步串行心智负担低异步但可用协程封装回同步数据拷贝多次多次可结合固定缓冲区减少拷贝适用场景入门、中小规模通用高并发服务极高吞吐、IO密集场景kv存储里io_uring最有价值的是用IORING_OP_READV/IORING_OP_WRITEV做磁盘读写或者用IORING_OP_RECV/SEND做网络收发。因为你可以先把一批请求的读写操作一次性提交进sqesubmission queue entry然后干点别的最后在cqecompletion queue entry里统一收割结果。请求是批量进去的完成也是批量出来的系统调用开销从“每请求两次”摊薄到“一批一次”。封装起来核心就两块一块提交一块收割// 提交侧把读请求塞进SQE并通知内核 struct io_uring_sqe *sqe io_uring_get_sqe(ring); io_uring_prep_recv(sqe, fd, buf, len, 0); io_uring_sqe_set_data(sqe, req_ctx); io_uring_submit(ring); // 收割侧批量取走完成的请求 int cqe_count io_uring_wait_cqe(ring, cqe); // 或使用非阻塞peek批量取 io_uring_for_each_cqe(ring, head, cqe) { struct my_req *req io_uring_cqe_get_data(cqe); handle_completion(req, cqe-res); } io_uring_cq_advance(ring, cqe_count);如果一个项目同时上了epoll、协程和io_uring最常见的分工是io_uring负责磁盘读写协程负责业务编排epoll负责网络事件感知。三者不冲突各管一段。实际测试中我做过一个基准同样的随机读场景纯epoll的状态机模型单线程跑到约8万QPS改用协程后逻辑复杂度大幅降低性能接近约7.5万QPS损失一点但换来代码可维护性再升级到io_uring批量提交单线程能到12万以上。真实场景里还会受网卡中断合并、缓存命中率影响但这个量级差异是能稳定观测到的。3. 存储引擎层的数据结构选型数组、红黑树、哈希、跳表、B树网络层决定了请求能多快进来存储层决定了数据能多快被找到。这一层选错结构前面网络优化得再好都没用。3.1 定位与本质这五种结构分别解决什么问题KV存储的核心操作就四个Put(key, value)、Get(key)、Delete(key)、Scan(startKey, endKey)。不同的数据结构在不同的操作上各有优势。数据结构读写范围查询内存占用典型用途哈希表O(1)O(1)不支持中高需预分配纯点查缓存、索引加速跳表O(log n)O(log n)支持较高多级指针内存KV引擎、实现有序集合类似Redis ZSET红黑树O(log n)O(log n)支持中序中内核调度器、早期KV引擎有序索引B树/B树O(log n)O(log n)支持叶节点链表低高扇出磁盘数据库、文件系统索引、现代KV引擎的磁盘组件数组O(log n) 可二分O(n) 移动支持天然有序最低元素总量固定、有序小数据量场景这张表里最关键的两组对比是“哈希 vs 有序结构”和“跳表 vs 红黑树 vs B树”。哈希赢在点查算一下hash定位到桶链上找一下或开放定址探几步平均O(1)。但它有两个硬伤不支持范围查询扩容的rehash会带来全量拷贝痛点虽然渐进式rehash能缓解但工程实现复杂度高。跳表、红黑树、B树都是有序遍历的结构。区别在于红黑树是严格平衡二叉树树高约log n查询稳定。但为了实现范围查询需要中序遍历会把原理分布在不同缓存行的节点逐个访问cache locality比较差。跳表用多级指针来“跳过”节点同样可以范围遍历。它比红黑树好在工程上不需要旋转操作插入删除只改动相邻节点指针并发控制后面细说也要容易得多。Redis选它做有序集合底层这个决策本身就说明问题。B树/B树赢在“高扇出”一个节点存几百个key一次磁盘IO或者一次cache line命中的覆盖范围远大于二叉树。磁盘KV写多读少、key分区间有序时B树的写性能和扫描性能是最强的。3.2 数组最被低估的“数据结构”很多人把数组排除在KV结构之外但我在做一个小型Redis协议兼容层时意外发现在key是连续递增整数比如会话ID的场景数组根本是首选。原因有三第一cache locality无敌。数组是连续内存二分查找也好直接索引也好访问的第k个元素能以极大概率命中CPU缓存。如果是红黑树每跳一个节点可能都要从主存重新读。实测在小数据量几百到几千条目下数组二分查找经常比红黑树还快。第二零指针开销。数组没有prev/next指针、没有颜色标记、没有节点元数据内存使用率接近100%。如果用朴素的链式红黑树每个节点光颜色标记和指针就有三四十字节额外开销数组这边只是裸数据。第三构造简单容易直接序列化。做持久化时数组可以一整个mmap出去冷启动加载速度碾压任何指针密集的结构。代码上数组加二分查找找key是比红黑树更省心的写法// key若是有序递增可用整型数组存储索引再二分 static int kv_bsearch(const struct kv_entry *arr, size_t len, uint64_t key) { size_t lo 0, hi len; while (lo hi) { size_t mid lo ((hi - lo) 1); if (arr[mid].key key) { lo mid 1; } else { hi mid; } } return (lo len arr[lo].key key) ? (int)lo : -1; }但数组的短板也很致命插入和删除都是O(n)的搬移。所以数组只能用在“启动时全量加载、运行中只读或极少写”的场景比如索引快照、只读副本。3.3 哈希表点查之王以及它的扩容之痛哈希表是KV存储里最常见的索引结构。内存KVmemcached早期版本、Redis的hash类型、各语言内置map基本都是它。对点查场景哈希表几乎是无敌的计算hash、桶定位、链表或开放定址解决冲突E(key)接近O(1)。工程上要踩的坑主要在扩容。扩容如果一次性做一个100万条目的哈希表在rehash瞬间会卡顿因为要重新分配内存、重新计算所有key的hash并搬运。在线下服务里这可能是“慢请求尖刺”的来源。解决方案是渐进式rehash把重hash分摊到每次插入/查找中每次搬一部分桶。Redis的dict就是这么做的。我自己实现过一轮核心是维护两个hash表查询时先查新表、再查旧表插入时只插新表并顺带从旧表搬一批bucket到新表。用开放定址法linear probing时还有一个隐蔽的坑删除不能直接置空否则查询链会断。通常需要标记删除tombstone、定期整理或者干脆根本不提供删除。做KV存储的Delete接口时必须小心。3.4 红黑树 vs 跳表 vs B树有序结构的三个流派如果业务需要范围查询哈希表就出局了你得从红黑树、跳表、B树里选。红黑树适合“写少读多”的通用有序索引。它的弱点在于每次插入删除可能触发旋转旋转是局部性的在单线程下容易实现、效率也高但一旦多线程并发写旋转和变色会波及树的不同部分加锁范围往往要比跳表大。我早期用Linux内核里那种红黑树实现写过KV索引查询很快但Add和Remove在并发下的锁竞争成了瓶颈。跳表在并发场景下有结构性优势。因为插入新节点时只需要先找到插入位置然后对新节点和它后面N个指针执行CAS操作不同插入点之间的冲突概率很低。Redis用跳表而不是红黑树很多人以为是作者偏爱其实是因为跳表的范围遍历对缓存更友好按层级一格格跳而且实现和调试成本更低。换红黑树范围遍历时你要做中序遍历栈或递归碰上并发还要处理旋转带来的结构变动。跳表的并发插入核心可以写成这样// 跳表插入时向上层追加指针只需CAS更新后继指针 for (int lvl 0; lvl new_node-height; lvl) { Node *expected update_nodes[lvl]-next[lvl]; if (!CAS(update_nodes[lvl]-next[lvl], expected, new_node)) { // 冲突时需要重新查找位置后重试 goto retry; } }B树/B树适合“磁盘或持久化”场景。它的精髓是扇出高一棵三层的B树如果每节点存200个key能覆盖200^3800万个key。每次查询走三次指针就到底了。这在内存里看不出差距但在磁盘上就意味着一棵三层树最多三次磁盘IO就能完成一次查key。对比红黑树100万key的树高约20层随机读时每层都可能是冷cache甚至换页20次磁盘IO必然比3次慢得多。现在流行的高性能KV引擎比如RocksDB的LSM分支里的磁盘组件本质就是按块组织、高扇出的B树。用B树做KV存储索引数据组织会类似这样// 简化B树节点结构键数组有序叶子节点用指针串成链表 struct bpt_node { bool is_leaf; int nkeys; uint64_t keys[ORDER]; union { struct { struct bpt_node *children[ORDER 1]; } internal; struct { struct value_ref values[ORDER]; struct bpt_node *next; } leaf; }; };3.5 组合拳哈希跳表的经典搭配我在做内存KV引擎时最终没有全表只用一种结构而是采用了“哈希分片 每片一个跳表”的组合。思路是这样的先用key的哈希值做2的幂次取模拆成N个分片shard每个分片内部一个跳表。这样既拿到了哈希分片带来的并发扩容、负载分散又保留了跳表的范围查询能力——范围查询按key直接定位到某个分片内扫描即可。这个设计同时解决了两个问题一是缩窄了单点数据量跳表高度自然下降查询从log n变成log(n/N)二是并发上用分片锁替代全局锁不同分片的写操作可以并行锁粒度细很多。配合前面讲的协程网络层整体结构非常清晰。4. 整合实战基于“协程网络层 混合数据结构”搭建一个KV存储引擎有了前面的选择和论证可以看看一个整合后的引擎大概长什么样了。这一节描述的是我实际做过的一个原型项目规模不大全内存Redis协议兼容目标是验证“io_uring处理磁盘协程处理并发跳表做有序索引”这套组合的可行性。4.1 整体架构与模块划分整个引擎只运行在单机上但结构上是分层的[网络接入层] epoll 事件循环监听 socket连接建立后分配给一个协程 [协程调度层] 每连接一个协程协程内部以同步方式读请求、组装响应 [命令解析层] 解析 Redis 风格协议文本 [存储引擎层] 哈希分片固定64片每片一个跳表索引指向内存value [持久化层] io_uring 异步刷盘为AOF日志文件不阻塞主流程连接进来后epoll只负责把可读事件转给协程调度器调度器唤醒对应协程协程在业务代码里做正常的read、解析、查跳表、write。读到半包时就yield等epoll通知再加醒来继续读。存引擎内部不关心网络只暴露Put/Get/Delete/Scan接口。4.2 关键代码片段协程化处理一个GET命令这段代码展示的是查值逻辑static void handle_get(CoScheduler *sched, Conn *c, const char *key) { uint32_t shard hash_key(key) % SHARD_COUNT; Value *val shard_table[shard].get(key); // 跳表查找 if (!val) { co_write(c, $-1\r\n, 5); // 返回 nil return; } char buf[24]; int n snprintf(buf, sizeof(buf), $%zu\r\n, val-len); co_write(c, buf, n); co_write(c, val-data, val-len); co_write(c, \r\n, 2); }端到端全是同步写法没有回调但是底层是协程。你会发现出错误的机会明显变少至少不再需要手写拆分读缓冲区的状态机了。4.3 实测数据协程跳表分片的效果我在一台8核虚拟机内存16GBCPU是普通Xeon上做了基准测试用自带的压测客户端模拟1000个并发连接混合读写4:1key分布均匀指标纯epoll单线程直接查询协程全局红黑树协程64分片跳表QPS约7.8万约7.2万约14.6万P99延迟2.8 ms2.1 ms0.8 ms最大连接数1万级5万级5万级分片带来的并发提升比预期的还大。原先全局红黑树一个锁挡住所有写分片之后锁只在片内竞争加上跳表不涉及全局树旋转写路径几乎是无等待的。协程模型在连接数上去后的优势也体现得很明显连接数从1000涨到5000P99延迟只涨了不到0.2ms。4.4 持久化层怎么用io_uring内存KV如果没有持久化重启数据就丢了生产环境不可接受所以原型里加了AOF。传统做法是主线程把日志同步写到磁盘每一条命令一次write性能会被fsync拖垮。我的做法是把AOF的写入提交到io_uring队列由内核异步完成不阻塞主流程。当DMA或设备队列积压太多时才让主流程等待一批完成从系统上做背压。这里有个关键选型点io_uring虽然好但实现复杂度偏高需要管理内存池给SQE和CQE做内存复用。我踩过的坑是直接把一个栈上的buffer传给io_uring_prep_writev内核还没完成写栈已经出栈被冲掉了导致数据错乱。后面改为每个请求上下文在堆上分配一块固定内存请求完成回收到池子问题才消失。5. 选型决策背后的权衡逻辑为什么“最优”不存在每一层都讲完之后回头看这张全景决策图真正的重点不是“哪个结构最快”而是“在什么约束下哪个最合适”。场景特征网络层推荐数据结构推荐理由点查为主、key不可枚举、小数据量epoll 就够哈希表简单直接不做没必要的复杂度范围查询多、写多、需要并发epoll/协程分片跳表锁粒度小范围扫描对缓存友好数据量大到必须落盘io_uring 异步写B树或LSM分组结构高扇出降低磁盘IO次数key规律如自增ID、只读场景epoll/协程数组二分零指针开销加载快足够快稳定性优先团队不熟新内核纯协程如ntYco或epoll红黑树可用内核现成实现每多一个“高级特性”就多一份运维风险很多人会问“B树一定比跳表快吗”答案是不一定。如果你数据全在内存B树的扇出优势完全体现不出来反而因为节点内部的数组偏移和叶子链表的指针操作显得笨重跳表或红黑树的单key查找在100万数据里摊下来也就是20次左右的访存已经非常快。B树真正的优势只在数据大于内存、要换页到磁盘、且访问以块为单位的时候。所以问题从来不是“绝对谁快”而是“在什么量级和什么存储层级下”。从这个角度看一句话总结我这些年做存储引擎的心得“先从你的访问模型出发不要从某种数据结构的传说出发。哈希做不了范围查询数组做不了增量更新跳表的内存是红黑树的两倍B树的实现比跳表复杂五倍以上。你要交易的是工程复杂度、内存开销、并发能力、点查/扫表性能这几个维度没有免费的午餐。”6. 过一遍我实操中踩过的坑希望帮你省一个月时间最后这部分是最值钱的我把做这个项目过程中实际踩过、修过的问题都列出来。每个都是网上很少有文档写清楚的。6.1 epoll的EPOLLONESHOT你没用就会出“惊群”类问题把同一个fd反复注册到事件循环里如果你的处理是异步的先读一部分、遇到需要等待的事件就return等下一轮再读会出现同一个事件被多个线程抢着处理的情况尤其开了SO_REUSEPORT时。正确做法是用EPOLLONESHOT每次事件到达后内核自动把该fd从监听集中移出等处理完再epoll_ctl重新挂上。这样能避免半包状态被多处同时处理。6.2 协程栈要预分配别裸用系统默认栈ntYco这类库默认走mmap分配栈但如果你不控制栈大小默认的协程栈可能只有64KB到128KB一个深度递归或者缓存了一个大的局部结构体就把栈撑爆。我在压测时遇到过莫名其妙的segfault后来定位到是协程栈溢出写穿了相邻的栈区域。解法是设置一个“栈底哨兵值”定期检查有没有被改写或者统一把协程栈从64KB提到512KB并做页面对齐。内存成本可以接受但要明确知道自己在干什么。6.3 io_uring和内存池小心恐怖的上限和“无人收割”的通知io_uring最坑的一点是如果CQE队列满了内核会暂停接收新SQE你的提交函数可能被阻塞。在KV存储里这意味着主流程可能卡在内核把CQE清空之前间接形成一种非常隐蔽的死锁。我的经验是队列深度至少配置成请求峰值的两倍比如最大并发256则uring队列深度512并且给收割线程设置独立清理逻辑每隔几毫秒强制io_uring_peek_cqe老一批完成事件避免通知丢失或积压。6.4 跳表和红黑树在键值大小时的表现差异如果你的value很大比如几KB的JSON跳表和红黑树存的大概率是指向value的指针或引用而不是value本身。这样内存使用是稳定的。但如果你图省事直接把value存成节点内部的大字节数组跳表的内存碎片和红黑树的节点膨胀会被放大很多倍。实测存1KB的value时跳表的内存利用率相比“指针方案”会掉到60%以下。有一个经验法则节点内只存metadata大数据放堆上这是KV引擎的通用最优解。6.5 范围扫描在跳表里也要小心跨分片问题分片可以大幅提升并发度但代价是范围查询变复杂了。你按key查一棵跳表是连续扫描没问题但如果你按key的范围跨了多个分片比如range是hash分片不相邻的区间就需要合并多个文件或临时结果集。工程上可以处理但这是我一开始没有预料到的最大的“设计后遗症”。如果业务范围查询比重很大建议考虑不按hash分片、而是按key分片的方案牺牲一部分点查并发换取范围扫描的一致性。7. 最后一个建议先跑通一条最简链路再谈优化如果你读完也想自己写一个KV存储我最真诚的建议是不要一开始就同时上协程、io_uring、B树、跳表、哈希分片。你先用一个数组模拟存储用epoll加单线程跑通“能接收请求、能存数据、能返回结果”的完整链路然后逐步替换掉每一环。先把epoll换成协程跑一轮性能对比再把数组换成哈希表看看点查性能爬升多少再加一个跳表做范围查询最后如果你真需要持久化才引入io_uring。每一环替换之后单独压测的收益和代价你心里要有数。这样的一个项目做下来你对“epoll到底慢在哪”“协程切换实际要花多久”“B树的扇出在内存里有没有用”等问题的理解会远超看任何书或任何博客。纸上得来终觉浅存储引擎这种系统光靠理论推导总会漏掉一两处只在压力下才会暴露的真实瓶颈。我在最后一代原型里整个启动、加载、查询、刷盘、压测的完整链路跑一圈不到一周就完成了后面几周时间全花在调哈希分片参数、修io_uring的边界问题、给协程栈加保护上。如果你希望少走弯路这条渐进的路径是最稳的。祝你的KV引擎早日跑出自己的满意数据。