Random notes on improving the Redis LRU algorithm

2016-07-29

Redis LRU 알고리즘 개선에 대한 단상

원문은 Salvatore Sanfilippo님이 2016-07-29에 게재했습니다. 이 블로그 구독하기

Redis는 종종 캐시 용도로 사용되며, 사용할 최대 메모리를 고정해 두는 방식으로 운용된다. 새로운 데이터가 들어오면 기존 데이터를 삭제해 공간을 확보해야 한다. 캐시로서 Redis의 효율성은 어떤 데이터를 내보낼지에 대해 얼마나 현명한 결정을 내리는지와 직결된다. 곧 필요해질 데이터를 삭제하는 것은 나쁜 전략이며, 다시 요청될 가능성이 낮은 데이터를 삭제하는 것이 좋은 전략이다.

다른 말로 하면 모든 캐시는 히트/미스 비율을 갖는데, 이는 정성적으로 말하면 캐시가 처리할 수 있는 읽기 요청의 비율을 의미한다. 대부분의 워크로드에서 캐시 키에 대한 접근은 데이터셋 전체에 균등하게 분포하지 않는다. 종종 소수의 키가 전체 접근의 대부분을 차지한다. 게다가 접근 패턴은 시간이 지남에 따라 자주 바뀌는데, 한때 요청이 매우 많았던 키가 더 이상 자주 접근되지 않게 되고, 반대로 한때 인기가 없던 키가 가장 많이 접근되는 키로 바뀌기도 한다는 뜻이다.

따라서 일반적으로 캐시가 해야 할 일은 앞으로 접근될 확률이 가장 높은 키를 유지하는 것이다. 축출 정책(eviction policy, 새로운 데이터가 들어올 공간을 만들기 위해 사용하는 정책)의 관점에서 보면 이는 반대로 해석된다. 즉, 앞으로 접근될 확률이 가장 낮은 키를 데이터셋에서 제거해야 한다. 문제는 단 하나다. 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 시간이나 단 한 비트의 추가 공간도 사용하지 않고도 충분히 개선할 수 있다는 것은 분명했다.

하지만 무언가를 개선하려면 그것을 들여다봐야 한다. 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 모드가 추가되었다(see the —lru-test option), 이를 통해 거듭제곱 법칙(power-law) 접근 패턴에서 LRU 코드의 성능을 확인하는 또 다른 방법을 갖게 되었다. 이 도구는 새로운 알고리즘이 좀 더 현실에 가까운 워크로드에서도 더 잘 동작함을 다른 테스트로 검증하는 데 사용되었다. 또한 파이프라이닝을 사용하고 초당 접근 횟수를 표시하므로, 서로 다른 구현을 벤치마크하거나 적어도 명백한 속도 저하를 확인하는 데 활용할 수 있다.

Least Frequently Used

지금 이 블로그 글을 쓰는 이유는 며칠 전 Redis 캐시 축출 코드의 부분적인 재구현과 여러 개선 작업을 했기 때문이다.

모든 것은 하나의 오픈 이슈에서 시작됐다. Redis 3.2에서 여러 데이터베이스를 사용할 때 알고리즘이 국소적인 선택을 하며 축출한다는 문제였다. 예를 들어 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_value

24비트 LFU 카운터가 기존 키에 연결된 새로운 객체로 복사된다.

Redis unstable의 새로운 축출 코드에는 다른 좋은 소식도 있다.

정책이 이제 “cross DB” 방식으로 동작한다. 과거에는 이 글 초반에 설명했듯이 Redis가 국소적인 선택을 했지만, 이제는 LRU뿐만 아니라 모든 정책에 대해 이 문제가 수정되었다.
만료 시간이 설정된 키의 남은 TTL을 기준으로 축출하는 volatile-ttl 축출 정책도 이제 다른 정책처럼 풀을 사용한다.
키 풀에서 SDS 객체를 재사용함으로써 성능이 더 좋아졌다.

이 글은 예상보다 훨씬 길어졌지만, 새로운 기능과 기존에 있던 것들의 개선점에 대해 몇 가지 인사이트를 제공했기를 바란다. Redis는 특정 문제를 해결하는 “솔루션”이라기보다는 범용 도구다. 이를 올바른 방식으로 적용하는 것은 현명한 개발자에게 달려 있다. 많은 사람들이 Redis를 캐싱 솔루션으로 사용하므로, 이 분야의 개선은 항상 수시로 연구되고 있다.

Hacker News 댓글: https://news.ycombinator.com/item?id=12185534