Lazy Redis is better Redis

2015-09-26

게으른 Redis가 더 나은 Redis

Redis가 단일 스레드라는 사실은 누구나 알고 있습니다. 아주 잘 아는 사람들은 사실 Redis가 *약간은* 단일 스레드라고 말할 것입니다. 디스크에서 특정 느린 작업을 수행하기 위한 스레드도 있기 때문입니다. 지금까지 스레드로 처리한 작업은 I/O에 집중되어 있었기 때문에, 다른 스레드에서 비동기 작업을 수행하는 작은 라이브러리의 이름도 bio.c였습니다. 기본적으로 Background I/O라는 뜻입니다.

그런데 얼마 전, 저를 포함해 많은 사람이 원하던 새로운 Redis 기능을 만들겠다고 약속하면서 이슈를 하나 열었습니다. 바로 “lazy free”입니다. 원래 이슈는 여기 있습니다: https://github.com/antirez/redis/issues/1748.

이 이슈의 요지는 Redis의 DEL 작업이 보통 블로킹된다는 것입니다. 따라서 Redis에 “DEL mykey”를 보냈는데 해당 키에 객체가 5천만 개나 들어 있다면, 서버는 그동안 아무것도 처리하지 못한 채 몇 초 동안 멈춥니다. 역사적으로 이는 Redis 설계의 부작용으로 대부분 받아들여졌지만, 특정 사용 사례에서는 제약이 됩니다. 블로킹되는 명령은 DEL만이 아닙니다. 하지만 DEL은 특별합니다. 보통 우리는 이렇게 말하기 때문입니다. O(1)과 O(log_N) 명령을 사용하는 한 Redis는 매우 빠릅니다. O(N) 명령을 사용해도 되지만, 그것은 우리가 최적화한 대상이 아니라는 점을 알아야 합니다. 지연 시간이 급증할 수 있으니 대비해야 합니다.

합리적으로 들리는 말입니다. 하지만 빠른 작업으로 만든 객체도 결국 삭제해야 합니다. 그리고 이때 Redis는 블로킹됩니다.

첫 번째 시도

단일 스레드 서버에서 작업을 논블로킹으로 만드는 쉬운 방법은 세상을 멈추는 대신 작업을 조금씩 처리하는 것입니다. 예를 들어 할당된 메모리 100만 개를 해제해야 한다면, 모든 작업을 for() 루프에서 처리하며 블로킹하는 대신 밀리초마다 1000개씩 해제할 수 있습니다. 사용하는 CPU 시간은 같거나, 로직이 더 필요하므로 조금 더 많을 수 있습니다. 하지만 사용자 관점에서 지연 시간은 훨씬 나아집니다. 밀리초마다 1000개를 해제하는 데 필요한 CPU 사이클은 애초에 사용되지 않고 있었을 수도 있습니다. 여기서 핵심은 몇 초 동안 블로킹하지 않는 것입니다. Redis 내부의 많은 기능이 이런 방식으로 동작합니다. LRU 축출과 키 만료가 대표적인 예이고, 해시 테이블의 점진적 리해시 같은 기능도 있습니다.

그래서 처음 시도한 방법은 새로운 타이머 함수를 만들고 그 안에서 축출을 수행하는 것이었습니다. 객체를 연결 리스트에 넣어 두고, 타이머 함수가 호출될 때마다 천천히 조금씩 회수하도록 했습니다. 이 방식이 제대로 동작하려면 몇 가지 요령이 필요합니다. 예를 들어 해시 테이블로 구현된 객체도 Redis의 SCAN 명령 내부에서 사용하는 것과 같은 방식으로 점진적으로 회수했습니다. 딕셔너리 내부의 커서를 가져와 요소를 하나씩 순회하며 해제하는 방식입니다. 이렇게 하면 타이머가 호출될 때마다 해시 테이블 전체를 해제할 필요가 없습니다. 타이머 함수에 다시 진입했을 때 어디까지 처리했는지는 커서가 알려 줍니다.

적응형 처리는 어렵다

이 작업에서 어려운 부분이 뭔지 아시나요? 이번에는 아주 특수한 작업을 조금씩 처리하고 있기 때문입니다. 바로 메모리를 해제하는 작업입니다. 메모리를 조금씩 해제하는 동안 서버 메모리 사용량이 매우 빠르게 증가한다면, 지연 시간을 줄이려다가 제한 없이 메모리를 사용할 수 있습니다. 이는 매우 나쁜 상황입니다. 예를 들어 다음과 같은 경우를 생각해 보세요.

WHILE 1
    SADD myset element1 element2 … many many many elements
    DEL myset
END

백그라운드에서 myset을 삭제하는 속도가 한 번 호출될 때마다 엄청난 수의 요소를 추가하는 SADD 호출보다 느리다면, 메모리 사용량은 영원히 증가할 것입니다.

하지만 몇 가지 실험을 거친 뒤, 아주 잘 동작하도록 만들 방법을 찾았습니다. 타이머 함수가 메모리 압박에 적응할 수 있도록 두 가지 아이디어를 사용했습니다.

메모리 추세를 확인합니다. 증가하고 있는가, 감소하고 있는가? 그에 따라 해제 작업의 적극성을 조절합니다.
“1”을 기준으로 타이머 자체의 실행 빈도도 조절합니다. 해제할 메모리가 거의 없을 때 이벤트 루프를 계속 중단하며 CPU 시간을 낭비하지 않도록 하기 위해서입니다. 동시에 정말 필요할 때는 타이머가 약 300Hz까지 실행될 수 있습니다.

이 아이디어를 구현했던 함수는 이제 사라졌지만, 그 코드의 일부는 다음과 같습니다.

/* Compute the memory trend, biased towards thinking memory is raising
 * for a few calls every time previous and current memory raise. */
if (prev_mem < mem) mem_trend = 1;
mem_trend *= 0.9; /* Make it slowly forget. */
int mem_is_raising = mem_trend > .1;

/* Free a few items. */
size_t workdone = lazyfreeStep(LAZYFREE_STEP_SLOW);

/* Adjust this timer call frequency according to the current state. */
if (workdone) {
    if (timer_period == 1000) timer_period = 20;
    if (mem_is_raising && timer_period > 3)
        timer_period--; /* Raise call frequency. */
    else if (!mem_is_raising && timer_period < 20)
        timer_period++; /* Lower call frequency. */
} else {
    timer_period = 1000;    /* 1 HZ */
}

좋은 요령이고 아주 잘 작동했습니다. 하지만 이 작업을 단일 스레드에서 처리해야 한다는 점은 여전히 조금 아쉬웠습니다. 제대로 처리하려면 로직이 많이 필요했고, 어쨌든 lazy free 사이클이 매우 바쁠 때는 초당 처리량이 평소의 약 65%로 감소했습니다.

객체를 다른 스레드에서 해제하는 편이 훨씬 간단할 것입니다. 해제 작업만 전담하는 스레드가 있다면, 새 값을 데이터셋에 추가하는 것보다 메모리를 해제하는 작업이 거의 항상 더 빠르기 때문입니다. 메인 스레드가 할당자를 호출하고 lazy free 스레드도 같은 할당자를 사용하는 동안 어느 정도 경합은 발생할 수 있습니다. 하지만 Redis가 할당에 사용하는 시간은 일부에 불과하고, I/O, 명령 디스패치, 캐시 미스 등에 훨씬 더 많은 시간을 사용합니다.

하지만 스레드 기반 lazy free를 구현하는 데는 큰 문제가 있었습니다. 바로 Redis 자체였습니다. 내부 설계가 객체를 서로 공유하는 방식에 완전히 치우쳐 있었기 때문입니다. 결국 객체에는 참조 카운트가 있지 않습니까? 그렇다면 최대한 많이 공유하지 않을 이유가 있을까요? 메모리와 시간을 절약할 수 있습니다. 몇 가지 예를 들어 보겠습니다. SUNIONSTORE를 실행하면 대상 집합에 공유 객체가 생깁니다. 마찬가지로 클라이언트 출력 버퍼에는 소켓으로 보낼 응답 객체 목록이 들어 있으므로, SMEMBERS 같은 호출을 수행하는 동안 집합의 모든 멤버가 출력 버퍼 목록에서 공유 객체가 될 수 있습니다. 객체를 공유하는 방식은 정말 유용하고, 사랑스럽고, 훌륭하고, 대단히 멋져 보입니다.

하지만 잠깐, 여기에는 뭔가 더 있습니다. SUNIONSTORE 이후 데이터베이스를 다시 로드하면 객체가 공유되지 않은 상태가 되므로 메모리 사용량이 갑자기 이전보다 더 늘어날 수 있습니다. 별로 좋지 않습니다. 게다가 클라이언트에 응답을 보낼 때는 어떻게 될까요? 객체가 작을 때는 실제로 객체를 일반 버퍼에 *이어 붙입니다*. 그렇지 않으면 write() 호출을 여러 번 수행하는 것이 비효율적이기 때문입니다! (참고로 writev()도 도움이 되지 않습니다.) 즉, 우리는 이미 대부분 복사하고 있습니다. 프로그래밍에서 유용하지 않은 무언가가 존재한다면, 그것은 문제가 될 가능성이 큽니다.

실제로 집계형 데이터 타입을 담은 키에서 값을 조회할 때마다 다음 구조를 순회해야 했습니다.

key -> value_obj -> hash table -> robj -> sds_string

그렇다면 “robj” 구조체를 완전히 없애고, 집계형 값을 해시 테이블(또는 스킵 리스트)의 SDS 문자열만으로 구성하면 어떨까요? (SDS는 Redis 내부에서 문자열에 사용하는 라이브러리입니다.) 여기에는 문제가 있습니다. SADD myset myvalue 같은 명령을 생각해 보세요. 예를 들어 client->argv[2]를 가져와 집합을 구현하는 해시 테이블에서 그대로 참조할 수는 없습니다. 값을 때로는 *복제*해야 하기 때문입니다. 명령을 파싱할 때 만들어진 클라이언트 인자 벡터에 이미 존재하는 값을 재사용할 수 없습니다. 하지만 Redis 성능은 캐시 미스의 영향을 크게 받습니다. 그렇다면 간접 참조를 한 단계 줄이는 것으로 이를 상쇄할 수 있지 않을까요?

그래서 이 새로운 lazyfree 브랜치 작업을 시작했고, 아무런 맥락 없이 Twitter에 진행 상황을 트윗했습니다. 덕분에 모두가 제가 절망했거나 미친 사람이라고 생각하고 있었습니다. (결국 몇 명은 이 lazyfree가 대체 뭐냐고 물어보기도 했습니다.) 그래서 제가 한 일은 무엇일까요?

클라이언트 출력 버퍼가 robj 구조체 대신 동적 문자열만 사용하도록 변경했습니다. 응답을 만들어야 할 때 값은 항상 복사됩니다.
모든 Redis 데이터 타입이 공유 robj 구조체 대신 SDS 문자열을 사용하도록 변환했습니다. 간단해 보이나요? 여러 주에 걸쳐 버그에 매우 민감한 코드 약 800줄을 수정했습니다. 하지만 이제 모든 테스트가 통과합니다.
lazyfree를 스레드 기반으로 다시 작성했습니다.

그 결과 데이터 구조 구현에 robj 구조체가 더 이상 사용되지 않으므로 Redis의 메모리 효율이 좋아졌습니다. (다만 명령 디스패치와 복제처럼 공유가 많이 일어나는 코드 경로에서는 여전히 robj 구조체를 사용합니다.) 스레드 기반 lazy free는 훌륭하게 동작하며 메모리를 회수하는 속도도 점진적 방식보다 빠릅니다. 점진적 방식의 구현을 제가 아주 좋아하고, 스레드 기반 방식과 비교해도 그리 나쁘지 않았다는 점을 고려하면 더욱 그렇습니다. 이제 거대한 키를 삭제해도 성능 저하가 무시할 수 있을 정도로 작기 때문에 매우 유용합니다. 하지만 가장 흥미로운 점은 지금까지 테스트한 모든 작업에서 Redis가 더 빨라졌다는 사실입니다. 간접 참조를 줄인 것이 여기서 진정한 승자였습니다. 클라이언트 출력 버퍼가 더 단순하고 빨라졌다는 이유만으로, 관련 없는 벤치마크에서도 더 빠릅니다. 결국 브랜치에서는 점진적 lazy free 구현을 삭제하고 스레드 기반 구현만 남겼습니다.

API에 관한 참고 사항

그렇다면 API는 어떻게 될까요? 여전히 블로킹되는 DEL이 있고 기본 동작도 같습니다. Redis에서 DEL은 메모리를 지금 즉시 회수한다는 의미이기 때문입니다. 저는 이 동작을 바꾸고 싶지 않았습니다. 그래서 이제 값에 어떤 일이 일어나는지 더 명확하게 나타내는 UNLINK라는 새 명령을 추가했습니다.

UNLINK는 똑똑한 명령입니다. 객체를 할당 해제하는 데 드는 비용을 계산하고, 그 비용이 매우 작으면 DEL이 해야 하는 작업을 그대로 수행해 최대한 빨리 객체를 해제합니다. 그렇지 않으면 객체를 백그라운드 큐로 보내 처리합니다. 키 공간의 의미론 관점에서 보면 두 명령은 동일합니다.

FLUSHALL / FLUSHDB의 논블로킹 변형도 구현했지만, 아직 API 수준에는 반영하지 않았습니다. 옵션으로 LAZY를 지정하면 동작이 바뀌도록 할 뿐입니다.

lazy free만이 아니다

이제 집계형 데이터 타입의 값이 완전히 공유되지 않고, 클라이언트 출력 버퍼에도 공유 객체가 들어 있지 않으므로 활용할 수 있는 여지가 많습니다. 예를 들어 마침내 Redis에서 스레드 기반 I/O를 구현할 수 있습니다. 서로 다른 클라이언트를 서로 다른 스레드에서 처리하는 방식입니다. 즉, 데이터베이스에 접근할 때만 전역 잠금이 필요하고, 클라이언트의 읽기/쓰기 시스템 호출은 물론 클라이언트가 보내는 명령의 파싱까지도 서로 다른 스레드에서 수행할 수 있습니다. memcached와 비슷한 설계이며, 저도 구현하고 테스트해 보기를 기대하고 있습니다.

게다가 이제 집계형 데이터 타입에 대한 특정 느린 작업을 다른 스레드에서 수행할 수도 있습니다. 이때 “블로킹”되는 키는 일부뿐이고 나머지 모든 클라이언트는 계속 작업할 수 있습니다. 현재 블로킹 작업에 사용하는 방식(blocking.c 참고)에 키별로 현재 사용 중인 클라이언트를 저장하는 해시 테이블을 더하면 매우 비슷한 방식으로 구현할 수 있습니다. 따라서 어떤 클라이언트가 SMEMBERS 같은 작업을 요청하면 해당 키만 잠그고, 출력 버퍼를 만들어 요청을 처리한 다음, 나중에 키를 다시 해제할 수 있습니다. 키가 잠겨 있을 때 같은 키에 접근하려는 클라이언트만 블로킹됩니다.

이 모든 작업에는 내부 구조를 더욱 크게 바꾸는 일이 필요합니다. 하지만 여기서 중요한 결론은 금기가 하나 줄었다는 것입니다. 객체 복사에 드는 시간은 캐시 미스를 줄이고 집계형 데이터 타입의 메모리 사용량을 줄여 보상할 수 있습니다. 따라서 이제는 공유하지 않는 설계를 사용하는 스레드 기반 Redis를 생각해 볼 수 있습니다. 이 설계만이 단일 스레드 방식보다 쉽게 더 나은 성능을 낼 수 있습니다. 과거에는 동시 접근을 구현하기 위해 데이터 구조와 객체에 뮤텍스를 배치하는 방식의 스레드 기반 Redis를 언제나 나쁜 생각으로 여겼습니다. 하지만 다행히도 두 세계의 장점을 모두 얻을 수 있는 대안이 있습니다. 원한다면 과거처럼 빠른 작업을 모두 메인 스레드에서 계속 처리할 수도 있습니다. 성능 측면에서는 약간의 제한된 복잡성만 부담하면 얻는 것뿐일 것입니다.

예정 시기

내부를 많이 건드렸기 때문에 내일 당장 운영 환경에 적용할 수 있는 작업은 아닙니다. 따라서 제 계획은 이미 unstable에 들어간 것을 3.2로 부르고, Release Candidate 상태로 만들기 위한 작업을 진행한 다음, 이 브랜치를 3.4를 목표로 unstable에 병합하는 것입니다.

하지만 병합하기 전에 속도 저하가 발생하지 않았는지 매우 꼼꼼하게 확인해야 합니다. 아직 할 일이 분명히 더 남아 있습니다.

직접 시험해 보고 싶다면 Github의 “lazyfree” 브랜치를 확인해 보세요. 참고로 지금도 매우 활발하게 작업 중이므로, 현재는 어떤 부분이 순간적으로 완전히 망가져 있을 수도 있다는 점을 알아 두시기 바랍니다.