어제 Amplitude가 Set 자료형을 활용한 분석 시스템 확장에 관한 글을 게시했습니다. 해당 블로그 글은 여기에서 볼 수 있습니다: 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 개발자들은 단일 할당 배열로 리스트의 요소들을 표현하다가, 훨씬 메모리 효율이 떨어지는 실제 연결 리스트로 전환할 이유가 없다는 것을 깨달았습니다. 그 중간 지점에 해당하는 것이 있습니다. 바로 적은 수의 요소를 담는 배열들의 연결 리스트입니다. 다만 이들의 구현은 중간에서 요소를 삭제할 때 단편화를 처리하지 않았습니다. Pieter와 저는 과거에 이 방식이 가치가 있는지 파악하려 했지만, 단편화 해소에 드는 노력이 공간 절약으로 보상되지 않을 수 있다는 느낌이 있었고, 단편화를 처리하지 않는 구현은 Redis 리스트의 범용 구현으로는 너무 취약했습니다. 중간에서 요소 몇 개만 삭제해도 메모리 사용량이 크게 달라지기 때문입니다.

다행히 Matt Stancliff가 단편화 처리 부분을 포함해 이 아이디어를 훌륭하게 구현했고, 실험을 통해 새로운 구현이 성능 측면에서는 기존 Redis 구현과 적어도 동등하고, 메모리 사용량 측면에서는 훨씬 더 우수하다는 것을 보여주었습니다. 게다가 리스트의 메모리 효율은 더 이상 리스트 크기에 따라 달라지지 않았고, 다룰 표현 방식도 하나로 통일되었습니다.

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

Redis Set

Set의 메모리 사용량은 조금 특별합니다. 다른 모든 Redis 자료구조와 달리, 문자열로 구성된 Set을 위한 특수한 표현이 없습니다. 그래서 아주 작은 Set이라도 많은 메모리를 소비하게 됩니다. 특수한 표현이 실제로 존재하긴 하고 매우 훌륭하지만, Set이 숫자로만 이루어지고 크기가 작을 때만 동작합니다. 이 경우 “intset”이라는 특수 인코딩으로 Set을 표현하는데, 이는 정렬된 정수 선형 배열이므로 멤버 존재 여부를 이진 탐색으로 확인할 수 있습니다. 배열은 집합 내 가장 큰 요소에 따라 각 요소의 크기를 자동으로 바꾸므로, 1, 20, 30, 15라는 문자열을 가진 집합을 표현하는 데는 요소당 1바이트와 약간의 오버헤드만 듭니다. 문자열을 숫자로 표현할 수 있고 8비트 범위에 들어가기 때문입니다. 하지만 “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개의 요소를 담은 작은 집합체를 스캔하면서 잃는 부분은 더 나은 캐시 지역성 덕분에 다시 만회할 수 있으므로, 겉보기에 치명적인 시간/공간 트레이드오프처럼 보이는 것들도 실제로는 그렇지 않을 수 있으며 실험해 볼 여지가 있습니다.

Redis 해시 테이블 특화하기

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

이것이 범용 해시 테이블을 설계하려는 방식입니다. 곳곳에서 값을 처리하기 위한 포인터와 메서드(함수 포인터)를 사용하는 방식입니다. 하지만 Redis 자료구조에는 흥미로운 특성이 있습니다. 복잡한 자료구조의 모든 요소는 의미론적으로 항상 문자열이라는 점입니다. 해시는 문자열 필드와 문자열 값 사이의 맵이고, 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 딕셔너리를 저장하는 데에도 사용되어 각 키의 오버헤드를 훨씬 더 작게 만들 수 있습니다.