~/blog/skip-list/ko.mdx

Skip list: 동전 던지기에서 Redis의 순위표까지

높은 노드 몇 개로 검색을 줄이는 구조가 Redis에서는 순위를 세고, LevelDB에서는 쓰는 동안 읽히는 메모리 인덱스가 됩니다. 검색 경로와 span을 직접 바꾸고, 논문과 실제 구현이 어디서 갈라지는지 따라갑니다.

게임 순위표에서 점수를 바꾸는 일과 “내 위에 몇 명이 있나”를 묻는 일은 다른 연산입니다. 이름으로 점수를 찾기는 쉬워도, 앞에 있는 사람을 매번 세면 순위표가 길어질수록 오래 걸립니다.

Redis의 큰 sorted set은 이 둘을 서로 다른 구조에 맡깁니다. 이름은 해시 테이블에서 찾고, 점수 순서는 skip list에 둡니다. 그런데 skip list의 포인터만 따라가서는 건너뛴 사람이 몇 명인지 알 수 없습니다. Redis는 포인터 옆에 그 수까지 저장합니다.

이 글은 그 숫자에서 시작해서, 동전 던지기로 만든 높이가 왜 검색을 줄이는지, 저장 엔진과 동시성 자료구조에서는 무엇이 달라지는지 이어집니다. 원 논문과 Redis 6.2.6, LevelDB 1.23, OpenJDK 11의 구현을 읽었습니다. 아래 재현과 시각화 검증은 2026-10-10에 실행한 확인입니다. 화면의 2022년 날짜와 당시 실행 기록을 뜻하지는 않습니다.

순위표에 묻습니다 이름으로 점수 조회 점수 순서와 순위 조회 dict skip list forward: 다음 노드 span: 건너뛴 원소 수 범위 순회 순위 계산

연결 리스트에 급행 정류장을 만듭니다

정렬된 연결 리스트에서 42를 찾는다고 생각해 봅니다. 시작점에서 다음 노드를 읽고, 작으면 또 다음으로 갑니다. 배열처럼 가운데 주소를 바로 계산할 수 없으니 이진 탐색을 붙이기도 어렵습니다.

skip list는 일부 노드에 더 멀리 가는 포인터를 붙입니다. 바닥 층 L0에는 모든 노드가 있고, 위층은 그중 일부만 연결합니다. 높은 층에서 시작해 다음 값이 목표보다 작으면 오른쪽으로 갑니다. 다음 값이 목표 이상이면 같은 노드에서 한 층 내려갑니다. 위로 다시 올라가지는 않습니다.1

아래 그림에서 다음을 눌러 보시면 “지나갈 수 없어서 내려간다”는 동작도 한 단계로 나옵니다. 목표를 35로 바꾸면 값이 없는 검색을 볼 수 있습니다. 없다는 판정 역시 바닥 층에서 합니다.

포인터를 따라갑니다

L0∅L1∅L2∅L3∅ H 7 12 19 26 31 42 58 73

L3의 H에서 시작합니다. 목표는 42입니다.

노드 수: 8 seed: 7

숫자 키만 쓰고 최대 4층으로 제한한 학습 모델입니다. H는 헤더, ∅는 null입니다. 확률 모드에는 시드가 있는 난수를 쓰며, 삽입 높이는 2로 고정합니다. Redis의 성능이나 메모리 배치를 재현하지 않습니다. 휴대폰에서는 그림을 좌우로 밀어 볼 수 있습니다.
처음 예제의 전체 경로 읽기
  1. L3의 H에서 시작합니다. 목표는 42입니다.
  2. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. H에서 L2로 내려갑니다.
  3. 42보다 작은 26까지 L2 포인터를 따라갑니다.
  4. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. 26에서 L1로 내려갑니다.
  5. 다음 값은 42입니다. 그 포인터로 넘어가지 않습니다. 26에서 L0로 내려갑니다.
  6. 42보다 작은 31까지 L0 포인터를 따라갑니다.
  7. 다음 값은 42입니다. 그 포인터로 넘어가지 않습니다. L0에서 일치 여부를 확인합니다.
  8. 바닥 층에서 42를 찾았습니다.

7 (h=1), 12 (h=2), 19 (h=1), 26 (h=3), 31 (h=1), 42 (h=2), 58 (h=4), 73 (h=1)

각 위층은 바닥 리스트의 부분집합입니다. 검색 도중 작은 값을 건너뛸 수 있지만, 목표를 넘어서는 연결은 타지 않습니다. 목표 앞에 도착하면 아래층에 더 촘촘한 길이 있습니다.

여기서 높이는 검색의 정확성을 정하지 않습니다. 모든 노드가 높이 1이어도 답은 맞습니다. 오른쪽으로 걸어가는 횟수가 늘어날 뿐입니다. 높이 메뉴를 모두 높이 1로 바꾸고 73을 찾아 보면 차이를 볼 수 있습니다.

독립적인 승격 모델에서 검색·삽입·삭제 비용은 기댓값 O(log⁡n)O(\log n)입니다. 특정 리스트 하나의 최악 시간은 O(n)O(n)일 수 있습니다. 동전이 약속하는 것은 “이번에도 반드시 빠르다”가 아니라 분포 전체에서의 비용입니다.1

퀴즈높이가 나쁘게 나왔을 때

답을 고르면 해설이 나옵니다.

1문제 중 0개 맞힘

  1. 난수 결과가 좋지 않아 모든 노드의 높이가 1이 됐습니다. 어떤 문제가 생깁니까?

동전을 던지는 이유, 그리고 동전값

Pugh의 원 논문은 노드를 한 층 높일 확률을 pp로 둡니다. 처음 한 층은 누구에게나 있고, 승격에 성공할 때마다 한 층을 더 받습니다. 높이를 제한하지 않는 독립적인 승격 모델에서 높이 HH의 분포는 다음과 같습니다.1

P(H≥k)=pk−1E[H]=1+p+p2+⋯=11−p\begin{aligned} P(H \ge k)&=p^{k-1}\\ E[H]&=1+p+p^2+\cdots\\ &=\frac{1}{1-p} \end{aligned}

따라서 p=1/2p=1/2이면 노드당 forward 포인터 수의 기댓값은 2개, p=1/4p=1/4이면 4/34/3개입니다. 헤더, 값, span, backward 포인터, 할당기의 여유 공간을 뺀 forward 슬롯만의 계산입니다. 이것을 그대로 노드당 메모리 바이트라고 부를 수는 없습니다.

L0 L1 L2 L3 L4 0 20 40 60 80 100 비율 (%) 독립 승격 모델: 이 층에 도달하는 비율
p = 1/2p = 1/4

이 그래프는 측정값이 아니라 위 식의 값입니다. pp를 줄이면 위층 노드는 줄고, 같은 층에서 더 멀리 걸을 수 있습니다. Pugh가 분석한 탐색 비용의 주항은 (1/p)log⁡1/pn(1/p)\log_{1/p}n 형태입니다. p=1/2p=1/2와 p=1/4p=1/4는 이 주항이 같아지는 조합이지만, 실제 프로그램의 실행 시간이 같다는 뜻은 아닙니다.1

Redis 6.2.6은 승격 확률 ZSKIPLIST_P = 0.25, 최대 높이 ZSKIPLIST_MAXLEVEL = 32를 씁니다. LevelDB 1.23도 분기 계수 4로 높이를 뽑지만 최대 높이는 12입니다. 둘 다 교과서 그림의 “공정한 동전”을 그대로 쓰지 않습니다.23

앞의 그림은 읽을 수 있는 크기로 최대 높이를 4로 제한했습니다. p = 1/4나 p = 1/2를 고르면 시드가 있는 난수로 높이를 만들고, 다른 시드로 다시 뽑습니다. 작은 예제 하나가 논문의 기대 시간 증명이나 Redis의 난수 구현을 대신하지는 않습니다.

Redis는 이름과 순서를 따로 보관합니다

Redis 6.2.6의 zset에는 dict와 zsl이 있습니다. 멤버 이름으로 현재 점수를 찾을 때는 dict를 읽습니다. 점수 범위와 순위에서는 skip list를 탐색합니다. 두 구조는 멤버 문자열을 공유하고, dict의 값은 skip list 노드의 score 필드를 가리킵니다.24

멤버 alpha dict 엔트리 노드의 score 주소 skip list 노드 score 공유 멤버 문자열 level 배열 forward span backward: L0의 이전 노드

이 설명에는 크기 조건이 붙습니다. Redis 6.2.6의 작은 sorted set은 ziplist를 쓸 수 있습니다. 기본 zset-max-ziplist-entries는 128, zset-max-ziplist-value는 64바이트입니다. 이 조건을 넘으면 dict와 skip list를 쓰는 표현으로 바뀝니다. 모든 ZADD가 처음부터 skip list 노드를 만드는 것은 아닙니다.5

Redis의 정렬 기준도 “점수” 한 단어로 끝나지 않습니다. 점수가 같으면 sdscmp로 멤버 문자열을 비교합니다. 언어별 사전순이나 지역화된 문자열 정렬이 아니라 바이트 비교입니다. 이 글의 ASCII 예제에서는 같은 점수의 alpha, bravo, charlie가 그 순서로 나옵니다.4

멤버 이름은 유일하지만 점수는 중복될 수 있습니다. “skip list가 중복을 허용하나요?”라는 질문은 비교 키가 무엇인지 먼저 정해야 답할 수 있습니다. Redis에서는 (score, member)가 순서를 정하고, dict가 같은 멤버의 재등록을 갱신으로 처리합니다.

순위는 포인터 옆의 span으로 셉니다

forward가 목적지만 알려 준다면 span은 거기까지 바닥 원소를 몇 개 지나는지 알려 줍니다. Redis의 zslGetRank는 목표를 넘지 않는 연결을 타면서 span을 더합니다.4

이 그림의 값 42를 순위 모드로 찾아 보겠습니다. 설명용 높이에서는 H에서 26까지 span 4를 더하고, 26에서 42까지 span 2를 더합니다. 바닥 노드 여섯 개를 두 번의 수평 이동으로 셉니다. 이 값은 npm run test:skiplist가 그림과 같은 엔진에서 확인합니다.

포인터를 따라갑니다

L0∅L1∅L2∅L3∅ 1 2 4 7 1 1 2 1 1 2 3 1 1 1 1 1 1 1 0 H 7 12 19 26 31 42 58 73

L3의 H에서 시작합니다. 목표는 42입니다.

노드 수: 8 seed: 7

숫자 키만 쓰고 최대 4층으로 제한한 학습 모델입니다. H는 헤더, ∅는 null입니다. 확률 모드에는 시드가 있는 난수를 쓰며, 삽입 높이는 2로 고정합니다. Redis의 성능이나 메모리 배치를 재현하지 않습니다. 휴대폰에서는 그림을 좌우로 밀어 볼 수 있습니다.
처음 예제의 전체 경로 읽기
  1. L3의 H에서 시작합니다. 목표는 42입니다.
  2. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. H에서 L2로 내려갑니다.
  3. H에서 26까지 span 4을 더합니다. 누적 순위는 4입니다.
  4. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. 26에서 L1로 내려갑니다.
  5. 26에서 42까지 span 2을 더합니다. 누적 순위는 6입니다.
  6. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. 42에서 L0로 내려갑니다.
  7. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. L0에서 일치 여부를 확인합니다.
  8. 42를 찾았습니다. 내부 순위는 6이고, 0부터 세면 5입니다.

7 (h=1), 12 (h=2), 19 (h=1), 26 (h=3), 31 (h=1), 42 (h=2), 58 (h=4), 73 (h=1)

헤더 H는 내부 순위 0입니다. 첫 원소는 1이고, 그림의 42는 6입니다. Redis의 내부 순위와 공개 명령 ZRANK는 시작점이 다릅니다. ZRANK는 0부터 세므로 이 예제에 해당하는 공개 순위는 5입니다.4

span은 점수 차이가 아닙니다. 점수가 26에서 42로 벌어져도 그 사이에 몇 노드가 있는지만 셉니다. 끝의 null을 향하는 span에는 남아 있는 바닥 원소 수가 들어갈 수 있습니다. rank 탐색은 null 링크로 이동하지 않으므로 그 값을 더하지 않습니다.

범위 조회에서는 시작점을 찾은 뒤 L0를 따라 결과를 읽습니다. 결과 MM개를 반환해야 한다면 그 MM개를 읽는 비용은 사라지지 않습니다. ZRANGE의 O(log⁡N+M)O(\log N+M)에서 MM을 빼고 설명하면 큰 범위 조회의 비용을 놓칩니다.6

삽입은 두 포인터만 바꾸고 끝나지 않습니다

연결 리스트 삽입을 처음 배우면 앞 노드와 새 노드의 연결을 고칩니다. skip list에서도 각 층에서 새 노드 바로 앞에 멈춘 위치를 update[]에 모읍니다. Redis는 그 위치까지 센 순위를 rank[]에도 남깁니다.4

기존 연결의 span을 SS, 해당 층의 앞 노드에서 삽입 직전 위치까지 바닥에서 이동한 수를 dd라 두면, 새 연결의 span은 다음처럼 나뉩니다.

S앞→새=d+1,S새→뒤=S−dS_{\text{앞→새}}=d+1,\qquad S_{\text{새→뒤}}=S-d

새 노드가 참여하지 않는 더 높은 층도 원소 하나가 연결 밑에 추가됐으므로 span을 1 늘려야 합니다. 새 노드의 높이만큼 포인터를 연결하는 일과 전체 활성 층의 카운트를 고치는 일은 다릅니다.

아래는 높이 2인 값 35의 삽입입니다. 마지막 단계에서 바뀐 연결과 span이 주황색으로 표시됩니다. 35가 없는 L2에서도 26 → 58의 span이 3에서 4로 바뀝니다. 새 포인터가 없어도 카운트는 바뀝니다. 삭제 모드에서는 반대로 내려갑니다.

포인터를 따라갑니다

L0∅L1∅L2∅L3∅ H 7 12 19 26 31 42 58 73

L3의 H에서 시작합니다. 목표는 35입니다.

노드 수: 8 seed: 7

숫자 키만 쓰고 최대 4층으로 제한한 학습 모델입니다. H는 헤더, ∅는 null입니다. 확률 모드에는 시드가 있는 난수를 쓰며, 삽입 높이는 2로 고정합니다. Redis의 성능이나 메모리 배치를 재현하지 않습니다. 휴대폰에서는 그림을 좌우로 밀어 볼 수 있습니다.
처음 예제의 전체 경로 읽기
  1. L3의 H에서 시작합니다. 목표는 35입니다.
  2. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. H에서 L2로 내려갑니다.
  3. 35보다 작은 26까지 L2 포인터를 따라갑니다.
  4. 다음 값은 58입니다. 그 포인터로 넘어가지 않습니다. 26에서 L1로 내려갑니다.
  5. 다음 값은 42입니다. 그 포인터로 넘어가지 않습니다. 26에서 L0로 내려갑니다.
  6. 35보다 작은 31까지 L0 포인터를 따라갑니다.
  7. 다음 값은 42입니다. 그 포인터로 넘어가지 않습니다. L0에서 일치 여부를 확인합니다.
  8. 35는 없습니다. 바로 앞 값은 31입니다.
  9. 높이 2인 35를 삽입했습니다. L0과 L1을 연결하고 모든 층의 span을 갱신합니다.

7 (h=1), 12 (h=2), 19 (h=1), 26 (h=3), 31 (h=1), 35 (h=2), 42 (h=2), 58 (h=4), 73 (h=1)

그림의 엔진은 실제로 update[]와 rank[]를 만들고 연결과 span을 갱신합니다. 각 단계를 그럴듯하게 적어 둔 재생 표는 아닙니다. 테스트는 삽입과 삭제 2,000회를 정렬된 집합과 대조하고, 각 연결의 span이 목적지 순위에서 출발 순위를 뺀 값인지 검사합니다. 이는 이 학습 모델의 검증이며 Redis C 구현 전체의 검증을 대신하지 않습니다.

퀴즈높이 2인 노드를 넣었습니다

답을 고르면 해설이 나옵니다.

1문제 중 0개 맞힘

  1. 새 노드가 L0와 L1에만 존재합니다. 이 노드를 가로질러 가는 L2 링크는 어떻게 바뀝니까?

점수 변경에도 제자리 갱신이 있습니다

큰 Redis sorted set에서 점수를 바꿀 때마다 반드시 노드를 새로 만드는 것은 아닙니다. zslUpdateScore는 새 점수가 앞 노드의 점수보다 크고 뒤 노드의 점수보다 작은지 봅니다. 리스트 양 끝에서는 없는 이웃 쪽 조건을 생략합니다. 이 조건을 만족하면 score만 바꿉니다.4

순서가 유지되므로 연결과 span은 그대로입니다. dict가 노드의 score 주소를 가리키는 것도 여기에 맞습니다. 제자리 조건을 만족하지 못하면 기존 노드를 삭제하고 새 점수로 삽입합니다. 새 노드를 만든 경로에서는 dict가 가리키는 score 주소도 바뀝니다.

조건이 엄격한 <, >라는 점도 볼 만합니다. 이웃과 점수가 같아지는 변경은 멤버의 바이트 순서까지 따져야 하므로 이 빠른 경로로 판정하지 않습니다. 반면 아예 같은 점수를 다시 쓰는 ZADD는 상위 경로에서 점수 변경을 생략할 수 있습니다.

실제 Redis에서 확인합니다

다음 Lua는 기본 zset 임계값으로 시작한 단독 Redis 6.2.6에서 실행하는 재현입니다. ziplist 경계, 같은 점수의 순서, 점수 변경, 삭제, NaN 입력 거절을 확인합니다. 순위표 키는 65바이트 멤버를 잠깐 넣어 skiplist로 바꾼 뒤 그 멤버를 지웁니다. 여러 키를 쓰므로 Cluster 예제가 아니며, 운영 서버에 붙여서 실행하는 스크립트도 아닙니다.

zset-contract.lua
local boundary = "skiplist-check:boundary"
local board = "skiplist-check:board"
redis.call("DEL", boundary, board)
for i = 1, 128 do
redis.call("ZADD", boundary, i, string.format("m:%03d", i))
end
assert(redis.call("OBJECT", "ENCODING", boundary) == "ziplist")
redis.call("ZADD", boundary, 129, "m:129")
assert(redis.call("OBJECT", "ENCODING", boundary) == "skiplist")
redis.call("ZREM", boundary, "m:129")
assert(redis.call("OBJECT", "ENCODING", boundary) == "skiplist")
local trigger = string.rep("x", 65)
redis.call("ZADD", board, 10, "charlie", 10, "alpha", 10, "bravo")
redis.call("ZADD", board, 0, trigger)
redis.call("ZREM", board, trigger)
assert(redis.call("OBJECT", "ENCODING", board) == "skiplist")
local ties = table.concat(redis.call("ZRANGE", board, 0, -1), ",")
assert(ties == "alpha,bravo,charlie")
assert(redis.call("ZRANK", board, "alpha") == 0)
assert(redis.call("ZRANK", board, "bravo") == 1)
assert(redis.call("ZRANK", board, "charlie") == 2)
redis.call("ZADD", board, 20, "alpha")
redis.call("ZADD", board, 21, "alpha")
redis.call("ZADD", board, 21, "alpha")
assert(redis.call("ZCARD", board) == 3)
assert(redis.call("ZSCORE", board, "alpha") == "21")
assert(redis.pcall("ZADD", board, "nan", "alpha").err)
assert(redis.call("ZSCORE", board, "alpha") == "21")
local moves = table.concat(redis.call("ZRANGE", board, 0, -1), ",")
assert(moves == "bravo,charlie,alpha")
redis.call("ZREM", board, "charlie")
local deleted = table.concat(redis.call("ZRANGE", board, 0, -1), ",")
assert(deleted == "bravo,alpha")
return {
"boundary: ziplist/skiplist",
"ties: " .. ties,
"ranks: 0,1,2",
"moves: " .. moves,
"delete: " .. deleted
}

블로그 소스의 python3 scripts/test-skiplist-redis.py --docker는 이 코드 블록을 그대로 추출합니다. 격리한 redis:6.2.6 컨테이너에서 실행하고 컨테이너를 지웁니다. 이 글의 확인에서는 다음 결과가 나왔습니다.

boundary: ziplist/skiplist
ties: alpha,bravo,charlie
ranks: 0,1,2
moves: bravo,charlie,alpha
delete: bravo,alpha

이 명령 결과는 순서와 인코딩을 확인합니다. 제자리 갱신과 재삽입 중 어느 C 분기를 탔는지는 이 출력만으로 판별할 수 없습니다. 그 구분은 zslUpdateScore의 조건을 읽은 결과입니다. 내부 구현을 관찰한 것과 외부 동작을 재현한 것을 섞지 않습니다.

LevelDB는 읽는 동안 노드가 사라지지 않습니다

LevelDB 1.23의 memtable에도 skip list가 들어갑니다. 여기서 순서는 Redis의 점수 순서가 아닙니다. memtable 엔트리는 internal key를 포함하며, 사용자 키가 같으면 sequence number 등의 내부 정보가 비교에 들어갑니다. 새로운 버전이 앞에 오는 정렬 덕분에 읽기 시점에 맞는 버전을 찾습니다.7

memtable에 쓴 내용이 파일로 내려간 뒤에도 디스크에서 skip list를 읽는 것은 아닙니다. LevelDB의 SSTable은 블록과 인덱스를 쓰는 별도 형식입니다. “LSM 저장 엔진이 skip list를 쓴다”는 설명은 어느 층을 말하는지 붙여야 합니다.8

db/skiplist.h 맨 위의 동시성 계약은 구체적입니다. 쓰기는 외부에서 동기화하고, 읽기는 다른 쓰레드에서 동시에 해도 됩니다. 읽는 동안 skip list가 파괴되지 않아야 합니다. 노드는 Arena에서 할당하고, 개별 노드를 삭제하지 않습니다. 리스트를 파괴할 때 함께 정리합니다.3

새 노드가 독자에게 보이는 시점

기존 노드의 next42
새 노드의 next미공개
독자가 볼 수 있는 경로26 → 42

삽입 전

기존 링크가 42를 가리킵니다. 새 노드는 아직 독자가 도달할 수 없습니다.

LevelDB 1.23의 초기화와 release/acquire 공개 순서를 단일 링크로 줄인 모델입니다. CPU 시간을 측정하지 않으며, 전체 삽입의 동시성 증명은 아닙니다.
전체 상태 보기 (JavaScript 없이도 읽을 수 있습니다)

초기화 후 공개

  1. 삽입 전

    기존 노드의 next: 42 · 새 노드의 next: 미공개 · 독자가 볼 수 있는 경로: 26 → 42

    기존 링크가 42를 가리킵니다. 새 노드는 아직 독자가 도달할 수 없습니다.

  2. 새 노드 초기화

    기존 노드의 next: 42 · 새 노드의 next: 42 · 독자가 볼 수 있는 경로: 26 → 42

    쓰기 쓰레드가 35의 다음 포인터를 먼저 채웁니다.

  3. release로 연결

    기존 노드의 next: 35 · 새 노드의 next: 42 · 독자가 볼 수 있는 경로: 26 → 35 → 42

    앞 노드의 next를 공개합니다. 독자는 acquire로 이 링크를 읽습니다.

LevelDB의 Next()는 acquire load, SetNext()는 release store를 씁니다. 아직 공개되지 않은 새 노드의 링크를 초기화할 때는 relaxed store를 쓸 수 있습니다. “포인터는 원자적으로 읽히니까 괜찮다”로 끝내면, 포인터가 가리키는 노드의 초기화가 언제 보이는지 설명하지 못합니다.

삭제가 없다는 조건도 중요합니다. 독자가 읽던 노드가 도중에 해제되는 문제를 이 자료구조에서는 피합니다. Redis용 span과 개별 삭제를 이 코드에 붙이면 기존 동시성 계약으로 안전하다고 말할 수 없습니다. 추가 필드와 수명 규칙을 다시 설계해야 합니다.

동시 skip list는 구현마다 계약이 다릅니다

OpenJDK 11의 ConcurrentSkipListMap은 바닥 노드와 위층의 Index 노드를 나눕니다. CAS를 쓰는 갱신 경로와 삭제용 marker, 진행 중인 삭제를 돕는 코드가 있습니다. LevelDB처럼 “쓰기 하나와 삭제 없음”을 전제로 읽기만 허용하는 코드가 아닙니다.9

바닥 리스트의 삭제 알고리즘은 소스 주석이 Harris와 Michael의 HM 알고리즘으로 명시합니다. Fraser는 관련 연구로 인용합니다. 논문 목록에 이름이 있다고 해서 그 논문의 구현을 그대로 가져왔다고 읽으면 안 됩니다.9

이 구현의 주석은 바닥 리스트에서 값을 찾고 위의 인덱스를 탐색 보조로 사용한다고 설명합니다. 삽입과 삭제가 경쟁할 때 인덱스에 잠시 없는 노드가 생겨도 바닥 리스트가 값을 찾을 수 있어야 합니다. 처음 봤던 “높이가 정답을 결정하지 않는다”는 성질이 여기서 다시 쓰입니다.

Fraser의 Practical lock-freedom은 CAS 기반 자료구조뿐 아니라 메모리 회수까지 다룹니다. 노드를 리스트에서 분리하는 일과 다른 쓰레드가 더 이상 참조하지 않아 해제할 수 있는 시점을 정하는 일은 다릅니다. Java의 GC에 기대는 구현과 C/C++에서 수명을 직접 관리하는 구현을 포인터 그림 하나로 같다고 볼 수 없습니다.10

구현무엇의 순서인가갱신과 노드 수명에서 볼 부분
Redis 6.2.6 zset점수, 그다음 멤버 바이트dict와 span을 함께 고치며 개별 삭제를 합니다. 이 skip list 자체가 범용 동시성 컨테이너는 아닙니다.
LevelDB 1.23 memtableinternal key외부에서 쓰기를 동기화합니다. 동시 독자는 읽는 동안 구조가 살아 있어야 하고, 개별 삭제는 없습니다.
OpenJDK 11 ConcurrentSkipListMap키 comparator바닥/인덱스 분리, CAS, 삭제 도움, GC를 함께 봅니다.

표의 자료구조에 모두 skip list라는 이름이 붙어도 “동시에 쓸 수 있다”나 “삭제해도 독자가 안전하다”는 속성이 공유되지는 않습니다.

lock-free라는 용어도 “모든 호출이 정해진 횟수 안에 끝난다”는 뜻으로 쓰지 않습니다. 시스템 전체의 진행 보장과 한 호출의 완료 보장은 다릅니다. 재시도하는 호출이 오래 기다릴 수 있고, 이것은 wait-free와 구별해야 하는 부분입니다.10

논문에서는 rank 다음에 finger와 merge가 나옵니다

Pugh의 A Skip List Cookbook에는 검색과 삽입 외에 순위 연산, finger 검색, merge, split, concatenate가 나옵니다. 같은 자료구조라도 요청이 어디에서 시작하는지, 어떻게 이어지는지에 따라 더 할 일이 있습니다.11

finger는 이전 검색 근처의 위치를 기억하는 손가락입니다. 직전 위치에서 순위상 kk만큼 떨어진 대상을 찾는 검색을 기댓값 O(log⁡k)O(\log k)로 분석합니다. 모든 검색을 헤더에서 다시 시작하는 코드와 전제가 다릅니다. 이 결과가 Redis의 ZRANK에 자동으로 적용되는 것은 아닙니다.

merge도 두 입력이 얼마나 뒤섞였는지에 따라 작업량이 달라집니다. 한 리스트의 값이 다른 리스트 뒤에 통째로 붙는 경우에는 concatenate가 맞습니다. Cookbook이 분석하는 merge는 이런 입력의 배치를 구별합니다. 항상 양쪽 바닥 리스트를 끝까지 순회하는 병합만이 선택지는 아닙니다.

확률 자체를 빼는 연구도 있습니다. Munro, Papadakis, Sedgewick의 Deterministic Skip Lists는 층 사이의 간격에 조건을 두고 높이를 조정해 최악 시간의 로그 경계를 얻습니다. 노드 높이를 난수로 뽑는 구현에 그 보장이 생기는 것은 아닙니다.12

어떤 요청을 받습니까? 순위와 범위 직전 검색 근처 동시 갱신 최악 시간 상한 span이 있는 인덱스 finger를 유지하는 검색 공개 순서와 메모리 회수 간격을 유지하는 deterministic 변형

skip list를 선택한다고 해서 이 기능을 모두 받는 것은 아닙니다. 필요한 기능이 붙은 구현을 선택해야 합니다. 특히 Cookbook의 알고리즘, 저장 엔진의 수명 계약, concurrent map의 진행 보장을 한 문장으로 묶으면 실제 코드가 하지 않는 일을 설명하게 됩니다.

어떤 구현을 고를지 확인합니다

순위표라면 이름 조회, 같은 점수의 순서, rank가 필요한지부터 묻습니다. span이 없는 정렬 map은 범위 순회는 해도 rank를 같은 비용으로 답하지 못할 수 있습니다.

memtable이라면 삽입 후 노드를 개별 삭제해야 하는지 묻습니다. 수명을 통째로 묶을 수 있는 구조와, 아무 때나 노드를 지우는 구조는 독자를 보호하는 방법부터 다릅니다. 배열이나 B-tree와 비교할 때도 O(log⁡n)O(\log n)만으로 승자를 정하지 않습니다. 포인터를 따라가며 메모리를 읽는 비용, 연속 배치, 결과를 순회하는 길이까지 해당 작업에서 확인해야 합니다.

퀴즈다른 작업에 옮겨 봅니다

답을 고르면 해설이 나옵니다.

3문제 중 0개 맞힘

  1. span이 없는 skip list 기반 map에 내 순위 기능을 붙이려 합니다. 먼저 무엇을 확인해야 합니까?

  2. LevelDB 방식의 읽기 경로를 가져오면서 개별 노드를 즉시 free하도록 바꿨습니다. acquire/release 포인터면 충분합니까?

  3. Redis가 반환할 범위의 시작점을 빨리 찾았습니다. 결과 10,000개를 돌려주는 비용도 로그 시간입니까?

다음에 소스를 읽을 때

카드를 누르면 뒤집힙니다.

6장 중 0장 확인

각주

  1. William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Communications of the ACM, 1990. 링크는 PDF 미러이며, 출판 기록은 DOI 10.1145/78973.78977입니다. 표 1의 포인터 수와 정규화한 탐색 비용을 확인했습니다. 원 저자의 PDF 주소는 확인 당시 404였습니다. ↩ ↩2 ↩3 ↩4

  2. Redis 6.2.6 server.h: ZSKIPLIST_MAXLEVEL, ZSKIPLIST_P, zskiplistNode, zset. ↩ ↩2

  3. LevelDB 1.23 db/skiplist.h: 파일 상단의 계약, Node::Next, Node::SetNext, RandomHeight, Insert. 최대 높이 12, 분기 계수 4를 이 태그에서 확인합니다. ↩ ↩2

  4. Redis 6.2.6 t_zset.c: zslRandomLevel, zslInsert, zslDeleteNode, zslUpdateScore, zslGetRank, zsetAdd, zrankGenericCommand. ↩ ↩2 ↩3 ↩4 ↩5 ↩6

  5. Redis 6.2.6 redis.conf: zset-max-ziplist-entries, zset-max-ziplist-value. 테스트 실행기는 서버를 시작할 때 이 기본 경계를 명시합니다. ↩

  6. Redis ZRANGE 명령 문서: O(log⁡N+M)O(\log N+M). 현재 명령 문서의 복잡도 설명을 인용하며, 이 글의 실행 대상은 6.2.6입니다. ↩

  7. LevelDB 1.23 db/memtable.cc와 db/dbformat.h: KeyComparator, InternalKeyComparator. ↩

  8. LevelDB 1.23 doc/table_format.md: data block과 index block. ↩

  9. OpenJDK jdk-11+28의 ConcurrentSkipListMap.java: 구현 주석, Node, Index, 검색·삽입·삭제 경로. ↩ ↩2

  10. Keir Fraser, Practical lock-freedom, University of Cambridge, 기술 보고서 579, 2004. skip list 구현과 진행 보장, 메모리 회수를 다룹니다. ↩ ↩2

  11. William Pugh, A Skip List Cookbook, CS-TR-2286.1 / UMIACS-TR-89-72.1. 대학 저장소 PDF의 finger 검색과 선형 리스트 연산을 확인했습니다. rank, finger, merge의 보장은 각 알고리즘의 전제 아래 읽어야 합니다. ↩

  12. J. Ian Munro, Thomas Papadakis, Robert Sedgewick, Deterministic Skip Lists, SODA 1992. 저자 사이트의 PDF에서 로그 시간의 검색·삽입·삭제를 보장하는 변형을 확인했습니다. 논문 안의 모든 변형이 같은 갱신 비용을 갖는 것은 아닙니다. ↩

~/blog/skip-list/en.mdx

Skip lists: from coin flips to Redis rankings

A few tall nodes shorten a search. Redis adds rank accounting; LevelDB turns the structure into a memory index that can be read during writes. Change the paths and spans, then follow where the papers and production implementations diverge.

Updating a score on a game leaderboard and asking “how many players are ahead of me?” are different operations. Looking up a score by name is straightforward. Counting every player ahead of you gets more expensive as the board grows.

A large Redis sorted set assigns these jobs to different structures. A hash table handles member lookup; a skip list maintains score order. Forward pointers alone cannot tell you how many players a jump passed. Redis stores that count beside the pointer.

This article starts with that count, then follows why randomized heights shorten searches and what changes inside a storage engine or a concurrent container. The sources are the original papers and Redis 6.2.6, LevelDB 1.23, and OpenJDK 11. The reproductions and visualization checks below were run on 2026-10-10. They are not records of tests run on the displayed 2022 date.

Ask the leaderboard Look up a score by name Read score order and rank dict skip list forward: next node span: elements passed Range scan Rank calculation

Give a linked list some express stops

Imagine searching for 42 in a sorted linked list. Read the next node; if its value is smaller, read the next one. Unlike an array, you cannot calculate the address of the middle element, so adding binary search is not straightforward.

A skip list gives some nodes pointers that travel farther. The base level, L0, contains every node. Each higher level connects a subset. Start at the top. Move right while the next value is below the target. When the next value reaches or exceeds the target, descend at the current node. You never need to climb back up.1

Press Next below. Refusing a jump and descending is a step of its own. Change the target to 35 to try an unsuccessful search. Absence is established at the base level too.

Follow the pointers

L0∅L1∅L2∅L3∅ H 7 12 19 26 31 42 58 73

Start at H on L3. Target: 42.

Nodes: 8 seed: 7

Numeric-key teaching model, capped at 4 levels. H is the header; ∅ is null. Promotion uses a seeded PRNG; insertion uses height 2. Not Redis performance or its memory layout. Scroll the diagram horizontally on a phone.
Read the complete initial trace
  1. Start at H on L3. Target: 42.
  2. The next key is 58; do not cross it. Stay at H and descend to L2.
  3. Follow L2 to 26, which is below 42.
  4. The next key is 58; do not cross it. Stay at 26 and descend to L1.
  5. The next key is 42; do not cross it. Stay at 26 and descend to L0.
  6. Follow L0 to 31, which is below 42.
  7. The next key is 42; do not cross it. Check at L0.
  8. Found 42 at the base level.

7 (h=1), 12 (h=2), 19 (h=1), 26 (h=3), 31 (h=1), 42 (h=2), 58 (h=4), 73 (h=1)

Every upper level is a subset of the base list. Search may skip smaller values, but it never follows a link past the target. If it stops before the target, the lower level provides a finer path.

Height does not determine correctness. Even if every node has height 1, the answers remain correct. You just walk farther. Choose All height 1 and search for 73 to see the difference.

With independent promotion, search, insertion and deletion take expected O(log⁡n)O(\log n) time. One particular list can still take O(n)O(n) in the worst case. The coin controls the distribution of costs; it does not guarantee that every search is short.1

QuizAn unlucky height distribution

Choose an answer to see the explanation.

0 of 1 right

  1. Random promotion gives every node height 1. What goes wrong?

Why flip a coin, and how much does the coin cost?

Pugh’s original paper uses pp as the probability of promotion to another level. Every node gets its first level; each successful promotion adds one more. With independent promotions and no height cap, height HH has this distribution:1

P(H≥k)=pk−1E[H]=1+p+p2+⋯=11−p\begin{aligned} P(H \ge k)&=p^{k-1}\\ E[H]&=1+p+p^2+\cdots\\ &=\frac{1}{1-p} \end{aligned}

At p=1/2p=1/2, the expected number of forward pointers per node is 2. At p=1/4p=1/4, it is 4/34/3. This counts forward slots only. It excludes the header, values, spans, backward pointers, and allocator overhead. It is not a per-node byte measurement.

L0 L1 L2 L3 L4 0 20 40 60 80 100 Fraction (%) Independent promotion model: fraction reaching each level
p = 1/2p = 1/4

The chart evaluates the formula; it is not a measurement. Reducing pp produces fewer upper-level nodes and can mean longer walks within a level. The leading search-cost term in Pugh’s analysis has the form (1/p)log⁡1/pn(1/p)\log_{1/p}n. The choices p=1/2p=1/2 and p=1/4p=1/4 give the same leading term, but this does not make two programs equally fast.1

Redis 6.2.6 uses ZSKIPLIST_P = 0.25 and ZSKIPLIST_MAXLEVEL = 32. LevelDB 1.23 also samples heights with branching factor 4, but caps them at 12. Neither simply adopts the fair coin in the familiar textbook picture.23

The explorer caps height at 4 to keep the diagram readable. Choosing p = 1/4 or p = 1/2 generates heights with a seeded PRNG; Next seed samples another arrangement. One small example does not replace the expected-time analysis or reproduce Redis’s random generator.

Redis stores names and order separately

Redis 6.2.6’s zset contains a dict and a zsl. Member lookup reads the dict; score ranges and ranks use the skip list. The structures share member strings, and a dict value points to the skip-list node’s score field.24

Member alpha dict entry Address of node score skip list node score Shared member string level array forward span backward: previous L0 node

There is a size condition. Small sorted sets in Redis 6.2.6 can use ziplist encoding. The defaults are zset-max-ziplist-entries = 128 and zset-max-ziplist-value = 64 bytes. Exceeding a limit converts the representation to dict plus skip list. Not every ZADD allocates a skip-list node from the beginning.5

Redis order is not fully described by “score.” Tied scores compare member strings using sdscmp: byte order, not a locale-aware dictionary order. In the ASCII example here, tied members come out as alpha, bravo, charlie.4

Members are unique; scores may repeat. Before asking whether a skip list allows duplicates, define its comparison key. Redis orders by (score, member), while the dict turns another registration of the same member into an update.

Rank comes from spans beside the pointers

forward identifies the destination. span counts the base elements passed on the way there. Redis’s zslGetRank follows links that do not pass the target and adds their spans.4

Find 42 in Rank mode below. With the authored heights, the path from H to 26 adds span 4, and the path from 26 to 42 adds span 2. Two horizontal moves account for six base nodes. npm run test:skiplist checks these values using the same engine as the drawing.

Follow the pointers

L0∅L1∅L2∅L3∅ 1 2 4 7 1 1 2 1 1 2 3 1 1 1 1 1 1 1 0 H 7 12 19 26 31 42 58 73

Start at H on L3. Target: 42.

Nodes: 8 seed: 7

Numeric-key teaching model, capped at 4 levels. H is the header; ∅ is null. Promotion uses a seeded PRNG; insertion uses height 2. Not Redis performance or its memory layout. Scroll the diagram horizontally on a phone.
Read the complete initial trace
  1. Start at H on L3. Target: 42.
  2. The next key is 58; do not cross it. Stay at H and descend to L2.
  3. H to 26: add span 4. Rank so far: 4.
  4. The next key is 58; do not cross it. Stay at 26 and descend to L1.
  5. 26 to 42: add span 2. Rank so far: 6.
  6. The next key is 58; do not cross it. Stay at 42 and descend to L0.
  7. The next key is 58; do not cross it. Check at L0.
  8. Found 42. Internal rank: 6; a zero-based rank is 5.

7 (h=1), 12 (h=2), 19 (h=1), 26 (h=3), 31 (h=1), 42 (h=2), 58 (h=4), 73 (h=1)

Header H has internal rank 0; the first element has rank 1, and 42 has rank 6 here. Redis’s internal rank and public ZRANK use different origins. ZRANK starts at zero, so the corresponding public rank is 5.4

A span is not a score difference. The gap from score 26 to score 42 does not matter; the number of nodes does. A span on a null link can count remaining base elements. Rank search never follows a null link, so it never adds that span.

A range query first finds its starting point, then follows L0 through the results. Returning MM elements still requires reading those MM elements. Omitting MM from ZRANGE’s O(log⁡N+M)O(\log N+M) hides the cost of large range reads.6

Insertion changes more than two pointers

An ordinary linked-list insertion adjusts the predecessor and the new node’s links. A skip list records the predecessor at each level in update[]. Redis also records the rank reached at those positions in rank[].4

Let the old link have span SS, and let dd be the number of base elements between this level’s predecessor and the insertion position. The split produces:

Sbefore→new=d+1,Snew→after=S−dS_{\text{before→new}}=d+1,\qquad S_{\text{new→after}}=S-d

Even higher levels that do not contain the new node must increment a crossing span by 1. Linking the node on its own levels and maintaining counts on every active level are different jobs.

The next explorer inserts 35 with height 2. Its last step highlights changed links and spans in terracotta. The L2 link 26 → 58 changes its span from 3 to 4 even though 35 has no L2 pointer. A count changes without a new link. Deletion reverses the adjustment.

Follow the pointers

L0∅L1∅L2∅L3∅ H 7 12 19 26 31 42 58 73

Start at H on L3. Target: 35.

Nodes: 8 seed: 7

Numeric-key teaching model, capped at 4 levels. H is the header; ∅ is null. Promotion uses a seeded PRNG; insertion uses height 2. Not Redis performance or its memory layout. Scroll the diagram horizontally on a phone.
Read the complete initial trace
  1. Start at H on L3. Target: 35.
  2. The next key is 58; do not cross it. Stay at H and descend to L2.
  3. Follow L2 to 26, which is below 35.
  4. The next key is 58; do not cross it. Stay at 26 and descend to L1.
  5. The next key is 42; do not cross it. Stay at 26 and descend to L0.
  6. Follow L0 to 31, which is below 35.
  7. The next key is 42; do not cross it. Check at L0.
  8. 35 is absent. The predecessor is 31.
  9. Insert 35 with height 2. Relink L0/L1 and update spans on every level.

7 (h=1), 12 (h=2), 19 (h=1), 26 (h=3), 31 (h=1), 35 (h=2), 42 (h=2), 58 (h=4), 73 (h=1)

The engine actually builds update[] and rank[] and updates links and spans. It is not a table of plausible-looking authored snapshots. Tests compare 2,000 insertions and deletions against a sorted set and verify that each span equals destination rank minus source rank. This verifies the teaching model, not the entire Redis C implementation.

QuizInserting a height-2 node

Choose an answer to see the explanation.

0 of 1 right

  1. A new node exists only on L0 and L1. What happens to an L2 link crossing its position?

A score update can stay in place

Changing a score in a large Redis sorted set does not always allocate a new node. zslUpdateScore checks whether the new score is strictly greater than the previous node’s score and strictly smaller than the next node’s score. At either end, the missing neighbor’s condition is omitted. If the test passes, it changes only score.4

Order is preserved, so links and spans remain unchanged. The dict’s pointer to that score field fits this path. If the condition fails, Redis deletes the old node and inserts one with the new score. The dict’s score pointer is adjusted on the new-node path.

The strict < and > checks are worth noticing. A change that ties a neighbor’s score requires member-byte ordering, so this shortcut does not decide it. A ZADD that repeats the existing score can instead skip the score-update path above this function.

Check the actual Redis behavior

The following Lua reproduction runs against standalone Redis 6.2.6 started with the default zset limits. It checks the ziplist boundary, tied ordering, score updates, deletion, and rejection of NaN input. A temporary 65-byte member converts the leaderboard key to skiplist encoding before that member is removed. It uses multiple keys, so it is neither a Cluster example nor a script to attach to a production server.

zset-contract.lua
local boundary = "skiplist-check:boundary"
local board = "skiplist-check:board"
redis.call("DEL", boundary, board)
for i = 1, 128 do
redis.call("ZADD", boundary, i, string.format("m:%03d", i))
end
assert(redis.call("OBJECT", "ENCODING", boundary) == "ziplist")
redis.call("ZADD", boundary, 129, "m:129")
assert(redis.call("OBJECT", "ENCODING", boundary) == "skiplist")
redis.call("ZREM", boundary, "m:129")
assert(redis.call("OBJECT", "ENCODING", boundary) == "skiplist")
local trigger = string.rep("x", 65)
redis.call("ZADD", board, 10, "charlie", 10, "alpha", 10, "bravo")
redis.call("ZADD", board, 0, trigger)
redis.call("ZREM", board, trigger)
assert(redis.call("OBJECT", "ENCODING", board) == "skiplist")
local ties = table.concat(redis.call("ZRANGE", board, 0, -1), ",")
assert(ties == "alpha,bravo,charlie")
assert(redis.call("ZRANK", board, "alpha") == 0)
assert(redis.call("ZRANK", board, "bravo") == 1)
assert(redis.call("ZRANK", board, "charlie") == 2)
redis.call("ZADD", board, 20, "alpha")
redis.call("ZADD", board, 21, "alpha")
redis.call("ZADD", board, 21, "alpha")
assert(redis.call("ZCARD", board) == 3)
assert(redis.call("ZSCORE", board, "alpha") == "21")
assert(redis.pcall("ZADD", board, "nan", "alpha").err)
assert(redis.call("ZSCORE", board, "alpha") == "21")
local moves = table.concat(redis.call("ZRANGE", board, 0, -1), ",")
assert(moves == "bravo,charlie,alpha")
redis.call("ZREM", board, "charlie")
local deleted = table.concat(redis.call("ZRANGE", board, 0, -1), ",")
assert(deleted == "bravo,alpha")
return {
"boundary: ziplist/skiplist",
"ties: " .. ties,
"ranks: 0,1,2",
"moves: " .. moves,
"delete: " .. deleted
}

In the blog source, python3 scripts/test-skiplist-redis.py --docker extracts this exact code block. It executes it in an isolated redis:6.2.6 container and removes the container afterward. The check for this article returned:

boundary: ziplist/skiplist
ties: alpha,bravo,charlie
ranks: 0,1,2
moves: bravo,charlie,alpha
delete: bravo,alpha

This output checks order and encoding. It cannot identify which C branch performed an in-place update or a reinsertion. That distinction comes from reading zslUpdateScore. Source inspection and reproduced external behavior are separate evidence.

LevelDB keeps nodes alive while readers use them

LevelDB 1.23’s memtable also contains a skip list. Its order is not Redis score order. Memtable entries contain internal keys; when user keys match, internal information such as sequence number participates in comparison. Sorting newer versions first supports lookup at a read’s sequence.7

Flushing a memtable to disk does not mean disk reads traverse a skip list. LevelDB’s SSTables have their own block-and-index format. A claim that an LSM storage engine uses skip lists needs to name the layer.8

The concurrency contract at the top of db/skiplist.h is specific. Writes require external synchronization; readers may run concurrently from other threads. The skip list must remain alive while a read runs. Nodes come from an Arena and are not individually deleted. They are reclaimed when the list is destroyed.3

When a reader can reach the new node

Predecessor next42
New node nextUnpublished
Reachable reader path26 → 42

Before insertion

The old link points to 42. A reader cannot reach the new node yet.

A single-link model of initialization and release/acquire publication in LevelDB 1.23. It measures no CPU time and is not a concurrency proof for the entire insertion.
All snapshots (also available without JavaScript)

Initialize, then publish

  1. Before insertion

    Predecessor next: 42 · New node next: Unpublished · Reachable reader path: 26 → 42

    The old link points to 42. A reader cannot reach the new node yet.

  2. Initialize new node

    Predecessor next: 42 · New node next: 42 · Reachable reader path: 26 → 42

    The writer first fills in 35's successor pointer.

  3. Publish with release

    Predecessor next: 35 · New node next: 42 · Reachable reader path: 26 → 35 → 42

    The predecessor link is published. The reader loads that link with acquire.

LevelDB’s Next() uses an acquire load; SetNext() uses a release store. Initializing links in a node that is not yet published can use relaxed stores. Saying “pointers are read atomically” does not explain when the pointed-to node’s initialization becomes visible.

The absence of deletion matters too. A reader’s node is not freed halfway through its read in this structure. Adding Redis-style spans and individual deletion does not inherit safety from this concurrency contract. The new fields and lifetime rules need their own design.

Concurrent skip lists have different contracts

OpenJDK 11’s ConcurrentSkipListMap separates base nodes from upper-level Index nodes. It has CAS update paths, deletion markers, and code that helps pending deletions. It is not the LevelDB arrangement of externally synchronized writes and no individual deletion.9

The source comments identify the base-list deletion algorithm as Harris and Michael’s HM algorithm. Fraser is cited as related work. A name in the bibliography does not mean the implementation directly adopts that paper’s algorithm.9

The implementation comments describe locating values in the base list and using upper indexes as search aids. During competing updates, a node can temporarily be absent from the index without making its base-list value unfindable. The earlier property returns here: height does not decide whether an answer exists.

Fraser’s Practical lock-freedom addresses memory reclamation as well as CAS-based structures. Unlinking a node and establishing when no other thread can reference it are different operations. A Java implementation relying on GC and a C/C++ implementation managing lifetimes cannot be treated as equivalent because their pointer diagrams look similar.10

ImplementationWhat is ordered?Updates and lifetime to inspect
Redis 6.2.6 zsetScore, then member bytesDict and spans are maintained together; individual deletion is supported. The skip list itself is not a general concurrent container.
LevelDB 1.23 memtableInternal keysWrites are externally synchronized. Readers require a live structure; there is no individual deletion.
OpenJDK 11 ConcurrentSkipListMapKey comparatorBase/index separation, CAS, deletion assistance, and GC belong in the explanation.

Sharing the name skip list does not make these implementations share concurrent-write support or safe deletion during reads.

Lock-free also does not mean every call finishes within a bounded number of steps. System-wide progress and per-call completion guarantees are different. One call can retry for a long time under contention; that is part of the distinction from wait-free.10

The papers go beyond rank to fingers and merging

Pugh’s A Skip List Cookbook covers rank operations, search fingers, merge, split, and concatenation in addition to search and insertion. Where requests begin and how they follow one another can change the algorithms worth using.11

A finger remembers a position near the previous search. The report analyzes expected O(log⁡k)O(\log k) search for a target kk positions away. The premise differs from restarting every search at the header. Redis’s ZRANK does not automatically inherit this bound.

Merge work also depends on how interleaved the inputs are. If every value in one list comes after the other, concatenation fits. The Cookbook’s merge analysis distinguishes input arrangements like this. Walking both base lists to their ends is not the only possible merge algorithm.

Research can remove randomness too. Munro, Papadakis, and Sedgewick’s Deterministic Skip Lists maintains conditions on gaps between levels and adjusts heights to obtain worst-case logarithmic bounds. Those guarantees do not appear in an implementation merely because it samples random heights.12

What workload do you have? Ranks and ranges Search near the last position Concurrent updates Worst-case time bound Span-augmented index Search with a maintained finger Publication and reclamation Deterministic gap-maintaining variant

Choosing a skip list does not supply all these features. Choose an implementation that supports the required operation. Combining a Cookbook algorithm, a storage engine’s lifetime contract, and a concurrent map’s progress guarantee into one description attributes behavior that the code may not have.

Check the implementation against the job

For a leaderboard, start with member lookup, tie ordering, and whether rank is required. A sorted map without spans may scan ranges without answering rank at the same cost.

For a memtable, ask whether individual nodes must be deleted. Reclaiming a structure as a whole and deleting nodes at arbitrary times need different reader protection. Comparing against arrays or B-trees also takes more than an O(log⁡n)O(\log n) label. Check pointer-chasing memory access, contiguous layout, and result-scan length for the actual workload.

QuizApply it to another workload

Choose an answer to see the explanation.

0 of 3 right

  1. You want to add a rank operation to a skip-list map without spans. What should you inspect first?

  2. You copy LevelDB's reader path but add immediate free of individual nodes. Are acquire/release pointers enough?

  3. Redis quickly finds the start of a range. Does returning 10,000 results also take logarithmic time?

Keep these in mind when reading source

Click a card to flip it.

0 of 6 flipped

Notes

  1. William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, Communications of the ACM, 1990. This links a PDF mirror; the publication record is DOI 10.1145/78973.78977. Table 1 confirms pointer counts and normalized search cost. The author’s original PDF URL returned 404 during verification. ↩ ↩2 ↩3 ↩4

  2. Redis 6.2.6 server.h: ZSKIPLIST_MAXLEVEL, ZSKIPLIST_P, zskiplistNode, zset. ↩ ↩2

  3. LevelDB 1.23 db/skiplist.h: introductory contract, Node::Next, Node::SetNext, RandomHeight, Insert. Maximum height 12 and branching factor 4 are from this tag. ↩ ↩2

  4. Redis 6.2.6 t_zset.c: zslRandomLevel, zslInsert, zslDeleteNode, zslUpdateScore, zslGetRank, zsetAdd, zrankGenericCommand. ↩ ↩2 ↩3 ↩4 ↩5 ↩6

  5. Redis 6.2.6 redis.conf: zset-max-ziplist-entries, zset-max-ziplist-value. The test runner explicitly sets these default boundaries at server startup. ↩

  6. Redis ZRANGE documentation: O(log⁡N+M)O(\log N+M). This cites the current command documentation for complexity; the execution target is 6.2.6. ↩

  7. LevelDB 1.23 db/memtable.cc and db/dbformat.h: KeyComparator, InternalKeyComparator. ↩

  8. LevelDB 1.23 doc/table_format.md: data blocks and index blocks. ↩

  9. OpenJDK jdk-11+28 ConcurrentSkipListMap.java: implementation comments, Node, Index, and search/insertion/deletion paths. ↩ ↩2

  10. Keir Fraser, Practical lock-freedom, University of Cambridge technical report 579, 2004. Covers skip lists, progress guarantees, and memory reclamation. ↩ ↩2

  11. William Pugh, A Skip List Cookbook, CS-TR-2286.1 / UMIACS-TR-89-72.1. Finger search and linear-list operations were checked in the university repository PDF. Rank, finger, and merge guarantees need the assumptions of their respective algorithms. ↩

  12. J. Ian Munro, Thomas Papadakis, Robert Sedgewick, Deterministic Skip Lists, SODA 1992. The author-hosted PDF describes variants guaranteeing logarithmic search, insertion and deletion. Not every variant in the paper has the same update cost. ↩

ko.mdx

단축키Keyboard

/ ⌘K
글 검색Search posts
t
밝은/어두운 테마Light or dark theme
l
한국어/영어, 읽던 자리 유지Korean or English, keeping your place
[ ]
이전/다음 절Previous or next section
?
이 목록This list

↑↓ 이동move↵ 열기openesc 닫기close