7 缓存
从单核 CPU 到分布式系统，从前端到后台，缓存无处不在。古有朱元璋“缓称王”而终得天下，今有不论是芯片制造商还是互联网公司都同样采取了“缓称王”（缓存称王）的政策才能占据一席之地。缓存是原始数据的一个复制集，其本质就是空间换时间，主要是为了解决高并发读。
7.1 缓存的使用场景
缓存是空间换时间的艺术，使用缓存能提高系统的性能。“劲酒虽好，可不要贪杯”，使用缓存的目的是为了提高性价比，而不是一上来就为了所谓的提高性能不计成本的使用缓存，而是要看场景。
适合使用缓存的场景，以之前参与过的项目企鹅电竞为例：
1）一旦生成后基本不会变化的数据：如企鹅电竞的游戏列表，在后台创建一个游戏之后基本很少变化，可直接缓存整个游戏列表；
2）读密集型或存在热点的数据：典型的就是各种 App 的首页，如企鹅电竞首页直播列表；
3）计算代价大的数据：如企鹅电竞的 Top 热榜视频，如 7 天榜在每天凌晨根据各种指标计算好之后缓存排序列表；
4）千人一面的数据：同样是企鹅电竞的 Top 热榜视频，除了缓存的整个排序列表，同时直接在进程内按页缓存了前 N 页数据组装后的最终回包结果；
不适合使用缓存的场景：
1）写多读少，更新频繁；
2）对数据一致性要求严格；
7.2 缓存的分类
- 进程级缓存：缓存的数据直接在进程地址空间内，这可能是访问速度最快使用最简单的缓存方式了。主要缺点是受制于进程空间大小，能缓存的数据量有限，进程重启缓存数据会丢失。一般通常用于缓存数据量不大的场景。
- 集中式缓存：缓存的数据集中在一台机器上，如共享内存。这类缓存容量主要受制于机器内存大小，而且进程重启后数据不丢失。常用的集中式缓存中间件有单机版 redis、memcache 等。
- 分布式缓存：缓存的数据分布在多台机器上，通常需要采用特定算法（如 Hash）进行数据分片，将海量的缓存数据均匀的分布在每个机器节点上。常用的组件有：Memcache（客户端分片）、Codis（代理分片）、Redis Cluster（集群分片）。
- 多级缓存：指在系统中的不同层级的进行数据缓存，以提高访问效率和减少对后端存储的冲击。以下图的企鹅电竞的一个多级缓存应用，根据我们的现网统计，在第一级缓存的命中率就已经达 94%，穿透到 grocery 的请求量很小。
企鹅电竞首页多级缓存
整体工作流程如下：
- 1）请求到达首页或者直播间服务后，如果在本地缓存命中则直接返回，否则从下一级缓存核心存储进行查询并更新本地缓存；
- 2）前端服务缓存没有命中穿透到核心存储服务，如果命中则直接返回给前端服务，没有则请求存储层 grocery 并更新缓存；
- 3）前两级 Cache 都没有命中回源到存储层 grocery。
7.3 缓存的模式
关于缓存的使用，已经有人总结出了一些模式，主要分为 Cache-Aside 和 Cache-As-SoR 两类。其中 SoR（system-of-record）：表示记录系统，即数据源，而 Cache 正是 SoR 的复制集。
Cache-Aside：旁路缓存，这应该是最常见的缓存模式了。对于读，首先从缓存读取数据，如果没有命中则回源 SoR 读取并更新缓存。对于写操作，先写 SoR，再写缓存。这种模式架构图如下：
Cache-Aside结构图
逻辑代码：
//读操作 data = Cache.get(key); if(data == NULL) { data = SoR.load(key); Cache.set(key, data); } //写操作 if(SoR.save(key, data)) { Cache.set(key, data); }
这种模式用起来简单，但对应用层不透明，需要业务代码完成读写逻辑。同时对于写来说，写数据源和写缓存不是一个原子操作，可能出现以下情况导致两者数据不一致：
1）在并发写时，可能出现数据不一致。如下图所示，user1 和 user2 几乎同时进行读写。在 t1 时刻 user1 写 db，t2 时刻 user2 写 db，紧接着在 t3 时刻 user2 写缓存，t4 时刻 user1 写缓存。这种情况导致 db 是 user2 的数据，缓存是 user1 的数据，两者不一致。
Cache-Aside并发读写
2）先写数据源成功，但是接着写缓存失败，两者数据不一致。对于这两种情况如果业务不能忍受，可简单的通过先 delete 缓存然后再写 db 解决，其代价就是下一次读请求的 cache miss。
Cache-As-SoR：缓存即数据源，该模式把 Cache 当作 SoR，所以读写操作都是针对 Cache，然后 Cache 再将读写操作委托给 SoR，即 Cache 是一个代理。如下图所示：
Cache-As-SoR结构图
Cache-As-SoR 有三种实现：
1）Read-Through：发生读操作时，首先查询 Cache，如果不命中则再由 Cache 回源到 SoR 即存储端实现 Cache-Aside 而不是业务）。
2）Write-Through：称为穿透写模式，由业务先调用写操作，然后由 Cache 负责写缓存和 SoR。
3）Write-Behind：称为回写模式，发生写操作时业务只更新缓存并立即返回，然后异步写 SoR，这样可以利用合并写/批量写提高性能。
7.4 缓存的回收策略
在空间有限、低频热点访问或者无主动更新通知的情况下，需要对缓存数据进行回收，常用的回收策略有以下几种：
1）基于时间：基于时间的策略主要可以分两种：
- 基于 TTL（Time To Live）：即存活期，从缓存数据创建开始到指定的过期时间段，不管有没有访问缓存都会过期。如 redis 的 EXPIRE。
- 基于 TTI（Time To Idle）：即空闲期，缓存在指定的时间没有被访问将会被回收。
2）基于空间：缓存设置了存储空间上限，当达到上限时按照一定的策略移除数据。
3）基于容量：缓存设置了存储条目上限，当达到上限时按照一定的策略移除数据。
4）基于引用：基于引用计数或者强弱引用的一些策略进行回收。
缓存的常见回收算法如下：
- FIFO（First In First Out）：先进选出原则，先进入缓存的数据先被移除。
- LRU（Least Recently Used）：最基于局部性原理，即如果数据最近被使用，那么它在未来也极有可能被使用，反之，如果数据很久未使用，那么未来被使用的概率也较。
- LFU：（Least Frequently Used）：最近最少被使用的数据最先被淘汰，即统计每个对象的使用次数，当需要淘汰时，选择被使用次数最少的淘汰。
7.5 缓存的崩溃与修复
由于在设计不足、请求攻击（并不一定是恶意攻击）等会造成一些缓存问题，下面列出了常见的缓存问题和解决方案。
缓存穿透：大量使用不存在的 key 进行查询时，缓存没有命中，这些请求都穿透到后端的存储，最终导致后端存储压力过大甚至被压垮。这种情况原因一般是存储中数据不存在，主要有两个解决办法。
- 1）设置空置或默认值：如果存储中没有数据，则设置一个空置或者默认值缓存起来，这样下次请求时就不会穿透到后端存储。但这种情况如果遇到恶意攻击，不断的伪造不同的 key 来查询时并不能很好的应对，这时候需要引入一些安全策略对请求进行过滤。
- 2）布隆过滤器：采用布隆过滤器将，将所有可能存在的数据哈希到一个足够大的 bitmap 中，一个一定不存在的数据会被这个 bitmap 拦截掉，从而避免了对底层数据库的查询压力。
缓存雪崩：指大量的缓存在某一段时间内集体失效，导致后端存储负载瞬间升高甚至被压垮。通常是以下原因造成：
- 1）缓存失效时间集中在某段时间，对于这种情况可以采取对不同的 key 使用不同的过期时间，在原来基础失效时间的基础上再加上不同的随机时间；
- 2）采用取模机制的某缓存实例宕机，这种情况移除故障实例后会导致大量的缓存不命中。有两种解决方案：① 采取主从备份，主节点故障时直接将从实例替换主；② 使用一致性哈希替代取模，这样即使有实例崩溃也只是少部分缓存不命中。
缓存热点：虽然缓存系统本身性能很高，但也架不住某些热点数据的高并发访问从而造成缓存服务本身过载。假设一下微博以用户 id 作为哈希 key，突然有一天志玲姐姐宣布结婚了，如果她的微博内容按照用户 id 缓存在某个节点上，当她的万千粉丝查看她的微博时必然会压垮这个缓存节点，因为这个 key 太热了。这种情况可以通过生成多份缓存到不同节点上，每份缓存的内容一样，减轻单个节点访问的压力。
7.6 缓存的一些好实践
1）动静分离：对于一个缓存对象，可能分为很多种属性，这些属性中有的是静态的，有的是动态的。在缓存的时候最好采用动静分离的方式。如企鹅电竞的视频详情分为标题、时长、清晰度、封面 URL、点赞数、评论数等，其中标题、时长等属于静态属性，基本不会改变，而点赞数、评论数经常改变，在缓存时这两部分开，以免因为动态属性每次的变更要把整个视频缓存拉出来进行更新一遍，成本很高。
2）慎用大对象：如果缓存对象过大，每次读写开销非常大并且可能会卡住其他请求，特别是在 redis 这种单线程的架构中。典型的情况是将一堆列表挂在某个 value 的字段上或者存储一个没有边界的列表，这种情况下需要重新设计数据结构或者分割 value 再由客户端聚合。
3）过期设置：尽量设置过期时间减少脏数据和存储占用，但要注意过期时间不能集中在某个时间段。
4）超时设置：缓存作为加速数据访问的手段，通常需要设置超时时间而且超时时间不能过长（如 100ms 左右），否则会导致整个请求超时连回源访问的机会都没有。
5）缓存隔离：首先，不同的业务使用不同的 key，防止出现冲突或者互相覆盖。其次，核心和非核心业务进行通过不同的缓存实例进行物理上的隔离。
6）失败降级：使用缓存需要有一定的降级预案，缓存通常不是关键逻辑，特别是对于核心服务，如果缓存部分失效或者失败，应该继续回源处理，不应该直接中断返回。
7）容量控制：使用缓存要进行容量控制，特别是本地缓存，缓存数量太多内存紧张时会频繁的 swap 存储空间或 GC 操作，从而降低响应速度。
8）业务导向：以业务为导向，不要为了缓存而缓存。对性能要求不高或请求量不大，分布式缓存甚至数据库都足以应对时，就不需要增加本地缓存，否则可能因为引入数据节点复制和幂等处理逻辑反而得不偿失。
9）监控告警：跟妹纸永远是对的一样，总不会错。对大对象、慢查询、内存占用等进行监控。
8 分片
分片即将一个较大的部分分成多个较小的部分，在这里我们分为数据分片和任务分片。对于数据分片，在本文将不同系统的拆分技术术语（如 region、shard、vnode、partition）等统称为分片。分片可以说是一箭三雕的技术，将一个大数据集分散在更多节点上，单点的读写负载随之也分散到了多个节点上，同时还提高了扩展性和可用性。
数据分片，小到编程语言标准库里的集合，大到分布式中间件，无所不在。如我曾经写过一个线程安全的容器以放置各种对象时，为了减少锁争用，对容器进行了分段，每个分段一个锁，按照哈希或者取模将对象放置到某个分段中，如 Java 中的 ConcurrentHashMap 也采取了分段的机制。分布式消息中间件 Kafka 中对 topic 也分成了多个 partition，每个 partition 互相独立可以比并发读写。
8.1 分片策略
进行分片时，要尽量均匀的将数据分布在所有节点上以平摊负载。如果分布不均，会导致倾斜使得整个系统性能的下降。常见的分片策略如下：
- 区间分片
基于一段连续关键字的分片，保持了排序，适合进行范围查找，减少了垮分片读写。区间分片的缺点是容易造成数据分布不均匀，导致热点。如直播平台，如果按 ID 进行区间分片，通常短位 ID 都是一些大主播，如在 100-1000 内 ID 的访问肯定比十位以上 ID 频繁。常见的还有按时间范围分片，则最近时间段的读写操作通常比很久之前的时间段频繁。
区间分片 - 随机分片
按照一定的方式（如哈希取模）进行分片，这种方式数据分布比较均匀，不容易出现热点和并发瓶颈。缺点就是失去了有序相邻的特性，如进行范围查询时会向多个节点发起请求。
随机分片 - 组合分片：对区间分片和随机分片的一种折中，采取了两种方式的组合。通过多个键组成复合键，其中第一个键用于做哈希随机，其余键用于进行区间排序。如直播平台以主播 id+开播时间（anchor_id,live_time）作为组合键，那么可以高效的查询某主播在某个时间段内的开播记录。社交场景，如微信朋友圈、QQ 说说、微博等以用户 id+发布时间(user_id,pub_time)的组合找到用户某段时间的发表记录。
8.2 二级索引
二级索引通常用来加速特定值的查找，不能唯一标识一条记录，使用二级索引需要二次查找。关系型数据库和一些 K-V 数据库都支持二级索引，如 mysql 中的辅助索引（非聚簇索引），ES 倒排索引通过 term 找到文档。
- 本地索引
索引存储在与关键字相同的分区中，即索引和记录在同一个分区，这样对于写操作时都在一个分区里进行，不需要跨分区操作。但是对于读操作，需要聚合其他分区上的数据。如以王者荣耀短视频为例，以视频 vid 作为关键索引，视频标签（如五杀、三杀、李白、阿珂）作为二级索引，本地索引如下图所示：
本地索引 - 全局索引
按索引值本身进行分区，与关键字所以独立。这样对于读取某个索引的数据时，都在一个分区里进行，而对于写操作，需要跨多个分区。仍以上面的例子为例，全局索引如下图所示：
全局索引
8.3 路由策略
路由策略决定如何将数据请求发送到指定的节点，包括分片调整后的路由。通常有三种方式：客户端路由、代理路由和集群路由。
- 客户端路由
客户端直接操作分片逻辑，感知分片和节点的分配关系并直接连接到目标节点。Memcache 就是采用这种方式实现的分布式，如下图所示。
Memcache客户端路由 - 代理层路由
客户端的请求到发送到代理层，由其将请求转发到对应的数据节点上。很多分布式系统都采取了这种方式，如业界的基于 redis 实现的分布式存储 codis（codis-proxy 层），公司内如 CMEM（Access 接入层）、DCache（Proxy+Router）等。如下图所示 CMEM 架构图，红色方框内的 Access 层就是路由代理层。
CMEM接入层路由 - 集群路由
由集群实现分片路由，客户端连接任意节点，如果该节点存在请求的分片，则处理；否则将请求转发到合适的节点或者告诉客户端重定向到目标节点。如 redis cluster 和公司的 CKV+采用了这种方式，下图的 CKV+集群路由转发。
CKV+集群路由
以上三种路由方式都各优缺点，客户端路由实现相对简单但对业务入侵较强。代理层路由对业务透明，但增加了一层网络传输，对性能有一定影响，同时在部署维护上也相对复杂。集群路由对业务透明，且比代理路由少了一层结构，节约成本，但实现更复杂，且不合理的策略会增加多次网络传输。
8.4 动态平衡
在学习平衡二叉树和红黑树的时候我们都知道，由于数据的插入删除会破坏其平衡性。为了保持树的平衡，在插入删除后我们会通过左旋右旋动态调整树的高度以保持再平衡。在分布式数据存储也同样需要再平衡，只不过引起不平衡的因素更多了，主要有以下几个方面：
1）读写负载增加，需要更多 CPU；
2）数据规模增加，需要更多磁盘和内存；
3）数据节点故障，需要其他节点接替；
业界和公司很多产品也都支持动态平衡调整，如 redis cluster 的 resharding，HDFS/kafka 的 rebalance。常见的方式如下：
- 固定分区
创建远超节点数的分区数，为每个节点分配多个分区。如果新增节点，可从现有的节点上均匀移走几个分区从而达到平衡，删除节点反之，如下图所示。典型的就是一致性哈希，创建 2^32-1 个虚拟节点（vnode）分布到物理节点上。该模式比较简单，需要在创建的时候就确定分区数，如果设置太小，数据迅速膨胀的话再平衡的代价就很大。如果分区数设置很大，则会有一定的管理开销。
固定分区再平衡 - 动态分区
自动增减分区数，当分区数据增长到一定阀值时，则对分区进行拆分。当分区数据缩小到一定阀值时，对分区进行合并。类似于 B+树的分裂删除操作。很多存储组件都采用了这种方式，如 HBase Region 的拆分合并，TDSQL 的 Set Shard。这种方式的优点是自动适配数据量，扩展性好。使用这种分区需要注意的一点，如果初始化分区为一个，刚上线请求量就很大的话会造成单点负载高，通常采取预先初始化多个分区的方式解决，如 HBase 的预分裂。
8.5 分库分表
当数据库的单表/单机数据量很大时，会造成性能瓶颈，为了分散数据库的压力，提高读写性能，需要采取分而治之的策略进行分库分表。通常，在以下情况下需要进行分库分表：
1）单表的数据量达到了一定的量级（如 mysql 一般为千万级），读写的性能会下降。这时索引也会很大，性能不佳，需要分解单表。
2）数据库吞吐量达到瓶颈，需要增加更多数据库实例来分担数据读写压力。
分库分表按照特定的条件将数据分散到多个数据库和表中，分为垂直切分和水平切分两种模式。
- 垂直切分：按照一定规则，如业务或模块类型，将一个数据库中的多个表分布到不同的数据库上。以直播平台为例，将直播节目数据、视频点播数据、用户关注数据分别存储在不同的数据库上，如下图所示：
垂直切分
优点：
1）切分规则清晰，业务划分明确；
2）可以按照业务的类型、重要程度进行成本管理，扩展也方便；
3）数据维护简单；
缺点：
1）不同表分到了不同的库中，无法使用表连接 Join。不过在实际的业务设计中，也基本不会用到 join 操作，一般都会建立映射表通过两次查询或者写时构造好数据存到性能更高的存储系统中。
2）事务处理复杂，原本在事务中操作同一个库的不同表不再支持。如直播结束时更新直播节目同时生成一个直播的点播回放在分库之后就不能在一个事物中完成，这时可以采用柔性事务或者其他分布式事物方案。
- 水平切分：按照一定规则，如哈希或取模，将同一个表中的数据拆分到多个数据库上。可以简单理解为按行拆分，拆分后的表结构是一样的。如直播系统的开播记录，日积月累，表会越来越大，可以按照主播 id 或者开播日期进行水平切分，存储到不同的数据库实例中。优点：1）切分后表结构一样，业务代码不需要改动；2）能控制单表数据量，有利于性能提升；缺点：1）Join、count、记录合并、排序、分页等问题需要跨节点处理；2）相对复杂，需要实现路由策略；综上所述，垂直切分和水平切分各有优缺点，通常情况下这两种模式会一起使用。
8.6 任务分片
记得小时候发新书，老师抱了一堆堆的新书到教室，然后找几个同学一起分发下去，有的发语文，有的发数学，有的发自然，这就是一种任务分片。车间中的流水线，经过每道工序的并行后最终合成最终的产品，也是一种任务分片。
任务分片将一个任务分成多个子任务并行处理，加速任务的执行，通常涉及到数据分片，如归并排序首先将数据分成多个子序列，先对每个子序列排序，最终合成一个有序序列。在大数据处理中，Map/Reduce 就是数据分片和任务分片的经典结合。
