Bloom Clock

标签

分布式/时钟

字数

2661 字

阅读时间

11 分钟

Vector 向量时钟的空间是 $O (N)$ （ $N$ 是节点数）—— 每个节点都要为每一个已知节点维护一个计数器。节点数上万时这个向量本身就撑不住。

Bloom Clock 是 Lum Ramabaja 提出的概率型逻辑时钟（arXiv:1905.13064v4，2019-06-09），它换掉的就是这个 $N$ ：空间复杂度不依赖节点数，只依赖选定的参数，代价是判断从精确变成带置信度的。

这是一篇 arXiv 预印本，未经同行评审。下面的机制与公式来自该文，但结论的可靠性低于正式发表的版本。

用什么替代定长向量

向量时钟的每个分量是一个"我对节点 $j$ 知道多少"的整数。Bloom Clock 把这 N 个计数器换成一个定长的计数数组：长度为 $m$ 的数组，每个槽位是一个整数计数器（counting bloom filter，取值可累加，不限于 0/1）。

节点的每次事件不直接写"我推进了"，而是把这个节点自己的标识散列 $k$ 次，落到的槽位各自加一：

event(node_id):                 # 数组记为 A，长度 m，初值全 0
    for h in hash_functions:    # 共 k 个哈希函数
        A[ h(node_id) ] += 1

合并两个时钟（对应接收消息）就是逐槽位取最大，与向量时钟的 join 语义一致。

关键点是：同一个节点多次事件会落在同一组槽位上，所以计数增长反映的是"这个节点活跃了多少次"；不同节点之间靠哈希碰撞共享槽位。这个设计直接决定了后面误报的来源 —— 碰撞。

一个定长计数数组替代 $N$ 个计数器（ $m = 8$ 示意， $k = 3$ 个哈希函数）：

   节点 X 的一次 event ──▶ 落到 h₁(X)=2、h₂(X)=5、h₃(X)=7，这三个槽位各加一

      槽位   0    1    2    3    4    5    6    7
             [0]  [0]  [1]  [0]  [0]  [1]  [0]  [1]

   同一个节点再来一次 event ──▶ 还是这三个槽位各加一

      槽位   0    1    2    3    4    5    6    7
             [0]  [0]  [2]  [0]  [0]  [2]  [0]  [2]
      ⇒ 计数增长反映的是「这个节点活跃了多少次」

   节点 Y 的哈希压到了 X 用过的槽位上 ──▶ 碰撞，这就是误报的唯一来源

   合并两个时钟（对应接收消息）= 逐槽位取 max，与向量时钟的 join 语义一致

       A      [0]  [2]  [1]  [2]  [0]  [2]  [0]  [1]
       B      [2]  [2]  [1]  [2]  [1]  [2]  [0]  [0]
       max    [2]  [2]  [1]  [2]  [1]  [2]  [0]  [1]

比较规则：一边无假阴性，一边有误报

比较两个 bloom clock $A$ 与 $B$ 时只有两种结果：

情形一：存在某个槽位 $i$ 使 $A_{i} > B_{i}$ 。 这一条没有任何误判可能 —— 若在 $B$ 中某个槽位的计数比 $A$ 里小，说明 $A$ 记录的事件不可能全部被 $B$ 覆盖，两者必须不可比。该文的表述是 "false negatives are not possible"。

情形二：对所有槽位 $A_{i} \leq B_{i}$ 。 这时只能说" $A$ 可能先于 $B$ "。它可能是真的先后，也可能是误报： $A$ 记录的事件其实从未先于 $B$ 发生过，只是 $B$ 的计数因为随机碰撞恰好每个槽位都不小于 $A$ 。该文把误报定义为"我们以为两个 bloom clock 之间存在顺序，但这个顺序不成立"。

误报的概率可以直接算。设 $\sum_{i} B_{i}$ 是 $B$ 的总计数（总增量）， $\sum_{j} A_{j}$ 是 $A$ 的：

P_{误报} = {(1 - {(1 - \frac{1}{m})}^{\sum_{i} B_{i}})}^{\sum_{j} A_{j}}, \sum_{i} B_{i} \geq \sum_{j} A_{j}

拆开看每一项的来历： $1 / m$ 是某个槽位被一次增量命中的概率； $(1 - 1 / m)^{\sum B_{i}}$ 是经过 $\sum B_{i}$ 次增量后某个槽位仍然为 0 的概率；括号里是"该槽位已被命中过"；最后外层的 $\sum A_{j}$ 次方表示" $A$ 用到的每个槽位都被覆盖"。

注意公式里两个指数上的量：两个时钟的总计数差距越大， $\sum B_{i}$ 相对 $\sum A_{j}$ 越悬殊，误报率越高。该文给出的另一个量也指向同一件事 —— 逐槽位绝对差之和 $\sum_{i} | B_{i} - A_{i} |$ 越大，比较结果越可能是误报。

算例

一对具体的数组可以演示"怎么判"：

A = [0, 2, 1, 2, 0, 2], B = [2, 2, 1, 2, 1, 2]

两个数组长度都是 $m = 6$ ，各自的增量和是

\sum A_{i} = 7, \sum B_{i} = 10

判定分两步：

第一步，逐槽位看是否被覆盖。 若存在某个槽位 $A_{i} > B_{i}$ ，直接判不可比（这一步不会错）。本例里每个 $A_{i} \leq B_{i}$ ，所以 $A$ 被 $B$ "覆盖"（overlap），进入第二步 —— 但此时还不能下结论。

第二步，算误报率。 代入公式：

P = {(1 - {(1 - \frac{1}{6})}^{10})}^{7} = (1 - 0.1615)^{7} = {0.8385}^{7} \approx 0.29

也就是约 29% 的概率， $B$ 是在完全没有"见过 $A$ "的情况下、仅靠 10 次随机增量就碰巧覆盖了 $A$ 。这个数就是" $A$ 真的先于 $B$ "这一判断的置信度缺口。

这一步的解释是： $\sum B_{i}$ 相对 $\sum A_{j}$ 越悬殊，误报率越高 —— 上面 $\sum B_{i}$ 只比 $\sum A_{j}$ 多 3，所以误报率没有失控；若 $B$ 的增量远多于 $A$ ，这个数字会迅速逼近 1，判断就失去意义。

两步判定与它的两个方向：

      A = [0, 2, 1, 2, 0, 2]              B = [2, 2, 1, 2, 1, 2]
                 │
      ┌──────────┴──────────┐
      ▼                     ▼
   存在槽位 A_i > B_i       所有槽位 A_i ≤ B_i
      │                     │
   判「不可比」             判「A 可能先于 B」—— 只给到置信度
   （这一步绝不会错）        │
      │                     ├── 总计数差距小 ⇒ 误报率可控（本例 ≈ 29%）
      │                     └── 总计数差距大 ⇒ 误报率逼近 1，判断失去意义
      │                                          │
      │                          用 moving window 收窄：让计数大的那一方
      │                          挑出与自己时间戳差异最小的历史时间戳，重比一次
      └───── 「无假阴性」保障的是左边这一支 ─────┘

moving window：用历史把窗口收窄

误报率随总计数差距上升，意味着两个时钟的规模差到一定程度后就无法判别。这被称为一个"窗口"：在 $A$ 与 $B$ 之间发生的事件数落在这个窗口内，就无法确定顺序。

它给的缓解办法是让节点额外保存过去事件的时间戳，具体流程是：

先按上面的两步判定，得到" $A$ 可能先于 $B$ "；
计数较大的那一方（本例里是 $B$ ）在自己的历史时间戳里，挑出与对方时间戳差异最小的那一个；
拿这个更接近的时间戳重新做一次比较 —— 两者规模接近时误报率低，于是把不可判定的窗口收窄。

代价是空间不再恒定 —— 保存历史就等于把省下的向量换成了时间线。这个折中与方案的定位一致：优势集中在节点数远大于单节点平均本地事件数、且节点频繁更替的场景，并非普遍优于向量时钟。

顺带：底层 bloom filter 的三步与误报率

Bloom Clock 复用经典 bloom filter，该文也把它的完整算法与误报率公式给了出来，分三步：

定义 $k$ 个哈希函数；
定义一个 $m$ 位的位数组，初值全 0；
加入元素：把元素哈希 $k$ 次，把得到的 $k$ 个下标位置从 0 置为 1；查询元素：哈希 $k$ 次后查这 $k$ 个下标，只要有一个为 0 就说明该元素从未来过。

第 3 步的第后半句正是"没有假阴性"的来源。误报则来自碰撞：例子是插入 $Y$ （哈希到 ${11, 6, 1}$ ）与 $Z$ （哈希到 ${5, 2, 9}$ ）之后，查询一个从未插入的 $X$ 时它的三个下标恰好是 ${1, 5, 2}$ ，全为 1 —— 于是"看起来像插入过"。误报率：

P_{误报} = {(1 - {(1 - \frac{1}{m})}^{k n})}^{k}

$m$ 是数组长度， $k$ 是哈希函数个数， $n$ 是插入的元素数。三个变量可以自由调节 —— 这是 bloom filter 能"用可控的误报换空间"的原因。Bloom Clock 把位数组换成计数数组（counting bloom filter），因为时钟要能反映"多少次"而不是"有没有"。

经典 bloom filter：位数组加 $k$ 个哈希（ $m = 12$ 示意）

   插入 Y（哈希到 1、6、11）：    0 1 0 0 0 0 1 0 0 0 0 1
   插入 Z（哈希到 2、5、9）：     0 1 1 0 0 1 1 0 0 1 0 1
   查询 X（哈希到 1、5、2）：     三个位置全是 1 ⇒ 「看起来像插入过」⇒ 误报

        │           │     │
        └───────────┴─────┘  这三个位置是别的元素置上去的 —— 碰撞

   更新只有 0 → 1、没有 1 → 0 ⇒ 不存在假阴性；误报只能来自碰撞
   Bloom Clock 把它换成计数数组（counting bloom filter）：
   要能反映「多少次」而不只是「有没有」

该记的判据

判据	Bloom Clock	Vector 时钟
空间复杂度	$O (m)$ ，与节点数无关	$O (N)$ ，与节点数线性
判断结果	不可比 → 确定；可比 → 带置信度	精确
无假阴性的方向	判"不可比"绝不会错	无此问题
可调性	用 $m$ 、 $k$ 、历史长度换取置信度	只能整体变长
适用场景	节点数极大、churn 高、允许概然判断	节点数有界、要求精确

参考

Lum Ramabaja. The Bloom Clock. arXiv:1905.13064v4 [cs.DC], 2019-06-09.

贡献者

文件历史

最后编辑于大约 23 小时前查看完整历史

语法基础

gpu

cuda

train

infer

Bloom Clock

用什么替代定长向量

比较规则：一边无假阴性，一边有误报

算例

moving window：用历史把窗口收窄

顺带：底层 bloom filter 的三步与误报率

该记的判据

相关

参考

贡献者

文件历史

Bloom Clock ​

用什么替代定长向量 ​

比较规则：一边无假阴性，一边有误报 ​

算例 ​

moving window：用历史把窗口收窄 ​

顺带：底层 bloom filter 的三步与误报率 ​

该记的判据 ​

相关 ​

参考 ​

贡献者 ​

文件历史 ​

Bloom Clock

用什么替代定长向量

比较规则：一边无假阴性，一边有误报

算例

moving window：用历史把窗口收窄

顺带：底层 bloom filter 的三步与误报率

该记的判据

相关

参考

贡献者

文件历史