TECH 으로 돌아가기
TECH HACKER NEWS 7분 읽기 48 READS

발키 9.2, 스킵리스트를 버리고 B+트리로: 정렬 집합 메모리 최대 43% 절감

인메모리 데이터 저장소에서 정렬 집합(sorted set)은 생각보다 비싼 자료구조다. 역설적이게도, 저장하려는 원소 자체보다 '그 원소들이 어떤 순서로 정렬되어 있는지'를 기술하는 데 더 많은 메모리를 쓰는 경우가 생긴다. 레디스 계열 저장소에서 갈라져 나온 발키(Valkey)는 다가오는 9.2 버전에서 이 문제를 정면으로 겨냥했다. 리스트팩 임계치를 넘어선 큰 정렬 집합을 떠받치던 스킵리스트(skiplist)를 걷어내고, 캐시 친화적으로 설계한 B+트리 변형인 'fbtree'로 교체한 것이다. 500만 멤버를 넣은 테스트에서 멤버당 부가 메모리를 36~43% 줄여 최대 109MB를 아꼈다는 것이 핵심 성과다.

스킵리스트가 비쌌던 이유

기존 구조는 멤버별 O(1) 조회를 위한 해시테이블과, 랭크·점수 기반 정렬 조회를 위한 O(log n) 스킵리스트를 짝지어 썼다. 구조는 단순하지만 스킵리스트는 노드마다 원소를 딱 하나씩 담고, 그 노드들이 포인터로 이어진 채 메모리 곳곳에 흩어진다. 발키의 스킵리스트는 노드마다 8바이트 뒤로가기 포인터, 평균 1.33레벨의 전방 포인터와 스팬 값(레벨당 포인터 8바이트+스팬 8바이트), 그리고 8바이트 점수를 합쳐 멤버 문자열을 빼고도 약 37바이트의 부가 비용을 치렀다.

문제는 메모리 양만이 아니다. 노드가 제각각 별도 할당으로 흩어져 있으면, 구조를 따라가는 각 단계가 서로 무관한 메모리 위치를 반복해서 읽어야 한다. 게다가 다음에 어디를 읽을지가 직전 결과에 달려 있어 이 접근들은 '의존적'이다. CPU의 L1 캐시 적중이 약 1나노초인 데 비해 DRAM 접근은 100나노초 안팎이라는 점을 떠올리면, 이런 의존적 캐시 미스가 쌓일수록 코어는 메모리를 기다리며 놀게 된다. 원문이 인용한 2025년 연구에서도 전통적 스킵리스트가 비교 대상 B-트리보다 캐시 미스가 약 2.4~4.8배 많고 처리량은 2~8배 낮았다(발키가 아닌 별도 구현 기준).

fbtree는 무엇을 바꿨나

fbtree는 'Feature B+ Tree'의 약자로, 한 노드에 최대 61개의 엔트리나 자식 포인터를 담는 61-way 팬아웃을 쓴다. 512바이트 리프 노드 하나에 61개 멤버가 함께 들어가므로, 멤버마다 별도 노드를 갖던 구조에 비해 포인터 부가 비용이 크게 줄어든다. 점수와 멤버를 따로 두지 않고 정규화된 8바이트 점수 뒤에 멤버 바이트를 붙여 하나의 패킹된 값으로 저장해, 비교에 필요한 데이터를 한곳에 모으고 포인터 간접 참조 단계를 하나 더 없앴다. 노드 크기는 jemalloc 할당 클래스에 맞춰 낭비 없이 설계했다.

스킵리스트의 25% 레벨 규칙은 사실상 분기 계수 4 정도에 그치지만 fbtree는 61이다. 둘 다 O(log n) 복잡도지만, 트리 쪽이 훑어야 할 레벨 수가 훨씬 적어 값비싼 메모리 접근 기회도 줄어든다. 여기에 연속된 메모리 배치와 하드웨어 프리페칭 덕분에 몇 개의 캐시 라인에 걸친 노드를 효율적으로 읽을 수 있다. fbtree는 추가로 특정 연산을 겨냥한 최적화를 얹었다. 내부 노드는 각 앵커(자식 안의 최대 멤버)와 함께 4바이트짜리 '피처'를 저장하고, 공유 접두사는 따로 빼낸 뒤 피처들을 SIMD로 병렬 비교해 자식 노드를 읽기도 전에 내려갈 방향을 찾는다. 리프 노드를 이중 연결 리스트로 묶어 ZRANGE 같은 범위 스캔이 트리를 되짚어 오르지 않고 리프에서 리프로 이동하게 했고, 양 끝 리프를 캐싱해 ZPOPMIN 같은 연산을 O(1)로 유지했다.

실무자가 확인할 지점

이 변경은 철저히 내부적이다. 정렬 집합 명령과 동작은 그대로이며, 눈에 띄는 유일한 차이는 큰 정렬 집합에 대해 OBJECT ENCODING이 skiplist 대신 btree를 반환한다는 점이다. 모니터링·테스트·도구가 'skiplist'라는 문자열을 직접 검사하고 있다면 그 부분을 손봐야 한다. 리스트팩 임계치 아래의 작은 정렬 집합은 애초에 스킵리스트를 쓰지 않았으므로 영향이 없다.

수치를 보면 500만 개의 20바이트 멤버를 순차 삽입했을 때 멤버당 부가 비용이 50.3바이트에서 28.5바이트로 43% 줄었고, 무작위 순서 삽입에서는 32.0바이트로 36% 줄었다. 무작위 삽입이 부분적으로만 찬 노드를 더 많이 남기기 때문에 절감폭이 작다. 주의할 점은 절감이 '바이트당'이 아니라 '멤버당'이라는 것이다. 즉 작은 멤버가 많은 집합일수록 전체 메모리 대비 절감 효과가 크고, 멤버 크기가 커질수록 상대적 이득은 줄어든다. 처리량 측면에서는 트리를 재배치하는 ZADD와 ZREM이 얕아진 구조와 적은 포인터 갱신의 이득을 가장 크게 받아 각각 105%, 76% 향상됐다. 반면 ZSCORE와 ZRANDMEMBER는 정렬 인덱스가 아니라 해시테이블을 쓰므로 거의 변화가 없었다. 해당 벤치마크는 Graviton3 c7g.metal(64코어)에서 300만 멤버 집합으로 측정됐으며, ZRANDMEMBER를 제외한 모든 명령의 신뢰구간은 2% 이내였다.

정리하면, 명령 인터페이스를 건드리지 않고 자료구조 계층만 교체해 메모리와 쓰기 처리량을 동시에 끌어올린, 전형적인 '보이지 않는 개선'이다. 다만 벤치마크가 병합 커밋이 아닌 특정 PR 브랜치에서 측정됐다는 점, 그리고 발키 9.2가 아직 릴리스 후보(RC) 단계라는 점은 감안해야 한다. 큰 정렬 집합이나 ZADD·ZREM·ZRANK·ZCOUNT가 서비스에 중요하다면, GA 전에 RC를 실제 워크로드로 돌려 보고 이상이 있으면 이슈로 남기는 것이 현명한 접근이다.

SOURCE · HACKER NEWS
원문 전체 보기 → https://valkey.io/blog/from-skiplist-to-b+tree/
SHARE
NEXT · CHOOSE

변화를 읽었다면,
내가 만들 수익 구조를 고릅니다.

정보를 더 모으는 데서 멈추지 않고, 광고·외주·판매·중개·구독 중 내 상황에 맞는 출발점을 정해보세요.

21가지 수익 구조 살펴보기 →
처리 중...