redis布隆过滤器

发布于:2021-12-07 16:52:30

布隆过滤器
定义

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。


用处

布隆过滤器可以用于检索一个元素是否在一个集合中。具体使用有:


    网页爬虫对URL的去重,避免爬取相同的URL地址

    反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(同理,垃圾短信)

    缓存穿透,将所有可能存在的数据缓存放到布隆过滤器中,当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉


关于缓存穿透:


我们*时为了优化业务查询效率,通常会选择诸如redis一类的缓存, 数据查询时如果缓存有则直接通过缓存拿取,没有或者key过期的话,则去找数据库. 找到之后再把数据加入到缓存. 如果有这样的一个场景,有用户大量请求不存在的数据id, 这个时候, 因为缓存


没有,则统统全甩个数据库,这样很可能导致数据库宕掉.同时数据全都直接由持久层获得,?缓存命中率参数失去了意义,缓存也失去了意义.这类情况,称之为缓存穿透.


优点

它的优点是空间效率和查询时间都比一般的算法要好的多


缺点

它的缺点是有一定的误识别率和删除困难,但是瑕不掩瑜,他的优点足以让我们选择它作为提高查询性能的工具.


原理

布隆过滤器内部维护一个全为0的bit数组,需要说明的是,布隆过滤器有一个误判率的概念,误判率越低,则数组越长,所占空间越大。误判率越高则数组越小,所占的空间越小。


因为是bit数组,不是0 就是 1 , 这里我们初始化一个16位全0的数组:



这里为简化情况便于理解,我们设定hash函数个数为3 ,分别为?hash1(),hash2(),hash3()


bit数组长度arrLength为16位


对数据 data1, 分别使用 三个函数对其进行hash, 这里举例hash1(), 其他两个都是相同的


hashX(data1),通过hash算法和二进制操作, 然后? 处理后的哈希值 % arrLentgh,得到在数组的下标?,假设 下标 = 3,


如图我们将数组下标置为1:



同理,假设 3个函数处理完后如下图:



这样,花费很少的空间,就能够存储这条数据的存在情况, 当同样的数据请求过来,因为hash函数的特性, 三个函数hash过后,


通过判断三个比特位是否都是1,就可知道是否是同一条数据(???)


那么,情况真的这么简单吗?


其实,布隆过滤器有这样一个特性,那就是: 如果所有位都重复不代表是重复数据,如果有哪怕一位不重复,则肯定不是重复数据


因为hash值相同,不一定是相同数据,这个好理解吧?


而hash值不同,肯定不是相同数据. 因此,我们知道,布隆过滤器对于是否重复的判断,是有着误判率的.这一点我们需要了解.


实现

实现方式1:? 谷歌guaua框架(这方面请读者自行百度一下)


实现方式2: 借助redis


代码如下:


package com.example.demo.test;

import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;
import lombok.AllArgsConstructor;
import lombok.Data;
import redis.clients.jedis.Jedis;

import java.nio.charset.Charset;
import java.util.HashMap;
import java.util.Map;


/**
* redis布隆过滤器 (布隆过滤器规则: 如果所有位都重复不代表是重复数据,如果有哪怕一位不重复,则肯定不是重复数据)
*


* 新增数据处理后id填充布隆过滤器(得HASH,设置bitmap的位) ->
* 当新的请求来对比id , 看看是不是能在布隆过滤器中找到重复数据 ->
* true:判定为重复数据则进缓存找,如果没有,则是系统误判, 此时进入数据库
* false: 判定为非重复数据则直接进数据库
*/

public class RedisBloomFilter {
static final int expectedInsertions = 100;//要插入多少数据
static final double fpp = 0.01;//期望的误判率

//bit数组长度
private static long numBits;

//hash函数数量
private static int numHashFunctions;

private static Jedis jedis = new Jedis("127.0.0.1", 6379);
private static Map map = new HashMap<>();
static {
numBits = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
//数据模拟0(对象,需要用到序列化知识,篇幅过长,大家自己尝试一下)
//map.put("10000001", new Goods("10000001","雕牌洗衣粉",6.25,"洗衣粉" ));
//map.put("10000002", new Goods("10000002","小米空调",3006,"小米空调" ));
//map.put("10000003", new Goods("10000003","任天堂switch",1776.99,"任天堂switch" ));
//map.put("10000004", new Goods("10000004","联想笔记本电脑",6799,"联想笔记本电脑" ));

//数据模拟1(这里只缓存价格)
map.put("10000001", 6.25);
map.put("10000002", 3006);
map.put("10000003", 1776.99);
map.put("10000004", 6799);
}

public static void main(String[] args) {

//模拟入缓存的数据
map.forEach((k,v)->{
jedis.set(k, String.valueOf(v));
long[] indexs = getIndexs(String.valueOf(k));
for (long index : indexs) {
jedis.setbit("codebear:bloom", index, true);
}

});

//模拟用户请求的数据
String userInput1 = "10000001";
String userInput2 = "10000005";
String[] arr = {userInput1, userInput2};
for (int j = 0; j < arr.length; j++) {
boolean repeated = true;
long[] indexs = getIndexs(String.valueOf(arr[j]));
for (long index : indexs) {
Boolean isContain = jedis.getbit("codebear:bloom", index);
if (!isContain) {
System.out.println(arr[j] + "肯定没有重复!");
repeated = false;
//从数据库获取数据
String retVal = getByDb(arr[j]);
System.out.println("数据库获取到的数据为"+retVal);
break;
}
}
if (repeated) {
System.out.println(arr[j] + "有重复!");
//尝试从缓存获取
String retVal = getByCache(arr[j]);
if (retVal == null) {
//从数据库获取
retVal = getByDb(arr[j]);
System.out.println("数据库获取到的数据为"+retVal);
break;

}
System.out.println("缓存获取到的数据为"+retVal);

}
}

}


/**
* 从缓存获取数据
*/
public static String getByCache(String key){
return jedis.get(key);
}

/**
* 从数据库获取数据
*/
public static String getByDb(String key){
//从数据库获取数据逻辑没有实现
return "";
}

/**
* 根据key获取bitmap下标
*/
private static long[] getIndexs(String key) {
long hash1 = hash(key);
long hash2 = hash1 >>> 16;
long[] result = new long[numHashFunctions];
for (int i = 0; i < numHashFunctions; i++) {
long combinedHash = hash1 + i * hash2;
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
result[i] = combinedHash % numBits;
}
return result;
}

private static long hash(String key) {
Charset charset = Charset.forName("UTF-8");
return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong();
}

//计算hash函数个数
private static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}

//计算bit数组长度
private static 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)));
}
}

?

相关推荐

最新更新

猜你喜欢