江苏龙网

  1. 主页 > 生活百科 > >

Redis数据淘汰算法( 三 )

算法Redis

evictionPoolPopulate() 函数首先调用 dictGetSomeKeys() 函数从缓存对象集合中获取一些样本，并保存在 samples 数组中 。
for (j = 0; j < count; j++) { unsigned long long idle; sds key; robj *o; dictEntry *de; de = samples[j]; key = dictGetKey(de); if (server.maxmemory_policy != MAXMEMORY_VOLATILE_TTL) { if (sampledict != keydict) de = dictFind(keydict, key); o = dictGetVal(de); } if (server.maxmemory_policy & MAXMEMORY_FLAG_LRU) { idle = estimateObjectIdleTime(o); } else if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) { idle = 255-LFUDecrAndReturn(o); } else if (server.maxmemory_policy == MAXMEMORY_VOLATILE_TTL) { idle = ULLONG_MAX - (long)dictGetVal(de); } else { serverPanic("Unknown eviction policy in evictionPoolPopulate()"); }上面的代码主要是获取样本缓存对象的排序权值 idel，如果使用 LRU淘汰算法，那么就调用 estimateObjectIdleTime() 函数获取排序权值，estimateObjectIdleTime() 函数用于获取缓存对象有多长时间没有被访问 。排序按照 idle 的值升序排序，就是说 idle 的值越大，就排到越后 。
k = 0; while (k < EVPOOL_SIZE && pool[k].key && pool[k].idle < idle) k++; if (k == 0 && pool[EVPOOL_SIZE-1].key != NULL) { continue; } else if (k < EVPOOL_SIZE && pool[k].key == NULL) { } else { if (pool[EVPOOL_SIZE-1].key == NULL) { sds cached = pool[EVPOOL_SIZE-1].cached; memmove(pool+k+1,pool+k, sizeof(pool[0])*(EVPOOL_SIZE-k-1)); pool[k].cached = cached; } else { k--; sds cached = pool[0].cached; if (pool[0].key != pool[0].cached) sdsfree(pool[0].key); memmove(pool,pool+1,sizeof(pool[0])*k); pool[k].cached = cached; } } int klen = sdslen(key); if (klen > EVPOOL_CACHED_SDS_SIZE) { pool[k].key = sdsdup(key); } else { memcpy(pool[k].cached,key,klen+1); sdssetlen(pool[k].cached,klen); pool[k].key = pool[k].cached; } pool[k].idle = idle; pool[k].dbid = dbid; }}上面这段代码的作用是：根据 idle 的值找到当前缓存对象所在 EvictionPoolLRU 数组的位置，然后把缓存对象保存到 EvictionPoolLRU 数组中 。以下插图解释了数据采样的过程：

Redis数据淘汰算法

文章插图
 
所以 EvictionPoolLRU 数组的最后一个元素便是最优的淘汰缓存对象 。
从上面的分析可知，淘汰数据时只是从样本中找到最优的淘汰缓存对象，并不是从所有缓存对象集合中查找 。由于前面介绍的 LRU算法 需要维护一个LRU链表，而维护一个LRU链表的成本比较大，所以Redis才出此下策 。




推荐阅读


上一篇：玩壶时要注意的方方面面

下一篇：可以从这几方面进行紫砂茶具保养