• Feeds

  • Memcache mutex设计模式

    周六的S2 Web 2.0技术沙龙上介绍了memcache中使用mutex场景(文后要演讲稿),有网友对详情感兴趣,简单介绍如下。

    场景

    Mutex主要用于有大量并发访问并存在cache过期的场合,如

    • 首页top 10, 由数据库加载到memcache缓存n分钟
    • 微博中名人的content cache, 一旦不存在会大量请求不能命中并加载数据库
    • 需要执行多个IO操作生成的数据存在cache中, 比如查询db多次

    问题

    在大并发的场合,当cache失效时,大量并发同时取不到cache,会同一瞬间去访问db并回设cache,可能会给系统带来潜在的超负荷风险。我们曾经在线上系统出现过类似故障

    解决方法

    方法一
    在load db之前先add一个mutex key, mutex key add成功之后再去做加载db, 如果add失败则sleep之后重试读取原cache数据。为了防止死锁,mutex key也需要设置过期时间。伪代码如下
    (注:下文伪代码仅供了解思路,可能存在bug,欢迎随时指出。)

    if (memcache.get(key) == null) {
        // 3 min timeout to avoid mutex holder crash
        if (memcache.add(key_mutex, 3 * 60 * 1000) == true) {
            value = db.get(key);
            memcache.set(key, value);
            memcache.delete(key_mutex);
        } else {
            sleep(50);
            retry();
        }
    }

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

    v = memcache.get(key);
    if (v == null) {
        if (memcache.add(key_mutex, 3 * 60 * 1000) == true) {
            value = db.get(key);
            memcache.set(key, value);
            memcache.delete(key_mutex);
        } else {
            sleep(50);
            retry();
        }
    } else {
        if (v.timeout <= now()) {
            if (memcache.add(key_mutex, 3 * 60 * 1000) == true) {
                // extend the timeout for other threads
                v.timeout += 3 * 60 * 1000;
                memcache.set(key, v, KEY_TIMEOUT * 2);
    
                // load the latest value from db
                v = db.get(key);
                v.timeout = KEY_TIMEOUT;
                memcache.set(key, value, KEY_TIMEOUT * 2);
                memcache.delete(key_mutex);
            } else {
                sleep(50);
                retry();
            }
        }
    }

    相对于方案一
    优点:避免cache失效时刻大量请求获取不到mutex并进行sleep
    缺点:代码复杂性增大,因此一般场合用方案一也已经足够。

    方案二在Memcached FAQ中也有详细介绍 How to prevent clobbering updates, stampeding requests,并且Brad还介绍了用他另外一个得意的工具 Gearman 来实现单实例设置cache的方法,见 Cache miss stampedes,不过用Gearman来解决就感觉就有点奇技淫巧了。

    附:本次Web2.0技术沙龙演讲主题:微博Cache设计谈,需下载请点击演讲稿下menu/download (需登录slideshare)。

    如想及时阅读Tim Yang的文章,可通过页面右上方扫码订阅最新更新。

    « | »

    57 Comments  »

    1. 关于memCache Mutex 的做法,,InfoQ 北京 2010时, Facebook也介绍过类似的处理, 控制并发的场景使用Mutex或者Latch还是个必须的操作啊.

    2. 我在项目中用 memcache mutex 做锁,结果 code review 的时候,被人说成“山寨”了。

    3. Tim

      那是因为这个问题普及得还不够,需要你去布道

    4. tim yang那天讲得非常不错,感同身受,我今天也写了一篇博客 http://www.cnblogs.com/sunli/archive/2010/07/27/cache_key_mutex.html做了这个问题的补充

    5. Chancey

      仔细想了想,方案二判断了timeout1,这实际上跟未命中缓存是一个道理,甚至更多了一层判断,在并发高的时候,除了add mutex的请求外,其他请求仍然会休眠直至获取到缓存并且timeout1无过期

    6. yq

      做一个类似代理的layer去负责和memcache交互不就好了。当然系统复杂度会加大很多,但是可以等开源的系统出来。

    7. @yq: 通过代理和memcache交互不是一样的吗?

    8. 我怎么感觉搞复杂了呢,对付cache穿透问题,最简单的方法设置cache的时候,cache永不过期,然后系统通过cron定期“主动”更新cache。

    9. 我前面想简单了,忘了如果是多用户系统,用cron同时更新成千上万用户的用户信息,是不可能的。

    10. yq

      我说的不准确 不是代理 是让memcache直接和mysql交互

    11. Tin

      这次QCon的时候Facebook的那位工程师不是介绍了Facebook的加锁方法?使用Copy on write,但是争write的锁,失败的使用stale数据。类似Tim Yang说的第一种方案吧。

    12. Robin

      抱歉,我一直想问一下libmemcached不是有CAS吗?难道CAS不是用来解决并发原子的问题的?

    13. @Robin: libmemcached的cas也即是新版的memcached提供的cas功能,这个是用来保证多个客户端对memcached的操作通过无锁的方式实现原子性,如果数据已被其它用户修改过,则放弃保存,cas是没有加锁用于等待的,Tim Yang讲的是对数据库的相同操作加锁,一旦有一个用户查询数据重建缓存成功,那么剩下的用户就不用再去查询数据库了,这里解决的是解决重复查库的资源浪费。

    14. tszming

      方案二中,如果能接受到在短时间使用 stale 的数据,在第二个判断就不必用 mutex和 sleep,实现起来也相对容易。

    15. filebat

      感觉第二种方法的优点是在memcache还没有被刷新前, 减少读到dirty data的概率。

      没有看出来作者说的“避免cache失效时刻大量请求获取不到mutex并进行sleep”,这个优点。

    16. 当竞争不到锁的时候,为什么不直接返回旧的cache数据而要sleep呢?

    17. hanguokai

      ehcache中也提到了这个问题,和解决方法。还有个名字,叫作“Thundering Herd”,http://ehcache.org/recipes/thunderingherd.html

    18. lcycenter

      收益匪浅!!!

      上面的:
      v.timeout now() 吧?

    19. lcycenter

      收益匪浅!!!

      上面的“v.timeout 小等于 now()” 应该是 “v.timeout 大等于 now()”吧?

    20. 5w台灯

      这种写法有个问题,当MC当机后,出现死循环。

    21. Baokui Yang

      同前几位留言的看法一样,如果严格按上述伪码实现,两策略感觉本质上是一样的,第二种也达不到,timYang所言“避免cache失效时刻大量请求获取不到mutex并进行sleep”,的效果。

      感觉只需把第二种方案最后一个分支:
      else {
      sleep(50);
      retry();
      }
      改成使用stale值即可(其实这个时候还没stale,只是timeout1到了)
      不知是否timyang 手误:)

    22. chenbw

      第二种方案最后一个分支:
      else {
      sleep(50);
      retry();
      }

      个人认为也是可以的
      这样可以拿到最新数据

    23. conan

      如果无法连接到memcached的话会陷入死循环吧

    24. Jarvis

      请问PPT中提到的outbox hot vector中,hot是如何度量的?

    25. lzh

      第二种方法不错,学习了

    26. xiukuan

      第二种方案的第二个分支应该直接返回数据吧?
      因为实际上数据还没过期(memcache可以取到),只是到了可以更新的地步
      不让的话好像和第一种方案差不多了,都是等待写入锁

    27. 楼拴柱

      这种内存cache失效,且需要更新的情况,我想是否可以如下实现:
      1,cache并不马上移除,而是可以提供前台的读取访问,有总比没有好,取到过期数据总比没有数据好。
      2,把cache失效的key放到后台,由后台线程后台获取数据,并更新到cache中,保证每个失效的key只有一个去后台读取数据的原子操作,降低DB的压力。
      3,接下来的前台请求读到的数据就是新数据了。

      请杨老师指点。

    28. 技术深奥,真是高手QQ呵呵

    29. bright

      确实,方案2控制的思路更加精细,增加mutex key失败后retry是合理的,因为tim要实现的是”要取到最新数据且避免数据库访问压力”,楼上有人提出直接返回cache中timeout1已经过期的数据也是合理的,但超出了tim的前提场景了。

    30. 有两个问题:
      1.
      // load the latest value from db
      v = db.get(key);
      v.timeout = KEY_TIMEOUT;
      memcache.set(key, value, KEY_TIMEOUT * 2);

      这里的value是指什么?上下文也没出现过,是不是写错了。

      2.
      if( v.timeout now()时直接返回。

    31. 回复的内容怎么丢掉了了。
      第二个问题是:
      每次
      if (v.timeout now()) 时就直接返回吧。

    32. 第二个问题是:
      每次 if (v.timeout now()) 就直接返回了

    33. 如果捕捉不到内容,则把key扔进队列,然后定期把队列里的内容再此扔进cache中,前端只是做个友好界面提醒。。。

    34. 队列和数据库交互,把数据扔进cache中。

    35. 呃。。。这个不是很了解。。。

    36. xfly

      项目中就是使用的这种分布式缓存+mutex的方式控制并发,当时还跟架构小pk了下,现在终于有新的依据了,hoho~~:D

    37. bingobird

      第一种方案有点危险,如果批量请求是一个DB中不存在的值,则会引发线程堵塞(因为retry也不会有数据)。可以将retry改成判断锁是否存在。
      第二种方案里,如果没拿到锁,sleep跟retry也可以不做了,因为毕竟没有过期。
      (有些同学说为了拿到最新数据,但阻塞在此为了拿新数据实在不划算)

    38. 第二种方法不错

    39. zgl

      1 无止境的retry确实不太合适,我的做法是retry3次之后,则放弃并做合适的后续动作;此外可以考虑一些trick,比如每次sleep的时间逐渐增加。
      2 extend timeout没有必要,不如直接保证timeout1-timeout2足够大(至少大于一次DB查询的时间)
      3 拿不到更新锁的线程完全可以返回当前的cache值:a 此时不算脏数据,b 否则就失去这个提前预判cache失效思路的最大价值了

      if ((retVal = cache.getAsExpireableCacheObjectWrapper(key))!=null) {

      if (!retVal.isAboutToExpire(expireThreshold)) {
      return retVal;
      }
      //need pre-refresh the cache.
      return preRefreshCache();

      } else {
      return whenCacheMissed();
      }

      preRefreshCache() {
      //set flag
      if (!getCacheUpdateLock(…,10s)) {
      //Failed: Some other guy is refreshing -> return v
      return retVal;
      }
      //Success: I should do this refresh
      Object object = DB.query(…);
      Object put = cache.put(key, new ExpireableCacheObjectWrapper(object,expireOffsetSec,System.currentTimeMillis()), expireOffsetSec);
      //reset refresh flag.
      releaseCacheUpdateLock(…);
      return object;
      }

      whenCacheMissed() {
      if (!getCacheUpdateLock(…,10s)) {
      // some other guy is doing the DB job.
      //sleep and then re-check the cache
      Thread.sleep(1000);
      ExpireableCacheObjectWrapper retVal;
      int i=0;
      while ((retVal = cache.getAsExpireableCacheObjectWrapper(key))==null&&i<3) {
      i++;
      Thread.sleep(1000);
      }
      if (retVal==null) {
      throw new IllegalStateException("cache[key:" +key+
      "] waited for the DB guy for … seconds, and still no luck. fail this action, throw Exception.");
      }
      //cache hit on subsequent check(s)
      return retVal;
      } else {
      //query DB and then feed cache.
      //and then release flag
      Object obj = DB.query(…);
      Object put = cache.put(key, new ExpireableCacheObjectWrapper(obj,expireOffsetSec,System.currentTimeMillis()),expireOffsetSec);
      releaseCacheUpdateLock(…);
      return obj;
      }
      }

    40. 无论是第一和第二种方法,不停的retry肯定不行,当某个读DB的操作非常耗费时间的时候,很多请求都会阻塞。但是如果设置一个retry次数,那么就意味着,如果DB读取超时,返回的数据就会是空。不知道各位有何高见?

    41. stevencjh

      第二个 解决方案的第二个判断应该是直接返回cache值吧,否则跟第一种没有任何区别啊

    42. daydayup

      但是这种方式应该还是不能解决应用分布在多台机器上的时候可能会出现的thundering herd的情况,好想只能用来解决单机上的多进程/多线程之间访问出现cache失效的时候可能出现的情况。

    43. qingchao

      memcache.add(key_mutex, 3 * 60 * 1000) == true
      如果不加value的话,过期时间不生效~

    44. “文后要演讲稿”链接在我这里失效了,代理到教育网也不行,可不可以更新下?

    45. Short, sweet, to the point, FRatEexEc-ly as information should be!

    46. What a bunch of bigots you are. Armchair pundits, who have no idea what the conference is about. I have at least participated and am in a position to comment; you are not. HRH Prince Hassan made an effort to promote, peace and unnedstadring. Shame on you, but your ilk, does not understand the concept of shame. Please, enough, about your suffering.

    Leave a Comment