谈谈cache

一、缓存

什么是缓存: 用于存储数据的硬件或软件的组成部分，以使得后续更快访问相应的数据。
为什么引入缓存: 储存数据的硬件不能满足低延时,高访问量的要求
为什么不把全量数据缓存起来: 读取时延越低, 读取访问量越高的储存, 成本也越高.
折中: 二八原则. 80%的访问量集中在20%的数据上.
优点: 延时低, 易扩展, 降低成本
更新策略: 通知机制, 读触发, 定时刷新

二、组件

1. Memcached.

Memcached是开源的，高性能的，可分布式部署，用于网站提速，减轻数据库负载的缓存组件
高性能Key-Value存储
Slab Allocator的机制来实现分配、管理内存
LRU剔除算法

2. Redis

Redis是开源的，高性能的，支持分布式，支持多数据结构的缓存组件。
支持数据过期, 支持多种LRU策略

3. 自研

由于外界的组建持续维护性不可预测，另一方面外界组件出现问题时责任划分模糊。

三、分布式缓存

• 数据分片: 区间分片、hash分片、 slot分片。
• 对于hash分片，主要的哈希算法有静态哈希和一致性哈希
• 客户端实现(memcached), PROXY 层(托管的redis)
• 分布式可以理解问只是将数据缩小常数倍，对于海量数据，并不能解决核心问题，反而会引入更复杂的问题。

四、算法

1. 缓存算法

缓存通过设计良好的数据分块、预取、顺序预取、缓存替换等算法来提高对缓存内容的命中率。
缓存算法可以分为基于访问时间的策略、基于访问频率的策略、访问时间与频率兼顾策略、时间距离分布策略等类型。
算法也与储存有关系，比如使用全内存储存，算法更自由。使用共享内存储存，则对应的算法限制比较多了。

2. 缓存策略

1. 缓存什么内容
2. 何时进行缓存
3. 当缓存空间已满时如何进行替换,即缓存替换算法。
4. 何时更新数据

3. 淘汰策略

1. 基于访问时间
   此类算法按各缓存项的被访问时间来组织缓存队列,决定替换对象。
   LRU (LeastRecentlyUsed)是一种应用广泛的缓存算法。
   该算法维护一个缓存项队列,队列中的缓存项按每项的最后被访问时间排序。
   当缓存空间已满时,将处于队尾,即删除最后一次被访问时间距现在最久的项,将新的区段放入队列首部。
   但LRU算法仅维护了缓存块的访问时间信息,没有考虑被访问频率等因素,在某些访问模式下无法获得理想命中率。
   另一方面，这个算法以来多种数据结构，对于共享内存为储存的场景无法使用。
   当我们使用多阶hash的时候，我们只是对遇到的第一个过期的进行淘汰,且性能相当低效。

2. 基于访问频率
   此类算法用缓存项的被访问频率来组织缓存。如LFU、LRU-2、2Q、LIRS。
   LFU (LeastFrequentlyUsed)按每个缓存块的被访问频率将缓存中的各块排序,当缓存空间已满时,替换掉缓存队列中访问频率最低的一项。
   与LRU的缺点类似, LFU仅维护各项的被访问频率信息,对于某缓存项,如果该项在过去有着极高的访问频率而最近访问频率较低,当缓存空间已满时该项很难被从缓存中替换出来,进而导致命中率下降。
   LRU-2[2, 3]算法记录下每个缓存页面最后两次被访问的时间。
   替换页面时替换掉倒数第二次访问时间距现在最久的一项。
   在IRM (IndependentReferenceModel)访问模式下,LRU-2有着最好的预期命中率,由于LRU-2算法要维护一个优先级队列,所以该算法复杂度为logN(N为缓存队列中缓存项的数量)。
   2Q4使用LRU队列替换了LRU-2中的优先级队列,将算法时间复杂度由logN降为常数,且维护缓存项的各信息所需空间比LRU-2小。
   LIRS5维护一个变长的LRU队列,该队列的LRU端为最近至少被访问过2次的第Llirs项(Llirs为算法参数)。
   LIRS算法在IRM访问模式下可以获得很高的命中率,但对于SDD访问模式效率明显下降。
   年前服务加上了这个功能，访问越热，更新越快，效果很好。不过一些人工干预的冷剧会存在不更新或者数据不一致的问题。
   另外很久之前做的热key策略，也是基于频率做的，其实说到频率，肯定是指定时间内的次数，所以热key的具体含义是最近一段时间内的访问次数。由于有个窗口滑动，所以计数可以精确到秒级，而之前的算法就low多了，只是简单的除二，很容易波动－前期次数不够透传，后期大多数都够了不透传。

3. 访问时间与频率兼顾
   通过兼顾访问时间与频率,使得在数据访问模式变化时缓存策略仍有较好性能。如FBR、LRFU、ALRFU。
   多数此类算法具有一个可调或自适应参数,通过该参数的调节使缓存策略在基于访问时间与频率间取得一定平衡。
   FBR6维护一个LRU队列,并将该队列分为New、Middle、Old三段。
   对队列中的每一缓存项均维护一个计数值。
   当缓存中的一项被命中时,被命中的缓存项被移至New段的MRU端,如果该项原本位于Old或Middle段,则其计数值加1,原位于New段则计数值不变。
   当进行替换操作时,删除Old段计数值最小的一项(LRU端)。
   LRFU7为每一个缓存项维护一个权值C(x),其初始值为0, C(x)按以下公式变化。
   在t时刻, C(x) =1+2-λC(x): x被访问到2-λC(x)　: x未被访问进行替换操作时,C(x)值最小的一项被删除。
   当时, LRFU算法行为类似于LFU;而当时,该算法行为逼近LRU算法。该算法通过选用合适的λ值来获得时间与频率因素的平衡。
   LRFU虽然通过一个值来兼顾访问时间与频率因素,但由于值固定,当访问模式变化时,该算法无法做出相应的调整而造成性能下降。
   ALRFU8在此方面对LRFU进行了改进。通过对数据访问模式的历史进行监控,ALRFU动态调整值来适应数据访问模式的改变,表现出比LRFU更好的适应性。
   年前上的算法就是这个，不过更复杂。

4. 基于访问模式
   某些应用有较明确的的数据访问特点,进而产生与其相适应的缓存策略。
   笔者的最终模型是针对核心数据，依靠主动秒级别拉取更新更新的key列表，然后定时刷新时间小时级别。
   对于非核心数据，如定时全量更新的播放量和评分数据，缓存时间分钟级别，过期后进入过期次数逻辑。达到指定次数才刷新数据，如果在指定时间内次数不够依旧会强制刷新数据。

五、实践

1. Memached Multiget-Hole(multigut黑洞)
   对于multiget命令来说，分布式部署更多的节点，并不能提升multiget的承载量，甚至出现节点数越多，multiget的效率反而会降低，这就是multiget黑洞。
   笔者维护的服务是个三级key-value系统，也就是key-subkey-subsubkey-value的系统，其中中间两级都是最多批量支持128个的，这个问题很严重。

2. 反向Cache 对于大量不存在的key, 导致透传量很高.
   反向Cache就是将一个不存在的key放在缓存中，也就是在缓存中存一个空值。
   笔者的系统也存在这个问题，有两份数据：一份千万级别，一份十亿级别，　然后客户端无法区分数据在哪里，会先读千万级别的，导致储存大量空数据。

3. 缓存Fail-Fast (快速失败)
   当出现故障节点时，标识故障节点为不可用节点，读写不可用节点快速返回。
   公司内部有对应的负载均衡组件：l5

4. 缓存当作储存(Cache is Storage)
   缓存当作储存是指缓存中存储全量数据，不存在数据穿透的情况。
   理想是美好的，现实是残酷的，我们只能扩大缓存的储存，但是不可能储存下全量数据的。

5. dog-pile effect (狗桩效应)
   狗桩效应是由于极热访问的缓存数据失效，大量请求发现没有缓存，进而穿透至DB，导致数据库load瞬间飙高甚至宕机。
   我的经验是储存的数据增加一个重建状态来解决,重建时可以减小数据被淘汰的概率。

6. 极热点数据场景
   由于各种海量业务数据的冲刷，前端使用 local cache，命中率可能不高，性能提升也不明显.
   这个问题确实遇到了，移动端有一个统一cache, 挡掉了大量的重复数据。

7. 避免雪崩
   雪崩效应是由于缓存服务器宕机等原因导致命中率降低，大量的请求穿透到数据库，导致数据库被冲垮，业务系统出现故障，服务很难再短时间内回复。
   避免单点故障，保证缓存高命中率.
   故障期间通过降级非核心功能来保证核心功能可用性
   故障期间通过拒掉部分请求保证有部分请求还能正常响应
   清楚后端资源容量(访问底层设置防雪崩逻辑), 即使出现问题，也便于更好的流控(具体应该放量多少)
   笔者的经验是故障期间先把流量导走，然后下层全部重启，然后逐渐放量。

8. 数据一致性
   在分布式缓存中，通常要保证可用性(A)和可扩展性(P)，并折中采用数据最终一致性
   笔者做的缓存服务都是最终一致性，核心数据保证秒级别最终一致，非核心数据根据配置的策略来做到最终一致。

9. 缓存容量规划
   请求量
   命中率：预热，防止雪崩
   网络带宽：网卡、交换机
   存储容量：预估存储大小，过期策略、剔除率
   连接数
   笔者的服务实现了小set的概念，两台机器组成一个小set. 一个小set能够支持的量固定。