스킵리스트는 언제 써야 할까? 이론과 실전 사이의 간극

스킵리스트, 이름은 들어봤는데

Antithesis라는 결정론적 테스팅 회사의 블로그에서 "What are skiplists good for?"라는 글을 올렸어요. 스킵리스트(skiplist)라는 자료구조를 한 번쯤 들어보셨을 거예요. 알고리즘 책에서는 꽤 유명한 친구인데, 막상 실무에서 "저 스킵리스트 써봤어요" 하는 사람은 많지 않죠. 이 글은 그 간극에 대한 솔직한 이야기예요.

스킵리스트는 1989년 William Pugh가 발표한 자료구조로, 정렬된 데이터를 관리하는 데 쓰여요. 특징은 확률적 균형(probabilistic balancing) 이에요. 레드블랙 트리나 AVL 트리 같은 전통적인 균형 트리가 복잡한 회전 연산으로 균형을 맞추는 반면, 스킵리스트는 각 노드의 "층수"를 동전 던지기로 정해서 평균적으로 O(log n) 성능을 보장해요.

스킵리스트는 어떻게 동작하나

이게 뭐냐면, 정렬된 연결 리스트 여러 개를 층층이 쌓아놓은 구조예요. 맨 아래층은 모든 원소가 있는 보통 연결 리스트고, 한 층 올라갈 때마다 원소가 절반씩 줄어요. 원소를 찾을 때는 맨 위층에서 시작해서 "이 원소보다 크면 아래층으로 내려가고, 작거나 같으면 오른쪽으로 가고"를 반복해요. 지하철 급행과 완행을 갈아타는 느낌이죠. 먼 거리는 급행(상위 층)으로 빠르게 이동하고, 세밀한 구간은 완행(하위 층)으로 정확하게 찾는 거예요.

구현해보면 놀랄 만큼 간단해요. 삽입과 삭제도 포인터 몇 개만 바꾸면 되고, 회전도 재균형도 필요 없죠. 코드 길이로 따지면 레드블랙 트리의 3분의 1 정도면 충분해요. Redis의 정렬된 셋(sorted set), LevelDB나 RocksDB의 memtable, 그리고 우리가 잘 아는 수많은 데이터베이스에서 스킵리스트를 쓰고 있어요.

그런데 왜 잘 안 쓰이는 걸까

글의 핵심은 여기예요. 이론적으로 그렇게 멋진데 왜 실전 코드베이스에서는 B-트리나 해시 맵이 압도적으로 많을까요?

첫째, 캐시 친화성 문제예요. 현대 CPU는 연속된 메모리를 한꺼번에 불러오는 걸 좋아하거든요. B-트리는 한 노드에 여러 키를 담아서 캐시 라인 하나에 많은 정보가 들어가는 반면, 스킵리스트는 포인터를 따라가는 구조라 메모리 여기저기를 건너뛰어야 해요. 이게 벤치마크에서 상당한 차이를 만들어요.

둘째, 병렬성이에요. 스킵리스트의 가장 큰 장점으로 꼽히는 게 "락프리(lock-free) 구현이 쉽다"였는데, 실제로 잘 만든 병렬 B-트리(예: OLFIT이나 Bw-Tree)도 그 이상의 성능을 내요.

셋째, 확률적 보장의 불편함이에요. 스킵리스트는 평균적으로 O(log n)이지만 최악의 경우엔 O(n)이 될 수도 있어요. 확률이 낮긴 하지만 0은 아니거든요. 미션 크리티컬한 시스템에서는 이런 불확실성이 부담이에요.

그럼에도 불구하고 스킵리스트가 살아남은 이유는 구현의 단순함과 범위 쿼리(range query) 지원 때문이에요. Redis가 정렬된 셋에서 스킵리스트를 선택한 이유도 "ZRANGEBYSCORE 같은 범위 연산이 자연스럽고 코드가 간결해서"라고 돌려서 말한 적이 있죠.

그리고 등장한 '스킵트리'

이 글의 백미는 여기예요. Antithesis 팀은 스킵리스트의 아이디어를 트리에 적용한 스킵트리(skiptree) 라는 변형을 소개해요. 핵심은 "스킵리스트의 확률적 균형 아이디어는 좋은데, 리스트 기반이라 캐시 친화성이 떨어진다. 그렇다면 트리 구조에 확률적 균형을 씌우면 어떨까?" 하는 질문이에요.

스킵트리는 각 노드에 여러 키를 담아서 B-트리의 캐시 친화성을 유지하면서도, 노드 분할이나 병합 시 복잡한 재균형 없이 확률적으로 균형을 맞춰요. 구현은 B-트리보다 훨씬 단순하고, 성능은 근접하죠. 특히 동시성 제어나 결정론적 테스팅 환경에서 장점이 있다고 글은 주장해요.

업계 맥락에서 보면

FoundationDB, CockroachDB, TiKV 같은 분산 데이터베이스들이 내부적으로 어떤 인덱스 구조를 쓰느냐는 시스템 성능에 직접적인 영향을 줘요. 대부분은 LSM 트리 위에 B+트리 인덱스를 올린 형태를 쓰는데, 메모리상의 정렬된 버퍼(memtable)에는 스킵리스트가 여전히 인기예요. RocksDB가 대표적이죠.

한국 개발자에게 주는 시사점

실무에서 바로 스킵리스트를 구현할 일은 거의 없어요. 하지만 자료구조 선택 기준을 이론뿐 아니라 하드웨어 특성까지 고려해서 봐야 한다는 교훈은 중요해요. 알고리즘 시간복잡도만 보고 선택하는 시대는 이미 지났거든요. 캐시 미스, 브랜치 예측, 메모리 대역폭 같은 실제 하드웨어 요인이 빅오 표기를 이기는 경우가 허다해요.

또 Redis나 RocksDB를 튜닝할 일이 있다면 내부 구조를 이해하는 게 큰 도움이 돼요. 왜 특정 연산이 빠르고 특정 연산이 느린지, 메모리 사용량이 왜 그렇게 나오는지가 자료구조에서 결정되거든요.

마무리

스킵리스트는 아름답지만 현실의 왕좌는 B-트리가 차지하고 있어요. 그렇지만 스킵트리 같은 변형이 계속 나오는 걸 보면, 자료구조 연구는 아직도 진행형이에요. 여러분은 실무에서 "교과서 알고리즘과 실제 성능이 달랐던" 경험이 있으신가요?