LRFU (Least Recently/Frequently Used) 이란?

LRFU (Least Recently/Frequently Used)

Adaptive Cache Replacement Policy

캐시를 통해 데이터 처리 성능 향상의 꾀하는 경우에 캐시를 어떻게 유지하고 새로 교체해줄 것인 가에 대한 정책 중에 LRFU라는 게 있어서 찾아보는 중이다.
해당 기법을 본 건 LLAP Caching 부분을 읽다가 였다. (https://cwiki.apache.org/confluence/display/Hive/LLAP)

그 전에 알면 좋을 주요 교체 알고리즘으로 FIFO, LRU, LFU가 있다.
간단히 소개하면 아래와 같다.

FIFO (First In, First Out)
 - 가장 오래된 정보를 삭제한 자리에 새로운 정보를 저장하는 식이다.

LRU (Least Recently Used)
 - 가장 오래 사용되지 않은 정보를 교체한다.

LFU (Least Frequently Used)
 - 가장 빈도수가 적게 사용된 정보를 교체한다.

문제는 LRFU인데, 검색해보면 생각보다 나오는 내용이 없다.


먼저 wikipedia에서 Cache replacement policies를 찾아봤는데, 비슷한게 있었다.
그 내용을 살펴보면 아래와 같다.
https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_Frequent_Recently_Used_(LFRU)_[11]

LFRU (Least Frequent Recently Used)

LFU와 LRU의 장점을 합친 교체 정책으로써, 정보 중심 네트워크(Information-Centric Networking, ICN), 컨텐츠 전송 네트워크(CDN), 일반적인 형태의 분산 네트워크와 같은 캐시 어플리케이션에 적합하다. 

LFRU에서는 캐시가 2 부분으로 나눠지는데, privileged와 unprivileged 파티션으로 불린다. privileged 파티션에선 LRU를 적용하고, unprivileged 파티션에는 ALFU(거의 LFU?)를 적용한다는 것으로 예를 들면 다음과 같다. 

먼저, unprivileged에서 적은 횟수로 사용된 정보를 버리고, privileged 파티션에서 가장 오래된 정보가 unprivileged로 이동한다. 그리고 새로운 정보가 privileged의 빈자리로 들어온다.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

위와 같은 내용이었는데, 문제는 순서가 다르다. LRFU가 아니라 LFRU인데.

그래서 조금 더 찾아봤더니 96년도에 서울대에 쓴 논문이 검색된다. 

LRFU (Least Recently/Frequently Used) Replacement Policy: A Spectrum of Block Replacement Policies (1996)

내용을 요약해보면 아래와 같다. 이 논문에서 block을 하나의 저장 및 교체 단위로 본다.

LRFU (Least Recently/Frequently Used)

LFU는 작업량의 추세를 반영할 수 없다. 예를 들면, 예전에는 자주 쓰이다가 현재는 안 쓰이는 block과 최근에 들어서야 점점 더 많이 쓰이기 시작한 block이 있을 때, 전자를 교체 대상으로 삼을 것이다. 구현 관점에서 보면, 보통 Priority queue가 사용되므로 시간 복잡도는 O(log n)을 나타낸다.
반면 LRU는 가장 최근에 남아있는 데이터에 대한 빈도만을 통해 선택을 해야 한다. 결과적으로 제대로된 빈도수 확인이 안될 수 있다. 하지만 다른 정책에 비해 패턴에 의한 변화를 줄 수 있는 형태이며 매우 효율적으로 동작한다. 하나의 연결 리스트로 구현할 수 있으므로, 시간 복잡도는 상수 O(1)이다.

두 가지의 장점을 합쳐 과거의 모든 block의 빈도(frequency)와 최신성(recency)을 둘다 보고 교체 대상을 선정할 수 있도록 하는 것을 Least Recently/Frequently Used(LRFU)라고 부를 것이다. 가중치에 따라 해당 정책은 스펙트럼의 형태로 나타나며 시간 복잡도는 O(1)과 O(log n)의 사이가 될 것이다.
LRFU 정책은 CRF(Combined Recency and Frequency)라는 값을 통해 해당 블럭의 재사용성을 판단하며, 가장 작은 값의 block이 교체 대상이 된다.

자세한 CRF 계산 과정은 논문에서 확인할 수 있다.
그 중 인상적인 부분은 CRF를 계산하기 위한 공식에서 사용되는 F(x)의 parameter인 λ의 범위를 0과 1사이에서 선택하며, 그 값에 따라 LFU와 LRU의 스펙트럼 어딘가에 위치하게 된다는 점이었다.
F(x) = (1/2) ^(λx)

또한 상관관계가 있는 기간(correlated period)을 하나로 묶어 계산할 수 있는 형태에 대한 계산 변형도 가능하다. Database 시스템에서는 data access에 대한 frequency와 recency보다는 상위 작업인 transaction 레벨에서 미래 예측이 더 용이하다고 보고, Gc(x)을 정의해서 사용할 수 있도록 한다.

CRF의 계산을 매번 가지고 있는 전체 block에 대해 수행하는 이슈는, 자료구조 heap을 통해 피해갈 수 있도록 상세한 Implementation 가이드를 포함한다. 결과적으로 Implemetation은 가중치에 따라 연결 리스트와 heap(Priority queue)로 나뉘어 계산된다고 볼 수 있다.

작업량(workload)의 특성에 따라 parameter λ와 c를 변형하여 addaptive 정책을 구성할 수도 있다.