题外话

     最近计划对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. 分布式缓存系统 Memcached 入门    (阅读：14701)
2. 30分钟3300%性能提升――python+memcached网页优化小记    (阅读：12110)
3. Cacti 添加 Memcached 监控    (阅读：8096)
4. Redis和Memcached的区别    (阅读：6741)
5. 启用memcached压缩注意事项    (阅读：4066)
6. Memcached内存管理机制浅析    (阅读：3988)
7. MySQL数据库InnoDB存储引擎 Buffer pool LRU List Flush策略详解    (阅读：3773)
8. memcached 源码阅读笔记    (阅读：3617)
9. Memcached and MySQL    (阅读：3243)
10. Memcached的线程模型及状态机    (阅读：3241)