Redis|redis原理之布隆过滤器（Bloom Filter） Redis|布隆过滤器

一、Redis现网常见问题解决
1.1、缓存穿透——常见于不规范的key
概念：访问一个不存在的key，缓存不起作用，请求会穿透到DB，流量大时DB会挂掉。
解决方案：

采用布隆过滤器（Bloom Filter，Redis自带），使用一个足够大的bitmap，用于存储可能访问的key，不存在的key直接被过滤；（推荐）
或者访问key未在DB查询到值，也将空值写进缓存，但可以设置较短过期时间。

1.2、缓存雪崩——常见于大量的key设置相同过期时间
概念：大量的key设置了相同的过期时间，导致在缓存在同一时刻全部失效，造成瞬时DB请求量大、压力骤增，引起雪崩。
解决方案：可以给缓存设置过期时间时加上一个随机值时间，使得每个key的过期时间分布开来，不会集中在同一时刻失效。
1.3、缓存击穿——常见于热点key
概念：一个存在的key，在缓存过期的一刻，同时有大量的请求，这些请求都会击穿到DB，造成瞬时DB请求量大、压力骤增。
解决方案：在访问key之前，采用SETNX（set if not exists）来设置另一个短期key来锁住当前key的访问，访问结束再删除该短期key。

二、布隆（bloom）过滤器原理
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
从简单的定义可以看出，使用布隆过滤器目的是为了优化元素查找的性能，不过布隆过滤器提升的是得到这个元素（key）的存在性的性能。
既然要解决上面的问题，那么我们就需要做存在性检查。

对于广大程序员来说，“判断一个值是否存在”这么一个问题，可能新手会说遍历（数组），老手们会直接抛下一句“哈希表呗”然后不屑的离开

假设有这么一个场景：
如果给我们20亿条交易数据，而且会不断的增加，在每次访问缓存或者数据库之前做一个存在性检查，最直接想到的可能是类似hashtable这样的数据结构，去存储每个交易的key，每次有新的交易进来，就加入一条新的记录，容量不够就扩容，每次有查询进来，就做一次查找操作，这样的设计在数据越来越大的时候，占用的空间会越来越大，假设我们使用mysql的 varchar(36) 做uuid，每一条有36个字节（36byte），20亿条数据需要消耗的内存是：
即使用hash去压缩每一个key，这个容量一直增长的特点似乎也没有很好的办法去避免。

文章图片

这时候布隆过滤器就上场了，那么布隆过滤器是怎么做的呢？

准备一个bit数组
准备k个hash函数，输入目标的key值和salt，输出一个int类型的hash值
每次有新的key值进入的时候，用这k个hash函数分别加密后得到k个hash值
对于第3步得到的每个hash值value，把bit数组中的第value个位赋值成1
每次有查询来的时候，对查询的目标也做k次hash得到k个value，如果k个value在bit数组中的值都是1，那么这个key的存在性就是true，如果有其中一个value的bit数组值不是1，存在性即为false
从上面的步骤可以知道，空间是可控的，假设是一个21亿多位长度的bit数组，理论上只有不到0.3Gb，时间和计算量也是可控的，但是取决于hash函数的效率。

用一个简单的图形来解释，就是这样：

文章图片

【Redis|redis原理之布隆过滤器（Bloom Filter）】特别注意：布隆过滤器说存在的key，不一定真的存在。但是布隆过滤器说不存在的key是一定不存在的。
因为相同的hash函数输入相同的key，得出的hash值一定是相同的。所以，布隆过滤器有误差，误差的数学公式可以参考这个知乎答案，它跟bit数组的大小，k的大小，元素的数量都有关，但是一个容量足够大的通用布隆过滤器，一般可以达到几千万个元素的误差率在万分之几的数量级，具体可以参考github上一个C++的实现。
误差在这里是完全可以容忍的，本身布隆过滤器就是为了拦截大部分无效的访问，偶尔漏过去几条是完全没问题的。
三、简单Java实现

这里从网上找了一个简单的java实现，为了学习和理解，并非是通用的过滤器。

hardcode了k的值为9，每个salt是一个素数，用于计算字符串的hash，bit数组的容量为0x7fffffff - 2.

这里使用的hash函数也并非是高性能，如果在真实场景可以使用MurmurHash或者Fnv算法。

package www.lxk.com; public class BloomFilter { private static int[] salts = { 3, 5, 7, 11, 13, 17, 19, 23, 29 }; // avoid VM error private static boolean[] bitMap = new boolean[Integer.MAX_VALUE - 2]; // refer to String.hashCode function // the salt/seed in JDK String class is 31, all the prime salt values less // then 31 could only generate Integer values public static int myHash(String s, int salt) { if (s == null || s.isEmpty()) throw new RuntimeException("empty string"); int h = 0; for (int i = 0; i < s.length(); i++) h = salt * h + s.charAt(i); // to prevent negative values return Integer.MAX_VALUE & h; } public BloomFilter() { for (int i = 0; i < Integer.MAX_VALUE - 2; i++) bitMap[i] = false; } public boolean contains(String target) { if (target == null || target.isEmpty()) return false; for (int salt : salts) if (!bitMap[myHash(target, salt)]) return false; return true; } public void put(String target) { if (target == null || target.isEmpty()) throw new RuntimeException("empty string"); for (int salt : salts) bitMap[myHash(target, salt)] = true; } public static void main(String[] args) { BloomFilter b = new BloomFilter(); for (int i = 0; i < 100000000; i++) { String s = "test" + i; b.put(s); } int count = 0; for (int i = 0; i < 100000000; i++) { String s = "test" + i; if (b.contains(s)) count++; } System.out.println(count); count = 0; for (int i = 0; i < 200000000; i++) { String s = "test" + i; if (b.contains(s)) count++; } System.out.println(count); } }

这里的main函数做了一次简单的测试，往过滤器里面提前写入100000000（一亿）个不一样的字符串，再去查询0到一亿编号和二亿编号的字符串，其中一亿之前的应该都是存在的，从一亿到二亿的字符串应该是全都不存在的。
Output：

文章图片

也就是说有46个误差，不论跟一亿还是二亿的基数比，这很显然是可以接受的。
总结：其实现实中Redis本身就有布隆过滤器的插件，可以直接配置使用，并不需要自己去实现，更需要关心的可能是不同数据规模下如何进行调优，Redis的布隆过滤器是可以制定error_rate的，一般来说指定的error_rate越小，需要的空间和计算量都会越大，需要通过一些性能测试去选择我们需要且可以接受的参数。
详细的信息和使用可以参考开源的redis bloom repo

参考：https://blog.csdn.net/weixin_37373020/article/details/99306145