Valkey, 정렬 집합 메모리 오버헤드 43% 감축
원제 Valkey kills the skiplist, cuts sorted set overhead by up to 43%
122 포인트댓글 46
Key Point
대규모 정렬 집합을 많이 다루는 서비스라면 메모리 사용량 36~43% 절감과 주요 명령어 처리량 2배까지 향상되는 직접적 이득이 있으며, 기존 코드 호환성은 유지된다.
핵심 요약
- Valkey 9.2에서 정렬 집합(sorted set) 자료구조의 내부 구현을 스킵리스트에서 고팬아웃 B+ 트리 변종인 fbtree로 변경했다.
- 스킵리스트는 각 노드마다 역방향 포인터 8바이트와 평균 1.33개 레벨의 포인터·스팬 값(각 32바이트)을 저장해 노드당 약 37바이트 오버헤드를 발생시킨다.
- 스킵리스트의 분산된 메모리 배치와 의존성 있는 포인터 추종으로 인해 종래 B트리 대비 2.4~4.8배 더 많은 캐시 미스와 2~8배 낮은 처리량이 발생했다.
- fbtree는 61개 항목을 담을 수 있는 노드(512바이트 리프 노드)를 사용해 멤버 61개가 하나의 노드를 공유하며, 스코어와 멤버를 단일 압축 값으로 저장해 포인터 간접 참조를 제거한다.
- fbtree의 61배의 팬아웃은 스킵리스트의 약 4배 분기율과 비교해 같은 O(log n) 시간복잡도를 유지하면서 탐색 깊이와 메모리 페칭을 대폭 줄인다.
- inner 노드의 앵커에 4바이트 feature를 함께 저장해 SIMD로 병렬 비교하고, 리프 노드를 이중 연결 리스트로 연결해 범위 명령 시 트리를 타지 않고 순회 가능하다.
- 팬아웃 61의 B+ 트리는 메모리 접근 패턴 최적화와 하드웨어 프리페칭 덕분에 인접한 캐시 라인을 효율적으로 읽을 수 있다.
- ZPOPMIN 같은 끝 위치 작업을 위해 최좌측·최우측 리프를 캐시해 O(1) 성능을 유지한다.
- 500만 개 20바이트 멤버 순차 삽입 테스트에서 멤버당 오버헤드가 50.3바이트에서 28.5바이트로 43% 감소했고, 임의 삽입은 36% 감소(순차 삽입 시 약 109MB, 임의 삽입 시 약 92MB 절감).
- Graviton3 기반 테스트에서 ZADD는 105% 처리량 증가, ZREM은 76% 증가, ZCOUNT는 27% 증가를 기록했으나, ZSCORE와 ZRANDMEMBER는 해시 테이블 의존도가 높아 거의 변화 없었다.
- ZRANGE 등 범위 작업은 인덱스 탐색 비용이 감소한 뒤 결과 반환 비용이 더 커져 상대적으로 작은 성능 향상(1~6%)만 보였다.
- 명령어 동작과 반환 결과는 변하지 않으며, OBJECT ENCODING 반환값이 skiplist에서 btree로 바뀌는 것만 외적 차이다.
- 100만 명 이상 멤버를 가진 소규모 정렬 집합은 listpack 임계값 미만이므로 영향을 받지 않는다.