Redis Memory LFU(Least Frequently Used) 캐시

 Redis Memory LFU(Least Frequently Used) 캐시

 

·       Version : Redis 4.0

 

Redis 4.0 부터 제공되는 LFU 알고리즘 캐시는 자주 참조되는 데이터만 배치하고 그렇지 않은 데이터들은 메모리로부터 제거하여 자주 사용되는 데이터들이 메모리에 배치되도록하는  알고리즘이다. LRU 알고리즘은 최근에 액세스 했지만 실제로는 거의 요청하지 않는 항목에 대해서도 메모리에 보관하고 자주 요청되는 키에 대해서는 만료가 되기 때문에 의도하지 않은 성능이 나타날 수도 있다.

LFU는 Approximated LRU와 유사하다. 모리스 카운터라고 하는 확률적 카운터를 사용하여 개체의 액세스 빈도를 계산하고 감쇠 기간과 결합하여 시간이 지남에 따라 카운터가 감소한다. 알고리즘은 액세스 패턴의 변화를 확인하고 과거에 액세스가 있었지만 자주 액세스되지 않는 키는 삭제 후보로 선정한다. 이러한 방법은 LRU에서 발생하는것과 유사하게 샘플링된다. 그러나 LRU와 달리 LFU에는 특정 조정가능한 매개변수가 있다. 예를들어 더 이상 객체에 액세스하지 않게 되면 랭크를 얼마나 빨리 감소 시킬것인지 설정할 수 있다. Redis 4.0은 기본적으로 아래와 같이 구성된다.

·       100만건의 요청에 카운터를 포화시킨다.

·       카운터를 1분마다 감쇠한다.

 

카운터 범위 조정은 Redis.conf 파일에 아래와 같이 관련 파라메터를 수정한다.

·       lfu-log-factor 10 (기본값 10)

·       lfu-decay-time 1

lfu-decay-time의 변수값은 분(minute)로 사용되며 0으로 설정할 경우 항상 카운터를 스캔할 때마다 카운터를 감소시킨다.

lfu-log-factor의 범위는 0-255이며,  factor가 높을수록 최대 값에 도달하기 위해 더 많은 액세스가 필요하다. Hits 값은 사용자가 메모리로부터 데이터를 재참조한 값으로 높을 수록 좋다. 아래 표에서는 팩터가 10일때 1M 이상의 힛트가 발생하는 경우 가장 이상적인 것을 확인할 수 있다..

factor	100 hits	1000 hits	100k hits	1M hits	10M hits
0	104	255	255	255	255
1	18	49	255	255	255
10	10	18	142	255	255
100	8	11	49	143	255

 

 

[참고자료]

·       https://redis.io/topics/lru-cache

·       Approximate counting algorithm : https://en.wikipedia.org/wiki/Approximate_counting_algorithm

 

2019-06-06 / Sungwook Kang / http://sungwookkang.com

 

Redis, Redis Architecture, 레디스 메모리, Redis LFU, LFU 알고리즘, Least Frequently Used, 레디스 메모리 공간 확보, 레디스 메모리 제거