내 인생의 환희

간만에 논문 한편 소개 합니다.

논문 소개에 앞서 cache 운용 방법이 그동안 어떻게 변했는지 알아보겠습니다.
cache의 victim을 선정하는 방법에 대해 오랜기간 연구가 있었습니다.

최초 LRU 가 등장한 이후 LRU를 기반으로 개량 알고리즘들이 등장합니다.

• Disk age
  • LRU (Least Recently Used)
  • LFU (Least Frequently Used)
  • 2Q (2 Queue)
  • LIRS (Low Inter-reference Recency Set)
  • ARC (Adaptive Replacement Cache)

2Q(2Queue)는 이름대로 LRU가 두개를 의미합니다. 첫번째 Q에서 hit이 발생하면 두번째 Q로 옮겨 갑니다. 첫번째 Q에서 victim을 선정합니다.

LIRS는 cache 안에서 hit되는 간격이 짧은 것과 긴것을 가려서 LIR, HIR으로 명명하고 victim은 HIR에서 가져갑니다.
위그림처럼 IO가 발생했다고 가정할 때 D는 B보다 최근에 access되었지만, B는 1번 건너 access된 반면 LIRS는 4번 건너 access 되었기에 D보다 B가 locality가 높다고 판단하는 것입니다.

ARC는 2Q를 개량한 것으로 2Q의 크기를 workload에 따라 가변한 것입니다. L1, L2 어디든지 Hit 이 발생하면 L2의 MRU로 갑니다. Miss가 발생하면 L1의 MRU로 갑니다. Victim은 L1이 C보다 작으면 L2에서 , 같으면 L1에 선정합니다

• Flash age
  • FAB (Flash-Aware Buffer)
  • BPLRU (Block Padding LRU)
  • CFLRU (Clean First LRU)
  • LRU-WSR, LIRS-WSR (Write Sequence Reordering)
  • CFDC (Clean-First Dirty-Clustered)
  • REF (Recently Evicted First)

Flash 시대가 도래 하면서 Flash 특성을 고려한 cache 관리 기법이 등장합니다.

FAB 은 victim 을 선정할 때 LRU로 하지 않고 같은 Block에 속한 entry가 가장 많은 entry들이 한꺼번에 flush됩니다. 이제 반해 BPLRU는 아예 Block 단위로 LRU를 관리합니다

.

CFLRU는 Clean우선 victim으로 선정하여 NAND 에 program을 최소화 하였고, WSR은 dirty에게 한번더 기회를 주어 program을 미루겠다는 의도였습니다. 둘다 clean을 list에서 먼저 내보겠다는 의미는 일맥상통합니다.

CFDC는 CFLRU 에 BPLRU를 더한 개념으로 Clean list와 dirty list를 나누되, clean은 그냥 LRU, dirty list는 block단위의 LRU를 하였습니다.

REF도 Block단위를 고려한것이지만, 다른점은 block단위로 LRU를 하는 것이 아니라, victim을 선정할 때 같은 block을 우선하는 정책입니다.

그동안 Cache 운용정책에서 가장중요한 것은 LRU입니다. 거기에 LFU의 개념이 부분적으로 더하는 작업이 이루어졌고, Flash 시대에 이르러서는 NAND FTL의 garbage collection overhead를 최소화하기 위해 random 과 sequential, clean과 dirty 를 구별하는 방향으로 발전해 갔습니다.

오늘 소개할 논문(ACAR)도 그 연장선상에 있습니다.

CFDC처럼 list를 clean과 dirty로 구별하였습니다. 거기에 NR (Non-Resident) 개념을 추가했습니다. 즉, List는 유지하지만, data는 가지고 있지 않은 리스트를 말합니다. NR은 이미 victim으로 선정되어 Flush된 과거의 정보를 사용하여 미래를 예측하겠다는 것입니다.

만약 DR에서 Cache miss가 발생한 entry가 DNR에 있었다면 CR을 줄이고, DR을 늘리는 것이 DR의 hit ratio을 높이는 방법이 될 것입니다. 반대로 CR에서 miss가 발생한 entry가 CNR에서 발견되었다면 CR을 늘려야 겠지요.

이것이 ACAR의 핵심입니다. Data의 I/O 패턴에 따라 CR 과 DR을 가변적으로 운용하므로써, hit ratio를 높이겠다는 의도 입니다.

CR의 LRU에서만 victim을 정하는 것은 CF-LRU의 흔적입니다.

ACAR+ 는 ACAR에 Single List를 추가하여 2Q처럼 운용합니다. 이것으로 다량의 sequential data가 CR로 들어가는 것을 거를 수 있습니다.

하지만, 실험 결과는 그리 대단하지 않습니다.

저자가 만든 인위적인 패턴 에서는 그럭저럭 기존의 알고리즘에 비해 좋은 성적을 거두지만,

TPC-C bench mark에서는 별 다를 것이 없는 성적을 보여줍니다. ACAR+가 좋은 성능을 보여주는 이유는 ACAR 가 좋아서라기 보다는 TPC-C 가 2Q 에 유리한 패턴이기 때문입니다.

ACAR 는 과거(CNR, DNR)로부터 미래(CR, DR)를 예측하려는 시도를 했다는 것, 기존의 알고리즘(CFDC, CF-LRU, 2Q)을 적극적으로 융합했다는 것으로 의미를 찾을 수 있겠습니다.