面试官| 如何从10亿数据中快速判断是否存在某一个元素？

缓存雪崩

 Redis 中同一时间内的大批量缓存失效称之为缓存雪崩，如果这段时间还存在大量的请求发起，那就会导致数据库内出现大量的请求，会直接冲垮数据库。

数据库里存在，而缓存中没有，数据是因为时间失效而直达数据库的，这种情况称之为缓存雪崩。

缓存击穿

缓存击穿类似于缓存雪崩，唯一不同的是缓存击穿是指某个缓存失效，且同一时间有很大的并发请求访问这个 key，增加了数据库的缓存压力。

缓存穿透

缓存穿透是访问数据既不存在于 Redis 中，也不存在于数据库中。当达到一定的数量时就会导致数据库中进入大量的数据，给数据库的存储带来挑战。

布隆过滤器（Bloom Filter）

缓存穿透的解决方案中我们可以假设每个 key 都是第二种方式的话，那将会有不存在的 key 大量的被访问，将会全部进入到内存中被存储，此方式试行性不高。

哈希碰撞

lonely 和 wolf 落于同一个位置，在哈希运算的结果下不同的 key 值获得相同值的现象被称之为哈希碰撞，然后再位运算的方式，最后会让其落在同一位置。但哈希碰撞的量过多，也会引起数据判断的不准确性。

PS：需要注意的是，如果经过 N 次哈希函数，则需要得到的 N 个位置都是 1 才能判定存在，只要有一个是 0，就可以判定为元素不存在布隆过滤器中。

fpp

因为布隆过滤器中总是会存在误判率，因为哈希碰撞是不可能百分百避免的。布隆过滤器对这种误判率称之为假阳性概率，即：False Positive Probability，简称为 fpp。

在实践中使用布隆过滤器时可以自己定义一个 fpp，然后就可以根据布隆过滤器的理论计算出需要多少个哈希函数和多大的位数组空间。需要注意的是这个 fpp 不能定义为 100%，因为无法百分保证不发生哈希碰撞。

布隆过滤器的实现（Guava）

在 Guava 的包中提供了布隆过滤器的实现，下面就通过 Guava 来体会一下布隆过滤器的应用：

1. 引入 pom 依赖

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>29.0-jre</version></dependency>

2. 新建一个测试类 BloomFilterDemo：

package com.lonely.wolf.note.redis;

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

import java.text.NumberFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;

public class GuavaBloomFilter {
    private static final int expectedInsertions = 1000000;

    public static void main(String[] args) {
        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),expectedInsertions);

        List<String> list = new ArrayList<>(expectedInsertions);

        for (int i = 0; i < expectedInsertions; i++) {
            String uuid = UUID.randomUUID().toString();
            bloomFilter.put(uuid);
            list.add(uuid);
        }

        int mightContainNum1 = 0;

        NumberFormat percentFormat =NumberFormat.getPercentInstance();
        percentFormat.setMaximumFractionDigits(2); //最大小数位数

        for (int i=0;i < 500;i++){
            String key = list.get(i);
            if (bloomFilter.mightContain(key)){
                mightContainNum1++;
            }
        }
        System.out.println("【key真实存在的情况】布隆过滤器认为存在的key值数：" + mightContainNum1);
        System.out.println("-----------------------分割线---------------------------------");

        int mightContainNum2 = 0;

        for (int i=0;i < expectedInsertions;i++){
            String key = UUID.randomUUID().toString();
            if (bloomFilter.mightContain(key)){
                mightContainNum2++;
            }
        }

        System.out.println("【key不存在的情况】布隆过滤器认为存在的key值数：" + mightContainNum2);
        System.out.println("【key不存在的情况】布隆过滤器的误判率为：" + percentFormat.format((float)mightContainNum2 / expectedInsertions));
    }
}

运行之后的结果为：

image

第一部分输出的 mightContainNum1一定是和 for 循环内的值相等，也就是百分百匹配。即满足了原则 1：如果元素实际存在，那么布隆过滤器一定会判断存在。
第二部分的输出的误判率即 fpp 总是在 3% 左右，而且随着 for 循环的次数越大，越接近 3%。即满足了原则 2：如果元素不存在，那么布隆过滤器可能会判断存在。

这个 3% 的误判率是如何来的呢？我们进入创建布隆过滤器的 create 方法，发现默认的fpp就是 0.03：

image

对于这个默认的 3% 的 fpp 需要多大的位数组空间和多少次哈希函数得到的呢？在 BloomFilter 类下面有两个 default 方法可以获取到位数组空间大小和哈希函数的个数：

• optimalNumOfHashFunctions：获取哈希函数的次数

• optimalNumOfBits：获取位数组大小

debug 进去看一下：

[图片上传失败...(image-ffc4cf-1614312370626)]

得到的结果是 7298440 bit=0.87M，然后经过了 5 次哈希运算。可以发现这个空间占用是非常小的，100W 的 key 才占用了 0.87M。

PS：点击这里可以进入网站计算 bit 数组大小和哈希函数个数。

布隆过滤器的如何删除

布隆过滤器判断一个元素存在就是判断对应位置是否为 1 来确定的，但是如果要删除掉一个元素是不能直接把 1 改成 0 的，因为这个位置可能存在其他元素，所以如果要支持删除，那我们应该怎么做呢？最简单的做法就是加一个计数器，就是说位数组的每个位如果不存在就是 0，存在几个元素就存具体的数字，而不仅仅只是存 1，那么这就有一个问题，本来存 1 就是一位就可以满足了，但是如果要存具体的数字比如说 2，那就需要 2 位了，所以带有计数器的布隆过滤器会占用更大的空间。

带有计数器的布隆过滤器

下面就是一个带有计数器的布隆过滤器示例：

1. pom 文件引入依赖：

<dependency>
    <groupId>com.baqend</groupId>
    <artifactId>bloom-filter</artifactId>
    <version>1.0.7</version></dependency>

2. 新建一个带有计数器的布隆过滤器 CountingBloomFilter：

package com.lonelyWolf.redis.bloom;

import orestes.bloomfilter.FilterBuilder;

public class CountingBloomFilter {
    public static void main(String[] args) {
        orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
                0.01).countingBits(8).buildCountingBloomFilter();

        cbf.add("zhangsan");
        cbf.add("lisi");
        cbf.add("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //true
        cbf.remove("wangwu");
        System.out.println("是否存在王五：" + cbf.contains("wangwu")); //false
    }
}

构建布隆过滤器前面 2 个参数一个就是期望的元素数，一个就是 fpp 值，后面的 countingBits 参数就是计数器占用的大小，这里传了一个 8 位，即最多允许 255 次重复，如果不传的话这里默认是 16 位大小，即允许 65535次重复。

总结

本文主要讲述了使用 Redis 存在的三种问题：缓存雪崩，缓存击穿和缓存穿透。并分别对每种问题的解决方案进行了描述，最后着重介绍了缓存穿透的解决方案：布隆过滤器。原生的布隆过滤器不支持删除，但是可以引入一个计数器实现带有计数器的布隆过滤器来实现删除功能，同时在最后也提到了，带有计数器的布隆。

注：文章来源于网络。

如有侵权，请于后台联系，做删除处理，感谢您的支持。

巧用DNSlog实现无回显注入

反序列化漏洞CVE-2017-10271复现

渗透测试工程师视角下的渗透测试流程

干货｜Linux用户密码文件详解及破解原理！