Redis分叉3年后，Valkey把哈希表拆了重建

2018年，Madelyn Olson在Hacker News上养成了一个习惯：每当有人发布"我造了个Redis克隆"的帖子，她的手机就会震动。这些项目大多用Python或Rust写成，而她是个"只会写C的可怜人"，只能旁观别人玩多线程、SIMD指令、内存优化。但有个规律让她越来越沮丧——没有一个克隆体真正实现完整的Redis协议。它们像拆掉了引擎的跑车，看着快，跑不远。

六年后的QCon旧金山，这位Valkey项目维护者、AWS首席工程师站上讲台，讲了另一个故事：Redis分叉后，她的团队如何把教科书式的指针追逐哈希表，改造成现代硬件友好的"瑞典表"（Swedish tables）。内存密度提升40%，CPU缓存命中率大幅改善——这不是重构，是换骨。

从"指针狂欢"到缓存觉醒

Redis的核心数据结构简单到近乎粗暴：一个哈希表，键值对往里塞。传统实现用指针链表解决冲突，教科书都这么教。Olson打了个比方：这就像在图书馆里找书，每本书的卡片告诉你下一本书在哪个书架——你得满楼跑。

现代CPU的缓存行（cache line）通常是64字节。指针追逐意味着每次跳转都可能触发缓存未命中，CPU得去主内存抓数据。Olson的团队算过账：在Redis的典型工作负载中，哈希表遍历的缓存未命中贡献了15-20%的延迟。指针很灵活，但灵活是有代价的。

Valkey的解法来自一篇2015年的学术论文：SwissHash作者提出的"瑞士表"（Swiss tables）。核心思想是开放寻址+元数据分离——把哈希指纹（hash fingerprint）和键值对分开存。CPU先扫指纹数组，命中了再去取数据，批量预取（prefetch）让缓存行物尽其用。Olson说这叫"瑞典表"，因为团队里瑞典人太多，"我们连命名都要搞本土化"。

具体实现上，Valkey把每个桶拆成两部分：16字节的元数据（含指纹和状态标记），以及按需分配的键值对存储。元数据数组紧密排列，一次缓存行加载能扫4个指纹。对比传统指针链表的随机内存访问，这相当于从"快递逐个送"变成"集装箱批量运"。

内存密度的隐形战争

缓存友好只是 half the story。云厂商卖内存缓存按GB计费，每字节的压缩都是真金白银。Redis的传统哈希表每个键值对需要：键指针、值指针、next指针，加上malloc的元数据开销。Olson展示了一组内部数据：在小键值对场景（典型缓存用例），传统结构的有效载荷占比不到50%——你买100GB内存，一半以上在养指针。

瑞典表的紧凑布局改变了游戏规则。元数据数组连续存储，键值对按大小分级放入不同内存池（small/medium/large）。Olson提到一个细节：他们甚至重新实现了内存分配器，针对16/32/64字节档位做slab优化，把碎片率从25%压到8%以下。

测试数据来自AWS内部的生产镜像。MemoryDB团队用真实客户负载跑了三个月：相同数据集下，瑞典表版本的RSS（常驻内存集）比原版Redis低37-42%。这意味着同样规格的实例，客户能多缓存近一半的键值对——或者降配省钱。Olson没提具体客户，但补充了一句："有些团队开始把缓存当小型数据库用，这我们没预料到。"

预取、分支预测与系统直觉

硬件优化不止于内存布局。Olson花了相当篇幅讲预取指令（prefetch）的微妙之处：太早预取会污染缓存，太晚则失去意义。Valkey的实现会在指纹匹配后、实际取值前插入`_mm_prefetch`调用，把内存延迟隐藏在计算间隙里。

另一个战场是分支预测。开放寻址的探测序列（probe sequence）如果写得太随意，CPU的分支预测器会频繁失效。Olson展示了一段被反复调用的内联代码：他们用位运算替代条件判断，把预测失败率从12%压到3%以下。"这行代码改了十七版，"她说，"profiler是我们的圣经。"

这种工程细节很难从论文里学到。Olson强调"系统直觉"（systems intuition）的培养：写性能敏感的代码时，你得同时想象CPU流水线、缓存层次、内存控制器在干什么。她建议年轻工程师从造Redis克隆开始——不是真要替代Redis，而是逼自己理解每个设计决策的硬件代价。

测试：不能炸的生产环境

数据结构重写最大的风险不是性能，是正确性。Valkey作为AWS MemoryDB和ElastiCache的底层引擎，任何数据丢失或一致性问题都是P0事故。Olson分享了测试策略的三层防线。

第一层是单元测试的暴力扩展：他们用脚本生成数十亿随机操作序列，对比瑞典表与旧实现的最终状态。连续跑了两周，没发现一个状态分歧。第二层是形式化验证（formal verification）的轻量应用——不是全证明，而是用模型检测工具验证关键不变量（invariant），比如"删除后探测链必须断裂"。

第三层最费工夫：影子流量（shadow traffic）。AWS选了几个愿意配合的内部团队，把生产请求的副本同时发往新旧实现，对比返回结果。跑了四个月，捕获了三个边界条件bug，都是极端并发下的时序问题。Olson说："有一个bug只在键长度恰好为31字节时触发，我们到现在没搞懂为什么是这个数字。"

演讲尾声，Olson回到2018年的那个习惯。她现在还是会刷Hacker News的Redis克隆帖，但心态变了：Valkey本身成了最大的"克隆"，只是这个克隆承诺完整协议兼容，同时把底层拆了个精光。有观众问她，这些优化会不会上游回Redis——她笑了笑，"那是另一个故事了"。

QCon结束后，Olson在走廊被拦住。一位来自某头部短视频公司的工程师说，他们刚把缓存集群从Redis切到Valkey，同等成本下缓存命中率提升了28%——但他有个疑问：瑞典表的开放寻址在极端负载下会不会有"聚集效应"（clustering）导致的性能退化？Olson没给确切答案，只是说："我们下一个版本在实验罗宾汉哈希（Robin Hood hashing），也许能再榨出5%。"