一致性布谷过滤器的操作方法

摘要

本发明提供了数据结构领域的索引独立布谷过滤器、一致性布谷过滤器及操作方法。索引独立布谷过滤器包括多个桶，每个桶有b个槽位，多个桶被映射到一个范围从1到M‑1的一致性哈希环中。一致性布谷过滤器，包括s个异构的索引独立布谷过滤器，每个索引独立布谷过滤器有mi≥1个桶，每个桶有bi≥1个槽位，其中，s≥1，初始为1，i∈[0,s‑1]。本发明还从插入、查询、删除元素介绍了一致性布谷过滤器的操作方法，以及一致性布谷过滤器的容量调整问题。本发明在容量弹性、空间效率以及设计伸缩性方面都有着良好的表现。

权利要求

1.一致性布谷过滤器的操作方法，其特征是，所述操作方法包括元素插入，元素查询和元素删除；所述操作方法还包括对一致性布谷过滤器的容量进行调整，调整方式包括扩容、缩容、扩展和压缩，扩展是指向一致性布谷过滤器中增加未使用的索引独立布谷过滤器，压缩是指压缩稀疏索引独立布谷过滤器；

当要表示的元素数量急剧增加时，通过向一致性布谷过滤器中增加单个或多个未使用的索引独立布谷过滤器使得一致性布谷过滤器的容量增加，增加的索引独立布谷过滤器是异构的，桶和槽的数量能被调整；

当索引独立布谷过滤器因为集合元素的移除而变得稀疏时，一致性布谷过滤器尝试通过压缩操作将该索引独立布谷过滤器移除：一致性布谷过滤器首先选取最低利用率的索引独立布谷过滤器向量并移除；

将被移除的索引独立布谷过滤器中的元素指纹ηx重新插入到一致性布谷过滤器中，如果所述被移除的索引独立布谷过滤器中的元素指纹ηx被成功插入到一致性布谷过滤器，被选择的所述被移除的索引独立布谷过滤器可以安全移除，否则，不需要进一步压缩一致性布谷过滤器，压缩持续移除索引独立布谷过滤器直到存在被移除的索引独立布谷过滤器不能被安全移除；

其中，所述一致性布谷过滤器包括s个异构的索引独立布谷过滤器，每个索引独立布谷过滤器有mi≥1个桶，每个桶有bi≥1个槽位，其中，s≥1，初始值为1，i∈[0,s‑1]；mi个桶被映射到一个范围从1到M‑1的一致性哈希环中，其中M是一致性哈希环的取值范围；每个桶可存储0‑b个指纹，且为每个元素x提供k≥1个候选桶，为了确定元素x的候选桶，k个相互独立的哈希函数被用于将元素指纹ηx映射到一致性哈希环中，k个哈希函数的k个最近的桶被认为是元素指纹ηx的候选桶。

2.根据权利要求1所述的一致性布谷过滤器的操作方法，其特征是，一致性布谷过滤器追踪每个索引独立布谷过滤器中插入的元素数量，并将插入最后一个元素的索引独立布谷过滤器标记为活跃索引独立布谷过滤器，元素插入的操作方式如下：f

索引独立布谷过滤器将元素x映射到整数区间[0,2 ‑1]中来生成元素指纹ηx，其中f为元素指纹长度；

相互独立的k个哈希函数将元素指纹ηx映射到一致性哈希环中，基于生成的哈希值，一致性哈希决定元素指纹ηx在活跃索引独立布谷过滤器中的候选桶；

将元素指纹ηx按布谷哈希中的策略插入到活跃的索引独立布谷过滤器中，如果活跃索引独立布谷过滤器成功存储元素指纹ηx，那么插入结束；否则，一致性布谷过滤器会进行扩容操作或者扩展操作，扩容操作或者扩展操作后，将元素指纹ηx插入到扩容的或者扩展的索引独立布谷过滤器中。

3.根据权利要求1所述的一致性布谷过滤器的操作方法，其特征是，元素查询的操作方式如下：

通过相互独立的k个哈希函数对元素指纹ηx进行哈希来决定元素指纹ηx在一致性哈希环中的位置；

基于哈希值，一致性哈希得出对于元素指纹ηx在索引独立布谷过滤器中候选桶的位置：如果任一候选桶持有元素指纹ηx，成员关系查询终止，返回存在；相反，如果在所有的索引独立布谷过滤器中，都没有找到元素指纹ηx，一致性布谷过滤器判定元素x不属于集合A，返回不存在。

4.根据权利要求3所述的一致性布谷过滤器的操作方法，其特征是，元素x的删除需要首先进行成员关系查询来找出元素的可能位置，元素删除的操作方式如下：如果对应的元素指纹ηx在一致性布谷过滤器中未找到，删除操作返回失败；如果对应的元素指纹ηx在一致性布谷过滤器中被找到则直接执行删除。

5.根据权利要求1所述的一致性布谷过滤器的操作方法，其特征是，扩容是指向索引独立布谷过滤器中增加桶，缩容是指通过从指定索引独立布谷过滤器中移除桶；

扩容时，在其后继中存储的元素指纹ηx会受到影响：新的桶Bnew被映射到Bi和Bj(i,j∈[0,m‑1])之间，Bj是Bnew的后继，在这种情况下，仅在Bj中存储的元素可能需要被重新放置到Bnew中，即如果在Bj中的元素指纹ηx被映射到Bi和Bnew之间，则它应该被移动到Bnew中；否则，应该继续留在Bi中；

缩容时，当某个桶从索引独立布谷过滤器中移除时，仅在此桶中的元素需要被重新放置到一致性布谷过滤器中：若一致性哈希中的桶Bi和Bj，Bj是Bi的后继，一致性布谷过滤器优先尝试将桶Bi中的元素指纹ηx推到桶Bj中，然后将剩余元素重新放置到其余桶中，如果Bi中的元素指纹ηx被全部成功存储，Bi能够被移除，否则，Bi不能被移除。

6.根据权利要求1所述的一致性布谷过滤器的操作方法，其特征是，容量调整的触发条件是：通过元素的到达速率α和元素移除速率β共同决定是否需要调整一致性布谷过滤器容量，当α＞β时，进行扩容或者扩展；当α<β时，进行缩容和压缩；

通过元素的到达速率α和一致性布谷过滤器假阳性比率上界 共同决定扩容或者扩展：当 时，是阈值，一致性布谷过滤器能够在小规模单体扩容操作下插入抵达元素，小规模单体为在每次扩展中只增加单个桶；当 时，在增加新的索引独立布谷过滤器之后总体的假阳性比率不会超过 扩展操作才被触发，否则，一致性布谷过滤器仅使用桶级别的单体扩容操作；

当缩容的条件与扩展的条件一致时，压缩的条件与扩容的条件一致。

说明书

一致性布谷过滤器的操作方法

技术领域

[0001] 本发明属于网络应用数据结构领域，具体是涉及到一种一致性布谷过滤器的操作方法。

背景技术

[0002] 在数据库、缓存、路由器、存储和网络应用中，集合表示同时支持成员关系查询是一个基本的问题。这些系统通常采用概率型数据结构来表示集合元素，在很小的假阳性比
率下支持常数时间成员查询操作。用于成员查询广泛使用的概率型数据结构有布隆过滤
器，布谷过滤器以及它们的变种。布隆过滤器和布谷过滤器用不同的方式表示元素。布隆过
滤器是一个固定长度的初始比特为0的数组。为了插入一个元素，k个独立的哈希函数用于
将元素映射到比特向量，然后相应的比特会被置1。当检测任意元素x的成员关系时，布隆过
滤器只检查k个相应的比特位是否为0。如果都是1，布隆过滤器得出x是集合成员(可能隐含
一个假阳性元素)；否则，可以正确的得出x不是集合成员(无假阴性)。和布隆过滤器不同，
布谷过滤器在桶中直接存储元素指纹。布谷过滤器通过部分布谷哈希得出元素的两个候选
桶，将指纹存入其中之一。如果元素的指纹在任意一个候选桶中找到，则认为元素是集合成
员。然而布谷过滤器和布隆过滤器因为不能重新设置容量大小不能处理动态集合成员。为
此，动态布隆过滤器(DBF)和动态布谷过滤器(DCF)已经被提出。DBF和DCF尝试根据需求增
加和合并同构的布隆过滤器和布谷过滤器来实现容量的伸缩性。在DBF和DCF中，每个过滤
器的长度都是预置的，因为格或桶的索引是基于过滤器的长度取余得到，所以过滤器的长
度不能改变。只能通过增加和合并同构的过滤器来调整容量。在最坏的情况下，因为一个额
外的元素需要一个过滤器，导致空间利用率低于50％的结果。因此，在空间稀缺的场景下，
桶级别的容量调整对于节省空间是必要的。而且，DBF主要的缺陷在于由于可能有多个布隆
过滤器满足查询条件，不能支持可靠的删除操作。尽管DCF保证可靠的元素删除，利用异或
γ
操作在重新放置时得到第二个候选桶。所以，每个布谷过滤器的长度只能是m＝2 (γ≥0)。
否则，异或操作会超出范围。

[0003] 用于动态集合表示的概率型数据结构主要关注以下三个准则：容量弹性(CE)。数据结构的容量是依据集合基数来适应性调整的。尽管要表示的元素数量不可预测，但是可
用容量大小要适应性的随着集合基数趋势变化一致调整；空间效率(SE)。无论集合基数的
变化如何，空间利用率都保持在较高水平。这对空间稀缺的场景十分重要，例如：无线传感
器网络。设计伸缩性(DF)。所有的参数都是可调整的，用户可以根据设计目标定制自身的配
置。例如：哈希函数的数量可能为了更高的空间利用而增加，为了更好的查询吞吐而减少。
如果这些准则可以实现，将会给集合表示和成员关系查询带来前所未有的好处，保证空间
节省和服务质量。设计伸缩性进一步将数据结构扩展到更多有不同需求的一般场景。

[0004] 然而，现有的概率数据结构不能正确的同时实现上述三条准则。布隆过滤器和DBF有低的空间使用率。原因是为了最小的假阳性比率，保持一半的比特位为0。相反，布谷过滤
器和它的变种通过在每次插入中的重放置策略提高了空间利用率。DBF和DCF通过动态增加
和合并过滤器在一定程度上提供了容量弹性。然而，在现实中，需要更加细粒度的容量伸缩
来处理小规模的容量溢出和在一些元素被删除时及时的空间回收。而且，现有的数据结构
被设计可伸缩性限制。在布隆过滤器器得框架中，为了目标假阳性比率，参数需要细致的设
置。同时，布隆过滤器的现有协议必须使用固定数量的哈希函数和2的幂次方桶数。现有数
据结构在实现上述三条准则不足的共同原因是它们都维持了元素的格或桶的索引与过滤
器长度之间紧密的依赖。结果它们的容量不管动态集合的变化，必须是预置的和不可修改
的。

发明内容

[0005] 本发明的目的在于提供索引独立布谷过滤器、一致性布谷过滤器及操作方法，以解决现有方法无法同时实现用于动态集合表示的概率型数据结构的三条准则的现有技术
问题。

[0006] 为解决上述问题，本发明提供了一种索引独立布谷过滤器，包括多个桶，每个桶有b个槽位，多个桶被映射到一个范围从1到M‑1的一致性哈希环中，其中M是一致性哈希环的
取值范围。

[0007] 优选地，每个桶可存储0‑b个指纹，且为每个元素x提供k≥1个候选桶，为了确定元素x的候选桶，k个相互独立的哈希函数被用于将元素指纹ηx映射到一致性哈希环中，k个哈
希函数的k个最近的桶被认为是元素指纹ηx的候选桶。

[0008] 本发明还提供了一致性布谷过滤器，包括上述任意所述的s个异构的索引独立布谷过滤器，任意索引独立布谷过滤器有mi≥1个桶，每个桶有bi≥1个槽位，其中，s≥1，初始
为1，i∈[0,s‑1]。

[0009] 依托于上述一致性布谷过滤器，本发明还提供了一致性布谷过滤器的操作方法，操作方式包括元素插入，元素查询和元素删除。

[0010] 优选地，一致性布谷过滤器追踪每个索引独立布谷过滤器中插入的元素数量，并将插入最后一个元素的索引独立布谷过滤器标记为活跃索引独立布谷过滤器，元素插入的
操作方式如下：

[0011] 索引独立布谷过滤器将元素x映射到整数区间[0,2f‑1]中来生成元素指纹ηx，其中f为元素指纹长度；

[0012] 相互独立的k个哈希函数将元素指纹ηx映射到一致性哈希环中，基于生成的哈希值，一致性哈希决定元素指纹ηx在活跃索引独立布谷过滤器中的候选桶；

[0013] 将元素指纹ηx按布谷哈希中的策略插入到活跃的索引独立布谷过滤器中，如果活跃索引独立布谷过滤器成功存储元素指纹ηx，那么插入结束；否则，一致性布谷过滤器会进
行扩容操作或者扩展操作，扩容操作或者扩展操作后，将元素指纹ηx插入到扩展的或者扩
展的索引独立布谷过滤器中。

[0014] 优选地，元素查询的操作方式如下：

[0015] 通过相互独立的k个哈希函数对元素指纹ηx哈希来决定元素指纹ηx在一致性哈希环中的位置；

[0016] 基于哈希值，一致性哈希得出对于元素指纹ηx在索引独立布谷过滤器中候选桶的位置：如果任一候选桶持有元素指纹ηx，成员关系查询终止，返回存在；相反，如果在所有的
索引独立布谷过滤器中，都没有找到元素指纹ηx，一致性布谷过滤器判定元素x不属于集合
A，返回不存在。

[0017] 优选地，元素x的删除需要首先进行成员关系查询来找出元素的可能位置，元素删除的操作方式如下：

[0018] 如果对应的元素指纹ηx在一致性布谷过滤器中未找到，删除操作返回失败；如果对应的元素指纹ηx在一致性布谷过滤器中被找到则直接执行删除。

[0019] 优选地，所述操作方式还包括对一致性布谷过滤器的容量进行调整，调整方式包括扩容、缩容、扩展和压缩。

[0020] 优选地，扩容是指向索引独立布谷过滤器中增加桶，缩容是指通过从指定索引独立布谷过滤器中移除桶；

[0021] 扩容时，在其后继中存储的元素指纹ηx会受到影响：新的桶Bnew被映射到Bi和Bj(i,j∈[0,m‑1])之间，Bj是Bnew的后继。在这种情况下，仅在Bj中存储的元素可能需要被重新放
置到Bnew中，即如果在Bj中的元素指纹ηx被映射到Bi和Bnew之间，则它应该被移动到Bnew中；否
则，应该继续留在Bi中；

[0022] 缩容时，当某个桶从索引独立布谷过滤器中移除时，仅在此桶中的元素需要被重放置到一致性布谷过滤器中：若一致性哈希中的桶Bi和Bj，Bj是Bi的后继，一致性布谷过滤
器优先尝试将桶Bi中的元素指纹ηx推到桶Bj中，然后将剩余元素重放置到其余桶中，如果Bi
中的元素指纹ηx被全部成功存储，Bi可以被移除，否则，Bi不能被移除。

[0023] 优选地，扩展是指向一致性布谷过滤器中增加未使用的索引独立布谷过滤器，压缩是指压缩稀疏索引独立布谷过滤器；

[0024] 当要表示的元素数量急剧增加时，一致性布谷过滤器的容量可以通过向一致性布谷过滤器中增加单个或多个未使用的索引独立布谷过滤器立即增加，增加的索引独立布谷
过滤器可以是异构的，桶和槽的数量是可以调整的；

[0025] 当索引独立布谷过滤器因为集合元素的移除而变得稀疏时，一致性布谷过滤器尝试通过压缩操作将该索引独立布谷过滤器移除：

[0026] 一致性布谷过滤器首先选取最低利用率的索引独立布谷过滤器向量并移除；

[0027] 将被移除的索引独立布谷过滤器中的元素指纹ηx重新插入到一致性布谷过滤器中，如果被移除的索引独立布谷过滤器中的元素指纹ηx可以被成功插入到一致性布谷过滤
器，选择的被移除的索引独立布谷过滤器可以安全移除，否则，一致性布谷过滤器早已足够
简练，不需要进一步压缩，压缩持续移除索引独立布谷过滤器直到存在被移除的索引独立
布谷过滤器不能被安全移除。

[0028] 优选地，容量调整的触发条件是：通过元素的到达速率α和元素移除速率β共同决定是否需要调整一致性布谷过滤器容量，当α＞β时，进行扩容或者扩展；当α<β时，进行缩容
和压缩；

[0029] 通过元素的到达速率α和一致性布谷过滤器假阳性比率上界 共同决定扩容或者扩展：

[0030] 当 时，是阈值，一致性布谷过滤器可以在小规模单体扩容操作下插入抵达元素，小规模单体为在每次扩展中只增加单个桶；当 时，在增加新的索引独立布谷过
滤器之后总体的假阳性比率才不会超过 扩展操作才被触发。否则，一致性布谷过滤器仅
使用桶级别的单体扩容操作；

[0031] 对称的，缩容和压缩的条件与扩容和扩展一致。

[0032] 本发明包括以下的有益效果：

[0033] 本发明提出了索引独立布谷过滤器，其概率型数据结构可以将存储元素信息的桶或格的索引与过滤器长度解耦。在不需要重放置大多数元素的情况下，允许存储空间的伸
缩性变化。本发明还组合多个索引独立布谷过滤器作为一致性布谷过滤器，并且提出动态
集合表示和容量调整的算法，并且实现了设计的三条准则。

附图说明

[0034] 图1为本发明优选实施例索引独立布谷过滤器运行过程示意图；

[0035] 图2为本发明优选实施例所述索引独立布谷过滤器的随机二分图；

[0036] 图3为本发明优选实施例插入指纹数量与容量关系图；

[0037] 图4为本发明优选实施例参数对一致性布谷过滤器的影响对比图；

[0038] 图5为本发明优选实施例参数对CCFB的影响对比图；

[0039] 图6为本发明优选实施例参数对CCFF的影响对比图。

具体实施方式

[0040] 本发明中CCF指的是一致性布谷过滤器，I2CF指的是索引独立布谷过滤器，是CCF的基本组成单元。

[0041] 布谷哈希表：

[0042] 哈希表支持常数时间的查询，但是会导致仅仅接近50％的空间占有率。通过整合“两个随机选择的力量”到哈希表中，布谷哈希表在保证常数查询时间同时实现较高的空间
利用率。总的来说，布谷哈希表是有m个桶的数组。每个桶存储一个元素。为了插入元素x，两
个独立的哈希函数h1和h2用于为元素x选择候选桶。如果桶h1(x)％m或者h2(x)％m是空的，
元素会存储在其中之一。相反，如果两个桶均被占用，布谷哈希表会随机选取一个，提出已
存元素来安置x。被踢出的受害者会被分派到它的其它候选桶中。布谷哈希表会持续踢出并
重新安置已存元素直到受害者成功安置或者踢出的迭代此处超过预设的最大值。当元素插
入失败时，布谷哈希表被认为已满。为了查询或者访问元素，用户只需要检查元素的两个候
选桶。重新放置使得布谷哈希表优化了先前存入元素的放置，因此保证了较高的空间利用
率。在实际实现中，每个桶推荐存储多个元素，并且哈希函数的个数也可以有选择性而不是
固定值。

[0043] 一致性哈希：

[0044] 对于哈希表一个内在的缺点是调整大小需要对所有元素重新哈希。原因在于元素的位置是哈希值与表长度的余数。一致性哈希缓解了这种情况,在前提为单桶可存储多个
元素的条件下，调整哈希表时，只有一部分已存元素需要被移动。一致性哈希将元素和桶映
射到从0到M的环中。之后，元素被顺时针或者逆时针分派到环中。当一个新的增加环中时，
仅在其后继桶中的部分元素需要被移动。类似地，在桶被移除出哈希表时，该桶中的元素只
需被推到其后继桶中即可。假设哈希表中桶的数量是m，元素数量是n，平均每次更新影响的
元素只有n/m。一致性哈希已经被广泛应用与分布式系统，本实施例中使用一致性哈希来将
指纹分派到CCF桶中，同时可以随意愿单体扩容和单体缩容。

[0045] 布谷过滤器：

[0046] 布谷过滤器(CF)是基于布谷哈希表的轻量型概率数据结构，支持常数时间的成员关系查询。布谷过滤器将布谷哈希表中的实际元素内容替换为元素指纹。结构上，CF包含m
个可以存储b个指纹的桶，集合中元素x与由哈希函数h0生成的f比特指纹ηx相关联。对于CF
显而易见的问题是在不需要元素原始信息时得出被踢出元素候选桶。CF应用partial‑key
布谷哈希策略来处理这个问题。候选桶可以通过对当前桶的索引和被踢出元素指纹的哈希
值进行异或操作得到。

[0047] 元素x的两个候选桶通过h1(x)＝hash(x)和 得到。

[0048] 有了上述的设计，在插入元素x时，CF首先计算x的指纹，然后利用预先指定好的哈希函数h1和h2生成两个候选位置。之后指纹ηx会被存储到这两个候选位置之一，如果有必要
的话还会对提出的受害者元素重放置。为了查询元素y是否是集合A的成员，CF检查y对应的
候选桶。如果指纹ηy存在其中之一，CF判定y∈A；否则CF判定 由于指纹潜在的哈希碰
撞问题，CF可能会有假阳性错误(将本不属于集合的元素误认为是集合成员)。理论上，CF的
假阳性错误有上界 f是指纹的比特位数，b是每个桶中槽的数目。如
果集合A中所有元素均成功插入，对于CF来说没有假阴性的错误。

[0049] 最近，CF的几个变种也被提出进一步提高性能。实验性的结果验证了CF的性能，但是并没有被理论证明。简化版布谷过滤器(SCF)计算元素x的桶的位置h1(x)和
简化的影响可以通过指纹边缘图来可视化，其顶点是散列表的桶，并且其边
缘连接指纹的可能成对位置。基于图论，SCF提供了理论上的性能分析。自适应布谷过滤器
(ACF)尝试通过重新设置发生碰撞的指纹来从CF向量中移除假阳性错误。ACF包括一个CF和
相应的布谷哈希表。这样的设计确保ACF识别假阳性错误，将桶索引与指纹解耦。当一个假
阳性错误发生，ACF为冲突元素生成新的指纹，这个指纹可直接从哈希表中直接获取。结果，
假阳性错误之后不会再次发生。

[0050] 受动态布隆过滤器启发，动态布谷过滤器(DCF)动态的维持多个同构CF使得容量弹性改变。最开始，仅有一个CF保持活跃，随后的同构的CF将以主动或被动方式引入。一个
回收机制被建议合并两个低负载的CF，从而提高空间使用。DCF的假阳性比率上界为1‑(1‑
S
fCF) ，fCF是每个CF向量的假阳性比率，s是DCF中保持的CF数目。

[0051] 然而，以上CF的变种都不能正确实现我们的设计准则。SCF和ACF仅利用了哈希函数的优势，不能在部署后不能实现容量调整。DCF支持过滤器级别的容量改变但导致有限的
设计可伸缩性和不合时宜的空间回收。总之，我们提出了CCF，一种新颖的概率型数据结构
能够同时确保容量弹性、高的空间使用和设计可伸缩性。

[0052] 实施例1：

[0053] 为了表示动态集合，所用的数据结构应该提供弹性容量。尽管DBF和DCF能够提供在过滤器级别的容量调整，但不能提供更细粒度的容量改变。原因在于过滤器的长度是预
先设定的，在整个生命周期中不可改变。计算哈希值的异或操作通过限制过滤器的长度为2
的幂次方，更加恶化了容量的可伸缩性。因此，我们重新设计了布谷过滤器的框架，在这里
提出了I2CF。

[0054] 本发明提供了一种索引独立布谷过滤器，参见图1(a)，包括多个桶，每个桶有b个槽位，多个桶被映射到一个范围从1到M‑1的一致性哈希环中，其中M是一致性哈希环的取值
范围。为了在一致性哈希环中确保负载均衡，每个桶有v≥1虚拟节点，I2CF同样存储元素的
指纹而不是元素的实际内容，为每个元素提供k≥1个候选桶。如果元素的指纹被存储在候
选桶之一，那么这个元素就被成功表示。为了确定元素x的候选桶，k个相互独立的哈希函数
被用于将元素指纹ηx映射到一致性哈希环中。之后关于k个哈希函数的k个最近的桶(默认
顺时针)被认为是ηx的候选桶。用这种方式，候选桶是索引独立的并且有一致性哈希决定。
指纹可以存在这些候选桶的任意一个。如果所有的候选桶已被占用，I2CF随机踢出这些候
选桶之一的已存入指纹来插入新指纹，被踢出的受害者会被重新放置在它的一个候选桶
中。重新放置过程在桶中有空余位置时成功结束，在重放置次数达到给定阈值时失败结束。

[0055] 相比于布隆过滤器，I2CF有两个主要的改进。首先，I2CF将桶组织成一个一致性哈希环来解耦候选桶和过滤器长度之间的依赖。结果，I2CF自然能够根据需求来增加和移除
桶。一个I2CF简单的示例在图1中给出。第二，I2CF将布谷过滤器中固定的2个桶一般化为可
变变量k。通过后面的分析，k值越大空间利用越高，I2CF实现了桶级别的容量弹性和更高的
空间利用来表示动态集合。

[0056] 本发明还提供了一种一致性布谷过滤器，包括上述任意所述的s个异构的索引独立布谷过滤器，任意索引独立布谷过滤器有mi≥1个桶，每个桶有bi≥1个槽位，其中，s≥1，
初始为1，i∈[0,s‑1]。

[0057] I2CF提供桶级别的容量弹性，但是当集合基数动态变化的时候，单一的I2CF可能不能及时的提供足够的空间。因此，我们进一步扩展得到CCF通过动态地维持多个I2CF。就
像已有的CF变种，CCF同样利用指纹来表示集合中的元素。对于元素x的指纹可利用哈希函
f
数h0将x映射到[0,2‑1]得到。CCF包括s(s≥1，初始为1)个异构的I2CF。任意I2CFi(i∈[0,
s‑1])有mi≥1个桶，每个桶有bi≥1个槽位。所用的哈希函数ki和I2CFi中Mi的值同样允许与
其他I2CF中不同。这样的框架，CCF能实现最大的设计可伸缩性。注意到为了复用在I2CF之
间为指纹计算的哈希值，我们默认选择k0＝…＝ki＝…＝ks‑1＝k，并且M0＝…＝Mi＝…＝
Ms‑1＝M。更重要的是，CCF提供桶级别和过滤器级别的容量弹性。可以通过在I2CF中增加或
者移除桶，同样也可以引入未使用的I2CF或合并低使用率的I2CF。当一个I2CF被扩大或者
引入时，它会被标记为活跃状态来存储新元素。

[0058] 对于在CCF中的一个I2CFi(i∈[0,s‑1])，让bi代表每个桶中的槽位，ki代表在I2CFi中候选桶的个数。对于CCF查询的假阳性概率可被计算为：

[0059]

[0060] 当k0＝…＝ki＝…＝ks‑1＝k，并且b0＝…＝bi＝…＝bs‑1＝b时，

[0061]

[0062] CCF的假阳性错误源于指纹的哈希碰撞。如果两个元素x∈A， 有相同的指纹，即ηx＝ηy，对y的成员关系查询会由于x的存在隐含假阳性错误。在CCF框架中，成员关系查询
会查询所有的s个I2CF向量。对于I2CFi，假阳性比率是 总体的假阳性比率
得出为 注意到，DCF和CCF都有多个过滤器，有同样的假阳性比率。
一般地，f越大，会有越低的假阳性比率，更大的k，b，s导致更高的假阳性比率。然而，DCF不
能支持运行时假阳性比率，因为s会随着集合基数的增加而持续增加。结果，当更多的CF增
加时，DCF的假阳性比率会一直增加。相反，CCF通过为s设定阈值支持运行时假阳性比率保
证。如果s达到了阈值。一方面，CCF可以执行压缩操作来合并一些I2CF。另一方面，CCF仅使
用桶级别的容量变化来容纳新元素，因此s的值不会增加。这样假阳性比率会被合理的限
制。

[0063] 本发明还提供了一致性布谷过滤器的操作方法，操作方式包括元素插入，元素查询和元素删除。

[0064] 元素插入：

[0065] 算法1：在CCF插入元素指纹ηx；

[0066] 输入：需插入的元素指纹ηx；

[0067]

[0068] CCF追踪每个I2CF中插入的元素数量，之后将表示最后一个元素的I2CF标记为活f
跃I2CF。为了插入元素x，CCF首先将x映射到[0,2 ‑1]中来生成元素指纹。之后相互独立的k
个哈希函数将元素指纹ηx映射到一致性哈希环中。基于生成的哈希值，一致性哈希决定ηx的
在活跃I2CF中的候选桶。之后，尝试将ηx按布谷哈希中的策略插入到活跃I2CF中。如果活跃
I2CF成功存储指纹ηx，那么插入算法终止。否则，CCF容量会在桶级别或者过滤器级别扩展。
之后，ηx会被插入到扩展的或者增加的I2CF中。算法1中展示了伪代码。注意到，当扩展时，
CCF标记被操作的I2CF为活跃状态，因此待插入的数会被插入到这个I2CF向量。建议选择具
有最少桶的I2CF，以便在执行桶级别扩展时实现更好的平衡。有时，为了成功放置ηx，需要
增加多个桶。如果在插入x之后还有多个元素需要插入，CCF在假阳性比率限制下将会引入
新的I2CF向量，这样新的元素可以立即被插入。

[0069] 元素查询：

[0070] 算法2：在CCF查询元素x；

[0071] 输入：需查询的元素x；

[0072]

[0073] CCF的成员关系查询可能检查每个I2CF向量。在CCF中，s表示I2CF向量的数量。我们在最坏的情况下需要检查s·k桶。算法2表示了成员检测算法细节。通过相互独立的k个
哈希函数对元素指纹ηx哈希来决定元素指纹ηx在哈希环I2CFi(i∈[0,s‑1])中的位置。基于
哈希值，一致性哈希得出对于元素指纹ηx在I2CFi中候选桶的位置。如果任一候选桶持有元
素指纹ηx，成员关系查询终止，返回存在。相反，如果在所有的I2CF中，都没有找到元素指纹
ηx，CCF判定 返回不存在。对于查询的元素可能存在一定的假阳性错误，但是对于存储
元素不存在假阴性错误。

[0074] 元素删除：

[0075] 算法3：在CCF删除元素指x；

[0076] 输入：需删除的元素x；

[0077]

[0078]

[0079] 元素x的删除需要首先进行成员关系查询来找出元素的可能位置。如果对应的指纹ηx在CCF中未找到，删除操作返回失败。当一定数量的元素已经被从CCF中删除，容量调整
操作会被执行与降低CCF容量，保持较高的空间使用率。CCF偏向于选择过滤器级别的容量
调整，因为小的s可以保证较低的假阳性比率。

[0080] 对于动态集合表示本质上的挑战在于集合基数n的不可预测性。这一挑战对所采用的数据结构提出了新的要求。而且，集合基数n可能无规律变化，例如：n可能渐进的或者
急剧的增加或者减少。为了处理这个问题，数据结构必须在不同粒度上进行容量调整。因
此，本实施例提出了两个选择来扩展CCF的容量，即：纵向上向I2CF中增加桶，横向上向CCF
中增加未使用的I2CF。对称的，CCF的容量可以被缩小，通过从指定I2CF中移除桶，或者压缩
稀疏I2CF。单体扩容和单体缩容能进行桶级别的容量调整，同时，向外扩展和压缩实现过滤
器级别的容量调整。这些方法保证了CCF在表示动态集合时有很好的容量弹性。

[0081] 单体扩容：当新的桶被加入I2CF中时，仅在其后继中存储的元素指纹会受到影响。考虑新的桶Bnew被映射到Bi和Bj(i,j∈[0,m‑1])之间，Bj是Bnew的后继。在这种情况下，仅在
Bj中存储的元素可能需要被重新放置到Bnew中。具体地，如果在Bj中的指纹被映射到Bi和Bnew
之间，它应该被移动到Bnew中；否则，应该继续留在Bi中。极端情况下，Bj是空的，那么Bnew也应
该是空的。图1(b)中所示的为简单的扩容。

[0082] 单体缩容：相应地，CCF可以为了实现更高的空间利用率将桶从I2CF中移除。当某个桶从I2CF中移除时，仅在此桶中的元素需要被重放置到CCF中。考虑在一致性哈希中的桶
Bi和Bj，Bj是Bi的后继。CCF优先尝试将桶Bi中的指纹推到桶Bj中，然后将剩余元素重放置到
其余桶中。如果Bi中的指纹被全部成功存储，Bi可以被移除。否则，Bi不能被移除。图1(c)所
示为简单的缩容。当CCF单体缩容时，为了省时优先移除空的和低使用率的桶。

[0083] 向外扩展：另一个增加CCF容量的方法是增加未使用的I2CF。初始时，CCF维护单一I2CF，根据需求在单一过滤器上单体扩容和单体缩容。当要表示的元素数量急剧增加时，
CCF的容量可以通过向CCF中增加单个或多个未使用的I2CF立即增加。增加的I2CF可以是异
构的，因为它们是完全独立的。桶和槽的数量是可以调整的。

[0084] 压缩：当I2CF因为集合元素的移除而变得稀疏时，CCF尝试通过压缩操作将该I2CF移除。算法4中展示，CCF首先选取最低利用率的I2CFL向量并移除，更新后的CCF为CCFT。之
后，我们尝试将I2CFL中的指纹重新插入到CCFT中。如果I2CFL中的指纹可以被成功插入到
CCF，选择的I2CFL可以安全移除。否则，CCF早已足够简练，不需要进一步压缩。压缩算法持
续移除I2CF直到存在I2CF不能被安全移除。

[0085] 算法4：CCF容量压缩

[0086] 输入：待压缩的CCF；

[0087]

[0088] CCF在桶级别和过滤器级别提供容量弹性。CCF主要给用户提供了三个函数，即：元素插入、查询、删除，只有增加和删除才会触发容量调整过程。

[0089] 我们依靠元素的到达速率(α表示单位时间内元素到达的数量)和CCF假阳性比率上界 共同决定单体扩容和向外扩展的使用。仅当 时( 是阈值)，CCF可以在小规模
单体扩容操作下插入抵达元素(在每次扩张中只增加单个桶)。保守地使用向外扩展，因为
增加I2CF会导致更高的总体假阳性比率。仅当 时，ξCCF在增加新的I2CF之后总体的假
阳性比率才不会超过 向外扩展操作才有可能被触发。否则，CCF仅使用桶级别的单体扩容
操作。特殊情况下，当 时，但是现有I2CF在 限制下不允许插入更多的元素，CCF需要对
I2CF进行大规模单体扩容操作(每次扩张增加多个桶)。在每次单体扩容过程中需要增加的
桶数与到达速率α城比例。

[0090] 与大规模单体扩容操作相比，向外扩展操作能够及时扩展CCF，单体扩容为了增加桶的数量导致更多的时间复杂性。因此，在 的限制下，CCF更倾向于向外扩展而不是单体大
规模扩容操作。

[0091] 对称地，为了降低容量，CCF提供单体缩容操作从I2CF中移除桶和压缩操作来移除稀疏I2CF。当一个桶因为元素删除操作变空，它将被缩容操作移除出I2CF。压缩操作仅在
I2CF中存储的指纹低于阈值时才会触发。为此，CCF为每个I2CF增加了计数器来追踪存储指
纹的数量。

[0092] 在实际中，在线系统频繁地插入和删除元素，因此重复的调整CCF容量大小是不必要的。特别地，当元素到达速率接近移除速率(β表示单元时间内元素移除的数量)，需要的
容量是稳定的。在这种情况下，除非插入操作失败或者存在I2CF使用率极低，其余并不需要
立即调整CCF容量。因此，在更高的层次，我们建议使用α和β共同决定CCF容量调整策略。当α
＞β时，单体扩容和向外扩展操作需要来扩展CCF；当α<β时，进行单体缩容和压缩操作。

[0093] 表1

[0094]名称 BF DBF CF DCF ACF SCF I2CF CCF
容量弹性   ++   ++     ++ +++
空间效率 + + ++ ++ ++ ++ +++ +++
设计伸缩性 ++ ++ + + + + +++ +++

[0095] 如表1中所示，布隆过滤器和DBF有低的空间使用率。原因是为了最小的假阳性比率，保持一半的比特位为0。相反，布谷过滤器和它的变种通过在每次插入中的重放置策略
提高了空间利用率。DBF和DCF通过动态增加和合并过滤器在一定程度上提供了容量弹性。
然而，在现实中，需要更加细粒度的容量伸缩来处理小规模的容量溢出和在一些元素被删
除时及时的空间回收。而且，现有的数据结构被设计可伸缩性限制。在布隆过滤器器得框架
中，为了目标假阳性比率，参数需要细致的设置。同时，布隆过滤器的现有协议必须使用固
定数量的哈希函数和2的幂次方桶数(表中+越多表示越适应该准则)。

[0096] 实施例2：

[0097] CCF时间复杂度：

[0098] 考虑有s个I2CF的CCF，k0＝…＝ki＝…＝ks‑1＝k，b0＝…＝bi＝…＝bs‑1＝b时。让max表示允许重放置次数，m表示I2CF的长度。I2CF可能有不同的长度，为了简化，我们统一
设为m。CCF元素插入、查询、删除的时间复杂度分别是O(max·logm),O(s·k·b·logm),O
(s·k·b·logm)。

[0099] CCF引入一致性哈希来实现容量弹性。因此查询和删除的时间复杂度不再是常数级别。当我们需要知道元素候选桶的索引时，CCF需要参考底层的一致性哈希环。在实现中，
这些桶的哈希值被组织成形成二叉搜索树。给定元素的一个哈希值，相应的候选桶的位置
会在O(logm)时间内找到。为了将元素插入活跃I2CF中，最多max次重放置被允许，所以时间
复杂度为O(max·logm)。对于查询和删除操作，CCF最坏情况下需要遍历所有的I2CF，因此
时间复杂度为O(s·k·b·logm)。

[0100] 与DCF相比，CCF的时间复杂度由于额外的乘数logm要稍微高一些。对数级别的复杂度，由于随着m的急剧增加对数值增加缓慢，在实际应用中可以接受。应用一致性哈希的
分布式系统都会导致对数级别的复杂度。

[0101] CCF插入时的阈值：

[0102] CCF中的每个I2CF都可以动态的增加和删除桶来实现容量调整。对于给定参数的静态的I2CF，我们需要探讨有多少指纹可以被成功插入。给定需要被表示的指纹数量ni，一
个衍生的问题是寻找ni与mi之间的阈值Ti。当 I2CFi有1‑o(1)的概率成功插入ni元
素。否则I2CFi可能有1‑o(1)的概率失败插入ni元素。

[0103] 元素和桶之间的映射关系可以被抽象为ki阶超图，有mi节点，ni条超边，每一个超图的边独立的从mi个节点中选取固定大小的ki个节点连接。基于超图的核心理论，Ti可以认
为是ki和bi的函数。实际上，超图可能不是ki阶的因为ki个独立的哈希函数可能为元素x在
I2CFi中选择相同的索引桶。我们称这个现象为映射碰撞。映射碰撞破坏了超图的ki阶假设。

[0104] I2CFi的槽位可以很自然地表示为随机二分图G(V＝(η,S),E)，η表示要存储的指纹，S表示I2CFi中的槽位。图2中所示，每个槽位有两个下标，代表它的宿主桶号和在该桶中
的位置。例如S01表示第一个桶的第二个位置。在二分图中，边代表了指纹和槽位之间的指
派。如果桶是某个指纹的候选桶，该桶所有的槽位都会与该指纹有边的关系，来明确表示该
指纹可以被存入该桶的槽位中。在生成的二分图中，匹配意味着存储指纹的可能路径。这种
抽象自然提供给我们二分图中很重要的性质，即：Hall定理。

[0105] Hall定理：G(V＝(η,S),E)是集合X和集合Y的二分图。对于节点集合 NG(W)表示在G中W的邻居节点，即：Y中所有节点与W中的一些元素邻接。当且仅当对于X的每个子
集W，存在完全覆盖X的匹配：

[0106] |W|≤|NG(W)|          (3)

[0107] 另外，给定I2CFi的参数为mi，b，ki与待插入元素数量ni，我们有以下观察：

[0108] 1、对于插入随机元素x，Θ(Θ∈[0,ki])是代表x被映射到某个桶的次数。由于相互独立的哈希函数的使用，Θ遵循典型的二项分布。具体地，当Θ＝θ时，可以被计算为：

[0109]

[0110] p0表示元素x被映射到某个桶的概率。因为Θ≥1意味着x被映射到桶中，p0可以由下式得出：

[0111]

[0112] 2、Φ∈[0,ni]是代表映射到某个桶中的所有元素总数。Φ由于插入元素的独立性也服从典型的二项分布。具体地，Φ＝φ时：

[0113]

[0114] 联合考虑上述观察及Hall定理，我们为I2CFi提出了新的阈值 指纹有很高的概率可以被成功存储；相反，当 时，I2CFi有很高的概率不能成功存储一些指纹。

[0115] 如果Φ

[0116]

[0117] 是在Φ

[0118]

[0119] 阈值 可以由 的平均值得出：

[0120]

[0121] 通过上述描述可以通过综合考虑观察1,2和Hall定理证明。直觉上，当 时，意味着对于ni指纹有足够的空间。结果，当 时，I2CFi有很高的概率满足Hall定
理的要求。相反，如果 时， 对于ni指纹没有足够的空间来容纳。在这种情景下，
I2CFi以很高的概率不能满足Hall定理。如图3所示，给定mi＝50和bi＝2， 随着ki增长很
30
快。给定mi和ki，bi的增长也会导致 的增加。表2进一步表示了在mi＝2 ， 随着ki和bi变化
而变化。阈值提供了在实际中使用I2CF和CCF的引导。直觉上，更大的 保证了更高的空间
占用。所以，给定相同的值bi，I2CF在增加ki时有能力实现比DCF更好的空间使用率。

[0122] 表2

[0123]

[0124]

[0125] 成功表示的概率：

[0126] 对于给定I2CFi的 当 小于阈值，ni指纹可以以很高的概率成功存储。然而，他们没有解决衍生问题：对于给定I2CFi，成功存储ni指纹的概率，或者迁就一下，概率的上界
是多少？我们尝试利用一下观察解决这个问题。

[0127] 3、对于给定的ni指纹，在最大匹配图G(V＝(η,S),E)中边的数量意味着可以被成功插入I2CFi中最大数量的指纹。如果最大匹配是完全匹配，那么所有给定的指纹可以被
I2CFi成功存储。

[0128] 在参数为mi,ni,ki的I2CFi中，Ψ表示被成功插入的元素。计算Ψ概率分布的暴力破解方法是通过探索的可能空间，然后计数最大匹配包含数目Ψ＝ψ条边的二分图。然而，
这种方法因为要测试 的可能二分图，有指数增长的计算复杂度。因此，作为替代，我们
基于Hall定理和观察3得出了上界p{Ψ＝ni}(ni∈[1,mi·bi])。

[0129] 在参数为mi,ni,ki的给定I2CFi中，ni(ni∈[1,mi·bi])个待插入的指纹，所有ni指纹成功放置的概率上界：

[0130]

[0131] p{Ω＝j}代表ni个指纹被映射到I2CFi中的j个桶中。计算如下：

[0132]

[0133] Q是向量数组，每个向量有j个正整数，这些正整数之和为ni·ki。在Q中的向量数目表示为F(j,ni,ki)，可以通过输入j,ni,ki得到。Dl是在Q[l]中j个整数的可能组合。因子
计算了所有(ni·ki)依据Q[l]给定的分布映射到所选的k个桶的可能情
况。

[0134] 上述描述可以通过考虑观察3和Hall定理证明。p{Ω＝j}只计数ni个指纹映射到确定的j个桶的可能性，没有考虑ni指纹的子集不满足Hall定理。因此，等式(10)提供了上
界p{Ψ＝ni}，等式(11)可以通过将映射问题视为典型的球和桶的问题得到。

[0135] 当mi＝5,bi＝2,ki＝2,ni＝3时，我们通过计算p{Ψ＝5}举例。根据等式(10)，我们有p{Ψ＝3}≤p{Ψ＝2}+p{Ψ＝3}+p{Ψ＝4}+p{Ψ＝5}。根据等式(11)，p{Ψ＝2}＝
0.03968,p{Ψ＝3}＝0.3456,p{Ψ＝4}＝0.4992,p{Ψ＝5}＝0.1152。因此，p{Ψ＝3}的上
界为0.99968。当计算p{Ψ＝3}时，我们有ki·ni＝6＝1+1+4＝2+1+1＝1+2+3。因此F(j,ni,
ki)＝3，Q＝{[1,1,4],[1,2,3],[2,2,2]},D0＝3因为[1,1,4]有三种可能组合，D1＝6,D2＝
1。结果，

[0136] 通过上述分析，为使用CCF和I2CF的用户提供了参数设定的指南。

[0137] 实施例3：

[0138] 本实施例实现了两个版本的CCF，即只允许桶级别容量变化的CCFB，和只允许过滤10
器级别容量变化的CCFF。M的值设为5×10 ，一致性哈希环的虚拟节点数v设为10。图4(b),
(c),(d)描述了分别描述了CDF中桶的数量，空间利用率，空槽位的数量。

[0139] 通过结合考虑图4(a),(b)，我们可以得到DCF和CCF的容量弹性特征。很明显，CCFB实现了最好的弹性，在元素数量增加或者减少时使容量扩大或者缩小。图4(b)CCFB的曲线
完美的匹配了图4(a)中有mopt的曲线变化。CCFF也能通过动态执行的压缩和向外扩展算法
快速响应mopt的变化。然而DCF不能在mopt下降时及时压缩低使用率的CF。原因在于在低使用
率的CF中的指纹移到其他CF相应的桶中。因此，很难实现成功的压缩操作。相反的是，CCFF
尝试将在低使用率的I2CF中的指纹移到其余I2CF中，借以释放低使用率I2CF中被占用的
桶。CCFB和CCFF都有比DCF更好的容量弹性。

[0140] 而且，CDF的空间效率在图4(c)中描述。对于DCF，所得的空间效率大约有37％低于0.90。然而，对于CCFF和CCFB在最终结果中只用10％低于0.90。DCF最大的空间效率为0.970，
要低于CCFB(1.0)和CCFF(0.999)。为了准确，平均来说，DCF(0.8809)，CCFB(0.9481)，CCFF
(0.9425)。对应的，CDF的空槽位数量在图4(d)中展示。对于CCFF和CCFB在最终结果有93％和
97％低于500个空槽位，然而对于DCF来说只有62％。在最坏的情况下，DCF仍然有3176个空
槽位。超过16％的DCF最终结果中有超过1000个空槽位。原因在于DCF只能压缩可以将已存
入该低使用率CF的指纹移到其它未满的CF中。结果，当n的值减少时，DCF并不能及时回收低
使用率的CF。注意到CCFB要比CCFF有更多的空槽位。原因是在我们的实验中仅合并存储少于
2个指纹的桶。在实验的最后，由于元素的移除，容纳两个指纹的桶数目变多，但是CCFB并不
能立即回收空槽位。

[0141] 从以上的实验，我们得出CCF要比DCF能实现更好的容量弹性和更高的空间利用率。另一方面，设计可伸缩性却不能被很好的量化比较。直观上DCF只增加和合并同构的CF，
但是I2CF和CCF却允许不同的参数设置。这使得CCF要比DCF更适合于动态集合表示。

[0142] CCFB中参数的影响：

[0143] 这里量化了参数对CCFB的影响。特别应四个主要参数，即：候选桶数k，桶中的槽位数b，最大允许踢出次数max，和在一致性哈希环中虚拟节点的数目v。CCFB的参考设置为k＝
2,b＝3,max＝1200,v＝10。

[0144] 如图5(a)所示，当k从2增加到16时，CCF获得了更好的空间使用性能(从0.9481上升到0.9599)。当k＝16时，结果中接近有一半以上空间占用超过0.98。然而，当k＝2时，只有
低于12％的结果可以获得超过0.98的空间使用。对于一个元素，有更多的候选位置意味着
一个桶可以被分配到而更多的元素。结果，某个桶被分配到低于b个元素的的概率降低，从
而会有更高的空间使用。当b从3增加到6时，如图5(b)所示，空间1利用急剧增加。具体的，平
均来说，当b＝3时，空间利用为0.9481；当b＝6时，空间利用为0.9986。这个现象是合理的，
因为b越大，在CCFB中会有更少的桶。在雅虎的数据集中，被存储流的最大数量为7290。所以
max＝1200意味着在插入的重放置过程中，可能覆盖整个过滤器来发现潜在的空槽位。同
样，在过滤器中更少的桶数，某个桶被分配给少于b个元素的概率会变低。因此，结果中的空
间利用升高。

[0145] 当max的值从1200降到700时，在图5(c)中记录了CDF的空间使用率。很明显，更高的max值，CCF能实现更高的空间占有。原因是，更高的max，插入过程会搜素更多的桶，更有
希望来找到空桶来容纳指纹。而且，就像在图5(d)中所示，当一致性哈环中的虚拟节点从10
降到1时，空间使用下降很大(平均来说，从0.9481降到0.9298)。当v＝1时，结果中仅有16％
可以达到0.95的空间使用。相反的，当v＝10时，大约76％的结果可以达到0.95的空间使用。
越多的虚拟节点，一致性哈希在桶之间实现更好的负载均衡。所以，某个桶被分配少于b个
元素的可能性会降低，因此达到较高的空间利用。

[0146] CCFF中参数的影响：

[0147] 在空间利用的角度进一步评估了参数对CCFF的性能影响。考虑的参数包括在每个I2CF中桶的数量m，在桶中槽的数量b，最大踢出次数(重放置次数)max，一致性哈希环中虚
拟节点的个数v。参考的CCFF配置为m＝64,b＝3,max＝20,v＝10。

[0148] 如图6(a)所示，当m从64降到16时，CCFF实现了更好的空间利用。平均来说，从0.912上升到0.931。当m＝16时，大约一半(准确来说48.3％)的结果，空间利用超过0.98，然
而当m＝64时，仅有22.4％的结果可以实现0.98的空间利用。原因在于，m越小在增加和合并
I2CF时更细粒度的容量控制。例如，因为存储5个元素，额外的I2CF被引入时，16桶的I2CF确
实比64桶的I2CF更加节省空间。

[0149] 桶中的槽位数变化时，即b从3变化到6，如图6(b)所示。CCFF会变得多一些空间花费。具体的，平均空间利用从0.912降到0.899。当b＝6时，大约57％的结果，空间利用落在区
间[0.920,0.984]。然而，当b＝3时，大约52％的结果中空间利用超过0.940。这个现象是合
理的，因为固定m增加b意味着，在增加未利用的I2CF时需要更多的空间资源，在合并低使用
率的I2CF时更难。

[0150] 如图6(c)所示，在每次插入中增加最大允许重放置次数，即max从增加到50，空间利用只有微弱的增长(从0.912到0.913)。在理论上分析，让ω代表有m桶的I2CF中有空槽位
的桶数。假设对于踢出的受害者候选桶的选择是随机的。空槽位可以从I2CF中被搜索到的
概率是

[0151] 给定m和ω，这个概率确实随着max的增加而增加，然而是以一种边际的方式。因此，当max足够大时，即使对max增加很大的值，也可能会是特别小的增长。

[0152] 从上述的结果中，CCF的参数对它的性能有不同的影响。用户可以通过利用这些参数的优势来定制数据结构的配置实现自身目标。

[0153] 以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修
改、等同替换、改进等，均应包含在本发明的保护范围之内。