Huny's Dev Blog
huny.dev

Valkey 9.2 Sorted Set 아키텍처 해부: Skiplist에서 61-way fbtree(B+ Tree) 전환으로 멤버당 오버헤드 43% 절감·ZADD +105% 달성 원리와 동작 경계 점검하기

2026년 11월 19일 정식 출시된 Valkey 9.2의 대형 Sorted Set 내부 인덱스 교체(Skiplist → 61-way fbtree)를 해부한다. 8바이트 정규화 스코어 패킹·4바이트 Feature SIMD 탐색·512B 이중 연결 리프·jemalloc 클래스 정렬로 멤버당 오버헤드를 50.3B에서 28.5B(순차)/32.0B(무작위)로 줄이고 ZADD +105%·ZREM +76%를 달성한 원리와, OBJECT ENCODING(btree) 전환 경계를 검증한 로컬 Python 스크립트를 정리한다.

Hun Jang
Hun Jang Nov 22, 2026

Valkey 9.2 Sorted Set 인덱스 교체 추상 표지 아트워크: 힙 곳곳에 흩어진 포인터 체이싱(Skiplist) 노드에서 61-way 고분기·이중 연결 리프·캐시 친화적 B+ 트리(fbtree) 구조로 전환되는 아키텍처를 표현한 기하학 그래픽

2026년 11월 19일 정식 출시(GA)된 Valkey 9.2의 핵심 내부 변화는 대형 Sorted Set의 정렬 인덱스를 기존 확률적 Skiplist에서 61-way 고분기 B+ 트리 변형인 fbtree(Feature B+ Tree)로 교체하여, 응용 코드나 명령 동작을 전혀 바꾸지 않고도 500만 멤버 기준 멤버당 인덱스 메모리 오버헤드를 36~43%(50.3B → 28.5B/32.0B) 줄이고 ZADD·ZREM 처리량을 각각 105%·76% 끌어올린 점이다.

Redis와 Valkey 생태계에서 Sorted Set(ZSET)은 listpack 임계값을 넘기는 순간부터 해시 테이블(Hash Table)과 스킵리스트(Skiplist)를 나란히 유지해 왔다. 해시 테이블이 ZSCORE 같은 멤버 단건 조회를 O(1)로 처리한다면, 스킵리스트는 스코어와 순위 기반 범위 탐색(ZRANGE, ZRANK, ZCOUNT)을 O(log N)으로 담당했다. 그러나 Valkey 코어 개발팀(Rain Valentine, Dragos Andriciuc)이 2026년 11월 16일 공개한 기술 심층 분석(From Skiplists to B+ Trees: Making Valkey Sorted Sets More Memory Efficient)과 11월 19일 출시된 Valkey 9.2는 오랫동안 당연시되던 이 스킵리스트 구조를 완전히 걷어 내고 캐시·할당자 친화적인 fbtree를 도입했다.

이 글은 확인 기준일 November 22, 2026 시점의 Valkey 공식 fbtree 기술 아티클(2026-11-16), Valkey 9.2 릴리스 페이지(2026-11-19), Valkey 9.1 메모리 최적화 블로그(2026-08-13)를 교차 검증해 정리했다. 원격 프로덕션 클러스터나 AWS Graviton3(c7g.metal) C 바이너리 벤치마크를 직접 재실행하지는 않았으며, 공개된 fbtree 설계 명세(8바이트 정규화 스코어 패킹·61-way 분기·이중 연결 리프·4바이트 Feature 접두사 분리·listpack → btree 인코딩 전환)를 바탕으로 로컬 Python 검증 스크립트(verify_valkey_fbtree_zset.py)를 작성해 불변량과 경계 조건을 직접 검증한 결과를 함께 다룬다.

1. 흔한 오해와 핵심 설계 경계 3가지

fbtree 전환을 단순히 "정렬 자료구조만 바꾼 미세 튜닝"으로 이해하면 메모리 절감 폭과 운영 호환성 판단을 그르치기 쉽다. 도입 전 반드시 짚어야 할 경계는 세 가지다.

  1. 소형 Sorted Set(listpack)과 해시 테이블(Hash Table)은 그대로 유지된다: fbtree가 대체하는 대상은 listpack 임계값(기본 zset-max-listpack-entries 128, zset-max-listpack-value 64)을 초과한 대형 Sorted Set의 정렬 인덱스뿐이다. 멤버로 스코어를 찾는 O(1) 해시 테이블과 소형 키용 listpack 인코딩은 기존과 동일하다. 따라서 공식 벤치마크에서 ZSCORE(+2%)나 ZRANDMEMBER(+2%)처럼 해시 테이블 경로를 타는 명령은 변화 폭이 미미하며, 수백만 개 이상의 작은 멤버가 들어 있는 대형 ZSET에서 절감 효과가 극대화된다.
  1. 스킵리스트의 병목은 시간 복잡도가 아니라 '힙 분산 할당 + ~37~50.3B 포인터 세금'이다: 스킵리스트와 B+ 트리 모두 이론적 탐색 복잡도는 O(log N)이지만, 하드웨어 캐시 계층(L1 히트 ~1ns vs DRAM 접근 ~100ns)에서는 전혀 다른 비용을 치른다. 기존 스킵리스트는 노드 1개마다 별도 힙 할당을 일으키며, 뒤 포인터(8B)와 평균 1.33레벨(레벨 승격 확률 25%)의 앞 포인터(8B) 및 span(8B)이 합쳐져 순수 포인터·스팬 오버헤드만 약 29B, 8B 스코어를 더하면 멤버 문자열을 빼고도 노드당 약 37B(실측 할당자·레이아웃 포함 50.3B)를 소모했다. 반면 유효 분기 계수(branching factor)는 약 4에 불과해, 500만 개 원소 기준 평균 ~11.1번의 의존적 메모리 추적(이전 노드를 읽어야 다음 주소를 아는 직렬 DRAM 대기)이 발생했다.
  1. 기능은 100% 동일하지만 OBJECT ENCODING 출력 문자열은 skiplist에서 btree로 바뀐다: ZADD, ZREM, ZRANGE, ZRANK, ZPOPMIN 등 모든 Sorted Set 명령 의미와 동점자 사전식 정렬 규약은 바뀌지 않는다. 단, 운영 모니터링 스크립트나 통합 테스트 코드가 대형 Sorted Set에 대해 OBJECT ENCODING key의 반환값이 정확히 "skiplist"인지 단언(assert)하고 있다면 Valkey 9.2 업그레이드 전 "btree"를 허용하도록 수정해야 한다.

2. Skiplist vs fbtree 구조 도식 및 벤치마크 비교 표

Valkey 9.2 Sorted Set 인덱스 개편 도식: 왼쪽 Valkey ≤ 9.1의 힙 분산 Skiplist(4-way, 노드당 50.3B 오버헤드)와 오른쪽 Valkey 9.2의 61-way fbtree(4B Feature SIMD 탐색, 512B 이중 연결 리프, 8B 정규화 스코어+멤버 패킹, 멤버당 28.5B/32.0B 오버헤드) 비교

Valkey 공식 블로그가 공개한 500만 개 20바이트 멤버 메모리 시험과 Graviton3(c7g.metal, 64코어, 9 I/O 스레드, 파이프라인 깊이 10, 300만 멤버 ZSET, PR #4206 기준) 명령 처리량 측정치를 구조별로 정리하면 다음과 같다.

비교 항목
Valkey ≤ 9.1 (Hash Table + Skiplist)
Valkey 9.2 (Hash Table + fbtree)
인덱스 자료구조 / 분기 수
확률적 Skiplist (레벨당 25% 승격 → 유효 분기 약 4-way)
Feature B+ Tree (61-way 고분기; 5M 기준 깊이 4단계)
메모리 배치 및 할당자 적합성
원소 1개마다 개별 힙 할당 · backward(8B) • level[] ptr/span(~21B) • score(8B) • ele ptr
512B 리프 노드에 최대 61개 포인터 집적 · 64비트 빌드 기준 jemalloc 클래스 무손실 정렬 (32비트 innerNode는 1280B 클래스)
스코어·멤버 저장 및 비교 방식
스코어(double)와 멤버 문자열 포인터 분리 → 비교 시 추가 역참조
[정규화 8B 스코어 + 멤버 바이트] 단일 패킹 값 + Inner Node 공통 접두사 분리 & 4B Feature SIMD 병렬 탐색
범위 스캔(ZRANGE) · 끝단 팝(ZPOPMIN)
다음 노드를 읽어야 다음 주소를 아는 직렬 포인터 추적 · 헤드/테일 O(1)
이중 연결 리프로 61개 단위 처리 + 다음 리프 프리패치 · 좌·우 끝단 리프 캐시로 O(1) 유지
5M × 20B 멤버당 인덱스 오버헤드
(멤버 본문 제외)
50.3 B / 멤버
순차 삽입 28.5 B (-43%, 약 109 MB 절감)
무작위 삽입 32.0 B (-36%, 약 92 MB 절감)
주요 명령 처리량 변화
(Graviton3 3M ZSET)
기준선 (Baseline)
ZADD(업데이트) +105% · ZREM(50/50) +76% · ZCOUNT +27% · ZRANK +19% · ZRANGE +6% · ZPOPMIN ~0%
OBJECT ENCODING 반환값
skiplist (소형은 listpack)
btree (소형은 listpack 유지)

3. fbtree가 캐시 미스와 포인터 오버헤드를 줄이는 4가지 메커니즘

3.1 61-way 고분기와 jemalloc 할당자 클래스 정렬

스킵리스트가 원소 하나마다 독립된 힙 블록을 쪼개 할당하는 것과 달리, fbtree는 512바이트 리프 노드 하나에 최대 61개의 값 포인터를 촘촘히 담는다. 내부 노드(innerNode) 역시 64비트 빌드 기준 jemalloc 할당 크기 클래스에 딱 맞게 설계해 내부 단편화 낭비를 없앴다(지원되는 32비트 빌드에서는 1280바이트 클래스로 올림 정렬). 분기 수가 4에서 61로 커지면 500만 개 원소를 기준으로도 트리 높이가 4단계(61³ = 226,981, 61⁴ = 13,845,841)로 납작해지며, 노드 하나가 연속된 몇 개의 CPU 캐시 라인 안에 들어오기 때문에 하드웨어 프리패처가 다음 포인터들을 한꺼번에 끌어올 수 있다.

3.2 정규화 8바이트 스코어 패킹으로 이중 역참조 제거

기존에는 노드 안에 double 스코어와 멤버 문자열 포인터를 따로 두었기 때문에 정렬 비교를 할 때마다 추가 메모리 접근이 뒤따랐다. fbtree는 스코어와 멤버를 따로 두지 않고 정규화된 8바이트 스코어 뒤에 멤버 바이트를 바로 붙인 단일 패킹 값(packed value)으로 저장한다. IEEE-754 부동소수점은 그대로 바이트 비교(memcmp)를 하면 음수 비트 순서와 부호 비트가 어긋나므로, 양수는 부호 비트를 반전하고 음수는 전체 비트를 반전하며 -0.0과 +0.0을 정규화하는 변환을 거친 뒤, 스코어와 동점 시 멤버 바이트 순서를 단 한 번의 연속 바이트 비교로 판정한다.

3.3 공통 접두사 분리 + 4바이트 Feature SIMD 병렬 탐색

가변 길이 문자열이 들어가는 B+ 트리에서는 내부 노드가 자식 서브트리의 최댓값(anchor)을 비교하는 과정 자체가 문자열 역참조 비용을 유발한다. 게다가 실무 키·멤버(session:prod:eu-west:... 등)는 앞부분 접두사가 길게 겹치는 경우가 많다. fbtree 내부 노드는 앵커들의 공통 접두사를 따로 떼어 저장한 뒤, 갈라지는 지점의 4바이트 Feature만 떼어 자식 포인터와 함께 배치하고 이를 SIMD 명령으로 병렬 비교한다. 4바이트 Feature만으로 자식이 유일하게 특정되면 자식 노드를 읽기도 전에 즉시 내려갈 경로를 확정할 수 있고, 겹치더라도 이진 탐색 범위를 극소수로 좁힐 수 있다.

3.4 이중 연결 리프·끝단 리프 캐시·범위 삭제 최적화

B+ 트리가 범위 스캔과 우선순위 큐 워크로드에서 스킵리스트보다 느려지지 않게 하려면 순차 스캔과 양끝 원소 접근을 보완해야 한다. fbtree는 모든 리프 노드를 이중 연결 리스트(doubly-linked list)로 이어 ZRANGE가 트리를 다시 올라가지 않고 리프에서 다음 리프로 직행하게 하며, 현재 리프의 61개 항목을 처리하는 동안 다음 리프 노드를 미리 가져올 수 있게 한다. 동시에 가장 왼쪽·오른쪽 리프 포인터를 캐시해 ZPOPMIN이나 끝단 추가가 O(log N)이 아닌 O(1)로 동작하도록 보장하며, 연속 구간 삭제도 주변 트리를 통째로 재구성하지 않고 처리한다.

4. 로컬 Python 검증 스크립트 작성 및 불변량 확인

원격 Valkey 9.2 클러스터에 접속하지 않고도 fbtree의 핵심 계약(IEEE-754 8바이트 스코어 정규화, 61-way B+ 트리 연산 동치성, 4바이트 Feature 분리 및 깊이·메모리 산식)을 재현·검증하기 위해 로컬 Python 검증 스크립트(verify_valkey_fbtree_zset.py)를 작성해 실행했다.

로컬 환경에서 python C:/Users/admin/.gemini/antigravity/scratch/verify_valkey_fbtree_zset.py를 실행해 3가지 검증 시나리오를 점검한 결과는 다음과 같다.

  • 8바이트 IEEE-754 스코어 정규화 및 동점자 타이브레이킹 (Check 1): -inf, -1e12, -42.75, -0.0, 0.0, 0.5, +inf에 대해 -0.0과 +0.0이 동일한 8바이트 표현으로 정규화되고, 전체 구간이 바이트 단위 비교만으로 엄격 단조 증가하며, 동일 스코어(10.0)에서 멤버 바이트(b"alpha" < b"beta") 순으로 정렬되고 NaN은 예외로 차단됨을 확인했다.
  • 61-way fbtree 연산 동치성 및 구조 불변량 (Check 2): 초기 750건 적재 후 무작위 ZADD(신규 삽입·스코어 갱신), ZREM, ZPOPMIN, ZRANK, ZRANGE, ZCOUNT 혼합 2,000회(총 2,750연산, 최종 크기 461건)를 수행한 결과, 모든 반환값이 참조 Sorted Set 오라클과 100% 일치했으며 이중 연결 리프 순회 결과와 모든 내부 노드의 child_counts 합계·최대 분기 수(<= 61) 불변량이 손상 없이 유지됐다.
  • 트리 깊이·메모리 절감 산식·4B Feature 분리·인코딩 경계 (Check 3): 500만 원소 기준 유효 분기 4의 스킵리스트 평균 깊이(log₄(5M) ≈ 11.13 홉) 대비 61-way fbtree가 4단계로 줄어드는 것과 50.3B → 28.5B/32.0B의 절감률(43.3% / 36.4%, 약 109MB / 92MB)을 확인했다. 또한 21바이트 공통 접두사를 공유하는 3개 앵커에서 4바이트 Feature([b'eu-w', b'us-e', b'ap-n'])가 자식을 유일하게 분리함과 listpack(≤128, ≤64B) → btree 전환 경계를 확인해 ALL CHECKS PASSED (3/3 checks passed)로 종료됐다.

5. Valkey 9.2 업그레이드 및 실무 도입 체크리스트

대규모 랭킹 보드, 지연 작업 큐(ZPOPMIN/ZRANGEBYSCORE), 속도 제한기(sliding window), 시계열 인덱스로 Sorted Set을 대량 운영하는 팀은 Valkey 9.2 도입 시 아래 항목을 점검해야 한다.

  • OBJECT ENCODING 리터럴 검사 코드 점검: 운영 대시보드, 헬스체크, 단위·통합 테스트에서 대형 Sorted Set의 인코딩을 "skiplist" 문자열과 직접 비교하는 코드가 있다면 "btree"로(또는 skiplist/btree 동시 허용으로) 수정했는가?
  • 할당 메모리 절감 타깃 식별: fbtree의 절감액은 바이트 비례가 아니라 멤버 개수 비례(5M 멤버당 ~92–109 MB)이므로, 원소 수가 적은 대형 문자열 셋이 아니라 수십만~수천만 개의 짧은 멤버(10~64B)를 저장하는 ZSET 키에서 우선적으로 메모리·ZADD/ZREM 개선 효과를 측정할 계획인가?
  • AOF/RDB 압축 및 다운그레이드 호환성 사전 확인: Valkey 9.2는 fbtree 외에도 포크 없는 RDB 스냅샷(forkless-infrastructure-enabled)과 복제·백업 스트림 LZ4/Zstandard 압축, PH*(Path Hash) 타입을 함께 도입했다. 만약 9.2에서 9.1 이하로 롤백할 가능성이 있다면 rdbcompression을 기존 모드로 되돌리고 BGREWRITEAOF를 선행하는 절차를 런북에 반영했는가?
  • 워크로드별 사전 스테이징 검증: 실제 프로덕션 RDB 스냅샷을 Valkey 9.2 스테이징 노드에 올려 INFO memory, OBJECT ENCODING, ZADD/ZREM/ZRANGE P99 지연 시간 변화를 사전 계측했는가?

참고 자료 (References, 2026-11-22 확인)

확인 기준일: November 22, 2026

추천 글