redis原理之布隆过滤器(Bloom Filter)

2023-10-15 07:10

本文主要是介绍redis原理之布隆过滤器(Bloom Filter),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、Redis现网常见问题解决

1.1、缓存穿透——常见于不规范的key

概念:访问一个不存在的key,缓存不起作用,请求会穿透到DB,流量大时DB会挂掉。

解决方案:

  • 采用布隆过滤器(Bloom Filter,Redis自带),使用一个足够大的bitmap,用于存储可能访问的key,不存在的key直接被过滤;(推荐)
  • 或者访问key未在DB查询到值,也将空值写进缓存,但可以设置较短过期时间。

1.2、缓存雪崩——常见于大量的key设置相同过期时间

概念:大量的key设置了相同的过期时间,导致在缓存在同一时刻全部失效,造成瞬时DB请求量大、压力骤增,引起雪崩。

解决方案:可以给缓存设置过期时间时加上一个随机值时间,使得每个key的过期时间分布开来,不会集中在同一时刻失效。

1.3、缓存击穿——常见于热点key

概念:一个存在的key,在缓存过期的一刻,同时有大量的请求,这些请求都会击穿到DB,造成瞬时DB请求量大、压力骤增。

解决方案:在访问key之前,采用SETNX(set if not exists)来设置另一个短期key来锁住当前key的访问,访问结束再删除该短期key。
 

二、布隆(bloom)过滤器原理

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难

从简单的定义可以看出,使用布隆过滤器目的是为了优化元素查找的性能,不过布隆过滤器提升的是得到 这个元素(key)的存在性的性能。

既然要解决上面的问题,那么我们就需要做存在性检查。

对于广大程序员来说,“判断一个值是否存在”这么一个问题,可能新手会说遍历(数组),老手们会直接抛下一句“哈希表呗”然后不屑的离开

 假设有这么一个场景:

如果给我们20亿条交易数据,而且会不断的增加,在每次访问缓存或者数据库之前做一个存在性检查,最直接想到的可能是类似hashtable这样的数据结构,去存储每个交易的key,每次有新的交易进来,就加入一条新的记录,容量不够就扩容,每次有查询进来,就做一次查找操作,这样的设计在数据越来越大的时候,占用的空间会越来越大,假设我们使用mysql的 varchar(36) 做uuid,每一条有36个字节(36byte),20亿条数据需要消耗的内存是:

即使用hash去压缩每一个key,这个容量一直增长的特点似乎也没有很好的办法去避免。

这时候布隆过滤器就上场了,那么布隆过滤器是怎么做的呢?

  1. 准备一个bit数组
  2. 准备k个hash函数,输入目标的key值和salt,输出一个int类型的hash值
  3. 每次有新的key值进入的时候,用这k个hash函数分别加密后得到k个hash值
  4. 对于第3步得到的每个hash值value,把bit数组中的第value个位赋值成1
  5. 每次有查询来的时候,对查询的目标也做k次hash得到k个value,如果k个value在bit数组中的值都是1,那么这个key的存在性就是true,如果有其中一个value的bit数组值不是1,存在性即为false
  6. 从上面的步骤可以知道,空间是可控的,假设是一个21亿多位长度的bit数组,理论上只有不到0.3Gb,时间和计算量也是可控的,但是取决于hash函数的效率

用一个简单的图形来解释,就是这样:

特别注意:布隆过滤器说存在的key,不一定真的存在。但是布隆过滤器说不存在的key是一定不存在的。

因为相同的hash函数输入相同的key,得出的hash值一定是相同的。所以,布隆过滤器有误差,误差的数学公式可以参考这个知乎答案,它跟bit数组的大小,k的大小,元素的数量都有关,但是一个容量足够大的通用布隆过滤器,一般可以达到几千万个元素的误差率在万分之几的数量级,具体可以参考github上一个C++的实现。

误差在这里是完全可以容忍的,本身布隆过滤器就是为了拦截大部分无效的访问,偶尔漏过去几条是完全没问题的。

三、简单Java实现

  • 这里从网上找了一个简单的java实现,为了学习和理解,并非是通用的过滤器。
  • hardcode了k的值为9,每个salt是一个素数,用于计算字符串的hash,bit数组的容量为0x7fffffff - 2.
  • 这里使用的hash函数也并非是高性能,如果在真实场景可以使用MurmurHash或者Fnv算法。
package www.lxk.com;public class BloomFilter {private static int[] salts = { 3, 5, 7, 11, 13, 17, 19, 23, 29 };// avoid VM errorprivate static boolean[] bitMap = new boolean[Integer.MAX_VALUE - 2];// refer to String.hashCode function// the salt/seed in JDK String class is 31, all the prime salt values less// then 31 could only generate Integer valuespublic static int myHash(String s, int salt) {if (s == null || s.isEmpty())throw new RuntimeException("empty string");int h = 0;for (int i = 0; i < s.length(); i++)h = salt * h + s.charAt(i);// to prevent negative valuesreturn Integer.MAX_VALUE & h;}public BloomFilter() {for (int i = 0; i < Integer.MAX_VALUE - 2; i++)bitMap[i] = false;}public boolean contains(String target) {if (target == null || target.isEmpty())return false;for (int salt : salts)if (!bitMap[myHash(target, salt)])return false;return true;}public void put(String target) {if (target == null || target.isEmpty())throw new RuntimeException("empty string");for (int salt : salts)bitMap[myHash(target, salt)] = true;}public static void main(String[] args) {BloomFilter b = new BloomFilter();for (int i = 0; i < 100000000; i++) {String s = "test" + i;b.put(s);}int count = 0;for (int i = 0; i < 100000000; i++) {String s = "test" + i;if (b.contains(s))count++;}System.out.println(count);count = 0;for (int i = 0; i < 200000000; i++) {String s = "test" + i;if (b.contains(s))count++;}System.out.println(count);}
}

这里的main函数做了一次简单的测试,往过滤器里面提前写入100000000(一亿)个不一样的字符串,再去查询0到一亿编号和二亿编号的字符串,其中一亿之前的应该都是存在的,从一亿到二亿的字符串应该是全都不存在的。

Output:


 
也就是说有46个误差,不论跟一亿还是二亿的基数比,这很显然是可以接受的。

总结:其实现实中Redis本身就有布隆过滤器的插件,可以直接配置使用,并不需要自己去实现,更需要关心的可能是不同数据规模下如何进行调优,Redis的布隆过滤器是可以制定error_rate的,一般来说指定的error_rate越小,需要的空间和计算量都会越大,需要通过一些性能测试去选择我们需要且可以接受的参数。

详细的信息和使用可以参考开源的redis bloom repo
 

参考:https://blog.csdn.net/weixin_37373020/article/details/99306145

这篇关于redis原理之布隆过滤器(Bloom Filter)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/216173

相关文章

Redis中Stream详解及应用小结

《Redis中Stream详解及应用小结》RedisStreams是Redis5.0引入的新功能,提供了一种类似于传统消息队列的机制,但具有更高的灵活性和可扩展性,本文给大家介绍Redis中Strea... 目录1. Redis Stream 概述2. Redis Stream 的基本操作2.1. XADD

Knife4j+Axios+Redis前后端分离架构下的 API 管理与会话方案(最新推荐)

《Knife4j+Axios+Redis前后端分离架构下的API管理与会话方案(最新推荐)》本文主要介绍了Swagger与Knife4j的配置要点、前后端对接方法以及分布式Session实现原理,... 目录一、Swagger 与 Knife4j 的深度理解及配置要点Knife4j 配置关键要点1.Spri

从原理到实战深入理解Java 断言assert

《从原理到实战深入理解Java断言assert》本文深入解析Java断言机制,涵盖语法、工作原理、启用方式及与异常的区别,推荐用于开发阶段的条件检查与状态验证,并强调生产环境应使用参数验证工具类替代... 目录深入理解 Java 断言(assert):从原理到实战引言:为什么需要断言?一、断言基础1.1 语

Redis出现中文乱码的问题及解决

《Redis出现中文乱码的问题及解决》:本文主要介绍Redis出现中文乱码的问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 问题的产生2China编程. 问题的解决redihttp://www.chinasem.cns数据进制问题的解决中文乱码问题解决总结

MySQL中的表连接原理分析

《MySQL中的表连接原理分析》:本文主要介绍MySQL中的表连接原理分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、背景2、环境3、表连接原理【1】驱动表和被驱动表【2】内连接【3】外连接【4编程】嵌套循环连接【5】join buffer4、总结1、背景

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

Java Stream的distinct去重原理分析

《JavaStream的distinct去重原理分析》Javastream中的distinct方法用于去除流中的重复元素,它返回一个包含过滤后唯一元素的新流,该方法会根据元素的hashcode和eq... 目录一、distinct 的基础用法与核心特性二、distinct 的底层实现原理1. 顺序流中的去重

Redis的持久化之RDB和AOF机制详解

《Redis的持久化之RDB和AOF机制详解》:本文主要介绍Redis的持久化之RDB和AOF机制,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录概述RDB(Redis Database)核心原理触发方式手动触发自动触发AOF(Append-Only File)核

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模