首页->正文

Bloom Filter算法在php中的实现

2012-02-28 -Web开发 标签: php

由于涉及对千万级的URL去重,且要保证时间较短,开始想到的是最简易的php关联数组,对URL md5后取前16位做KEY。500万个URL,32位下占用的内存达到450M,而64位下则到790M,但处理速度很快。但千万级甚至上亿的URL此种方法就不适合了,当然可以通过把URL分开,交给不同的机器处理,例如crc32后,模除,之后再把过滤后的URL汇总。但这样必须考虑URL如何传输,代码变得较复杂,暂时先不考虑,先考虑下如何提升处理速度。因此,引入Bloom Filter算法来去重过滤。

*说明下php中已经有Bloom Filter的扩展模块http://pecl.php.net/package/bloomy,已经很好的实现此功能了,效率非常高,可以直接编译加载。

介绍下Bloom Filter的基本处理思路:申请一批空间用于保存0 1信息,再根据一批哈希函数确定元素对应的位置,如果每个哈希函数对应位置的值为全部1,说明此元素存在。相反,如果为0,则要把对应位置的值设置为1。由于不同的元素可能会有相同的哈希值,即同一个位置有可能保存了多个元素的信息,从而导致存在一定的误判率。

如果申请空间太小,随着元素的增多,1会越来越多,各个元素冲突的机会越来越来大,导致误判率会越来越大。另外哈希函数的选择及个数上也要平衡好,多个哈希函数虽然可以提供判断的准确性,但是会降低程序的处理速度,而哈希函数的增加又要求有更多的空间来存储位置信息。

详细的元素个数对应的最佳位置空间和哈希函数的个数关系参考这里,我是看不懂……
php的bloomy扩展中计算方法的关键部分贴出来给大家参考一下:
#define MAX_HASHES      50
double h;
double curr_size = 0.0;
double opt_size  = (double)SIZE_MAX;
double opt_h     = 0.0;
for (h = 0.0; h < (double)MAX_HASHES; h++) {
     if ((curr_size = ((-h * num_elements) / 
        log(1 - pow(max_error_rate, 1 / h)))) < opt_size) {
          opt_size = curr_size;
          opt_h    = h;
     }
}
//num_elements为元素的个数,max_error_rate为期望的错误概率
//opt_size为最佳位置空间,opt_h为最佳的哈希函数的个数


接下来说下php中此如何模拟此方法的实现,当然,效率上已经大大折扣了……

存储空间上可以使用php的数组或字符串方法处理:
php的数组类型适合处理较少的数据,较多的元素php数组占用内存量会很大。例如100w个元素的数组仅存储整型数字,由于php本身的原因,32位下要占用72M内存,大约可以满足100w*32=3200w个位置空间(int型的整数可存储32个位置)。

再说字符串,而字符串本身在php中就可以通过数组的方式访问和修改,每个字符可以存储8个位置的空间,所以32M的一个字符串可以存储32*1024*1024*8=268435456,大约2.6亿个位置,明显大于数组方式,并且字符串的内部都是CHAR类型,无论是32还是64位下都占用1字节,所以选择此种方式来实现。

实现过程中要考虑哈希函数个数的选择,理论上说在位置空间满足的情况下,哈希函数越多,准确程度越高。我们采用sha1方式,把sha1后的结果以7个长度分割,每段转换为10进制的数,对应存储位置。
那为什么是7个长度?由于sha1返回的是16进制的数据,取7位后最大数为0xFFFFFFF,即十进制的268435455,也就是2的28次方-1,在加上0正好为32M内存,即完全对应这7个长度的空间,从而避免模除,直接当做位置来存储。当然可以一次取8个,提高哈希函数的唯一性,但同时要申请更多内存,2的32次方/8,即512M内存。

默认的哈希函数个数为6个,也就是说对一个元素运行这6个函数,如果返回的值对应位置空间全部存在的话就表示这个元素已经存在。

具体的实现代码在这里,供大家参考。

再说下其中遇到的问题,开始想到的是用一个很长的空间存储位置信息,发现由于模除原因,php在32位下会有问题,虽然可以使用bcmod来解决,但是毕竟是一次函数调用,影响计算时间,而且随着元素的增多,由于哈希函数值的限制,导致再长的空间也无法使用。后来想到的就是根据每个元素sha1后,取前2位模除,分配到多个独立的存储空间中,保证了在大数据量下的准确度。当然这个分配算法有个原则:务必保证相同的元素分配到同一个空间中。

还有一个影响性能的问题要注意下,由于是要在一个字节上存储8个位置信息,而信息又是保存在字符串中,就要求对字符频繁进行ORD和CHR的操作,所以可以考虑提前把0-255之间的转换关系存到关联数组中,通过这样避免这两次函数调用,这样整个计算过程除了sha1函数的调用和截取,基本都可以通过数组和运算符完成,保证的程序的运行效率。

其他的排重方法
1 memcached去重的方法也可以考虑,优点是可以多个程序公用去重结果,准确率很高,缺点是必须安装单独的服务,并且每次去重前要删除全部的KEY。
2 文件判断方法,比如把元素hash后分成256/256目录,按照每个目录下1000个文件算,也能处理不少。当然这样可能较慢,但消耗的内存也最少,可以试验下。

另外可考虑的改进
1 单个服务器上可以采用多个进程同时处理这些URL,充分利用多CPU。当然得考虑好数据的分配,以及数据排重完成后续任务的跟进
2 如果对排重的要求不是很严格,可以把URL从整体上分配,例如某台机器只读取一部分,然后在各自进行排重处理,从而加快处理速度
3 还可以把每次排重完的位置空间保存到文件中,下次排重的时候直接读取到内存中

最后说一句,追求高效率的话,特别是这种数据计算、内存写入密集型的,还是用C写扩展吧……

参考资料
http://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8
http://www.perl.com/pub/2004/04/08/bloom_filters.html

下一篇 一则MySQL更新慢的问题

上一篇 session读取导致页面加载慢

相关文章

Ubuntu下编译安装PHP

使用curl_multi_init并发请求

php增加Last-Modified为何无效

用xhprof分析php代码

正则修饰符m和s用法

文章分类

开发小提示

  • 1:Mongodb中通过db.yourCollectionName. dataSize()查看某个文档的大小
  • 2:linux下用reset命令恢复查看二进制文件导致的命令行乱码
  • 3:查看MySQL表的索引情况show index from tableName
  • 更多...

交流

  • wangnow(a)126.com