Redis의 Bloom Filter에 대한 심층 분석
- 青灯夜游앞으로
- 2021-12-23 09:57:372887검색
캐시 침투를 방지하는 방법은 무엇입니까? 다음 기사에서는 캐시 침투를 방지하기 위한 Redis의 강력한 도구인 Bloom Filter(Bloom Filter)에 대해 알아보겠습니다.
개요
블룸 필터(Bloom Filter)는 Burton Howard Bloom이 1970년에 제안한 데이터 구조입니다. 실제로는 긴 이진 벡터와 일련의 무작위 매핑 함수입니다. [관련 권장사항: Redis 동영상 튜토리얼] Bloom Filter）是一个数据结构，由布隆（Burton Howard Bloom）于 1970 年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。【相关推荐：Redis视频教程】
布隆过滤器可以用于高效的检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远优于一般的算法，缺点是有一定的误识别率，而且难以删除（一般不支持，需要额外的实现）。
误识率指的是可以判断元素肯定不在集合中，判断元素可能在集合中，无法判断元素一定在集合中。
布隆过滤器之所以高效，因为它是一个概率数据结构，它能确认元素肯定不在集合中，或者元素可能在集合中。之所以说是可能，是因为它有一定的误识别率，使得无法 100% 确定元素一定在集合中。
问题引出
在日常工作中，有一个比较常见的需求，就是需要判断一个元素是否在集合中。例如以下场景
- 给定一个IP黑名单库，检查指定IP是否在黑名单中？
- 在接收邮件的时候，判断一个邮箱地址是否为垃圾邮件？
- 在文字处理软件中，检查一个英文单词是否拼写正确？
遇到这种问题，通常直觉会告诉我们，应该使用集合这种数据结构来实现。例如，先将 IP 黑名单库的所有 IP 全部存储到一个集合中，然后再拿指定的 IP 到该集合中检查是否存在，如果存在则说明该 IP 命中黑名单。
通过一段代码来模拟 IP 黑名单库的存储和检查。
public class IPBlackList {
public static void main(String[] args) {
Set<String> set = new HashSet<>();
set.add("192.168.1.1");
set.add("192.168.1.2");
set.add("192.168.1.4");
System.out.println(set.contains("192.168.1.1"));
System.out.println(set.contains("192.168.1.2"));
System.out.println(set.contains("192.168.1.3"));
System.out.println(set.contains("192.168.1.4"));
}
}集合的内部，通常是使用散列表来实现。其优点是查询非常高效，缺点是比较耗费存储空间。
一般在数据量比较小的时候，我们会使用集合来进行存储。以空间换时间，在占用空间较小的情况下，同时又能提高查询效率。
但是，当存储的数据量比较大的时候，耗费大量空间将会成为问题。因为这些数据通常会存储到进程内存中，以加快查询效率。而机器的内存通常都是有限的，要尽可能高效的使用。
另一方面，散列表在空间和效率上是需要做平衡的。存储相同数量的元素，如果散列表容量越小，出现冲突的概率就越高，用于解决冲突的时间将会花费更多，从而影响性能。
而布隆过滤器（Bloom Filter
Bloom 필터를 사용할 수 있는 경우 요소가 컬렉션에 있는지 여부를 효율적으로 검색합니다. 장점은 일반 알고리즘에 비해 공간 효율성과 쿼리 시간이 훨씬 좋다는 점이다. 단점은 오인식률이 일정하고 삭제가 어렵다는 점이다(일반적으로 지원되지 않으며 추가 구현이 필요하다).
- 위양성률이란 요소가 집합에 확실히 없다고 판단할 수 있고, 요소가 집합에 있을 수도 있다고 판단할 수 있지만 요소가 집합에 확실히 있다고 판단할 수 없다는 의미입니다. 세트.
-
질문
일상 업무에서는 요소가 세트에 있는지 확인해야 하는 경우가 많습니다. 예를 들어, 다음 시나리오
블룸 필터가 효율적인 이유는 해당 요소가 집합에 확실히 포함되어 있지 않거나, 집합에 포함되어 있을 수 있음을 확인할 수 있는 확률적 자료구조이기 때문입니다. 가능한 이유는 어느 정도 오인식률이 있어서 해당 요소가 집합에 반드시 포함되어 있다고 100% 확신하는 것이 불가능하기 때문입니다.
IP 블랙리스트 데이터베이스가 주어지면 지정된 IP가 블랙리스트에 있는지 확인합니까? 이메일을 받을 때 이메일 주소가 스팸인지 어떻게 판단하나요?
워드 프로세싱 소프트웨어에서 영어 단어의 철자가 올바른지 확인하시나요?
이런 종류의 문제에 직면할 때 우리의 직관은 대개 이를 구현하기 위해 집합과 같은 데이터 구조를 사용해야 한다고 말합니다. 예를 들어, 먼저 IP 블랙리스트 데이터베이스의 모든 IP를 세트에 저장한 다음, 지정된 IP가 세트에 존재하는지 확인합니다. 존재하는 경우 해당 IP가 블랙리스트에 도달했음을 의미합니다.
코드를 통해 IP 블랙리스트 라이브러리의 저장 및 확인을 시뮬레이션합니다.<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>
컬렉션의 내부는 일반적으로 해시 테이블을 사용하여 구현됩니다. 장점은 쿼리가 매우 효율적이라는 점이지만, 단점은 더 많은 저장 공간을 소모한다는 것입니다.
일반적으로 데이터의 양이 상대적으로 적을 때 컬렉션을 사용하여 저장합니다. 공간을 시간에 맞춰 거래하면 공간을 덜 차지하면서 쿼리 효율성을 높일 수 있습니다.- 그러나 저장되는 데이터의 양이 상대적으로 크면 많은 공간을 소모하는 것이 문제가 됩니다. 이러한 데이터는 일반적으로 쿼리 효율성을 높이기 위해 프로세스 메모리에 저장되기 때문입니다. 일반적으로 머신의 메모리는 제한되어 있으므로 최대한 효율적으로 사용해야 합니다. 반면, 해시 테이블은 공간과 효율성 측면에서 균형을 이루어야 합니다. 동일한 수의 요소를 저장하면 해시 테이블 용량이 작을수록 충돌 가능성이 높아지고 충돌 해결에 더 많은 시간이 소요되어 성능에 영향을 미칩니다.
Bloom Filter)의 등장으로 이 문제를 아주 잘 해결할 수 있습니다. 한편으로는 더 적은 메모리로 데이터를 저장할 수 있고, 다른 한편으로는 매우 효율적인 쿼리 성능을 얻을 수 있습니다. 기본 원리a먼저 이진 벡터를 만들고 모든 비트를 0
그런 다음 K 해시 함수를 선택하여 요소를 K번 해시하고 벡터 첨자의 비트를 계산합니다.
b요소 추가
다른 문자열을 추가하고
c두 번 해시하여 아래 첨자 11과 12를 얻고 해당 비트를 0에서 1까지 표시합니다.
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |||||1|||||1|1||||||
마지막으로 문자열
sam을 추가하고 두 번 해시하여 아래 첨자 0과 7을 얻고 해당 비트는 0에서 표시됩니다. 1로.
|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |1||||1|||1|||1|1|1||||||
위에 4개의 문자열을 추가했습니다. 각 문자열은 2번 해시되었으며 2비트에 해당하는 값은 1로 표시되었습니다. 총 6비트가 최종적으로 8비트 대신 1로 표시됩니다.
이는 서로 다른 요소를 해싱하여 얻은 위치가 겹칠 수 있음을 보여줍니다. 요소가 많을수록 중복 가능성이 높아집니다. 겹치는 위치에 두 개의 요소가 있는 경우 두 요소 중 하나가 세트에 있어야 한다고 판단할 수 없습니다.
세트에 요소가 존재하는지 확인하려면 동일한 방식으로 요소를 두 번 해시하고 얻은 두 첨자에 대해 Bloom 필터에서 해당 비트를 검색하면 됩니다. 해당 2비트가 모두 1이 아닌 경우 해당 요소는 확실히 집합에 포함되지 않습니다. 해당 2비트가 모두 1인 경우 해당 요소가 집합에 있을 수도 있고 존재하지 않을 수도 있음을 의미합니다.
예를 들어 b 문자열이 집합에 존재하는지 확인할 때 해싱하여 얻은 두 첨자는 모두 11입니다. 11에 해당하는 비트가 1인지 확인하여 찾습니다. 그러나 이것이 b가 컬렉션에 있어야 한다는 의미는 아닙니다. 이는 문자열 b 是否存在集合中，哈希得到的 2 个下标都为11。检查发现，11对应的位为1。但是，这并不能说明 b 一定在集合中。这是因为，字符串 c 哈希后的下标也包含11，有可能只是字符串c在集合中，而 b 却不存在，这就是造成了误识别，也称为假阳性。
再检查字符串 foo，哈希得到的下标分别为 8 和 13，对应的位都为0。因此，字符串 foo 肯定不在集合中。
数学原理
布隆过滤器背后的数学原理是
两个完全随机的数字相冲突的概率很小，因此可以在很小的误识别率条件下，用很少的空间存储大量信息。
误识别率
误识别率（FPP，false positive probabilistic）的计算如下。
假设布隆过滤器大小为 m 比特，存储了 n 个元素，使用 k 次散列函数来计算元素的存储位置。
- 添加 1 个元素，则任一比特为 1 的概率为
1/m，任一比特为 0 的概率为1-1/m； - 添加 1 个元素，执行 k 次散列之后，则任一比特为 0 的概率为
(1-1/m)^k，任一比特为 1 的概率为1-(1-1/m)^k； - 如果添加 n 个元素，那么任一比特为 0 的概率为
(1-1/m)^kn，任一比特为 1 的概率为1-(1-1/m)^kn； - 如果将 1 个新的元素，添加到已存在
n个元素的布隆过滤器中，则任一比特已经为 1 的概率与上面相同，概率为1-(1-1/m)^kn。因此，k 个比特都为1的概率为：(1-(1-1/m)^kn)^k，此即为新插入元素的误识别率。
当 n 值比较大时，$(1-(1-1/m)^{kn})^k$ 约等于 $(1-e^{-kn/m})^k$
假定布隆过滤器大小 m 为 16 比特，k为 8，存储元素 n 为1，那么误识别（假阳性）的概率是万分之五（5/10000）。
此时，m/n=16，事实上这表示 1个元素使用 16 个比特的空间来存储。
因此，当 k 相同时，m/n 为 16/1、32/2、64/4 等值时具有相同的误识别率。
网站 Bloom Filters - the math 给出了布隆过滤器的误识别率表，可以很方便的查处不同 m，n，k의 해시된 첨자에도 11이 포함되어 있기 때문입니다. 문자열 c가 집합에 있지만 b가 존재하지 않을 가능성이 있습니다. 이로 인해 오인이 발생합니다(가양성이라고도 함).
foo 문자열을 다시 확인하세요. 해싱으로 얻은 첨자는 각각 8과 13이고 해당 비트는 모두 0입니다. 따라서 foo 문자열은 확실히 세트에 없습니다.
수학적 원리
블룸 필터의 수학적 원리는- 완전히 난수 두 개가 충돌할 확률은 매우 작으므로 매우 짧은 시간 내에 감지할 수 있습니다. small 오인식률이 낮은 조건에서 작은 공간에 많은 양의 정보가 저장됩니다.
-
블룸 필터 크기가
m비트이고n요소를 저장한다고 가정합니다.k해시 함수를 사용하여 요소 위치 저장을 계산합니다. 1개의 요소를 추가하면 임의의 비트가 1일 확률은
오인식률 오인식률(FPP, false positive probabilistic)은 다음과 같이 계산됩니다.
1/m이고 임의의 비트가 0일 확률은 1-1/m입니다. ;1개의 요소를 추가하고 k개의 해시를 수행하면 임의의 비트가 0일 확률은 (1-1/m)^k이고 임의의 비트가 1일 확률은 1입니다. -(1-1/m)^k; n개 요소를 추가하면 임의의 비트가 0일 확률은 (1-1/m)^kn입니다. 임의의 비트가 1이라는 것은 1-(1-1/m)^kn입니다.
새 요소가 기존 n에 추가되는 경우 요소가 있는 Bloom 필터에서 , 임의의 비트가 이미 1일 확률은 위와 동일하며 확률은 1-(1-1/m)^kn입니다. 따라서 k 비트가 모두 1일 확률은 (1-(1-1/m)^kn)^k이며, 이는 새로 삽입된 요소의 오인식률입니다.
n 값이 상대적으로 큰 경우 $(1-(1-1/m)^{kn})^k$는 $(1-e와 거의 같습니다. ^{- kn/m})^k$
m이 16비트이고 k는 8이며 저장 요소 n이라고 가정합니다. code>가 1이면 오인(false positive) 확률은 10,000분의 5(5/10000)입니다. 🎜🎜 이때 <code>m/n=16은 실제로 1개의 요소가 16비트의 공간을 사용하여 저장한다는 의미입니다. 🎜🎜따라서 k가 동일할 때 m/n은 16/1, 32/2, 64/4 등일 때 오인식률이 동일합니다. 🎜🎜웹사이트Bloom 필터 - 수학은 다양한 m, n, k을 쉽게 확인하고 처리할 수 있는 Bloom 필터의 잘못된 인식률 표를 제공합니다. code> 주어진 값에서의 오인식률. 🎜🎜오인식률을 해결하려면🎜🎜오인식률을 해결하는 일반적인 방법으로는 🎜🎜🎜🎜Whitelist🎜🎜🎜🎜역추적 확인🎜🎜🎜🎜🎜Whitelist🎜🎜🎜일반적인 방법으로 더 작게 만들기 잘못 식별될 수 있는 데이터를 저장하는 데 작은 화이트리스트가 사용됩니다. 🎜🎜스팸 필터링을 예로 들어보세요. 이메일을 받을 때 스팸을 필터링하는 스팸 라이브러리가 있다고 가정해 보겠습니다. 🎜🎜이때 먼저 이 스팸 라이브러리를 Bloom 필터에 저장할 수 있습니다. 이메일을 받을 때 먼저 Bloom 필터를 통해 대부분의 일반 이메일을 효율적으로 필터링할 수 있습니다. 🎜🎜소수의 스팸 이메일(아마도)의 경우 일부는 일반 이메일일 수 있습니다. 🎜<p>再创建一个白名单库，当在布隆过滤器中判断可能为垃圾邮件时，通过查询白名单来确认是否为正常邮件。</p>
<p>对于没在白名单中的邮件，默认会被移动到垃圾箱。通过人工识别的方式，当发现垃圾箱中存在正常邮件的时候，将其移入白名单。</p>
<h3 data-id="heading-11"><strong>回源确认</strong></h3>
<p>很多时候，使用布隆过滤器是为了低成本，高效率的拦截掉大量数据不在集合中的场景。例如</p>
<ul>
<li>Google Bigtable，Apache HBase以及Apache Cassandra和PostgreSQL 使用 Bloom 过滤器来减少对不存在的行或列的磁盘查找。避免进行昂贵的磁盘查找，可大大提高数据库查询操作的性能。</li>
<li>在谷歌浏览器用于使用布隆过滤器来识别恶意URL的网页浏览器。首先会针对本地 Bloom 过滤器检查所有 URL，只有在 Bloom 过滤器返回肯定结果的情况下，才对执行的 URL 进行全面检查（如果该结果也返回肯定结果，则用户会发出警告）。</li>
<li>拦截掉大量非IP黑名单请求，对于少量可能在黑名单中的IP，再查询一次黑名单库。</li>
</ul>
<p><strong>这是布隆过滤器非常典型的应用场景，先过滤掉大部分请求，然后只处理少量不明确的请求。</strong></p>
<p><strong>这个方法，和白名单库的区别是，不需要再另外建立一套库来处理，而是使用本来就已经存在的数据和逻辑。</strong></p>
<p>例如 Google Bigtable 查询数据行本来就是需要查的，只不过使用布隆过滤器拦截掉了大部分不必要的请求。而 IP 是否为黑名单也是需要查询的，同样是先使用布隆过滤器来拦截掉大部分IP。</p>
<p>而上面垃圾邮件的处理，对于可能为垃圾邮件的情况，不是通过完整的垃圾邮件库再查询一次进行确认，而是用增加白名单来进行判断的方式。因为通常来说，白名单库会更小，便于缓存。</p>
<p>这里所说的回源，实际上是对可能被误识别的请求，最后要回到数据源头或逻辑确认一次。</p>
<h2 data-id="heading-12">Guava中的布隆容器的实现</h2>
<p>Guava 中就提供了一种 Bloom Filter 的实现。</p>
<h3 data-id="heading-13"><strong>guava包引入</strong></h3>
<p>要使用 Bloom Filter，需要引入 guava 包</p><pre class="brush:js;toolbar:false;"><dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency></pre><h3 data-id="heading-14"><strong>误判率测试</strong></h3>
<p>下面对布隆容器的误判率进行测试，分2步</p>
<ul style="list-style-type: disc;">
<li><p>往过滤器中放一百万个数，然后去验证这一百万个数是否能通过过滤器</p></li>
<li><p>另外找一万个数，去检验漏网之鱼的数量</p></li>
</ul><pre class="brush:js;toolbar:false;">/**
* 测试布隆过滤器(可用于redis缓存穿透)
*
* @author 敖丙
*/
public class TestBloomFilter {
private static int total = 1000000;
private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
// private static BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.001);
public static void main(String[] args) {
// 初始化1000000条数据到过滤器中
for (int i = 0; i < total; i++) {
bf.put(i);
}
// 匹配已在过滤器中的值，是否有匹配不上的
for (int i = 0; i < total; i++) {
if (!bf.mightContain(i)) {
System.out.println("有坏人逃脱了~~~");
}
}
// 匹配不在过滤器中的10000个值，有多少匹配出来
int count = 0;
for (int i = total; i < total + 10000; i++) {
if (bf.mightContain(i)) {
count++;
}
}
System.out.println("误伤的数量：" + count);
}
}</pre><p>运行结果</p><pre class="brush:js;toolbar:false;">误伤的数量：320</pre><p>运行结果表示，遍历这一百万个在过滤器中的数时，都被识别出来了。一万个不在过滤器中的数，误伤了320个，错误率是0.03左右。</p>
<h3 data-id="heading-15"><strong>Bloom Filter 源码分析</strong></h3><pre class="brush:js;toolbar:false;">public static <T> BloomFilter<T> create(Funnel<? super T> funnel, int expectedInsertions) {
return create(funnel, (long) expectedInsertions);
}
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
}
public static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp) {
return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
......
}</pre><p>Bloom Filter 一共四个 <code>create 方法，不过最终都是走向第4个。看一下每个参数的含义
funnel：数据类型(一般是调用Funnels工具类中的)expectedInsertions：期望插入的值的个数fpp： 错误率(默认值为0.03)strategy： 哈希算法 Bloom Filter的应用
更多编程相关知识，请访问：编程视频！！
위 내용은 Redis의 Bloom Filter에 대한 심층 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!