前言好久没写文章了。今天，我们就来了解一下大名鼎鼎的布隆过滤器。文本什么是布隆过滤器？这个牛逼的神器是Bloom在1970年发明的，它是一种二进制向量数据结构，当时专门用来解决数据查询问题。可用于告诉您某事一定不存在或可能存在。与List、Set、Map等传统数据结构相比，它的效率更高，占用空间更小，但缺点是它返回的结果是概率性的，而不是精确的。布隆过滤器有什么用？说起Bloomfilter的作用，大家可能首先想到的就是Redis缓存穿透，那么我们先来说说什么是缓存穿透？你一定去过京东、淘宝这样的购物网站。不知道大家有没有注意到：在我们日常的开发中，每个页面的URL其实都对应着一个具体的产品。比如我标红的857就是我们产品的sku号，你可以理解为这个产品型号的唯一编码。这里的产品编号是857，显示的页面自然是对应的内容。比如6月18日那天，亿万网友购物时，商城应用同时收到大量请求，要求接入、下单、支付。这时候机器怎么受得了？这就涉及到我们系统的架构了，我们来看一下。首先，作为商城的用户，他发起一个请求，比如他这里还需要查看857号的商品。这时候作为商城应用，会在后台查询Redis缓存服务器。如果缓存数据库中没有857号的产品数据，我们的程序需要在后台数据库服务器中查询，填充到Redis服务器中。这是一个正常的操作过程。那么经过长时间的积累，我们的缓存服务器中的数据可能是这样的。为了便于理解，这里我假设商城中有1000件商品，编号从1到1000。此时，作为商城用户，如果查询857号商品，商城应用不再需要从MySQL数据库，而是直接从Redis服务器中提取数据返回。因为Redis是基于内存的，所以在吞吐量和处理速度上比传统的MySQL数据库快很多倍。随着时间的不断积累，编号从1到1000的所有商品数据缓存都应该存放在Redis服务器中。Redis面临的安全风险：缓存穿透请注意，当前缓存中只有1~1000个数据。假设如果同行之间存在恶意竞争，或者第三方公司开发的爬虫机器人，在短时间内批量进行数据查询，而这些查询的数量在之前的数据库中是不存在的，比如8888、8889、8890这些是不存在的。这时候，我们的系统就会遇到一个很大的安全隐患：因为商城应用在查询后台Redis的时候，因为缓存中没有这些数据，所以才去数据库服务器查询。【无效请求的超高并发会导致崩溃】要知道数据库服务器不够强大，无法处理瞬时的超高并发访问。因此，在短时间内，这些爬虫机器人或者流量攻击机器人发出的无效请求，会被瞬间涌入数据库服务器，对我们系统的性能造成很大的影响，甚至会导致系统崩溃。而这种绕过Redis服务器，直接进入后台数据库查询的攻击方式，我们称之为缓存穿透。对于小规模的缓存穿透，不会对我们的系统造成太大的影响，但是如果是缓存穿透攻击，那就另当别论了。缓存渗透攻击是指恶意用户在短时间内查询大量不存在的数据，导致向数据库发送大量请求进行查询。当请求数超过数据库负载上限时，系统响应延迟很高甚至瘫痪，这是一种缓存渗透攻击。防止缓存穿透“神器”：Bloomfilter在架构设计中最常见的设计称为Bloomfilter，可以有效减少缓存穿透的情况。它的主要思想是用一个很长的二进制数组，通过一系列的Hash函数来判断数据是否存在。这么说可能有点晦涩难懂，但是我们会通过一系列的图来告诉你。布隆过滤器本质上是一个n位的二进制数组。您还知道，对于我们当前的场景，二进制只有0和1来表示。这里我模拟了一个二进制数组，每个数组的初始值为0。而这个二进制数组会存储在Redis服务器中，那么这个数组如何使用呢？1.多次哈希确定其位置。刚才我们提到作为现在的商城，假设有1000个商品编号，从1到1000。作为Bloomfilter，在初始化的时候，其实是对每个商品编号进行多次hash，来确定它们的位置。(1)商品1号的计算比如对于当前的“1”号，我们对其进行3次Hash。所谓Hash函数就是代入数据后确定一个具体的位置。Hash1函数：它定位二进制数组的第2位并将其值从0更改为1；哈希2函数：它位于索引5并将其从0更改为1；Hash3function:到索引为99的位置，把它从0改成1。(2)计算2号产品。1号产品计算完成后，轮到2号产品，2号产品经过3次Hash后分别位于索引1、3、98处。(3)第1000条的计算这时第2条也处理完了，我们继续往回走3、4、5、6、7、8，直到数到最后1000个，当处理完第1000条的时候，他将索引3、6、98分别设置为1。2.Bloomfilter在电商产品中的实践作为Bloomfilter，存储在Redis服务器中应该如何使用？这就涉及到我们日常开发中产品编号的对比。(1)首先看一个存在的情况。比如此时某用户想查询858号商品的数据。我们都知道858是存在的，所以我们根据原来的三个Hash，分别定位到位置1、5、98。当每个Hash位的值为1时，表示对应的数存在。(2)看一个不存在的情况。比如这里我们要查询8888，8888的值经过3次哈希后，位于3、6、100这三个位置，此时索引为100的值为0，如果多次Hash时任意位为0，表示该数据不存在。简单总结一下：如果布隆过滤器的Hash值全部为1，说明数据可能存在。注意我的表达：它可能存在；但如果某位的值为0，则一定不存在。在Bloomfilter设计之初，并不是一个准确的判断，因为Bloomfilter存在误判。(3)最后看一个误判的情况，看现在的演示：比如现在想查询8889的情况，经过3次Hash，恰好每一位都是1。虽然在数据库中，产品8889不存在；但是在Bloomfilter中，会判断为存在。这是Bloomfilter会出现的小概率误判。3、如何减少Bloomfilter的误判？减少误报的发生有两种方法：第一种是增加二进制位数。原来的情况下，我们把索引位设置为100，但是如果扩大10000倍，达到100万，Hash之后的数据会不会更分散，重复的出现会更小，这是第一种方式。二是增加Hash的数量。其实每一次Hash过程都是为了增加数据的特性。特征越多，误判的概率越小。现在我们已经做了3次Hash，那么如果再做10次，是不是误判的概率会小很多？但是在这个过程中，代价是CPU需要进行更多的计算，这会降低Bloomfilter的性能。说到这里，我想你应该对布隆过滤器有所了解。但是在我们的开发过程中，我们如何使用布隆过滤器呢？过来看看。开发中如何使用布隆过滤器？1.Bloomfilter在Java中的应用其实作为Java这么多年的积累。像Bloomfilter这样的经典算法早就为我们封装集成了。Java中提供了一个Redisson组件，它内置了Bloomfilter，可以让程序员非常简单直接的设置Bloomfilter。以上代码就是Redisson的使用方法。前几行代码用于设置Redis服务器的服务地址和端口号。而后面的重点就在这里，我们实例化了一个Bloomfilter对象，后面的参数是指Redis用哪个key来保存Bloomfilter数据？下面这句话很关键。作为当前的布隆过滤器，这里需要调用tryInit方法。它有两个参数：第一个参数是初始化布隆过滤器的长度。长度越大，误判性的可能性越低。第二个0.01表示最大允许的误报率为1%，在我们之前的项目中通常设置为1%。如果这个值设置得太小，虽然会降低误报率，但是会产生更多的Hash运算，会降低系统的性能（刚刚提到），所以1%也是我建议的值。布隆过滤器初始化完成后，我们可以通过add方法向其添加数据。所谓添加数据，就是对数据进行多次哈希，将对应的位从0变为1的过程。比如现在我们把数字1加进去，然后就可以使用布隆过滤器的contains方法来判断当前数据是否存在。我们输入1，它输出true；输入不存在的8888，输出false。请注意：这两个结果的含义是不同的。如果输出为false，说明该数据肯定不存在；但是如果输出为真，有1%的概率可能不存在，因为布隆过滤器误判了。以上就是Bloomfilter在Java中的应用，但是如果要在项目中使用Bloomfilter应该是什么样子呢？它的处理流程是怎样的？2.Bloomfilter在项目中的应用我们来看看在项目中使用Bloomfilter的过程。其实归结为以下三部分：第一部分是在应用启动时初始化布隆过滤器。.比如初始化1000、10000、100000商品，完成0到1的转化，之后用户发送请求时，会添加商品编号。如果布隆过滤器判断该数存在，则直接读取存储在Redis缓存中的数据；如果此时Redis缓存中没有对应的商品数据，则直接读取数据库，将读取到的信息重新加载到Redis缓存中。这样下次用户查询相同编号的数据时，可以直接读取缓存。还有一种情况，如果Bloomfilter判断不包含该数，则直接返回该数据不存在的消息，这样就可以在Redis层面拦截该请求。你可能会想，布隆过滤器既然有误判率，万一误判了怎么办？其实在大多数情况下，我们的误判不会对系统造成额外的影响。因为刚才我们设置了1%的误报率，所以仅仅10000个请求就可能出现100个误报。我们已经阻止了99%的无效请求，那些漏掉的请求对我们的系统没有真正的影响。扩展问题：初始化后对应的商品被删除了怎么办？最后还有一个扩展的小问题：Bloomfilter初始化后对应的product被删除了怎么办？这是布隆过滤器的一个小困难。因为布隆过滤器某一位的二进制数据可能被多个编号的Hash位引用。比如Bloomfilter中的bit2为1，但可能同时被3、5、100、1000这4个itemnumbers引用。不允许直接删除布隆过滤器的某一位，否则数据会乱，怎么办？这里有两种业界常见的解决方案：布隆过滤器的定时重建和异步重建。例如，我们每4小时在额外的服务器上异步执行一个任务计划，以重新生成Bloomfilter并替换现有的Bloomfilter。计数布隆过滤器。在标准的Bloomfilter下，无法知道当前bit引用了哪些具体的数据，而countingBloomfilter是对这个bit附加的计数信息，表示Bits被多个数据引用。（如果你对计数BloomFilter感兴趣，可以查看CountingBloomFilter的原理和实现）总结一下今天关于BloomFilter的知识，到此结束。参考：拉勾教育《如何抗住亿级流量之布隆过滤器》
