1. 导读

按照现在流行的互联网分层架构模型，最简单的架构当属Web响应层+DB存储层的架构。从最开始的单机混合部署Web和DB，到后来将二者拆分到不同物理机以避免共享机器硬件带来的性能瓶颈，再随着流量的增长，Web应用变为集群部署模式，而DB则衍生出主从机来保证高可用，同时便于实现读写分离。这一连串系统架构的升级，本质上是为了追求更高的性能，达到更低的延时。

高德作为一款国民级别的导航软件，导航路线的数据质量是由数据中心统一管理的。为了保证数据的鲜度，数据中心需要对不断变化的现实道路数据进行收集，将这些变化的信息保存到数据库中，从而保证导航数据的鲜度；另一方面数据中心内部多部门协调生产数据的时候，会产生海量请求查询最新生产的数据，这就要求数据的管理者要控制数据库连接数，降低请求的响应耗时，同时也需要保证返回数据的实时性。

在平衡数据鲜度和性能之间，高德数据中心针对不同的业务场景使用了不同的策略，达到了数据变更和缓存同步低延迟的目标，同时保障了系统的稳定性。

本文将提及的缓存技术则是提升性能的另一把利刃。然而任何技术都是有可为有可不为，没有最好的技术只有最适合的技术，因此在使用缓存之前，我们也需要了解下引入缓存模块所带来的好处和坏处。

##2. 缘起：为何使用缓存

在应用对外提供服务时，其稳定性受到诸多因素影响，其中比较重要的有CPU、内存、IO(磁盘IO、网络IO)等，这些硬件资源十分宝贵，因此对于那些需要经过复杂计算才能得到结果的，或者需要频繁读取磁盘数据的，最好将结果缓存起来，避免资源的重复消耗。

2.1 CPU瓶颈

如果项目中有很多正则表达式计算，或者某个计算结果是多次中间结果合并后才得出的，且CPU的使用率一直居高不下，那么就可以考虑是否应该将这些结果缓存起来，根据特定Key直接获取Value结果，减少中间链路的传递过程，减少CPU的使用率。

2.2 IO瓶颈

众所周知，从磁盘获取数据受到磁盘转速、寻道速度、磁盘缓冲区大小等诸多因素影响，这些因素决定了磁盘的IOPS，同时我们也知道对于数据的读写来说，CPU的缓存读写速度> 内存的读写速度 >磁盘的读写速度。虽然磁盘内部也配备了缓存以匹配内存的读写速度，但其容量毕竟是有限的，那么当磁盘的IOPS无法进一步提升的时候，便会想到将数据缓存到内存中，从而降低磁盘的访问压力。这一策略常被应用于缓解DB数据库的数据访问压力。

3. 选择本地缓存和分布式缓存的考量点

既然可以使用缓存来提升系统吞吐能力，那么紧接着遇到的问题就是选择本地缓存，还是分布式缓存？什么时候需要使用多级缓存呢？接下来，让我们聊一聊在使用缓存优化项目的过程中，本地缓存和分布式缓存的应用场景和优缺点。

3.1 本地缓存的优缺点和应用场景

统一进程带来了以下优势：

由于本地缓存和应用在同一个进程中，因而其稳定性很高，达到了和应用同生共死的境界；
由于在同一进程中，避免了网络数据传输带来的消耗，所有缓存数据直接从进程所在的内存区域获取即可。

强耦合性也会导致以下这些劣势：

本地缓存和应用共享一片JVM内存，争抢内存资源，无法水平扩展，且可能造成频繁的GC，影响线上应用的稳定性。
由于没有持久化机制，在项目重启后缓存内数据就会丢失，对于高频访问数据，需要对数据进行预热操作。
多份进程内缓存存储着同样的数据内容，造成内存使用浪费。
同样的数据存储在不同的本地机器，数据变化后，很难保证数据的一致性。

结合以上优缺点，我们就会想到，如果有一种数据需要频繁访问，但一旦创建后就轻易不会改变，而且初始创建时就能预估占用的内存空间，那么这种类型的数据无疑是最适合用本地缓存存储了。

既然有了上述的应用场景，我们反观技术开发中的诉求，发现其实很多优秀的框架已经在这样使用了，比如缓存类class的反射信息，包括field、method等。因为class的数量是有限的，且内容不会轻易改变，在使用时无需再使用反射机制，而只需要从本地缓存读取数据即可。

3.2 分布式缓存的优缺点和应用场景

优势：

数据集中存储，消除冗余数据，解决整体内存的占用率，易于维护集群建缓存数据的一致性。
缓存中间件可以对缓存进行统一管理，便于水平扩容。

劣势：

依赖分布式缓存中间件稳定性，一旦挂了，容易造成缓存雪崩；
由于是跨机器获取缓存数据，因此会造成数据传输的网络消耗，以及一些序列化/反序列化的时间开销。

对于上述缺点中，网络耗时等开销是难免的，而且这些操作耗费的时间在可接受范围内，而对于中间件的稳定性则可以通过服务降级、限流或者多级缓存思路来保证。我们主要看中的是它的优点，既然分布式缓存天然能保证缓存一致性，那么我们倾向于将需要频繁访问却又经常变化的数据存放于此。

4. 选择缓存框架的衡量标准

在了解了何时使用缓存以及缓存的优缺点后，我们就准备大刀阔斧开始升级系统了，可紧接着的问题也随之出现，对于本地缓存和分布式缓存，到底应该使用什么框架才是最适用的呢？

现在的技术百花齐放，不同的技术解决的问题侧重点也不同，对于本地缓存来说，如果无资源竞争的代码逻辑，可以使用HashMap，而对于有资源竞争的多线程程序来说，则可以使用ConcurrentHashMap。但以上二者有个通病就是缓存占用只增不减，没有缓存过期机制、也没有缓存淘汰机制。

那么本地缓存是否有更高性能的框架呢？而对于分布式缓存，领域内常用的Redis和Memcache又应该怎样取舍呢？本小节期望通过横向对比的方式，分别给出一个比较通用的缓存框架方案，当然如果有个性化需求的，也可以根据不同缓存框架的特性来取舍。

不同本地缓存框架的横向对比，如下表所示：

总结：如果不需要淘汰算法则选择ConcurrentHashMap，如果需要淘汰算法和一些丰富的API，推荐选择Caffeine。

不同分布式缓存框架的横向对比，如下表所示：

对于存储容量而言，Memcache采用预先分配不同固定大小存储单元的方式，内存空间使用并不紧凑。如果存储Value对象大小最大为1MB，那么当一个对象有1000KB，那么会存储到大小最匹配1MB的单元中，因此会浪费24KB的内存；而Redis是使用之前才去申请空间，内存使用紧凑，但频繁对内存的扩容和收缩，可能造成内存碎片。

总结：由于Redis具有丰富的数据结构能满足不同的业务场景需求，同时Redis支持持久化，能有效地解决缓存中间件重启后的数据预加载问题，因此大多数应用场景中还是推荐使用Redis。

5. 缓存框架使用过程的知识点

不论是本地缓存还是分布式缓存，在使用缓存提升性能的时候，必然会考虑缓存命中率的高低，考虑缓存数据的更新和删除策略，考虑数据一致性如何维护，本小节主要针对以上的问题来分析不同实现方案的优缺点。

5.1 缓存命中率

缓存命中率不仅是系统性能的一个侧面指标，也是优化缓存使用方案的一个重要依据。缓存命中率=请求命中数/请求总数。接下来的若干缓存使用策略所围绕的核心考量点就是在保证系统稳定性的同时，旨在提升缓存命中率。

5.2 缓存更新策略

5.2.1 主动请求DB数据，更新缓存

通过在集群中的每台机器都部署一套定时任务，每隔一段时间就主动向数据库DB请求最新数据，然后更新缓存。这样做的好处是可以避免缓存击穿的风险，在缓存失效前就主动请求加载DB数据，完成缓存数据更新的无缝连接。

但这样做也增加了机器的CPU和内存的占用率，因为即使有若干Key的缓存始终不被访问，可还是会被主动加载加载到内存中。也就是说，提高了业务抗风险能力，但对CPU和内存资源并不友好。

详情可参见下图，分布式缓存中存储着DB中的数据，每隔4.9s就会有定时任务执行去更新缓存，而缓存数据失效时间为5s，从而保证缓存中的数据永远存在，避免缓存击穿的风险。但对于Web请求来说，只会访问k1的缓存数据，也即对于k2和k3数据来说，是无效缓存。

5.2.2 被动请求DB数据，更新缓存

当有请求到达且发现缓存没数据时，就向DB请求最新数据并更新缓存。这种方案完全可以看做是方案一的互斥方案，它解决的是机器CPU和内存浪费的问题，内存中存储的数据始终是有用的，但却无法避免缓存失效的瞬间又突然流量峰值带来的缓存击穿问题，在业务上会有一定的风险。

详情见下图，缓存不会主动加载数据，而是根据Web请求懒加载数据。对于请求k1数据来说，发现缓存没有对应数据，到DB查询，然后放入Cache，这是常规流程；但如果有突发流量，大量请求同时访问k2数据，但Cache中没有数据时，请求就会同时落到DB上，可能压垮数据库。

5.3 缓存过期策略

5.3.1 依赖时间的过期策略

定时删除

对于需要删除的每个Key都配备一个定时器，元素超时时间一到就删除元素，释放元素占用的内存，同时释放定时器自身资源。其优点是元素的删除很及时，但缺点也很明显，比如为每个Key配备定时器肯定会消耗CPU和内存资源，严重影响性能。这种策略只适合在小数据量且对过期时间又严格要求的场景能使用，一般生产环境都不会使用。

惰性删除

元素过期后并不会立马删除，而是等到该元素的下一次操作（如：访问、更新等）才会判断是否过期，执行过期删除操作。这样的好处是节约CPU资源，因为只有当元素真的过期了，才会将其删除，而不用单独管理元素的生命周期。但其对内存不友好，因为如果若干已经过期的元素一直不被访问的话，那就会一直占用内存，造成内存泄漏。

定期删除

以上两种元素删除策略各有优缺点，无非是对CPU友好，还是对内存友好。为了结合两者的优点，一方面减少了元素定时器的配备，只使用一个定时器来统一扫描过期元素；另一方面加速了判断元素过期的时间间隔，不是被动等待检测过期，而是间隔一段时间就主动执行元素过期检测任务。正是由于以上的改进点，此方案是元素过期检测的惯常手段。

我们假设一个场景，为了保护用户隐私，通常在用户电话和商家电话之间，会使用一个虚拟电话作为沟通的桥梁。业务使用中，往往同一个虚拟号码在一定时间内是可以对相同的用户和商家建立连接的，而当超出这个时间后，这个虚拟号码就不再维护映射关系了。

虚拟电话号码的资源是有限的，自然会想到创建一个虚拟号码资源池，管理虚拟号码的创建和释放。比如规定一个虚拟号码维持的关系每次能使用15分钟，那么过期后要释放虚拟号码，我们有什么方案呢？

A. 方案一：全量数据扫描，依次遍历判断过期时间

字段名称	字段含义
vr_phone	虚拟号码
expire_seconds	相对超时时间
create_time	虚拟号码创建时间
other_fields	其它扩展字段

对于DB中存储的以上内容，每天记录都存储着虚拟号码的创建时间，以及经过expire_seconds就会删除此记录。那么需要配备一个定时任务扫描表中的所有记录，再判断current_time - create_time >expire_seconds，才会删除记录。

如果数据量很大的情况，就会导致数据删除延迟时间很长，这并不是可取的方案。那是否有方案能直接获取到需要过期的vr_phone，然后批量过期来解决上述痛点呢？来看看方案二吧。

B. 方案二：存储绝对过期时间+BTree索引，批量获取过期的vr_phone列表

字段名称	字段含义
vr_phone	虚拟号码
expire_timestamp	删除记录时间戳
other_fields	其它扩展字段

将相对过期时间expire_seconds改为记录过期的时间戳expire_timestamp，同时将其添加BTree索引提高检索效率。仍然使用一个定时器，在获取待删除vr_phone列表时只需要select vr_phone from table where now()>=expire_timestamp即可。

对于空间复杂度增加了一个BTree数据结构，而基于BTree来考虑时间复杂度的话，对于元素的新增、修改、删除、查询的平均时间复杂度都是O(logN)。

此方案已经能满足业务使用需求了，那是否还有性能更好的方案呢？

d) 单层定时轮算法

我们继续讨论上面的案例，寻找更优的解题思路。下表是DB存储元素：

字段名称	字段含义
vr_phone	虚拟号码
other_fields	其它扩展字段

此时DB中不再存储和过期时间相关的数据，而专注于业务数据本身。对于过期的功能我们交给单层定时轮来解决。其本质是一个环形数组，数组每一格代表1秒，每次新加入的元素放在游标的上一格，而游标所指向的位置就是需要过期的vr_phone列表。

执行过程：

1、初始化：启动一个timer，每隔1s，在上述环形队列中移动一格，1->2->3…->29->750->1…有一个指针来标识有待过期的slot数据

2、新增数据：当有一个新的vr_phone创建时，存储到指针的上一个slot中。对于有slot冲突的场景，可以利用链表解决冲突，也可以利用数组解决冲突。链表和数组的考量标准还是依赖于单个slot的数据长度，如果数据过长，那么存储的数组会很长，则需要很大的内存空间才能满足，无法利用内存碎片的空间。

3、过期数据：指针每隔1秒移动一个slot，那么指针指向的slot就是需要过期的数据，因为新增的数据在环形slot转完一圈后，才会被指向到。

这样一种算法结构，将时间和空间巧妙地结合在了一起。新增元素的时间复杂度为O(1)，直接插入待批量过期的slot的上一个位置即可；获取待删除元素列表时间复杂度也是O(1)，就是待批量过期的slot位置。流行框架Netty、Kafka都有定时轮的影子。

当然，单层定时轮只适用于固定时间过期的场景，如果需要管理不同过期时间的元素，那么可以参考"多层定时轮算法"，其实就是模拟现实世界的时针、分针、秒针的概念，建立多个单层定时轮，采用进位和退位的思想来管理元素的过期时间。

以上各种元素过期策略各有优缺点，可以根据业务的诉求来取舍。比如Memcache只是用了惰性删除，而Redis则同时使用了惰性删除和定期删除以结合二者的优点。

5.3.2 依赖空间的过期策略

此处只探讨最经典的三种策略FIFO、LRU、LFU的原理及实现方案，对于其它改进算法，感兴趣的同学可以自行查找。

a) FIFO：先进先出，当空间不足时，先进入的元素将会被移除。此方案并没有考虑元素的使用特性，可能最近频繁访问的一个元素会被移除，从而降低了缓存命中率。实现：基于LinkedHashMap的钩子函数实现FIFOMap。

// 链表头部是最近最少被访问的元素，需要被删除
public class FIFOMap<K, V> extends LinkedHashMap<K, V> {
    private int maxSize;

    //LinkedHashMap每次插入数据，默认都是链表tail；当accessOrder=false，元素被访问不会移动位置
    public FIFOMap(int maxSize) {
        super(maxSize, 0.75f, false);
        this.maxSize = maxSize;
    }

    //每次put和putAll新增元素的时候都会触发判断;当下面函数=true时，就删除链表head元素
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

b) LRU：最近最少使用算法，当下多次被访问的数据在以后被访问的概率会很大，因此保留最近访问的元素，提高命中率。可以应对流量突发峰值，因为存储的池子大小是固定的，因此内存占用不可能过多。但也有缺点：如果一个元素访问存在间歇规律，1分钟前访问1万次，后面30秒无访问，然后再访问一万次，这样就会导致被删除，降低了命中率。实现：基于LinkedHashMap的钩子函数实现LRUHashMap。

// 链表头部是最近最少被访问的元素，需要被删除
public class LRUMap<K, V> extends LinkedHashMap<K, V> {
    private int maxSize;

    //LinkedHashMap每次插入数据，默认都是链表tail；当accessOrder=true时，被访问的元素也会放到链表tail
    public LRUMap(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }

    //每次put和putAll新增元素的时候都会触发判断;当下面函数=true时，就删除链表head元素
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() >= maxSize;
    }
}

c) LFU：最近最少频率使用，根据数据的历史访问频率来淘汰数据，其核心思想是"如果数据过去被访问多次，那么将来被访问的频率也更高"。这种算法针对LRU的缺点进行了优化，记录了元素访问的总次数，选出访问次数最小的元素进行删除。原本的LFU算法要求记录所有元素的访问次数，但考虑到内存成本，改进后的LFU是在有限队列中进行淘汰。

实现：Redis的优先级队列Zset实现，Zset存储元素的数量固定，Value是访问次数，超过size就删除访问次数最小的即可。但这种删除策略对于有时效性的数据却并不合适，对于排行榜类的数据，如果某个历史剧点击量特别高，那么就始终不会被淘汰，新剧就没有展示的机会。改进方案，可以将Value存储为入库时间戳+访问次数的值，这样随着时间流逝，历史老剧就可能被淘汰。

6. 其他影响命中率的因素

6.1 缓存穿透

对于数据库中本就不存在的值，缓存中肯定也不会存在，此类数据的查询一定会落到DB上。为了减少DB访问压力，我们期望将这些数据都可以在缓存中cover住，以下是两种解法。

解法一：缓存null值：

该方法对于元素是否存在于DB有精准的判断，可如果存在海量null值的数据，则会对内存过度占用。

布隆过滤：

使用场景是海量数据，且不要求精准判断和过滤数据。其思路是借助Hash和bit位思想，将Key值映射成若干Hash值存储到bit数组中。

B. 新增元素时，将元素的Key根据预设的若干Hash函数解析成若干整数，然后定位到bit位数组中，将对应的bit位都改为1。

C. 判断元素是否存在，也是将元素的Key根据Hash函数解析成整数，查询若干bit位的值。只要有一个bit位是0，那么这个Key肯定是新元素，不存在；如果所有bit位全都是1，那么这个Key很大概率是已经存在的元素，但也有极小的概率是Key3经过若干Hash函数定位到bit数组后都是Hash冲突的，可能造成误判。

6.2 缓存击穿

缓存中原本一批数据有值，但恰好都同时过期了，此时有大量请求过来就都会落到DB上。避免这种风险也有两种解法。

解法一：随机缓存失效时间：

对缓存中不同的Key设置不同的缓存失效时间，避免缓存同时失效带来大量请求都落到DB上的情况。

解法二：主动加载更新缓存策略，替代缓存过期删除策略：

在缓存失效之前就主动到DB中加载最新的数据放到缓存中，从而避免大量请求落到DB的情况。

6.3 缓存雪崩

大量缓存同时过期，或者缓存中间件不可用，导致大量请求落到DB，系统停止响应。解法是对缓存设置随机失效时间，同时增加缓存中间件健康度监测。

7. 保证业务数据一致性的策略

在分析了影响缓存命中率的若干策略和方案后，我们结合实际开发诉求，来分析下缓存是如何降低DB的访问压力，以及DB和缓存中业务数据的一致性如何保证？

维护数据一致性常用的方案有两种：先操作DB，再操作Cache；先操作Cache，再操作DB。而以上两步操作都期望是全部成功，才能保证操作是原子性的。如果不依赖事务，那么对数据怎样操作才能保证即使流程异常中断，对业务影响也是最小呢？

7.1 对于读取操作

因为只是读取，不涉及数据修改，因此先读缓存，Cache miss后，读DB数据，然后set cache就足够通用。

7.2 对于写入操作

7.2.1 先操作DB，再操作(delete/update)缓存

当DB数据操作成功，但缓存数据（不论是delete还是update）操作失败，就会导致在未来一段时间内，缓存中的数据都是历史旧数据，并没有保证操作的原子性，无法接受。

7.2.2 先操作(delete/update)缓存，再操作DB

第一种方案：当update缓存成功，但操作DB失败，虽然缓存中的数据是最新的了，但这个最新的数据最终并没有更新到DB中，当缓存失效后，还是会从DB中读取到旧的数据，这样就会导致上下游依赖的数据出现错误，无法接受。
第二种方案：先delete缓存，再操作DB数据，我们详细讨论下这种方案：
- 如果delete就失败了，整体操作失败，相当于事务回滚；
- 如果delete成功，但DB操作失败，此时会引起一次cache miss，紧接着还是会从DB加载旧数据，相当于整体无操作，事务回滚，代价只是一次cache miss；
- 如果delete成功，且DB操作成功，那么整体成功。

结论：先delete缓存，再操作DB，能尽可能达到两步处理的原子性效果，即使流程中断对业务影响也是最小的。

8. 小结

对于缓存的使用没有绝对的黄金标准，都是根据业务的使用场景来决定什么缓存框架或者缓存策略是最适合的。但对于通用的业务场景来说，以下的缓存框架选择方法应该可以满足大部分场景。

对于本地缓存，如果缓存的数量是可估计的，且不会变化的，那么可使用JDK自带的HashMap或ConcurrentHashMap来存储。

对于有按时间过期、自动刷新需求的本地缓存可以使用Caffeine。

对于分布式缓存且要求有丰富数据结构的，推荐使用Redis。

本文转载自公众号高德技术（ID：amap_tech）。

原文链接：

https://mp.weixin.qq.com/s/DdqEgfO-H77QhhUfdX4YRg

创作场景

系统性能提升利刃，缓存技术使用的实践与思考