基于Bloom Filter 的Left 算法的应用研究

刘文君 曹 伟 王 键

（江阴职业技术学院，江苏 江阴 214405）

1. 引言

布隆过滤器已经得到深入研究，普遍认为bloom filter 的优势在于快捷和空间利用率高，缺点是存在一定的识别错误率[1]。本文尝试结合d-left 算法，对原有布隆过滤器进行优化改进，解决一般哈希表存在的最坏访问时间的问题。在实现方面可以按照设计需要折中考虑存储器利用率、加入失败概率等因素，具有很好的灵活性和可扩展性，以期提高空间效率。

2. 基于Bloom Filter的Left算法概述

2.1 Left Counting Bloom Filter 算法的格式

若d=2 时，2-left Hashing 指的是将一个哈希表分成长度相等的两半，分别叫做T1和T2，给T1和T2分别配备一个哈希函数，h1和h2。在存储一个新的key 时，同时用两个哈希函数进行计算，得出两个地址h1[key]和h2[key]。这时需要检查T1中的h1[key] 位置和T2中的h2[key]位置，哪一个位置已经存储的（有碰撞的）key 比较多，然后将新key 存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key，就把新key 存储在左边的T1子表中，2-left 也由此而来。在查找一个key 时，必须进行两次Hash，同时查找两个位置[2]。

Left Hashing 是对前者的扩展。2-left Hashing 固定了对应的子表的个数是2，d-left Hashing 更加灵活，子表的个数是一个变量d，同时也意味着哈希函数的个数是d。在d-left Hashing 中，整个哈希表被分成d 个从左到右依次相邻的子表，每个子表对应一个相互独立的哈希函数。在加入新key 时，这个key 被d 个哈希函数同时计算，产生d 个相互独立的位置，然后将key 加入到负载最轻的位置（bucket）中。如果负载最轻的位置有多个，就把key 加入到最左边的负载最轻的子表中。同样地，如果要查找一个key，需要同时查找d 个位置。

2.2 Left Counting Bloom Filter 算法的空间分配

哈希函数的输出值（Hash value）通常有两种用途：一种用作地址，比如在哈希表中要存储一个元素，首先要针对这个元素生成一个随机地址；另一种用作fingerprint（或者叫digital summary），比如将密码字符串Hash成一个fingerprint，验证时进行核对。d-Left hashing 的存储信息的方式是将以上两种用途结合了起来：一个Hash value 分作两部分，一部分用作存储地址，另一部分用作fingerprint。

使用一个哈希函数，将其Hash value 分作两部分，高位部分用作随机地址，低位部分留作fingerprint。若用这一个哈希函数存储一个集合，则在基于Perfect Hashing 的方法中，第一步用的哈希函数是Perfect Hash Function，即一个集合的n 个元素会映射到n 个bucket中，没有碰撞。由于Perfect Hash Function 不能应对变动的集合，并且对大多数应用来说开销太大，所以上述所说的一个哈希函数并不是Perfect Hash Function。由此可知碰撞会产生，并且各个bucket 的负载并不均衡，实际上单个哈希函数Hash value 的分布服从泊松（Poisson）分布[2]。

从一个Hash value 同时用作地址和fingerprint 出发，构造一个简洁的存储方式来存储一个集合的fingerprints 基本可行，但遇到了负载不均衡的问题。为此提出使用d-left Hashing 来了解决哈希表的负载平衡问题。在没有d-left Hashing 的情况下，同一个Hash value 高位用作地址低位用作fingerprint，这就意味着同一个地址对应着多个fingerprint。一个地址对应一个bucket，因此一个bucket 需要存储多个fingerprint。由于单个哈希函数的Hash value 分布不均，各个bucket 的负载也不均衡。如果每个bucket 能存储的fingerprint 数量固定，为了不溢出必须按最坏的情况来分配bucket 的容量，这就造成了不小的浪费。

使用d-left Hashing 之后，fingerprint 的分布相对比较均衡，因此大大减少了空间的浪费。原来即使分配很大的哈希表，由于按最坏情况分配bucket 容量，仍然很难缩小bucket 的容量，并且哈希表中大量空间闲置。而使用d-left Hashing 可以让存储的信息分布均匀，更加紧凑，从而用更小的空间存储同样多的信息。在前文Perfect Hashing 章节中提到过，d-left CBF 可以比CBF节省至少一倍的空间，就是因为CBF 负载不均衡，很多空间都被浪费掉了。

因此，d-left CBF 的主要思路就是利用d-left Hashing 的方法存储fingerprint。

2.3 Left Counting Bloom Filter 算法的调用方法

首先使用一个d-left 哈希表，表中每个bucket 可以容纳若干个（固定数量的）cell，每个cell 的位数固定，包括一个fingerprint 和一个counter。包含一个fingerprint还要包含一个counter 是为了处理碰撞（collision）。在dleft 哈希表的d 个子表中，每个子表都要处理碰撞的情况。在某一个子表出现碰撞时，会发现已经有同样的fingerprint 被存储到同一位置，因此，有了counter 只需把counter 的值加1 即可。

在没有应用d-left Hashing 的情况下，使用一个哈希函数，把它的Hash value 分成两段，高位作存储地址，低位作fingerprint。现在要应用d-left Hashing，有d 个存储地址需要生成，仍然用一个哈希函数，但把它的Hash value 分成d+1 段：高位的d 段分别用作d 个存储地址，每个子表对应一个，剩下的低位部分作为fingerprint。

在添加一个key 时，先对它作一次Hash，得到d 个存储位置和一个fingerprint，然后判断d 个位置中的负载情况，并在负载最轻的几个位置中选择最左边的插入。如果选择的位置已经存储了相同的fingerprint，就把那个cell 的counter 加1。在删除一个key 时，同样地作一次Hash，然后在d 个存储位置查找相应的fingerprint，如果找到就将这个cell 置空或者将相应的counter 减1。

到此为止d-left CBF 的构造基本完成。但实际上，上面的构造过程中有一个缺陷，这个缺陷会在从集合中删除元素时出现。

针对该缺陷，特别提出对应的优化补救办法来改进d-Left CBF。

3. 对于Left算法下的BloomFilter的优化改进

3.1 基于Bloom Filter 的Left 算法的优化改进

根据前面的描述并分析，不难发现出现该缺陷的有三个前提：

(1) x 和y 的fingerprint 相同；

(2) 位置选择有重合；

(3) x 不选择重合位置，y 选择重合位置；

其中fingerprint 相同无法避免，因为碰撞总会出现，cell 中的counter 也是为此而设置的。元素是否选择重合位置也无法控制，因为这要根据当时的负载情况而定。所以能够弥补这个缺陷，只能从位置重合入手。即在不考虑碰撞的前提下，使得不同元素的d 个位置选择完全没有重合[3]。

为此提出的解决方案是：将Hashing 的整个操作分成两个阶段。第一阶段，用一个哈希函数H 计算要插入元素x 的Hash value，记做fx；第二阶段，为了获得d 个存储位置，另外引入d 个随机置换（random permutation）。令

其中b 是bucket index，表示存储位置；r 是remainder，表示要存储的fingerprint。然后令d 个置换为：

其中Pi(fx)对应着x 在第i 个子表的存储位置和fingerprint。因为置换意味着一一对应，因此不同元素的Hash value 作置换之后的值仍然不同。这样就达到了前面提到的让不同元素的d 个位置选择完全没有重合的目标[3]。

引入随机置换避免了位置重合之后，还需要在插入元素之前完成一项工作。每次插入一个元素时，先要在它的d 个位置选择中检查是否已经存有相同的fingerprint，如果有，就把相应cell 的counter 加1。由于不同元素的存储位置不会重合，因此只有在碰撞的情况下才会出现两个相同fingerprint 能存入同一组存储位置的情况。而一旦在插入之前作了检测，再作删除操作时就永远不会发现d 个位置中有两个完全相同的fingerprint。至此，删除元素时的缺陷问题已经完全解决。

3.2 Left Counting Bloom Filter 的优化与标准CBF 的比较

若将d-Left CBF 与标准的CBF 进行比较，假设要表示的集合有m 个元素，构造d-left CBF 的各个参数如下：

Left 哈希表包含4 个子表；每个子表包含m/24 个bucket，使得bucket 的平均负载是6 个元素；子表中每个bucket 可以容纳8 个cell，8 个就能以很高的概率保证不会溢出；cell 中每个counter 包含2 位，可以容纳4 个相同的fingerprint；且fingerprint 设置必须为表示空的状态即全0。

假设用r 位表示fingerprint，那么false positive 的概率就是24×2-r。其中两个fingerprint 完全相同的概率为(1/2)r，又因d-left hashing 使得查找时有4 个选择（有4个子表），每个选择对应一个bucket，一个bucket 平均负载是6，所以需乘以24。整个d-left CBF 所需的所有位数为4m(r+2)/3。其中r+2 表示一个cell 的位数，m 是集合元素个数，一个bucket 能容纳8 个cell，但平均负载是6 个，所以乘以4/3 就得到全部的位数。

再与标准CBF 进行比较。假设对于m 个元素的集合，CBF 使用cm 个counter，每个counter 使用4 位，哈希函数的个数k 使用最优值cln2，得到false positive 的概率为（2-ln2）c，总共使用4cm 位。如果令c=(r+2)/3，则两种方法使用的位数相同，比较false positive 概率会发现当r≥7 时，

（2-ln2）（r+2）/3＞24×2-r

而且使用的位数越多，两个false positive 概率的差距就越大。当r = 14 时，c = 16/3，虽然两个结构使用的位数相同，但CBF 比d-left CBF 的false positive 概率大100 倍以上。

若false positive 概率相同，假设标准CBF 使用9 个4 位的counter（每个元素36 位），6 个独立的哈希函数，得到的false positive 概率为0.01327。d-left CBF 使用11位的fingerprint（每个元素52/3 位），得到的false positive概率为0.01172。计算可得，（52/3）÷36= 0.48，即d-left CBF 只使用了CBF 不到一半的空间，就得到了比CBF更低的错误率。

因此由于d-left CBF 负载均衡，可比负载不均衡的CBF 节省至少一倍的存储空间。

4. 仿真测试

通过仿真测试，比较d-left CBF 和标准CBF。首先，确定一张哈希表，包含4 个子表，每个子表包含2048 个bucket，子表中每个bucket 容纳8 个cell，可处理4×2048×8=216 个元素，假设预期的目标负载值为3×214=49152，那么49152÷（4?2048）=6，即平均每个bucket 负载6 个。正如前面章节介绍，如果bucket 的过载非常小，可以被忽略不计，在本例中，每个元素的过载量大约是接近10-27，完全可以忽略。其次，设置剩下部分的每个cell，所使用的计数器的位数，本次仿真中设置cell 中有14 位用于存放fingerprints，已知假设用r 位表示fingerprint，那么false positive 的概率就是24×2-r=24×2-14≈0.001465。

在这个表构造中，将Hashing 的整个操作分成两个阶段。第一步用了一个（Perfect）哈希函数生成了这个元素的存储地址，第二步用另一个哈希函数生成这个元素的fingerprint，然后将fingerprint 存储到第一步生成的地址中。另外引入d 个随机线性置换（random linear permutation），因为置换意味着一一对应，因此能保证不同元素的Hash value 做置换之后的值仍然不同。

当这些都构建完毕以后，重复上文所述测试10000次，在每次试验中，均按照之前对d-left CBF 的预计，将总共的负载设置为3×214=49152，从而保证每个bucket的平均负载为6 个元素。在所有的随机插入和删除操作后，溢出没有出现，检查bucker 的负载和对照bucket 的分布，可以获得下表结果。

?

仔细观察表中数据，不难发现仿真结果已经非常接近预期。

同样通过10000 次试验，获得标准CBF 的false positive 概率在0.108 ～0.205 之间，其平均值大约低于0.1529，非常接近的预期。注意这个值高于d-left CBF 的false positive 概率，约0.86 左右。所以通过本次仿真测试，获得d-left CBF 比CBF 使用更少的存储空间，却能得到比CBF 更低的运算错误率，也就是具有更高的效率。

比较d-left CBF 与原先标准的CBF，首先从理论着手进行推导，当这两种CBF 使用的hash 表位数相同，CBF 的false positive 概率高于d-left CBF 的false positive 概率，而且随着使用的位数越多，两个false positive概率的差距就越大。反之，若false positive 概率相同，dleft CBF 只使用了CBF 不到一半的hash 表位数，换个说法就是节约了一半的空间。其次通过仿真试验，构建一个虚拟网络环境，对网段内节点进行测试，完成动态删减和自动更新的操作，实践结果证明了的理论推导是正确的，空间确实被节约了一半左右。

5. 小结

对d-left CBF 而言，其主要的思路就是将d-left Hashing 加入到计数型Bloom Filter 中，利用d-left Hashing 的方法存储计数型Bloom Filter 中的fingerprint，从而用更小的空间存储同样多的信息。

对于当前网络而言，随时变化的节点信息，是一个巨大的信息量，而如何有效地存储管理这些信息更是一个难题。对于标准的BF 而言，虽然处理速度非常快捷，但是功能过于简单，特别是不具有删除操作，当节点出现损坏，需要从集合表中删除该节点信息时，这个漏洞就显而易见了。对于标准的CBF 而言，虽然增加的删除操作，但却付出了存储空间成倍增长的代价。d-left CBF就是为了改进标准的CBF 臃肿的结构而提出的。

因此，确信将d-left Hashing 加入到CBF 中，利用d-left Hashing 的方法存储CBF 中的fingerprint，确实能用更小的空间存储同样多的信息，同时还能保留原有CBF 的删除操作功能，实现对网络中随时变化的节点信息的动态管理。在实践中，将这种哈希表结构应用到千兆以太网接入网关上实现流量统计和过滤，收到了很好的效果。值得在今后的网络管理中使用。

[1]肖明忠，代亚非.Bloom Filter及其应用综述[J].计算机科学，2004，(04)：180-183.

[2]谭兴晔，张勇，雷振明.基于d-left算法的硬件哈希表研究与实现[J].计算机应用研究，2005，(10)：52-55.

[3]C.Rijmen，V.klavos.N.The NIST Cryptographic Workshop on Hash Functions Rechberger[J]，Security&Privacy Magazine，IEEE Volume 4，Issue1，Jan-Feb.2006：54-56.

[4]AndreiB，M ichaelM.Net work applications of bloom filters：a survey[J].InternetMath，2003，1(4)：485-509.

[5]刘卫江，白磊，景泉.基于Sample_CBF技术的长流识别实现[J].计算机工程，2007，33(20)：116-118.