2024-07-30 2024-07-30 4693 字 10 分钟

- 性能优化

#include <iostream>
using namespace std;
int main(){
    cout << "你可以在这里编写，测试代码!" << endl;
    cout << "目前只支持c++,java和python!" << endl;
    cout << "点击右上角切换语言!" << endl;
    return 0;
}

Cuckoo过滤器

Cuckoo过滤器简介

Cuckoo简介

在中国有个成语叫“鸠占鹊巢”，讲述的是一种鸟类的奇特行为。这种鸟就是布谷鸟，也叫杜鹃（古时称鸤鸠）。布谷鸟有个特别的习性，它们不会自己筑巢，而是将自己的蛋偷偷放在其他鸟类的巢里，由这些宿主鸟来孵化。等到布谷鸟的小鸟孵出来后，它们会把巢里的其他蛋全部扔出，让宿主鸟只喂养自己，这样它们可以更快地长大。

布谷鸟过滤器

布谷鸟过滤器（Cuckoo Filter）是一种高效的集合成员检测工具，主要用于判断一个元素是否存在于某个集合中。它的工作原理类似于布隆过滤器（Bloom Filter），但在查询效率、空间利用率上更具优势，并且还能支持元素的删除。

布谷鸟过滤器是一种节省内存的概率性数据结构。它的查询结果有两种：一种是“元素一定不存在”，另一种是“有较大可能存在”。需要注意的是，当查询结果显示元素可能存在时，实际上可能因为哈希碰撞而导致误判。（下文详细简介）

名字的由来

布谷鸟过滤器之所以得名，是因为它的插入过程有点像布谷鸟的行为。如果在插入元素时发生哈希碰撞，布谷鸟过滤器会把原有的元素“踢出”位置，这种行为就像布谷鸟雏鸟把寄主鸟蛋推开一样。因此，这种过滤器被形象地称为布谷鸟过滤器。

Cuckoo过滤器有什么用

布谷鸟过滤器（Cuckoo Filter）在实际应用中有很多有效的场景。以下是几个典型的例子：

数据库查询优化：布谷鸟过滤器能够显著降低数据库的负载。在执行数据库查询之前，可以通过布谷鸟过滤器先进行检测，以确定数据是否存在于数据库中。如果过滤器表明数据不存在，就可以避免不必要的数据库访问，从而提高查询效率。
解决缓存穿透问题：在Redis中，布谷鸟过滤器可以有效地应对缓存穿透问题，防止恶意攻击。通过将布谷鸟过滤器作为缓存层的一部分，可以过滤掉那些不在缓存中的请求，减少对后端数据库的直接压力。
内存效率优化：在Redis处理大规模数据集合时，传统的数据结构如哈希表会消耗大量内存。布谷鸟过滤器可以用更少的内存实现类似的功能，从而提升内存使用效率。
RedisBloom模块：Redis的RedisBloom模块实现了布谷鸟过滤器，作为其数据结构之一，用于高效管理大规模数据集合。通过布谷鸟过滤器，RedisBloom能够提供快速的查询和更新操作，提升系统的性能和响应速度。

Cuckoo过滤器的原理

布谷鸟过滤器的作用是查询一个数据是否在一个集合之中，显然首先需要将集合中元素的指纹"存储“到布谷鸟过滤器之中，然后用户通过查询布谷鸟过滤器去判断该数据是否在集合之中，当集合变小时，我们可以删除布谷鸟过滤器中的相应指纹。综上可以知道，布谷鸟过滤器需要包含三个算法"Insert”、“Lookup”、“Delete”，下面分别介绍这几个算法。

预备知识

指纹：

首先介绍密码学中的哈希函数。为了防止与下面介绍的哈希表中的哈希函数重复，我们称密码学中的哈希函数为"散列函数"。散列函数是一种数学函数，它能够将任意长度的输入转换为固定长度的字符串。散列函数具有单向性，即从散列值反推原始输入是不可行的，但可以通过简单计算得到输入的散列值。

利用散列函数，我们可以生成文件的“指纹”。例如：对于一个文件 x，首先计算其散列值 hash = H(x)，其中 H(·) 表示散列函数。然后，从 hash 中提取若干位（例如前8位），作为文件 x 的指纹。为了便于描述，我们定义一个“指纹函数” fingerprint(x)，它的作用是计算文件 x 的指纹，即 fp = fingerprint(x) 是 x 的指纹。

哈希函数：

哈希函数是将文件映射到哈希表中相应存储位置的函数。哈希表是一种高效的数据结构，其查询操作的时间复杂度为O(1)。这种高效性得益于哈希函数的作用。常见的哈希函数包括“平方取中法”、“除留取余法”和“随机数法”等。

在布谷鸟过滤器中，需要计算一个数据的两个索引，故需要使用两个哈希函数 $h_1(x)$ 和 $h_2(x)$。首先，我们定义一个好的哈希函数 $H(\cdot)$。基于这个哈希函数，我们可以定义这两个哈希函数为：$h_1(x) = H(x)$ 和 $h_2(x) = h_1(x) \oplus H(\text{fingerprint}(x))$。其中，$H(\cdot)$ 是我们所定义的哈希函数，而 $\text{fingerprint}(x)$ 是数据 $x$ 的指纹。

可以看出，两个哈希函数 $h_1(x)$ 和 $h_2(x)$ 是对称的，他们两个具有相同的地位，若已知其中任意一个，比如已知 $h_2(x)$ ，可以计算另一个 $h_1(x) = h_2(x) \oplus H(\text{fingerprint}(x))$。这两个哈希函数的巧妙设计在插入时有大用。

哈希表

首先，我们来简单介绍布谷鸟过滤器（Cuckoo Filter）使用的数据结构。布谷鸟过滤器的核心数据结构是哈希表，这个哈希表由多个哈希桶组成。每个哈希桶对应一个唯一的索引，并且每个哈希桶内包含 $2^n$ 个槽位。初始化时，所有哈希桶的所有槽位的值都设为 0，表示这些槽位当前未存储任何数据。下图展示了一个示例，其中 $n=2$ 并且哈希表由 16 个哈希桶组成：

如图所示，该哈希表共有 16 个索引(哈希桶)，每个索引对应 4 个槽位（因此被称为四路哈希桶）。当前每个槽位的值都为 0，表示这个哈希表尚未存储任何信息。

当我们需要将数据存储到布谷鸟过滤器中时，并不会直接存储整个数据，而是将数据的指纹存储到布谷鸟过滤器中，以节省存储空间。具体的存储和操作方法将在下文中详细介绍。

Insert 算法

布谷鸟过滤器的索引计算需要用到哈希函数 $H(\cdot)$ 和指纹函数 fingerprint(·)。假设我们想要将数据 x 添加到布谷鸟过滤器中，我们按照以下步骤执行添加操作：

计算指纹和索引：首先我们计算 x 的指纹 fp = fingerprint(x)，然后分别使用两个哈希函数计算数据在哈希表中的两个索引 $h_1 = h_1(x)$ 和 $h_2 = h_2(x)$ .
检查空闲槽位：检查哈希表中这两个索引 $h_1$ 和 $h_2$ 对应的哈希桶是否有空闲槽位。如果找到空闲槽位，则将指纹 $fp$ 存储到这个槽位中。
处理满槽位：如果两个哈希桶中的所有槽位都已满，则需要进行挤兑操作。随机选择一个满槽位，将其中的元素（假设为 magpie,实际是一个指纹）踢出，并将指纹 $fp$ 存储到该槽位上。假设该槽位的索引为 $h_{old}$，计算 magpie 的新索引 $h_{new}=h_{old}\oplus H(magpie)$，如果 $h_{new}$处有空闲的槽位，则将 magpie 存储到该槽位上。如果 $h_{new}$ 处也没有空闲槽位，则重复上述挤兑过程，直到找到合适的位置。
循环挤兑和扩容：在挤兑过程中，可能会出现循环挤兑的情况，即被踢出的元素计算新的索引后又需要继续挤兑其他元素。为了避免无限循环，我们设定一个阈值，如果循环挤兑的次数超过该阈值，就会触发扩容操作。扩容涉及到增大哈希表的大小，并重新计算数据在新哈希表中的索引位置，虽然这一过程较为耗时，但可以有效解决循环挤兑问题。

以下是插入数据到布谷鸟过滤器的过程示例：

对上述插入过程的简单描述如下：

首先，使用哈希函数计算数据 $x$ 的两个位置索引 $2 = h_1(x)$ 和 $6 = h_2(x)$。然后随机选择一个位置存放数据 $x$（在这里选择了索引 6）。
由于两个索引位置都已经满了，因此我们将随机选择一个位置存放数据指纹 $x$，并将该位置原有的指纹（在这里是指纹 a）踢出。
被踢出的指纹 a 需要重新计算它的另一个位置索引，计算方式为： $h_{new}(x_a)= h_1(x_a)\oplus H(a)$ ,其中 $h_1(x_a)$ 是当前位置的索引，$x_a$ 是指纹 a 对应的数据，也就是哈希表中存储的元素。因此，被提出的 a 可以计算自己的另一个索引 $4 = h_1(x_a)\oplus H(fp_{x_a}) = 6\oplus H(a)$。需要说明的是，这个过程并不会用到源数据 $x_a$ 。
元素 a 继续挤兑另一个元素（在这里是索引 4 处的元素 c），并计算出 c 的另一个位置索引为： $1 = 4\oplus H(c)$,这个位置是空的，因此c存储到这个位置。

在上述过程中，使用一路哈希桶时，在未发生哈希碰撞的情况下，哈希桶的利用率为 50%。通过增加每个索引位置对应的哈希桶中的槽位数量可以提高空间利用率。理论上，当使用哈希桶大小为 2、4 和 8 时，空间利用率分别会提高到 84%、95% 和 98%。下图展示了二路哈希桶的添加元素过程，但不再对具体细节进行描述。

均衡分配

在上述的插入过程中，可以注意到，计算第二个索引位置时，指纹在与桶索引进行异或计算之前会先进行哈希处理。这种处理方式有助于在哈希表中实现均衡分配。如果第二个索引使用了 $i \oplus H(\text{fingerprint})$ 的计算方式，并且指纹的大小相对于哈希表的总大小（即哈希桶的数量）较小，那么被踢出的元素最终将会落在邻近的桶中。

举个例子，如果使用的是 8 位指纹，那么被踢出的元素将被放置在距离原桶 $i$ 最多 256（即 $2^8$）个桶的位置，因为异或计算会影响桶索引的低 8 位，而高位则保持不变。这种哈希指纹的方法确保了元素能够重新分布到哈希表的不同桶中，从而实现了均衡分配，减少了哈希碰撞，并提高了哈希表的利用率。

Lookup 算法

Lookup 算法用于查询一个数据是否存在于布谷鸟过滤器中。查询过程如下：

计算待查询数据 $x$ 的指纹 $fp = \text{fingerprint}(x)$。
根据指纹计算两个哈希索引 $h_1 = h_1(x)$ 和 $h_2 = h_2(x)$。
检查哈希表中这两个索引对应的桶是否包含该指纹 $fp$。

如果在这两个桶中都没有找到指纹 $fp$，则可以确定数据 $x$ 不在过滤器中。若在其中一个桶中找到了指纹 $fp$，则有很大可能数据 $x$ 存在于过滤器中，但不能完全确定，因为可能存在哈希碰撞。

Delete 算法

Delete 算法用于从布谷鸟过滤器中删除一个元素。操作步骤如下：

计算待删除元素 $x$ 的指纹 $fp = \text{fingerprint}(x)$。
根据指纹计算两个哈希索引 $h_1 = h_1(x)$ 和 $h_2 = h_2(x)$。
在哈希表中查找这两个索引对应的桶，找到并删除其中的指纹 $fp$。

一旦成功删除指纹 $fp$，则相应的元素 $x$ 被从过滤器中移除。

删除的局限

布谷鸟过滤器的删除并不完美，删除操作在相同哈希值仅被插入一次时是完美的，如果元素没有插入就进行删除，可能会出现误删除 (删除了相同哈希值的其他元素)，如果元素插入了多次，但是每次删除操作只删除一个值，那么就需要知道元素插入了多少次才能彻底删除，或者循环删除直到失败为止。

CuckooFilter与BloomFilter

优点

支持删除操作：布谷鸟过滤器支持删除元素，而布隆过滤器不支持。
高负载因子的查询效率更高：在高负载因子场景下，布谷鸟过滤器的查询效率通常优于布隆过滤器。
较低的存储空间开销：在存储数据量较大且期望误判率较低（低于 3%）的场景中，布谷鸟过滤器的存储空间开销通常低于布隆过滤器。
更易于实现：布谷鸟过滤器相较于布隆过滤器更容易实现。

缺点

桶大小要求：布谷鸟过滤器使用备用候选桶的方案，其中候选桶与首选桶通过位置和指纹的哈希异或计算得出。这要求桶的大小必须是 2 的幂（如 4、8、16、32 等），限制了桶大小的灵活性。
插入性能较低：布谷鸟过滤器在插入时，如果目标位置已满，需要将已有的指纹踢出到候选桶，这会导致插入性能下降。与布隆过滤器相比，布谷鸟过滤器的插入操作由于哈希碰撞的处理而更为复杂，插入性能相对较低。
处理重复元素的限制：布隆过滤器允许重复插入相同的元素，而布谷鸟过滤器在插入已存在的元素时会执行踢出操作，因此对重复元素的插入存在一定的限制。
删除操作的不完美：布谷鸟过滤器的删除操作并不完美。当元素仅插入一次时，删除操作是有效的；但如果元素未插入却尝试删除，可能会误删除相同哈希值的其他元素。如果元素插入多次，每次删除只会删除一个副本，这就需要知道元素的插入次数才能彻底删除，或者需重复删除操作直到删除失败。值得注意的是，如果只需要保证元素“绝对不存在”的语义，直接删除即可，无论是否存在重复元素。

Cuckoo过滤器的代码实现

参考文献

基于属性的加密 →