算法与数据结构

一致性哈希与布隆过滤器

02-线性数据结构进阶预计 20 分钟一致性哈希布隆过滤器分布式概率结构
学习状态：

一句话定义

一致性哈希（Consistent Hashing）把键与节点都放到环形哈希空间上，使节点增减只影响相邻弧段的数据分布，解决普通 hash mod N 在扩缩容时全量重映射的问题；布隆过滤器（Bloom Filter）用位数组加 k 个哈希函数实现空间极省的「可能存在 / 一定不存在」判断，误判率可控但不支持删除。

为什么重要

这两个结构是「哈希思想离开单机」的第一站：分布式缓存、负载均衡、分库分表靠一致性哈希把重映射代价从全量压到 1/N；缓存穿透防护、爬虫去重、海量集合成员判断靠布隆过滤器把「是否存在」的存储压到每元素几个比特。它们也是理解 HyperLogLog、Count-Min Sketch 这类概要数据结构（Sketching）的入口。

前置知识

kp-009（哈希与冲突）；概率基础（独立事件乘法、指数近似 (1−x)≈e^(−x)）。

核心概念

  • 普通取模的病根：bucket = hash(key) mod N，N 从 4 变 5 时几乎所有键换宿主（模数变了），缓存瞬间全失效。
  • 哈希环：把 hash 值域想象成 0~2³²−1 的环；键顺时针找第一个节点。节点增减只搬运环上相邻一段 → 期望只迁移 1/N 数据。
  • 虚拟节点（VNode）：每个物理节点映射成 100–200 个环上点，抹平「节点少时弧长不均」的倾斜。
  • 布隆过滤器：m 位位数组初始全 0；插入时对键算 k 个哈希各置 1 位；查询时 k 个位全 1 才「可能存在」，任一为 0 则「一定不存在」。
  • 误判率：p ≈ (1 − e^(−kn/m))^k；最优 k = (m/n)·ln 2，此时每元素约需 1.44·log₂(1/p) 位。

原理与机制

布隆过滤器的机制是「多哈希投票」：k 个函数把键投到 m 位中的 k 个位置，查询即看这 k 位是否全被置 1；误判源于「位被不同键共享」——插入越多、位数组越满，投票被搭便车的概率越高，误判率公式正是对这个共享概率的计算。一致性哈希的机制是「顺时针找第一个节点」：归属只由相邻弧段决定，节点增减只改动局部映射，虚拟节点用数量把弧长方差摊平。

直观类比

  • 一致性哈希：一桌人围圆桌按钟点坐，新来一人只挤占他落座点左右邻座的空间，其他人纹丝不动。
  • 布隆过滤器：门卫记人靠「特征指纹清单」——清单上没有名字的肯定没来过；有名字的也可能只是指纹撞车，需要再查花名册确认。

公式或模型

误判率推导骨架：单一位在某次插入后仍为 0 的概率是 (1 − 1/m)^(kn) ≈ e^(−kn/m)；查询的 k 位全被他人置 1 的概率即上式 k 次方。代入最优 k 得每位比特数与 p 的关系：

p = (1 − e^(−kn/m))^k ,  k* = (m/n) ln 2
例：n = 10⁷, 目标 p = 1% ⇒ k* ≈ 7, m/n ≈ 9.6 位/元素
⇒ 总内存 ≈ 10⁷ × 9.6 / 8 ≈ 12 MB（对比存 10⁷ 条字符串至少数百 MB）

一致性哈希迁移量：节点从 N 到 N+1，期望迁移比例 ≈ 1/(N+1)。

图示

哈希环:            0°
          节点B ●     ● 节点A
        （每节点再拆 100+ 虚拟点均布环上）
       键 h(k) 顺时针找下一个节点。
  新增节点C → 只接管 B→C 弧段上的键，其余不动。

布隆过滤器: k=3
插入 x:  h₁=h₃, h₂=h₇, h₃=h₉ → bits[3]=bits[7]=bits[9]=1
查询 y:  bits[h₁(y)]..bits[h₃(y)] 全 1 ⇒ "可能存在"（待回源确认）

实例或案例

  • Memcached/早期 Dynamo 一致性哈希分片；Kafka 分区分配、分库分表中间件同样借鉴环形/带权哈希。
  • Redis 集群用 16384 槽（预分裂的固定桶 + 槽迁移）是同一思想的变体：先分大量槽再映射节点，扩缩容只搬槽。
  • Chrome 浏览器恶意网址检测用布隆过滤器先本地过滤；爬虫 URL 去重； Cassandra/LevelDB/HBase 在磁盘读路径上用布隆过滤器挡住「键不存在」的无谓 IO。
  • 变体：计数布隆（支持删除）、Cuckoo Filter、HyperLogLog（基数估计，标准误约 1.3%）。

常见误区

  • 把「可能存在」当「一定存在」：布隆说存在只是概率说 yes，必须回源二次确认；说「不存在」才是硬保证。
  • 认为一致性哈希天然均匀：节点少时环上弧长方差极大，必须靠虚拟节点数量修正。
  • 布隆参数拍脑袋：m、k 必须按预估 n 与目标 p 计算；元素远超 n 时误判率失控，且位数组无法动态扩。
  • 需要删除/计数时仍用普通布隆：应换计数布隆或 Cuckoo Filter，否则删除会误伤其他键。

自测题

  1. n=10⁶、p=1%，布隆过滤器最优 k 与总内存大约多少？

答案要点：k≈7，每元素约 9.6 位 ⇒ 约 1.2 MB。

  1. 为什么布隆过滤器不支持删除？计数布隆怎么解决？

答案要点：多位共享、无法区分归属；计数布隆把每 bit 换成小计数器，删除即减一，代价是空间翻数倍且计数器可能饱和。

  1. 普通取模分片从 8 台扩到 9 台，期望多少比例的键需要迁移？一致性哈希呢？

答案要点：普通取模几乎所有键（≈8/9）换宿主；一致性哈希期望约 1/9。

与其他知识点的关系

kp-009 是两者的母体；kp-015 LSM 用布隆过滤器优化读路径；kp-023 海量 Top-K 场景会同时用到一致性分片与概率结构；kp-031 位运算实现位数组。

延伸阅读

Bloom 1970 原始论文；Karger 等 1997 一致性哈希论文；Mitzenmacher & Upfal《Probability and Computing》相关章节。

前置知识点

相关知识点