看LRU，顺便看到自适应缓存替换算法(ARC)

看LRU，顺带就看了一下ARC，LRU知道，ARC是个什么鬼

ARC算法的描述

ARC算法是为了整个LFU和LRU两种替换算法的优点,实现他们之间的自适应的workload调整。算法把有效缓存队列划分为两个,T1和T2,其中T1是LRU队列用于保存最近使用的条目、T2是LFU队列用于保存最常使用的条目。他们各自都包含了一个名为ghost list的淘汰队列,分别命名为B1、B2,但tracking操作(即外部添加、查找操作)只针对T1、T2进行.ARC算法会根据缓存命中情况自动调整T1、T2的大小,以保证整个缓存既定长度的恒定。当新元素较多的时候,T1长度会增长T2长度会缩小,而当旧元素命中较多时候 T2长度会增长T1长度会缩小。

理论ARC算法核心结构:

T1, 用于保存最近的条目 T2, 用于保存最常用的条目,至少被引用两次 B1, 用于保存从T1淘汰的条目 B2, 用于保存从T2淘汰的条目

. . . [   B1  <-[     T1    <-!->      T2   ]->  B2   ] . .
      [ . . . . [ . . . . . . ! . .^. . . . ] . . . . ]
                [   fixed cache size (c)    ]
        [             L             ]

L可视为一个有效的缓存队列整体,其长度恒定不变。通过T1、T2长度的变化改变偏重P的大小。

首次添加  Add("A")
          | T1(LRU)  |      | B1(LRU)  |       | T2 (LFU)|     | B2 (LFU)|
      |----------|      |----------|       |---------|     |---------|
ele(A)->  |  ele(A)  |      |          |       |         |     |         |
      |----------|      |----------|       |---------|     |---------|

第二次添加或者访问 Add("A") / Get("A")
          | T1(LRU)  |      | B1(LRU)  |       | T2 (LFU)|     | B2 (LFU)|
      |----------|      |----------|       |---------|     |---------|
          |          |      |          |       |  ele(A) |     |         |
      |----------|      |----------|       |---------|     |---------|

对于已被T1或者T2淘汰的数据,再次添加 Add("A"),会直接进入T2
          | T1(LRU)  |      | B1(LRU)  |       | T2 (LFU)|     | B2 (LFU)|
      |----------|      |----------|       |---------|     |---------|
          |          |      |  ele(A)  |       |         |     |         |
      |----------|      |----------|       |---------|     |---------|

          | T1(LRU)  |      | B1(LRU)  |       | T2 (LFU)|     | B2 (LFU)|
      |----------|      |----------|       |---------|     |---------|
          |          |      |          |       |  ele(A) |     |         |
      |----------|      |----------|       |---------|     |---------|

理论ARC算法替换过程新元素: + 若空间不足,淘汰T2 + 添加新元素到T1

已存在元素: + 若在B1或B2存在,移动到T2 + 若空间不足,淘汰T1

查询命中 + 若T1查询命中,移动到T2

算法实现: 本包跟2Q算法实现类似,将T2用LRU队列来实现。其结构如下图所示。T1,T2,B1,B2依然按照理论ARC中的设计,区别只是T2 B2用的是LRU算法而不是LFU。

本包算法实现结构:

          | T1(LRU)  |      | B1(LRU)  |       | T2 (LRU)|     | B2 (LRU)|
          |----------|      |----------|       |---------|     |---------|
ele(A)->  |  ele(A)  |      |          |       |         |     |         |
      |----------|      |----------|       |---------|     |---------|

ARC算法结构对象:

type ARCCache struct {
    size int // 整体缓存的既定长度
    p    int // P T1和T2的侧重值

    t1 simplelru.LRUCache // T1 最近使用队列
    b1 simplelru.LRUCache // B1 T1淘汰队列

    t2 simplelru.LRUCache // T2 最常使用队列
    b2 simplelru.LRUCache // B2 T2淘汰队列

    lock sync.RWMutex  // 读写锁
}

bingoohuang / blog