分布式缓存的基本原理

随着互联网的发展，用户规模和数据规模越来越大，对系统的性能提出了更高的要求，缓存就是其中一个非常关键的组件，从简单的商品秒杀，到全民投入的双十一，我们都能见到它的身影。

分布式缓存首先也是缓存，一种性能很好但是相对稀缺的资源，和我们在课本上学习的CPU缓存原理基本相同，CPU是用性能更好的静态RAM来为性能一般的DRAM加速，分布式缓存则是通过内存或者其他高速存储来加速，但是由于用到了分布式环境中，涉及到并发和网络的问题，所以会更加复杂一些，但是有很多方面的共性，比如缓存淘汰策略。计算机行业有一句鼎鼎大名的格言就指出了缓存失效的复杂性。

There are only two hard things in Computer Science: cache invalidation and naming things (计算科学中最难的两件事是命名和缓存失效)
– Phil Karlton

本文包括四个部分，分布式缓存的更新模式、失效机制、淘汰策略和常见问题及解决方案，重点是围绕缓存的通用原理和实现来说明，不针对某个具体的系统，算法部分主要采用伪代码说明。

缓存的更新模式

Cache Aside模式

1. 读取失效：cache数据没有命中，查询DB，成功后把数据写入缓存
2. 读取命中：读取cache数据
3. 更新：把数据更新到DB，失效缓存

图示

// Read
data = cache.get(id);
if (data == null) {
    data = db.get(id);
    cache.put(id, data);
}


// Write
db.save(data);
cache.invalid(data.id);

为什么更新不直接写缓存？

为了降低并发情况下的数据不一致发生概率（cache aside无法完全避免数据不一致，只能降低发生的概率，如果需要数据强一致可以考虑使用分布式事务），如下图所示

Thread-A: Write DB Version(A)
Thread-B: Write DB Version(B)
Thread-B: Write Cache Version(B)
Thread-A: Write Cache Version(A) -- 数据库结果是B，缓存里面变成A了

这种情况下如果改为失效的话数据不一致的情况能够避免

Thread-A: Write DB Version(A)
Thread-B: Write DB Version(B)
Thread-B: Expire Cache
Thread-A: Expire Cache -- 两种情况只失效缓存，下次读操作会把db的最新值刷新到缓存中。

Read/Write Through模式

缓存代理了DB读取、写入的逻辑，可以把缓存看成唯一的存储。

# [xxx] 表示一个组件
# 箭头表示数据方向
Read:
Client <-- [Cache <-- DB]

Write:
Client --> [Cache --> DB]

Write Behind Caching(Write Back)模式

这种模式下所有的操作都走缓存，缓存里的数据再通过异步的方式同步到数据库里面。所以系统的写性能能够大大提升了。

缓存失效策略

一般而言，缓存系统中都会对缓存的对象设置一个超时时间，避免浪费相对比较稀缺的缓存资源。对于缓存时间的处理有两种，分别是主动失效和被动失效。

主动失效

主动失效是指系统有一个主动检查缓存是否失效的机制，比如通过定时任务或者单独的线程不断的去检查缓存队列中的对象是否失效，如果失效就把他们清除掉，避免浪费。主动失效的好处是能够避免内存的浪费，但是会占用额外的CPU时间。

被动失效

被动失效是通过访问缓存对象的时候才去检查缓存对象是否失效，这样的好处是系统占用的CPU时间更少，但是风险是长期不被访问的缓存对象不会被系统清除。

缓存淘汰策略

缓存淘汰，又称为缓存逐出(cache replacement algorithms或者cache replacement policies)，是指在存储空间不足的情况下，缓存系统主动释放一些缓存对象获取更多的存储空间。

对于大部分内存型的分布式缓存（非持久化），淘汰策略优先于失效策略，一旦空间不足，缓存对象即使没有过期也会被释放。这里只是简单介绍一下，相关的资料都很多，一般LRU用的比较多，可以重点了解一下。

FIFO

先进先出（First In First Out）是一种简单的淘汰策略，缓存对象以队列的形式存在，如果空间不足，就释放队列头部的（先缓存）对象。一般用链表实现。

LRU

最近最久未使用（Least Recently Used），这种策略是根据访问的时间先后来进行淘汰的，如果空间不足，会释放最久没有访问的对象（上次访问时间最早的对象）。比较常见的是通过优先队列来实现。

LFU

最近最少使用（Least Frequently Used），这种策略根据最近访问的频率来进行淘汰，如果空间不足，会释放最近访问频率最低的对象。这个算法也是用优先队列实现的比较常见。

分布式缓存的常见问题

缓存穿透

• DB中不存在数据，每次都穿过缓存查DB，造成DB的压力。一般是网络攻击
• 解决方案：放入一个特殊对象（比如特定的无效对象，当然比较好的方式是使用包装对象）

代码示例

# 我们先看看最简单的青铜姿势
value = cache.get(key)
if value is None:
    value = db.get(key)
    # 由于value为空，实际上缓存并没有写进去，一旦这个key成为热点，db的压力将会极大
    cache.put(key, value, expire)
    return value
else:
    return value

# 简单优化一下，升级成为白银姿势
wrapped_value = cache.get(key)
if wrapped_value is None:
    value = db.get(key)
    # 即使是空对象也通过包装对象放到缓存，当然考虑到空间还可以采用特殊值（比如-1代表不存在）的方式
    cache.put(key, wrapped_value(value), expire)
    return wrapped_value.value
else:
    return wrapped_value.value

缓存击穿

• 在缓存失效的瞬间大量请求，造成DB的压力瞬间增大
• 解决方案1：更新缓存时使用分布式锁锁住服务，防止请求穿透直达DB
• 解决方案2：使用布隆过滤器（bloom filter）过滤，可以过滤掉大部分缓存中不存在的key，但是需要注意布隆过滤器并不能过滤所有不存在的key，用于大部分的业务场景足够了，但是有可能无法过滤网络攻击（通过构造出可以不被布隆过滤器过滤但是缓存中不存在的key）。
• 当然，以上两种方案也可以结合起来使用。

# 白银姿势
wrapped_value = cache.get(key)
if wrapped_value is None:
    value = db.get(key)
    # 在写入缓存之前，大量的请求突然涌入，db瞬间被打垮
    cache.put(key, wrapped_value(value), expire)
    return wrapped_value.value
else:
    return wrapped_value.value
    
# 在白银姿势的基础上我们再优化成黄金姿势
wrapped_value = cache.get(key)
if wrapped_value is None:
    # 查db之前加一把锁
    while wrapped_value is None:
        if try_lock(key):
            value = db.get(key)
            cache.put(key, wrapped_value(value), expire)
            return wrapped_value.value
        else:
            # 等待10毫秒之后重试
            sleep(0.01)
            wrapped_value = cache.get(key)
    return wrapped_value.value
else:
    return wrapped_value.value

缓存雪崩

• 大量缓存设置了相同的失效时间，同一时间失效，造成服务瞬间性能急剧下降
• 解决方案：缓存时间使用基本时间加上随机时间

# 通过随机失效时间登上王者姿势
wrapped_value = cache.get(key)
if wrapped_value is None:
    # 查db之前加一把锁
    while wrapped_value is None:
        if try_lock(key):
            value = db.get(key)
            # 嗯，就是一个随机失效时间，最好是在某个区间
            cache.put(key, wrapped_value(value), random_expire())
            return wrapped_value.value
        else:
            # 等待10毫秒之后重试
            sleep(0.01)
            wrapped_value = cache.get(key)
    return wrapped_value.value
else:
    return wrapped_value.value

参考资料

• 缓存的三种方案