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、T、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  // 读写锁
}

资料

1. golang-lru 包学习 - ARC 算法
2. 常用缓存淘汰算法 LFU、LRU、ARC、FIFO、MRU