【Redis 源码日志】— Redis 数据淘汰机制

作者:郑思愿

出处:http://daoluan.net


概述

在 Redis 中,允许用户设置最大使用内存大小 server.maxmemory,在内存限定的情况下是很有用的。譬如,在一台 8G 机子上部署了 4 个 Redis 服务点,每一个服务点分配 1G 的内存大小,减少内存紧张的情况,由此获取更为稳健的服务。Redis 内存数据集大小上升到一定大小的时候,就会施行数据淘汰策略。Redis 提供 6 种数据淘汰策略:

  1. volatile-lru:从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用 的数据淘汰
  2. volatile-ttl:从已设置过期时间的数据集(server.db[i].expires)中挑选将要过期的数 据淘汰
  3. volatile-random:从已设置过期时间的数据集(server.db[i].expires)中任意选择数据 淘汰
  4. allkeys-lru:从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰
  5. allkeys-random:从数据集(server.db[i].dict)中任意选择数据淘汰
  6. no-enviction(驱逐):禁止驱逐数据

Redis 确定驱逐某个键值对后,会删除这个数据,并将这个数据变更消息发布到本地(AOF 持久化)和从机(主从连接)。

LRU 数据淘汰机制

在服务器配置中保存了 lru 计数器 server.lrulock,会定时(Redis 定时程序serverCorn())更新,server.lrulock 的值是根据 server.unixtime 计算出来的。

// redisServer 保存了lru 计数器
struct redisServer {
...
unsigned lruclock:22; /* Clock incrementing every minute, for LRU */
...
};

另外,从 struct redisObject 中可以发现,每一个 Redis 对象都会设置相应的 lru,即最近访问的时间。可以想象的是,每一次访问数据的时候,会更新 redisObject.lru。

LRU 数据淘汰机制是这样的:在数据集中随机挑选几个键值对,取出其中 lru 最大的键值对淘汰。所以,你会发现,Redis 并不是保证取得所有数据集中最近最少使用(LRU)的键值对,而只是随机挑选的几个键值对中的。

// 每一个redis 对象都保存了lru
#define REDIS_LRU_CLOCK_MAX ((1<<21)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 10 /* LRU clock resolution in seconds */
typedef struct redisObject {
   // 刚刚好32 bits
   // 对象的类型,字符串/列表/集合/哈希表
   unsigned type:4;
   // 未使用的两个位
   unsigned notused:2; /* Not used */
   // 编码的方式,redis 为了节省空间,提供多种方式来保存一个数据
   // 譬如:“123456789” 会被存储为整数123456789
   unsigned encoding:4;
   unsigned lru:22; /* lru time (relative to server.lruclock) */
   // 引用数
   int refcount;
   // 数据指针
   void *ptr;
} robj;

// redis 定时执行程序。联想:linux cron
int serverCron(struct aeEventLoop *eventLoop, long long id, void *clientData) {
   ......
   /* We have just 22 bits per object for LRU information.
   * So we use an (eventually wrapping) LRU clock with 10 seconds resolution.
   * 2^22 bits with 10 seconds resolution is more or less 1.5 years.
   **
   Note that even if this will wrap after 1.5 years it's not a problem,
   * everything will still work but just some object will appear younger
   * to Redis. But for this to happen a given object should never be touched
   * for 1.5 years.
   **
   Note that you can change the resolution altering the
   * REDIS_LRU_CLOCK_RESOLUTION define.
   */
   updateLRUClock();
   ......
}
   // 更新服务器的lru 计数器
void updateLRUClock(void) {
   server.lruclock = (server.unixtime/REDIS_LRU_CLOCK_RESOLUTION) &
   REDIS_LRU_CLOCK_MAX;
}

TTL 数据淘汰机制

Redis 数据集数据结构中保存了键值对过期时间的表,即 redisDb.expires,在使用 SET 命令的时候,就有一个键值对超时时间的选项。和 LRU 数据淘汰机制类似,TTL 数据淘汰机制是这样的:从过期时间 redisDB.expires 表中随机挑选几个键值对,取出其中 ttl 最大的键值对淘汰。同样你会发现,Redis 并不是保证取得所有过期时间的表中最快过期的键值对,而只是随机挑选的几个键值对中的。

无论是什么机制,都是从所有的键值对中挑选合适的淘汰。

在哪里开始淘汰数据

Redis 每服务客户端执行一个命令的时候,会检测使用的内存是否超额。如果超额,即进行数据淘汰。

// 执行命令
int processCommand(redisClient *c) {
       ......
       // 内存超额
       /* Handle the maxmemory directive.
       **
       First we try to free some memory if possible (if there are volatile
       * keys in the dataset). If there are not the only thing we can do
       * is returning an error. */
       if (server.maxmemory) {
               int retval = freeMemoryIfNeeded();
       if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {
               flagTransaction(c);
               addReply(c, shared.oomerr);
               return REDIS_OK;
       }
   }
   ......
}

这是我们之前讲述过的命令处理函数。在处理命令处理函数的过程,会涉及到内存使用量的检测,如果检测到内存使用超额,会触发数据淘汰机制。我们来看看淘汰机制触发的函数 freeMemoryIfNeeded() 里面发生了什么。

// 如果需要,是否一些内存
int freeMemoryIfNeeded(void) {
   size_t mem_used, mem_tofree, mem_freed;
   int slaves = listLength(server.slaves);
   // redis 从机回复空间和AOF 内存大小不计算入redis 内存大小
   // 关于已使用内存大小是如何统计的,我们会其他章节讲解,这里先忽略这个细节
   /* Remove the size of slaves output buffers and AOF buffer from the
   * count of used memory. */
   mem_used = zmalloc_used_memory();
   // 从机回复空间大小
   if (slaves) {
       listIter li;
       listNode *ln;
       listRewind(server.slaves,&li);
   while((ln = listNext(&li))) {
       redisClient *slave = listNodeValue(ln);
   unsigned long obuf_bytes = getClientOutputBufferMemoryUsage(slave);
   if (obuf_bytes > mem_used)
       mem_used = 0;
   else
       mem_used -= obuf_bytes;
   }
}
   // server.aof_buf && server.aof_rewrite_buf_blocks
   if (server.aof_state != REDIS_AOF_OFF) {
       mem_used -= sdslen(server.aof_buf);
       mem_used -= aofRewriteBufferSize();
   }
   // 内存是否超过设置大小
   /* Check if we are over the memory limit. */
   if (mem_used <= server.maxmemory) return REDIS_OK;
   // redis 中可以设置内存超额策略
   if (server.maxmemory_policy == REDIS_MAXMEMORY_NO_EVICTION)
       return REDIS_ERR; /* We need to free memory, but policy forbids. */
   /* Compute how much memory we need to free. */
       mem_tofree = mem_used - server.maxmemory;
       mem_freed = 0;
   while (mem_freed < mem_tofree) {
       int j, k, keys_freed = 0;
       // 遍历所有数据集
       for (j = 0; j < server.dbnum; j++) {
           long bestval = 0; /* just to prevent warning */
           sds bestkey = NULL;
           struct dictEntry *de;
           redisDb *db = server.db+j;
           dict *dict;
       // 不同的策略,选择的数据集不一样
       if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
           server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
       {
           dict = server.db[j].dict;
       } else {
           dict = server.db[j].expires;
       }
       // 数据集为空,继续下一个数据集
       if (dictSize(dict) == 0) continue;
       // 随机淘汰随机策略:随机挑选
       /* volatile-random and allkeys-random policy */
       if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
           server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
       {
           de = dictGetRandomKey(dict);
           bestkey = dictGetKey(de);
       }
   // LRU 策略:挑选最近最少使用的数据
   /* volatile-lru and allkeys-lru policy */
       else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
           server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
       {
       // server.maxmemory_samples 为随机挑选键值对次数
       // 随机挑选server.maxmemory_samples 个键值对,驱逐最近最少使用的数据
       for (k = 0; k < server.maxmemory_samples; k++) {
           sds thiskey;
           long thisval;
           robj *o;
       // 随机挑选键值对
           de = dictGetRandomKey(dict);
       // 获取键
           thiskey = dictGetKey(de);
       /* When policy is volatile-lru we need an additional lookup
       * to locate the real key, as dict is set to db->expires. */
       if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
           de = dictFind(db->dict, thiskey);
           o = dictGetVal(de);
           // 计算数据的空闲时间
           thisval = estimateObjectIdleTime(o);
           // 当前键值空闲时间更长,则记录
           /* Higher idle time is better candidate for deletion */
       if (bestkey == NULL || thisval > bestval) {
           bestkey = thiskey;
           bestval = thisval;
           }
       }
   }
   // TTL 策略:挑选将要过期的数据
   /* volatile-ttl */
   else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
   // server.maxmemory_samples 为随机挑选键值对次数
   // 随机挑选server.maxmemory_samples 个键值对,驱逐最快要过期的数据
   for (k = 0; k < server.maxmemory_samples; k++) {
   sds thiskey;
   long thisval;
   de = dictGetRandomKey(dict);
   thiskey = dictGetKey(de);
   thisval = (long) dictGetVal(de);
   /* Expire sooner (minor expire unix timestamp) is better
   * candidate for deletion */
   if (bestkey == NULL || thisval < bestval) {
       bestkey = thiskey;
       bestval = thisval;
       }
   }
}
   // 删除选定的键值对
   /* Finally remove the selected key. */
   if (bestkey) {
       long long delta;
   robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
   // 发布数据更新消息,主要是AOF 持久化和从机
   propagateExpire(db,keyobj);
   // 注意, propagateExpire() 可能会导致内存的分配,
   // propagateExpire() 提前执行就是因为redis 只计算
   // dbDelete() 释放的内存大小。倘若同时计算dbDelete()
   // 释放的内存和propagateExpire() 分配空间的大小,与此
   // 同时假设分配空间大于释放空间,就有可能永远退不出这个循环。
   // 下面的代码会同时计算dbDelete() 释放的内存和propagateExpire() 分配空间的大小// propagateExpire(db,keyobj);
   // delta = (long long) zmalloc_used_memory();
   // dbDelete(db,keyobj);
   // delta -= (long long) zmalloc_used_memory();
   // mem_freed += delta;
   /////////////////////////////////////////
/* We compute the amount of memory freed by dbDelete() alone.
* It is possible that actually the memory needed to propagate
* the DEL in AOF and replication link is greater than the one
* we are freeing removing the key, but we can't account for
* that otherwise we would never exit the loop.
**
AOF and Output buffer memory will be freed eventually so
* we only care about memory used by the key space. */
// 只计算dbDelete() 释放内存的大小
   delta = (long long) zmalloc_used_memory();
   dbDelete(db,keyobj);
   delta -= (long long) zmalloc_used_memory();
   mem_freed += delta;
   server.stat_evictedkeys++;
   // 将数据的删除通知所有的订阅客户端
   notifyKeyspaceEvent(REDIS_NOTIFY_EVICTED, "evicted",
   keyobj, db->id);
   decrRefCount(keyobj);
   keys_freed++;
   // 将从机回复空间中的数据及时发送给从机
/* When the memory to free starts to be big enough, we may
* start spending so much time here that is impossible to
* deliver data to the slaves fast enough, so we force the
* transmission here inside the loop. */
   if (slaves) flushSlavesOutputBuffers();
   }
}
   // 未能释放空间,且此时redis 使用的内存大小依旧超额,失败返回
   if (!keys_freed) return REDIS_ERR; /* nothing to free... */
   }
   return REDIS_OK;
}
赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 【Redis 源码日志】— Redis 数据淘汰机制
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏