今天小面就和大家来聊一下布隆!!!他可以开盾,大招起飞!可保人可开团!!!......
假如你的服务后台存储有大量数据,通过缓存提高查询效率,当缓存中不存某条记录再去数据库中查询,这就可以大大减少对数据库的请求压力。但是有一天某黑客构建大量不存在于缓存中的 key 发起缓存穿透攻击,在QPS足够高的情况下,有可能会把数据库压跨,这种情况下该怎么办呢?
当我们谈论到redis缓存穿透问题的时候,其中一个解决方法就是使用布隆过滤去,那么布隆过滤器到底是什么呢? 关注公主号thisjava,今天就带大家初识布隆过滤器
使用Google Guava库来实现基于布隆过滤器的海量字符串去重是一个很好的选择。布隆过滤器是一种空间效率极高的概率型数据结构,它利用位数组表示集合,并使用哈希函数将元素映射到位数组的某些位置。布隆过滤器可以高效地检查一个元素是否可能属于某个集合,但有一定的误报率。
之前我们介绍Redis入门系列课程的时候,讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一,就是使用布隆过滤器,但是由于并没有详细介绍什么是布隆过滤器,所以就有很多小伙伴问我——到底什么是布隆过滤器?
布隆过滤器(Bloom Filter)是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构,它可以告诉你某种东西一定不存在或者可能存在。当布隆过滤器说,某种东西存在时,这种东西可能不存在;当布隆过滤器说,某种东西不存在时,那么这种东西一定不存在。
布隆过滤器是一个叫“布隆”的人提出的,本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure)。它本身是一个很长的二进制向量,特点是高效地插入和查询,可以用来确定 “某一条数据一定不存在或者可能存在一个集合中”。
布隆过滤器是一种基于概率的数据结构,用于判断一个元素是否存在于一个集合中。相比于传统的数据结构,布隆过滤器具有占用空间少、查询速度快的特点,常被用于缓存、爬虫去重等场景。Redis 作为一款流行的 NoSQL 数据库,也提供了对布隆过滤器的支持。本文将介绍如何使用 Redis 实现布隆过滤器,并提供 Java 示例代码和单元测试。
当进行元素判断时,查询此元素的几个哈希位置上的值是否为 1,如果全部为 1,则表示此值存在,如果有一个值为 0,则表示不存在。因为此位置是通过 hash 计算得来的,所以即使这个位置是 1,并不能确定是那个元素把它标识为 1 的,因此布隆过滤器查询此值存在时,此值不一定存在,但查询此值不存在时,此值一定不存在。
在大数据场景下,布隆过滤器是一种常用的数据结构,用于快速判断元素是否存在。而 Redis 则是一种流行的缓存和数据存储系统,广泛应用于互联网领域。
本篇文章的代码示例已放到 github 上,Git地址为:advance(记录每一个学习过程),项目的介绍页面是我所有文章的一个引用目录,大家在引用目录里面即可找到对应文章的一个代码路径。
使用 JDK 自带的 Set 集合来进行 URL 去重,看上去效果不错,但是这种做法有一个致命了缺陷,就是随着采集的 URL 增多,你需要的内存越来越大,最终会导致你的内存崩溃。那我们在不使用数据库的情况下有没有解决办法呢?布隆过滤器!它就可以完美解决这个问题,布隆过滤器有什么特殊的地方呢?接下来就一起来学习一下布隆过滤器。
这个牛轰轰的神器是布隆这位大牛在 1970 年发明的,是一个二进制向量数据结构,当时专门解决数据查询问题。可以用来告诉你 某样东西一定不存在或者可能存在。
https://www.cnblogs.com/qdhxhz/p/11237246.html
布隆过滤器(英语:Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。
很多人想到的是HashMap。 确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。
redis 在 4.0 的版本中加入了 module 功能,布隆过滤器可以通过 module 的形式添加到 redis 中,所以使用 redis 4.0 以上的版本可以通过加载 module来使用 redis 中的布隆过滤器。但是这不是最简单的方式,使用 docker 可以直接在 redis 中体验布隆过滤器。
在程序的世界中,布隆过滤器是程序员的一把利器,利用它可以快速地解决项目中一些比较棘手的问题。如网页 URL 去重、垃圾邮件识别、大集合中重复元素的判断和缓存穿透等问题。
海量数据处理以及缓存穿透这两个场景让我认识了布隆过滤器 ,我查阅了一些资料来了解它,但是很多现成资料并不满足我的需求,所以就决定自己总结一篇关于布隆过滤器的文章。希望通过这篇文章让更多人了解布隆过滤器,并且会实际去使用它!
布隆过滤器(BloomFilter)是由一个叫“布隆”的小伙子在1970年提出的,它是一个很长的二进制向量,主要用于判断一个元素是否在一个集合中。
你可能没想到: RocketMQ、 Hbase 、Cassandra 、LevelDB 、RocksDB 这些知名项目中都有布隆过滤器的身影。
前面的学习,我们知道了Redis的很多应用场景,但是最常见的还是缓存,“性能不够,缓存来凑”,在一些高并发的场景合理的使用缓存,还是可以减缓系统压力的。
这个时候,布隆过滤器(Bloom Filter)就派上了用场。 作为一种空间高效的概率型数据结构,布隆过滤器能够快速有效地检测一个元素是否属于一个集合。其应用广泛,从网络爬虫的网页去重,到数据库查询优化,乃至比特币网络的交易匹配,都离不开它的身影。
布隆过滤器作为一个精巧且实用的数据结构,对于后端程序员来讲,学习和理解布隆过滤器有很大的必要性。希望通过这篇文章让更多人了解布隆过滤器的原理,并且会实际去使用它!
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数,布隆过滤器可以用于检索一个元素是否在一个集合中。
如图所示,当字符串存储要加入到布隆过滤器中时,该字符串首先由多个哈希函数生成不同的哈希值,然后在对应的位数组的下表的元素设置为 1(当位数组初始化时 ,所有位置均为0)。当第二次存储相同字符串时,因为先前的对应位置已设置为1,所以很容易知道此值已经存在(去重非常方便)。
它们两的相同点是:它们都存在误判的情况。例如,使用哈希表时,不同元素的哈希值可能相同,所以这样就产生误判了;而布隆过滤器的特征是,当布隆过滤器说,某个数据存在时,这个数据可能不存在;当布隆过滤器说,某个数据不存在时,那么这个数据一定不存在。
4*4000000000 /1024/1024/1024 = 14.9G ,考虑到其中有一些重复的话,那1G的空间也基本上是不够用的。
布隆过滤器的Python3实现,包括标准、计数、标准扩容、计数扩容。更新自pybloom。
我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的? 用服务器记录了用户看过的所有历史记录,当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选,过滤掉那些已经存在的记录。 如何快速查找呢?
在Redis 缓存击穿(失效)、缓存穿透、缓存雪崩怎么解决?中我们说到可以使用布隆过滤器避免「缓存穿透」。
比如我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的?
布隆过滤器本质上是一种概率型的数据结构,用于检索一个元素是否在集合中,它将告诉你一个数据“一定不存在或可能存在。
一个网站有 100 亿 url 存在一个黑名单中,每条 url 平均 64 字节。这个黑名单要怎么存?若此时随便输入一个 url,你如何快速判断该 url 是否在这个黑名单中?
数据结构是个很有意思的东西,很多设计非常巧妙的数据结构能够大大降低某项操作的时间或者空间复杂度。所以我来开个专题来讲一些高级的,用途广泛的数据结构。搞数据结构专题的好处就是能够普及一些数据结构的原理和思想,第二个就是能够省下我很多考虑分享主题的时间。低级的数据结构,比如Hash,Set,链表队列之类的我就不讲了默认大家都会了。今天是第一篇,我们来讲讲布隆过滤器。
在之前的 拜托,面试官别问我「布隆」了 一文中,很多小伙伴留言说并不能看出布隆过滤器有比位图更方便,今天的文章就补充更详细一点。
本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
位图的优点是节省空间,快,缺点是要求范围相对集中,如果范围分散,空间消耗上升,同时只能针对整型,字符串通过哈希转化成整型,再去映射,对于整型没有冲突,因为整型是有限的,映射唯一的位置,但是对于字符串来说,是无限的,会发生冲突,会发生误判:此时的情况的是不在是正确的,在是不正确的,因为可能不来是不在的,但是位置跟别人发生冲突,发生误判
这个时候,布隆过滤器(Bloom Filter)就派上了用场。作为一种空间高效的概率型数据结构,布隆过滤器能够快速有效地检测一个元素是否属于一个集合。其应用广泛,从网络爬虫的网页去重,到数据库查询优化,乃至比特币网络的交易匹配,都离不开它的身影。
本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。
公司用户中心,有大量的用户请求,为防止缓存击穿,需要设计一个缓存策略 ,将恶意请求过滤掉。
布隆过滤器(Bloom Filter)是一种数据结构,可以快速、高效地判断一个元素是否存在于一个集合中,其特点是空间效率高且查询速度快。在日常的编程工作和项目开发中,布隆过滤器经常被用于缓存、防止缓存穿透等场景。
之所以谈到布隆过滤器主要是因为以前工作中用到redis,为了防止缓冲穿透而使用了布隆过滤器(BloomFilter)。这次温故而知新,再深入学习它的原理,顺带提提它的其他用途。
在实际开发中,会遇到很多要判断一个元素是否在某个集合中的业务场景,类似于垃圾邮件的识别,恶意ip地址的访问,缓存穿透等情况。类似于缓存穿透这种情况,有许多的解决方法,如:redis存储null值等,而对于垃圾邮件的识别,恶意ip地址的访问,我们也可以直接用 HashMap 去存储恶意ip地址以及垃圾邮件,然后每次访问时去检索一下对应集合中是否有相同数据。
在简单数组或列表中插入新数据时,插入数据的索引不是从要插入的值确定的。这意味着密钥(索引)和值(数据)之间没有直接关系。因此,如果需要在数组中搜索值,则必须在所有索引中进行搜索。在哈希表中,您可以通过散列值来确定键或索引。这意味着密钥是根据值确定的,每次需要检查列表中是否存在该值时,您只需对值进行散列并搜索该密钥,查找速度非常快,时间复杂度为O(1)。
在空间上相对于其他数据结构,有很大优势, 20亿的数据需要 2000000000bit/8/1024/1024 = 238 M ,如果使用数组来存储,假设每个用户 ID 占用 4个字节的空间,存储20亿用户需要 2000000000byte/4/8/1024/1024 = 7600M 的空间,是布隆过滤器的32倍。
不知道从什么时候开始,本来默默无闻的布隆过滤器一下子名声大燥,在面试中面试官问到怎么避免缓存穿透,你的第一反应可能就是布隆过滤器,缓存穿透=布隆过滤器成了标配,但具体什么是布隆过滤器,怎么使用布隆过滤器不是很清楚,那今天我们就来把他说清楚,讲明白。。
领取专属 10元无门槛券
手把手带您无忧上云