关于redis:Redis-对过期数据的处理

39次阅读

共计 3871 个字符,预计需要花费 10 分钟才能阅读完成。

Redis 对过期数据的解决

在 redis 中,对于曾经过期的数据,Redis 采纳两种策略来解决这些数据,别离是惰性删除和定期删除

惰性删除

惰性删除不会去被动删除数据,而是在拜访数据的时候,再查看以后键值是否过期,如果过期则执行删除并返回 null 给客户端,如果没有过期则返回失常信息给客户端。

它的长处是简略,不须要对过期的数据做额定的解决,只有在每次拜访的时候才会查看键值是否过期,毛病是删除过期键不及时,造成了肯定的空间节约。

源码

robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags) {
    robj *val;

    if (expireIfNeeded(db,key) == 1) {/* Key expired. If we are in the context of a master, expireIfNeeded()
         * returns 0 only when the key does not exist at all, so it's safe
         * to return NULL ASAP. */
        if (server.masterhost == NULL) {
            server.stat_keyspace_misses++;
            notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
            return NULL;
        }

        /* However if we are in the context of a slave, expireIfNeeded() will
         * not really try to expire the key, it only returns information
         * about the "logical" status of the key: key expiring is up to the
         * master in order to have a consistent view of master's data set.
         *
         * However, if the command caller is not the master, and as additional
         * safety measure, the command invoked is a read-only command, we can
         * safely return NULL here, and provide a more consistent behavior
         * to clients accessign expired values in a read-only fashion, that
         * will say the key as non existing.
         *
         * Notably this covers GETs when slaves are used to scale reads. */
        if (server.current_client &&
            server.current_client != server.master &&
            server.current_client->cmd &&
            server.current_client->cmd->flags & CMD_READONLY)
        {
            server.stat_keyspace_misses++;
            notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
            return NULL;
        }
    }
    val = lookupKey(db,key,flags);
    if (val == NULL) {
        server.stat_keyspace_misses++;
        notifyKeyspaceEvent(NOTIFY_KEY_MISS, "keymiss", key, db->id);
    }
    else
        server.stat_keyspace_hits++;
    return val;
}

定期删除

定期删除:Redis 会周期性的随机测试一批设置了过期工夫的 key 并进行解决。测试到的已过期的 key 将被删除。

具体的算法如下:

    • Redis 配置项 hz 定义了 serverCron 工作的执行周期,默认为 10,代表了每秒执行 10 次;
    • 每次过期 key 清理的工夫不超过 CPU 工夫的 25%, 比方 hz 默认为 10, 则一次清理工夫最大为 25ms;
    • 清理时顺次遍历所有的 db;
    • 从 db 中随机取 20 个 key, 判断是否过期,若过期,则逐出;
    • 若有 5 个以上 key 过期,则反复步骤 4, 否则遍历下一个 db;
    • 在清理过程中,若达到了 25%CPU 工夫,退出清理过程;

    尽管 redis 确实是一直的删除一些过期数据,然而很多没有设置过期工夫的数据也会越来越多,那么 redis 内存不够用的时候是怎么解决的呢?这里咱们就谈判到淘汰策略

    Redis 内存淘汰策略

    当 redis 的内存超过最大容许的内存之后,Redis 会触发内存淘汰策略,删除一些不罕用的数据,以保障 redis 服务器的失常运行

    在 redis 4.0 以前,redis 的内存淘汰策略有以下 6 种

    • noeviction:当内存应用超过配置的时候会返回谬误,不会驱赶任何键
    • allkeys-lru:退出键的时候,如果过限,首先通过 LRU 算法驱赶最久没有应用的键
    • volatile-lru:退出键的时候如果过限,首先从设置了过期工夫的键汇合中驱赶最久没有应用的键
    • allkeys-random:退出键的时候如果过限,从所有 key 随机删除
    • volatile-random:退出键的时候如果过限,从过期键的汇合中随机驱赶
    • volatile-ttl:从配置了过期工夫的键中驱赶马上就要过期的键

    在 redis 4.0 当前,又减少了以下两种

    • volatile-lfu:从所有配置了过期工夫的键中驱赶应用频率起码的键
    • allkeys-lfu:从所有键中驱赶应用频率起码的键

    内存淘汰策略能够通过配置文件来批改,redis.conf 对应的配置项是 maxmemory-policy 批改对应的值就行,默认是 noeviction

    LRU(the least recently used 最近起码应用)算法

    如果一个数据在最近没有被拜访到,那么在将来被拜访的可能性也很小,因而当空间满的时候,最久没有被拜访的数据最先被置换(淘汰)

    LRU 算法通常通过双向链表来实现,增加元素的时候,直接插入表头,拜访元素的时候,先判断元素是否在链表中存在,如果存在就把该元素挪动至表头,所以链表的元素排列程序就是元素最近被拜访的程序,当内存达到设置阈值时,LRU 队尾的元素因为被拜访的工夫线较远,会优先踢出

    然而在 redis 中,并没有严格履行 LRU 算法,之所以这样是因为 LRU 须要耗费大量的额定内存,须要对现有的数据结构进行较大的革新,近似 LRU 算法采纳在现有数据结构的根底上应用随机采样法来淘汰元素,能达到和 LRU 算法十分近似的成果。Redis 的 LRU 算法给每个 key 减少了一个额定的长度为 24bit 的小字段,记录最初一次被拜访的工夫戳。

    redis 通过 maxmemory-samples 5 配置,对 key 进行采样淘汰。同时在 Redis3.0 当前增加了淘汰池进一步晋升了淘汰准确度。

    然而 LRU 算法是存在肯定的问题

    例如,这示意随着工夫的推移,四个不同的键拜访。每个“〜”字符为一秒钟,而“|”最初一行是以后时刻。

    ~ A ~ A ~ A ~~ A A ~ A |

    B B B B B B B B B B B B〜|

    ~~ C ~~ C ~ C ~~~~ |

    ~ D ~~~ D ~ D ~~~~ D |

    在上图中,依照 LRU 机制删除的话删除的程序应该是 C ->A->B->D 其实这并不是咱们想要的,因为 B 被拜访的频率是最高的,而 D 被拜访的频率比拟低,所以咱们更想让 B 保留,把 D 删除,所以咱们接下来看另一种策略 LFU

    LFU(leastFrequently used 最不常常应用)

    如果一个数据在最近一段时间内很少被拜访到,那么能够认为在未来他被拜访到的概率也很小。所以,当空间满时,最小频率拜访的数据最先被淘汰

    Redis 应用 redisObject 中的 24bit lru 字段来存储 lfu 字段,这 24bit 被分为两局部:

    1: 高 16 位用来记录拜访工夫(单位为分钟)

    2: 低 8 位用来记录拜访频率,简称 counter

    16 bits      8 bits
    

    +—————-+——–+

    Last decr time | LOG_C |

    然而 counter 8bit 很容易就溢出了,技巧是用一个逻辑计数器,给予概率的对数计数器,而不是一个一般的递增计数器

    uint8_t LFULogIncr(uint8_t counter) {if (counter == 255) return 255;
        double r = (double)rand()/RAND_MAX;
        double baseval = counter - LFU_INIT_VAL;
        if (baseval < 0) baseval = 0;
        double p = 1.0/(baseval*server.lfu_log_factor+1);
        if (r < p) counter++;
        return counter;
    }

    对应的概率分布计算公式为

    1.0/((counter - LFU_INIT_VAL)*server.lfu_log_factor+1);

    其中 LFU_INIT_VAL 为 5,其实简略说就是,越大的数,递增的概率越低
    严格依照 LFU 算法,工夫越久的 key,counter 越有可能越大,被剔除的可能性就越小。counter 只增长不衰减就无奈辨别热点 key。为了解决这个问题,redis 提供了衰减因子 server.lfu_decay_time, 其单位为分钟,计算方法也很简略,如果一个 key 长时间没有拜访那么他的计数器 counter 就要缩小,缩小的值由衰减因子来管制

    关注我的技术公众号,每个工作日都有优质技术文章推送。
    微信扫一扫下方二维码即可关注:

    正文完
     0