服务端缓存初探｜uunnfly's blog

缓存，在计算机世界中很早就出现了，例如在CPU中，就有一级缓存，二级缓存，三级缓存。根据局部性原理（时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。), 使用缓存能让我们以较低的成本，获得较高的收益（运行速度等）。在我们平时上网过程中，也处处都存在缓存，比如浏览器或客户端本身就带有浏览资源的缓存，DNS查询中也会有DNS缓存，看电影时看的是CDN里的缓存等等。这篇文章谈论的是后台开发接触密切的服务端缓存。

缓存属性

我们先思考一个问题：如何判断缓存是好还是不好？显然需要一定的指标去判断，而不能仅仅依靠人的感觉。下面有几个核心指标可以反映缓存的性能与特点。

吞吐量：指系统在单位时间内处理请求的数量，通常使用OPS值（每秒钟可进行的操作次数）评价，反映缓存对并发读写的能力。
命中率：缓存结果请求成功次数/请求总次数，反映缓存价值的高低。如果命中率很低，缓存使用的意义就不大。

我们在对缓存进行选型时，以下两点也比较重要：

分布式支持：ConcurrentHashMap也是一种缓存，但是无法分布式。memcached本身不支持分布式，但是是一种“进程外”的缓存，因此客户端可以实现伪分布式。而Redis本身就支持分布式。
扩展功能：例如过期时间与过期策略的设定，淘汰策略，命中率、吞吐量统计等管理功能。

淘汰策略

缓存的容量不是无限的，当空间已满又想put新数据时，需要淘汰掉一部分原有缓存。常见的一般淘汰策略有：

FIFO：先进先出，最先进入缓存的数据将被清除。根据局部性原理，这种策略的表现一般较差，只适合只追求数据时效性的场景。
LRU：淘汰最久最少未使用的数据，此策略适合在处理在短期内大量访问的热点数据，但是也会淘汰那些近期未被访问的热点数据。
LFU：淘汰最不经常使用的数据。LFU记录了每个数据的访问次数，需要淘汰时从访问次数最少的数据开始。LFU能够保留下很久之前的热点数据，但是其热度不会随着时间而下降。而且LFU需要使用额外的访问计数器，降低了吞吐量。

随着人们的要求越来越高，出现了更加复杂的淘汰策略, 例如 Caffeine 使用了一种名为 W-TinyLFU 的淘汰策略，这种淘汰策略主要针对LFU的两个缺点：热点不能随时间改变，以及需要额外空间记录访问次数。

针对需要额外记录访问次数，W-TinyLFU使用Sketch分析访问数据(Sketch是指用少量数据来估算全部数据的特征)，Caffeine使用Count–min sketch 来实现此功能。count-min sketch可看作布隆过滤器的变种, 布隆过滤器只用一个hash函数，而Count-min sketch使用多个hash函数，并且必须互不相同。

Count-min sketch结构：

添加元素：当添加元素时，每行使用不同的hash函数计算，将对应的位置 + 1

查询元素(出现次数)：分别计算各hash值，取其中的最小值，故称为Count-min
为了解决LFU不便于处理随时间变化的热度变化问题，W-TinyLFU采用了基于“滑动时间窗”的热度衰减算法，简单理解就是每隔一段时间，便会把计数器的数值减半，以此解决“旧热点”数据难以清除的问题。
对于某些近期内热点但是绝对频率不高的数据，比如日志，近期的日志可能查看次数较多，但是过了这段时间次数很少，因此可以结合LRU的特点。W-TinyLFU将缓存分为两大块，第一块叫Window Cache，当第一块满时把低价值的淘汰到第二块Main Cache，Main Cache根据数据的访问频繁程度分为不同的段，单独某一段局部来看又是基于LRU策略去实现的（称为Segmented LRU）

可以从基准测试结果看出，W-TinyLfu效果命中率很高，接近于Optimal.

缓存分类

进程内缓存

这类缓存的特点是在进程内提供服务，没有网络开销，效率较高，但是一般只能单机使用。

ConcurrentHashMap

对于简单的缓存需求，我们使用ConcurrentHashMap就能胜任，以下是一个使用例子，提供过期时间功能，但是不支持淘汰策略，无限制使用会导致内存溢出。

LocalCache.java: 储存value与过期时间

public class LocalCache {
	private long expiry;
	private long timestamp;
	private Object value;

	public LocalCache(Object value, long expiry) {
		this.expiry = expiry;
		this.timestamp = System.currentTimeMillis() + expiry;
		this.value = value;
	}
    //省略getter与setter
}

LocalCacheUtil.java: 本地缓存工具类，持有一个concurrentHashMap

public class LocalCacheUtil {
    private static final ConcurrentMap<String, LocalCache> CACHE_MAP = new ConcurrentHashMap<>();
    private static long ININT_EXPIRE = 60 * 60 * 1000;

    public <T> T get(Class<T> cls, String key) {
        LocalCache c = CACHE_MAP.get(key);;
        if (c == null) {
            return null;
        } else {
            if (c.getTimestamp() >= System.currentTimeMillis()) {
                return (T) c.getValue();
            }
            CACHE_MAP.remove(key);//已过期，移除数据
            return null;
        }
    }

    public void put(String key, Object value, long expiry) {
        LocalCache c = new LocalCache(value, expiry);
        CACHE_MAP.put(key, c);
    }

    public void put (String key, Object value) {
        put (key, value, ININT_EXPIRE);
    }

    public void remove(String key) {
        CACHE_MAP.remove(key);
    }
}

guava cache与caffeine

Guava Cache是Google开源的Java重用工具集库Guava里的一款缓存工具，使用多个segments方式的细粒度锁。在guava cache中对于写操作直接加锁，对于读操作，如果读取的数据没有过期，且已经加载就绪，不需要进行加锁，如果没有读到会再次加锁进行二次读，如果还没有需要进行缓存加载。Guava Cache拥有失效策略，自动刷新等功能，其本质是对LRU的封装。

Caffeine 是一个高性能、出色的缓存类库。淘汰策略使用上面介绍的W-TinyLFU，表现优秀。而且对于读操作伴随的各种其他操作，比如Sketch结构的修改, 对过期键的处理，Guava Cache是同步执行，因此吞吐量不可避免地会收到影响。而Caffeine选择用日志异步的方式处理。将对数据的读、写过程看作是日志（即对数据的操作指令）的提交过程。

在Caffeine的实现中，设有专门的环形缓存区（Ring Buffer，也常称作Circular Buffer）来记录由于数据读取而产生的状态变动日志。为进一步减少竞争，Caffeine给每条线程（对线程取Hash，哈希值相同的使用同一个缓冲区）都设置一个专用的环形缓冲。

分布式缓存

分布式缓存可分为两类，一种是”复制式缓存“，一种是”集中式缓存“。复制式缓存在每个节点都有一份副本，进程读取时没有网路消耗，但是有数据变更，写入，删除时需要通知其他所有节点，随着节点数量上升，复制性能大大下降。这类缓存如JBossCache已经基本退出历史舞台。集中式缓存是目前的主流缓存形式，读，写都需要网络连接，而且在进程之外，没有节点数量上升带来性能下降的困扰，又可以为异构语言的应用程序提供服务，比如Redis使用C语言编写，可以为Java，Python等语言编写的程序提供缓存服务，减少了耦合增加了复用性。

Memcached

memcached是一个高效的分布式内存cache，只支持内存存储，只支持key-value形式的存储，功能较为简单，适合简单业务场景下的缓存。

在memecached中有两个较为关键的概念：slab和chunk。slab是一个内存块，memcached每次申请都是一个slab，slab的大小固定为1M。slab内有多个chunk，同一个slab内的chunk大小相等，memcached将slab分为多个class来管理，拥有相同chunk大小的slab属于同一个class。当有新数据要存储时，memcached选择最合适的chunk大小，如果对应的class下的slab用完了，会再申请一个slab。如果数据超过1M，memcached会将其切割，放入多个chunk中。

图8 memcached内存结构图

伪分布式

memcached服务端并不支持分布式，但是集中式缓存的特点使其可以借助客户端实现伪分布式。

新增数据：memcache客户端计算hash得到目标服务器地址，再新增其数据至指定节点。

查询数据：memcache客户端计算hash得到目标服务器地址，再从指定节点查询。

一般需要配合一致性Hash算法以免节点变更时导致所有key都要重新分布。

新增数据

查询数据

一致性Hash

一致性Hash中的一致性是指当物理节点发生变更时，只影响这个节点相关的键，而不会影响其他节点的键。

首先构造一个长度为2 ^ 32的哈希环，然后把物理节点经过hash后放入环中对应位置，当有需要查询key对应的节点在哪时，计算key在环上的位置后，顺时针寻找节点，第一个即为key所属的节点。假设某个node下线，也不会导致所有的key都要重新分布。

为了使key分布更均匀，可以给物理节点几个虚拟节点，分布在环上的不同地方。

Redis

Redis是一个远程内存数据库（非关系型数据库），支持多种数据类型（string，hash，set，list，sorted set），并且自带分布式功能，且能持久化，功能强大。

服务器与Sentinel(哨兵)系统

图11 Redis分布式集群图2

Redis cluster

Redis Cluster是一个实现了分布式且允许单点故障的Redis高级版本, 集群通过分片（sharding）来进行数据共享，并提供复制和故障转移功能。

集群通过分片的方式来保存数据库中的键值对：集群的整个数据库被分为16384个槽（slot），数据库中的每个键都属于这16384个槽的其中一个，集群中的每个节点可以处理0个或最多16384个槽。

当数据库中的16384个槽都有节点在处理时，集群处于上线状态（ok）；相反地，如果数据库中有任何一个槽没有得到处理，那么集群处于下线状态（fail）

对于客户端请求的key，根据公式HASH_SLOT=CRC16(key) mod 16384，计算出映射到哪个分片上，然后Redis会去相应的节点进行操作

为什么是16384？简单来说够用且心跳包成本低，详见为什么Redis集群有16384个槽

多级缓存

进程内缓存与分布式缓存并不矛盾，可以搭配使用。如下图所示，把进程内缓存作为一级缓存，分布式缓存作为二级缓存，首先访问一级缓存，如果查询失败则访问二级缓存，若二级缓存查询成功，则返回数据并回填至一级缓存；若二级缓存查询失败，则向最终数据源查询并回填至一级，二级缓存。

上述过程较为繁杂，如果由开发人员手动多次查询，填充，代码入侵性强，复杂易出错，应当提供一二级缓存联合查询的封装好的接口。

还有一个问题是如果数据发生更新，怎么通知各节点的进程内缓存更新？一种设计原则是“变更以分布式缓存中的数据为准，访问以进程内缓存的数据优先”, 借助于Redis的pub/sub功能，让应用程序订阅Redis的变更通知，当数据变更时向Redis发布这一消息，Redis再通知其他应用程序，让其删除进程内缓存。