Cache 替换算法之:2Q

作者: yuwh_507 | 来源:发表于2015-05-20 17:42 被阅读506次

Simplified 2Q

Simplified 2Q

如果访问的数据P在Am中命中,将他放回到Am的Rear中,如果在A1命中,则将其从A1中移除,放入到Am中。

如果在A1和Am中都没有命中,则优先使用两个队列的空闲空间,将其放入A1的Rear端;如果没有剩余空间,则检查A1的Threshold,超过的话从A1的Front移除就数据,若没有超过,则从Am的Front端移除数据,新数据放入A1的Rear

Full Version2Q

2Q

Simplified 2Q的Threshold参数至关重要,这个参数过大或过小都无法合理平衡A1和Am的负载,尤其是当程序的数据模型变化时,这个值需要随着变化,这使得Cache的空间很难被合理使用,因此有了Full version 2Q来解决这个问题。

Full vision 2Q将A1分解成A1-in和A1-out两个队列,其中Kin为A1-in的阈值,Kout为A1-out的阈值。在A1-in和A1-out中不再保存数据,而是存放数据指针,这样Am可以使用所有的Slot,在一定程度上解决了适配性的问题

LRU算法都是居于Link list来实现的,数据从Front取出放回到Rear的过程是一个链表的替换过程,操作不算复杂,但是替换过程伴随着多处链表遍历,这个时间是不可忽略的。

相关文章

  • Cache 替换算法之:2Q

    Simplified 2Q 如果访问的数据P在Am中命中,将他放回到Am的Rear中,如果在A1命中,则将其从A1...

  • Cache 替换算法之:基本算法

    Cache miss不仅意味着需要从主存获取数据,而且还需要将cache的某一个block替换出去。常用的算法包括...

  • Cache 替换算法之:LIRS

    Second Change 传统的FIFO和LRU算法都没有使用访问次数这个信息,使得对于空间局限性较弱的场景效率...

  • Cache 替换算法和写策略

    前言:来吧,继续补 Cache 的知识。 替换算法 还记得组相联吗?就是主存中的一块可以放在 Cache 中的一组...

  • 软考每天一练||网络工程师

    以下关于Cache的叙述中,正确的是( )。 A.在容量确定的情况下,替换算法的时间复杂度是影响Cache命中率的...

  • LRU Cache理解

    LRU Cache 1. 概念解析,LRU Cache算法 Lru Cache算法就是Least Recently...

  • ES缓存

    node query cache 一个节点的所有shard共享一个缓存区。利用LRU算法替换缓存内容。 query...

  • 缓存相关

    cache淘汰算法:LIRS 算法 缓存那些事 Redis缓存淘汰算法,LRU算法,LRU算法讲解

  • 重新组织函数 - Substitute Algorithm

    简述 Substitute Algorithm(替换算法)指你想把一个算法替换成另一个更清晰的算法,将函数本体替换...

  • LRUCache - C++

    LRUCache是一种常用的缓存替换算法,其原理是根据使用率淘汰数据,一般会实现为一个队列,如果一个cache命中...

网友评论

    本文标题:Cache 替换算法之:2Q

    本文链接:https://www.haomeiwen.com/subject/qtblqttx.html