1.1.1. 06.布隆过滤器


布隆过滤器

当处理某一个值是不是已经存在 HyperLogLog 中时,它无能为力,它没有提供这样的方法。

场景:当我们使用新闻 APP 来看新闻时,它会不停的给我们推荐新闻,并且过滤到已经看过的重复新闻。怎么实现呢?

  • 如果将已收看过的新闻数据存在关系型数据库如 mysql 中,当推送系统进行推送时,可以从每个用户的历史记录里进行筛选,以过滤到看过的新闻,但是如果用户量很大并且看过的新闻很多的时候,服务器性能恐怕是跟不上的。
  • 如果采用缓存,那么又得浪费巨大的空间,这个数据一般是线性增长,坚持的了一个月但是没法坚持更长时间。

高级数据结构布隆过滤器(Bloom Filter)闪亮登场了, 它就是专门用来解决这种去重问题的。它在起到去重作用的同时,在空间上还能节省 90% 以上,只是稍微有那么点不精确, 也就是有一定的误判概率。

可以将布隆过滤器理解为不怎么精确的 set 结构。当布隆过滤器说某个值存在时,这个值可能不存在;当它说某个值不存在时,那么就一定不存在。

安装

# 下载包
git clone https://github.com/RedisBloom/RedisBloom.git
# 编译,会得到 redisbloom.so 
make

记录 redisbloom.so 的位置,然后将它加载到 Redis 中,这里有两个方式。

  1. 启动时加入
    # /path/to 改为自己的路径
    redis-server --loadmodule /path/to/redisbloom.so
    
  2. 放入配置文件中,我这边配置文件路径是 /usr/local/etc/redis.conf
    • 添加下面代码后保存,同样 /path/to 改为自己的路径。
      loadmodule /path/to/redisbloom.so
      
    • 然后重启 brew services restart redis,之后再打开 redis-cli 就可以使用布隆过滤器了

基本命令

添加一个元素,bf.add [key] [value] 判断一个元素是否存在, bf.exists [key] [value]

添加多个元素,bf.madd [key] [value1] [value2]... 判断多个元素是否存在,bf.mexists [key] [value1] [value2]...

127.0.0.1:6379> bf.add demo user1
(integer) 1
127.0.0.1:6379> bf.add demo user2
(integer) 1
127.0.0.1:6379> bf.add demo user3
(integer) 1
127.0.0.1:6379> bf.add demo user4
(integer) 1
127.0.0.1:6379> bf.add demo user5
(integer) 1
127.0.0.1:6379> bf.exists demo user1
(integer) 1
127.0.0.1:6379> bf.exists demo user10
(integer) 0
127.0.0.1:6379> bf.madd demo user6 user7 user8 user9 user10
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
127.0.0.1:6379> bf.mexists demo user11 user10 user9
1) (integer) 0
2) (integer) 1
3) (integer) 1

控制布隆控制器的误判率,bf.reserve [key] [error_rate] [initial_size]

  • error_rate:错误率,错误率越低,需要的空间越大。
  • initial_size:预计需要可能放入的数量。
  • 如果不是用 bf.reserve ,默认 error_rate 是 0.01,initial_size 是 100。
127.0.0.1:6379> bf.reserve demo 0.9 10
OK
127.0.0.1:6379> bf.madd demo user6 user7 user8 user9 user10
1) (integer) 1
2) (integer) 1
3) (integer) 0
4) (integer) 0
5) (integer) 0
127.0.0.1:6379> bf.mexists demo user11 user10 user1
1) (integer) 1
2) (integer) 1
3) (integer) 1

当 initial_size 设置过大时,会浪费存储空间,设置过小会影响准确率。所以一定要尽可能估计好元素个数,避免浪费空间。

同样,error_rate 越小,需要的存储空间就越大。对于不需要那么精确的场合,error_rate 稍大一点,无伤大雅。比如新闻 APP 去重新闻一样,误判只有小部分文章不适合被推送。

布隆过滤器的原理

每个布隆过滤器对应到 Redis 的数据结构就是一个大型的 位数组 和几个不一样的无偏 hash 函数。所谓无偏 hash 函数就是能够把 hash 值算的比较均匀,让元素被 hash 映射到位数组中比较均匀。

如图,baidu 这个词被 hash 函数算出值后取模得到得到一个位置,每个函数都会算出一个位置。

布隆过滤器的原理

布隆过滤器原理

当往布隆过滤器中添加 key 时,会使用多个 hash 函数对 key 进行 hash,算出一个整数索引值,然后对位数组长度取模运算得到一个位置,每个函数都会得到一个位置。再把这些位置都设置为 1,就完成了 add 操作。

向布隆过滤器询问一个 key 是否存在时,与 add 同样的操作,看看这几个值是否为 1,只要有一个为 0 则表示不存在。都为 1 ,并不能说明这个 key 一定存在,而是极有可能存在。因为这个 1 很有可能是别的 key 存在导致的。所以如果这个位数组比较稀疏,判断正确的概率就会很大,否则就小。

空间占用估计

布隆过滤器有两个参数,第一个是预计元素的数量 n,第二个是错误率 f。公式 根据这两个输入得到两个输出,第一个输出是位数组的长度 l,也就是需要的存储空 间大小( bit ),第二个输出是 hash 函数的最佳数量 k。 hash 函数的数量也会直接影 响到错误率,最佳的数量会有最低的错误率。

k=0.7*(l/n) #约等于
f=0.6185^(l/n)^表示次方计算,也就是 math.pow

为了省去麻烦,现在有很多现成的在线布隆计算器。

当实际元素超出时,误判率会有怎样变化

f=(1-0.5^t)^k #极限近似,k 是 hash 函数的最佳数量。

应用

  • 新闻 app 推送新闻过滤已读新闻。
  • 爬虫系统,过滤已经爬过的 URL。
  • 邮件的垃圾过滤系统,会有某些正常邮件也被放入垃圾邮件目录中,这个就是误判导致,概率很低。
Copyright © Kagami丶 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-12-10 21:46:19

results matching ""

    No results matching ""