题外话
最近计划对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算法并不是最适合。列举两种方案：