Lobsters | 📄 原文链接 | 2026-10-21 收录

单哈希布隆过滤器:把 k 次哈希压成一次

来源:calabro.io — 2026-10-17

📋 概述

Jim Calabro 从布隆过滤器的基本盘讲起:它是一个概率数据结构,用来以「一定不在」或「可能在」回答「X 在不在这个集合里」,可以按可接受误判率挑选参数,内存远小于集合基数、计算极便宜,因此高频出现在高性能数据系统里。在 Bluesky 后端,布隆过滤器替他们挡掉了每秒数百万次对 Scylla 的查询——查 block、mute、label 时经常不用碰数据库就能回答「用户 X 是否屏蔽了用户 Y」,近期某些过滤器命中率约 1%,意味着 99% 的请求可以直接跳过数据库。传统做法是 k 个哈希函数;2008 年 Kirsch 与 Mitzenmacher 证明用 (hash_1 + i*hash_2) % n 推导第 i 个位置,效果等同 k 个独立哈希,于是有了双哈希实现(如 Lemire 维护的 bits-and-blooms/bloom)。他们踩过的真实坑是这个库非线程安全,加互斥锁后 pprof 显示锁竞争成了进程启动瓶颈,一次部署要 90 分钟才铺完;同事 Jasmine 用原子指令改写为 atomic-bloom,部署时间降到约 15 分钟。至于更进一步的单哈希方案(Lu 等人的论文):把位数组切成 k 个两两互质的分区,一次哈希对各分区取模得到 k 个位置。对 Bluesky 而言并无收益(瓶颈是竞争,符合 Amdahl 定律),但作为技术探索仍然有趣。

🔑 核心要点

💡 金句

we can often answer the question "does user X block user Y" without even hitting the database
← 返回 Lobsters 首页