Scalable Bloom Filter

#CS/DataStructure

可扩展布隆过滤器（Scalable Bloom Filter，SBF） 是为了解决传统布隆过滤器无法动态扩展，必须预先知道集合大小（ $n$ ）的问题而设计的。在实际使用中，集合大小往往不可知，过小的位图导致误报率增加；过大的位图导致空间浪费。

可扩展布隆过滤器 基于布隆过滤器变体。

原理

可扩展布隆过滤器 有两个关键点：

SBF 由一个或多个布隆过滤器变体组成
后续的布隆过滤器变体的误报率等比例缩小，以保证整体误报率保持在一个数值内

SBF 创建时有一个 $k_{0}$ 切片的位图，误报率为 $P_{0}$ 。当该过滤器满了（误报率即将超出阈值），就新增一个 $k_{1}$ 个切片，误报率为 $P_{1} = P_{0} r$ 的新过滤器，并保证 $0 < r < 1$ 。

当共计有 $l$ 个过滤器时， $l$ 个过滤器的误报率为 $P_{0}, P_{0} r, P_{0} r^{2}, . . ., P_{0} r^{l - 1}$ 。此时 SBF 整体的误报率为：

\begin{matrix} (1) & P = 1 - \prod_{i = 0}^{l - 1} (1 - P_{0} r^{i}) \end{matrix}

由于有缩放公示：

1 - \prod_{i} (1 - P_{i}) \leq \sum_{i} P_{i}

将缩放公示带入 (1) 可以得到 $P$ 的上限：

P \leq \sum_{i = 0}^{l - 1} P_{0} r^{i} \leq lim_{l \to \infty} \sum_{i = 0}^{l - 1} P_{0} r^{i}

因此有：

\begin{matrix} (2) & P \leq P_{0} \frac{1}{1 - r} \end{matrix}

每个过滤器的 slice 个数为

k_{0} = l o g_{2} (P_{0}^{- 1})

和

k_{i} = l o g_{2} (P_{i}^{- 1}) = k_{0} + i l o g_{2} (r^{- 1})

为了保证每个 $k_{i}$ 为整数，自然令 $r = \frac{1}{2}$ ，此时有

\begin{matrix} (3) & k_{i} = k_{0} + i \end{matrix}

意味着每个新加的过滤器都需要增加一个 slice。将 (3) 代入公示 (2)，此时 SBF 的整体纳伪率为

P \leq 2 P_{0} = 2^{1 - k_{0}}

除了令 $r = \frac{1}{2}$ 以保证 $k_{i}$ 为整数外，还可以选择其他的 $r$ ，并令

k_{i} = ⌈ k_{0} + i l o g_{2} (r^{- 1}) ⌉

论文证明 $0.8 \leq r \leq 0.9$ 时，虽然初始会使用更多内存，当可以使平均空间增长速度最低。^[1]

存储量增长

初始存储量影响初始空间占用，后续增加的过滤器会影响空间占用增长速度。自然，用户希望初始空间占用尽可能低，且使用时空间占用也合理。因此，SBF 应该能够以有效的方式适应几个数量级的大小变化。

当新增过滤器时，新过滤器可存储的元素数量取决于所需的误报率 $P$ 。为了灵活处理，选择指数增长的可容纳量，也就是不同过滤器中切片长度为 $m_{0}, m_{0} s, m_{0} s^{2} . . ., m_{0} s^{l - 1}$ 。

如布隆过滤器变体所属，当过滤器达到半满时停止插入，此时过滤器 $i$ 可以容纳

n \approx M \frac{(l n (2)^{2})}{| l n (P) |} < M \frac{(l n (2)^{2})}{| l n (2) |} = M l n (2)

代入可得

n_{i} < m_{0} s^{i} l n (2)

也就是说，有 $l$ 个过滤器的 SBF 可以容纳

(l n 2) m_{0} \sum_{i = 0}^{l - 1} s^{i}

元素。

论文讨论了不同 $s$ 的区值对空间增长速度的影响，这里不赘述。

应用

给定期望的误报率 $P$ ：

选择 $0.8 \leq r \leq 0.9$ ，并通过公示计算 $k_{i}$
对于缓慢增长，选择 $s = 2$ ，对于快速增长，选择 $s = 4$ ，并计算出 $m$

A Scalable Bloom Filter addresses the problem of having to choose an a priori maximum size for the set, and allows an arbitrary growth of the set being repre- sented. The two key ideas are:

A SBF is made up of a series of one or more (plain) Bloom Filters; when ﬁlters get full due to the limit on the ﬁll ratio, a new one is added; querying is made by testing for the presence in each ﬁlter.
Each successive bloom ﬁlter is created with a tighter maximum error probability on a geometric progression, so that the compounded probability over the whole series converges to some wanted value, even accounting for an inﬁnite series.

Almeida, Paulo Sérgio, Carlos Baquero, Nuno Preguiça, and David Hutchison. “Scalable Bloom Filters.” Information Processing Letters 101, no. 6 (March 2007): 255–61. https://doi.org/10.1016/j.ipl.2006.10.007. ↩︎ ↩︎