商过滤器 | Codeboy's Blog

形式陈述

原键近似，完整指纹精确

选正整数q、r，令 $p=q+r$ 、 $m=2^q$ 。原键x先得到p位指纹f(x)，分成q位商Q和r位余数R：

f(x)=Q\,2^r+R,\quad 0\le Q<m,\quad 0\le R<2^r.

商过滤器在m槽数组里保存指纹多重集，每槽只有r位余数和3个状态位，不为每条记录直接保存商。本文保留至少一个空槽，记录数 $n\le m-1$ 。查询先算f(x)，再精确判断这个指纹是否出现；指纹缺失意味着x确定不存在，出现只说明x可能存在。[1, §3]

同商的记录构成一段run，余数非降排列；不同run按其商的循环次序排列。从一个真空槽之后开始读，便可把循环序列展开。发生碰撞时，run整体向右挤，但它的逻辑首页仍是Q。

三个状态位分别是：

O[j]：是否存在商为j的记录，属于逻辑首页j
C[j]：槽j记录是否继续前一记录的同商run，即它不是run首项
S[j]：槽j记录是否离开了自己的逻辑首页

O不随记录移动；余数、C、S描述物理记录，移动时C/S还可能要调整。稳定合法状态中，三位都为0的槽才是真空槽。余数0本身是合法数据，不能用它表示空。[1, §3，pp.1630–1631]

双游标找回省略的商

查询指纹(Q,R)先看O[Q]；为0即可否定。否则，从槽Q向左走到第一个S=0的位置b。这是当前聚簇首项，物理run首项游标s也置为b。聚簇内每个置位O对应一个run，二者次序一致：

text

while b != Q:
    s = s + 1
    while C[s] == 1: s = s + 1
    b = b + 1
    while O[b] == 0: b = b + 1

所有槽下标模m。每轮让s跳过一个完整run，让b跳到下一个非空逻辑桶，所以两者始终对应。b抵达Q时，s就是目标run首项。沿run查余数，遇等于R就成功，遇大于R或run末尾即失败。

向左搜索不会把目标误带到无关空槽：若Q处被更早run占用，它的S为1；若该处已经是目标run未移位首项，则S为0。至少一个真空槽给每段拥挤布局提供了不绕无限圈的锚点。

直觉

省掉商以后，仍要知道每段属于谁

直接保存完整p位指纹很简单，却浪费了“数组位置已经提供了一部分地址”这一信息。无碰撞时，商Q的记录就在槽Q，存R已足够；碰撞后，位图O保存哪些首页确实有记录，C保存物理run边界，S保存聚簇锚点。双游标把这两份顺序信息重新配对。

这里不是“只比余数即可”。两个不同商可以有相同余数，它们属于不同run；必须先找对商。近似发生在不同原键拥有同一个完整p位指纹时，不能与单纯首页冲突混为一谈。

例子与边界

一个位既描述首页，又落在别人的run中

取q=r=3，容量8。依次插入完整指纹9、11、18，即(1,1)、(1,3)、(2,2)。表为：

物理槽	余数	O	C	S	记录实际所属商
1	1	1	0	0	1
2	3	1	1	1	1
3	2	0	0	1	2

槽2的O=1表示商2存在，但槽2里的余数3属于商1。若把O随这条记录搬走，就会改变另一个逻辑桶的存在性。查询18从Q=2向左退到1，物理s跳过商1的两项到3，逻辑b跳到置位O[2]，于是两者正确配对。

再插入10=(1,2)，它进入商1的有序run中间：槽1至4余数为1、2、3、2，C为0、1、1、0，S为0、1、1、1；O仍只在1、2置位。排序的是每个run内部，不是整张表的余数。

商过滤器的O位留在逻辑首页，C和S描述物理余数记录；两游标按同一run序号前进。

插入与删除怎样改位

插入先检查容量；已满到m−1时返回失败且不改状态。首页真空则直接存余数、置O。否则记住原O[Q]，将它置1，再用双游标定位目标run：旧run内按余数找位置，新run按逻辑商次序插在对应边界。

把后继记录向右推到最近真空槽，O各留原地。新记录若在run首项，C=0，否则C=1；若在旧首项前插入，旧首项C必须改为1。凡向右移动的旧记录都已经离开首页，S置1；新记录的S按实际槽是否等于Q设置。重复完整指纹也插入一份，不能默默折叠。

删除先定位一个匹配记录。若它是此商唯一记录，清O[Q]；若它是run首项且后面还有同商记录，把后继的C清0。之后留下一个洞，把后面S=1的连续记录逐项左移，遇空槽或S=0的记录停止。

左移时须知道记录属于哪个商，才能重新算S。维护当前商指针：遇旧C=0的新run首项，就向前找下一置位O；旧C=1仍属于原run。记录移到其商槽时，S变0，否则仍为1。最后清洞的C、S；此时洞的O也必须为0，这是可检查的不变量，而不是允许随意把O一起清掉。

正确性依赖两份顺序同步：右推和左移都不交换记录先后次序；run首项变化通过C维护，存在的商通过O维护，聚簇起点由S=0重建。于是更新后双游标仍按相同序号配对逻辑商和物理run，解码得到的多重集恰增加或减少一份目标指纹。

“可能存在”不能授权删除

设两个不同原键x、y恰有同一指纹。若两者都已插入，表内应有两份指纹；删掉已确认存在的x后仍留一份，y不会假阴性。若把重复指纹去重，删除其中一键就会把另一键的证据也删掉。

反过来，x根本不在集合中，仅因撞上y而查询为真，此时删除x会误删y的唯一指纹。因此原键层删除必须由权威集合确认x确实存在，或由外部一致的引用计数/操作历史保证。过滤器不能单靠自身“可能存在”的回答验证删除前提。重复插入同一原键的策略也须由上层规定；本文底层接口每次增加一份指纹。

推论与应用

概率、空间与最坏扫描

先固定存储的不同原键和一个非成员x。若f按独立均匀的p位分布作用于这些键，k个不同已存键给出

\Pr[\text{误报}]=1-(1-2^{-p})^k\le k2^{-p}\le n2^{-p}=\alpha2^{-r},\qquad \alpha=n/m.

这里n是存储的指纹记录数，可能因重复而大于k。若只知f来自通用哈希族，仍可对每个固定键对的完整指纹碰撞用并集上界 $k2^{-p}$ ；精确乘积公式则不再由两键碰撞界推出。看到函数后自适应选择查询也不在此固定查询证明里。

主表占m(r+3)位，另需种子、容量等元数据；每记录主表成本为 $(r+3)/\alpha$ 位。低负载会浪费空槽，高负载则增加扫描与挤动，不能只比较单槽r+3位便声称任意负载都节省空间。

按余数和下标装入RAM字计，查找、插入、删除最坏均O(m)。定位时两游标各只向前走，删除维护商指针也不反复从头找，故不是把每次移动再乘一次全表扫描。随机负载下的短聚簇需额外分布分析；确定性正确性不依赖这些平均性能假设。

与静态Xor过滤器不同，本接口可逐项改动已编码指纹多重集，代价是位状态维护和位移；Xor的剥离证书则在整批构建时一次完成。二者都没有原键层的精确肯定答案。

终点任务进一步插入58、59、1，使商7的run绕回槽0，再解码整张表并删除10。必须同时列出O、C、S以及商/余数对应；只展示查询布尔值无法发现位归属错误。

参考资料

[1] Michael A. Bender等，Don't Thrash: How to Cache Your Hash on Flash，PVLDB 5(11)，2012，pp.1627–1637，§3，尤其印刷pp.1629–1631及Figure3：商余数表示、三位元数据、双游标和更新。本文选用有真空槽的顺序多重集版本，并给出循环、重复指纹与删除前提检查。

形式陈述 ​

原键近似，完整指纹精确 ​

双游标找回省略的商 ​

省掉商以后，仍要知道每段属于谁 ​

一个位既描述首页，又落在别人的run中 ​

插入与删除怎样改位 ​

“可能存在”不能授权删除 ​

概率、空间与最坏扫描 ​

反向链接