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

2021年09月15日 阅读数:2
这篇文章主要向大家介绍面试官:如何从10亿数据中快速判断是否存在某一个元素?,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
前言

当 Redis 用做缓存时,其目的就是为了减小数据库访问频率,下降数据库压力,可是假如咱们某些数据并不存在于 Redis 当中,那么请求仍是会直接到达数据库,而一旦在同一时间大量缓存失效或者一个不存在缓存的请求被恶意攻击访问,这些都会致使数据库压力骤增,这又该如何防止呢?java

缓存雪崩

缓存雪崩指的是 Redis 当中的大量缓存在同一时间所有失效,而假如恰巧这一段时间同时又有大量请求被发起,那么就会形成请求直接访问到数据库,可能会把数据库冲垮。git

缓存雪崩通常形容的是缓存中没有而数据库中有的数据,而由于时间到期致使请求直达数据库。面试

解决方案

解决缓存雪崩的方法有不少,经常使用的有如下几种:redis

  • 加锁,保证单线程访问缓存。这样就不会有不少请求同时访问到数据库。
  • key 值的失效时间不要设置成同样。典型的就是初始化预热数据<typo data-origin="值的" ignoretag="true">的时</typo>候,将数据存入缓存时能够采用随机时间来确保不会在同一时间有大量缓存失效。
  • 内存容许的状况下,能够将缓存设置为永不失效。
缓存击穿

缓存击穿和缓存雪崩很相似,区别就是缓存击穿通常指的是单个缓存失效,而同一时间又有很大的并发请求须要访问这个 key,从而形成了数据库的压力。算法

解决方案

解决缓存击穿的方法和解决缓存雪崩的方法很相似:sql

  • 加锁,保证单线程访问缓存。这样第一个请求到达数据库后就会从新写入缓存,后续的请求就能够直接读取缓存。
  • 内存容许的状况下,能够将缓存设置为永不失效。
缓存穿透

缓存穿透和上面两种现象的本质区别就是这时候访问的数据不但在 Redis 中不存在,并且在数据库中也不存在,这样若是并发过大就会形成数据源源不断的到达数据库,给数据库形成极大压力。数据库

解决方案

对于缓存穿透问题,加锁并不能起到很好地效果,由于自己 key 就是不存在,因此即便控制了<typo data-origin="地" ignoretag="true">线</typo>程的访问数,可是请求仍是会源源不断的到达数据库。数组

解决缓存穿透问题通常能够采用如下方案配合使用:缓存

  • 接口层进行校验,发现非法的 key 直接返回。好比数据库中采用的是自增 id,那么若是来了一个非整型的 id 或者负数 id 能够直接返回,或者说若是采用的是 32 位 uuid,那么发现 id 长度不等于 32 位也能够直接返回。
  • 将不存在的数据也进行缓存,能够直接缓存一个空或者其余约定好的无效 value。采用这种方案最好将 key 设置一个短时间失效时间,不然大量不存在的 key 被存储到 Redis 中,也会占用大量内存。
布隆过滤器(Bloom Filter)

针对上面缓存穿透的解决方案,咱们思考一下:假如一个 key 能够绕过第 1 种方法的校验,而此时有大量的不存在 key 被访问(如 1 亿个或者 10 亿个),那么这时候所有存储到内存中,是不太现实的。数据结构

那么有没有一种更好的解决方案呢?这就是咱们接下来要介绍的布隆过滤器,布隆过滤器就能够用尽量小的空间存储尽量多的数据。

什么是布隆过滤器

布隆过滤器(Bloom Filter)是由布隆在 1970 年提出的。它其实是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。

布隆过滤器能够用于检索一个元素是否在一个集合中。它的优势是空间效率和查询时间都比通常的算法要好得多,缺点是有必定的误识别率并且删除困难。

位图(Bitmap)

Redis 当中有一种数据结构就是位图,布隆过滤器其中重要的实现就是位图的实现,也就是位数组,而且在这个数组中每个位置只有 0 和 1 两种状态,每一个位置只占用 1 个字节,其中 0 表示没有元素存在,1 表示有元素存在。以下图所示就是一个简单的布隆过滤器示例(一个 key 值通过哈希运算和位运算就能够得出应该落在哪一个位置):

面试官:如何从10亿数据中快速判断是否存在某一个元素?_架构
image
哈希碰撞

上面咱们发现,lonely和wolf落在了同一个位置,这种不一样的key值通过哈希运算后获得相同值的现象就称之为哈希碰撞。发生哈希碰撞以后再通过位运算,那么最后确定会落在同一个位置。

若是发生过多的哈希碰撞,就会影响到判断的准确性,因此为了减小哈希碰撞,咱们通常会综合考虑如下 2 个因素:

  • 增大位图数组的大小(位图数组越大,占用的内存越大)。
  • 增长哈希函数的次数(同一个 key 值通过 1 个函数相等了,那么通过 2 个或者更多个哈希函数的计算,都获得相等结果的几率就天然会下降了)。

上面两个方法咱们须要综合考虑:好比增大位数组,那么就须要消耗更多的空间,而通过越多的哈希计算也会消耗 cpu 影响到最终的计算时间,因此位数组到底多大,哈希函数次数又到底须要计算多少次合适须要具体状况具体分析。

布隆过滤器的 2 大特色

下图这个就是一个通过了 2 次哈希函数获得的布隆过滤器,根据下图咱们很容易看到,假如咱们的 Redis 根本不存在,可是 Redis 通过 2 次哈希函数以后获得的两个位置已是 1 了(一个是 wolf 经过 f2 获得,一个是 Nosql 经过 f1 获得,这就是发生了哈希碰撞,也是布隆过滤器可能存在误判的缘由)。

面试官:如何从10亿数据中快速判断是否存在某一个元素?_缓存_02
image

因此经过上面的现象,咱们从布隆过滤器的角度能够得出布隆过滤器主要有 2 大特色:

  1. 若是布隆过滤器判断一个元素存在,那么这个元素可能存在
  2. 若是布隆过滤器判断一个元素不存在,那么这个元素必定不存在

而从元素的角度也能够得出 2 大特色:

  1. 若是元素实际存在,那么布隆过滤器必定会判断存在
  2. 若是元素不存在,那么布隆过滤器可能会判断存在

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>

  1. 新建一个测试类 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));
    }
}

运行以后的结果为:

面试官:如何从10亿数据中快速判断是否存在某一个元素?_缓存_03
image

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

这个 3% 的误判率是如何来的呢?咱们进入建立布隆过滤器的 create 方法,发现默认的fpp就是 0.03:

面试官:如何从10亿数据中快速判断是否存在某一个元素?_java_04
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>

  1. 新建一个带有计数器的布隆过滤器 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 存在的三种问题:缓存雪崩,缓存击穿和缓存穿透。并分别对每种问题的解决方案进行了描述,最后着重介绍了缓存穿透的解决方案:布隆过滤器。原生的布隆过滤器不支持删除,可是能够引入一个计数器实现带有计数器的布隆过滤器来实现删除功能,同时在最后也提到了,带有计数器的布隆

上一篇: kubernetes控制器