# 布谷鸟过滤器

**Repository Path**: mixinju/cuckoo-filter

## Basic Information

- **Project Name**: 布谷鸟过滤器
- **Description**: 布谷鸟过滤器的C++实现，参考了论文作者在github上开源的部分
- **Primary Language**: Unknown
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-03-28
- **Last Updated**: 2023-02-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# README

## 项目背景

最早在我大一到大二那个暑假的时候，导师给了我们几个人几篇关于数据结构和算法方面的论文，希望可以开阔一下我们的视野，我看了其中一篇，这篇论文主要内容是关于在多个集合里面查询某个元素是否存在这多个集合中的任意一个，如果存在，又具体在那个集合里面。论文中提到了布隆过滤器和布谷鸟过滤器。然后我就去搜索这两个玩意，无意间找到了一篇介绍的比较详细的博客，里面给出了布谷鸟过滤器论文的GitHub项目地址。当时就心学来潮，想要自己参照着做一个。但是当时对C++还没有一个比较系统的学习，看源代码的时候，有些东西根本就不知道是什么。所以就暂时放下啦。



大二寒假，又重新捡起这个项目，打算在家里把它实现，可是想象很美好，现实很残酷，里面涉及的很多关于位的操作着实让我看不明白。



大二开学，计划写两个项目，第一个就是使用Go 语言实现的一个类似于groupchche 分布式缓存，然后在了解分布式缓存相关知识的时候，又看到了过滤器在解决 **缓存穿透** 中的作用，于是在完成了缓存这个项目后就开始了这个过滤器的实现。



虽然寒假在家没有完全搞懂整个逻辑，尤其是位的相关操作，但是这次在看的时候，很快就理解了里面比较核心的位操作。大概花了半天时间熟悉了项目的代码结构和原理，就开始写啦，中途还算顺利。 

## 遇到的困难

1. 首先要理解布谷鸟过滤器的基本工作原理和发送碰撞时其特有的挤兑策略是如何实现的
2. 按位进行存储和读取的时候遇到大量的位操作，刚开始难以捉摸其含义
3. 内存分配相关，对于使用动态内存分配的空间，一定要释放
4. C++ 泛型的特性，模板的使用，以及模板的嵌套

## API

`Add(item)` 向过滤器中添加一个元素

`Contina(item)` 查询是否存在某一个元素

`Size()` 返回当前总共有多少个元素存在与过滤器中

`Delete(item)` 从过滤器中删除对应的元素

`SizeInBytes()` 返回当前过滤器总共占用的内存字节数

### 简单示例

```C++
//创建一个元素类型是 32 位无符号整数大小为1000 的过滤器
CuckooFilter<uint32_t, 12> filter(1000);

// 插入一定数量的元素
for (uint32_t i = 0; i < 500; i++){
  if (filter.Add(i) != OK) {
    break;
  }
}

//统计误判率
for (uint32_t i = 1000; i <  2000; i++) {
  if (filter.Contain(i) == OK) {
    falseQueries++;
  }
    totalQueries++;
}

std::cout << "false positive rate is "
      << 100.0 * falseQueries / totalQueries << "%\n";

```




### 文件结构

## 构建方式

因为我自己对于稍微大型项目的构建和CMake也驾驭的不是很熟练，就使用了基本上不需要构建工具，简单的 `include` 就可以运行起来整个代码。当然也可以使用CMake 进行构建

CMake 构建方式如下

```C++
mkdir build
cd build
cmake 
```


> 本机运行环境为Windows11平台上的 WSL2，使用JetBrains 的Clion 进行开发


## 性能测试

> 增加操作和C++ `std::vector`  进行对比


### 插入

**N个桶插入N个数据**

|数据量（万）|时间（s）|同等数量下 `std::vector` 花费时间(s)|
|---|---|---|
|1|0.00052|0.00012|
|10|0.00608|0.00118|
|50|0.04158|0.00591|
|100|0.08712|0.01180|
|1000|1.16222|0.12054|



**N个桶插入2N个数据**

|数据量（万）|时间（s）|同等数量下 `std::vector` 花费时间(s)|
|---|---|---|
|2|0.00208|0.00024|
|20|0.01465|0.00242|
|100|0.06295|0.01199|
|200|0.12445|0.02399|
|2000|3.84169|0.24473|



**2N个桶插入N个数据**

|数据量（万）|时间（s）|同等数量下 `std::vector` 花费时间(s)|
|---|---|---|
|1|0.00046|0.00012|
|0|0.00482|0.00118|
|50|0.02667|0.00591|
|100|0.06395|0.01180|
|1000|1.24359|0.12054|





### 误判率(False Positive)

> X-Y 表示 X 个数据，Y 个桶


|数据量(万)|N-N|N-2N|N-N/2|
|---|---|---|---|
|1|0.05000%|0.06000%|0.07000%|
|10|0.07200%|0.04400%|0.10600%|
|50|0.06940%|0.05200%|0.09540%|
|100|0.09600%|0.04670%|0.09410%|
|1000|0.05636%|0.02801%|0.09819%|





以上测试结果与预期也基本相符，在100万以内的性能，还是可以的，但是1000万及以后就会出现耗时较长的情况。





## 存在的问题

### 1. false negative 

在N-N 也就是N 个数据N个bucket 的情况下

从 1 万到1000万进行测试，发现所有插入的数据都可以找到。

在2N-N ，也就是2N 个数据，N个bucket的情况下

平均只有 50%~60% 的数据插入进去，理论上每一个 bucket 有四个 tag，应该是可以插进去的，我猜想可能是哈希函数的问题。

### 2. 查询操作

在进行查询操作的性能测试时，我是先插入若干的数据，再去进行查询，然后利用前面已经测试过的插入数据的测试结果，两者相减，理论上就可以得到查询操作的时间，但是从结果来看，有些时候甚至出现了负数，这个就很让人迷惑啦。