ARC: A Self-Tuning, Low Overhead Replacement Cache

사담

학기 중에 논문을 쓰고 수업을 듣느라 블로그 관리를 못했는데 운영체제 수업에서 논문을 많이 읽어서 아카이브용으로 블로그에 좋았던 논문들을 정리하려고 한다.
ARC는 처음에는 수식이 많아서 읽기가 꺼려졌는데 읽어보니 오히려 설명을 잘해서 진짜 잘 쓴 논문이구나 싶던 논문이다. 아이디어 자체는 기존의 $FRC_p$를 개선시킨 것에 지나지 않는데 상당히 유명한 논문인 것을 보면 대학원생 입장에서는 목표로 삼을만한 이상적인 논문이다.

Intro

메모리 분야에서 cache는 최적화를 하기에 가장 제일 먼저 떠올릴 수 있는 아이디어다. 당연히 전체 메모리가 빠르고 크면 좋겠지만, 비용의 문제 때문에 일반적으로 cache는 main memory보다 훨씬 작은 크기를 가진다. 따라서 cache가 꽉 차면 기존의 page 중 하나를 page out (evict)해야 하는데, 이 cache replacement policy에 따라 cache의 성능이 크게 영향을 받기 때문에 잘 정하는 것이 중요하다. 일반적으로는 LRU를 쓰지만 여러 연구들이 더 나은 cache replacement policy를 만들었고, 이 논문 역시 overhead를 낮추면서 hit rate를 최대화한다는 것이 주요 목표다.

Contribution

page size가 동일할 때 (superpage가 없을 때) demand paging 시나리오에서 새로운 cache replacement policy인 ARC(Adaptive Replacement Cache)를 제안한다.
ARC는 기존의 policy들에 비해 여러 장점을 가지는데

1. recency와 frequency를 모두 고려
   • correlated reference도 고려
2. online algorithm이다.
   • workload, cache size에 따른 parameter tuning이 필요없다.
   • 실행 도중에 worload pattern이 변하더라도 self-tuning한다.
3. computational overhead, space overhead가 작다.
   • computational overhead : O(1) (LRU와 동일)
   • space overhead : LRU의 2배
4. scan에 강하다.
   • scan은 one-time-only sequential read request를 의미한다.

Backgrounds

기존의 Page Replacement Policy들은 아래와 같다.

MIN

Belady가 제안. 가장 큰 forward distance의 page를 교체. online policy에 대한 상한선 제공

LRU (Least Recent Used)

• 가장 오래된 page를 교체
• workload가 LRU SDD(stack depth distribution)인 경우 optimal
• SDD는 recency를 고려하지만 frequency는 고려하지 않는다. 따라서 불균일한 page reference에 대해서는 성능이 좋지 않다.

LFU (Least Frequency Used)

• frequency를 고려하는 IRM (Independent Reference Model) 모델에서 optimal
• $O(log\ n)$ 시간 복잡도
• recent history를 아예 고려하지 않아서 correlated reference page (옛날에 빈도가 높게 접근했으나 최근에는 access하지 않는 page)가 계속 남아있는 문제가 있다.

LRU-2

• 2번째 reference가 가장 오래된 page를 교체. LFU에 대해 적응성 개선
• $O(log\ n)$ 시간 복잡도
• CIP (Correlated Information Period) : 한번만 본 page를 어느 시간만큼 저장할 지 결정. cache size c에 따라 가장 높은 hit rate를 보이는 CIP/c가 다르다.

2Q

• O(1) 복잡도로 LRU-2 근사
• $A_m$ : hot page, $A_1$ : cold page, correlated page
• $A_1$는 $K_{in}$개 만큼의 cache와 $K_{out}$개의 ghost cache를 저장한다.
• hot page가 분리되어있어 scan-resistant하다.
• cache size $c$에 따라 $K_{in}$, $K_{out}$ tuning해야 한다.
  

LIRS (Low Inter-reference Recency Set)

• IRR : stack distance와 유사한 개념. 이전 reference부터 현재 reference까지 다른 unique한 page가 몇 개 access되었는지를 의미한다.
• IRR이 크면 교체 후보가 된다.
  • $L_{lirs}$ : 최근 $R_{max}$ 안에 두 번 이상 본 page
  • $L_{hirs}$ : 최근 $R_{max}$ 안에 한번만 본 page
• $L_{hirs}$, $R_{max}$를 tuning해야 함.
• stack pruning도 필요하다고 한다.

FBR (Frequency-Based Replacement)

• LRU list를 new, middle, old로 나눈다.
• cache hit 시 new 안에 있는 MRU로 이동
  • middle, old에 있었던 경우 count가 증가
  • new section에 있으면 hit여도 count 증가 x (corrlated frequency에 의한 cache pollution 방지)
• count의 rescale이 필요하다. 평균 count가 $A_{max}$ 이상이 되면 모든 count를 반으로 줄인다.
• new, old 길이, $A_{max}$ 등을 tuning해야 한다.
  

LRFU (Least Recency/Frequency Used)

• 처음에는 $C(x) = 0$이다가 위 식대로 update하면서 제일 작은 $C(x)$를 가진 page를 교체
• λ가 0에 가까워지면 frequency 고려하는 비중이 커져서 LFU, 1에 가까워지면 recency 고려하는 비중이 커져서 LRU가 된다.
• λ에 따라 성능이 많이 바뀜 (tuning이 필요하다)
• ALRFU (Adaptive LRFU) : λ를 동적으로 조정하도록 수정한 알고리즘. 하지만 추가적인 tunable parameter가 존재하며, $O(log\ n)$ 복잡도여서 λ가 작으면 LRU보다 50배까지도 느리다고 한다.

MQ

• LRU queue m개 ($Q_0, \dots, Q_{m-1}$)를 사용
  $Q_i$ : 최근에 $2^i$ 이상 $2^{i+1} - 1$ 이하 access한 page
• hit 시 page frequency가 증가하고 각 queue의 MRU로 이동, expire time은 currentTime + lifeTime으로 설정됨.
• expire되면 다음 queue로 보내며 Q_out에서 교체
• peak temporal distance의 큰 변화가 있을 때에 동적으로 adapt함. (ARC는 tick마다 계속 적응한다.)
• n개 queue가 있어서 LRU, ARC, 2Q보다 space overhead는 크다.

c.f. Ghost Cache (Shadow Cache)

underlying cache를 지원하는 것보다 더 큰 크기의 cache directory를 사용하는 경우 이 directory를 ghost cache라고 한다. 최근에 evict된 cache page의 metadata를 저장할 때 사용한다. 일반적으로 DRAM에 저장되며 block address, pointer 정도를 저장한다.
2Q, MQ, LRU-2, ALRFU, LIRS 등에서 ghost cache를 사용한다.

[요약]

A CLASS OF REPLACEMENT POLICIES

replacement policy와 관련해서 하도 많은 policy가 나와서인지 아예 policy들의 class를 정의해놓았다. ARC는 $DBL(2c)$를 확장한 $\Pi(c)$에 속하는 $FRC_p(c)$에서 p를 동적으로 변환하는 policy이다.

• $c$ : page 수 (cache 크기)
• $\pi, \pi(c)$ : replacement policy를 의미
• $DBL(2c)$ : page 수의 2배를 관리하고 기억하는 정책
• $\Pi(c)$ : 제안하는 class

$[DBL(2c)]$

• 두 개의 가변 크기 list $L_1$, $L_2$를 유지
• $L_1$ : 한 번만 본 page (evict된 후 처음이거나 아예 처음)
• $L_2$ : 2번 이상 본 page

두 개 합이 2c보다 많아지거나 $L_1$이 c개보다 많아지면 교체하는데, $L_1$에 $c$개의 page가 있는 경우 $L_1$에서 replace하고, 아닌 경우 $L_2$에서 하나 빼고 $L_1$의 MRU에 새로 넣는다.

• $0 \le | L_1 | + | L_2 | \le 2c,0 \le | L_1 | \le c, 0 \le | L_2 | \le 2c$

$[\pi(c) ∈ \Pi(c)]$

DBL에서 관리하는 $2c$의 cache를 가지지만, physically하게는 $c$개의 page만을 가진다. (나머지 $c$개는 ghost cache다.) $2c$개를 관리하는 이유는 더 작으면 1, 2, ..., c에 대해 loop reference할 때 hit ratio가 0이라서 그렇다고 한다.

$\pi(c)$는 아래의 특성들을 가진다.

1. $L_1 = T_1^{\pi} \cup B_1^{\pi}, L_2 = T_2^{\pi} \cup B_2^{\pi}$
2. $| L_1 \cup L_2 | < c$ 인 경우 $B_1^{\pi}$, $B_2^{\pi}$는 비어있음.
3. $| L_1 \cup L_2 | \ge c$ 인 경우 $| T_1^{\pi} \cup T_2^{\pi} | = c$
4. $T_1^{\pi}$나 $B_1^{\pi}$이 비어있지 않으면, $T_1^{\pi}$의 LRU가 $B_1^{\pi}$의 MRU보다 더 최근에 access했다. (2도 동일)
5. $T_1^{\pi} \cup T_2^{\pi}$ 에는 policy $\pi(c)$로 남은 page들만 남아있다.

• $T$ (physical cache) : policy에서 남은 것 중 c개를 가지고 있음
• $B$ (ghost cache) : 여기서 miss난 경우에는 이전 access를 기억함.

space overhead는 LRU의 2배다. 4번 특성은 어떤 page가 $L_1$에 caching되어있다면, 그 page보다 recent한 page들은 모두 caching되어있다는 것을 내포한다. 또한 cache가 꽉 찼다는 것은 $| T_1^{\pi} \cup T_2^{\pi} | = c$ 라는 의미이므로 $T_1^{\pi}$나 $T_2^{\pi}$ 둘 중에서 뭘 replace할지만 policy에서 정하면 된다.

Adaptive Replacement Cache

Fixed Replacement Cache

$FRC_p(c)$ : $\Pi(c)$에 속함. p는 $0 \le p \le c$의 parameter

$T_{1, p} \equiv T_1^{FRC_p(c)}$, $T_{2, p} \equiv T_2^{FRC_p(c)}$, $B_{1, p} \equiv B_1^{FRC_p(c)}$, $B_{2, p} \equiv B_2^{FRC_p(c)}$ 라 할 때 $T_{1, p}$ 에 $p$개의 page, $T_{2, p}$ 에 $c-p$개의 page를 최대한 유지하려고 함

Replacement Policy : Replace(x_t, p)

• $|T_{1, p}| > p$ 인 경우 $T_{1, p}$ 의 LRU를 replace
• $|T_{1, p}| < p$ 인 경우 $T_{2, p}$ 의 LRU를 replace
• $|T_{1, p}| = p$ 인 경우 L_1에서 miss난 경우 L_1에서 replace, L_2에서 miss난 경우 L_2에서 replace
  

ARC

[adaptation parameter]

• $p \in [0,c]$
• $FRC_p$와 replacement는 정확히 동일하게 동작하지만, FRC와 다르게 p가 계속 변함.
• p의 직관적인 의미는 $T_1$에 저장할 target size
• p가 0에 가까워지면 $L_2$에 favor를 주겠다는 것이고, c에 가까워지면 $L_1$에 favor를 줌.

편의를 위해 $T_{1} \equiv T_1^{ARC}$, $T_{2} \equiv T_2^{ARC}$, $B_{1} \equiv B_1^{ARC}$, $B_{2} \equiv B_2^{ARC}$라고 가정한다.

[알고리즘]

input stream $x_1, \dots, x_t, \dots$ 에 대해

1. cache hit ($x_t \in T_1 \cup T_2$)
   $T_2$의 MRU로 옮김

2. cache miss in B_1 ($x_t \in B_1$)
   p를 $\delta_1$ 만큼 증가 → replace → $x_t$를 $T_2$의 MRU로 옮김

3. cache miss in B_2 ($x_t \in B_2$)
   p를 $\delta_2$ 만큼 감소 → replace → $x_t$를 $T_2$의 MRU로 옮김

4. cache miss not in L ($x_t \notin L_1 \cup L_2$)

   1. $|L_1| = c$
      1. $|T_1| < c$ : $B_1$의 LRU page를 evict → replace
      2. $|T_1| = c$ : $B_1$이 비어있으므로 $T_1$의 LRU를 지움
   2. $|L_1| < c$
      1. $| L_1 | + | L_2 | \ge c$ : 꽉 찼으면 $B_2$에서 LRU page를 evict → replace
      2. $| L_1 | + | L_2 | < c$ : $T$도 다 안 찼으므로 그냥 넣어도 상관없음

   이후 $x_t$를 $T_1$의 MRU로 옮김

(p가 동적으로 바뀌므로 순간적으로는 T가 p보다 훨씬 커질 수도 있음)

[Learning]

• intuition : B_1에서 miss가 나면 T_1의 size를 늘리고 (p 증가), B_2에서 miss가 나면 T_2의 size를 늘린다 (p 감소).
• idea : 더 좋은 성능을 보이는 쪽의 list에 invest함
• learning rate $\delta_1$, $\delta_2$ : p를 한번에 얼마나 변경할 것인지를 결정함.

1. $B_1$에서 miss인 경우
   $\delta_1 = \begin{cases} 1, {if\ |B_1| \ge |B_2|}\\ |B_2| / |B_1|, \text{o.w.} \end{cases}$
2. $B_2$에서 miss인 경우
   $\delta_2 = \begin{cases} 1, {if\ |B_2| \ge |B_1|}\\ |B_1| / |B_2|, \text{o.w.} \end{cases}$

(B_1에서 miss가 났다는 건 B_1 크기가 1 이상이라는 거고 소수만큼을 할 순 없으니 자른 것으로 보인다.)

ARC의 장점

[Self-Tunable]
ARC는 쉬지 않고 적응하고 learning한다. 따라서 stable한 IRM에서 transient SDD로 바뀌더라도 잘 적응할 수 있다.

[Scan-Resistant]

$L_1$, $L_2$에 없던 큰 page가 access되는 경우 $L_1$의 MRU에만 계속 들어가고 중요한 page들인 $L_2$에 영향을 주지 않는다.
또 scan의 경우 $B_1$에서 다시 access되는 ($B_1$ miss) 경우가 거의 없으므로 $T_2$의 크기가 계속 늘어난다. 따라서 scan에 점점 더 강해진다.

Evaluation

기본적으로 가장 좋은 parameter로 tuning한 offline 알고리즘들보다도 성능이 대체적으로 좋고, online 알고리즘보다도 좋다고 한다.

또한 $FRC_p$에 대해 workload 별로 가장 좋은 성능을 보이는 $p$를 고정해놓고 ARC와 비교한 결과에서의 특이점은 아래와 같다고 한다.

• $P_4$ : workload pattern이 많이 변하는데 $FRC_p$의 경우에는 고정된 p를 가지므로 적응하지 못해서 성능이 더 안 좋다.
• $P_8$ : workload pattern이 거의 일정한데 이 경우에는 ARC의 적응 알고리즘 등으로 인해 ARC가 약간 cost가 높다.

Reference

• Megiddo, N., & Modha, D. S. (2003, March). ARC: A Self-Tuning, Low Overhead Replacement Cache. In Fast (Vol. 3, No. 2003, pp. 115-130).