应用场景：新闻推荐中的去重，垃圾邮件地址的过滤，危险域名的过滤，URL爬虫去重等
在这些情况下，一般会想到解决方案：服务器记录了用户看过的所有历史纪录，推荐系统每次都从用户的历史纪录内筛选已经看过的记录，但用户量很大并且每个用户看过的新闻又很多时，推荐系统的去重功能在性能上不一定能跟的上。并且如果历史记录保存在关系数据库中，去重就要频繁的对数据库进行exists查询，当并发量上来时，数据库首先会扛不住压力。
再其次可能会想到缓存，但这么大量的历史纪录全部缓存下来，浪费的存储空间就太大了，并且这个存储空间是线性增长的，能撑得住一个月，不一定撑得了几年，但不用缓存，性能又跟不上。而追求更少占用空间，更高性能的最优解方案是就是布隆过滤器（Bloom Filter）, 起到去重的同时，在空间上还能节省90%以上，只是存在一定的误判概率。
Redis4.0开始自带了这个功能，较低版本可以使用第三方扩展，实现布隆过滤器的功能，第三方扩展在空间占用上做的不是很好
基本使用
布隆过滤器有两个基本指令，bf.add 添加元素，bf.exists 查询元素是否存在，bf.madd 一次添加多个元素，bf.mexists 一次查询多个元素。
布隆过滤器在第一次 add 的时候自动创建基于默认参数的过滤器，Redis 还提供了自定义参数的布隆过滤器。在add之前使用 bf.reserve 指令显式创建，其有3个参数，key，error_rate， initial_size，错误率越低，需要的空间越大，error_rate 表示预计错误率，initial_size 参数表示预计放入的元素数量，当实际数量超过这个值时，误判率会上升，所以需要提前设置一个较大的数值来避免超出。默认的 error_rate 是0.01，initial_size 是100。
注意事项
布隆过滤器的 initial_size 估计的过大，会浪费存储空间，估计的过小，就会影响准确率，用户在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出估计值很多。布隆过滤器的 error_rate 越小，需要的存储空间就越大，对于不需要过于精确的场合，error_rate 设置稍大一点也无伤大雅。
在创建数据之前，确定最终追求的错误率越低还是空间占用越小，如果创建数据时埋下坑，那就不好玩了。
基础原理
每个布隆过滤器对应到 Redis 的数据结构里面就是一个大型的位数组和几个不一样的无偏 hash 函数。所谓无偏就是能够把元素的 hash 值算得比较均匀。 向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash 算得一个整数索引值然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置。再把位数组的这几个位置都置为 1 就完成了 add 操作。 向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都位 1，只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。如果都是 1，这并不能说明这个 key 就一定存在，只是极有可能存在，因为这些位被置为 1 可能是因为其它的 key 存在所致。如果这个位数组比较稀疏，判断正确的概率就会很大，如果这个位数组比较拥挤，判断正确的概率就会降低。
维基百科：Bloom Filter
空间计算
布隆过滤器存储的是数据指纹，不存储数据本身，这在实际上进行了压缩空间。
布隆过滤器有两个参数，第一个是预计元素的数量 n，第二个是错误率 f。公式根据这两个输入得到两个输出，第一个输出是位数组的长度 l，也就是需要的存储空间大小 (bit)，第二个输出是 hash 函数的最佳数量 k。hash 函数的数量也会直接影响到错误率，最佳的数量会有最低的错误率。
k=0.7*(l/n) # 约等于 f=0.6185^(l/n) # ^ 表示次方计算，也就是 math.pow，从公式中可以看出 位数组相对越长 (l/n)，错误率 f 越低，这个和直观上理解是一致的，位数组相对越长 (l/n)，hash 函数需要的最佳数量也越多，影响计算效率
当一个元素平均需要 1 个字节(8bit) 的指纹空间时 (l/n=8)，错误率大约为 2%
错误率为 10%，一个元素需要的平均指纹空间为 4.792 个 bit，大约为5bit
错误率为 1%，一个元素需要的平均指纹空间为 9.585 个 bit，大约为10bit
错误率为 0.1%，一个元素需要的平均指纹空间为 14.377 个 bit，大约为15bit，
文章内容参考自 付费掘金小册，作者老钱
最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券
