bloom filter的开源实现程序memcached bloom filter
bloom filter是我目前看到的最经典的算法之一,用非常低的错误率换取非常高的时间、空间的效率,在各种海量数据场景或者需要快速判断的场景中都得到了大量的使用,但是,在国内的互联网,至少公开的研究中,还很少有人把这个当成一个课题来研究,也没有一个系统级别的开源的实现。
mc_bloom_filter 是用memcached的协议来封装的bloom filter的操作,牺牲了一些bloom filter的特性,来成全所有的语言能使用这一高效的工具,这是这个项目开发的目标。
鉴于google code 一直被墙,我决定用这篇博客来代替google code。
https://code.google.com/p/mc-bloom-filter/
各版本下载
多线程版本:mc_bloom_filter-multi-threads-v0.3beta
单线程版本:mc_bloom_filter-v0.2beta1
开发设计文档:mc_bloom_filter设计文档
效率测试文档:mc_bloom_filter各版本测试结果
google code 上的介绍
Introduction
Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员,被广泛使用于各种海量数据排重的场景中。Mc bloom filter是一个全新的排重服务器,它采用memcached的网络层封装了bloom filter的操作,使各种语言php、java、perl、python、go、c等等,都能使用memcached的协议进行bloom filter的操作。
Details
作者
bloom filter 的简介
bloom_filter的百度百科 Google黑板报 bloom filter算法详细介绍
mc bloom filter 的特性
- 1.完全采用memcached的网络层协议,创建、删除、添加、查看状态等。
- 2.mc bloom filter 是一个全内存的排重服务器,所有数据均放在内存中。
- 3.可以在一个实例中创建多个bloom filter,在内存允许的情况,可以创建几十G大小的bloom filter,支持最高上 百亿 的数据排重。
- 4.采用google员工写的的高性能hash算法murmurhash,保证bloom filter的hash的高速
- 5.单线程版单机读写速度能达到十万次/s(同网段两台服务器多线程压力测试 服务器配置:8核 Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 12G内存)
- 6.多线程版单机读写能力均能达到30万次/s(同网段两台服务器多线程压力测试 服务器配置:8核 Intel(R) Xeon(R) CPU E5620 @ 2.40GHz 12G内存)
- 7.32位、64位服务器兼容。
mc bloom filter 的安装
bloom filter 使用memcached网络层,依赖于libevent,先登录http://libevent.org/ 下载最新稳定版本。
wget https://github.com/downloads/libevent/libevent/libevent-2.0.20-stable.tar.gz tar zxvf libevent-2.0.20-stable.tar.gz cd libevent-2.0.20-stable ./configure make && make install
在bloom filter 的google code 上,下载mc bloom filter的最新稳定版本
1.wget bloom filter的最新稳定版本 2.修改Makefile文件,主要是修改libevent到你的目录 3.在目录中执行make,生成mc_bloom_filter【线上版】 mc_bloom_filter_【调试版】 两个可执行文件,调试版会打很多日志 4. nohup ./mc_bloom_filter -p12345 -d -uroot -m4000 –p/tmp/mc_bloom_filter.pid –l127.0.0.1 日志文件就是当前目录的nohup.out文件
mc bloom filter的启动参数
参数 | 是否必须 | 值的含义 |
p(小p) | 是 | 监听端口,默认12345 |
P(大P) | 是 | pid文件的地址 |
u(小u) | 是 | 用哪个用户运行 |
m(小m) | 是 | 最大内存,单位m |
d(小d) | 是 | 是否用daemon后台运行 |
l(小l) | 是 | 监听的ip |
t | 否 | 表示线程个数,只多线程版本有此参数,单线程无此参数,t默认为4 |
v | 否 | 是否将调试的输出打印出来,如果添加这个参数,会在终端或者nohup.out中打印调试信息 |
mc bloom filter 的命令
add | add key 0 0 value_lengthexpected_max_amount_of_elements|false_positive_rate比如add test 0 0 131000000|0.001 表示创建一个预计存100万,误判率千分之一的bloom filter | 成功返回STORED 失败返回NOT_STORED |
set | set key 0 0 subkey_lengthsubkey | 成功返回STORED 失败返回NOT_STORED |
get | get key|subkey | 存在返回1,不存在啥都不返回 |
stats | stats 查看服务器的总体状况 | 信息列表 |
stats blooms | 列举所有过滤器的名称和占用内存字节大小 | 信息列表 |
stats bloom key | 可以查看名字为key的bloom filter的详细信息 | 信息列表 |
try | try expected_max_amount_of_elements|false_positive_rate比如 try 100000000|0.0001 表示计算1亿个目标存储数,在误判率万分之一的情况下,需要的内存大小用来预估过滤器所需的内存大小和hash函数个数 | 信息列表 |
setmem | setmem size(Mbytes) 用来设定当前进程可使用的内存容量,单位是m,比如要设置内存1G,setmem 1024 成功返回STORED | 成功返回STORED,失败返回NOT_STORED |
PHP 的使用demo
<?php $mc = new Memcache(); $mc -> add("my_bloom","10000000|0.0001"); $mc -> set("my_bloom","2222222"); var_dump($mc->get("my_bloom|2222222"); ?>
具体的文档在这里 https://code.google.com/mc_bloom_filter
相关推荐
- 程序员,中国最值得同情的职业么?
- Posted on 04月25日
- Lua在linux下的安装[Lua研究一]
- Posted on 03月08日
- Webkit内核探究【2】——Webkit CSS实现【转】
- Posted on 04月06日
- 如何让网站打开更快第三弹–开启压缩篇【转载】
- Posted on 04月11日
先顶了,我们小组最近也要弄这个
欢迎使用,有问题,我们随时做技术支持
Hi we need technical support for our company kindly contact me on danqam@gmail.com as soon as possible
学习了,给朋友看看
谢谢,我想问下,我有大约n=1亿 个数字的集合(每个数字有10位),所有数字大小都是随机分布的。我想保证错误率低于0.01,按公式,哈希函数需要k约7个。请问如何选择哈希函数比较合适呢?我用seed种了7个质数。如何?* @param type $str* @param type $seed 7,11,13,17,19,23,29* @return type*/private function hash($str, $seed){$hash = 0;for($len = strlen($str),$i=0; $i<$len; $i++){$hash = $seed * $hash + ord($str{$i});}return $hash & 0x3FFFFFF;//2^27}
谢谢,我想问下,我有大约n=1亿 个数字的集合(每个数字有10位),所有数字大小都是随机分布的
没看懂你问的啥…
谢谢,我想问下,我有大约n=1亿 个数字的集合(每个数字有10位),所有数字大小都是随机分布的
你好 我执行 echo “stats”|nc 127.0.0.1 12345 怎么没有返回东西了 另外如果使用java访问的话 网上那些第三方包 可以用吗 stats bloom有提供这个方法?
stats 是个私有方法,你可以修改你的sdk来支持这个命令,也可以直接走socket发送这个命令。
很赞
很久没有过来了,今天过来看一看!
本人在此留言并不代表本人同意、支持或者反对文章观点;
网站不错很漂亮,欢迎互访!
很久没有过来了,今天过来看一看!
[good] 学习了,给朋友看看
这个更刺j激,准备好手纸哦 A 片。。 http://T.CN/RcLNTFM
这个更刺j激,准备好手纸哦 A 片。。 http://T.CN/Rca9M0K
全都到碗里来 !美臀/丝袜/美熟女乱伦精品大合集 !!!【 v.ht/xZiU 】
这个更刺j激,准备好手纸哦 A 片。。 http://uVU.cc/iqVw
男人的天堂、高清萝舞,电动棒棒各种耍 http://uVU.cc/iqVo
这个 更C刺j激,A 片:htTP://uVU.Cc/iqVr
打开 288d.pw 都是 浪美眉
快来看!这个爽/啊,/男/人/都/喜/欢/,哇:,htTP://uVU.Cc/iqVp
▇▇▇▇无毒爽站【htTP://v.ht/aS8H】 ,在线爽,夫妇必备 ▇▇▇▇▇
是男L人L就L上的L网C战,A 片:htTP://uVU.Cc/ijW6
是男L人L就L上的L网C战,A 片:htTP://uVU.Cc/ijW6
是男L人L就L上的L网C战,A 片:htTP://uVU.Cc/ijW6
淘宝 天猫 内部无门槛优 惠券Q群 594970228
男人的天堂、高清s萝舞,电动s棒棒各种耍 http://uVU.cc/iqVo
这个更,刺,激,准备,好手纸哦 A 片。。 http://T.CN/RxzMCzF
会出的 因为第九季会出乌拉拉
官员喊:要高薪养廉,不给高新我们就不廉洁,我们会贪污!
是的在夏天这个事件将会大规模爆发注意做好防范工作。