Cache In Action

原文:http://carlosfu.iteye.com/blog/2269678

1.缓存的一些基本常识

 一、基本概念

 

1. Cache(缓存): 从cpu的一级和二级缓存、Internet的DNS、到浏览器缓存都可以看做是一种缓存。

维基百科: 写道

a store of things that will be required in the future, and can be retrieved rapidly.

(存贮数据(使用频繁的数据)的临时地方,因为取原始数据的代价太大了,所以我可以取得快一些)

     

 

 

2. Cache hit(缓存命中)(下图左)

When a data element is requested from cache and the elements exists for the given key.

3. Cahe miss(缓存未命中): 与Cache hit相反(下图右)

 

4. 缓存算法:缓存容量超过预设,如何踢掉“无用”的数据。

例如:LRU(Least Recently Used) FIFO(First Input First Output)Least Frequently Used(LFU) 等等  

5. System-of-Record(真实数据源): 例如关系型数据库、其他持久性系统等等。

   也有英文书叫做authority data(权威数据)

 

6. serialization-and-deserialization(序列化与反序列化):可以参考:序列化与反序列化(美团工程师写的,非常棒的文章)

    后面也有单独文章去分析。

   

 

 

6. Scale Up (垂直扩容) 和 Scale out (水平扩容)

 

  驴拉车,通常不是把一头驴养壮(有极限),而通常是一群驴去拉(当然每个个体也不能太差)。 

 

 

 

服务器也是一样的道理,至少互联网是这样:

7. Write-through 和 write-behind

 

8.阿姆而达定律:用于计算缓存加速比

 

 

二、缓存的种类或者类型

 

1. LocalCache(独立式): 例如Ehcache、BigMemory Go

(1) 缓存和应用在一个JVM中。

(2) 缓存间是不通信的,独立的。

(3) 弱一致性。

 

2. Standalone(单机): 

(1) 缓存和应用是独立部署的。

(2) 缓存可以是单台。(例如memcache/redis单机等等)

(3) 强一致性

(4) 无高可用、无分布式。

(5) 跨进程、跨网络

 

3. Distributed(分布式):例如Redis-Cluster, memcache集群等等

(1) 缓存和应用是独立部署的。

(2) 多个实例。(例如memcache/redis等等)

(3) 强一致性或者最终一致性

(4) 支持Scale Out、高可用。

(5) 跨进程、跨网络

 

4. Replicated(复制式): 缓存数据时同时存放在多个应用节点的,数据复制和失效的事件以同步或者异步的形式在各个集群节点间传播。(也是弱一致性)

这种用的不太多。

 

 

三、数据层访问速度:(作为开发人员要记住这些量级)

 

2.是否真的需要缓存?

一、缓存的成本和收益是什么:

 

  既然要讨论是否真的需要缓存这个问题,就要知道缓存带来的成本与收益(好处、坏处)是什么?

  收益 成本
缓存 + 后端存储(资源)
1. 加速读写

2. 降低后端负载


1. 数据不一致性

2. 代码维护成本

3. 架构复杂度

 

  上面的表格应该清楚的表达了使用缓存后的收益和成本分别是什么。下面将进行详细的解析

 

二、缓存成本与收益详解:

 

  1. 收益是很明显的,通常来说一个设计还不错的缓存系统,能够帮助你的业务实现加速读写,同时帮助降低了后端负载。

   (1) 加速读写:通常来说加速是明显的,因为缓存通常都是全内存的系统,而后端(可能是mysql、甚至是别人的HTTP, RPC接口)都有速度慢和抗压能力差的特性,通过缓存的使用可以有效的提高用户的访问速度同时优化了用户的体验。

   (2) 降低后端负载:通过缓存的添加,如果程序没有什么问题,在命中率还可以的情况下,可以帮助后端减少访问量和复杂计算(join、或者无法在优化的sql等),在很大程度降低了后端的负载。

  2. 成本:

   (1) 数据不一致性:无论你的设计做的多么好,缓存数据与权威数据源(可以理解成真实或者后端数据源)一定存在着一定时间窗口的数据不一致性,这个时间窗口的大小可大可小,具体多大还要看一下你的业务允许多大时间窗口的不一致性。

   (2) 代码维护成本:加入缓存后,代码就会在原数据源基础上加入缓存的相关代码,例如原来只是一些sql, 现在要加入k-v缓存,必然增加了代码的维护成本。

   (3) 架构复杂度:加入缓存后,例如加入了redis-cluster,一般来说缓存不会像Mysql有专门的DBA,很有可能没有专职的管理人员,所以也增加了架构的复杂度和维护成本。

 

三、如何选择?

 

  如果当前系统的访问速度和访问量能够满足现有的要求,就不必增加缓存,其实像mysql并没有那么差,一台运行良好的Mysql,扛个QPS=1000没什么问题。

  如果要加入选择了缓存,一定要能给出足够的理由,不是为了简单的show技术和想当然,最好的方法就是用数据说话:加速比有多少、后端负载降低了多少。

 

四、什么样的场景需要缓存?

 

    在公司里,据我观察,无论怎么更新架构,使用各种新技术,但是80%的项目还是离不开SQL的,下面我们以SQL作为后端数据源、以Redis作为缓存层,说一下哪些场景是需要缓存的。

1、复杂开销大的计算、降低后端负载

    以Mysql为例子,一些复杂的操作或者计算(例如大量联表操作、一些分组计算),如果不加

缓存,大量流量将在这些复杂计算的执行。

 

2. 加速请求响应

    即使单条后端数据足够快(例如select * from table where id=?),那么依然可以利用redis/memcache将这些操作进行merge做优化(例如:cache(select * from table where id in(id1,id10....idK))),从而优化整个IO链的相应时间。

 

 

附图一张:

 

3.缓存常用更新策略对比

 一、缓存的几种更新策略

 

  从下面的表格看,缓存的更新策略大致分为三种,本文将从一致性和维护成本两个方面对于三种缓存更新策略进行简要说明,因为这些东西比较理论和抽象,如哪里说得不对,欢迎拍砖。

   

  注:

  (1) 一致性:缓存和真实数据源(例如mysql, hbase, elasticsearch等等)是否存在一段时间数据的不一致。

  (2) 维护成本: 开发人员的开发和维护成本。

策略 一致性 维护成本
LRU/LIRS/FIFO算法剔除 最差
超时剔除 较差 较低
主动更新

 

二、LRU/LFU/FIFO算法剔除

 

1. 使用场景:

    通常用于缓存使用量超过了预设的最大值时候(缓存空间不够),如何对现有的数据进行清理。例如FIFO会把最新进入缓存的数据清理出去, LRU会把最近最少使用的数据清理掉。

例如:Memcache使用的是LRU,具体Memcache如何实现的,这里就不在赘述了,网上资料多的是。

例如:Redis使用maxmemory-policy这个配置作为内存最大值后对于数据的更新策略。

配置名 含义 默认值
maxmemory 最大可用内存 不使用该配置,也就对内存使用无限制
maxmemory-policy 内存不够时,淘汰策略 volatile-lru
  • volatile-lru -> 用lru算法删除过期的键值
  • allkeys-lru -> 用lru算法删除所有键值
  • volatile-random -> 随机删除过期的键值
  • allkeys-random -> 随机删除任何键值
  • volatile-ttl -> 删除最近要到期的键值
  • noeviction -> 不删除键,只返回一个错误

 

2. 常用算法:

这里不再赘述,常用的算法有如下几种:

FIFO[first in first out] 

LFU[Less Frequently Used] 

LRU[Least Recently used] 

 

 

3. 一致性

可以想象,要清理哪些数据,不是由开发者决定(只能决定大致方向:策略算法),数据的一致性是最差的。

 

4. 维护成本

这些算法不需要开发者自己来实现,通常只需要配置最大maxmemory和对应的策略即可。

开发者只需要有这个东西,知道是什么意思,选择自己需要的算法,算法的实现是由缓存服务器实现的。

 

 

三、超时剔除

 

1. 使用场景:

   就是我们通常做的缓存数据过期时间设置,例如redis和memcache都提供了expire这样的API,来设置K-V的过期时间。

   一般来说业务可以容忍一段时间内(例如一个小时),缓存数据和真实数据(例如:mysql, hbase等等)数据不一致(一般来说,缓存可以提高访问速度降低后端负载),那么我们可以对一个数据设置一定时间的过期时间,在数据过期后,再从真实数据源获取数据,重新放到缓存中,继续设置过期时间。

   例如: 一个视频的描述信息,我们可以容忍一个小时内数据不一致,但是涉及到钱的方面,如果不一致可想而知。

   

2. 一致性:

    一段时间内(取决于过期时间)存在数据一致性问题,即缓存数据和真实数据源数据不一致。

 

3. 维护成本

      用户的维护成本不是很高,只需要设置expire过期时间即可(前提是你的业务允许这段时间可能发生的数据不一致)。

 

四、主动更新

 

1. 使用背景:

   业务对于数据的一致性要求很高,需要在真实数据更新后,立即更新缓存数据。

   具体做法:例如可以利用消息系统或者其他方式(比如数据库触发器,或者其他数据源的listener机制来完成)通知缓存更新。

 

2.  一致性:

   可以想象一致性最高(几乎接近强一致),但是有个问题:如果主动更新发生了问题,那么这条数据很可能很长时间不会更新了(所以可以结合超时剔除一起使用,下面最佳实践会说到)

 

3. 维护成本:

   相当高,用户需要自己来完成更新(需要一定量的代码,从某种程度上加大了系统的复杂性),需要自己检查数据是否真的更新了之类的工作。

 

五、最佳实践

    其实最佳实践就是组合使用:

    1. 一般来说我们都需要配置超过最大缓存后的更新策略(例如:LRU)以及最大内存,这样可以保证系统可以继续运行(例如redis可能存在OOM问题)(极端情况下除外,数据一致性要求极高)。

    2. 一般来说我们需要把超时剔除和主动更新组合使用,那样即使主动更新出了问题,也能保证过期时间后,缓存就被清除了(不至于永远都是脏数据)。

4.缓存的粒度控制

一、什么是缓存粒度

 

    下面这个图是很多项目关于缓存使用最常用的一个抽象,那么我们假设storage层为mysql, cache层为redis。

 

   

 

 

    假如我现在需要对视频的信息做一个缓存,也就是需要对select * from video where id=?的每个id在redis里做一份缓存,这样cache层就可以帮助我抗住很多的访问量(注:这里不讨论一致性和架构等等问题,只讨论缓存的粒度问题)。

    我们假设视频表有100个属性(这个真有,有些人可能难以想象),那么问题来了,需要缓存什么维度呢,也就是有两种选择吧:

Java代码  

  1. (1)cache(id)=select * from video where id=#id  
  2. (2)cache(id)=select importantColumn1, importantColumn2 .. importantColumnN from video where id=#id  

 

    其实这个问题就是缓存粒度问题,我们在缓存设计应该佮预估和考虑呢?下面我们将从通用性、空间、代码维护三个角度进行说明。

 

二、全部数据和部分数据比较

 

1. 两者的特点是显而易见的:

数据类型 通用性 空间占用(内存空间 + 网络码率) 代码维护
全部数据


简单 
部分数据


 

 较为复杂

 

 

2. 通用性:

    如果单从通用性上看,全部数据是最优秀的,但是有个问题就是是否有必要缓存全部数据,认为以后会有这样的需求,但是从经验看除了非常重要的信息,那些不重要的字段基本不会在需求里出现,也就是说这种通用性 通常都是想象出来的。太多人觉得通用性是最重要的。vid拿一些基本信息,会想专辑明星。。要不要用通用性高的,于是加了全局的,通用性很重要,但是要想清楚。

 

3. 空间占用:

    很显然,缓存全部数据,会占用大量的内存,有人会说,不就费一点内存吗,能有多少钱?而且已经有人习惯了把缓存当做下水道来使用,什么都框框的往里面放,但是我这里要说内存并不是免费的,可以说是很珍贵的资源。instagram21->4G的例子就说明了这个道理,好的程序员可以帮助公司节约大量的资源。

    而且单个cache(id)也带来两个问题:序列化的开销和网络流量的开销(QPS,百倍),都是无容忽视的。

 

4. 代码维护:

    代码维护性,全部数据的优势更加明显,而部分数据一旦要加新字段就会修改代码,而且还需要对原来的数据进行刷新。

 

 

三、总结:

 

 缓存粒度问题是一个容易被忽视的问题,如果使用不当,可能会造成很多无用空间的浪费,可能会造成网络带宽的浪费,可能会造成代码通用性较差等情况,必须学会综合数据通用性、空间占用比、代码维护性 三点评估取舍因素权衡使用。

5.穿透问题

 一. 缓存穿透 (请求数据缓存大量不命中):

    缓存穿透是指查询一个一定不存在的数据,由于缓存不命中,并且出于容错考虑, 如果从存储层查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到存储层去查询,失去了缓存的意义。

    例如:下图是一个比较典型的cache-storage架构,cache(例如memcache, redis等等) + storage(例如mysql, hbase等等)架构,查一个压根就不存在的值, 如果不做兼容,永远会查询storage。

二. 危害:

     对底层数据源(mysql, hbase, http接口, rpc调用等等)压力过大,有些底层数据源不具备高并发性。

     例如mysql一般来说单台能够扛1000-QPS就已经很不错了(别说你的查询都是select * from table where id=xx 以及你的机器多么牛逼,那就有点矫情了)

     例如他人提供的一个抗压性很差的http接口,可能穿透会击溃他的服务。

     

三. 如何发现:

   我们可以分别记录cache命中数, storage命中数,以及总调用量,如果发现空命中(cache,storage都没有命中)较多,可能就会在缓存穿透问题。

   注意:缓存本身的命中率(例如redis中的info提供了类似数字,只代表缓存本身)不代表storage和业务的命中率。

   

四. 产生原因以及业务是否允许?

    产生原因有很多:可能是代码本身或者数据存在的问题造成的,也很有可能是一些恶意攻击、爬虫等等(因为http读接口都是开放的)

    业务是否允许:这个要看做的项目或者业务是否允许这种情况发生,比如做一些非实时的推荐系统,假如新用户来了,确实没有他的推荐数据(推荐数据通常是根据历史行为算出),这种业务是会发生穿透现象的,至于业务允不允许要具体问题具体分析了。

 

五. 解决方法:

解决思路大致有两个,如下表。下面将分别说明

解决缓存穿透 适用场景 维护成本
缓存空对象
1. 数据命中不高

2. 数据频繁变化实时性高


1.代码维护简单

2.需要过多的缓存空间

3. 数据不一致

bloomfilter或者压缩filter提前拦截
1. 数据命中不高

2. 数据相对固定实时性低


1.代码维护复杂

2.缓存空间占用少

       1. 缓存空对象

         

        (1). 定义:如上图所示,当第②步MISS后,仍然将空对象保留到Cache中(可能是保留几分钟或者一段时间,具体问题具体分析),下次新的Request(同一个key)将会从Cache中获取到数据,保护了后端的Storage。

        (2) 适用场景:数据命中不高,数据频繁变化实时性高(一些乱转业务)

        (3) 维护成本:代码比较简单,但是有两个问题:

             第一是空值做了缓存,意味着缓存系统中存了更多的key-value,也就是需要更多空间(有人说空值没多少,但是架不住多啊),解决方法是我们可以设置一个较短的过期时间。

             第二是数据会有一段时间窗口的不一致,假如,Cache设置了5分钟过期,此时Storage确实有了这个数据的值,那此段时间就会出现数据不一致,解决方法是我们可以利用消息或者其他方式,清除掉Cache中的数据。

        (4) 伪代码:

Java代码  

  1. package com.carlosfu.service;  
  2.   
  3. import org.apache.commons.lang.StringUtils;  
  4.   
  5. import com.carlosfu.cache.Cache;  
  6. import com.carlosfu.storage.Storage;  
  7.   
  8. /** 
  9.  * 某服务 
  10.  *  
  11.  * @author carlosfu 
  12.  * @Date 2015-10-11 
  13.  * @Time 下午6:28:46 
  14.  */  
  15. public class XXXService {  
  16.   
  17.     /** 
  18.      * 缓存 
  19.      */  
  20.     private Cache cache = new Cache();  
  21.   
  22.     /** 
  23.      * 存储 
  24.      */  
  25.     private Storage storage = new Storage();  
  26.   
  27.     /** 
  28.      * 模拟正常模式 
  29.      * @param key 
  30.      * @return 
  31.      */  
  32.     public String getNormal(String key) {  
  33.         // 从缓存中获取数据  
  34.         String cacheValue = cache.get(key);  
  35.         // 缓存为空  
  36.         if (StringUtils.isBlank(cacheValue)) {  
  37.             // 从存储中获取  
  38.             String storageValue = storage.get(key);  
  39.             // 如果存储数据不为空,将存储的值设置到缓存  
  40.             if (StringUtils.isNotBlank(storageValue)) {  
  41.                 cache.set(key, storageValue);  
  42.             }  
  43.             return storageValue;  
  44.         } else {  
  45.             // 缓存非空  
  46.             return cacheValue;  
  47.         }  
  48.     }  
  49.   
  50.   
  51.     /** 
  52.      * 模拟防穿透模式 
  53.      * @param key 
  54.      * @return 
  55.      */  
  56.     public String getPassThrough(String key) {  
  57.         // 从缓存中获取数据  
  58.         String cacheValue = cache.get(key);  
  59.         // 缓存为空  
  60.         if (StringUtils.isBlank(cacheValue)) {  
  61.             // 从存储中获取  
  62.             String storageValue = storage.get(key);  
  63.             cache.set(key, storageValue);  
  64.             // 如果存储数据为空,需要设置一个过期时间(300秒)  
  65.             if (StringUtils.isBlank(storageValue)) {  
  66.                 cache.expire(key, 60 * 5);  
  67.             }  
  68.             return storageValue;  
  69.         } else {  
  70.             // 缓存非空  
  71.             return cacheValue;  
  72.         }  
  73.     }  
  74.   
  75. }  

 

2. bloomfilter或者压缩filter(bitmap等等)提前拦截

        (1). 定义:如上图所示,在访问所有资源(cache, storage)之前,将存在的key用布隆过滤器提前保存起来,做第一层拦截, 例如: 我们的推荐服务有4亿个用户uid, 我们会根据用户的历史行为进行推荐(非实时),所有的用户推荐数据放到hbase中,但是每天有许多新用户来到网站,这些用户在当天的访问就会穿透到hbase。为此我们每天4点对所有uid做一份布隆过滤器。如果布隆过滤器认为uid不存在,那么就不会访问hbase,在一定程度保护了hbase(减少30%左右)。

              注:有关布隆过滤器的相关知识,请自行查阅,有关guava中如何使用布隆过滤器,之后会系列文章给大家介绍。

        (2) 适用场景:数据命中不高,数据相对固定实时性低(通常是数据集较大)

        (3) 维护成本:代码维护复杂, 缓存空间占用少

              第一是空值做了缓存,意味着缓存系统中存了更多的key-value,也就是需要更多空间(有人说空值没多少,但是架不住多啊),解决方法是我们可以设置一个较短的过期时间。

              第二是数据会有一段时间窗口的不一致,假如,Cache设置了5分钟过期,此时Storage确实有了这个数据的值,那此段时间就会出现数据不一致,解决方法是我们可以利用消息或者其他方式,清除掉Cache中的数据。

六、参考资料:

http://www.xwuxin.com/?p=1938

http://blog.jobbole.com/83439/ (那些年我们一起追过的缓存写法)

http://www.tuicool.com/articles/7jMZFzj

附图一张,单机负载,哈哈:

  6.雪崩问题-stampeding herd(惊逃的野牛)

一、什么是缓存雪崩

      从下图可以很清晰出什么是缓存雪崩:

      1. 由于Cache层承载着大量请求,有效的保护了Storage层(通常认为此层抗压能力稍弱),所以Storage的调用量实际很低,所以它很爽。

      2. 但是,如果Cache层由于某些原因(宕机、cache服务挂了或者不响应了)整体crash掉了,也就意味着所有的请求都会达到Storage层,所有Storage的调用量会暴增,所以它有点扛不住了,甚至也会挂掉 

 

雪崩问题在国外叫做:stampeding herd(奔逃的野牛),指的的cache crash后,流量会像奔逃的野牛一样,打向后端

 

      

    二、 缓存雪崩的危害

       

           雪崩的危害显而易见,通常来讲可能很久以前storage已经扛不住大量请求了,于是加了cache层,所以雪崩会使得storage压力山大,甚至是挂掉。   

 

    三、如何预防缓存雪崩

   

    1. 保证Cache服务高可用性:

        和飞机都有多个引擎一样,如果我们的cache也是高可用的,即使个别实例挂掉了,影响不会很大(主从切换或者可能会有部分流量到了后端),实现自动化运维。例如:

 

     memcache的一致性hash:

     

     redis的sentinel和cluster机制:

     

     

    

    

   有关memcache和redis的高可用方案,之后会有文章进行介绍。

 

  2. 依赖隔离组件为后端限流:

      其实无论是cache或者是mysql, hbase, 甚至别人的API,都会出现问题,我们可以将这些视同为资源,作为并发量较大的系统,假如有一个资源不可访问了,即使设置了超时时间,依然会hang住所有线程,造成其他资源和接口也不可以访问。

      相信大家一定遇到过这样的页面:这些应该就是淘宝的降级策略。

       
       

       降级在高并发系统中是非常正常的:比如推荐服务中,很多都是个性化的需求,假如个性化需求不能提供服务了,可以降级补充热点数据,不至于造成前端页面是个大空白(开了天窗了)

       在实际项目中,我们对重要的资源都进行隔离,比如hbase, elasticsearch, zookeeper, redis,别人的api(可能是http, rpc),让每种资源都单独运行在自己的线程池中,即使资源出现了问题,对其他服务没有影响。

       但是线程池如何管理,比如如何关闭资源池,开启资源池,资源池阀值管理,这些做起来还是相当麻烦的,幸好netfilx公司提供了一个很牛逼的工具:hystrix,可以做各种资源的线程池隔离。

        有关hystrix的详细介绍可以参考:http://hot66hot.iteye.com/blog/2155036

        hystrix附图:

       

3. 提前演练:

   在项目上线前,通过演练,观察cache crash后,整体系统和storage的负载, 提前做好预案。  

     

7.无底洞问题(multiget hole)

一、背景 

  1. 什么是缓存无底洞问题:

Facebook的工作人员反应2010年已达到3000个memcached节点,储存数千G的缓存。
他们发现一个问题--memcached的连接效率下降了,于是添加memcached节点,添加完之后,并没有好转。称为“无底洞”现象

      

 2. 缓存无底洞产生的原因:

   键值数据库或者缓存系统,由于通常采用hash函数将key映射到对应的实例,造成key的分布与业务无关,但是由于数据量、访问量的需求,需要使用分布式后(无论是客户端一致性哈性、redis-cluster、codis),批量操作比如批量获取多个key(例如redis的mget操作),通常需要从不同实例获取key值,相比于单机批量操作只涉及到一次网络操作,分布式批量操作会涉及到多次网络io。

    

    

    

 

3. 无底洞问题带来的危害:

  (1) 客户端一次批量操作会涉及多次网络操作,也就意味着批量操作会随着实例的增多,耗时会不断增大。

  (2) 服务端网络连接次数变多,对实例的性能也有一定影响。

 
4. 结论:

  用一句通俗的话总结:更多的机器不代表更多的性能,所谓“无底洞”就是说投入越多不一定产出越多。

  分布式又是不可以避免的,因为我们的网站访问量和数据量越来越大,一个实例根本坑不住,所以如何高效的在分布式缓存和存储批量获取数据是一个难点。

 

二、哈希存储与顺序存储

   在分布式存储产品中,哈希存储与顺序存储是两种重要的数据存储和分布方式,这两种方式不同也直接决定了批量获取数据的不同,所以这里需要对这两种数据的分布式方式进行简要说明:

   1. hash分布:

   hash分布应用于大部分key-value系统中,例如memcache, redis-cluster, twemproxy,即使像mysql在分库分表时候,也经常会用user%100这样的方式。

   hash分布的主要作用是将key均匀的分布到各个机器,所以它的一个特点就是数据分散度较高,实现方式通常是hash(key)得到的整数再和分布式节点的某台机器做映射,以redis-cluster为例子:

    

   问题:和业务没什么关系,不支持范围查询。

  2. 顺序分布

  

 

 3. 两种分布方式的比较:

分布方式 特点 典型产品
哈希分布
1. 数据分散度高

2.键值分布与业务无关

3.无法顺序访问

4.支持批量操作


一致性哈希memcache

redisCluster

其他缓存产品

顺序分布
1.数据分散度易倾斜

2.键值分布与业务相关

3.可以顺序访问

4.支持批量操作


BigTable

Hbase

 

 

 

三、分布式缓存/存储四种Mget解决方案

 

1. IO的优化思路:

  (1) 命令本身的效率:例如sql优化,命令优化

  (2) 网络次数:减少通信次数

  (3) 降低接入成本:长连/连接池,NIO等。

  (4) IO访问合并:O(n)到O(1)过程:批量接口(mget),

 

2.  如果只考虑减少网络次数的话,mget会有如下模型:

 

 

3. 四种解决方案:

(1).串行mget

将Mget操作(n个key)拆分为逐次执行N次get操作, 很明显这种操作时间复杂度较高,它的操作时间=n次网络时间+n次命令时间,网络次数是n,很显然这种方案不是最优的,但是足够简单。

 

 

(2). 串行IO

    将Mget操作(n个key),利用已知的hash函数算出key对应的节点,这样就可以得到一个这样的关系:Map<node, somekeys>,也就是每个节点对应的一些keys

    它的操作时间=node次网络时间+n次命令时间,网络次数是node的个数,很明显这种方案比第一种要好很多,但是如果节点数足够多,还是有一定的性能问题。

 

 

(3). 并行IO

   此方案是将方案(2)中的最后一步,改为多线程执行,网络次数虽然还是nodes.size(),但网络时间变为o(1),但是这种方案会增加编程的复杂度。

   它的操作时间=1次网络时间+n次命令时间

 

 

(4). hash-tag实现。

    第二节提到过,由于hash函数会造成key随机分配到各个节点,那么有没有一种方法能够强制一些key到指定节点到指定的节点呢?

    redis提供了这样的功能,叫做hash-tag。什么意思呢?假如我们现在使用的是redis-cluster(10个redis节点组成),我们现在有1000个k-v,那么按照hash函数(crc16)规则,这1000个key会被打散到10个节点上,那么时间复杂度还是上述(1)~(3)

      

    那么我们能不能像使用单机redis一样,一次IO将所有的key取出来呢?hash-tag提供了这样的功能,如果将上述的key改为如下,也就是用大括号括起来相同的内容,那么这些key就会到指定的一个节点上。

   例如:

    

   

Java代码  

  1. user1,user2,user3......user1000  
  2. {user}1,{user}2,{user}3.......{user}1000  

 

 

 

例如下图:它的操作时间=1次网络时间+n次命令时间

 

 

3. 四种批量操作解决方案对比:

方案 优点 缺点 网络IO
串行mget
1.编程简单

2.少量keys,性能满足要求

大量keys请求延迟严重 o(keys)
串行IO
1.编程简单

2.少量节点,性能满足要求


大量node延迟严重

o(nodes)
并行IO
1.利用并行特性

2.延迟取决于最慢的节点


1.编程复杂

2.超时定位较难

o(max_slow(node))
hash tags 性能最高
1.tag-key业务维护成本较高

2.tag分布容易出现数据倾斜

o(1)

 

 

 

 

四、总结和建议

 

    无底洞问题对资源和性能有一定影响,但是其实大部分系统不需要考虑这个问题,因为

    1. 99%公司的数据和流量无法和facebook相比。

    2. redis/memcache的分布式集群通常来讲是按照项目组做隔离的,以我们经验来看一般不会超过50对主从。   

    所以这里只是提供了一种优化的思路,开阔一下视野。

    

 

五、参考文献

  1. Facebook's Memcached Multiget Hole: More machines != More Capacity  
  2. Multiget的无底洞问题
  3. 再说memcache的multiget hole(无底洞)

8.热点key问题(mutex key) 

 一、引出热点key问题

 

       我们通常使用 缓存 + 过期时间的策略来帮助我们加速接口的访问速度,减少了后端负载,同时保证功能的更新,一般情况下这种模式已经基本满足要求了。

       但是有两个问题如果同时出现,可能就会对系统造成致命的危害:

      (1) 这个key是一个热点key(例如一个重要的新闻,一个热门的八卦新闻等等),所以这种key访问量可能非常大。

      (2) 缓存的构建是需要一定时间的。(可能是一个复杂计算,例如复杂的sql、多次IO、多个依赖(各种接口)等等)

 

       于是就会出现一个致命问题:在缓存失效的瞬间,有大量线程来构建缓存(见下图),造成后端负载加大,甚至可能会让系统崩溃 。

 

    

         

 

 

二、四种解决方案(注释:第1,2种方法来自Tim Yang博客

 

我们的目标是:尽量少的线程构建缓存(甚至是一个) + 数据一致性 + 较少的潜在危险,下面会介绍四种方法来解决这个问题:

 

1. 使用互斥锁(mutex key): 这种解决方案思路比较简单,就是只让一个线程构建缓存,其他线程等待构建缓存的线程执行完,重新从缓存获取数据就可以了(如下图)

     如果是单机,可以用synchronized或者lock来处理,如果是分布式环境可以用分布式锁就可以了(分布式锁,可以用memcache的add, redis的setnx, zookeeper的添加节点操作)。

     下面是Tim yang博客的代码,是memcache的伪代码实现

      

Java代码  

  1. if (memcache.get(key) == null) {  
  2.     // 3 min timeout to avoid mutex holder crash  
  3.     if (memcache.add(key_mutex, 3 * 60 * 1000) == true) {  
  4.         value = db.get(key);  
  5.         memcache.set(key, value);  
  6.         memcache.delete(key_mutex);  
  7.     } else {  
  8.         sleep(50);  
  9.         retry();  
  10.     }  
  11. }  

     

 

      如果换成redis,就是:

Java代码  

  1. String get(String key) {  
  2.    String value = redis.get(key);  
  3.    if (value  == null) {  
  4.     if (redis.setnx(key_mutex, "1")) {  
  5.         // 3 min timeout to avoid mutex holder crash  
  6.         redis.expire(key_mutex, 3 * 60)  
  7.         value = db.get(key);  
  8.         redis.set(key, value);  
  9.         redis.delete(key_mutex);  
  10.     } else {  
  11.         //其他线程休息50毫秒后重试  
  12.         Thread.sleep(50);  
  13.         get(key);  
  14.     }  
  15.   }  
  16. }  

 

 

       

2. "提前"使用互斥锁(mutex key):

   在value内部设置1个超时值(timeout1), timeout1比实际的memcache timeout(timeout2)小。当从cache读取到timeout1发现它已经过期时候,马上延长timeout1并重新设置到cache。然后再从数据库加载数据并设置到cache中。伪代码如下:

 

Java代码  

  1. v = memcache.get(key);  
  2. if (v == null) {  
  3.     if (memcache.add(key_mutex, 3 * 60 * 1000) == true) {  
  4.         value = db.get(key);  
  5.         memcache.set(key, value);  
  6.         memcache.delete(key_mutex);  
  7.     } else {  
  8.         sleep(50);  
  9.         retry();  
  10.     }  
  11. } else {  
  12.     if (v.timeout <= now()) {  
  13.         if (memcache.add(key_mutex, 3 * 60 * 1000) == true) {  
  14.             // extend the timeout for other threads  
  15.             v.timeout += 3 * 60 * 1000;  
  16.             memcache.set(key, v, KEY_TIMEOUT * 2);  
  17.   
  18.             // load the latest value from db  
  19.             v = db.get(key);  
  20.             v.timeout = KEY_TIMEOUT;  
  21.             memcache.set(key, value, KEY_TIMEOUT * 2);  
  22.             memcache.delete(key_mutex);  
  23.         } else {  
  24.             sleep(50);  
  25.             retry();  
  26.         }  
  27.     }  
  28. }  

 

 

 

3. "永远不过期":

    

    这里的“永远不过期”包含两层意思:

    (1) 从redis上看,确实没有设置过期时间,这就保证了,不会出现热点key过期问题,也就是“物理”不过期。

    (2) 从功能上看,如果不过期,那不就成静态的了吗?所以我们把过期时间存在key对应的value里,如果发现要过期了,通过一个后台的异步线程进行缓存的构建,也就是“逻辑”过期

   

    从实战看,这种方法对于性能非常友好,唯一不足的就是构建缓存时候,其余线程(非构建缓存的线程)可能访问的是老数据,但是对于一般的互联网功能来说这个还是可以忍受。

   

Java代码  

  1. String get(final String key) {  
  2.         V v = redis.get(key);  
  3.         String value = v.getValue();  
  4.         long timeout = v.getTimeout();  
  5.         if (v.timeout <= System.currentTimeMillis()) {  
  6.             // 异步更新后台异常执行  
  7.             threadPool.execute(new Runnable() {  
  8.                 public void run() {  
  9.                     String keyMutex = "mutex:" + key;  
  10.                     if (redis.setnx(keyMutex, "1")) {  
  11.                         // 3 min timeout to avoid mutex holder crash  
  12.                         redis.expire(keyMutex, 3 * 60);  
  13.                         String dbValue = db.get(key);  
  14.                         redis.set(key, dbValue);  
  15.                         redis.delete(keyMutex);  
  16.                     }  
  17.                 }  
  18.             });  
  19.         }  
  20.         return value;  
  21.     }  

 

 

 

4. 资源保护:

       之前在缓存雪崩那篇文章提到了netflix的hystrix,可以做资源的隔离保护主线程池,如果把这个应用到缓存的构建也未尝不可。

 

 

 

三、四种方案对比:

 

      作为一个并发量较大的互联网应用,我们的目标有3个:

      1. 加快用户访问速度,提高用户体验。

      2. 降低后端负载,保证系统平稳。

      3. 保证数据“尽可能”及时更新(要不要完全一致,取决于业务,而不是技术。)

      所以第二节中提到的四种方法,可以做如下比较,还是那就话:没有最好,只有最合适。 

解决方案 优点 缺点
简单分布式锁(Tim yang)
 1. 思路简单

2. 保证一致性


1. 代码复杂度增大

2. 存在死锁的风险

3. 存在线程池阻塞的风险

加另外一个过期时间(Tim yang)  1. 保证一致性 同上 
不过期(本文)
1. 异步构建缓存,不会阻塞线程池


1. 不保证一致性。

2. 代码复杂度增大(每个value都要维护一个timekey)。

3. 占用一定的内存空间(每个value都要维护一个timekey)。

资源隔离组件hystrix(本文)
1. hystrix技术成熟,有效保证后端。

2. hystrix监控强大。

 

 


1. 部分访问存在降级策略。

 

 

四、总结

 

   1.  热点key + 过期时间 + 复杂的构建缓存过程 => mutex key问题

   2. 构建缓存一个线程做就可以了。

   3. 四种解决方案:没有最佳只有最合适。

五、参考文献:(本文部分代码和图来自如下两篇博客)

 

  1. Memcache mutex设计模式(Tim Yang)
  2. cache中的key mutex问题解决及延伸应用
  3. 谈谈Redis的SETNX
时间: 2024-09-17 04:13:04

Cache In Action的相关文章

转贴一个有关MYSQL的文章.E文的.MySQLs Query Cache

cache|mysql A typical scenarioBoss: Our new website is crawling! How can it be, we have four state-of-the-art web servers - what's the problem?You: Well, the web servers are fine - it's the database server that's struggling.Boss: What? You told me th

picasso图片缓存框架

picasso是Square公司开源的一个Android图形缓存库,地址http://square.github.io/picasso/,可以实现图片下载和缓存功能. picasso使用简单,如下 [java] view plaincopyprint? Picasso.with(context).load("http://i.imgur.com/DvpvklR.png").into(imageView);   主要有以下一些特性: 在adapter中回收和取消当前的下载: 使用最少的内

VS 2010 和 .NET 4.0 系列之《在VS 2010中查询和导航代码》篇

本系列文章导航 VS 2010 和 .NET 4.0 系列之<ASP.NET 4 中的SEO改进 >篇 VS 2010 和 .NET 4.0 系列之<干净的Web.Config文件 >篇 VS 2010 和 .NET 4.0 系列之<起始项目模板>篇 VS 2010 和 .NET 4.0 系列之<多定向支持>篇 VS 2010 和 .NET 4.0 系列之<多显示器支持>篇 VS 2010 和 .NET 4.0 系列之<代码优化的Web开发

Android图片加载利器之Picasso源码解析

看到了这里,相信大家对Picasso的使用已经比较熟悉了,本篇博客中将从基本的用法着手,逐步的深入了解其设计原理. Picasso的代码量在众多的开源框架中算得上非常少的一个了,一共只有35个class文件,但是麻雀虽小,五脏俱全.好了下面跟随我的脚步,出发了. 基本用法 Picasso.with(this).load(imageUrl).into(imageView); with(this)方法 public static Picasso with(Context context) { if

艾伟_转载:VS 2010 和 .NET 4.0 系列之《在VS 2010中查询和导航代码》篇

本系列文章导航 VS 2010 和 .NET 4.0 系列之<ASP.NET 4 中的SEO改进 >篇 VS 2010 和 .NET 4.0 系列之<干净的Web.Config文件 >篇 VS 2010 和 .NET 4.0 系列之<起始项目模板>篇 VS 2010 和 .NET 4.0 系列之<多定向支持>篇 VS 2010 和 .NET 4.0 系列之<多显示器支持>篇 VS 2010 和 .NET 4.0 系列之<代码优化的Web开发

一起谈.NET技术,VS 2010 和 .NET 4.0 系列之《在VS 2010中查询和导航代码》篇

本系列文章导航 VS 2010 和 .NET 4.0 系列之<ASP.NET 4 中的SEO改进 >篇 VS 2010 和 .NET 4.0 系列之<干净的Web.Config文件 >篇 VS 2010 和 .NET 4.0 系列之<起始项目模板>篇 VS 2010 和 .NET 4.0 系列之<多定向支持>篇 VS 2010 和 .NET 4.0 系列之<多显示器支持>篇 VS 2010 和 .NET 4.0 系列之<代码优化的Web开发

picasso_强大的Android图片下载缓存库

 picasso是Square公司开源的一个Android图形缓存库,地址http://square.github.io/picasso/,可以实现图片下载和缓存功能.仅仅只需要一行代码就能完全实现图片的异步加载:   1 Picasso.with(context).load("http://i.imgur.com/DvpvklR.png").into(imageView);   Api看起来非常独特,是吧.     Picasso不仅实现了图片异步加载的功能,还解决了android中

HBase in Action前三章笔记

最近接触HBase,看了HBase In Action的英文版.开始觉得还行,做了些笔记,但是后续看下去,越来越感觉到实战这本书比较偏使用上的细节,对于HBase的详细设计涉及得非常少.把前三章的一些笔记帖一下,后面几章内容不打算整理了,并不是说书内容不好. key-value存储,强一致性,多个RegionServer节点对client端是不暴露细节的 使用场景:典型的web-search, capture incremental data, ad. click stream, content

ZendFramework中使用Cache缓存机制

如下图所示建立工程: 代码如下: 1.<?php2.3./**4. * IndexController - The default controller class5. *6. * @author7. * @version8. */9.10.require_once 'Zend/Controller/Action.php';11.require_once 'Zend/Cache.php';12.require_once 'Zend/Registry.php';13.require_once 'Z