探究redis和memcached的 LRU算法--------redis的LRU的实现

vlei

　　一直对这redis和memcached的两个开源缓存系统的LRU算法感兴趣。今天就打算总结一下这两个LRU算法的实现和区别。
　　首先要知道什么是LRU算法：LRU是Least Recently Used 近期最少使用算法。相关的资料网上一大堆。http://en.wikipedia.org/wiki/Cache_algorithms#LRU

　　
redis的六种策略


rewriteConfigEnumOption(state,"maxmemory-policy",server.maxmemory_policy,
"volatile-lru", REDIS_MAXMEMORY_VOLATILE_LRU,
"allkeys-lru", REDIS_MAXMEMORY_ALLKEYS_LRU,
"volatile-random", REDIS_MAXMEMORY_VOLATILE_RANDOM,
"allkeys-random", REDIS_MAXMEMORY_ALLKEYS_RANDOM,
"volatile-ttl", REDIS_MAXMEMORY_VOLATILE_TTL,
"noeviction", REDIS_MAXMEMORY_NO_EVICTION,
NULL, REDIS_DEFAULT_MAXMEMORY_POLICY);

• volatile-lru：从已设置过期时间的数据集（server.db.expires）中挑选最近最少使用的数据淘汰
  
• volatile-ttl：从已设置过期时间的数据集（server.db.expires）中挑选将要过期的数据淘汰
  
• volatile-random：从已设置过期时间的数据集（server.db.expires）中任意选择数据淘汰
  
• allkeys-lru：从数据集（server.db.dict）中挑选最近最少使用的数据淘汰
  
• allkeys-random：从数据集（server.db.dict）中任意选择数据淘汰
  
• no-enviction（驱逐）：禁止驱逐数据
  

　　而lru算法经常是被用在缓存系统，就比如我们的memcached和redis上。
　　首先介绍一下redis的。我去最近刚发布的redis3.0上搜索一下代码，通过它的代码实现和如何实现lru来讲解。
　　/* The actual Redis Object */
#define REDIS_LRU_BITS 24
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1000 /* LRU clock resolution in ms */
typedef struct redisObject {
unsigned type:4;
unsigned encoding:4;
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount;
void *ptr;
} robj;
/* Macro used to obtain the current LRU clock.
* If the current resolution is lower than the frequency we refresh the
* LRU clock (as it should be in production servers) we return the
* precomputed value, otherwise we need to resort to a function call. */
#define LRU_CLOCK() ((1000/server.hz <= REDIS_LRU_CLOCK_RESOLUTION) ? server.lruclock : getLRUClock())
　　unsigned int getLRUClock(void) {
return (mstime()/REDIS_LRU_CLOCK_RESOLUTION) & REDIS_LRU_CLOCK_MAX;
}





定义相关的一些lru的一些常量，并将　　 unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

讲object的成员加入一个24位长度的lru成员。
　　


　　


我们发现使用最简单粗暴的方式，就是和ALL -key机制是一样，随机选出16个。通过过期时间对pool内存数据进行淘汰。
　　  /* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
struct evictionPoolEntry *pool = db->eviction_pool;
while(bestkey == NULL) {
evictionPoolPopulate(dict, db->dict, db->eviction_pool);
/* Go backward from best to worst element to evict. */
for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
if (pool[k].key == NULL) continue;
de = dictFind(dict,pool[k].key);
/* Remove the entry from the pool. */
sdsfree(pool[k].key);
/* Shift all elements on its right to left. */
memmove(pool+k,pool+k+1,
sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
/* Clear the element on the right which is empty
* since we shifted one position to the left.  */
pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;
/* If the key exists, is our pick. Otherwise it is
* a ghost and we need to try the next element. */
if (de) {
bestkey = dictGetKey(de);
break;
} else {
/* Ghost... */
continue;
}
}
}
}

通过lru来淘汰，返回lru时间，然后通过当前lru比较
　　/* Given an object returns the min number of milliseconds the object was never
* requested, using an approximated LRU algorithm. */
unsigned long long estimateObjectIdleTime(robj *o) {
unsigned long long lruclock = LRU_CLOCK();
if (lruclock >= o->lru) {
return (lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
} else {
return (lruclock + (REDIS_LRU_CLOCK_MAX - o->lru)) *
REDIS_LRU_CLOCK_RESOLUTION;
}
}
　　



在servercron会定时更新起LRU的时间。随机找到maxmemeory中的key，然后根据lru数&#20540;进行删除。
因为unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {


这个方法是通过随机得来的数据。



总结：
redis只是每个Object维护一个相对的时间,淘汰时,随机取3个或者更多的,找到最老的进行淘汰.这样节省了双链表的指针开销,读时还不用加锁.虽不能保证一定淘汰最老的,但倾向于淘汰偏老的对象,
经过我们线上的实测:和标准的LRU对比,命中率的损失非常小, 效果不错。





更多文章，欢迎访问
http://blog.iyunv.com/wallwind






　　


　　


　　


　　




　　


　　


　　








　　
　　


　　





版权声明：本文为博主原创文章，未经博主允许不得转载。