关于redis Key淘汰策略的实现方法

1 配置文件中的最大内存删除策略

在redis的配置文件中,可以设置redis内存使用的最大值,当redis使用内存达到最大值时(如何知道已达到最大值?),redis会根据配置文件中的策略选取要删除的key,并删除这些key-value的值。若根据配置的策略,没有符合策略的key,也就是说内存已经容不下新的key-value了,但此时有不能删除key,那么这时候写的话,将会出现写错误。

1.1 最大内存参数设置

若maxmemory参数设置为0,则分两种情况:

*在64位系统上,表示没有限制。
*在32为系统上,是3G,redis官方文档的说法是,32位系统最大内存是4G,预留1G给系统。而且策略会自动设置为noeviction。

也就是说在32位系统上,若maxmemory设置为0,则默认是3G,当到达3G,再往reidis中写入时,则会报错。

1.2 到达最大内存时的几种删除key的策略

*  volatile-lru -> remove the key with an expire set using an LRU algorithm
    按照LRU算法(最少最近没使用)来选取,并删除已经设置了expire时间的key。
*  allkeys-lru -> remove any key accordingly to the LRU algorithm
    根据LRU算法,删除任意的key。不论这个key是否设置了expire时间。
*  volatile-random -> remove a random key with an expire set
    随机删除一个设置了expire时间的key。
*  allkeys-random -> remove a random key, any key
    随机删除任意一个key,不论这个key是否设置了expire时间。
*  volatile-ttl -> remove the key with the nearest expire time (minor TTL)
    删除具有最近终止时间值(TTL)的key。
*  noeviction -> don't expire at all, just return an error on write operations
    若没有设置终止时间,返回一个错误。

1.3 配置内存最大值策略

以下这些命令的默认策略是:volatile-lru

# At the date of writing this commands are: set setnx setex append
 # incr decr rpush lpush rpushx lpushx linsert lset rpoplpush sadd
 # sinter sinterstore sunion sunionstore sdiff sdiffstore zadd zincrby
 # zunionstore zinterstore hset hsetnx hmset hincrby incrby decrby
 # getset mset msetnx exec sort
 #
 # The default is:
 # maxmemory-policy volatile-lru

1.4 配置要删除key的检测样本个数

maxmemory-samples

由于LRU和最小TTL算法都是不是精确的算法。因此你可以选择要检测样本的个数。例如,默认情况下redis将会检查3个key,并从这3个key中选取一个最近没有使用的key。当然你可以修改检查样本的个数的值。

要修改这个值,可以通过在配置文件中设置参数:

maxmemory-samples 3

2 实现

这几种删除策略的实现都是在函数 freeMemoryIfNeeded(void) 中完成的。下面具体讲解每种策略是如何实现的。

2.1 什么时候去删除key-value

当设置了maxmemory-policy策略后,什么时候会去删除key呢?

实际上,当设置了maxmemory参数后,在处理每个命令的时候都会根据maxmemory-policy去删除对应的key值。

代码如下:

// 处理客户端的每个命令,都会调用这个函数
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. */
  // 以上意思是:若存在可以删除的key,就释放一些内存,若不存在,给客户端返回一个错误。
  if (server.maxmemory) {               // 若maxmemory不为0,则调用以下函数,释放其中一些key
    int retval = freeMemoryIfNeeded();   // 根据配置策略删除key
    if ((c->cmd->flags & REDIS_CMD_DENYOOM) && retval == REDIS_ERR) {  // 若出错,就终止处理命令,把错误返回给客户端
      flagTransaction(c);
      addReply(c, shared.oomerr);
      return REDIS_OK;
    }
  }
  ... ...
}

实战1:若没有设置maxmemory变量,即使设置了maxmemory-policy,也不会起作用。

实战2:若没有设置maxmemory变量,在处理命令时将不会调用释放策略,会加速命令的处理过程。

2.2 删除key的总体流程

当内存达到最大值时需要按策略删除老的key,所有的删除操作和删除策略的实现都是在函数freeMemoryIfNeeded()中实现的。

在执行删除策略之前,先要选取db和查找key。

总体步骤如下:

int freeMemoryIfNeeded(void) {
  size_t mem_used, mem_tofree, mem_freed;
  int slaves = listLength(server.slaves);
  mstime_t latency;

  /* 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;
    }
  }
  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;

  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;
  latencyStartMonitor(latency);
  while (mem_freed < mem_tofree) {
    int j, k, keys_freed = 0;
    // 遍历16个数据库

    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;

      // 这里要注意,若是ALLKEYS_xx策略,则直接在对应库结构的dict中查找key。
      // 若是非ALLKEYS_xx策略,也就是可能是 volatile-xxx等策略,操作的库结构将设置成expires结构。

      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;
      }
      // 若数据库的大小为0,说明没有key存在,继续在下一个数据库中查找
      if (dictSize(dict) == 0) continue;

... ... 

}

2.2 volatile-lru机制和allkeys-lru的实现

2.2.1 redis中的LRU机制

对于LRU机制,redis的官方文档有这样的解释:

Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.

However since Redis 3.0 (that is currently in beta) the algorithm was improved to also take a pool of good candidates for eviction. This improved the performance of the algorithm, making it able to approximate more closely the behavior of a real LRU algorithm.
What is important about the Redis LRU algorithm is that you are able to tune the precision of the algorithm by changing the number of samples to check for every eviction. This parameter is controlled by the following configuration directive:

maxmemory-samples 5

The reason why Redis does not use a true LRU implementation is because it costs more memory. However the approximation is virtually equivalent for the application using Redis. The following is a graphical comparison of how the LRU approximation used by Redis compares with true LRU.

大意是说,redis的LRU算法不是正真意思上的LRU。而是使用另外一种方式实现的。也就意味着,redis并不能每次都选择一个最好的key来删除。没有使用正真的LRU算法的原因是,它可能会消耗更多的内存。该算法和正真的LRU算法效果大概相同。

redis是在一小部分key中选择最优的要删除的key。这一小部分key的个数可以指定,可以在配置文件中设置参数maxmemory-samples 。

2.2.2 LRU机制的实现

freeMemoryIfNeeded()函数,首先要计算最大空余内存和目前已经使用的内存大差值,若不够了,就要释放老的key-value。

若使用的是LRU策略,就会走以下代码,先进行最优删除key的选择,然后进行删除操作:

int freeMemoryIfNeeded(void) {
  size_t mem_used, mem_tofree, mem_freed;
  int slaves = listLength(server.slaves);
  mstime_t latency;

  /* Remove the size of slaves output buffers and AOF buffer from the
   * count of used memory. */
  mem_used = zmalloc_used_memory(); // 计算目前使用的内存大小,要排除slave和AOF使用的buffer大小
  if (slaves) { //遍历slaves链表,减去slave使用的内存数量
    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;
    }
  }
  if (server.aof_state != REDIS_AOF_OFF) { //减去AOF使用的内存大小
    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;
  // 不释放内存
  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;
  latencyStartMonitor(latency);
  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;

       // 这一步要先选择淘汰取值的数据库的dict
      if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
      { //若maxmemory-policy的值是LRU或RANDOM时,直接在主数据库中进行淘汰
        dict = server.db[j].dict;
      } else { // 其他策略,在已经设置了终止时间的key中间进行淘汰。
        dict = server.db[j].expires;
      }
      if (dictSize(dict) == 0) continue; //当前数据库没有数据跳过

      /* volatile-random and allkeys-random policy */ //若是RANDOM策略中的一个
      if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
        server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
      {
        de = dictGetRandomKey(dict);
        bestkey = dictGetKey(de);
      }

      /* volatile-lru and allkeys-lru policy */// 若删除策略是LRU策略中的一个
      else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
        server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
      {
        // 根据配置文件中maxmemory_samples的值,决定做几次选择,删除的key要从这些key中选出来。
        for (k = 0; k < server.maxmemory_samples; k++) {
          sds thiskey;
          long thisval;
          robj *o;

          // 从库中随机选取一个key-value结构(dictEntry类型)的节点
          de = dictGetRandomKey(dict);
          thiskey = dictGetKey(de); // // 从该节点中获取key的字符串地址
          /* When policy is volatile-lru we need an additional lookup
           * to locate the real key, as dict is set to db->expires. */
          // 若最大内存删除策略是volatile-lru,则需要从db中查找thiskey。
          // 若是VOLATILE-xx策略,则目前操作的库的存储结构是expires,此时需要从dict中找到该key
          if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
            de = dictFind(db->dict, thiskey);
          // 获取key de的value值
          o = dictGetVal(de);
          // 查看该key的剩下的生存时间
          thisval = estimateObjectIdleTime(o);

          /* Higher idle time is better candidate for deletion */
          // 每次都从遍历的几个Key中选出lru最长的key。
          // 那么如何更新key的lru值呢?每次查找该key的时候就会更新该key的lru值,该值是系统的时间戳。
          if (bestkey == NULL || thisval > bestval) {
            bestkey = thiskey;
            bestval = thisval;
          }
        }
      }

      /* volatile-ttl */
      else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
        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;
          }
        }
      }

      ... ...
      // 到这里,要删除的最优key已经选出来了。现在进入删除阶段。
      // 不论哪种策略,只要选出了最优key,就会执行以下删除流程。

      /* Finally remove the selected key. */
      if (bestkey) {
        long long delta;

        robj *keyobj = createStringObject(bestkey,sdslen(bestkey));
        propagateExpire(db,keyobj);
        /* 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. */
        // 删除该bestkey对应的key-value值。注意这里既要从dict中删除,还要从expires中删除。
        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();
      }
    }
    if (!keys_freed) {
      latencyEndMonitor(latency);
      latencyAddSampleIfNeeded("eviction-cycle",latency);
      return REDIS_ERR; /* nothing to free... */
    }
  }
  latencyEndMonitor(latency);
  latencyAddSampleIfNeeded("eviction-cycle",latency);
  return REDIS_OK;
}

以上这篇关于redis Key淘汰策略的实现方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 浅谈redis的maxmemory设置以及淘汰策略

    redis的maxmemory参数用于控制redis可使用的最大内存容量.如果超过maxmemory的值,就会动用淘汰策略来处理expaire字典中的键. 关于redis的淘汰策略: Redis提供了下面几种淘汰策略供用户选择,其中默认的策略为noeviction策略: ·   noeviction:当内存使用达到阈值的时候,所有引起申请内存的命令会报错. ·   allkeys-lru:在主键空间中,优先移除最近未使用的key. ·   volatile-lru:在设置了过期时间的键空间中,优

  • 关于redis Key淘汰策略的实现方法

    1 配置文件中的最大内存删除策略 在redis的配置文件中,可以设置redis内存使用的最大值,当redis使用内存达到最大值时(如何知道已达到最大值?),redis会根据配置文件中的策略选取要删除的key,并删除这些key-value的值.若根据配置的策略,没有符合策略的key,也就是说内存已经容不下新的key-value了,但此时有不能删除key,那么这时候写的话,将会出现写错误. 1.1 最大内存参数设置 若maxmemory参数设置为0,则分两种情况: *在64位系统上,表示没有限制.

  • Redis中LRU淘汰策略的深入分析

    前言 Redis作为缓存使用时,一些场景下要考虑内存的空间消耗问题.Redis会删除过期键以释放空间,过期键的删除策略有两种: 惰性删除:每次从键空间中获取键时,都检查取得的键是否过期,如果过期的话,就删除该键:如果没有过期,就返回该键. 定期删除:每隔一段时间,程序就对数据库进行一次检查,删除里面的过期键. 另外,Redis也可以开启LRU功能来自动淘汰一些键值对. LRU算法 当需要从缓存中淘汰数据时,我们希望能淘汰那些将来不可能再被使用的数据,保留那些将来还会频繁访问的数据,但最大的问题是

  • redis 数据删除策略和逐出算法的问题小结

    数据存储和有效期 在 redis 工作流程中,过期的数据并不需要马上就要执行删除操作.因为这些删不删除只是一种状态表示,可以异步的去处理,在不忙的时候去把这些不紧急的删除操作做了,从而保证 redis 的高效 数据的存储 在redis中数据的存储不仅仅需要保存数据本身还要保存数据的生命周期,也就是过期时间.在redis 中 数据的存储结构如下图: 获取有效期 Redis是一种内存级数据库,所有数据均存放在内存中,内存中的数据可以通过TTL指令获取其状态 删除策略 在内存占用与CPU占用之间寻找一

  • Spring Boot监听Redis Key失效事件实现定时任务的示例

    业务场景 我们以订单功能为例说明下: 生成订单后一段时间不支付订单会自动关闭.最简单的想法是设置定时任务轮询,但是每个订单的创建时间不一样,定时任务的规则无法设定,如果将定时任务执行的间隔设置的过短,太影响效率. 还有一种想法,在用户进入订单界面的时候,判断时间执行相关操作.方式可能有很多,在这里介绍一种监听 Redis 键值对过期时间来实现订单自动关闭. 实现思路 在生成订单时,向 Redis 中增加一个 KV 键值对,K 为订单号,保证通过 K 能定位到数据库中的某个订单即可,V 可为任意值

  • redis实现加锁的几种方法示例详解

    前言 本文主要给大家介绍了关于redis实现加锁的几种方法,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 1. redis加锁分类 redis能用的的加锁命令分表是INCR.SETNX.SET 2. 第一种锁命令INCR 这种加锁的思路是, key 不存在,那么 key 的值会先被初始化为 0 ,然后再执行 INCR 操作进行加一. 然后其它用户在执行 INCR 操作进行加一时,如果返回的数大于 1 ,说明这个锁正在被使用当中. 1. 客户端A请求服务器获取key的值为1表示

  • PHP使用Redis替代文件存储Session的方法

    本文实例讲述了PHP使用Redis替代文件存储Session的方法.分享给大家供大家参考,具体如下: PHP默认使用文件存储session,如果并发量大,效率非常低.而Redis对高并发的支持非常好,所以,可以使用redis替代文件存储session. 这里,介绍下php的session_set_save_handler 函数的作用和使用方法.该函数定义用户级session保存函数(如打开.关闭.写入等). 原型如下: bool session_set_save_hanler(callback

  • PHP+redis实现添加处理投票的方法

    本文实例讲述了PHP+redis实现添加处理投票的方法.分享给大家供大家参考,具体如下: <?php header("Content-Type:text/html;charset=utf-8"); include 'lib/mysql.class.php'; $mysql_obj = mysql::getConn(); if(class_exists('Redis')){ //redis $redis = new Redis(); $redis->pconnect('127

  • 异步redis队列实现 数据入库的方法

    业务需求 app客户端向服务端接口发送来json 数据 每天 发一次 清空缓存后会再次发送 出问题之前业务逻辑: php 接口 首先将 json 转为数组 去重 在一张大表中插入不存在的数据 该用户已经存在 和新增的id 入另一种详情表 问题所在: 当用户因特殊情况清除缓存 导致app 发送json串 入库并发高 导致CPU 暴增到88% 并且居高不下 优化思路: 1.异步队列处理 2.redis 过滤(就是只处理当天第一次请求) 3.redis 辅助存储app名称(验证过后批量插入数据app名

  • redis通过pipeline提升吞吐量的方法

    案例目标 简单介绍 redis pipeline 的机制,结合一段实例说明pipeline 在提升吞吐量方面发生的效用. 案例背景 应用系统在数据推送或事件处理过程中,往往出现数据流经过多个网元: 然而在某些服务中,数据操作对redis 是强依赖的,在最近的一次分析中发现: 一次数据推送会对 redis 产生近30次读写操作! 在数据推送业务中的性能压测中,以数据上报 -> 下发应答为一次事务:而对于这样的读写模型,redis 的操作过于频繁,很快便导致系统延时过高,吞吐量低下,无法满足目标:

随机推荐

其他