Redis(5.0.3)内存淘汰LRU/LFU

May 20, 2019
Redis
源码分析
Redis

简介

redis的LRU与LFU都是概率算法。并不是绝对准确的LRU或LFU算法。

Redis在内存满载时触发内存淘汰，最开始是有概率淘汰掉一些不应该淘汰的key。但它会越来越准。这一切都是因为Redis采用了一个全局池子来存放待淘汰key，池子是带序的，按key的空闲时间从小到大。

每次入池子的key，都是从keyspace(db->dict或db->expires)中随机挑选的(随机挑选的个数由maxmemory-samples参数控制，默认5个)。在入池的时候，如果池子里已经有key，就采用插入的思想，把新key插在合适的位置保持池子有序。

例如池子末端有空间：e要放进[a,b,c,d,NULL]中c的位置，先挪成[a,b,c,c,d]，然后把e覆盖进去，变成[a,b,e,c,d]。

池子末端没有空间：e要放进[a,b,c,d]中c的位置，先挪成[b,c,c,d]，然后把e覆盖进去，变成[b,c,e,d]

key的空闲时间又是如何记录的？

LRU或LFU策略都共用了redisObject里的lru字段，它总长24位，前16位用于LRU，而LFU则用到24位。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#define LRU_BITS 24
typedef struct redisObject {
    // var:4 的写法用了位域
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount;
    void *ptr;
} robj;

而LFU也分成前16位和后8位来用，前16位和LRU保持一致，用来放置访问时间。后8位用来存放访问次数。

8位的上限是255，怎样存放访问次数？Redis用了一个基于概率的对数计数器。效果大概是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


# +--------+------------+------------+------------+------------+------------+
# | factor | 100 hits   | 1000 hits  | 100K hits  | 1M hits    | 10M hits   |
# +--------+------------+------------+------------+------------+------------+
# | 0      | 104        | 255        | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 1      | 18         | 49         | 255        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 10     | 10         | 18         | 142        | 255        | 255        |
# +--------+------------+------------+------------+------------+------------+
# | 100    | 8          | 11         | 49         | 143        | 255        |
# +--------+------------+------------+------------+------------+------------+

factor也是通过参数lfu-log-factor控制，默认是10。(更详细可以参考http://mysql.taobao.org/monthly/2018/09/08/)

另外还有个控制衰减因子的参数，lfu-decay-time，它默认是1。因为长时间不读取key的话，是需要进行衰减的，否则它一直停留在255，就不会被淘汰。

接下来介绍下一些关键的数据结构和方法。

evictionPoolEntry

存放待淘汰对象的池子，池子是全局对象evictionPoolEntry，它在evictionPoolAlloc()初始化。evictionPoolAlloc()被initServer()调用。

这里要注意的是cached字段，它是用来避免系统调用带来的开销。所以255以内的字符串对象，可以直接使用它来缓存。但是大于255的就只能申请内存了。而在淘汰池子里的对象时，很重要的一件事是把这些大于255的key占用内存空间释放掉。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#define EVPOOL_SIZE 16
struct evictionPoolEntry {
    unsigned long long idle;    /* Object idle time (inverse frequency for LFU) */
    sds key;                    /* Key name. */
  	// cached用途就是对长度小于255的key可以复用内存空间。否则每次都创建新的sds对象影响性能
    sds cached;                 /* Cached SDS object for key name. */
    int dbid;                   /* Key DB number. */
};

static struct evictionPoolEntry *EvictionPoolLRU;

void evictionPoolAlloc(void) {
    struct evictionPoolEntry *ep;
    int j;

    ep = zmalloc(sizeof(*ep)*EVPOOL_SIZE);
    for (j = 0; j < EVPOOL_SIZE; j++) {
        ep[j].idle = 0;
        ep[j].key = NULL;
        ep[j].cached = sdsnewlen(NULL,EVPOOL_CACHED_SDS_SIZE);
        ep[j].dbid = 0;
    }
    EvictionPoolLRU = ep;
}

LRU的更新函数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


unsigned int LRU_CLOCK(void) {
    unsigned int lruclock;
    if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {
        atomicGet(server.lruclock,lruclock);
    } else {
        lruclock = getLRUClock();
    }
    return lruclock;
}

val->lru = LRU_CLOCK();

读取对象LRU的空闲时间

1
2
3
4
5
6
7
8
9


unsigned long long estimateObjectIdleTime(robj *o) {
    unsigned long long lruclock = LRU_CLOCK();
    if (lruclock >= o->lru) {
        return (lruclock - o->lru) * LRU_CLOCK_RESOLUTION;
    } else {
        return (lruclock + (LRU_CLOCK_MAX - o->lru)) *
                    LRU_CLOCK_RESOLUTION;
    }
}

LFU的更新函数

1
2
3
4
5
6
7
8


void updateLFU(robj *val) {
    // 先根据之前的访问时间与衰减因子，将counter衰减一次
    unsigned long counter = LFUDecrAndReturn(val);
    // 然后根据这次的访问更新counter
    counter = LFULogIncr(counter);
    // 将访问时间与最新counter存起来
    val->lru = (LFUGetTimeInMinutes()<<8) | counter;
}

读取对象LFU的空闲时间

需要注意LFU的空闲时间是以次数来计算的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


idle = 255-LFUDecrAndReturn(o)

unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

更新LRU/LFU字段

每次读取key时，都会更新key对应的LRU/LFU字段

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);
        if (server.rdb_child_pid == -1 &&
            server.aof_child_pid == -1 &&
            !(flags & LOOKUP_NOTOUCH))
        {
            if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
                // 开启了LFU才更新LFU字段
                updateLFU(val);
            } else {
                // 否则更新LRU字段
                val->lru = LRU_CLOCK();
            }
        }
        return val;
    } else {
        return NULL;
    }
}

什么时候检查内存？

每次执行client发过来的命令时，都会做检查(server.c/processCommand())。核心方法是freeMemoryIfNeeded()这个方法，它被包在freeMemoryIfNeededAndSafe()里

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int processCommand(client *c) {
  // ...
  if (server.maxmemory && !server.lua_timedout) {
    int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR;
    // ...
  }
  // ...
}

int freeMemoryIfNeededAndSafe(void) {
    if (server.lua_timedout || server.loading) return C_OK;
    return freeMemoryIfNeeded();
}