布隆过滤器的那点事

编程入门 行业动态 更新时间:2024-10-24 01:57:16

布隆<a href=https://www.elefans.com/category/jswz/34/1771166.html style=过滤器的那点事"/>

布隆过滤器的那点事

文章目录

  • 布隆过滤器-Bloom Filter
    • 是什么
    • 为什么用它
      • 有哪些实践
    • 如何使用
      • 代码
      • 运行结果
      • 代码源码分析
      • 别人怎么用

布隆过滤器-Bloom Filter

学习前经典3问,what,why,how;它是什么,为什么用它,怎么用它

是什么

布隆过滤器是一个节省空间的概率型数据结构。设计目的是为了判断一个元素是否在一个集合中。结果只有两种,1是可能存在,2是一定不存在。参考wiki

  • 执行流程

前置知识:
1.比特数组每一个位置元素只可能是0或者1,而且布隆过滤器将数据结构都私有化,无法外部访问;
2.哈希函数可以选用murmur3,md5,sha1,crc等,可参考Hashing类;

【插入】对每一个输入依次执行k个哈希函数,并将结果映射到[0,m)上,得到k个值,这k个值对应比特数组的索引位,然后我们将这k个值插入到比特数组中对应的位置,即将默认的0或者已经修改成1的值变更为1。
【查询】对每一个输入一次执行k个哈希函数,并将结果映射到[0,m)上,得到k个值,这k个值对应比特数组的索引位,依次检查这k个值对应比特数组保存的值,全是1返回true,否则返回false。

查询存在误判,而且随着比特数组越来越满,误判概率也越来越大;


  • 误判率Ffp
    误判率(false positive probability)=判断错误/预测总数,布隆过滤器有一个可预测的误判断率计算
Pfp ≈ (1 - e^{-kn/m})^k
  • 比特数组长度m
    布隆过滤器的长度m可以根据给定或者期望的误判率FFP和预估添加的元素个数n计算得到
m = - (n·lnPfp) / ((ln2)^2)
  • hash函数的个数k
    哈希函数的格式可以通过比特数组长度和预估数据量进行估计
k = ln2 * (m / n)


目前公司日志量级激增,发现是由于大量异常访问导致,所以需要添加一个uid的黑名单过滤,估计黑名单有1千万个uid,如果过滤不完全可以后面再数据处理。要求误判率在0.1以下。
已知:

n = 1 * 10^7;
Ffp = 0.1

求解:

m = - (1 * 10^7 * ln0.1) / (ln2^2) ≈ 5 * 10^7;
k = ln2 * (5 * 10^7 / 1 * 10^7) = 3.5 = 4

为什么用它

  1. 优点是空间效率和查询时间都比一般的算法要好的多;
  2. 缺点是有一定的误识别率,而且删除困难(Counting_Bloom_filter可以);
  3. 实际应用中基本也是实时分桶来处理布隆过滤器(既可以放在本地内存也可以放在redis等内存系统);
  4. 可以根据输入的特性,针对性的设计hash函数,可优化性能;

有哪些实践

这些实践都有一个共同的特点,那就是数据量大但是对准确性有一定的容忍度

  1. 大数据中广告等业务对DAU等准确性要求不是很高的实时统计场景;
  2. 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;
  3. URL去重或者黑名单系统;
  4. 缓解缓存穿透的问题,减少没必要的Redis或数据库查询请求;
  5. Medium使用布隆过滤器避免推荐给用户已经读过的文章

缓存穿透:大量本身就无数据的请求越过缓存(即缓存没有命中),直接请求数据库,而我们添加布隆过滤器相当于是在缓存请求前面加了一个筛子,将肯定不存在的请求直接过滤掉,缓解缓存穿透引起的压力

如何使用

1.布隆过滤器有很多实现和优化,由Google开发著名的Guava库就提供了布隆过滤器的实现。在基于Maven的Java项目中要使用Guava提供的布隆过滤器,只需要引入以下依赖(可以从maven repository中查找稳定的依赖):

<!-- .google.guava/guava -->
<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>28.2-jre</version>
</dependency>

代码

public static void main(String[] args) {// 创建布隆过滤器// Funnels是如何计算哈希值的抽象,即如何根据输入object将其转换为hashcode,可自定义也可使用内置,自定义自己实现funnel方法即可BloomFilter<String> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), 10000, 0.01);// 将数据通过单点的方式添加,也可批量添加,比如布隆过滤器重构时for (int i = 0; i < 10000; i++) {// 添加一个元素可查看BloomFilterStrategies.put方法bf.put(i + "common log body");}// 统计一下确定存在的数据是否存在误判int wrongJudge = 0;for (int i = 0; i < 10000; i++) {// 对于确定存在的,如果判断不存在即为误判if (!bf.mightContain(i + "common log body")) wrongJudge++;}System.out.println("全部都是确定存在,判断错误的个数: " + wrongJudge);// 统计一下确定不存在的数据的误判数量int wrongJudge1 = 0;for (int i = 10000; i < 20000; i++) {// 对于确定不存在的,如果判断存在即为误判if (bf.mightContain(i + "common log body")) wrongJudge1++;}System.out.println("全部都是确定不存在,判断错误的个数: " + wrongJudge1);
}

运行结果

查看运行结果可以看到,真实误判率=110/10000=0.011,和估计的误判率相差无几

全部都是确定存在,判断错误的个数: 0
全部都是确定不存在,判断错误的个数: 110

代码源码分析

1.创建布隆过滤器,根据之前的公式计算估计的比特数组长度和哈希函数的个数

/** 创建布隆过滤器,需要参数funnel+strategy,expectedInsertions,fpp,numBits,numHashFunctions */
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {// 根据预估数据量n和误判率Ffp估计比特数组的长度m// (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));long numBits = optimalNumOfBits(expectedInsertions, fpp);// 根据预估数据量n和比特数组的长度m估计哈希函数的个数k,如果是小数,四舍五入取整// Math.max(1, (int) Math.round((double) m / n * Math.log(2)));int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);// 根据计算结果创建布隆过滤器return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);

2.向布隆过滤器中添加元素
BloomFilterStrategies.put

public <T> boolean put(T object, Funnel<? super T> funnel, int numHashFunctions, LockFreeBitArray bits) {// 比特数组的长度long bitSize = bits.bitSize();// 根据规则计算哈希值long hash64 = Hashing.murmur3_128().hashObject(object, funnel).asLong();int hash1 = (int) hash64;int hash2 = (int) (hash64 >>> 32);// 无符号右移32位boolean bitsChanged = false;for (int i = 1; i <= numHashFunctions; i++) {// 这里根据哈希值模拟多个哈希函数的结果,// 并不是之前想的k个哈希函数分别作用输入的key,得到k个索引值int combinedHash = hash1 + (i * hash2);// Flip all the bits if it's negative (guaranteed positive number)if (combinedHash < 0) {combinedHash = ~combinedHash;}bitsChanged |= bits.set(combinedHash % bitSize);}return bitsChanged;
}

3.检查布隆过滤器是否含有某元素
BloomFilterStrategies.mightContain
流程和添加元素是一样,只是将set方法换成了get方法,只要有一个不存在即返回false

别人怎么用

  • 大数据实时日活计算之Bloom Filter(58同城)

在上一个版本判断用户是否存在时,使用多个位置存储元素,就会有多次需要访问Redis;为了减少对Redis访问;可以看到,Bloom Filter使用的多个hash算出的每个位置,其实对应一个二进制数,所以我们只需把这个二进制数据转化十进制,然后根据这数字所在位置是否为1来判断用户是否存在,这样只需要访问redis一次即可(需要注意这个值大小是否越界)

更多推荐

布隆过滤器的那点事

本文发布于:2024-02-11 17:12:37,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1682193.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:过滤器   那点

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!