스킵리스트는 무엇에 좋은가?

스킵리스트는 이진 탐색 트리의 대체재처럼 동작하는 랜덤 자료구조로, 검색을 **O(log n)**에 처리한다.

• linked list 위에 여러 단계의 express lane를 얹어 빠르게 탐색한다.
• 구현이 비교적 단순해 lock-free concurrent 구현에도 잘 맞는다.

Antithesis는 고객 소프트웨어를 반복 실행하며 버그를 찾는데, 이 과정에서 선택과 fault 주입으로 인해 branching tree of timelines가 생긴다.

문제는 이 데이터를 당시 Google BigQuery에 넣고 있었다는 점이다.

• BigQuery는 대량 스캔과 집계에는 강하지만 point lookup이 느리다.
• parent pointer로 트리를 저장하면 조상 추적 같은 쿼리가 depth만큼 반복 조회를 요구해 비효율적이다.
• 데이터를 OLTP DB와 BigQuery로 분리하는 방법도 있었지만, 2PC와 일관성 문제가 생긴다.

해결책은 skiptree였다.

• 각 레벨마다 별도 SQL 테이블을 둔다: tree0, tree1, tree2...
• 각 행은 현재 노드의 next_level_ancestor와 그 사이의 노드 목록인 ancestors_between를 가진다.
• 어떤 노드의 조상을 찾을 때는 테이블을 위로 올라가며 고정된 수의 JOIN만 수행한다.

예를 들어 노드 I의 조상을 찾으면 tree0에서 시작해 tree1로 점프하며 중간 노드 G를 수집하고, 이어서 A까지 올라가 최종적으로 [G, C, A]를 얻는다.

이 방식 덕분에:

• 재귀 쿼리 없이 조상 추적이 가능해졌다.
• BigQuery의 planner limit 바로 아래가 되도록 skip level 수를 맞췄다.
• 각 쿼리의 스캔 비용도 기하급수적으로 늘지 않고, 대략 일반 테이블 스캔의 2배 수준으로 유지됐다.

SQL은 길고 보기 불편했지만, 사람 손으로 쓰지 않고 JavaScript compiler가 생성했다.

이 구조는 Antithesis에서 약 6년 동안 사용됐고, 나중에 자체 분석 DB인 Pangolin으로 옮기면서 더 효율적인 tree 쿼리를 지원하게 됐다.

핵심 메시지는, 흔치 않은 자료구조라도 실제 문제에 맞으면 큰 시간과 비용을 절약할 수 있다는 점이다. Skiplists, skiptrees, skipgraphs는 다 연결되어 있고, 단순한 구현만으로도 충분히 쓸모 있을 수 있다.