四个数据结构的真实战场

去年做一套实时风控引擎，QPS 8k，要求 99.9% 请求 < 20 ms。我们先后把哈希表、布隆过滤器、跳跃表、红黑树轮番拉上线，最后留下一串“血与泪”的日志。今天把选型过程+事故细节拆开写，给后来人一个参考。

1. 哈希碰撞：当 20 亿条记录撞上 1 条误判

最早的核心是一张 64 GB 的内存哈希表，Key 是 uint64_t(user_id)，Value 是一个 32 bit 的位图。上线第一周风平浪静，第二周突然报警：延迟飙到 200 ms。排查发现：

• 负载均衡把流量打到一台新机，哈希种子随机变化；
• 两个不同的 user_id 算出同一个 bucket，链表长度=65536；
• CPU 在 __memcmp_avx512 上打满。

修复：

把 bucket_count 从 2^28 调到 2^30，再把哈希种子固化（cityhash128_with_seed_v1）。改造后延迟回到 9 ms，但内存多吃了 16 GB，老板骂了十分钟。

2. 布隆过滤器：一次“以为 0.1 % 误判”的惨案

为了节省 16 GB，我们引入布隆过滤器：8 GB 内存，预计误判率 0.1%，用来挡掉 95% 的冷用户。结果：

• 实际误判率 1.5%，导致 3 万用户被风控误杀；
• 客服电话被打爆，老板第二次骂人。

事后总结：

• 公式算出来的 0.1% 是“理论值”，我们忽略了哈希函数质量和实际 key 分布；
• 调整了 3 次 bit 数组大小，最终 12 GB 才把误判压到 0.05%。

3. 跳跃表：Redis 能跑，不代表我也能跑

冷用户过滤完后，热用户需要按时间窗口排序。我们用 Go 自己撸了一个“极简”跳跃表，level 最大 32，期望 O(log n)。上线测试：

• 本地 benchmark 漂亮得飞起：插入 100 w/s，查询 150 w/s；
• 线上 Go GC mark 阶段把 STW 顶到 40 ms，P99 再次爆表。

根因：

• 跳跃表节点全是小对象，Go 的 span 利用率低，GC 扫描爆炸；
• 切到 runtime.GOMAXPROCS(16) + sync.Pool 后，STW 降到 5 ms，但复杂度已经秒杀我们的耐心。

结论：

“Redis 能跑，是因为它是单进程 + jemalloc，而不是跳跃表本身够快。”

4. 红黑树：老而弥坚，但让 SSD 吃了苦头

最后把排序部分换成红黑树，找了一个开源的 llrb 实现（C + cgo）。

• 插入 O(log n) 稳定，GC 无压力；
• 但节点指针 + 颜色位 + 对齐填充，每条记录平均 48 byte 额外开销；
• 总内存 34 GB，把机器 SSD swap 打穿两次。

缓解方案：

• 把节点池化，对齐到 64 byte cache line，内存降到 31 GB；
• 延迟稳定在 12 ms，老板说“再优化就砍需求”，项目结束。

5. 一句话总结选型心得

• 哈希表：最快，也最脆弱，碰撞是隐形炸弹。
• 布隆过滤器：省内存，但“理论误判”只活在论文里。
• 跳跃表：写起来爽，跑起来 GC 教你做人。
• 红黑树：老顽固，稳得一批，代价是内存和实现复杂度。