bytejava Java进阶手册

# 内存逐出淘汰机制

# 淘汰策略

为了避免内存不断增加超过系统上限，redis提供了maxmemory参数控制redis的最大内存量。 当超过内存量时，redis提供了几种处理策略

  • noeviction 不会继续处理写请求但是会继续响应读请求，能够保证不丢数据，但是新的写请求无法处理。这是默认策略
  • volatile-lru 会使用lru的策略尝试清除设置了过期时间的key。LRU优先清除最近没有使用的key。
  • volatile-lfu 会使用lfu的策略尝试清除设置了过期时间的key。LRU优先清除最近使用使用次数少的key。
  • volatile-ttl 淘汰设置了过期时间的key，优先淘汰ttl比较小的key。
  • volatile-random 随机淘汰设置了过期时间的key
  • allkeys-lru 淘汰全部的key，按照lru策略
  • allkeys-lfu 淘汰全部的key，按照lfu策略
  • allkeys-random 淘汰全部的key，随机选择

# redis LRU实现

LRU是Least Recently Used的缩写。 一种常见的LRU实现是通过双向链表加Map实现，在redis中并没有使用这种方式因为这样会占用比较多的额外内存。 redis使用的是一种近似LRU实现。 redis为每个key中保存了一个24bit的数据，记录的是最近访问的时间戳。 当发现内存超过maxmemory时，redis会随机采样出5个key，根据最近访问时间戳淘汰掉最旧的key。 如果淘汰后还是超过maxmemory，则继续采样淘汰直到内存小于maxmemory。

typedef struct redisObject {
    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;
1
2
3
4
5
6
7
8
9

lru字段更新时间

int objectSetLRUOrLFU(robj *val, long long lfu_freq, long long lru_idle,
                       long long lru_clock, int lru_multiplier) {
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        if (lfu_freq >= 0) {
            serverAssert(lfu_freq <= 255);
            val->lru = (LFUGetTimeInMinutes()<<8) | lfu_freq;
            return 1;
        }
    } else if (lru_idle >= 0) {
        /* Provided LRU idle time is in seconds. Scale
         * according to the LRU clock resolution this Redis
         * instance was compiled with (normally 1000 ms, so the
         * below statement will expand to lru_idle*1000/1000. */
        lru_idle = lru_idle*lru_multiplier/LRU_CLOCK_RESOLUTION;
        long lru_abs = lru_clock - lru_idle; /* Absolute access time. */
        /* If the LRU field underflows (since lru_clock is a wrapping clock),
         * we need to make it positive again. This be handled by the unwrapping
         * code in estimateObjectIdleTime. I.e. imagine a day when lru_clock
         * wrap arounds (happens once in some 6 months), and becomes a low
         * value, like 10, an lru_idle of 1000 should be near LRU_CLOCK_MAX. */
        if (lru_abs < 0)
            lru_abs += LRU_CLOCK_MAX;
        val->lru = lru_abs;
        return 1;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# LFU

redis4.0之后提供了LFU的策略，LFU是Least Frequently Used的缩写，也就是访问次数多的key有更大概率留在内存中。

# 更多参考

← hyperloglog →