转载自http://blog.chinaunix.net/uid-20708886-id-5753422.html

在使用redis作为缓存的场景下，内存淘汰策略决定的redis的内存使用效率。在大部分场景下，我们会采用LRU(Least Recently Used)来作为redis的淘汰策略。本文将由浅入深的介绍redis lru策略的具体实现。
       首先我们来科普下，什么是LRU ？(以下来自*) 
 
     Discards the least recently used items first. This algorithm
requires keeping track of what was used when, which is expensive if one
wants to make sure the algorithm always
discards the least recently used item. General implementations of this
technique require keeping "age bits" for cache-lines and track the
"Least Recently Used"  cache-line based
on age-bits. In such an implementation, every time a cache-line is
used, the age of all other cache-lines changes.
      简而言之，就是每次淘汰最近最少使用的元素 。一般的实现，都是采用对存储在内存的元素采用 'age bits’ 来标记该元素从上次访问到现在为止的时长，从而在每次用LRU淘汰时，淘汰这些最长时间未被访问的元素。
    
      这里我们先实现一个简单的LRU Cache，以便于后续内容的理解 。(来自leetcod,不过这里我重新用Python语言实现了)

实现该缓存满足如下两点:
      1.get(key) - 如果该元素(总是正数)存在，将该元素移动到lru头部，并返回该元素的值，否则返回-1。
      2.set(key,value) - 设置一个key的值为value(如果该元素存在),并将该元素移动到LRU头部。否则插入一个key,且值为value。如果在设置前检查到，该key插入后，会超过cache的容量，则根据LRU策略，删除最近最少使用的key。