Redis - LFU 알고리즘이란?

Redis는 4.0 버전부터 LFU 알고리즘이라는것을 추가 지원하기로 했다.

 

Redis의 LFU 알고리즘이란?

LFU (Least Frequently Used)란 뜻으로 자주 사용되는 캐시는 메모리상에 그대로 두고, 그렇지 않은 데이터들을 지워주는 알고리즘을 의미한다. 

 

Redis LFU는 Approximated LRU라는 페이지 교체 알고리즘과 비슷한 형태이며,  모리스 카운터라는 확률적 알고리즘을 이용해서 데이터들의 엑세스 빈도를 계산하고, 감쇠기간과 결합하여 일정 시간이 지나면 카운터를 감소시키도록 한다.

 

Redis는 총 24비트의 공간을 갖고 있다.

 

redis

이 24비트중 LRU time을 체크하는데 16비트를 사용하고 나머지 8비트는 LFU data의 카운터를 체크하는데 사용한다.

LFU의 경우 최대 8비트의 값만 사용가능하기 때문에 ' 0 ~ 255 ' 의 숫자를 사용가능하다.

 

( 내가 생각하기에는 카운터를 체크하는데 255의 숫자는 금방 채워지기 때문에 모리스 카운터라는 확률적 카운터를 이용해서 해당 카운터를 주기적으로 감소 시켜주는것 같다. )

 

LFULogIncr

위의 코드는 LFU의 카운터를 증가 Redis상의 소스 코드이다 .

• 0과 1 사이에 랜덤 값을 구합니다. //  double R = (double)rand()/RAND_MAX;

• 확률 P를 구합니다. // double P = 1.0/(baseval*server.lfu_log_factor+1); 

• R < P 이면 증가시킵니다. //  if (R < P) counter++;

 

 

 

LFU는 조정가능한 매개 변수가 있다.  

 

• lfu-log-factor 
• lfu-decay-time

이렇게 총 두가지가 있으며 redis.conf파일을 통해서 수정이 가능하다.