Redis 布隆过滤器介绍

Redis 布隆过滤器介绍

文章目录

• • 前言
  • 原理
  • 应用场景
  • 常用命令

前言

在 Redis 相关的面试题中，经常会被问到如何解决缓存穿透的问题。
缓存穿透是指查询一个 Redis 中不存在的 key，导致每次查询都穿透 Redis，访问到数据库，造成数据库压力过大。比如一直查询 id 为 -1 的用户记录。
解决方案也很多，比如在接口层增加校验，Redis 中缓存空值，或者是使用布隆过滤器。
布隆过滤器可以过滤掉 Redis 中不存在的 key，但是没被布隆过滤器过滤掉的 key 也是有可能不存在 Redis 中，即有一定的误判率。
家人们，咱就是说，当布隆过滤器说某个值不存在时，那就肯定不存在，当布隆过滤器说某个值存在时，这个值有可能不存在。

原理

每个布隆过滤器对应到 Redis 的数据结构里就是一个大型的位数组和几个不一样的无偏 hash 函数，如下图中的 f、g、h 就是这样的 hash 函数。所谓无偏就是能够把元素的 hash 值算的比较均匀，让元素被 hash 映射到位数组中的位置比较随机。

向布隆过滤器中添加 key 时，会使用多个 hash 函数对 key 进行 hash，算得一个整数索引值，然后对位数组长度进行取模运算得到一个位置，每个 hash 函数都会算得一个不同的位置，再把位数组的这几个位置都置为 1，就完成了 add *** 作。
向布隆过滤器询问 key 是否存在时，跟 add 一样，也会把 hash 的几个位置都算出来，看看位数组中这几个位置是否都为 1，只要有一个位为 0，那么说明布隆过滤器中这个 key 不存在。如果这几个位置都是 1，并不能说明这个 key 就一定存在，而是极有可能存在，因为这些位被置为 1，可能是因为其他的 key 存在所致。如果这个位数组比较稀疏，判断正确的概率就会很大，如果这个位数组比较拥挤，判断正确的概率就会降低。

应用场景

• 爬虫系统中，对 URL 进行去重，已经爬过的页面就不用爬了。
• 新闻客户端每次推荐新内容时，去掉已经看过的内容。
• 邮箱系统的垃圾邮件过滤。

常用命令

• bf.add、bf.exists

• bf.madd、bf.mexists（批量 *** 作命令）

  127.0.0.1:6379> bf.add codehole user1 
  (integer) 1 
  127.0.0.1:6379> bf.add codehole user2 
  (integer) 1 
  127.0.0.1:6379> bf.add codehole user3 
  （integer) 1 
  127.0.0.1:6379> bf.exists codehole userl 
  (integer) 1 
  127.0.0.1:6379> bf.exists codehole user2 
  （integer) 1 
  127.0.0.1:6379> bf.exists codehole user3 
  (integer) 1 
  127.0 . 0.1:6379> bf.exists codehole user4 
  (integer) 0 
  127.0.0.1:6379> bf.madd codehole user4 users user6 
  1) (integer) 1 
  2) (integer) 1 
  3) (integer) 1 
  127.0.0.1:6379> bf.mexists codehole user4 users user6 user7 
  1) （integer) 1 
  2) （integer) 1 
  3) （integer) 1 
  4) （integer) 0