布隆过滤器的思想
如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。
Hash表的数据结构
不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
布隆过滤器的Hash算法
Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。
纯Java实现的方案
public class MyBloomFilter { /** * 一个长度为10 亿的比特位 */ private static final int DEFAULT_SIZE = 256 << 22; /** * 为了降低错误率，使用加法hash算法，所以定义一个8个元素的质数数组 */ private static final int[] seeds = {3, 5, 7, 11, 13, 31, 37, 61}; /** * 相当于构建 8 个不同的hash算法 */ private static HashFunction[] functions = new HashFunction[seeds.length]; /** * 初始化布隆过滤器的 bitmap */ private static BitSet bitset = new BitSet(DEFAULT_SIZE); /** * 添加数据 * * @param value 需要加入的值 */ public static void add(String value) { if (value != null) { for (HashFunction f : functions) { //计算 hash 值并修改 bitmap 中相应位置为 true bitset.set(f.hash(value), true); } } } /** * 判断相应元素是否存在 * @param value 需要判断的元素 * @return 结果 */ public static boolean contains(String value) { if (value == null) { return false; } boolean ret = true; for (HashFunction f : functions) { ret = bitset.get(f.hash(value)); //一个 hash 函数返回 false 则跳出循环 if (!ret) { break; } } return ret; } /** * 测试。。。 */ public static void main(String[] args) { for (int i = 0; i < seeds.length; i++) { functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]); } // 添加1亿数据 for (int i = 0; i < 100000000; i++) { add(String.valueOf(i)); } String id = "123456789"; add(id); System.out.println(contains(id)); // true System.out.println("" + contains("234567890")); //false } } class HashFunction { private int size; private int seed; public HashFunction(int size, int seed) { this.size = size; this.seed = seed; } public int hash(String value) { int result = 0; int len = value.length(); for (int i = 0; i < len; i++) { result = seed * result + value.charAt(i); } int r = (size - 1) & result; return (size - 1) & result; } } 复制代码
Redis实现布隆过滤器
布隆过滤器介绍
布隆过滤器是一个很长的二进制向量和一系列随机映射函数，适用于判断某个数据在集合中是否存在，会存在误识别。
- 优点是空间效率和查询时间都比一般的算法要好的多
- 缺点是有一定的误识别率和删除困难。
布隆过滤器使用场景
客户端--布隆过滤器(hashmap)-redis缓存--DB数据库
- 在程序启动时，将redis的所有key先缓存预热(加载)到布隆过滤器中，也可以用hashmap，但布隆过滤器的性能会比hashmap快很多。
- 客户端请求的时候，先经过布隆过滤器，判断key是否存在，不存在的话，直接返回，可以解决redis的穿透和击穿。
- 布隆过滤器误判经过redis里，也不会造成原先大批量的涌入，这是可以接受的
- 如果redis的key有所变更，让布隆过滤器重新缓存预热，可解决删除问题
布隆过滤器存在的问题
误判
- Jarye2本身在二进制向量表中不存在，由于hash值和其他碰撞，导致以为存在。
- 解决方式： 把误判概率设置的足够小，但会导致向量表会大很多。
删除困难
加入把Jarye2删了，会把向量地址8 13的值设置为0，导致原先应该命中的Jarye1无法命中
**解决方式：**缓存重新预热。
布隆过滤器demo示例
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>22.0</version> </dependency> 复制代码
/** * 测试demo */ public class BlongTest { /** * 在布隆中存放100万条数据 */ private static Integer size = 1000000; public static void main(String[] args) { /** * 最后参数为误判率，必须要>0.0 * 误判率是3% 100W的数据，二巷数组长度为730W * 误判率是1% 100W的数据，二巷数组长度为960W * 综合效率和准确率，建议值是1% * */ BloomFilter<Integer> integerBloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.01); for (int i = 0; i < size; i++) { integerBloomFilter.put(i); } // 从布隆中查询数据是否存在 ArrayList<Integer> strings = new ArrayList<>(); for (int j = size; j < size + 10000; j++) { if (integerBloomFilter.mightContain(j)) { strings.add(j); } } System.out.println("误判数量:" + strings.size()); } } 复制代码
基于布隆过滤器解决Redis击穿问题
@RequestMapping("/getOrder") public OrderEntity getOrder(Integer orderId) { if (integerBloomFilter != null) { if (!integerBloomFilter.mightContain(orderId)) { System.out.println("从布隆过滤器中检测到该key不存在"); return null; } } // 1.先查询Redis中数据是否存在 OrderEntity orderRedisEntity = (OrderEntity) redisTemplateUtils.getObject(orderId + ""); if (orderRedisEntity != null) { System.out.println("直接从Redis中返回数据"); return orderRedisEntity; } // 2. 查询数据库的内容 System.out.println("从DB查询数据"); OrderEntity orderDBEntity = orderMapper.getOrderById(orderId); if (orderDBEntity != null) { System.out.println("将Db数据放入到Redis中"); redisTemplateUtils.setObject(orderId + "", orderDBEntity); } return orderDBEntity; } @RequestMapping("/dbToBulong") public String dbToBulong() { List<Integer> orderIds = orderMapper.getOrderIds(); integerBloomFilter = BloomFilter.create(Funnels.integerFunnel(), orderIds.size(), 0.01); for (int i = 0; i < orderIds.size(); i++) { integerBloomFilter.put(orderIds.get(i)); } return "success"; } 复制代码
