作者：刘欢（浅奕）
1 问题背景
分布式缓存一般被定义为一个数据集合，它将数据分布（或分区）于任意数目的集群节点上。集群中的一个具体节点负责缓存中的一部分数据，整体对外提供统一的访问接口[1]。分布式缓存一般基于冗余备份机制实现数据高可用，又被称为内存数据网格（IMDG, in-memory data grid）。在云平台飞速发展的今天，作为提升应用性能的重要手段，分布式缓存技术在工业界得到了越来越广泛的关注和研发投入[2]。弹性缓存平台[3]是分布式缓存集群在云计算场景下的新形态，其强调集群的动态扩展性与高可用性。动态扩展性表达了缓存平台可提供透明的服务扩展的能力，高可用性则表达了缓存平台可以容忍节点失效。
Tair是阿里巴巴集团自研的弹性缓存/存储平台，在内部有着大量的部署和使用。Tair的核心组件是一个高性能、可扩展、高可靠的NoSQL存储系统。目前支持MDB、LDB、RDB等存储引擎。其中MDB是类似Memcached的内存存储引擎，LDB是使用LSM Tree的持久化磁盘KV存储引擎，RDB是支持Queue、Set、Maps等数据结构的内存及持久化存储引擎。
Tair的数据分片和路由算法采用了Amazon于2007年提出的一种改进的一致性哈希算法[4]。该算法将整个哈希空间分为若干等大小的Q份数据分区（也称为虚拟节点，Q>>N，N为缓存节点数），每个缓存节点依据其处理能力分配不同数量的数据分区。客户端请求的数据Key值经哈希函数映射至哈希环上的位置记为token，token值再次被哈希映射为某一分区标识。得到分区标识后，客户端从分区服务器映射表中查询存放该数据分区的缓存节点后进行数据访问。使用该算法对相同数据Key进行计算，其必然会被映射到固定的DataServer上，如图：
此时DataServer单节点的读写性能便成了单数据Key的读写性能瓶颈，且无法通过水平扩展节点的方式来解决。由于阿里巴巴集团内部电商系的促销活动天然的存在热点数据，所以要增强整个弹性缓存/存储平台的稳定性和服务能力，就必须提升热点数据的读写能力，使其能做到水平扩展。
2 解决方案
解决方案分为三部分：热点识别、读热点方案和写热点方案。
其中读写热点方案都是以服务端能对热点访问进行精准的识别为前提的。另外对于可以提前预知热点Key的情况，也提供相应的客户端API以支持特定数据Key或者特定Namespace的所有数据Key预先标记为热点Key的能力。
2.1 DataServer上的热点统计过程
DataServer收到客户端的请求后，由每个具体处理请求的工作线程（Worker Thread）进行请求的统计。工作线程用来统计热点的数据结构均为ThreadLocal模式的数据结构，完全无锁化设计。热点识别算法使用精心设计的多级加权LRU链和HashMap组合的数据结构，在保证服务端请求处理效率的前提下进行请求的全统计，支持QPS热点和流量热点（即请求的QPS不大但是数据本身过大而造成的大流量所形成的热点）的精准识别。每个采样周期结束时，工作线程会将统计的数据结构转交到后台的统计线程池进行分析处理。统计工作异步在后台进行，不抢占正常的数据请求的处理资源。
2.2 读热点方案
2.2.1 服务端设计
原始Tair的数据访问方式是先进行Hash(Key)%BucketCount的计算，得出具体的数据存储Bucket，再检索数据路由表找到该Bucket所在的DataServer后对其进行读写请求的。所以相同Key的读写请求必然落在固定的DataServer上，且无法通过水平扩展DataServer数量来解决。
本方案通过在DataServer上划分一块HotZone存储区域的方式来解决热点数据的访问。该区域存储当前产生的所有读热点的数据，由客户端配置的缓存访问逻辑来处理各级缓存的访问。多级缓存架构如下：
所有DataServer的HotZone存储区域之间没有权重关系，每个HotZone都存储相同的读热点数据。客户端对热点数据Key的请求会随机到任意一台DataServer的HotZone区域，这样单点的热点请求就被散列到多个节点乃至整个集群。
2.2.2客户端设计
2.2.2.1 客户端逻辑
当客户端在第一次请求前初始化时，会获取整个Tair集群的节点信息以及完整的数据路由表，同时也会获取配置的热点散列机器数（即客户端访问的HotZone的节点范围）。随后客户端随机选择一个HotZone区域作为自身固定的读写HotZone区域。在DataServer数量和散列机器数配置未发生变化的情况下，不会改变选择。即每个客户端只访问唯一的HotZone区域。
客户端收到服务端反馈的热点Key信息后，至少在客户端生效N秒。在热点Key生效期间，当客户端访问到该Key时，热点的数据会首先尝试从HotZone节点进行访问，此时HotZone节点和源数据DataServer节点形成一个二级的Cache模型。客户端内部包含了两级Cache的处理逻辑，即对于热点数据，客户端首先请求HotZone节点，如果数据不存在，则继续请求源数据节点，获取数据后异步将数据存储到HotZone节点里。使用Tair客户端的应用常规调用获取数据的接口即可，整个热点的反馈、识别以及对多级缓存的访问对外部完全透明。HotZone缓存数据的一致性由客户端初始化时设置的过期时间来保证，具体的时间由具体业务对缓存数据不一致的最大容忍时间来决定。
客户端存储于本地的热点反馈过期后，数据Key会到源DataServer节点读取。如果该Key依旧在服务端处于热点状态，客户端会再次收到热点反馈包。因为所有客户端存储于本地的热点反馈信息的失效节奏不同，所以不会出现同一瞬间所有的请求都回源的情况。即使所有请求回源，也仅需要回源读取一次即可，最大的读取次数仅为应用机器数。若回源后发现该Key已不是热点，客户端便回到常规的访问模式。
2.2.2.2 散列比和QPS偏差的关系
设集群普通QPS为 C，热点QPS为 H，机器数为 N，则每台机器QPS为:
A=(C+H)/N
则普通机器QPS偏差比为：
P_c=(C/N)/A=(C/N)/((C+H)/N)=C/(C+H) ，当 H=0 时，P_c=1
则热点机器偏差比为：
P_h=(C/N+H)/A=(C/N+H)/((C+H)/N)=(C+HN)/(C+H) ，当 H=0 时，P_h=1
进行散列后，设散列机器数为 M，则热点机器偏差比为：
P_(h')=(C/N+H/M)/A=(C/N+H/M)/((C+H)/N)=(CM+HN)/(M(C+H))
设散列比为 K，即 M=KN，则有：
P_(h')=(CM+HN)/(M(C+H))=(CKN+HN)/(KN(C+H))=(CK+H)/(K(C+H))，当 K=1 时， P_(h')=1
2.3 写热点方案
2.3.1 服务端设计
2.3.1.1 处理方式
对于写热点，因为一致性的问题，难以使用多级缓存的方式来解决。如果采用写本地Cache，再异步更新源DataServer的方案。那么在Cache写入但尚未更新的时候，如果业务机器宕机，就会有已写数据丢失的问题。同时，本地 Cache会导致进行数据更新的某应用机器当前更新周期内的修改对其他应用机器不可见，从而延长数据不一致的时间。故多级Cache的方案无法支持写热点。最终写热点采用在服务端进行请求合并的方式进行处理。
热点Key的写请求在IO线程被分发到专门的热点合并线程处理，该线程根据Key对写请求进行一定时间内的合并，随后由定时线程按照预设的合并周期将合并后的请求提交到引擎层。合并过程中请求结果暂时不返回给客户端，等请求合并写入引擎成功后统一返回。这样做不会有一致性的问题，不会出现写成功后却读到旧数据，也避免了LDB集群返回成功，数据并未落盘的情况（假写）。具体的合并周期在服务端可配置，并支持动态修改生效。
2.3.2 客户端设计
写热点的方案对客户端完全透明，不需要客户端做任何修改。
2.3.3 性能指标
LDB集群实际压测效果为单Key合并能做到单Key百万的QPS（1ms合并，不限制合并次数），线上实际集群为了尽可能保证实时性，均采用了最大0.1ms以及单次最大合并次数为100次的限制。这样单Key在引擎层的最大落盘QPS就能控制在10000以下（而合并的QPS则取决于应用的访问频率）。Tair服务端的包处理是完全异步化的，进行热点请求的合并操作并不阻塞对其他请求的处理。唯一的影响就是增大客户端对热点key的写请求的RT. 按照现在的配置，最坏情况下，客户端的热点key的写操作会增大0.1ms，这个影响是微乎其微的。
【招聘传送门】欢迎感兴趣的同学加入我们，详情请点击：
Tengine资深开发工程师/研发专家
分布式存储研发专家
超大规模内存存储系统研发专家
系统运营开发(Devops)专家
参考文献
[1] Oracle Coherence,http://www.oracle.com/technetwork/cn/middleware/coherence/distributed-caching-089211-zhs.html
[2] Qin XL, Zhang WB, Wei J, Wang W, Zhong H, Huang T. Progress and challenges of distributed caching techniques in cloud computing. Ruanjian Xuebao/Journal of Software, 2013,24(1):50−66 (in Chinese). http://www.jos.org.cn/1000-9825/4276.htm
[3] Gualtieri M, Rymer JR. The forrester wave: Elastic caching platforms.Q2, 2010. ftp://ftp.software.ibm.com/software/solutions/soa/pdfs/wave_elastic_caching_platforms_q2_2010.pdf
[4] Hastorun D, Jampani M, Kakulapati G, Pilchin A, Sivasubramanian S, Vosshall P, Vogels W. Dynamo: Amazon’s highly available key-value store.In: Proc. of the ACM Symp. on Operating Systems Principles (SOSP 2007). 2007. 205−220. [doi: 10.1145/1323293.1294281]