综合技术

预防缓存击穿-布隆过滤器

微信扫一扫,分享到朋友圈

预防缓存击穿-布隆过滤器
0

为什么使用布隆过滤器

  • 布隆过滤器是用来判断一个元素是否出现在给定集合中的重要工具,具有快速,比哈希表更节省空间等优点,而缺点在于有一定的误识别率

  • 布隆过滤器(bloom filter)是Google Guava类库里面的组件

  • 当代换联网环境下使用缓存的公司可说遍地都是大家都知道使用缓存就是为了缓存一些冷数据以减少数据库压力

  • 查询一些缓存不存在的数据 透过缓存直接查询数据库

  • 服务报错

布隆过滤器代码实现

  • 代码实现

    package com.f.fmodules.fuser.bloom;
    
        import com.google.common.base.Charsets;
        import com.google.common.hash.BloomFilter;
        import com.google.common.hash.Funnels;
    
        import java.util.*;
    
        public class BloomFilterDemo {
    
            public static void main(String[] args) {
                final int count = 500000;
                List<String> stringList = new ArrayList<>(count);
                Set<String> stringSet = new HashSet<>();
                //创建布隆过滤器 初始化过滤器数据
                BloomFilter<String> bloomString = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),count);
                for (int i =0;i< count;i++){
                    String id = UUID.randomUUID().toString();
                    stringList.add(id);
                    stringSet.add(id);
                    bloomString.put(id);
                }
                int wrong = 0;
                int right = 0;
                for (int i =0;i< count; i++) {
                    String checkString = i % 100 == 0 ? stringList.get(i) : UUID.randomUUID().toString();
                    //布隆过滤器 进过hash算法和byte数组 校验是否存在于集合中
                    if (bloomString.mightContain(checkString)){
                        //校验是否误判
                        if (stringSet.contains(checkString)){
                            right++;
                        }else{
                            wrong++;
                        }
                    }
                }
                System.out.println("50万测试数据-->共抵挡: "+(count - wrong - right)+"次非法入侵"+"    误判"+wrong);
            }
        }
  • 运行结果

  • 为什么会有14721次误判呢 咱们跟进源码进行深入探索

    深入源码可发现 误判率在百分之三的情况下 有300多万个byte数组 会进行5次hash算法进行判断数据是否存在已知数据中

  • 初始化布隆过滤器时设置误判率为0.01

    //创建布隆过滤器 初始化过滤器数据
        BloomFilter<String> bloomString = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),count,0.001);
  • debug深入源码

    此时发现误判率设置为百分之一的情况下 byte数组达到七百多万 而需要进行的hash算法次数达到十次

  • 查看运行结果

    结果可看出 误判率为百分之一的情况下 5000次正确访问 只有500多次误判(并不是设置的误判率越小越好 误判率越小 需要进行hash计算次数越多消耗资源越多)

阅读原文...

微信扫一扫,分享到朋友圈

预防缓存击穿-布隆过滤器
0
简书

魅族16s价格提前泄露:3398元起售 这价格你觉得香吗?

上一篇

途家民宿发布"一体两翼"新战略 全面进军短租服

下一篇

评论已经被关闭。

插入图片

热门分类

往期推荐

预防缓存击穿-布隆过滤器

长按储存图像,分享给朋友