【分布式技术专题】分布式缓存优化之初探布隆过滤器的使用指南

这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战

布隆过滤器的思想

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。

Hash表的数据结构

不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

布隆过滤器的Hash算法

Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

纯Java实现的方案

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示例

xml复制代码<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>22.0</version>
</dependency>

csharp复制代码/**
 * 测试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击穿问题

kotlin复制代码@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";
}

资料参考

www.cnblogs.com/wuwuyong/p/…

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有