博客

定义

布隆过滤器是由Burton Howard Bloom大佬在1970年提出的一种概念。由一个很长的二进制数组和一些哈希函数所构成。

原理

对于一个元素，在添加是先通过一些哈希函数计算出特定的值，在根据这些值为下标在二进制数组里面找到对应的bit位，把位里的值从0变为1。当验证一个元素是否存在时，也是先通过这些哈希函数计算对应的值，根据这些值为数组的下标查找对应的bit位，如果所有的bit位都为1，那么说明这个元素可能存在，如果有一个或者多个bit位的值为0，那么这个元素一定不存在。

布隆过滤器实验

guava布隆过滤器使用

• 首先我们需要引入谷歌guava包，我这里使用maven进行项目jar依赖

      <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>20.0</version>
            <scope>compile</scope>
        </dependency>

• 根据guava提供的布隆过滤器，我们需要初始化布隆过滤器参数和一些静态方法提供使用即可。

/**
 * 使用谷歌guava布隆过滤器
 * 布隆过滤器-将验证的数据放在jvm-内存中
 *
 * @author zrh
 */
public class LocalBloomFilter {

    /**
     * 创建布隆过滤器
     * 后面两个参数：
     *      预估插入数据数量
     *      允许数据误差率
     */
    private final static BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), 10000000, 0.00000001);

    /**
     * 检索元素是否在布隆过滤器中
     *
     * @param id
     * @return
     */
    public static Boolean match(String id) {
        return bloomFilter.mightContain(id);
    }

    /**
     * 往布隆过滤器过滤器添加元素
     *
     * @param id
     */
    public static void put(String id) {
        bloomFilter.put(id);
    }
}

• 初始化布隆过滤器后，我们就可以填充数据到布隆过滤器里。

/**
 * 初始化数据到布隆过滤器
 *
 * @author zrh
 */
@Order
@Slf4j
@Configuration
public class BloomFilterConfig implements InitializingBean {

    /**
     * 初始化数据到布隆过滤器
     */
    @Override
    public void afterPropertiesSet() {
        // 模拟的数据
        List<Integer> list = Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9);
        log.info("加载数据到布隆过滤器,size:{}", list.size());
        if (!CollectionUtils.isEmpty(list)) {
            list.stream().forEach(item -> {
                LocalBloomFilter.put(item + "");
            });
        }
    }
}

• 我们可以写一个拦截器针对性进行拦截过滤。

/**
 * 布隆过滤器 - 拦截过滤
 *
 * @author zrh
 */
@Slf4j
@Component
public class BloomFilterInterceptor extends HandlerInterceptorAdapter {

    /**
     * 自定义拦截过滤方法
     *
     * @param request
     * @param response
     * @param o
     * @return
     * @throws IOException
     */
    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object o) throws IOException {
        // 如果是OPTIONS则结束请求
        if (HttpMethod.OPTIONS.toString().equals(request.getMethod())) {
            response.setStatus(HttpStatus.NO_CONTENT.value());
            return true;
        }
        response.setHeader("Content-type", "application/json;charset=UTF-8");
        // 获取参数
        String id = request.getParameter("id");
        if (id == null) {
            String currentUrl = request.getRequestURI();
            PathMatcher matcher = new AntPathMatcher();
            Map<String, String> pathVariable = matcher.extractUriTemplateVariables("/filter/product/{id}", currentUrl);
            id = pathVariable.get("id");
        }

        log.info("进入布隆过滤器拦截器。。。");
        // 使用guava布隆过滤器进行拦截过滤
        if (LocalBloomFilter.match(id)) {
            return true;
        }

        // 不在本地布隆过滤器当中，直接返回验证失败。设置响应头
        response.setHeader("Content-Type", "application/json");
        response.setCharacterEncoding("UTF-8");
        String result = new ObjectMapper().writeValueAsString("布隆过滤器拦截，参数不存在：" + id);
        response.getWriter().print(result);
        return false;
    }
}

• 写一个可以被拦截过滤的controller方法进行测试。
• 当输入一个存在布隆过滤器的元素时，可以请求通过
  
  
• 当输入一个不存在布隆过滤器的元素时，请求就被拦截了
  
  

redis隆过滤器使用

• 上述的布隆过滤器是使用谷歌guava包进行创建使用，是基于本地jvm内存存储数据，这样很明显不能用于分布式系统。
• 所以如果想要在分布式系统里使用布隆过滤器就需要整合redis进行使用。使用redis的setBit命令即可对对应key设置bit位，
• 首先我们需要自定义一个布隆过滤器处理器

/**
 * 算法过程：
 * 1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
 * 2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
 * 3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
 * 4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
 */
public class BloomFilterHelper<T> {
    private Long bitSize; // 二进制数组大小
    private int numHashFunctions; // hash函数个数
    private Funnel<T> funnel;
    /**
     * @param expectedInsertions 预估插入数据数量
     * @param fpp                允许数据误差率
     * @param funnel
     */
    public BloomFilterHelper(Long expectedInsertions, double fpp, Funnel<T> funnel) {
        this.funnel = funnel;
        bitSize = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
    }
    /**
     * 计算bit数组大小
     * @param n 预估插入数据数量
     * @param p 允许数据误差率
     * @return
     */
    private long optimalNumOfBits(long n, double p) {
        if (p == 0) p = Double.MIN_VALUE;
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
    /**
     * 计算hash函数个数
     * @param n 预估插入数据数量
     * @param m bit数组大小
     * @return
     */
    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
    /**
     * 计算元素的hash散列下标
     * @param value 元素
     * @return
     */
    public Long[] mightContain(T value) {
        Long[] longs = new Long[numHashFunctions];
        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);
        for (int i = 1; i <= numHashFunctions; ++i) {
            int combinedHash = hash1 + i * hash2;
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            longs[i - 1] = combinedHash % bitSize;
        }
        return longs;
    }
}

• 基于布隆过滤器处理器整合redis，初始化布隆过滤器实例和一些操作方法提供使用。

/**
 * 基于redis 配置布隆过滤器
 *
 * @author zrh
 */
@Configuration
public class BloomRedisService {

    @Autowired
    private StringRedisTemplate redisTemplate;

    /**
     * 初始化布隆过滤器实例
     */
    private static final BloomFilterHelper bloomFilterHelper = new BloomFilterHelper(10000000L, 0.01,
            (Funnel<String>) (from, into) -> into.putString(from, Charsets.UTF_8));

    /**
     * 添加初始数据到布隆过滤器
     *
     * @param key
     * @param value
     * @param <T>
     */
    public <T> void addByBloomFilter(String key, T value) {
        // 根据随机hash函数计算元素hash值
        Long[] mightContain = bloomFilterHelper.mightContain(value);
        // 对redis里的比特位进行赋值
        Arrays.stream(mightContain).forEach(o -> redisTemplate.opsForValue().setBit(key + value, o, true));
    }

    /**
     * 验证数据是否存在
     *
     * @param key
     * @param value
     * @param <T>
     * @return
     */
    public <T> Boolean includeByBloomFilter(String key, T value) {
        // 根据随机hash函数计算元素hash值
        Long[] mightContain = bloomFilterHelper.mightContain(value);
        // 判断是否
        return !Arrays.stream(mightContain).anyMatch(o -> !redisTemplate.opsForValue().getBit(key + value, o));
    }
}

• 添加基础数据到布隆过滤器

/**
 * 初始化数据到布隆过滤器
 *
 * @author zrh
 */
@Order
@Slf4j
@Configuration
public class BloomFilterConfig implements InitializingBean {

    /**
     * redis - key
     */
    public final static String BLOOM_STRING_FILTER = "bloom:string:filter:";

    @Autowired
    private BloomRedisService service;

    /**
     * 初始化数据到布隆过滤器
     */
    @Override
    public void afterPropertiesSet() {
        // 模拟的数据
        List<Integer> list = Lists.newArrayList(1, 2, 3, 4, 5, 6, 7, 8, 9);
        log.info("加载数据到布隆过滤器,size:{}", list.size());
        if (!CollectionUtils.isEmpty(list)) {
            list.stream().forEach(item -> {
//                LocalBloomFilter.put(item + "");
                service.addByBloomFilter(BLOOM_STRING_FILTER, item + "");
            });
        }
    }
}

• 在自定义拦截器中进行拦截过滤

/**
 * 布隆过滤器 - 拦截过滤
 *
 * @author zrh
 */
@Slf4j
@Component
public class BloomFilterInterceptor extends HandlerInterceptorAdapter {

    @Autowired
    private BloomRedisService bloomRedisService;

    /**
     * 自定义拦截过滤方法
     *
     * @param request
     * @param response
     * @param o
     * @return
     * @throws IOException
     */
    @Override
    public boolean preHandle(HttpServletRequest request, HttpServletResponse response, Object o) throws IOException {
        // 如果是OPTIONS则结束请求
        if (HttpMethod.OPTIONS.toString().equals(request.getMethod())) {
            response.setStatus(HttpStatus.NO_CONTENT.value());
            return true;
        }
        response.setHeader("Content-type", "application/json;charset=UTF-8");
        // 获取参数
        String id = request.getParameter("id");
        if (id == null) {
            String currentUrl = request.getRequestURI();
            PathMatcher matcher = new AntPathMatcher();
            Map<String, String> pathVariable = matcher.extractUriTemplateVariables("/filter/product/{id}", currentUrl);
            id = pathVariable.get("id");
        }

        log.info("进入布隆过滤器拦截器。。。");
        // 使用guava布隆过滤器进行拦截过滤
//        if (LocalBloomFilter.match(id)) {
//            return true;
//        }

        // 在redis中使用布隆过滤器
        if (bloomRedisService.includeByBloomFilter(BLOOM_STRING_FILTER, id)) {
            return true;
        }

        // 不在本地布隆过滤器当中，直接返回验证失败。设置响应头
        response.setHeader("Content-Type", "application/json");
        response.setCharacterEncoding("UTF-8");
        String result = new ObjectMapper().writeValueAsString("布隆过滤器拦截，参数不存在：" + id);
        response.getWriter().print(result);
        return false;
    }
}

• 最后基于redis实现的布隆过滤器和guava实现的布隆过滤器效果是一致的。

优缺点

优点

• 因为不存储元素本身，而是用bit位的形式存储数据，所以占用空间很小，且数据安全性有优势。
• 因为通过随机hash函数计算hash值，通过hash值为下标在bit数组中查找，时间复杂度是O(hash函数个数)，所以时间查找很快。

缺点

• 因为不同元素经过hash函数计算后可能会出现相同的hash值（hash碰撞），会导致不存在的元素也能通过布隆过滤器，所以有一定的误判率。
• 因为元素保存在bit位里（0不存在，1存在）。例如元素A经过hash计算后的下标是 1 5 8，元素B经过hash计算后的下标是2 6 8。如果这是需要把B元素删除那就需要把数组里下标为2 6 8的bit位变为0，但是元素A在下标8也存在。所以有hash碰撞的原因，对数据的删除很不友好。

使用场景

• 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询数据库，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到数据库。如果不在布隆器中，则直接响应返回。
• WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。
• 判断用户是否阅读过某视频或文章，当然会导致一定的误判，但不会让用户看到重复的内容。
• 利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

最后

• 这里分享一个关于腾讯视频中布隆过滤器使用的真实案例
  
  Now 直播发现页短视频瀑布流优化
  
• 针对布隆过滤器对删除数据很不友好的缺点，有一种叫做Counting Bloom Filter，里面维护了一个counter数组，里面存的就不是bit元素，这样用几倍的空间占用解决了布隆过滤器不能删除的缺点。
• 在真实的场景中二进制数组的长度非常长，进过不同的hash计算后，得出的下标在数组中的跨度可能会非常大，就是不连续值就会导致CPU命中率低，这是布隆过滤器实践场景中的性能瓶颈。
• 有一种性能更好也支持添加删除的过滤器叫布谷鸟过滤器。今天这里就不再多讲了，在后面的文章中我会介绍这种性能更好的布谷鸟过滤器，这里有个链接你们可以去看看布谷鸟过滤器的使用规则和原理
  
  布谷鸟哈希可视化
  
• 最后虚心学习，共同进步。-_-