Memcached的LRU算法
本文最后更新于 4652 天前,其中的信息可能已经有所发展或是发生改变。

题外话
最近计划对Memcached做一些尝试性的改造,主要是针对Memcached在处理过期数据的时候进行改造,以实现在一个缓存的过期时间达到的时候,可以对该缓存的数据进行一个验证和存储的处理。

这个需求,主要是为了解决MySQL的写入瓶颈,通过延期、合并写入请求来减少MySQL的并发写入量。现在逐渐记录出来和有需要的朋友一起讨论。当然,今天的主要内容是关于LRU的部分。

LRU算法
LRU是Least Recently Used最近最少使用算法。源于操作系统使用的一种算法,对于在内存中但最近又不用的数据块叫做LRU,操作系统会将那些属于LRU的数据移出内存,从而腾出空间来加载另外的数据。

我们来看Memcached(版本 1.4.9)的相关代码:

/* expires items that are more recent than the oldest_live setting. */
void do_item_flush_expired(void) {
    int i;
    item *iter, *next;
    if (settings.oldest_live == 0)
        return;
    for (i = 0; i < LARGEST_ID; i++) {
        /* The LRU is sorted in decreasing time order, and an item's timestamp
         * is never newer than its last access time, so we only need to walk
         * back until we hit an item older than the oldest_live time.
         * The oldest_live checking will auto-expire the remaining items.
         */
        for (iter = heads[i]; iter != NULL; iter = next) {
            if (iter->time >= settings.oldest_live) {
                next = iter->next;
                if ((iter->it_flags & ITEM_SLABBED) == 0) {
                    do_item_unlink(iter);
                }
            } else {
                /* We've hit the first old item. Continue to the next queue. */
                break;
            }
        }
    }
}

属于LRU的item是被时间逆序排序了,一个item的失效时间应该是永远比它自身上次被访问的时间大。所以在找到一个item的失效时间比oldest_live这个时间小之前,我们只需要把已经逆序排序的item继续往结尾遍历即可,一旦找到这个item,其他剩余的item也就可以判定为过期了。

如何改动?
我们的思路是让Memcached来作为MySQL的中间承接方,其实LRU算法并不是最适合。列举两种方案:

  1. 继续采用LRU算法,我们需要对Memcached进行改造的是do_item_flush_expired这个函数的执行频度,同时改造do_item_unlink函数来适应需求。
  2. 改用FIFO(先入先出)算法,彻底放弃Memcachd的整个过期处理机制或者另外添加一个FIFO算法序列,来专门为我们的业务需要服务。

为什么写这篇文章?
想写出来和大家一起讨论,看有没有其他的一些更好的用来解决MySQL写入并发的方案。

参考资料
对Memcached有疑问的朋友可以参考下列文章:
Linux下的Memcache安装https://kimi.pub/257.html
Windows下的Memcache安装https://kimi.pub/258.html
Memcache基础教程https://kimi.pub/259.html
Discuz!的Memcache缓存实现https://kimi.pub/261.html
Memcache协议中文版https://kimi.pub/306.html
Memcache分布式部署方案https://kimi.pub/395.html
Memcached的LRU算法https://kimi.pub/449.html

评论

  1. 13 年前
    2011-10-26 16:12:07

    你的意思是要改造Memcache,当其中某个数据过期被删除前,先将它存入Mysql?
    这样不太好吧。Memcache本身就是一个高速缓存,把他和Mysql绑起来,难免会有问题。假如Memcache满了,然后有大量新数据涌进来,那么Memcache中过期数据往Mysql中转存这一步就有可能会是一个瓶颈,旧数据被清掉的太慢,新数据保存失败。
    我觉得还是单独写个脚本定时将MC中的数据转存入Mysql比较好。
    另外Memcache也可以考虑换成Redis,Redis可以做执久化和replication,防止进程重启或者突然挂掉导致数据丢失。

    • 博主
      ElmerZhang
      13 年前
      2011-10-26 16:57:41

      怪我没说清楚,比如我们的业务模型就是社交游戏,社交游戏的用户特点,就是上线之后开始游戏,操作时候十分钟之内关闭游戏下线。我们先定义PHP和MySQL之间有个中间件叫Mcache

      在这个过程中,比如用户刚上线

      SELECT money,exp FROM user WHERE uid = ‘1’;

      于是PHP把这个query通过PHP扩展发给了Mcache,Mcache接到这个query,发现没有数据,于是就向MySQL查到数据存下来再返回给PHP;
      几分钟之后,又来了一个操作,加了4个金币

      UPDATE user SET money=money+4 WHERE uid = ‘1’;

      这时候,Mcache接到这个query,发现已经有数据了,就直接在Mcache中对这个数据修改;
      几分钟之后,又来了一个操作,加了10个金币 5点经验

      UPDATE user SET money=money+4, exp=exp+5 WHERE uid = ‘1’;

      这时候,Mcache接到这个query,发现已经有数据了,就直接在Mcache中对这个数据修改;
      又来了一个操作,请求用户当前的金币和经验

      SELECT money,exp FROM user WHERE uid = ‘1’;

      这时候,Mcache直接就把最新的query发给PHP去了。

      当30分钟之后,Mcache自动将这条记录update给MySQL。

      这样能减少对MySQL的写入并发,之所以不用NOSQL的方案,是目前NOSQL的方案无法解决回档的问题。而MySQL在热备、增量备份方面的优势是NOSQL方案无法比拟的。你说呢?

      • Kimi
        13 年前
        2011-10-26 17:34:40

        明白了。那么将数据读到缓存,更新缓存,将缓存数据持久化到Mysql,都应该是Mcache这个中间件做的事情,而不是Memcached做的,所以只要把这个中间件做好就OK了呀。
        我提到Redis的意思是让它替代Memcache做缓存,而不是做持久化存储。
        关键数据确实仍然应该用Mysql存储,NoSQL在数据备份、恢复等方面比Mysql还差点。

        • 博主
          ElmerZhang
          13 年前
          2011-10-26 19:15:33

          确实,关键性的数据还是得用MySQL存储。为了避免制造重复车轮,计划是在Memcached代码上去做Mcache这个东西。然后开源发出来。有木有兴趣的说~

      • kaka
        Kimi
        13 年前
        2011-10-26 23:18:36

        思路确实不错,“写”也可以放内存中执行了。。。

        不过如何应对灾难情况呢?比如:

        “当30分钟之后,Mcache自动将这条记录update给MySQL” —

        这半小时内,会用内存来存一些金币或经验的操作数据,如果出现了XXX问题造成了机器重启,内存数据丢失又如何应对呢?

        • 博主
          kaka
          13 年前
          2011-10-27 9:35:25

          在这种情况下每个用户会最多丢失半个小时的数据。任何不在计划内的机器重启对MySQL都有可能造成致命性的损害。当然这种不在计划内的机器重启对Mcache也会造成致命性的损害(丢失半个小时的数据)。

          • kaka
            Kimi
            13 年前
            2011-10-27 18:23:42

            任何不在计划内的机器重启是可能会造成致命伤害,不过如果是从怎样把这种伤害降到最小的角度来讨论呢??

            比如,若用redis是不是出现XXX情况会好一些?

            redis也是基于内存存储的,不过同时具有以下特点:

            1、redis具有持久化机制,可以定期将内存中的数据持久化到硬盘上。

            2、redis具备binlog功能,可以将所有操作写入日志,当redis出现故障,可依照binlog进行数据恢复。

          • 博主
            kaka
            13 年前
            2011-10-27 18:41:09

            说的有道理,主要是我之前读过Memcached的代码,所以就直接想到用Memcached了。利用Memcached处理过期数据的时候将数据写入MySQL中去。

            我来研究下Redis的代码,看什么时候做这个写入MySQL的操作比较合适。

          • kaka
            kaka
            13 年前
            2011-10-27 22:49:30

            redis这2年很火的,sina微博就是用的redis。。

            不过我的项目没达到那个量级,所以只是看过一些资料,没有实践经验。。希望以后可以看到kimi兄的分享哦~~~ :)

          • 博主
            kaka
            13 年前
            2011-10-28 16:22:00

            之前公司有研究过redis,主要是当时redis需要内存完全大于数据,否则会有性能问题,持久化的特点数据亦不会自动过期,所以就没过多关注,在这点上,Membase就完全超过redis。

          • kaka
            kaka
            13 年前
            2011-10-30 0:14:38

            Membase 能搜到的资料还是比较少的,在你的一篇blog上看到过介绍,貌似优点很多。。。

            想请教下kimi兄在生产环境实践中,有无遇到什么问题或者瓶颈??如果现在一个项目想选择nosql的缓存方案,

            是否是首推Membase??

          • 博主
            kaka
            13 年前
            2011-10-30 18:17:06

            看数据量吧,目前是各有优缺点,我们是在生产环境采用的Membase,放弃Tokyotyrant、Redis也是有原因的,推荐采用Membase,但是Membase的资料却是太少了。

          • tcl
            kaka
            13 年前
            2011-11-20 1:19:25

            1.个人觉得哪有完美的方案,没有。都是看实际需求,可以不可以满足。出现错误情况能不能忍受,能忍受到什么程度的错误
            2.当时做游戏的时候也是将数据写到memcached,然后后台有个程序定时的从memcached中取数据,写到mysql,往memcached中的写数据的时候设置永不过期,后台程序取走数据,写到mysql的时候再设置memcached中数据过期。但是数据都放到了memcached中了。万一memcached挂了,就歇菜了。这块是不是写的时候写到两个memcached中,还是说写到一个memcached集群里面。

  2. sogo
    12 年前
    2012-1-30 11:55:10

    cache 除了解决高并发方面的问题,想请教一下,读cache 与读取mysql 的时间上面,那个更快,如果评测?

  3. 12 年前
    2012-3-30 19:17:12

    博主.你的代码插件用的是啥,能否告知?

  4. 8 年前
    2016-5-16 15:11:47

    评论内容比主题有看点

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇