深入理解redis——布隆过滤器BloomFilter 深入理解redis——布隆过滤器

1.布隆过滤器是什么
2.布隆过滤器的特点
3.布隆过滤器使用场景
4.布隆过滤器原理
5.布隆过滤器优缺点
6.布隆过滤器应用
7.总结
1.布隆过滤器是什么
redis的布隆过滤器其实有点像我们之前学习过的hyperloglog 深入理解redis——新类型bitmap/hyperloglgo/GEO ，它也是不保存元素的一个集合，它也不保存元素的具体内容，但是能判定这个元素是否在这个集合中存在（hyperloglog是判定集合中存在的不重复元素的个数）。
1）它是由一个初值都为零的bit数组和多个哈希函数构成，用来快速判断某个数据是否存在。
2）本质就是判断具体数据存不存在一个大的集合中。
3）布隆过滤器是一种类似set的数据结构，只是统计结果不太准确
2.布隆过滤器的特点
1）一个元素如果在布隆过滤器里判定结果为不存在，则一定不存在
2）一个元素在布隆过滤器里判定结果存在，则不一定存在（原理会在下面解释）
3）布隆过滤器可以添加元素，但是不能删除元素，删除元素会导致误判率增加。
4）误判只会发生在过滤器没有添加过的元素，对于已经添加过的元素不会发生误判。
3.布隆过滤器使用场景
1）解决缓存穿透的问题：
缓存穿透是什么：
一般情况下，我们在查询数据的时候，如果用到redis，那么先去查redis，如果缓存中没有，再去查数据库，如果数据库中也不存在，那么就发生了缓存穿透。
当发生缓存穿透的时候，可能会有大量的查询直击mysql，一定程度上会拖垮数据库。
解决方案：
1.1）给空key设置一个空value.
但是当大量空key出来的时候，也相当于查了很多次mysql，也可能会拖垮数据库。
1.2）使用布隆过滤器
把已存在的key保存在布隆过滤器中，相当于redis前面有一层布隆过滤器的保护。
当出现请求的时候：
1.2.1）先去查询布隆过滤器是否存在（如果布隆过滤器返回为不存在，那是一定不存在。）
1.2.2）如果存在，才去redis，甚至mysql查询，如果不存在，直接返回。
2）黑白名单的问题：
解决原理同上，把黑名单全部放入布隆过滤器，再进行过滤。
3）海量数据查找是否存在的问题都可以用布隆过滤器。（比如现有50亿个电话号码，和10万个电话号码，快速准确地判定号码是否存在。）
4.布隆过滤器原理
布隆过滤器使用了多个Hash函数和一个初始值都为0的bit大型数组构成。
add：
比如我们现在有一个对象obj1，它先用多个hash函数得到多个不同的值，再拿数组长度进行对这多个值取模得到多个位置，将这几个位置置为1，就完成了add操作。
query:
查询的时候，只要多个哈希函数算出来的下标其中有一位是0就代表这个key不存在，如果都是1，可能是存在，则可能遇上了哈希冲突（这就是为什么，布隆过滤器，无是一定无，有可能有）。

文章图片

为什么布隆过滤器不能删除：
如果布隆过滤器删除了一个元素，就是将某个对象的多个下标置为了0，就大概率会影响到别的元素，因为很可能多个元素共享了某一个下标，所以删除元素会导致误判率增加。
5.布隆过滤器优缺点
优点：高效地插入和查询，占用空间少
缺点：不能删除元素，存在误判。
6.布隆过滤器应用

public class RedissonBloomFilterDemo { public static final int _1W = 10000; //布隆过滤器里预计要插入多少数据 public static int size = 100 * _1W; //误判率,它越小误判的个数也就越少 public static double fpp = 0.03; static RedissonClient redissonClient = null; static RBloomFilter rBloomFilter = null; static { Config config = new Config(); config.useSingleServer().setAddress("redis://192.168.111.147:6379").setDatabase(0); //构造redisson redissonClient = Redisson.create(config); //通过redisson构造rBloomFilter rBloomFilter = redissonClient.getBloomFilter("phoneListBloomFilter", new StringCodec()); //初始化布隆过滤器 rBloomFilter.tryInit(size, fpp); // 1测试布隆过滤器有+redis有 rBloomFilter.add("10086"); redissonClient.getBucket("10086", new StringCodec()).set("chinamobile10086"); // 2测试布隆过滤器有+redis无 //rBloomFilter.add("10087"); //3 测试，都没有}public static void main(String[] args) { String phoneListById = getPhoneListById("10087"); System.out.println("------查询出来的结果： " + phoneListById); //暂停几秒钟线程 try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } redissonClient.shutdown(); }private static String getPhoneListById(String IDNumber) { String result = null; if (IDNumber == null) { return null; } //1 先去布隆过滤器里面查询 if (rBloomFilter.contains(IDNumber)) { //2 布隆过滤器里有，再去redis里面查询 RBucket rBucket = redissonClient.getBucket(IDNumber, new StringCodec()); result = rBucket.get(); if (result != null) { return "i come from redis: " + result; } else { result = getPhoneListByMySQL(IDNumber); if (result == null) { return null; } // 重新将数据更新回redis redissonClient.getBucket(IDNumber, new StringCodec()).set(result); } return "i come from mysql: " + result; } return result; }private static String getPhoneListByMySQL(String IDNumber) { return "chinamobile" + IDNumber; } }

7.总结
【深入理解redis——布隆过滤器BloomFilter】今天学习和总结了布隆过滤器，它是一种不保存数据，但是能判定数据是否在集合中存在的一种数据类型。