其他判重数据结构
Bloom Filter
- 无法支持
删除和计数的功能， - 需要更多的存储空间来存储数据
因为在CS中，删除和计数是常见的操作，但是这会对布隆过滤器的存储空间产生影响，同样为了实现这一操作，需要更多的存储空间
- 数据量一旦达到了一定的层级，就需要进行一个扩容，对数据进行一个rehash
理论篇
如何工作
Cuckoo Filter可以支持删除和有限计数 和有界FPP1来优化布隆过滤器，其存储效率高于标准布隆过滤器
- cuckoo的每个元素使用两个bucket（每个元素对应到两个不同的bucket索引位置）
- cuckoo的每个bucket可能会存储多个元素，不只有一个元素
- bucket中存储的是data的
低f位的指纹而不是真实的数据（根据FPP确定的） - 使用
部分对称密钥来计算两个bucket的索引位置
基础操作
查找元素的时候，cuckoo会使用哈希函数并检查两个桶中的指纹，没有找到匹配的指纹，说明数据一定不在，如果找到了指纹，那么数据可能在- 当另一个元素将匹配到的指纹插入到两个已检查桶的任何一个时，就会报错
- 删除：删除该值对应存储桶中的指纹
- 计数：在
cuckoo中维护一个count来实现 - 插入：计算出两个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个位置都满了)，所以需要进行一个迭代kick
for (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;
}
有什么用
- 可以帮助我们快速的检查一个元素是否在某个集合中
数据库查询优化，将数据插入到cuckoo中，可以通过查询过滤器，来测试某个数据是否存在，如果查询失败，就不需要访问数据库- 边缘过滤，可以帮助我们快速的过滤掉一些无用的请求，提高网络传输效率。
类似于边缘缓存，但原始数据不需要存储在过滤器中1.利用网络边缘的
缓存节点（CDN边缘节点）缓存数据的技术，可以更快的向用户提供所需的内容，用户在请求特定的数据，即使在远程的服务器上，也能在较短的时间进行访问，常用在静态网页，图像，视频，音乐等多媒体内容的分发
2. 原始数据不需要存在过滤器中：可以在数据流传输过程中通过算法，技术和架构。进行实时的分析和过滤操作，提高数据处理和应用的效率和可靠性
如何选择
- Cuckoo Filter如果不会影响时间敏感度2，优先选择Cuckoo Filter，Cuckoo相比拥有更好的查询速度和更低的误判率，时间敏感度更好，可以快速的响应各种请求并且缩短响应时间
- Cuckoo的插入上随着数据的增多，效率会逐渐低下
- 对于相同的误报率，Cuckoo需要更少的空间
- Cuckoo还可以支持删除操作
参考
Cuckoo filter [Explained]
Cuckoo Filter: Practically Better Than Bloom
Bloom Filters by Example