面试题：缓存设计之实时推荐引擎缓存穿透应对

Question

在实时推荐引擎的缓存系统中，缓存穿透是一个常见问题，即查询一个不存在的数据，每次都绕过缓存直接查询数据库，给数据库带来压力。请详细阐述你会如何设计缓存机制来有效避免缓存穿透问题，包括可能用到的数据结构和算法。

Answer 1

1. 布隆过滤器（Bloom Filter）

• 原理：布隆过滤器是一种概率型数据结构，它通过多个哈希函数将一个元素映射到一个位数组的不同位置并置为1。当查询某个元素时，只要对应位置不全为1，就可判定该元素一定不存在；若全为1，则大概率存在（存在误判）。
• 数据结构：位数组（Bit Array）。位数组的大小会影响误判率，一般来说，位数组越大，误判率越低。
• 算法：
  • 插入：对于要插入的元素，通过多个哈希函数计算出在位数组中的位置，将这些位置置为1。
  • 查询：对要查询的元素，用相同的哈希函数计算位置，若对应位置不全为1，则元素不存在；若全为1，需进一步查数据库确认，因为存在误判可能。
• 在缓存中的应用：在缓存之前先使用布隆过滤器进行过滤，若布隆过滤器判定数据不存在，就直接返回，不再查询数据库，减少数据库压力。

2. 空值缓存

• 原理：当查询数据库发现数据不存在时，将这个查询条件对应的空值也缓存起来，并设置较短的过期时间。这样下次查询同样的数据时，直接从缓存获取空值，避免查询数据库。
• 数据结构：可以使用常见的缓存数据结构，如Redis的键值对结构。键为查询条件，值为空值标识（如null或特定的字符串）。
• 算法：
  • 查询：先查缓存，若缓存中有值，直接返回；若缓存无值，查数据库。
  • 更新：数据库查询到数据为空时，将空值缓存起来；若查询到数据，更新缓存中的数据值。

3. 缓存雪崩预防

• 原理：缓存雪崩是指大量缓存同时过期，导致大量请求直接访问数据库。通过设置缓存的过期时间为一个随机值，避免大量缓存同时过期。
• 数据结构：同普通缓存数据结构，如Redis的键值对。
• 算法：在设置缓存过期时间时，使用一个基础过期时间加上一个随机的偏移量。例如，基础过期时间为T，随机偏移量为[0, ΔT]内的随机值，最终过期时间为T + random(0, ΔT)。这样可以分散缓存过期时间，防止大量缓存同时失效引发类似缓存穿透对数据库造成的压力。