Redis 数据淘汰机制

港控/mmm° 2022-06-07 01:52 169阅读 0赞

## 概述 ##

在 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;
    }
    }
    // 内存是否超过设置大小
    /* 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;
    }