其他判重数据结构

• Bloom Filter

1. 无法支持删除和计数的功能，
2. 需要更多的存储空间来存储数据

因为在CS中，删除和计数是常见的操作，但是这会对布隆过滤器的存储空间产生影响，同样为了实现这一操作，需要更多的存储空间

1. 数据量一旦达到了一定的层级，就需要进行一个扩容，对数据进行一个rehash

理论篇

如何工作

Cuckoo Filter可以支持删除和有限计数 和有界FPP¹来优化布隆过滤器，其存储效率高于标准布隆过滤器

• cuckoo的每个元素使用两个bucket（每个元素对应到两个不同的bucket索引位置）
• cuckoo的每个bucket可能会存储多个元素，不只有一个元素
• bucket中存储的是data的低f位的指纹而不是真实的数据（根据FPP确定的）
• 使用部分对称密钥来计算两个bucket的索引位置

基础操作

1. 查找元素的时候，cuckoo会使用哈希函数并检查两个桶中的指纹，没有找到匹配的指纹，说明数据一定不在，如果找到了指纹，那么数据可能在
2. 当另一个元素将匹配到的指纹插入到两个已检查桶的任何一个时，就会报错
3. 删除：删除该值对应存储桶中的指纹
4. 计数：在cuckoo 中维护一个count来实现
5. 插入：计算出两个bucket索引位置，将元素的指纹存放到两个bucket的其中一个空闲的位置中，冲突就需要进行递归的对元素迁移，重复上诉操作

实现

获得索引位置

bucketi=h1(x) = hash(x),
//使用对称加密
bucketj=h2(x) = h1(x) ⊕ hash(x’s fingerprint).
//使用对称加密很方便获得另一个hash位置
bucketi=bucketj^hash(x’s fingerprint).

    void generateIndexHash(const string &data, uint32_t fp, uint32_t &b1, uint32_t &b2) //根据该finger生成获得对应的存储位置{b1 = finger_hash_(data) % num_bucket_; //生成两个索引位b2 = (b1 ^ finger_hash_(to_string(fp))) % num_bucket_;}

插入

cuckoo 会使用hash函数将与元素hash到两个bucket中，并将指纹（低f位，根据hash函数计算出来的（和选择插入位置的哈希函数不同））插入到任意一个开放的位置（每个hash桶可以存储多个元素，而不仅仅只有一个）

• 如果两个桶都有位置，那么cuckoo会将该元素的指纹随机选择一个桶插入（不是插入到两个桶），插入到该桶中的任意一个空闲的位置（由hash函数计算出来）
• 如果随机选择的其中一个桶位置被占了，就会插入到另一个桶中
• 如果两个桶都满了，cuckoo会将其中一个桶的某个元素踢走，新元素插入到该位置上，如果被题的元素有备用位置，就将其插入到备用的位置上，递归（递归的进行插入，在两个桶捣腾，重复上诉过程）这一过程，如果所有备用位置都完了，就认为失败
  

    bool InsertImpl(uint32_t fp, uint32_t bucket_index){vector<uint32_t> &bucket = table_[bucket_index]; //获得对应的桶//因为每个桶存4个元素for (uint8_t i = 0; i < num_entry_per_bucket_; i++){if (!bucket[i]){max_entry_++; //存储的元素++bucket[i] = fp;return true;}}return false;}bool Insert(const string &data){//获得指纹,获得低finger位置uint32_t fp = finger_hash_(data) & ((1 << fingerprint_size_) - 1); //这个是对应的指纹位最大也才10位，所以不会超出限制uint32_t b1, b2;                                                   //每个元素对应两个索引位置generateIndexHash(data, fp, b1, b2);if (InsertImpl(fp, b1))return true;if (InsertImpl(fp, b2))return true;//两个都满了(2个bucket的8个位置都满了)，所以需要进行一个迭代kickfor (uint32_t i = 0; i < kMaxNumKicks; i++){//选择其中一个桶的元素，并让该元素离开uint32_t b = (rand() % 2 == 0) ? b1 : b2;uint32_t r = rand() % num_entry_per_bucket_; //获得要替代的元素uint32_t tmp_fp = table_[b][r];table_[b][r] = fp; //插入fp = tmp_fp;       //将该kick出去的fp要获得他其他的索引位//根据该fingerprint获得其对应的两个索引位置//还是b1和b2两个位置if (b == b1){//因为在转化的时候，要替换的元素只有一个位置不一样if (b2 = (finger_hash_(to_string(fp)) ^ b1) % num_bucket_; InsertImpl(fp, b2))return true;}if (b == b2){if (b1 = (finger_hash_(to_string(fp)) ^ b2) % num_bucket_; InsertImpl(fp, b1))return true;}}return false;}

查找

bool lookUpImpl(uint32_t fp, uint32_t index){vector<uint32_t> &bucket = table_[index];for (uint8_t i = 0; i < num_entry_per_bucket_; i++){if (bucket[i] == fp){return true;}}return false;}bool lookUp(const string &data) //查找一个元素{uint32_t fp = finger_hash_(data) & ((1 << fingerprint_size_) - 1); //这个是对应的指纹位最大也才10位，所以不会超出限制uint32_t b1, b2;generateIndexHash(data, fp, b1, b2);if (lookUpImpl(fp, b1) || lookUpImpl(fp, b2)){return true;}return false;}

删除

    bool DeleteImpl(uint32_t fp, uint32_t index) //实现删除的逻辑{vector<uint32_t> &bucket = table_[index];for (uint8_t i = 0; i < num_entry_per_bucket_; i++){if (bucket[i] == fp){//找到了max_entry_; //总个数减少bucket[i] = 0;return true;}}return false;}bool Delete(const string &data) //删除一个元素{uint32_t fp = finger_hash_(data) & ((1 << fingerprint_size_) - 1); //这个是对应的指纹位最大也才10位，所以不会超出限制//获得他的索引位置uint32_t b1, b2;generateIndexHash(data, fp, b1, b2);//因为一个元素只会出现一个bucket中，所以找到一个就算可以了if (DeleteImpl(fp, b1) || DeleteImpl(fp, b2)){return true;}return false;}

有什么用

1. 可以帮助我们快速的检查一个元素是否在某个集合中
2. 数据库查询优化，将数据插入到cuckoo中，可以通过查询过滤器，来测试某个数据是否存在，如果查询失败，就不需要访问数据库
3. 边缘过滤，可以帮助我们快速的过滤掉一些无用的请求，提高网络传输效率。
   类似于边缘缓存，但原始数据不需要存储在过滤器中
   

   1.利用网络边缘的缓存节点（CDN边缘节点）缓存数据的技术，可以更快的向用户提供所需的内容，用户在请求特定的数据，即使在远程的服务器上，也能在较短的时间进行访问，常用在静态网页，图像，视频，音乐等多媒体内容的分发
   2. 原始数据不需要存在过滤器中：可以在数据流传输过程中通过算法，技术和架构。进行实时的分析和过滤操作，提高数据处理和应用的效率和可靠性

如何选择

1. Cuckoo Filter如果不会影响时间敏感度²，优先选择Cuckoo Filter，Cuckoo相比拥有更好的查询速度和更低的误判率，时间敏感度更好，可以快速的响应各种请求并且缩短响应时间
2. Cuckoo的插入上随着数据的增多，效率会逐渐低下
3. 对于相同的误报率，Cuckoo需要更少的空间
4. Cuckoo还可以支持删除操作

参考

Cuckoo filter [Explained]
Cuckoo Filter: Practically Better Than Bloom
Bloom Filters by Example