Memcached的LRU算法

标签: memcached lru 算法 | 发表时间:2011-10-26 13:00 | 作者:kimi Eric
出处:http://www.ccvita.com/

题外话
最近计划对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 lru 算法] 推荐:

Memcached的LRU算法

- Eric - 平凡的世界
最近计划对Memcached做一些尝试性的改造,主要是针对Memcached在处理过期数据的时候进行改造,以实现在一个缓存的过期时间达到的时候,可以对该缓存的数据进行一个验证和存储的处理. 这个需求,主要是为了解决MySQL的写入瓶颈,通过延期、合并写入请求来减少MySQL的并发写入量. 现在逐渐记录出来和有需要的朋友一起讨论.

[转][转]Redis、Memcached、Guava、Ehcache中的算法

- - heiyeluren的blog(黑夜路人的开源世界)
缓存那些事,一是内存爆了要用LRU(最近最少使用)、LFU(最少访问次数)、FIFO的算法清理一些;二是设置了超时时间的键过期便要删除,用主动或惰性的方法. 今天看 Redis3.0的发行通告里说,LRU算法大幅提升了,就翻开源码来八卦一下,结果哭笑不得,这旧版的"近似LRU"算法,实在太简单,太偷懒,太Redis了.

一致性hash算法在memcached中的使用

- - CSDN博客推荐文章
  1、我们的memcache客户端(这里我看的spymemcache的源码),使用了一致性hash算法ketama进行数据存储节点的选择. 与常规的hash算法思路不同,只是对我们要存储数据的key进行hash计算,分配到不同节点存储. 一致性hash算法是对我们要存储数据的服务器进行hash计算,进而确认每个key的存储位置.

memcached+magent实现memcached集群

- - 编程语言 - ITeye博客
首先说明下memcached存在如下问题.   本身没有内置分布式功能,无法实现使用多台Memcache服务器来存储不同的数据,最大程度的使用相同的资源;无法同步数据,容易造成单点故障. (memagent代理实现集群).       在 Memcached中可以保存的item数据量是没有限制的,只要内存足够.

使用Redis作为一个LRU缓存

- - 并发编程网 - ifeve.com
原文链接  译者:flychao88. 当用Redis作为一个LRU存储时,有些时候是比较方便的,在你增添新的数据时会自动驱逐旧的数据. 这种行为在开发者论坛是非常有名的,因为这是流行的memcached系统的默认行为. LRU实际上只是支持驱逐的方式之一. 这页包含更多一般的Redis maxmemory指令的话题用于限制内存使用到一个定额,同时它也深入的涵盖了Redis所使用的LRU算法,实际上是精确LRU的近似值.

使用LinkedHashMap实现LRU缓存

- - 鸟窝
可能很多人已经知道了这个技术,但是对于我来说,虽然使用Java十余年了,最近才了解到 LinkedHashMap这个类. 使用这个类可以方便的实现一个本地的LRU Cache类. 之所以没有关注到这个类,是因为在面对本地缓存的case时,我经常会考虑 guava这个框架. 最早可以搜到的一篇关于 LinkedHashMap实现本地缓存的文章之一是这篇: How to set up a simple LRU cache using LinkedHashMap ,发表于2005年.

MemCached详解

- - CSDN博客推荐文章
首先,我们来了解一下MemCached与MemCache之间的区别:. Memcache是一个自由和开放源代码、高性能、分配的内存对象缓存系统. 用于加速动态web应用程序,减轻数据库负载. 它可以应对任意多个连接,使用非阻塞的网络IO. 由于它的工作机制是在内存中开辟一块空间,然后建立一个HashTable,Memcached自管理这 些HashTable.

Memcached调优

- - 四火的唠叨
文章系本人原创,转载请保持完整性并注明出自 《四火的唠叨》. 项目中有一个对实时响应性比较高的服务,引入了Memcached以减少延迟和减少数据库压力. 但是期间遇到了一些问题,这里记录一些调优细节. 最开始我使用的是 Memcached Java Client,但是最后放弃了,放弃原因包括:.

memcached协议

- - 开源软件 - ITeye博客
旧版: http://code.sixapart.com/svn/memcached/trunk/server/doc/protocol.txt. 新版: https://github.com/memcached/memcached/blob/master/doc/protocol.txt.

Java使用memcached

- - 互联网 - ITeye博客
首先到 http://danga.com/memcached下载memcached的windows版本和java客户端jar包,目前最新版本是memcached-1.2.1-win32.zip和java_memcached-release_1.6.zip,分别解压后即可. 然后是安装运行memcached服务器,我们将memcached-1.2.1-win32.zip解压后,进入其目录,然后运行如下命令:c:>;memcached.exe -d install
c:>memcached.exe -l 127.0.0.1 -m 32 -d start.