郑州哪家做网站便宜,贵金属交易平台,温州网站 公司,陕西住房城乡建设网站目录 布隆过滤器介绍
布隆过滤器的落地应用场景
高并发处理
多个过滤器平滑切换
分析总结 布隆过滤器介绍
布隆过滤器#xff08;Bloom Filter#xff09;是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是…目录 布隆过滤器介绍
布隆过滤器的落地应用场景
高并发处理
多个过滤器平滑切换
分析总结 布隆过滤器介绍
布隆过滤器Bloom Filter是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
它的优点是空间效率和查询时间都比一般的算法要好的多缺点是有一定的误识别率和删除困难。
什么业务场景需要使用这个布隆过滤器呢我个人觉得是对误判数据不敏感。比如在一个质检系统中客服人员对重复的录音是非常敏感的至于少了一些录音对他们来说是无所谓的。
刚刚好我们使用布隆过滤器对录音文件名进行过滤布隆过滤器返回true的时候我们把这部分录音给丢弃掉返回false的时候这部分数据就入库。而布隆过滤器返回false的时候说明这个数据是100%不存在的满足我们的应用场景。
布隆过滤器的落地应用场景
过滤代码
package com.tml.mouseDemo.service;import lombok.extern.slf4j.Slf4j;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import org.springframework.util.StringUtils;import javax.annotation.PostConstruct;
import java.time.Duration;/*** 分布式布隆过滤器的实现*/
Service
Slf4j
public class BloomFilterService {Autowiredprivate RedissonClient redissonClient;private RBloomFilter bloomFilter;PostConstructpublic void init() {//参数布隆过滤器的名字bloomFilter redissonClient.getBloomFilter(repeatAudioFileName);// 初始化布隆过滤器 预计数据量 误判率boolean b bloomFilter.tryInit(50000L, 0.03);log.info(repeatAudioFileName bloomFilter tryInit :{}, b);}public boolean checkFileNameRepeat(String audioFileName) {if (!StringUtils.hasText(audioFileName)) {throw new NullPointerException(audioFileName is empty);}//通过setNx的原子操作保证在多个布隆过滤器之间有一个平滑的过度boolean setIfAbsent redissonClient.getBucket(audioFileName).setIfAbsent(1, Duration.ofHours(1));if (!setIfAbsent) {log.info(this file is repeat!);return true;}boolean contains bloomFilter.contains(audioFileName);if (!contains) {boolean add bloomFilter.add(audioFileName);log.info(checkFileNameRepeat not contain:{} add:{}, audioFileName, add);//添加失败说明过滤器中已经存在这个元素了return !add;}return true;}}代码说明
高并发处理
contains()和add()是两个操作在多线程并发条件下需要结合这两个方法的返回值来综合判断是不是布隆过滤器包含这个元素。
多个过滤器平滑切换
setIfAbsent()这个操作是一个更加严谨的操作考虑到实际场景中是有多个布隆过滤器的在第一个布隆过滤器和第二个布隆过滤器进行切换的时候怎么做到平滑的切换呢
比如我们的应用场景中每天都会创建一个布隆过滤器而录音的数据是源源不断的推送过来的但是我们录音数据有一个特点是相同的录音的数据可能会多次推送并且多次的最大间隔不会超过1小时
假设repeatAudioFileName-20240206这个过滤器中已经包含了某个录音文件A刚刚好时间到了20230207这天需要重新创建布隆过滤器在repeatAudioFileName-20240207这个过滤器中恰好又有相同的文件进来了需要判断在新的过滤器中刚好没有这个文件这个时候又会将录音A文件入库这个就是业务异常了。 优化后的方案如下 优化的方案的代码就是如上
对应的压测代码也发一下 Testpublic void testRedis() throws InterruptedException {int threadSize 100;String fileName sagfdsfgewfgdsghf25870.mkv;long start System.currentTimeMillis();CyclicBarrier cyclicBarrier new CyclicBarrier(threadSize);CountDownLatch countDownLatch new CountDownLatch(threadSize);for (int i 0; i threadSize; i) {new Thread(() - {try {cyclicBarrier.await();boolean b bloomFilterService.checkFileNameRepeat(fileName);log.info(checkFileNameRepeat----------:{}, b);} catch (Exception e) {e.printStackTrace();} finally {countDownLatch.countDown();}}, repeat_test_ i).start();}countDownLatch.await();long end System.currentTimeMillis();log.info(start:{}-- cost:{} ms, start, (end - start));} 分析总结
布隆过滤器有对应的优缺点是不是使用你们的业务场景需要想清楚。上面的案例中之所以不用数据库的唯一约束是因为我们使用了sharding-jdbc分库分表相同的文件名的数据对应的订单id不一样也不是在一个表中不好控制。
顺便说一下布隆过滤器的应用场景还是很广泛的在以太坊ETH底层实现中就用了布隆过滤器。
