欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bloom filter server 博客分类: boost学习 boostbloom filter

程序员文章站 2024-03-06 13:42:26
...
1.实现
基于boost svn中bloom filter库编写。为beta版,需要依赖其他项目的日志库等组件,有兴趣的朋友可以私信联系,我来优化
https://github.com/godlovesdog/bloom_filter
2.简介
bloom filter是一种消重过滤器,该过滤器具有如下

优势:
  • 存储空间小:过滤器是一个位矢量,每个数据元素被hash成该矢量中的某几个bit,而非hash成多个字节。
  • 时间复杂度低:O(1),只需进行简单的hash计算

缺点:
  • 有一定的误判率——如果待查询数据在filter中,就一定能被判别出来;但因为hash碰撞,未在filter中的元素仍有可能被误判为已存在
  • 误判率可以通过增大存储空间而控制在一定范围内。如用512MB空间作为filter,使用7个hash函数时,向该过滤器中存储1000万个元素时,误判率为1.26312e-07%;存储1亿条记录时,误判率为0.201594%
  • 无法删除filter中的元素

3.使用
3.1 启动
git clone $G:bloom_filter
cd bloom_filter/bin
./bloom_filter

配置文件bloom_filter/conf.ini
默认监听8000端口
3.2 请求
支持GET及POST两种http请求方式:
  • GET:查询某个key是否已在filter中存在
  • POST:查询某key是否已存在filter中,不存在则将其插入到filter中

参数必须为"ks"多个key之间以逗号分隔
curl http://172.28.0.23:8000/?ks=1,2
curl http://172.28.0.23:8000/?ks=1,2 -X POST
3.3 返回结果
json字符串
{
    "1": "false",
    "3": "false"
}
相关标签: boost bloom filter