千万级数据去重其实并不复杂

痛定思痛。 2022-11-26 08:52 117阅读 0赞

之前曾经看过一句话觉得挺好，大概的意思就是不同的数据结构有不同的适用场景和优缺点，需要仔细权衡自己的需求之后妥善适用它们。感觉布隆过滤器的实现是正好印证了这句话。

### 一、原理 ###

布隆过滤器本质上是一种比较巧妙的概率型数据结构，用来告诉我们某个东西一定不存在或可能存在，特点是高效的插入和查询，但不支持删除。

布隆过滤器不保存数据本身，而是通过 K 个hash 函数来计算在 byte\[\] 数组中的存放位置，并把这些个位置置为 1。如果计算结果所有需要置起的位置对应的值都是0，则认为该值不存在，如果存在值为1的位置（表示该位置被其他数据设置过），则认为该值可能存在。所以相比List、Map这种数据结构，它更省内存，可以被用来处理数据过滤、黑名单、处理缓存穿透等问题。举个例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hzZjE1NzY4NjE1Mjg0_size_16_color_FFFFFF_t_70_pic_center]  
假设我们布隆过滤器长度为10，同时有3个hash函数，我们给定一个数据为”hello“，通过3个hash函数计算后得到位置分别为1，4，7，假设此时这三个位置上的值都为0，表明该数据不存在。给定另一个数据为”sun“，计算后得到位置为2，7，9，此时位置7已经被置为1，则认为该数据可能存在。可见，布隆过滤器的容错跟本身定义的容量和整体的数据量的大小有关，容量一定的情况下，数据量越大，出现误判的可能性越大。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hzZjE1NzY4NjE1Mjg0_size_16_color_FFFFFF_t_70_pic_center 1]  
对于布隆过滤器，Guava、Redis本身已经有实现，就不用重复去造轮子了。

### 二、基于Guava实现 ###

#### 2.1 添加依赖： ####

<dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>19.0</version>
    </dependency>

#### 2.2 增加两个配置项信息 ####

bloomFilter.elementSize=10000000 //布隆过滤器预估存放的最大值
    bloomFilter.errorProbability=0.0000001 //误判率

#### 2.3 对布隆过滤器做一个封装，方便操作数据： ####

public interface BloomFilterWrap { 
    
        boolean add(String info);
    
        boolean clear();
    }

#### 2.4 接口实现： ####

@Component
    public class RepeatFilterWrap implements BloomFilterWrap{ 
    
        @Value("${bloomFilter.elementSize}")
        private long elementSize;
        
        @Value("${bloomFilter.errorProbability}")
        private double errorProbability;
        
        private BloomFilter<String> bloomFilter;
    
        @PostConstruct
        private void init() throws Exception{ 
            initBloomFilter();
        }
    
        @Override
        public boolean add(String info) { 
            if(bloomFilter.mightContain(info)){ 
                return false;
            }
            bloomFilter.put(info);
            return true;
        }
    
        @Override
        public boolean clear() { 
            initBloomFilter();
            return true;
        }
    
        private void initBloomFilter(){ 
            bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), elementSize, errorProbability);
        }
    }

### 三、效果 ###

一千万条数据，误判率百万分之一，最后计算出来占用的内存只有40M。在公司实际项目中，存在着大量的黑名单在数据发送的时候需要被过滤，就采用了布隆过滤器和Redis配合校验，每次发送的时候会先判断数据是否存在布隆过滤器中，存在的话再去查Redis中是否存在，避免每次请求都去查Redis，效果还是很可观的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hzZjE1NzY4NjE1Mjg0_size_16_color_FFFFFF_t_70_pic_center 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hzZjE1NzY4NjE1Mjg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/4bfe40eeedf54d9e929a5f1bc2162829.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hzZjE1NzY4NjE1Mjg0_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/74f7a64ba5cb4a3bb4b1b404fc369be3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hzZjE1NzY4NjE1Mjg0_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/c92a9147e8c84b028a588bce92a9d9df.png