缓存相关知识整理汇总

20 minute
CS
, , , ,

缓存分类

缓存可分为本地缓存和分布式缓存：

本地缓存：指的是在应用中的缓存组件，其最大的优点是应用和 cache 是在同一个进程内部，请求缓存非常快速，没有过多的网络开销等，在单应用不需要集群支持或者集群情况下各节点无需互相通知的场景下使用本地缓存较合适；同时，它的缺点也是应为缓存跟应用程序耦合，多个应用程序无法直接的共享缓存，各应用或集群的各节点都需要维护自己的单独缓存，对内存是一种浪费。常见的本地缓存有：

  • Ehcache
  • Guava Cache
  • Caffeine

Caffeine 是基于 JAVA8 的高性能缓存库。并且在 Spring5 (Springboot 2.x) 后，Spring 官方放弃了 Guava，而使用了性能更优秀的 Caffeine 作为默认缓存组件。

分布式缓存：指的是与应用分离的缓存组件或服务，其最大的优点是自身就是一个独立的应用，与本地应用隔离，多个应用可直接的共享缓存。常见的分布式缓存有：

  • Redis
  • Memcached

Memcached 不支持灾难恢复，对分布式支持不如 Redis，已经基本被 Redis 取代，下面着重记录 Redis 相关要点。

Redis

线程模型

Redis 内部使用文件事件处理器 file event handler ，这个文件事件处理器是单线程的，所以 Redis 才叫做单线程的模型。它采用 IO 多路复用机制同时监听多个 socket，将产生事件的 socket 压入内存队列中，事件分派器根据 socket 上的事件类型来选择对应的事件处理器进行处理。

文件事件处理器的结构包含 4 个部分：

  • 多个 socket
  • IO 多路复用程序
  • 文件事件分派器
  • 事件处理器（连接应答处理器、命令请求处理器、命令回复处理器）

单线程模型效率高的原因:

  • 纯内存操作
  • 核心是基于非阻塞的 IO 多路复用机制
  • 单线程反而避免了多线程的频繁上下文切换问题，预防了多线程可能产生的竞争问题

Redis 6.0 开始引入多线程，Redis 在有些方面，单线程已经不具有优势了。因为读写网络的 Read/Write 系统调用在 Redis 执行期间占用了大部分 CPU 时间，如果把网络读写做成多线程的方式对性能会有很大提升。

Redis 的多线程部分只是用来处理网络数据的读写和协议解析，执行命令仍然是单线程。

通信流程

多个 socket 可能会并发产生不同的操作，每个操作对应不同的文件事件，但是 IO 多路复用程序会监听多个 socket，会将产生事件的 socket 放入队列中排队，事件分派器每次从队列中取出一个 socket，根据 socket 的事件类型交给对应的事件处理器进行处理。

持久化机制

  • RDB：RDB 持久化机制，是对 Redis 中的数据执行周期性的持久化。
  • AOF：AOF 机制对每条写入命令作为日志，以 append-only 的模式写入一个日志文件中，在 Redis 重启的时候，可以通过回放 AOF 日志中的写入指令来重新构建整个数据集。

Redis 支持同时开启开启两种持久化方式，用 AOF 来保证数据不丢失，作为数据恢复的第一选择；用 RDB 来做不同程度的冷备，在 AOF 文件都丢失或损坏不可用的时候，还可以使用 RDB 来进行快速的数据恢复。

主从架构

主从(master-slave)架构，一主多从实现高并发，主节点负责写，并且将数据复制到其它的 slave 节点，从节点负责读。所有的读请求全部走从节点。Redis 在主从的基础上通过哨兵机制切换主从实现高可用。

主从复制流程大致是，初次连接全量复制，通过 RDB 快照 + 增量复制机制完成，如果复制过程中断线也会采用增量复制完成（可通过 heartbeat 机制确认连接情况）。

哨兵机制大致是，哨兵监控 master，如果一个哨兵觉得 master 宕机了，则是主观宕机(sdown)，超过 quorum 个认为这是客观宕机(odown)，此时选举出新 master 候选人，这个人得到 majority 个哨兵的认可就可以成为 master。

  • quorum 的计算公式为：quorum = (哨兵节点数/2) + 1
  • majority 是选举机制中的一个值，可以理解为选票，majority >= quorum 并且 majority > 哨兵数量的一半
  • 选举机制中，候选者是判断哪个节点下线的哨兵，候选者投给自己，其他人投给收到的第一个申请的人

关于选举机制带来的“脑裂”问题，其实就是出现 2 个 master，原 master 因为网络问题脱离，而其他人开始选新 master，后来原 master 恢复，导致出现 2 个 master。原 master 未进行主从切换复制数据，清空数据并成为 slave，导致丢失数据。通过限制 master 的 slave 个数大于 0 和延迟时间不超一定时间即可避免这个问题。

集群模式

Redis cluster，主要是针对海量数据+高并发+高可用的场景。Redis cluster 支撑 N 个 Redis master node，每个 master node 都可以挂载多个 slave node。

集群模式下，各个 master 存储不同的数据，采用一致性哈希算法来计算 key 的目标 master。具体来说，Redis 集群通过一致性哈希和槽（slot）机制来管理和定位键。

Redis 集群将整个键空间分为 16384 个槽。每个键通过 CRC16 算法计算哈希值，然后对 16384 取模，决定其属于哪个槽。集群中的每个 master 负责若干个槽。

对于普通的哈希算法，一旦其中一个 master 挂了，将会影响其他大多 master 的哈希，导致大量 key 需要重新分布，采用一致性哈希，可以将影响降低到单个 master，一致性哈希还采用了虚拟节点的方法，实现 key 的均匀分布：

数据结构

  • String: SDS，基于 C 字符串的动态长度可变字符串。
  • List: QuickList(LinkedList+ZipList)
  • Set: HashTable/IntSet。如果一个集合只包含整数值元素，且元素数量少于 512 个时，会使用 Intset。
  • Hash: HashTable/ZipList。如果保存的所有键值对的键和值的字符串长度都小于 64 字节且数量小于 512 个则采用 ZipList。
  • Zset: ZipList/SkipList+Dict。当 Zset 保存的键值对数量少于 128 个且每个元素的长度小于 64 字节时使用 ZipList，否则使用 SkipList。

缓存过期策略

缓存的存储空间有限制，当缓存空间被用满时，如何保证在稳定服务的同时有效提升命中率？这就由缓存清空策略来处理，设计适合自身数据特征的清空策略能有效提升命中率。常见的一般策略有：

FIFO(first in first out)：

先进先出策略，最先进入缓存的数据在缓存空间不够的情况下（超出最大元素限制）会被优先被清除掉，以腾出新的空间接受新的数据。策略算法主要比较缓存元素的创建时间。在数据实效性要求场景下可选择该类策略，优先保障最新数据可用。

LFU(less frequently used)：

最少使用策略，无论是否过期，根据元素的被使用次数判断，清除使用次数较少的元素释放空间。策略算法主要比较元素的hitCount（命中次数）。在保证高频数据有效性场景下，可选择这类策略。

LRU(least recently used)：

最近最少使用策略，无论是否过期，根据元素最后一次被使用的时间戳，清除最远使用时间戳的元素释放空间。策略算法主要比较元素最近一次被get使用时间。在热点数据场景下较适用，优先保证热点数据的有效性。

除此之外，还有一些简单策略比如：

  • 根据过期时间判断，清理过期时间最长的元素；
  • 根据过期时间判断，清理最近要过期的元素；
  • 随机清理；
  • 根据关键字（或元素内容）长短清理等。

Redis 过期策略是：定期删除+惰性删除。

定期删除，指的是 Redis 默认是每隔 100ms 就随机抽取一些设置了过期时间的 key，检查其是否过期，如果过期就删除。

惰性删除，就是在获取 key 的时候，如果此时 key 已经过期，就删除，不会返回任何东西。

如果定期删除漏掉了很多过期 key，然后你也没及时去查，也就没走惰性删除，此时大量过期 key 堆积在内存里，导致 Redis 内存块耗尽了，所以还需要走内存淘汰机制：

  • noeviction: 当内存不足以容纳新写入数据时，新写入操作会报错；
  • allkeys-lru：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的 key（这个是最常用的）。
  • allkeys-random：当内存不足以容纳新写入数据时，在键空间中，随机移除某个 key；
  • volatile-lru：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，移除最近最少使用的 key。
  • volatile-random：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，随机移除某个 key。
  • volatile-ttl：当内存不足以容纳新写入数据时，在设置了过期时间的键空间中，有更早过期时间的 key 优先移除。

手写 LRU，很简单，指定好最大容量，使用 python 的有序字典即可，获取 key 时重新入典，放 key 时如果存在则重新入典，如果满了就移除最空闲数据。

 1import collections
 2
 3class LRUCache:
 4
 5    def __init__(self, capacity):
 6        self.capacity = capacity
 7        self.queue = collections.OrderedDict()
 8
 9    def get(self, key):
10        if key not in self.queue:
11            return -1
12        value = self.queue.pop(key)
13        self.queue[key] = value
14        return self.queue[key]
15
16    def put(self, key, value):
17        if key in self.queue:
18            self.queue.pop(key)
19        elif len(self.queue.items()) == self.capacity:
20            self.queue.popitem(last=False)
21        self.queue[key] = value

缓存问题

缓存雪崩（宕机）

缓存系统宕机，大量请求打到数据库上。

解决方案如下：

  • 事前：Redis 高可用，主从+哨兵，Redis cluster，避免全盘崩溃。
  • 事中：本地 ehcache 缓存 + hystrix 限流&降级，避免 MySQL 被打死。
  • 事后：Redis 持久化，一旦重启，自动从磁盘上加载数据，快速恢复缓存数据。

缓存穿透（绕过）

安全攻击，利用某些数据值的特点，大量请求一定不在数据库中的数据，导致缓存无法生成一直请求数据库。

数据保密，空值缓存保护，布隆过滤器拦截等方式来解决。

关于布隆过滤器：

布隆过滤器是一个很长的二进制向量和一系列随机映射函数，用于检索一个元素是否在一个集合中。

它的空间效率和查询时间都远远超过一般的算法，但是有一定的误判率 （函数返回 true , 意味着元素可能存在，函数返回 false ，元素必定不存在）。

布隆过滤器的四个核心属性：

  • k : 哈希函数个数
  • m : 位数组长度
  • n : 插入的元素个数
  • p : 误判率

布隆过滤器无法删除元素，但我们可以通过计数布隆过滤器和定时重新构建布隆过滤器两种方案实现删除元素的效果。

使用场景：

缓存失效

缓存失效（击穿），就是说某个 key 非常热点，访问非常频繁，处于集中式高并发访问的情况，当这个 key 在失效的瞬间，大量的请求就击穿了缓存，直接请求数据库。

不同场景下的解决方式可如下：

  • 若缓存的数据是基本不会发生更新的，则可尝试将该热点数据设置为永不过期。
  • 若缓存的数据更新不频繁，且缓存刷新的整个流程耗时较少的情况下，则可采用互斥锁以保证仅少量的请求能请求数据库并重新构建缓存，其余线程则在锁释放后能访问到新缓存。
  • 若缓存的数据更新频繁或者在缓存刷新的流程耗时较长的情况下，可以利用定时线程在缓存过期前主动地重新构建缓存或者延后缓存的过期时间，以保证所有的请求能一直访问到对应的缓存。

并发竞争问题

多个实例要更新同一个 key，可以采用分布式锁来解决竞争问题。

可以基于 zookeeper 实现分布式锁。每个系统通过 zookeeper 获取分布式锁，确保同一时间，只能有一个系统实例在操作某个 key，别人都不允许读和写。

缓存与数据库双写

Cache Aside Pattern: 最经典的缓存+数据库读写的模式。

对于读操作，先读缓存，缓存没有的话，就读数据库，然后取出数据后放入缓存，同时返回响应。

对于写操作，可以先更新数据库，再删除缓存，也可以反过来，两者各有优劣。

（推荐）如果后删缓存，且删除失败，则会出现不一致的问题，可以采用延时双删的方法来确保之后缓存一定被删除，也就是把这个删除的动作在不久之后再执行一次，可通过 MQ 回调的方式完成，确保缓存一定被删除。

如果先删缓存，若删除失败则返回错误停止后续操作，但需要注意在高并发的情况下，某一线程删除缓存后在更新数据库操作未完成的情况下，另一线程如果进行读操作又会更新缓存，导致不一致。在这种情况下，可以通过有序消息队列的方式来确保操作的有序进行。（但这里也可以采用延时双删来完成）

Reference