共计 2426 个字符，预计需要花费 7 分钟才能阅读完成。
布隆过滤器
1. 背景
个别应用布隆过滤器来解决一个理论问题：缓存穿透。
缓存穿透：绕过 Redis 服务器，间接进入后盾数据库查问的攻击方式，咱们就称之为缓存穿透。缓存穿透攻打，是指歹意用户在短时内大量查问不存在的数据，导致大量申请被送达数据库进行查问，当申请数量超过数据库负载下限时，使零碎响应呈现高提早甚至瘫痪的攻击行为，就是缓存穿透攻打。
而解决缓存穿透的计划通常有两种：
1. 缓存空对象
从缓存上取不到数据，在数据库中也取不到，这时能够把 key-value 键值对写成 key-null 键值对，并且设置无效工夫（设置短一些）。这样能够避免带有歹意的用户频繁地用一个值来攻打数据库。
2. 布隆过滤器
2. 介绍
过滤器，顾名思义，就是不让某些申请通过，不放行某些歹意的申请。在缓存中，采纳布隆过滤器，将可能存在的数据哈希到足够大的 bitmap 上，如果客户端申请的数据不存在，布隆过滤器会回绝客户端的申请，如果存在则会放行申请，再去查问缓存，按步骤执行前面的操作。
布隆过滤器 宗旨是采纳一个很长的二进制数组，通过一系列的 Hash 函数来确定该数据是否存在。
布隆过滤器实质上是一个 n 位的二进制数组。你也晓得二进制只有 0 和 1 来示意，针对于以后咱们的场景。这里我模仿了一个二进制数组，其每一位它的初始值都是 0。
3. 原理
咱们举个例子来感受一下其中原理。
咱们提到作为以后的商城，假如有 1000 个商品编号，从 1~1000。作为布隆过滤器，在初始化的时候，实际上就是对每一个商品编号进行若干次 Hash 来确定它们的地位。
-
“1”号商品计算：
比如说针对于以后的“1”编号，咱们对其执行了三次 Hash。所谓 Hash 函数就是将数据代入当前确定一个具体的地位。- Hash 1 函数：它会定位到二进制数组的索引为 1 上，并将其数值从 0 改为 1；
- Hash 2 函数：它定位到索引为 5 的地位，并将从 0 改为 1；
- Hash 3 函数：定位到索引为 99 的地位上，将其从 0 改为 1。
如图：
- “2”号商品计算：
那 1 号商品计算完当前，该轮到 2 号商品。2 号商品通过三次 Hash 当前，别离定位到索引为 1、3 以及 98 号地位上。
留神：原始数据中 1 号位因为方才曾经变成了 1，当初它不变；而 3 号位和 98 号位原始数据从 0 变为 1。
这里又衍生出一个 Hash 新规定：如果在 Hash 后，原始位它是 0 的话，将其从 0 变为 1；如果自身这一位就是 1 的话，则放弃不变。 - “1000”号商品计算：
此时 2 号商品也解决完了，咱们持续向后 3、4、5、6、7、8 直到编号达到了最初一个 1000，当商品编号 1000 解决完后，他将索引为 3、6、98 设置为 1。
计算结束了，该怎么用呢？逻辑怎么呢？
- 先看一个曾经存在的状况
比方，此时某一个用户要查问 858 号商品数据。都晓得 858 是存在的，那么依照原始的三个 Hash 别离定位到了 1、5 和 98 号位，当每一个 Hash 位的数值都是 1 时，则代表对应的编号它是存在的。 - 再看一个不存在的状况
如这里要查问 8888。8888 这个数值通过三次 Hash 后，定位到了 3、6 和 100 这三个地位。此时索引为 100 的数值是 0，在屡次 Hash 时有任何一位为 0 则代表这个数据是不存在的。
针对以上两种状况的总结：如果布隆过滤器所有 Hash 的值都是 1 的话，则代表这个数据可能存在，它是可能存在；但如果某一位的数值是 0 的话，它是肯定不存在的。
但存在一种状况，比方：
比方当初我要查问 8889 的状况，通过三次 Hash 正好每一位上都是 1。只管在数据库中，8889 这个商品是不存在的；但在布隆过滤器中，它会被断定为存在。这就是在布隆过滤器中会呈现的小概率的误判状况。
那如何缩小这样的概率呢？
- 第一个是减少二进制位数。在原始状况下咱们设置索引位达到了 100，然而如果咱们把它放大 1 万倍，达到了 100 万，是不是 Hash 当前的数据会变得更扩散，呈现反复的状况就会更小，这是第一种形式。
- 第二个是减少 Hash 的次数。其实每一次 Hash 解决都是在减少数据的特色，特色越多，呈现误判的概率就越小。
但以上解决方案，带来一个问题：便是 CPU 须要进行更多运算，这会让布隆过滤器的性能有所升高。
redis 缓存穿透 – 利用
1. 初始化布隆过滤器
第一个局部是在利用启动时，咱们去 初始化布隆过滤器。例如将 1000 个、1 万个、10 万个商品进行初始化，实现从 0 到 1 的转化工作。
2. 当有申请打过去时，首先在布隆过滤器中判断数据是否存在
不存在，间接返回
存在，走 Redis 判断3. 在 Redis 中存在，则返回，否则须要从数据库中获取数据，并载入 Redis 缓存中
当用户发来申请时，会附加商品编号，如果布隆过滤器判断编号存在，则间接去读取存储在 Redis 缓存中的数据；如果此时 Redis 缓存没有存在对应的商品数据，则间接去读取数据库，并将读取到的信息从新载入到 Redis 缓存中。这样下一次用户在查问雷同编号数据时，就能够间接读取缓存了。
另外一种状况是，如果布隆过滤器判断没有蕴含编号，则间接返回数据不存在的音讯提醒，这样便能够在 Redis 层面将申请进行拦挡。
其实在大多数状况下，咱们呈现误判也不会对系统产生额定的影响。因为像方才咱们设置 1% 的误判率，1 万次申请才可能会呈现 100 次误判的状况。咱们曾经将 99% 的有效申请进行了拦挡，而这些漏网之鱼也不会对咱们零碎产生任何本质影响。
这里持续提出一个问题：初始化后，对应商品被删怎么办？
如果布隆过滤器初始化后，对应商品被删除了，该怎么办呢？这是一个布隆过滤器的小难点。
因为布隆过滤器某一位的二进制数据，可能被多个编号的 Hash 位进行援用。比如说，布隆过滤器中 2 号位是 1，然而它可能被 3、5、100、1000 这 4 个商品编号同时援用。这里是不容许间接对布隆过滤器某一位进行删除的，否则数据就乱了，怎么办呢？
设计一个带计数的简单数据结构：
计数布隆过滤器。在规范的布隆过滤器下，是无奈得悉以后某一位它是被哪些具体数据进行了援用，然而计数布隆过滤器它是在这一位上额定的 附加的计数信息，表白出该位被几个数据进行了援用