Redis近似LRU算法优化

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
云原生多模数据库 Lindorm,多引擎 多规格 0-4节点
云数据库 MongoDB,独享型 2核8GB
推荐场景:
构建全方位客户视图
简介: 本篇文章主要讲下在Redis 3.0中对于近似LRU算法的优化

公有云Redis服务:https://www.aliyun.com/product/kvstore?spm=5176.8142029.388261.37.59zzzj

背景

在前一篇文章《Redis作为LRU Cache的实现》中,我们看到了在Redis 2.8.19中LRU算法的具体实现,Redis使用了24 bit的lru时间戳来模拟一个近似的LRU算法,节省了实现一个严格LRU算法所需要的大量内存空间。

但是,上篇文章我们也挖了一个坑,说过现有的近似算法模拟效果还有待提高,今天这篇文章就是来填上这个坑,讲一下在Redis 3.0中对近似LRU算法的优化,既提升了算法的性能也提升了模拟效果。

Redis 3.0 LRU算法优化实现

Redis 3.0中主要做了如下优化:

  • LRU时钟的粒度从秒级提升为毫秒级
  • 使用新的API来获取LRU替换时的采样样本
  • 默认的LRU采样样本数从3提升为5
  • 使用eviction pool来选取需要淘汰的key

提升LRU时钟的粒度,主要是为了在测试LRU算法性能时,能够在更短的时间内获取结果,更新LRU时钟的方法也有所变化,如果LRU时钟的时间粒度高于serverCron刷新的时间粒度,那么就主动获取最新的时间,否则使用server缓存的时间,

/* Macro used to obtain the current LRU clock.
 * If the current resolution is lower than the frequency we refresh the
 * LRU clock (as it should be in production servers) we return the
 * precomputed value, otherwise we need to resort to a system call. */
#define LRU_CLOCK() ((1000/server.hz <= LRU_CLOCK_RESOLUTION) ? server.lruclock : getLRUClock())

unsigned int getLRUClock(void) {
    return (mstime()/LRU_CLOCK_RESOLUTION) & LRU_CLOCK_MAX;
}

在源码的utils/lru目录下有测试脚本,测试前需要把src/redis.h中的REDIS_LRU_CLOCK_RESOLUTION宏设置为1,即LRU时钟的分辨率为1ms,然后重新编译源码,执行方式如下,

ruby test-lru.rb > /tmp/lru.html

测试完成后会生成一个html页面,包含测试结果,以及一个图形化的插入淘汰流程

截图 2016-11-18 15时53分22秒.jpg

Redis 2.8中每次选取淘汰样本时,都是调用dictGetRandomKey来随机获取一个key,会根据maxmemory-samples配置的大小,多次调用。这个流程在Redis 3.0中被优化为一次调用获取指定数量的key,且不需要每次都调用随机函数,如下,

unsigned int dictGetSomeKeys(dict *d, dictEntry **des, unsigned int count) {
    unsigned long j; /* internal hash table id, 0 or 1. */
    unsigned long tables; /* 1 or 2 tables? */
    unsigned long stored = 0, maxsizemask;
    unsigned long maxsteps;

    if (dictSize(d) < count) count = dictSize(d);
    maxsteps = count*10;

    /* Try to do a rehashing work proportional to 'count'. */
    for (j = 0; j < count; j++) {
        if (dictIsRehashing(d))
            _dictRehashStep(d);
        else
            break;
    }

    tables = dictIsRehashing(d) ? 2 : 1;
    maxsizemask = d->ht[0].sizemask;
    if (tables > 1 && maxsizemask < d->ht[1].sizemask)
        maxsizemask = d->ht[1].sizemask;

    /* Pick a random point inside the larger table. */
    unsigned long i = random() & maxsizemask;
    unsigned long emptylen = 0; /* Continuous empty entries so far. */
    while(stored < count && maxsteps--) {
        for (j = 0; j < tables; j++) {
            if (tables == 2 && j == 0 && i < (unsigned long) d->rehashidx) {
                if (i >= d->ht[1].size) i = d->rehashidx;
                continue;
            }
            if (i >= d->ht[j].size) continue; /* Out of range for this table. */
            dictEntry *he = d->ht[j].table[i];

            /* Count contiguous empty buckets, and jump to other
             * locations if they reach 'count' (with a minimum of 5). */
            if (he == NULL) {
                emptylen++;
                if (emptylen >= 5 && emptylen > count) {
                    i = random() & maxsizemask;
                    emptylen = 0;
                }
            } else {
                emptylen = 0;
                while (he) {
                    /* Collect all the elements of the buckets found non
                     * empty while iterating. */
                    *des = he;
                    des++;
                    he = he->next;
                    stored++;
                    if (stored == count) return stored;
                }
            }
        }
        i = (i+1) & maxsizemask;
    }
    return stored;
}

dictGetSomeKeys会随机从db的某个起始位置开始,连续获取指定数量的key,需要注意的是,如果db对应的字典正在做rehash,可能需要从两个hashtable来获取key。如果需要根据某种分布来随机获取字典里面的key,这种采样方式可能是不合适的,但是如果只是为了随机获取一系列key来作为LRU算法的淘汰样本,这种方式是可行的。

采样性能的提升带来的好处就是,我们可以在不牺牲淘汰算法性能的情况下,提高采样的样本数,让Redis的近似LRU算法更接近于严格LRU算法,所以目前Redis把超过maxmemory后默认的采样样本数从3个提升到5个。

最后一个也是最重要的改进是,选取要淘汰key的流程。之前是每次随机选取maxmemory-samples个key,然后比较它们的idle时间,idle时间最久的key会被淘汰掉。在Redis 3.0中增加了一个eviction pool的结构,eviction pool是一个数组,保存了之前随机选取的key及它们的idle时间,数组里面的key按idle时间升序排序,当内存满了需要淘汰数据时,会调用dictGetSomeKeys选取指定的数目的key,然后更新到eviction pool里面,如果新选取的key的idle时间比eviction pool里面idle时间最小的key还要小,那么就不会把它插入到eviction pool里面,这个思路和LIRS替换算法利用的每个块的历史信息思想有些类似,

eviction pool更新逻辑代码如下,

#define EVICTION_SAMPLES_ARRAY_SIZE 16
void evictionPoolPopulate(dict *sampledict, dict *keydict, struct evictionPoolEntry *pool) {
    int j, k, count;
    dictEntry *_samples[EVICTION_SAMPLES_ARRAY_SIZE];
    dictEntry **samples;

    /* Try to use a static buffer: this function is a big hit...
     * Note: it was actually measured that this helps. */
    if (server.maxmemory_samples <= EVICTION_SAMPLES_ARRAY_SIZE) {
        samples = _samples;
    } else {
        samples = zmalloc(sizeof(samples[0])*server.maxmemory_samples);
    }

    count = dictGetSomeKeys(sampledict,samples,server.maxmemory_samples);
    for (j = 0; j < count; j++) {
        unsigned long long idle;
        sds key;
        robj *o;
        dictEntry *de;

        de = samples[j];
        key = dictGetKey(de);
        /* If the dictionary we are sampling from is not the main
         * dictionary (but the expires one) we need to lookup the key
         * again in the key dictionary to obtain the value object. */
        if (sampledict != keydict) de = dictFind(keydict, key);
        o = dictGetVal(de);
        idle = estimateObjectIdleTime(o);

        /* Insert the element inside the pool.
         * First, find the first empty bucket or the first populated
         * bucket that has an idle time smaller than our idle time. */
        k = 0;
        while (k < MAXMEMORY_EVICTION_POOL_SIZE &&
               pool[k].key &&
               pool[k].idle < idle) k++;
        if (k == 0 && pool[MAXMEMORY_EVICTION_POOL_SIZE-1].key != NULL) {
            /* Can't insert if the element is < the worst element we have
             * and there are no empty buckets. */
            continue;
        } else if (k < MAXMEMORY_EVICTION_POOL_SIZE && pool[k].key == NULL) {
            /* Inserting into empty position. No setup needed before insert. */
        } else {
            /* Inserting in the middle. Now k points to the first element
             * greater than the element to insert.  */
            if (pool[MAXMEMORY_EVICTION_POOL_SIZE-1].key == NULL) {
                /* Free space on the right? Insert at k shifting
                 * all the elements from k to end to the right. */
                memmove(pool+k+1,pool+k,
                    sizeof(pool[0])*(MAXMEMORY_EVICTION_POOL_SIZE-k-1));
            } else {
                /* No free space on right? Insert at k-1 */
                k--;
                /* Shift all elements on the left of k (included) to the
                 * left, so we discard the element with smaller idle time. */
                sdsfree(pool[0].key);
                memmove(pool,pool+1,sizeof(pool[0])*k);
            }
        }
        pool[k].key = sdsdup(key);
        pool[k].idle = idle;
    }
    if (samples != _samples) zfree(samples);
}

当选取的淘汰策略和LRU相关时(allkeys-lru或volatile-lru),freeMemoryIfNeeded会调用evictionPoolPopulate来更新eviction pool,然后淘汰掉eviction pool里面的最后一个元素所对应的key,这样的选取淘汰key的方式的好处是:假设说新随机选取的key的访问时间可能比历史随机选取的key的访问时间还要新,但是在Redis 2.8中,新选取的key会被淘汰掉,这和LRU算法利用的访问局部性原理是相违背的,在Redis 3.0中,这种情况被避免了。

此外,如果某个历史选取的key的idle时间相对来说比较久,但是本次淘汰并没有被选中,因为出现了idle时间更久的key,那么在使用eviction pool的情况下,这种idle时间比较久的key淘汰概率增大了,因为它在eviction pool里面被保存下来,参与下轮淘汰,这个思路和访问局部性原理是契合的。

Redis 2.8相比,改进的效果我们可以引用一下上篇文章《Redis作为LRU Cache的实现》中第一张图的下半部分,

截图 2016-11-18 17时26分07秒.jpg

我们可以看到在前面1/2需要淘汰的key里面(浅灰色的点),Redis 3.0残留下来的key明显比Redis 2.8少了很多,而且后面新插入的1/2的key里面(绿色的点),Redis 3.0没有一个淘汰的key。

总结

Redis 3.0中对于LRU替换算法的优化,在只维护一个eviction pool带来的少量开销情况下,对算法效率的提升是比较明显的,效率的提升带来的是访问命中率的提升。同时,在目前3.4的unstable版本中我们也可以看见Redis计划实现LFU算法以支持更丰富的业务场景,阿里云Redis服务团队也会持续跟进。此外,对于LIRS这种基于LRU的改进算法,在不影响性能的前提下,我们也会研究在内核上做支持。

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
目录
相关文章
|
12天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
13天前
|
人工智能 算法 大数据
Linux内核中的调度算法演变:从O(1)到CFS的优化之旅###
本文深入探讨了Linux操作系统内核中进程调度算法的发展历程,聚焦于O(1)调度器向完全公平调度器(CFS)的转变。不同于传统摘要对研究背景、方法、结果和结论的概述,本文创新性地采用“技术演进时间线”的形式,简明扼要地勾勒出这一转变背后的关键技术里程碑,旨在为读者提供一个清晰的历史脉络,引领其深入了解Linux调度机制的革新之路。 ###
|
23天前
|
NoSQL 关系型数据库 MySQL
MySQL与Redis协同作战:百万级数据统计优化实践
【10月更文挑战第21天】 在处理大规模数据集时,传统的单体数据库解决方案往往力不从心。MySQL和Redis的组合提供了一种高效的解决方案,通过将数据库操作与高速缓存相结合,可以显著提升数据处理的性能。本文将分享一次实际的优化案例,探讨如何利用MySQL和Redis共同实现百万级数据统计的优化。
61 9
|
23天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。
|
23天前
|
NoSQL 关系型数据库 MySQL
MySQL与Redis协同作战:优化百万数据查询的实战经验
【10月更文挑战第13天】 在处理大规模数据集时,传统的关系型数据库如MySQL可能会遇到性能瓶颈。为了提升数据处理的效率,我们可以结合使用MySQL和Redis,利用两者的优势来优化数据查询。本文将分享一次实战经验,探讨如何通过MySQL与Redis的协同工作来优化百万级数据统计。
53 5
|
22天前
|
存储 缓存 算法
优化轮询算法以提高资源分配的效率
【10月更文挑战第13天】通过以上这些优化措施,可以在一定程度上提高轮询算法的资源分配效率,使其更好地适应不同的应用场景和需求。但需要注意的是,优化策略的选择和实施需要根据具体情况进行详细的分析和评估,以确保优化效果的最大化。
|
23天前
|
并行计算 算法 IDE
【灵码助力Cuda算法分析】分析共享内存的矩阵乘法优化
本文介绍了如何利用通义灵码在Visual Studio 2022中对基于CUDA的共享内存矩阵乘法优化代码进行深入分析。文章从整体程序结构入手,逐步深入到线程调度、矩阵分块、循环展开等关键细节,最后通过带入具体值的方式进一步解析复杂循环逻辑,展示了通义灵码在辅助理解和优化CUDA编程中的强大功能。
|
23天前
|
存储 缓存 算法
前端算法:优化与实战技巧的深度探索
【10月更文挑战第21天】前端算法:优化与实战技巧的深度探索
20 1
|
24天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于贝叶斯优化CNN-LSTM网络的数据分类识别算法matlab仿真
本项目展示了基于贝叶斯优化(BO)的CNN-LSTM网络在数据分类中的应用。通过MATLAB 2022a实现,优化前后效果对比明显。核心代码附带中文注释和操作视频,涵盖BO、CNN、LSTM理论,特别是BO优化CNN-LSTM网络的batchsize和学习率,显著提升模型性能。
|
1月前
|
存储 缓存 算法
如何通过优化算法和代码结构来提升易语言程序的执行效率?
如何通过优化算法和代码结构来提升易语言程序的执行效率?

相关产品

  • 云数据库 Tair(兼容 Redis)