어제 Amplitude는 Set 데이터 타입을 활용하는 맥락에서 분석(analytics) 스케일링에 관한 글을 게시했다. 해당 블로그 포스트는 여기에서 확인할 수 있다: https://amplitude.com/blog/2015/08/25/scaling-analytics-at-amplitude/

Hacker News에서는 왜 그 대신 Redis를 사용하지 않느냐는 질문이 올라왔다: https://news.ycombinator.com/item?id=10118413

Amplitude 개발자들은 Redis를 사용하지 않는 나름의 이유를 가지고 있다. 그리고 일반적으로 매우 특수한 문제를 가능한 가장 좋은 방식으로 스케일링하고 싶다면, 수직적인 자체 솔루션을 구현하는 것이 합리적이다. 나는 바퀴를 재발명하는 것에 반대하지 않는다. 때로는 범용 시스템이 제공할 수 없는, 매우 특수한 바퀴가 필요할 때가 있다. 게다가 직접 솔루션을 만들면 자신이 만든 것에 대한 통제권을 갖게 되고, 창의성과 개발자로서 할 수 있다는 자신감이 높아지며, 앞으로 발생할 어떤 버그든 외부 도움 없이 디버깅할 수 있게 된다.

반면에 물론 시스템 소프트웨어를 처음부터 만드는 것은 매우 복잡한 일이며, 무언가를 적극적으로 개발하고 싶다면 지속적인 개발이 필요하고, 전담 팀이 없다면 멈춰버린, 진화하지 않는 코드 덩어리가 되기 마련이다. 매우 수직적이고 전문화된 경우라면, 새로 만든 시스템은 전체 애플리케이션 문제가 가진 일부만을 처리할 수 있을 가능성이 높으면서도, 여전히 추가 컴포넌트로서 관리해야 한다. 게다가 대부분 한 명 혹은 소수의 프로그래머가 만들었는데 그들이 나중에 회사를 떠나면, 그것을 수정하고 발전시키는 것은 매우 큰 문제가 된다. 규모 있는 외부 커뮤니티도 없고, 원래 개발자도 없기 때문이다.

기본적으로 사내에서 직접 만드는 것이 그 자체로 좋거나 나쁜 것은 아니며, 경우에 따라 다르다. 물론 언제 처음부터 구현할 가치가 있고 언제 그렇지 않은지를 판단하는 것은 감각의 문제다. 훌륭한 개발자라면 안다.

내 관점에서는 Amplitude 개발자들의 최종 솔루션이 무엇이었든 간에, 그 과정과 그들이 Redis를 사용하지 않는 이유를 읽어보는 것이 흥미롭다. 그들이 제기한 우려 중 하나는 Redis의 Set 데이터 타입 오버헤드였다. 나는 그런 우려를 갖는 것이 타당하다고 생각한다. Redis Set은 훨씬 더 메모리 효율적으로 만들 수 있으며, Amplitude 글을 읽기 몇 주 전부터 이미 Set의 메모리 효율을 개선할 방법을 탐색하기 시작했다. 오늘 그 계획을 여러분과 공유하고자 한다.

데이터 타입의 이중 표현

원칙적으로는 평범한 자료구조가 있었고, 알고리즘 교과서가 제안하는 방식대로 다소간 구현되어 있었다. 자료구조의 각 노드를 동적으로 할당하는 방식이었다. 할당 오버헤드, 뚱뚱한 포인터, 낮은 캐시 지역성이 이 기본적인 해결책의 큰 한계였다.

Pieter Noordhuis와 나는 이후 Redis 추상 데이터 타입의 특화된 구현을 만들었는데, 하나의 할당에 수십 개에서 수백 개의 요소를 담는 단일 할당을 사용하고, 때로는 공간을 더 잘 활용하기 위해 ad-hoc 인코딩을 적용해 매우 메모리 효율적으로 만들었다. 이러한 자료구조 버전들은 특정 연산에 대해 O(N) 시간 복잡도를 가지거나, 때로는 특정 형식(숫자)이나 크기를 가진 요소로 제한되기도 한다.

예를 들어 Hash를 생성하면, 적은 수의 요소에 적합한 메모리 효율적인 방식으로 표현되기 시작한다. 이후 요소 수가 특정 임계값에 도달하면 실제 해시 테이블로 변환된다. 즉, Redis 데이터 타입의 메모리 효율은 저장하는 요소 수에 크게 좌우된다는 뜻이다.

다음 단계: Redis 리스트

어느 시점에 Twitter 개발자들은 List의 아이템을 나타내는 단일 할당 내 요소 배열에서, 메모리 효율이 훨씬 떨어지는 실제 연결 리스트로 전환할 이유가 없다는 것을 깨달았다. 중간 어딘가에 해답이 있었다. 바로 몇 개의 아이템을 담는 배열들의 연결 리스트였다. 그들의 구현은 중간에서 무언가를 제거했을 때 단편화를 처리하지 않는다. Pieter와 나는 과거에 이 방식이 가치가 있는지 파악해보려 했지만, 단편화 해소에 드는 노력이 공간 절약으로 보상받지 못할 수도 있다는 느낌이 있었고, 단편화를 처리하지 않는 이 아이디어의 구현은 Redis 리스트의 범용 구현으로는 너무 취약했다. 중간에서 몇 개 요소만 제거해도 메모리 사용량이 극적으로 달라지기 때문이다.

다행히 Matt Stancliff가 단편화 처리를 포함해 이 아이디어를 훌륭하게 구현했고, 몇 차례 실험 끝에 새로운 구현이 성능 관점에서는 Redis의 기존 구현과 적어도 동등하고 메모리 사용량 관점에서는 훨씬 더 낫다는 것을 보여주었다. 게다가 리스트의 메모리 효율은 더 이상 리스트 크기의 함수가 아니었고, 다뤄야 할 표현 방식도 하나로 통일됐다.

리스트는 다소 특별한데, 작은 배열들의 연결 리스트를 갖는 것이 다른 데이터 타입에는 쉽게 적용되지 않을 수 있는 정말 최적의 표현이기 때문이다. Set이나 다른 데이터 타입에도 비슷한 것을 할 수 있을까?

Redis Set

Set의 메모리 사용량은 조금 특별하다. 다른 모든 Redis 자료구조와 달리 문자열로 구성된 Set을 위한 특화된 표현이 없다. 그래서 아주 작은 Set이라도 많은 메모리를 소비하게 된다. 특화된 표현 자체는 실제로 존재하며 훌륭하지만, Set이 숫자로만 구성되고 크기가 작을 때만 동작한다. 그런 경우 우리는 “intset”이라는 특수 인코딩으로 Set을 표현한다. 이는 정렬된 정수 선형 배열로, 멤버 존재 여부를 이진 탐색으로 확인할 수 있다. 배열은 Set 내 가장 큰 요소에 따라 각 요소의 크기를 자동으로 바꾸므로, 1, 20, 30, 15라는 문자열을 가진 Set을 표현하는 데는 요소당 1바이트와 약간의 오버헤드만으로 충분하다. 문자열을 숫자로 표현할 수 있고 8비트 범위 안에 들어가기 때문이다. 하지만 Set에 “a” 하나만 추가해도 전체 해시 테이블로 변환된다:

127.0.0.1:6379> sadd myset 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding myset
"intset"
127.0.0.1:6379> sadd myset a
(integer) 1
127.0.0.1:6379> object encoding myset
"hashtable"

정수 Set은 Redis에서 매우 많이 사용되는 데이터 타입이므로, 이런 기능이 있는 것은 실제로 매우 유용하다. 하지만 왜 다른 모든 경우에 있는 것처럼 숫자가 아닌 문자열로 구성된 작은 Set을 위한 특화된 표현은 없을까? 사실 세 가지 표현을 가진 데이터 타입을 갖는 것이 Redis 내부 관점에서 좋은 일이 아닐 것이라는 생각 때문이었다. t_zset.c나 t_set.c를 보면 여러 표현을 다루는 데 일정한 주의가 필요하다는 것을 알 수 있다. N개의 표현을 다루는 일을 추상화하려 하면 할수록 특정 최적화에 접근할 수 없게 된다. 게다가 리스트 사례는 모든 장점을 가진 단일 표현을 가질 수 있다는 것을 보여주었다. N개의 요소를 담은 작은 집합(aggregate)을 스캔하면서 잃는 것은 더 나은 캐시 지역성 덕분에 만회할 수 있으므로, 비극적인 시간/공간 트레이드오프처럼 보이는 것들을 실험해 보는 것이 가능하며, 실제로는 그렇지 않다.

Redis 해시 테이블 특화하기

큰 Hash, 숫자가 아닌(혹은 큰) Set, 그리고 큰 Sorted Set은 현재 해시 테이블로 표현된다. 구현은 dict.c 파일 안에 있는 것이다. 체이닝으로 충돌을 해결하는 꽤 단순한 방식으로 구현된 해시 테이블이다. 이 해시 테이블 구현의 특별한 점은 단 두 가지뿐이다. 리해싱을 위해 절대 블로킹하지 않으며, 리해싱 과정이 점진적으로 처리된다는 것이다. 나는 VMware 후원을 받던 첫 몇 달 동안 이 작업을 했고, 물론 지연 시간 측면에서 큰 성과였다. dict.c는 또한 Pieter Noordhuis가 고안한 “scanning”이라는 특수 원시 연산도 구현하는데, 이는 오버헤드나 상태 없이도 합리적인 보장을 제공하는 커서 기반 이터레이터다. 그 외에 Redis 해시 테이블은 키와 값이 무언가를 가리키는 포인터일 것으로 기대하고, 키를 비교하고 해제하며 값을 해제하기 위한 메서드를 필요로 한다.

이것이 범용 해시 테이블을 설계하고 싶은 방식이다. 값을 다루기 위해 어디서나 포인터와 메서드(함수 포인터)를 사용하는 것이다. 하지만 Redis 자료구조에는 흥미로운 특성이 있다. 복잡한 자료구조의 모든 요소는 의미상 항상 문자열이라는 점이다. Hash는 문자열 필드와 문자열 값 사이의 맵이며, Set은 문자열의 비순서 집합이고, 그 마찬가지다.

문자열 키와 문자열 값만을 저장하도록 설계된 해시 테이블을 구현하면 어떻게 될까? 글쎄… 그런 해시 테이블을 매우 메모리 효율적으로 만들 수 있는 간단한 방법이 있는 것처럼 보인다. 로드 팩터를 1보다 큰 값, 예를 들어 10으로 설정할 수 있고, 해시 테이블에 버킷이 5개 있다면 각 버킷은 평균적으로 10개의 요소를 담게 될 것이다.

그러면 각 버킷은 현재 작은 데이터 타입에 사용하는 인코딩과 매우 유사한 방식으로, 길이가 앞에 붙은 키-값 아이템들의 선형 배열 같은 형태가 될 것이다. 예를 들면 다음과 같다:

0: <3>foo<3>bar<5>hello<6>world!<0>
1: <8>user:103<3>811 … <0>
2: … <0>

등등이다. 인코딩은 특화될 수도 있고 그냥 MessagePack 같은 기존의 것을 사용할 수도 있다. 따라서 각 버킷에서 하는 추가 작업은 얻게 되는 더 나은 지역성 덕분에 충분히 보상될 수 있다.

이 자료구조 위에 스캐닝과 점진적 리해싱을 구현하는 것도 가능하다. 나는 초기 분석을 해봤고, dict.c의 구현을 그대로 복사할 수는 없지만 동일한 효과를 얻는 다른 방법을 찾는 것은 가능하다.

참고로, 기술적으로 말하면 그런 해시 테이블에 포인터를 저장하는 것도 가능하다. 해시 테이블 구현의 관점에서는 그냥 문자열일 뿐이며, 해시 테이블 타입에서 그것들이 특별한 처리가 필요한 포인터라는 것을 알릴 수 있다(예를 들어 값을 해제하는 함수 포인터 등). 하지만 그것이 가치가 있는지는 테스트만이 말해줄 수 있다.

하지만 이를 Set 이상에 사용하거나, 적어도 현재 가지고 있는 작은 표현들을 없애고 *오직* 그런 표현만을 사용하려면 해결해야 할 문제들이 있다. 예를 들어, 현재의 작은 표현들은 매우 흥미로운 특성을 가지고 있다. 별도의 작업 없이 그 자체로 이미 직렬화된 형태라는 것이다. 우리는 이를 RDB 파일에 데이터를 저장하거나 Redis Cluster에서 노드 간에 데이터를 전송하는 데 사용한다. 특화된 해시 테이블도 가능하면 동일한 특성을 가져야 하며, 적어도 각 버킷 하나하나는 별도의 후처리 작업 없이 이미 직렬화된 형식이어야 한다. 그렇지 않다면, 이 새로운 딕셔너리는 확장 이후에만 범용 해시 테이블을 대신해 사용할 수 있는데, 그것만으로도 이미 큰 성과다.

결론

이것은 설계를 개선하고, 나중에 구현으로 검증하며, 특정한 정당한 워크로드에서 큰 성능 저하가 없음을 보장하기 위해 심도 있는 부하 테스트를 거치는 데 어느 정도 시간이 필요한 초기 아이디어다. 모든 것이 잘 진행된다면 과거보다 훨씬 더 메모리 효율적인 Redis 서버로 귀결될 수 있다. 이러한 해시 테이블은 각 키의 오버헤드를 훨씬 더 작게 만들기 위해 메인 Redis 딕셔너리를 저장하는 데도 사용될 수 있다.