Memcached的LRU算法

题外话
最近计划对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;
            }   
        }   
    }   
}

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

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

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