Redis - 키 제거 정책 2

본 글은 Redis - 키 제거 정책 1 글에서 이어집니다.

https://redis.io/docs/manual/eviction/

Key eviction

 

1.  대략적인 LRU 알고리즘

Redis LRU 알고리즘은 정확한 구현이 아닙니다. 이는 레디스가 제거 대상(과거에 가장 멀리 접근했던 접근권을 최적의 대상)으로 선정할 수 없다는 것을 의미한다. 대신 적은 수의 키를 샘플링하고 샘플링된 키 중 가장 오래된 키를 제거함으로써 LRU 알고리즘의 근사치를 실행하려고 시도합니다.

 

그러나 레디스 3.0 이후 알고리즘이 개선되어 제거를 위한 좋은 후보를 얻을 수 있게 되었습니다. 이를 통해 알고리즘의 성능이 향상되어 실제 LRU 알고리즘의 동작을 보다 가깝게 추정할 수 있게 되었습니다.

Redis LRU 알고리즘에서는 제거를 확인할 샘플 수를 변경하여 알고리즘의 정밀도를 조정할 수 있습니다.

maxmemory-samples 5

그렇다면 samples 수를 늘리면 실제 LRU 알고리즘 처럼 유사해지지 않을까? → 응답속도가 느려짐

Redis가 진정한 LRU 구현을 사용하지 않는 이유는 더 많은 메모리 비용이 들기 때문입니다. 그러나 근사값은 Redis를 사용하는 애플리케이션과 거의 동일합니다.

이론상 LRU, 3.0(10 samples), 2.8(5 samples), 3.0(5 samples)

그래프에서 세 가지 종류의 점을 볼 수 있고, 세 가지 뚜렷한 띠를 형성하고 있습니다.

• 밝은 회색 밴드는 제거된 물체입니다.
• 회색 밴드는 제거되지 않은 개체입니다.
• 녹색 밴드는 추가된 개체입니다.

보시다시피 Redis 3.0은 Redis 2.8에 비해 5개의 샘플로 더 잘 작동함

Redis 3.0에서 10의 샘플 크기를 사용하면 근사치는 Redis 3.0의 이론적 성능에 매우 가깝다.

LRU는 미래에 주어진 키에 액세스할 가능성을 예측하는 모델일 뿐입니다.

또한 데이터 액세스 패턴이 멱함수 법칙과 매우 유사할 경우 대부분의 액세스는 LRU 근사 알고리즘이 잘 처리할 수 있는 키 집합에 있습니다.

시뮬레이션에서 멱함수 법칙 액세스 패턴을 사용하면 실제 LRU와 레디스 근사치의 차이가 최소이거나 존재하지 않는다는 것을 발견했다.

CONFIG SET max memory-samples <count> 

명령을 사용하여 샘플 크기에 대한 다른 값을 사용하여 실험 할 수 있습니다.(캐시 누락률 확인 가능)

 

2.  새로운 LFU 모드

Redis 4.0부터는 LFU(Least Recently Used) 제거 모드를 사용할 수 있습니다.

LFU 모드에서 레디스는 항목의 액세스 빈도를 추적하려고 하므로 거의 사용되지 않는 항목은 제거됩니다.

→ 이것은 종종 사용되는 키가 메모리에 남아 있을 가능성이 높다는 것을 의미합니다.

 

LFU 모드를 구성하려면 다음 정책을 사용할 수 있습니다.

volatile-lfu: 만료 필드가 true로 설정된 가장 자주 사용하지 않는 키를 제거합니다.(expire set에 적용)

allkeys-lfu: 자주 사용하는 키를 유지합니다. 가장 자주 사용하지 않는(LFU) 키를 제거합니다. (모든 키에 적용)

 

Redis는 알고리즘을 더 잘 적용하기 위해 Morris 카운터 범위를 조정할 수 있고 이를 통해 대략적인 LFU를 사용합니다.

이러한 매개 변수를 조정하는 방법에 대한 지침은 redis.conf 파일에서 확인할 수 있습니다.

lfu-log-factor 10
lfu-time 1

 

 

감쇠 시간은 카운터가 샘플링될 때 해당 값보다 오래된 것으로 판명될 때 감쇠해야 하는 분 단위입니다. 특수 값 0은 스캔할 때마다 카운터를 항상 디코딩하는 것을 의미하며, 거의 유용하지 않습니다.

 

카운터 로그 계수는 0-255 범위에 있는 주파수 카운터를 포화시키는 데 필요한 히트 수를 변경합니다. 계수가 높을수록 최대값에 도달하기 위해 더 많은 액세스가 필요합니다.

 

계수가 낮을수록 다음 표에 따라 낮은 액세스에 대한 카운터의 해상도가 더 좋습니다.

+--------+------------+------------+------------+------------+------------+
| 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        |
+--------+------------+------------+------------+------------+------------+

factor가 높을 수록 포화 시키는데 걸리는 히트가 오래 걸린다는 의미