BloomFilter布隆过滤器的实现解决缓存击穿问题

谁借莪１个温暖的怀抱￠ 2024-04-19 15:08 72阅读 0赞

**什么是缓存的击穿**  
缓存穿透是指缓存和数据库中都没有的数据，缓存每次都无法命中，因为我们默认不会缓存null 值，导致用户访问 id=-1 这样的数据时，一直都无法命中，这时的用户很可能是攻击者，攻击会导致数据库压力过大。  
解决方法：  
A.在redis缓存null, 当它再次查询id = -i ，在缓存里面有值，可以不在访问数据库  
但是**缺点缓存了null 值**  
B.使用**BloomFilter**  
Bloom Filter是一个占用空间很小、效率很高的随机数据结构，它由一个bit数组和一组Hash算法构成。可用于判断一个元素是否在一个集合中，查询效率很高（1-N，最优能逼近于1）。  
在很多场景下，我们都**需要一个能迅速判断一个元素是否在一个集合中**  
1.**判断500w条（url）里面是否包含一个url地址；**  
2.**从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；**  
3.**将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉**

用户访问，先经过一个集合，集合里面有所有的数据标识，当集合里面有标识，代表数据库里面也有标识（判断一个数据在集合里面有没有）  
a.当集合里面有，缓存里面有，返回缓存的值  
b.缓存里面没有，查询数据库。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70]  
方案：  
1 .使用HashSet 的唯一唯一性，去重  
HashSet dataLabel = new HashSet();  
dataLabel.add();  
dataLable.add();  
当数据量很大时，它的内存占用大不大 ？非常大  
一个地址16字节，10亿即可达到上百G的内存。HashSet效率逼近O(1)，数据库就不谈效率了，不在一个数量级。  
2.将地址用MD5算法或其他单向映射算法计算后存入HashSet，无论地址多大，保存的只有MD5后的固定位数  
，占用空间小于存储完整信息，存在冲突的可能（非垃圾邮箱可能MD5后和某垃圾邮箱一样，概率低）  
3…布隆过滤器，将所有地址经过多个Hash算法，映射到一个bit数组  
所有地址经过Hash后映射到同一个bit数组，看清了，只有一个超大的bit数组，保存所有的映射，占用空间极小，冲突概率高。

大家知道，java中的HashMap有个扩容参数默认是0.75，也就是你想存75个数，至少需要一个100的数组，而且还会有不少的冲突。实际上，Hash的存储效率是0.5左右，存5个数需要10个的空间。算起来占用空间还是挺大的。  
而布隆过滤器就不用为每个数都分配空间了，而是直接把所有的数通过算法映射到同一个数组，带来的问题就是冲突上升，只要概率在可以接受的范围，用时间换空间，在很多时候是好方案。布隆过滤器需要的空间仅为HashMap的1/8-1/4之间，而且它不会漏掉任何一个在黑名单的可疑对象，问题只是会误伤一些非黑名单对象。

BoolmFilter  
初始化状态是一个全为0的bit数组  
数据存储的容器时bit 集合BitSet  
当容量很小，存储数据很多时，hash 容易碰撞，具体时计算处理的pos 值，一样了，导致的，通过增加hash 函数的个数来减少碰撞。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70 1]  
如何使用位集合来判断一个数据是否存在  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70 2]  
实现Boolmfilter  
public class BloomFilter \{

// 1 初始化一个位集合
    public static int length = Integer.MAX_VALUE;
    
    public static BitSet sets = new BitSet(length);
    
    // 准备hash  hash
    public static int hash_length = 5 ;
    public static int []sends = new int[] {17,19,29,31,37};
    public static HashFun []funs = new HashFun[hash_length];
    static {
    	for (int i = 0; i < hash_length; i++) {
    		funs[i] = new HashFun(sends[i]);
    	}
    }
    
    public static void add(String key) {
    	for (HashFun hashFun : funs) {
    		int hashCode = hashFun.hash(key); // 计算hash 函数
    		int pos  = hashCode & (length-1); // 映射在位集合上的位置
    		System.out.println("位置有："+ pos);
    		sets.set(pos, true);
    	}
    }
    
    public static boolean has(String key) {
    	for (HashFun hashFun : funs) {
    		int hashCode = hashFun.hash(key); // 计算hash 函数
    		int pos  = hashCode & (length-1); // 映射在位集合上的位置
    		if(!sets.get(pos)) {
    			return false ;
    		}
    	}
    	return true;
    }
    public static void main(String[] args) {
    	add("mayun");
    	System.out.println("----------------");
        add("mahuateng");
        if(has("mayun")) {
        	System.out.println("ok");
        }else {
        	System.out.println("error");
        }
        
        if(has("mahuateng")) {
        	System.out.println("ok");
        }
    }

public class HashFun \{

private int send ;
    
    public HashFun(int send) {
    	this.send = send ;
    }
    public int hash(String key) {
    	int h = 0;
    
    	char []value = key.toCharArray();
    
    	if (h == 0 && value.length > 0) {
    		char val[] = value;
    		for (int i = 0; i < value.length; i++) {
    			h = this.send  * h + val[i];
    		}
    	}
    	return h;
    }

\}  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4f3d9ffb396e4e529505a12310748342.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/306bf14577f149258d0f71629775d1fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/2ab4a7a97cc84facb7213cc200589cf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RwZjM3MzUyMQ_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f9d919862b11470481eeff6efecb0ac7.png