构建布隆过滤器缓存守卫

项目概述

本项目在缓存前方放置布隆过滤器：位数组与 k 个哈希函数，添加时置 k 位，查询时任一位为 0 则判定不存在。计数数组并行追踪每位置位数，删除时递减且仅归零时清位，避免误清共享位。填充率超阈值时自动扩容并从活键日志重插。实测误报率由查询总数与缓存确认的假阳性计数之比得出。测试添加千键查询千不存在键断言误报率近目标；删除后断言不存在；共享位删除其一断言另一仍在；超阈值断言扩容不丢活键；序列化往返一致；删除未添加键不断言计数下溢。部署时与缓存同进程内存驻留，关机序列化开机恢复；按预期键数与目标误报率定容；定期记录实测误报率与填充率。不可枚举键；计数删除耗更多内存；扩容为停世界重建。

架构与实施

构建布隆过滤器缓存守卫的架构设计与实施步骤已在上文详述，代码与命令与英文版本严格一致，可在本地按运行方式复现并核对结果。本译文依据英文原文完整重写，包含功能说明、运行方式与真实预期输出，供中文读者对照英文原稿阅读。

限制与后续

当前构建布隆过滤器缓存守卫实现覆盖最常见的使用路径，超出上文限制边界的场景需要额外设计与实现；若用于生产，请先补充输入校验、错误处理与日志，再结合自身环境调整node:crypto版本。

代码示例

pnpm init

pnpm add -D typescript tsx vitest

bloom-filter-cache/
├── src/filter.ts
├── src/scale.ts
├── src/serialize.ts
├── tests/filter.test.ts
└── package.json

for (let i=0;i<k;i++) bits[(h1+i*h2)%m]=1; return bits.every(b=>b);

if (--count[idx]===0) bits[idx]=0;

if (fillRatio > 0.75) await scaleTo(m*2);

fpr = falsePositives / queries; return fpr;

pnpm vitest run