黑马程序员技术交流社区

标题: 【上海校区】基于Redis的布隆过滤器的实现 [打印本页]

---

作者: 陈泽    时间: 2019-12-26 17:14
标题: 【上海校区】基于Redis的布隆过滤器的实现


项目简介  
      包含一个基于Redis的布隆过滤器的实现，以及应用到爬虫中scrapy框架中的Demo中。
       地址：BloomFilterRedis
布隆过滤器
      网上有很多介绍，推荐《数学之美》，介绍的很详尽，此处不再阐述
哈希函数
      布隆过滤器中需要n个哈希函数，我使用的是Arash Partow提供的常见哈希函数

建立在Redis上的布隆过滤器
     Redis中有一个数据结构叫做Bitmap(在下方有官网详解)，它提供一个最大长度为512MB（2^32）的位数组。我们可以把它提供给布隆过滤器做位数组。
     根据《数学之美》中给出的数据，在使用8个哈希函数的情况下，512MB大小的位数组咋误报率万分之五的情况下可以对约两亿的url去重。而若单纯的使用set()去重的话，以一个url64个字节记，两亿url约需要128GB的内存空间，不敢想象。
     我使用的策略是使用哈希函数算出哈希值对2^32取模，填入bitmap中。


Redis之Bitmap
      以下内容翻译来自官网http://www.redis.cn/topics/data-types-intro.html#bitmaps，
       英文水平有限，有些地方选择了意译，大佬路过还请不吝赐教
       Bitmap不是一个确切的数据类型，而是基于String类型定义的一系列面向位操作的方法。因为String是二进制安全的并且他们的最大长度是512MB,所以String类型很适合去作为一个2^32长度的位数组。
       位操作方法可以被分为两组：
               一、对单一位的操作，比如设置某一位为1或0，或者得到这一位的值；
               二、对一组位的操作，比如说计算一定范围内的1的个数(比如计数)
       bitmap一个最大的优势是它通常能在存储信息的时候节省大量空间。比如说一个用增量ID来辨别用户的系统，可以用仅仅512MB的空间来标识40亿个用户是否想要接受通知

       使用SETBIT和GITBIT命令来对位进行置数和检索
      

[Shell] 纯文本查看 复制代码

> setbit key 10 1

(integer) 1

> getbit key 10

(integer) 1

> getbit key 11

(integer) 0

       SETBIT 如上所示，意思是将第10位置位为1，第二个参数可为0或1。如果设置的位超出了当前String的长度，那么会自动增长。（最长2^32，下同）
      GETBIT 如上所示，返回第10位和第11位的数据，分别是1和0。如果查找的位超出了当前String的长度，那么会返回0     


      接下来是三个对一组位进行操作的命令:
      BITOP 执行不同字符串之间的逐位操作。所提供的操作有AND，OR，XOR和NOT。BITCOUNT
      BITCOUNT 计数,返回bitmap里值为1的位的个数.
      BITPOS 返回第一个0或1的位置
      BITPOS和BITCOUNT不仅可以作用于整个bitmap，还可以作用于一定的范围,下面是一个BITCOUNT的例子:
      

[Shell] 纯文本查看 复制代码

> setbit key 0 1

(integer) 0

> setbit key 100 1

(integer) 0

> bitcount key

(integer) 2

       应用实例略……

整合进scrapy

      Scrapy中可以在settings.py中通过DUPEFILTER_CLASS配置过滤器，github上给出了示例工程。

验证
    起初的验证策略是：使用scrapy框架从一个百度百科页面出发，提取页面内其它百科词条的链接，在过滤器内将过滤掉的url记录在本地文件
filted.txt中，将正确请求的到的结果存入mongoDB。


    在起初测试时发现filted.txt中记录的过滤掉的url中百分之九十九都不在mongoDB内，注意到已过滤掉约1万条url，而mongoDB中仅有300条，
使用bitcount key命令查看redis中的bitmap中的值为1的位的个数，发现有约10万。而mongoDB中的300条数据至多置位300*8=2400位，显
然哪里出了问题。经分析，这是因为大量经过过滤器的请求尚存在于scrapy的请求队列中，未被发出，所以mongoDB里也不会有相应记录。


     所以为了验证布隆过滤器的可靠性，在过滤器过滤前将所有的url都存入allurl.txt文件，等文件内url达到一定规模后，与filted.txt进行
相应处理——编写脚本计算误报率。经验证，在对百度百科约70万条url进行处理后，过滤约40万条，误判量为0。此验证规模甚小，但笔者近期无具体大
规模去重需求，欢迎有需求或有兴趣的同仁使用并反馈。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2