开发笔记:大数据之布隆过滤器学习

1 BloomFilter的由来

​ 由霍华德.布隆的一个人在70年代提出的一个二进制向量数据结构。它可以帮助我们检测一个元素是否为这个集合中的一员。检测的结果可以100%保证元素一定不在这个集合中&＃xff0c;但是不能100%一定在这个集合中。

tips:

从容器角度来说&＃xff1a;

​ 如果布隆过滤器判断元素在集合中存在&＃xff0c;不一定存在

​ 如果布隆过滤器判断不存在&＃xff0c;一定不存在

从元素角度来说&＃xff1a;

​ 如果元素实际存在&＃xff0c;布隆过滤器一定判断存在

​ 如果元素实际不存在&＃xff0c;布隆过滤器可能判断存在

1.1 爬虫

1.2 在hbase中的应用

作用&＃xff1a;能减少get/scan的查询时间。不过它肯定增加集群的负担&＃xff0c;在早期的hbase中是默认关闭的。在当前版本中默认实际是开启的。
hbase支持以下的布隆过滤器的类型&＃xff1a;
- NONE &＃xff1a; 不使用布隆过滤器
- ROW &＃xff1a; 行键使用布隆过滤器
- ROWCOL &＃xff1a; 行键&＃43;列簇使用布隆过滤器


1.3 缓存穿透

所谓缓冲穿透&＃xff0c;就是例如在上图中&＃xff0c;用户向Redis请求查询&＃xff0c;但是没有查询到。接下来就会去数据库中查询&＃xff0c;发现数据库里也没有&＃xff0c;返回空。经过多次这样的操作&＃xff0c;如果每次查询不到&＃xff0c;都要在去数据库中再访问一遍&＃xff0c;无疑会给数据库造成很大的压力。这种情况就是属于穿透了。
这时候就需要在Redis中设置一个特殊的标志&＃xff0c;当用户访问Redis为空或者访问到这个标志后&＃xff0c;就默认数据库中也没有这个数据&＃xff0c;也就减少了数据库的压力。
但是有一点要注意&＃xff0c;这个访问到特殊标志&＃xff0c;就默认数据库没有数据一定要设置存活时间&＃xff0c;当数据库中增加信息的时候&＃xff0c;一定要让用户可以访问到。
随着数据的增多&＃xff0c;特殊标识符的使用显得有点不足&＃xff0c;这时候还是布隆过滤器承担重任。


1.4 布隆过滤器的其他应用场景

• 反垃圾邮件&＃xff0c;从数十亿垃圾邮件列表中 判断某邮箱是否是垃圾邮箱
• Google Chrome使用布隆过滤器识别恶意URL
• Medium使用布隆过滤器避免推荐给用户已经读过的文章
• Google BigTable,Apache HBase,Apache Cassandra使用布隆过滤器减少对不存在的行和列的查找。

1.5 拓展

问&＃xff1a;如何在海量元素中&＃xff08;例如 10 亿无序、不定长、不重复&＃xff09;快速判断一个元素是否存在&＃xff1f;

• 答1&＃xff1a;好&＃xff0c;我们最简单的想法就是把这么多数据放到数据结构里去&＃xff0c;比如List、Map、Tree&＃xff0c;一搜不就出来了吗&＃xff0c;比如map.get(),我们假设一个元素1个字节的字段&＃xff0c;10亿的数据大概需要 900G 的内存空间&＃xff0c;这个对于普通的服务器来说是承受不了的。
• 答2&＃xff1a;用一种好的方法&＃xff0c;巧妙的方法来解决&＃xff0c;这里引入一种节省空间的数据结构&＃xff0c;位图&＃xff0c;他是一个有序的数组&＃xff0c;只有两个值&＃xff0c;0 和 1。0代表不存在&＃xff0c;1代表存在。

我们还需要一个映射关系&＃xff0c;你总得知道某个元素在哪个位置上吧&＃xff0c;然后在去看这个位置上是0还是1&＃xff0c;

• 用到哈希函数&＃xff0c;用哈希函数有两个好处&＃xff0c;第一是哈希函数无论输入值的长度是多少&＃xff0c;得到的输出值长度是固定的&＃xff0c;第二是他的分布是均匀的&＃xff0c;如果全挤的一块去那还怎么区分&＃xff0c;比如MD5、SHA-1这些就是常见的哈希算法。

如上图中的1998和1996经过哈希函数得到的哈希值一样&＃xff0c;就成为哈希冲突或者哈希碰撞。我们可以通过两种方法降低哈希碰撞产生的可能性。第一是扩大位图&＃xff0c;但是内存消耗也在增加。第二是经过多个河西函数处理&＃xff0c;但是越来越耗费时间。所以&＃xff0c;还是需要用到布隆过滤器来处理。