微信号:tiankonguse-code

介绍:这里是tiankonguse在代码世界里学习时的记录

谈谈cache

2017-02-19 13:05 天空的代码世界

一、缓存

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


二、组件

1. Memcached.

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


2. Redis

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


3. 自研

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


三、分布式缓存

  1. 数据分片: 区间分片、hash分片、 slot分片。

  2. 对于hash分片,主要的哈希算法有静态哈希和一致性哈希

  3. 客户端实现(memcached), PROXY 层(托管的redis)

  4. 分布式可以理解问只是将数据缩小常数倍,对于海量数据,并不能解决核心问题,反而会引入更复杂的问题。


四、算法

1. 缓存算法

缓存通过设计良好的数据分块、预取、顺序预取、缓存替换等算法来提高对缓存内容的命中率。


缓存算法可以分为基于访问时间的策略、基于访问频率的策略、访问时间与频率兼顾策略、时间距离分布策略等类型。


算法也与储存有关系,比如使用全内存储存,算法更自由。使用共享内存储存,则对应的算法限制比较多了。


2. 缓存策略

  1. 缓存什么内容

  2. 何时进行缓存

  3. 当缓存空间已满时如何进行替换,即缓存替换算法。

  4. 何时更新数据


3. 淘汰策略

  1. 基于访问时间
    此类算法按各缓存项的被访问时间来组织缓存队列,决定替换对象。
    LRU (LeastRecentlyUsed)是一种应用广泛的缓存算法。


    该算法维护一个缓存项队列,队列中的缓存项按每项的最后被访问时间排序。
    当缓存空间已满时,将处于队尾,即删除最后一次被访问时间距现在最久的项,将新的区段放入队列首部。
    但LRU算法仅维护了缓存块的访问时间信息,没有考虑被访问频率等因素,在某些访问模式下无法获得理想命中率。


    另一方面,这个算法以来多种数据结构,对于共享内存为储存的场景无法使用。
    当我们使用多阶hash的时候,我们只是对遇到的第一个过期的进行淘汰,且性能相当低效。

  2. 基于访问频率
    此类算法用缓存项的被访问频率来组织缓存。如LFU、LRU-2、2Q、LIRS。


    LFU (LeastFrequentlyUsed)按每个缓存块的被访问频率将缓存中的各块排序,当缓存空间已满时,替换掉缓存队列中访问频率最低的一项。


    与LRU的缺点类似, LFU仅维护各项的被访问频率信息,对于某缓存项,如果该项在过去有着极高的访问频率而最近访问频率较低,当缓存空间已满时该项很难被从缓存中替换出来,进而导致命中率下降。


    年前服务加上了这个功能,访问越热,更新越快,效果很好。不过一些人工干预的冷剧会存在不更新或者数据不一致的问题。


    另外很久之前做的热key策略,也是基于频率做的,其实说到频率,肯定是指定时间内的次数,所以热key的具体含义是最近一段时间内的访问次数。


    由于有个窗口滑动,所以计数可以精确到秒级,而之前的算法就low多了,只是简单的乘以一个系数,很容易波动-前期次数不够透传,后期大多数都够了不透传。

  3. 访问时间与频率兼顾
    通过兼顾访问时间与频率,使得在数据访问模式变化时缓存策略仍有较好性能。如FBR、LRFU、ALRFU。
    多数此类算法具有一个可调或自适应参数,通过该参数的调节使缓存策略在基于访问时间与频率间取得一定平衡。


    年前上的算法就是这个,不过更复杂。

  4. 基于访问模式
    某些应用有较明确的的数据访问特点,进而产生与其相适应的缓存策略。


    笔者的最终模型是针对核心数据,依靠主动秒级别拉取更新更新的key列表,然后定时刷新时间小时级别。


    对于非核心数据,如定时全量更新的播放量和评分数据,缓存时间分钟级别,过期后进入过期次数逻辑。达到指定次数才刷新数据,如果在指定时间内次数不够依旧会强制刷新数据。


五、实践

  1. Memached Multiget-Hole(multigut黑洞)
    对于multiget命令来说,分布式部署更多的节点,并不能提升multiget的承载量,甚至出现节点数越多,multiget的效率反而会降低,这就是multiget黑洞。


    笔者维护的服务是个三级key-value系统,也就是key-subkey-subsubkey-value的系统,其中中间两级都是最多批量支持128个的,这个问题很严重。

    key代表拉去什么类型的数据:如要拉去用户资料还是视频数据,就使用这个来标识

    subkey代表拉去谁的数据:用户的话是用户唯一标识,视频的话是视频的唯一标识。

    subsubkey代表拉去什么数据:如拉去用户的昵称还是头像

    value代表具体数据

  2. 反向Cache 对于大量不存在的key, 导致透传量很高.
    反向Cache就是将一个不存在的key放在缓存中,也就是在缓存中存一个空值。


    笔者的系统也存在这个问题,有两份数据:一份千万级别,一份十亿级别,然后客户端无法区分数据在哪里,会先读千万级别的,导致储存大量空数据。

    或者大部分数据的资料不完善,下层都没有储存对应的数据。

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

  4. 缓存当作储存(Cache is Storage)
    缓存当作储存是指缓存中存储全量数据,不存在数据穿透的情况。


    理想是美好的,现实是残酷的,我们只能扩大缓存的储存,但是不可能储存下全量数据的。

  5. dog-pile effect (狗桩效应)
    狗桩效应是由于极热访问的缓存数据失效,大量请求发现没有缓存,进而穿透至DB,导致数据库load瞬间飙高甚至宕机。


    我的经验是储存的数据增加一个重建状态来解决,重建时可以减小数据被淘汰的概率。

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

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

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

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


 
天空的代码世界 更多文章 TCP通信之RST apache配置命令笔记 今年一月的数据怎么差了呢 一致性hash基础知识(二) 一致性hash基础知识
猜您喜欢 CaaS环境下实践经验总结(二):监控系统部署 【神文】用文言文英语和白话文三语评述机器学习之产生式模型 【10-28】讨论下电商项目设计的逻辑安全问题 一周阅读推荐 #1 Docker 1.13.0 详细更新日志