Redis LRU 알고리즘 개선에 대한 단상
Redis는 종종 캐시로 사용되며, 사용할 최대 메모리를 고정된 값으로 지정하는 형태로 운영됩니다. 새로운 데이터가 들어오면 오래된 데이터를 삭제해 공간을 확보해야 합니다. 캐시로서 Redis의 효율성은 어떤 데이터를 제거할지에 대해 얼마나 좋은 결정을 내리는지와 직결됩니다. 곧 필요할 데이터를 삭제하는 것은 나쁜 전략이며, 다시 요청될 가능성이 낮은 데이터를 삭제하는 것이 좋은 전략입니다.
달리 말하면 모든 캐시는 히트/미스 비율을 가집니다. 정성적으로 말하자면 캐시가 처리할 수 있는 읽기 질의의 비율을 의미합니다. 대부분의 워크로드에서 캐시 키에 대한 접근은 데이터셋 전체에 균등하게 분포하지 않습니다. 종종 소수의 키가 전체 접근의 대부분을 차지합니다. 게다가 접근 패턴은 시간이 지나면서 바뀌기 일쑤이며, 이는 시간이 흐르면 한때 요청이 많던 키가 더 이상 자주 접근되지 않을 수도 있고, 반대로 한때 인기 없던 키가 가장 많이 접근되는 키가 될 수도 있음을 의미합니다.
따라서 일반적으로 캐시가 해야 할 일은 미래에 접근될 확률이 가장 높은 키를 유지하는 것입니다. 제거 정책(새로운 데이터가 들어올 공간을 만들기 위해 사용하는 정책)의 관점에서 보면 이는 반대로 해석됩니다. 즉, 미래에 접근될 확률이 가장 낮은 키를 데이터셋에서 제거해야 합니다. 문제는 단 하나, Redis를 비롯한 캐시는 미래를 예측할 수 없다는 점입니다.
LRU 알고리즘
캐시는 미래를 예측할 수 없지만 다음과 같이 추론할 수 있습니다. 다시 요청될 가능성이 높은 키는 최근에 자주 요청된 키라는 것입니다. 일반적으로 접근 패턴이 아주 갑자기 바뀌지는 않으므로 이는 효과적인 전략입니다. 하지만 ‘최근에 자주 요청된’이라는 개념은 얼핏 보기보다 훨씬 교묘합니다(이에 대해서는 곧 다시 다루겠습니다). 그래서 이 개념은 LRU라고 불리는 알고리즘으로 단순화되며, 이 알고리즘은 대신 키가 마지막으로 요청된 시점만을 추적합니다. 자주 접근되는 키는 드물게 접근되는 키에 비해 유휴 상태(접근되지 않은 상태)가 짧을 확률이 더 높습니다.
예를 들어 다음은 네 개의 서로 다른 키에 대한 시간 경과에 따른 접근을 나타낸 것입니다. “~” 문자 하나는 1초를 의미하며, 끝에 있는 “|” 선은 현재 시점을 나타냅니다.
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|키 A는 5초에 한 번, 키 B는 2초에 한 번, 키 C와 D는 모두 10초에 한 번 접근됩니다.
키 B는 접근 빈도가 높기 때문에 유휴 시간이 가장 짧은 축에 속하며, 이는 마지막 접근 시점이 네 키 중 두 번째로 최근이라는 뜻입니다.
마찬가지로 A와 C의 유휴 시간인 2초와 6초는 두 키의 접근 빈도를 잘 반영합니다. 하지만 보시다시피 이 방법은 항상 통하는 것은 아닙니다. 키 D는 10초마다 접근되지만 네 키 중 가장 최근의 접근 시점을 가지고 있습니다.
그럼에도 장기적으로 보면 이 알고리즘은 충분히 잘 동작합니다. 일반적으로 접근 빈도가 높은 키일수록 유휴 시간이 더 짧습니다. LRU 알고리즘은 가장 오랫동안 사용되지 않은(Least Recently Used) 키, 즉 유휴 시간이 가장 긴 키를 제거합니다. 구현도 간단합니다. 특정 키가 마지막으로 접근된 시점만 추적하면 되기 때문입니다. 때로는 그것조차 필요 없습니다. 제거 대상이 되는 모든 객체를 연결 리스트로 연결해 두면 됩니다. 객체가 접근되면 리스트의 맨 앞으로 옮기고, 제거가 필요할 때는 리스트의 꼬리에서부터 제거하면 됩니다. 짜잔! 성공입니다.
Redis의 LRU: 그 시작
처음에 Redis는 LRU 제거를 지원하지 않았습니다. 메모리 효율이 큰 관심사가 되면서 나중에 추가되었습니다. Redis Object 구조를 조금 수정해 24비트의 공간을 확보했습니다. 객체들을 연결 리스트로 연결할 만한 여유는 없었습니다(포인터가 너무 커집니다!). 게다가 구현은 효율적이어야 했습니다. 제거할 키를 선정하는 과정 때문에 서버 성능이 크게 떨어져서는 안 됐기 때문입니다.
객체 안의 24비트는 현재 유닉스 시간을 초 단위로 나타낸 값 중 하위 비트들을 저장하기에 충분합니다. Redis 소스 코드 안에서 “LRU clock”이라고 불리는 이 표현은 오버플로가 발생하기까지 194일이 걸립니다. 키의 메타데이터는 그보다 훨씬 자주 갱신되므로 이 정도면 충분했습니다.
하지만 더 복잡한 문제가 하나 더 있었습니다. 제거하기 위해 유휴 시간이 가장 긴 키를 어떻게 선정할 것인가 하는 문제였습니다. Redis의 키 공간은 평면적인 해시 테이블로 표현됩니다. 이 메타데이터를 담기 위해 다른 자료구조를 추가하는 것은 선택지가 아니었습니다. 그러나 LRU 자체가 우리가 달성하고자 하는 것의 근사치라면, LRU 자체를 근사해 보는 것은 어떨까 하는 생각이 들었습니다.
초기의 Redis 알고리즘은 아주 단순했습니다. 키를 제거해야 할 때 무작위로 3개의 키를 뽑아 그중 유휴 시간이 가장 긴 키를 제거하는 방식이었습니다. 기본적으로 키 공간에서 무작위 샘플링을 수행해 그중 더 나은 키를 제거하는 셈입니다. 이후 이 “무작위 3개”는 설정 가능한 “무작위 N개”로 바뀌었고, 알고리즘 속도도 개선되어 성능 손실 없이 기본값이 5개 샘플링으로 상향되었습니다. 얼마나 단순한지를 생각하면 정말 잘 동작했고, 사실 매우 잘 동작했습니다. 곰곰이 생각해보면 이 알고리즘으로는 절대 최상의 결정을 내리지는 않지만, 아주 나쁜 결정을 내릴 가능성도 매우 낮습니다. 데이터셋 안에 아주 자주 접근되는 키들의 부분 집합이 있다면, 5개를 샘플링했을 때 유휴 시간이 아주 짧은 키만 뽑히는 불운을 겪기는 어렵기 때문입니다.
하지만 이 알고리즘을 여러 번 실행되는 과정 전체로 놓고 보면, 흥미로운 정보를 많이 버리고 있음을 알 수 있습니다. N개의 키를 샘플링하는 과정에서 꽤 괜찮은 후보들을 많이 만나더라도 결국 가장 좋은 하나만 제거하고 다음 주기에는 다시 처음부터 시작하기 때문입니다.
파이트 클럽의 첫 번째 규칙: 알고리즘을 맨눈으로 관찰하라
어느 시점 저는 차기 Redis 3.0 릴리스를 작업 중이었습니다. Redis 2.8은 여러 환경에서 LRU 캐시로 활발히 사용되고 있었고, 사람들은 Redis의 제거 정밀도에 대해 크게 불평하지는 않았습니다. 하지만 눈에 띄는 추가 CPU 시간을 쓰지 않고도, 단 1비트도 추가하지 않고도 개선할 수 있음은 분명했습니다.
하지만 무언가를 개선하려면 직접 들여다봐야 합니다. LRU 알고리즘을 들여다보는 방법은 여러 가지가 있습니다. 예를 들어 다양한 워크로드를 시뮬레이션하는 도구를 작성해 최종적인 히트/미스 비율을 확인할 수 있습니다. 저도 그렇게 했지만, 히트/미스 비율은 접근 패턴에 크게 좌우되므로 이 정보에 더해 알고리즘의 품질을 시각적으로 보여주는 유틸리티를 하나 더 작성했습니다.
프로그램은 매우 단순했습니다. 일정 개수의 키를 추가한 뒤, 각 키의 유휴 시간이 점차 줄어들도록 순차적으로 접근했습니다. 마지막으로 기존보다 50% 더 많은 키(그림에서 녹색으로 표시된 키)를 추가해, 기존 키 중 절반이 제거되어야 하는 상황을 만들었습니다.
완벽한 LRU 구현이라면 새로 추가된 키는 하나도 제거되지 않고, 기존 데이터셋의 앞쪽 50%가 제거됩니다.
다음은 이 프로그램이 서로 다른 버전과 설정의 Redis에 대해 생성한 결과입니다.
http://redis.io/images/redisdoc/lru_comparison.png
그래프를 볼 때 지금까지 논의한 구현이 Redis 2.8의 것임을 기억해 주시기 바랍니다. Redis 3.0에서 보이는 개선 내용은 다음 절에서 설명합니다.
LRU V2: 중요한 정보를 버리지 말자
새로운 시각화 도구를 이용해 몇 분 만에 새로운 접근법을 시도하고 테스트할 수 있었습니다. Redis가 사용하던 기본 알고리즘을 개선하는 가장 분명한 방법은, 그렇지 않으면 버려질 정보를 제거 후보들의 “풀(pool)”에 모아두는 것이었습니다.
기본적으로 N개의 키를 샘플링할 때, 그 결과를 더 큰 키 풀(기본값은 16개)을 채우는 데 사용했습니다. 이 풀은 키를 유휴 시간 순으로 정렬해 두므로, 새로운 키는 풀 안에 있는 키 중 하나보다 유휴 시간이 더 길거나 풀에 빈자리가 있을 때만 진입합니다.
이 작은 변경으로 알고리즘 성능은 제가 위에서 링크한 이미지에서 볼 수 있듯이 극적으로 개선되었고, 구현도 그리 복잡하지 않았습니다. 여기저기서 memmove()를 몇 번 쓰고 약간의 프로파일링을 거쳤을 뿐, 이 부분에서 큰 버그가 있었던 기억은 없습니다.
동시에 LRU 정밀도를 테스트하기 위한 새로운 redis-cli 모드가 추가되었습니다(—lru-test 옵션을 참고하시기 바랍니다). 덕분에 멱법칙(power-law) 접근 패턴에서 LRU 코드의 성능을 확인할 수 있는 또 다른 방법이 생겼습니다. 이 도구는 다른 테스트를 통해 새로운 알고리즘이 보다 현실에 가까운 워크로드에서 더 잘 동작함을 검증하는 데 사용되었습니다. 파이프라이닝을 사용하고 초당 접근 횟수를 표시하므로, 서로 다른 구현을 벤치마크하거나 최소한 눈에 띄는 속도 저하를 확인하는 용도로도 사용할 수 있습니다.
Least Frequently Used
제가 지금 이 블로그 글을 쓰는 이유는 며칠 전 Redis 캐시 제거 코드를 부분적으로 재구현하고 여러 가지를 개선하는 작업을 했기 때문입니다.
모든 것은 하나의 공개 이슈에서 시작되었습니다. Redis 3.2에서 여러 데이터베이스를 사용할 때 알고리즘이 각 DB별로 지역적인 선택을 하며 제거를 수행한다는 문제였습니다. 예를 들어 DB 0에는 유휴 시간이 짧은 키만 있고 DB 1에는 유휴 시간이 긴 키만 있는데도, Redis는 각 DB에서 하나씩 키를 제거했습니다. 더 합리적인 선택은 당연히 DB 1의 키부터 제거하기 시작해 나중에 다른 키들을 제거하는 것입니다.
Redis를 캐시로 사용할 때 여러 DB를 함께 쓰는 경우는 드물기 때문에 보통은 큰 문제가 되지 않습니다. 하지만 이렇게 해서 저는 다시 제거 코드를 만지게 되었습니다. 결국 풀에 데이터베이스 ID를 포함하도록 수정하고, DB마다 별도의 풀을 쓰는 대신 모든 DB가 하나의 풀을 공유하도록 했습니다. 처음에는 더 느렸지만 프로파일링과 튜닝을 거쳐 결국 원래 구현보다 약 20% 더 빨라졌습니다.
하지만 그 시점에 Redis의 이 서브시스템에 대한 호기심이 다시 자극되었고, 더 개선하고 싶어졌습니다. LRU 구현을 개선하려고 며칠을 보냈습니다. 풀을 더 크게 만들어 볼까? 최적의 키를 고르는 동안 흐르는 시간을 고려해 볼까?
얼마간의 시간이 지나고 도구를 다듬은 뒤에야, LRU 알고리즘은 데이터베이스에서 샘플링하는 데이터 양에 의해 제한될 뿐 그 자체로는 매우 훌륭하고 개선하기 어렵다는 것을 깨달았습니다. 이는 사실 서로 다른 알고리즘을 보여주는 이미지에서도 어느 정도 드러납니다. 주기마다 10개의 키를 샘플링하면 이론적인 LRU와 거의 같은 정확도를 보였습니다.
원래 알고리즘을 개선하기 어렵다는 것을 알게 된 뒤, 새로운 알고리즘을 테스트하기 시작했습니다. 이 글의 서두로 조금 되돌아가 보면, LRU는 사실 일종의 편법이라고 말한 바 있습니다. 우리가 정말로 원하는 것은 미래에 접근될 확률이 가장 높은 키, 즉 가장 최근에 접근된 키가 아니라 가장 자주 접근된 키를 유지하는 것입니다.
접근 횟수가 가장 적은 키를 제거하는 알고리즘을 LFU라고 합니다. Least Frequently Used의 약자로, 새로운 키를 위한 공간을 만들기 위해 제거하려는 키의 특성을 나타냅니다.
이론적으로 LFU는 각 키에 카운터를 하나씩 연결하는 것만큼 단순합니다. 접근이 있을 때마다 카운터가 증가하므로, 특정 키가 다른 키보다 더 자주 접근된다는 것을 알 수 있습니다.
물론 Redis에만 국한되지 않는, LFU 구현 전반에 걸친 몇 가지 문제가 더 있습니다.
- LFU에서는 LRU에서처럼 “맨 앞으로 이동”하는 연결 리스트 트릭을 이용해 제거 대상을 간단히 정렬된 상태로 유지할 수 없습니다. “완벽한 LFU”에서는 키가 접근 횟수 순으로 정렬되어야 하기 때문입니다. 접근된 키를 올바른 위치로 옮기는 작업은 같은 점수를 가진 키가 많을 수 있어 문제가 될 수 있습니다. 키의 빈도 카운터가 아주 조금만 변했더라도 최악의 경우 연산이 O(N)이 될 수 있습니다. 또한 뒤에 나오는 2번에서 보겠지만 접근 카운터가 항상 조금씩만 변하는 것도 아니며, 때로는 갑자기 크게 변하기도 합니다.
- LFU는 접근이 있을 때마다 접근 카운터를 단순히 증가시키는 것만큼 자명하게 동작하지 않습니다. 앞서 말했듯이 접근 패턴은 시간이 지나면서 변하므로, 더 이상 계속 접근되지 않는 높은 점수의 키는 시간이 지나면서 점수가 낮아져야 합니다. 우리 알고리즘은 시간에 따라 적응할 수 있어야 합니다.
Redis에서는 첫 번째 문제는 문제가 되지 않습니다. LRU에서 사용한 트릭, 즉 후보 풀을 이용한 무작위 샘플링을 그대로 사용하면 됩니다. 두 번째 문제는 여전히 남습니다. 그래서 일반적으로 LFU 구현은 가끔씩 접근 카운터를 감소시키거나 절반으로 줄이는 방법을 가지고 있습니다.
24비트 공간에 LFU 구현하기
LFU 자체도 구현상의 특성이 있지만, Redis에서는 LFU를 모델링하기 위해 24비트 LRU 필드만을 사용할 수 있습니다. 객체당 단 24비트로 LFU를 구현하는 것은 조금 더 까다롭습니다.
24비트 안에서 해야 할 일은 다음과 같습니다.
- 일종의 접근 빈도 카운터.
- 카운터를 언제 절반으로 줄일지 결정할 수 있을 만큼의 정보.
제가 선택한 해결책은 24비트를 두 개의 필드로 나누는 것이었습니다.
16 bits 8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+16비트 필드는 마지막 감소 시점으로, Redis가 카운터가 마지막으로 감소된 시점을 알 수 있게 합니다. 8비트 필드는 실제 접근 카운터입니다.
8비트 카운터는 금방 오버플로가 나지 않을까 생각하실 겁니다. 핵심은 단순한 카운터 대신 로그 카운터를 사용했다는 점입니다. 키에 접근할 때 카운터를 증가시키는 함수는 다음과 같습니다.
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255;
double r = (double)rand()/RAND_MAX;
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++;
return counter;
}기본적으로 카운터의 값이 클수록 카운터가 실제로 증가할 확률은 낮아집니다. 위 코드는 카운터가 증가할수록 점점 작아지는 0과 1 사이의 수 p를 계산합니다. 그런 다음 0과 1 사이의 난수 r을 뽑아 r < p일 때만 카운터를 증가시킵니다.
redis.conf 파라미터를 통해 카운터가 얼마나 공격적으로 증가할지 설정할 수 있지만, 예를 들어 기본 설정에서는 다음과 같은 일이 일어납니다.
100번의 히트 후 카운터 값은 10이 됩니다. 1000번 후에는 18, 10만 번 후에는 142가 되며, 100만 번 히트하면 255 한계에 도달해 더 이상 증가하지 않습니다.
이제 이 카운터가 어떻게 감소되는지 살펴보겠습니다. 16비트는 분 단위로 변환된 유닉스 시간의 하위 비트들을 저장하는 데 사용됩니다. Redis가 키 공간을 무작위로 샘플링하며 풀을 채울 키를 탐색할 때, 마주치는 모든 키에 대해 감소 여부를 검사합니다. 마지막 감소가 N분보다 더 오래전에 수행되었다면(N은 설정 가능), 카운터 값이 높은 경우에는 절반으로 줄이고, 낮은 경우에는 단순히 1 감소시킵니다(카운터 해상도가 매우 작기 때문에 접근 횟수가 적은 키들 사이를 더 잘 구분하기 위함입니다).
또 다른 문제가 있습니다. 새로운 키도 결국 살아남을 기회가 필요합니다. 일반적인 LFU에서는 새로 추가된 키의 접근 점수가 0이므로 제거 후보로 매우 적합합니다. Redis에서는 새로운 키가 LFU 값 5로 시작합니다. 이 초기값은 증가 및 절반 감소 알고리즘에 반영됩니다. 시뮬레이션 결과, 이 변경으로 키들이 접근 횟수를 누적할 시간을 벌게 됩니다. 점수가 5보다 낮은 키가 우선적으로 제거됩니다(오랫동안 비활성 상태였던 키).
코드와 성능
위에서 설명한 구현은 Redis의 “unstable” 브랜치에서 찾을 수 있습니다. 초기 테스트 결과 멱법칙 접근 패턴에서 키당 동일한 메모리를 사용하면서도 LRU보다 성능이 우수했습니다. 하지만 실제 접근 패턴은 다를 수 있습니다. 접근의 시간적·공간적 지역성은 매우 다양한 방식으로 변할 수 있으므로, 실제 사용 사례에서 LFU가 어떻게 동작하는지, 그리고 Redis LFU 구현에서 조정할 수 있는 두 개의 파라미터가 워크로드별로 성능을 어떻게 바꾸는지 알게 된다면 매우 기쁠 것입니다.
또한 특정 키의 빈도 카운터를 보고하기 위해 OBJECT FREQ 하위 명령이 추가되었습니다. 이는 애플리케이션의 접근 패턴을 관찰하는 데도 유용하고, LFU 구현을 디버깅하는 데도 유용합니다.
런타임에 LRU와 LFU 정책을 전환하면 거의 무작위에 가까운 제거가 일어나게 된다는 점에 유의하시기 바랍니다. 24비트 카운터에 누적된 메타데이터가 새로 선택된 정책의 의미와 맞지 않기 때문입니다. 하지만 시간이 지나면 다시 적응합니다.
아직 개선할 여지는 아마 많이 남아 있습니다.
Ben Manes가 TinyLRU라는 알고리즘을 설명하는 흥미로운 논문을 알려주었습니다(http://arxiv.org/pdf/1512.00727.pdf).
이 논문에는 아주 기발한 아이디어가 담겨 있습니다. 현재 객체들의 접근 빈도를 기억하는 대신, 지금까지 본 모든 객체들의 접근 빈도를 (확률적으로) 기억하자는 것입니다. 이렇게 하면 이름만 보고 접근이 적을 것 같다고 판단되는 새로운 키는 아예 거부할 수도 있어, 키를 제거하는 것이 히트/미스 비율을 낮추게 될 경우 아예 제거가 필요 없게 됩니다.
이 기법은 일반적인 GET/SET LFU 캐시에는 매우 흥미롭지만, Redis의 자료구조 서버라는 특성에는 적용하기 어렵다고 생각합니다. 사용자는 키가 생성된 후 적어도 몇 밀리초 동안은 키가 존재할 것으로 기대합니다. 키 생성 자체를 거부하는 것은 Redis의 의미론상 맞지 않아 보입니다.
다만 Redis는 키가 덮어쓰일 때 LFU 정보를 유지합니다. 예를 들어 다음 명령을 실행한 뒤에는
SET oldkey some_new_value24비트 LFU 카운터가 기존 키와 연결된 새로운 객체에 복사됩니다.
Redis unstable의 새로운 제거 코드에는 그 밖에도 반가운 소식이 있습니다.
- 정책이 이제 “크로스 DB”로 동작합니다. 과거에는 이 글 서두에서 설명했듯이 Redis가 지역적인 선택을 했습니다. 이제는 LRU뿐만 아니라 모든 정책에 대해 이 문제가 수정되었습니다.
- 만료(expire)가 설정된 키의 남은 수명(TTL)을 기준으로 제거하는 volatile-ttl 제거 정책도 이제 다른 정책들처럼 풀을 사용합니다.
- 키 풀에서 SDS 객체를 재사용함으로써 성능이 개선되었습니다.
이 글은 예상보다 훨씬 길어졌지만, 새로운 기능과 기존에 있던 것들의 개선에 대해 몇 가지 통찰을 드릴 수 있었기를 바랍니다. Redis는 특정 문제를 해결하기 위한 “솔루션”이라기보다는 범용 도구입니다. 이를 올바른 방식으로 적용하는 것은 합리적인 개발자의 몫입니다. 많은 사람들이 Redis를 캐싱 솔루션으로 사용하므로, 이 영역의 개선은 항상 수시로 검토되고 있습니다.
Hacker News 댓글: https://news.ycombinator.com/item?id=12185534