免费网站建设推广,长沙网站制作app开发公司,网站首页鲁大师,东莞推广宣传短视频redis通常使用缓存#xff0c;是使用一种固定最大内存的使用。当数据达到可使用的最大固定内存时#xff0c;我们需要通过移除老数据来获取空间。redis作为缓存是否有效的重要标志是如何寻找一种好的策略#xff1a;删除即将需要使用的数据是一种糟糕的策略#xff0c;而删…redis通常使用缓存是使用一种固定最大内存的使用。当数据达到可使用的最大固定内存时我们需要通过移除老数据来获取空间。redis作为缓存是否有效的重要标志是如何寻找一种好的策略删除即将需要使用的数据是一种糟糕的策略而删除那些很少再次请求的数据则是一种好的策略。 在其他的缓存组件还有个命中率仅仅表示读请求的比例。访问一个缓存中的keys通常不是分布式的。然而访问经常变化这意味着不经常访问相反有些keys一旦不流行可能会转向最经常访问的keys。 因此通常一个缓存系统应该尽可能保留那些未来最有可能被访问的keys。针对keys淘汰的策略是那些未来极少可能被访问的数据应该被移除。 但有一个问题redis和其他缓存系统不能够预测未来。
LRU算法
缓存系统不能预测未来原因是那些很少再次被访问的key也很有可能最近访问相当频繁。如果经常被访问的模式不会突然改变那么这是一种很有效的策略。然而“最近经常被访问”似乎更隐晦地标明一种 理念。这种算法被称为LRU算法。最近访问频繁的key相比访问少的key有更高的可能性。 举个例子这里有4个不同访问周期的key每一个“~”字符代表一秒结尾的“|”表示当前时刻。
~~~~~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|
A key每5秒请求一次B周期是2秒C、D都是10秒。 访问频率最高的是B因为它的空闲时间最短这意味着B是4个key中未来最有可能被访问的key。 同样的A和C目前的空闲时间是2s和6s也能很好地反映它们本身的周期。然而你可以看到不够严谨D的访问周期是10秒但它却是4个key中最近被访问的。 当然在一个很长的运行周期中LRU算法能工作得很好。通常有一个更高访问频率的key当然有一个更低的空闲周期。LRU算法淘汰最少被访问key那些有最大空闲周期的key。实现上也相当容易只需要额外跟踪最近被访问的key即可有时甚至都需要把所有我们想要淘汰的对象放到一个链表中当一个对象访问就移除链表头部元素当我们要淘汰元素是就直接淘汰链表尾部开始。
redis中的LRU:起因
最初redis不支持LRU算法。当内存有效性成为一个必须被解决的问题时后来才加上了。通过修改redis对象结构在每个key对象增加24bit的空间。没有额外的空间使用链表把所有对象放到一个链表中大指针因此需要实现得更加有效不能因为key淘汰算法而让整个服务改动太大。 24bits的对象已经足够去存储当前的unxi时间戳。这个表现被称为“LRU 时钟”key元数据经常被更新所以它是一个有效的算法。 然后有另一个更加复杂的问题需要解决如何选择访问间隔最长的key然后淘汰它。 redis内部采用一个庞大的hash table来保存添加另外一个数据结构存储时间间隔显然不是一个好的选择。然而我们希望能达到一个LRU本身是一个近似的通过LRU算法本身来实现。
redis原始的淘汰算法简单实现**当需要淘汰一个key时随机选择3个key淘汰其中间隔时间最长的key。**基本上我们随机选择key淘汰key效果很好。后来随机3个key改成一个配置项N随机key。但把默认值提高改成5个后效果大大提高。考虑到它的效果你根本不用修改他。
然而你可能会想这个算法如何有效执行你可以看到我们如何捣毁了很多有趣的数据。也许简单的N key我们会遇到很多好的决策但是当我们淘汰最好的下一个周期又开始抓。
验证规则第一条用肉眼观察你的算法
其中有一个观点已经应用到Redis 3.0正式版中了。在redis2.8中一个LRU缓存经常被使用在多个环境用户关于淘汰的没有抱怨太多但是很明显我可以提高它通过不仅仅是增加额外的空间还有额外的CPU时间。 然而为了提高某项功能你必须观察它。有多个不同的方式去观察LRU算法。你可以通过写工具观察例如模拟不同的工作负载、校验命中率和失误率。 程序非常简单增加一些指定的keys然后频繁地访问这些keys以至于每一个key都有一个下降的空闲时间。最终超过50%的keys被增加一半的老key需要被淘汰。 一个完美理想的LRU实现应该是没有最新加的key被淘汰而是淘汰最初的50%的老key。
规则二不要丢弃重要信息
借助最新的可视化工具我可以在尝试新的方法观察和测试几分钟。使用redis最明显有效的提高算法就是积累对立的垃圾信息在一个淘汰池中。 基本上当N keys算法被采用时通常会分配一个很大的线程pool默认为16key这个池按照空闲时间排序所以只有当有一个大于池中的一个或者池为空的时候最新的key只会进入到这个池中。 同时一个新的redis-cli模式去测量LRU算法也增加了(看这个-lru-test选项)。 还有另外一个方式去检验LRU算法的好坏通过一个幂等访问模式。这个工具通常校验用一个不同的测试新算法工作工作效果好于真实世界负载。它也同样使用流水线和每秒打印访问日志因此可以被使用不用为了基准不同的思想至少可以校验和观察明显的速度回归。
规则三、最少使用原则LFU算法 一切源于一个开放性问题但你有多个redis 3.2数据库时而淘汰算法只能在本机选择。因此假如你全部空闲小的key都是DB0号机器空闲时间长的key都是1号机器redis每台机器都会淘汰各自的key。一个更好的选择当然是先淘汰DB1最后再淘汰DB0。 当redis被当作缓存使用时很少有情况被分成不同的db上这不是一个好的处理方式。然而这也是我为什么我再一次修改淘汰代码的原因。最终我能够修改缓存池包括数据库id使用单缓存池为多个db代替多缓存池。这种实现很麻烦但是通过优化和修改代码最终它比普通实现要快到20%。 然而这时候我对这个redis缓存淘汰算法的好奇心又被点燃。我想要提升它。我花费了几天想要提高LRU算法实现或许可以使用更大的缓存池通过历史时间选择最合适被淘汰的key 经过一段时间通过优化我的工具我理解到LRU算法受限于数据库中的数据样本有时可能相反的场景效果非常好因此要想提高非常非常难。实际上能通过展示不同算法的图片上看这有点非常明显每个周期10个keys几乎和理论的LRU算法表现一致。 当原始算法很难提高时我开始测试新的算法。 如果我们倒回到博客开始我们说过LRU实际上有点严格。哪些key需要我们真正想要保留将来有最大可能被访问最频繁被访问而不是最近被访问的key。 淘汰最少被访问的key算法成为LFULeast Frequently Used将来要被淘汰腾出新空间给新key。 理论上LFU的思想相当简单只需要给每个key加一个访问计数器。每次访问就自增1所以也就很容易知道哪些key被访问更频繁。 当然LFU也会带起其他问题不单单是针对redis对于LFU实现 1、不能使用“移除顶部元素”的方式keys必须要根据访问计数器进行排序。每访问一次就得遍历所有key找出访问次数最少的key。 2、LFU不能仅仅是只增加每一访问的计数器。正如我们所讲的访问模式改变随时变化因此一个有高访问次数的key后面很可能没有人继续访问它因此我们的算法必须要适应超时的情况。 在redis中第一个问题很好解决我们可以在LRU的方式一样随机在缓存池中选举淘汰其中某项。第二个问题redis还是存在因此一般对于LFU的思想必须使用一些方式进行减少或者定期把访问计数器减半。
24位的LFU实现
LFU有它本身的实现在redis中我们使用自己的24bit来记录LRU。 为了实现LFU仅仅需要在每个对象额外新增24bit 1、一部分用于保存访问计数器 2、足够用于决定什么时候将计数器减半的信息
我的解决方法是把24bit分成两列
16bits8bitslast decr timeLOG_C
16位记录最后一次减半时间那样redis知道上一次减半时间另外8bit作为访问计数器。 你可能会想8位的计数器很快就会溢出是的相对于简单计数器我采用逻辑计数器。逻辑计数器的实现
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_factor1);if (r p) counter;return counter;}
基本上计数器的较大者更小的可能计数器会增加上面的代码计算p位于0~1之间但计数器增长时会越来越小位于0-1的随机数r只会但满足rp时计数器才会加一。 你可以配置计数器增长的速率如果使用默认配置会发生
100次访问后计数器101000次访问是是1810万次访问是142100万次访问后达到255并不在继续增长
下面让我们看看计数器如果进行衰减。16位的被储存为unix时间戳保留到分钟级别redis会随机扫描key填充到缓存池中如果最后一个下降的时间大于N分钟前可配置化如果计数器的值很大就减半或者对于值小的就直接简单减半。 这里又衍生出另外一个问题就是新进来的key是需要有机会被保留的。由于LFU新增是得分都是0非常容易被选举替换掉。在redis中开始默认值为5。这个初始值是根据增长数据和减半算法来估算的。模拟显示得分小于5的key是首选。
代码和性能
上面描述的算法已经提交到一个非稳定版的redis分支上。我最初的测试显示它在幂等模式下优于LRU算法测试情况是每个key使用用相同数量的内存然而真实世界的访问可能会有很大不同。时间和空间都可能改变得很不同所以我会很开心去学习观察现实世界中LFU的性能如何两种方式在redis实现中对性能的改变。 因此新增了一个OBJECT FREQ子命令用于报告给定key的访问计数器不仅仅能有效提观察一个计数器而且还能调试LFU实现中的bug。 注意运行中切换LRU和LFU刚开始会随机淘汰一些key随着24bit不能匹配上然而慢慢会适应。 还有几种改进实现的可能。Ben Manes发给我这篇感兴趣的文章描述了一种叫TinyLRU算法。链接
这篇文章包含一个非常厉害的观点相比于记录当前对象的访问频率让我们概率性地记录全部对象的访问频率看到了这种方式我们甚至可以拒绝新key同样我们相信这些key很可能得到很少的访问所以一点也不需要淘汰如果淘汰一个key意味着降低命中/未命中率。 我的感觉这种技术虽然很感兴趣GET/SET LFU缓存但不适用与redis性质的数据服务器用户期望keys被创建后至少存在几毫秒。拒绝key的创建似乎在redis上就是一种错误。 然而redis保留了LFU信息当一个key被覆盖时举个例子
SET oldkey some_new_value
24位的LFU计数器会从老的key复制到新对象中。
新的redis淘汰算法不稳定版本还有以下几个好消息 1、跨DB策略。在过去的redis只是基于本地的选举现在修复为所有策略不仅仅是LRU。 2、易变ttl策略。基于key预期淘汰存活时间如今就像其他策略中的使用缓存池。 3、在缓存池中重用了sds对象性能更好。
这篇博客比我预期要长但是我希望它反映出一个见解在创新和对于已经存在的事物实现上一种解决方案去解决一个特定问题一个基础工具。由开发人员以正确的方式使用它。许多redis的用户把redis作为一个缓存的解决方案因此提高淘汰策略这一块经常一次又一次被拿出来探讨。
