누구나 Redis가 싱글 스레드라는 걸 안다. 조금 더 잘 아는 사람이라면 사실 Redis는 *어느 정도* 싱글 스레드라고 말할 것이다. 디스크에서 느린 작업을 처리하기 위한 스레드가 있으니까. 지금까지 스레드를 활용한 작업은 I/O에 너무 집중되어 있어서, 다른 스레드에서 비동기 작업을 수행하던 작은 라이브러리를 우리는 bio.c라고 불렀다. 말 그대로 Background I/O다.

하지만 얼마 전 나는 나를 포함해 많은 사람이 원하던 “lazy free”라는 새로운 Redis 기능을 약속하는 이슈를 열었다. 원래 이슈는 여기 있다: https://github.com/antirez/redis/issues/1748.

이슈의 요지는 Redis의 DEL 연산이 보통 블로킹된다는 것이다. 그래서 Redis에 “DEL mykey”를 보내는데 그 키에 마침 5천만 개의 객체가 들어 있다면, 서버는 그 사이 아무것도 처리하지 못한 채 몇 초 동안 블로킹된다. 역사적으로 이는 대부분 Redis 설계의 부작용으로 받아들여졌지만, 특정 사용 사례에서는 한계가 된다. DEL만이 블로킹 명령어는 아니지만 특별한 경우다. 우리는 보통 이렇게 말하니까 말이다. Redis는 O(1)이나 O(log_N) 명령어를 쓸 때 매우 빠르다. O(N) 명령어도 쓸 수는 있지만 우리가 최적화에 중점을 둔 경우가 아니라는 점을 알고 있어야 하며, 지연 시간 스파이크를 각오해야 한다.

이 말은 일리 있어 보이지만, 동시에 빠른 연산으로 생성된 객체라도 결국 삭제해야 한다. 그리고 이 경우 Redis는 블로킹된다.

첫 번째 시도

싱글 스레드 서버에서 연산을 논블로킹으로 만드는 쉬운 방법은 모든 것을 멈추는 대신 점진적으로 처리하는 것이다. 그래서 해제해야 할 할당이 100만 개라면, for() 루프 안에서 모든 걸 블로킹하는 대신 예를 들어 1밀리초마다 1,000개씩 해제할 수 있다. 쓰는 CPU 시간은 같거나 로직이 더 들어가서 조금 더 들지만, 사용자 관점의 지연 시간은 훨씬 낫다. 어쩌면 1밀리초당 1,000개를 해제하는 데 쓰인 그 사이클조차 원래는 유휴 상태였을지도 모른다. 핵심은 몇 초 동안 블로킹되는 걸 피하는 것이다. Redis 내부의 많은 기능이 이런 식으로 동작한다. LRU 제거와 키 만료가 대표적인 예지만, 해시 테이블의 점진적 리해싱처럼 다른 예도 많다.

그래서 내가 처음 시도한 것이 바로 이것이었다. 새로운 타이머 함수를 만들고 거기서 해제를 수행하는 것이다. 객체들은 그냥 연결 리스트에 큐잉해 두고, 타이머 함수가 호출될 때마다 천천히 점진적으로 회수되도록 했다. 이걸 잘 동작하게 하려면 몇 가지 트릭이 필요하다. 예를 들어 해시 테이블로 구현된 객체들은 Redis SCAN 명령어 내부에서 쓰는 것과 같은 메커니즘을 이용해 점진적으로 회수했다. 딕셔너리 내부에서 커서를 잡고 원소 하나하나를 해제하면서 순회하는 방식이다. 이렇게 하면 각 타이머 호출마다 해시 테이블 전체를 해제할 필요가 없다. 타이머 함수에 다시 진입했을 때 커서가 어디서 멈췄는지 알려준다.

적응형으로 만드는 일은 어렵다

이 방식에서 어려운 점이 뭔지 아는가? 이번에 우리가 점진적으로 하는 작업이 매우 특수하다는 것이다. 바로 메모리를 해제하는 일이다. 그래서 메모리를 점진적으로 해제하는 동안 서버 메모리가 매우 빠르게 증가하면, 지연 시간을 위해 결국 *무제한*의 메모리를 소비하게 될 수도 있다. 정말 좋지 않다. 예를 들어 이런 경우를 상상해 보자.

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

백그라운드에서 myset을 삭제하는 속도가 SADD 호출로 한 번에 엄청난 양의 원소를 추가하는 속도보다 느리다면, 메모리 사용량은 끝없이 커질 것이다.

하지만 몇 번의 실험 끝에 아주 잘 동작하는 방법을 찾았다. 타이머 함수는 메모리 압박에 적응하기 위해 두 가지 아이디어를 사용했다.

1. 메모리 추세를 확인한다. 증가하는지 감소하는지에 따라 얼마나 적극적으로 해제할지 조절한다.
2. “1”에 기반해 타이머 주기 자체도 조절한다. 해제할 게 별로 없을 때 이벤트 루프를 계속 방해하며 CPU 시간을 낭비하지 않기 위해서다. 동시에 정말 필요할 때는 타이머가 초당 약 300회까지 올라갈 수 있다.

이제 더 이상 존재하지 않는 함수에서, 이 아이디어를 구현했던 코드의 일부다.

/* 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 브랜치 작업을 시작했고, 트위터에 아무 맥락 없이 이에 대해 트윗을 올렸다. 그래서 다들 내가 절망했거나 미쳤다고 생각했다(몇몇은 결국 이 lazyfree가 도대체 뭔지 물어보기도 했다). 그래서 내가 한 일은 무엇인가?

1. 클라이언트 출력 버퍼를 robj 구조체 대신 단순 동적 문자열만 쓰도록 변경했다. 응답을 만들 때는 항상 값을 복사한다.
2. 모든 Redis 자료형을 공유된 robj 구조체 대신 SDS 문자열을 쓰도록 변환했다. 간단해 보인다고? 몇 주에 걸쳐 버그에 극도로 민감한 코드 약 800줄을 바꿨다. 하지만 이제 모든 테스트를 통과한다.
3. lazyfree를 스레드 방식으로 다시 작성했다.

결과적으로 Redis는 이제 메모리를 더 효율적으로 쓴다. 자료구조 구현에 robj 구조체가 더 이상 남아 있지 않기 때문이다(다만 명령어 디스패치나 리플리케이션처럼 공유가 많이 일어나는 코드 경로에서는 여전히 사용된다). 스레드 기반 lazy free는 아주 잘 동작하고 메모리 회수 속도도 점진적 방식보다 빠르다. 점진적 구현도 내가 아주 좋아하는 방식이었고 스레드 방식과 비교해도 그리 나쁘지 않았지만 말이다. 이제는 거대한 키를 삭제해도 성능 저하가 무시할 수준이라 매우 유용하다. 하지만 가장 흥미로운 점은, 지금까지 테스트한 모든 연산에서 Redis가 더 빨라졌다는 것이다. 인디렉션을 줄인 게 정말 결정적이었다. 클라이언트 출력 버퍼가 더 단순하고 빨라졌기 때문에 관련 없는 벤치마크에서도 더 빠르다. 결국 나는 이 브랜치에서 점진적 lazy freeing 구현을 삭제하고 스레드 방식만 남겼다.

API에 대한 참고

그런데 API는 어떻게 할까? 우리는 여전히 블로킹 DEL을 가지고 있다. 기본값은 그대로다. Redis에서 DEL은 지금 당장 메모리를 회수하라는 의미니까. 그걸 바꾸고 싶지 않았다. 그래서 이제 UNLINK라는 새로운 명령어가 생겼다. 값에 무슨 일이 일어나는지를 더 명확하게 드러내는 이름이다.

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

FLUSHALL / FLUSHDB의 논블로킹 변형도 구현됐지만, 아직 API 레벨에서는 아니다. LAZY 옵션을 주면 동작이 바뀌게 될 것이다.

단순한 지연 해제를 넘어

이제 집합 자료형 값들이 완전히 공유되지 않고, 클라이언트 출력 버퍼에도 공유 객체가 없으니 활용할 여지가 많다. 예를 들어 마침내 Redis에서 스레드 기반 I/O를 구현할 수 있게 됐다. 서로 다른 클라이언트를 서로 다른 스레드가 처리하는 방식이다. 즉, 데이터베이스에 접근할 때만 전역 락이 필요하고, 클라이언트의 read/write 시스템 콜이나 심지어 클라이언트가 보낸 명령어를 파싱하는 작업조차도 다른 스레드에서 일어날 수 있다. 이는 memcached와 비슷한 설계로, 구현하고 테스트해 보고 싶은 방식이다.

게다가 집합 자료형에 대한 특정 느린 연산을 다른 스레드에서 구현하는 것도 이제 가능해졌다. 소수의 키만 “블로킹”되고 다른 모든 클라이언트는 계속 진행할 수 있는 방식이다. 이는 현재 블로킹 연산에서 하는 것과 매우 비슷한 방식으로 달성할 수 있다(blocking.c 참조). 여기에 어떤 키가 현재 어떤 클라이언트에 의해 사용 중인지 저장하는 해시 테이블을 더하면 된다. 그래서 클라이언트가 SMEMBERS 같은 것을 요청하면 해당 키만 락을 걸고, 출력 버퍼를 만들며 요청을 처리한 뒤 다시 키를 해제하면 된다. 키가 블로킹된 동안에는 같은 키에 접근하려는 클라이언트만 블로킹된다.

이 모든 것은 훨씬 더 과감한 내부 변경을 필요로 하지만, 요점은 우리가 금기 하나를 없앴다는 것이다. 객체 복사 시간을 더 적은 캐시 미스와 집합 자료형의 더 작은 메모리 풋프린트로 상쇄할 수 있으니, 이제 우리는 공유하지 않는(share-nothing) 설계의 스레드 기반 Redis를 자유롭게 고민할 수 있다. 그 설계만이 싱글 스레드 방식을 쉽게 능가할 수 있다. 과거에는 자료구조와 객체에 뮤텍스를 걸어 동시 접근을 구현하는 방식으로 스레드 기반 Redis를 생각하면 항상 나쁜 아이디어로 여겨졌지만, 다행히 두 세계의 장점을 모두 취할 대안이 있다. 그리고 원한다면 여전히 빠른 연산들은 예전처럼 메인 스레드에서 처리하도록 할 수도 있다. 어느 정도 제한된 복잡성을 감수하면 성능 면에서는 이득만 있을 것이다.

예상 일정

나는 내부 구조를 많이 건드렸고, 이게 당장 내일 라이브로 나가는 코드는 아니다. 그래서 내 계획은 현재 unstable에 있는 것들을 3.2로 부르고, 이를 Release Candidate 상태로 만드는 작업을 한 뒤, 이 브랜치를 3.4를 목표로 unstable에 병합하는 것이다.

하지만 병합하기 전에, 속도 저하가 없는지 매우 꼼꼼하게 확인해야 한다. 분명히 해야 할 일이 더 남아 있다.

직접 시험해 보고 싶다면 GitHub에서 “lazyfree” 브랜치를 확인하면 된다. 참고로 지금 매우 활발하게 작업 중이라 특정 순간에는 완전히 망가져 있을 수도 있다.