面试题：缓存设计之缓存穿透高级难度题

Question

假设你正在开发一个高并发的电商系统，商品ID为数字类型，现出现了缓存穿透问题。在不影响原有业务逻辑性能的前提下，你会如何设计一个高效的布隆过滤器来解决该问题？请详细描述布隆过滤器的参数设置、数据结构及使用流程。

Answer 1

布隆过滤器参数设置

1. 预估数据量 n：首先要预估电商系统中商品 ID 的数量。比如预计系统中有 1000 万个商品，那么 n = 10000000。
2. 误判率 p：误判率指的是布隆过滤器将一个不存在的元素误判为存在的概率。对于电商系统，通常选择一个较低的误判率，如 p = 0.001（0.1%）。
3. 哈希函数个数 k：根据公式 k = (n / m) * ln(1 / 2)，以及 m = - (n * ln(p)) / (ln(2) ^ 2) 来计算。
   • 先计算布隆过滤器的位数组大小 m，以 n = 10000000，p = 0.001 为例，m = - (10000000 * ln(0.001)) / (ln(2) ^ 2) ≈ 19188309。
   • 再计算哈希函数个数 k，k = (n / m) * ln(1 / 2)，带入数值可得 k ≈ 7。

数据结构

布隆过滤器主要由一个位数组（bit array）和多个哈希函数组成。

1. 位数组：是一个长度为 m 的二进制数组，初始值全部为 0。如上述计算 m = 19188309，那么位数组就有 19188309 个 bit 位。
2. 哈希函数：选择 k 个不同的哈希函数，如常用的 MurmurHash 等。每个哈希函数都能将输入的商品 ID 映射到 [0, m - 1] 的范围内，用于确定位数组中的位置。

使用流程

1. 初始化：初始化布隆过滤器，设置好位数组大小 m 和哈希函数个数 k。
2. 添加数据：当一个商品 ID 进入系统时，通过 k 个哈希函数分别计算出 k 个哈希值，对应到位数组的 k 个位置，将这 k 个位置的值设为 1。例如商品 ID = 123，经过 7 个哈希函数计算得到的位置分别为 100、200、300、400、500、600、700，那么将位数组中这 7 个位置的值设为 1。
3. 查询数据：当查询一个商品 ID 是否存在时，同样通过 k 个哈希函数计算出 k 个哈希值，对应到位数组的 k 个位置。如果这 k 个位置的值全部为 1，则认为该商品 ID 可能存在（存在误判可能）；如果其中有任何一个位置的值为 0，则该商品 ID 一定不存在。这样在高并发电商系统中，当查询商品 ID 时，先通过布隆过滤器过滤，不存在的直接返回，避免查询底层存储，解决缓存穿透问题。