Redis ZSET — 왜 대기열엔 heap이 아니라 skip list인가
목표: "skip list가 빠르다"를 넘어 "어떤 워크로드에서, 왜, 몇 배나, 어떤 메커니즘 때문에" 까지 설명하고, 그걸 벤치마크로 증명할 수 있게 만들기.
관련: queue (우선순위 큐·heap의 제자리) / cache (Redis in-memory) / thread (단일 스레드 & 락-프리 설계)
한 줄 결론(블로그 마지막 문장감):
heap이 나쁜 게 아니다. 대기열은 '우선순위 큐'가 아니라 '순위 조회 시스템'이라서 도구가 안 맞았던 것이다. 워크로드가 자료구조를 결정한다.
§0. 문제 제기 — MyRedis는 왜 느렸나
대기열(waiting queue / leaderboard)의 요청 분포를 실제로 뜯어보면:
- 유저당 진입 1번 (
ZADD) - 유저당 폴링 수십~수백 번 (
ZRANK— "나 지금 몇 번째야?") - 최상위 처리 (
ZPOPMIN) — 상대적으로 드묾
즉 **전체 연산의 95%+가 순위 조회(ZRANK)**다. 그런데 heap 기반 구현에서 ZRANK는 하필 **O(N)**이다.
100만 명 대기 중, 폴링 한 번:
heap → 최대 100만 번 선형 순회
skip list → 약 20번 점프 (log₂ 1,000,000 ≈ 20)
MyRedis가 느렸던 이유가 수식으로 나온다. "느낌"이 아니라 워크로드 × 연산 복잡도의 곱이 병목이었다.
§1. 두 구조의 근본 차이
Heap = "느슨한 정렬"
배열 기반 완전 이진 트리. 보장하는 불변식은 딱 하나 — 부모 ≤ 자식(min-heap 기준).
1
/ \
3 2
/ \ / \
7 8 5 9
- 아는 것: 루트가 최솟값 그거 하나.
- 모르는 것: 형제끼리 대소 관계 (3과 2 중 뭐가 큰지 heap은 신경 안 씀).
- 배열
[1,3,2,7,8,5,9]을 그대로 읽어도 정렬 순서가 아니다.
→ heap은 "최솟값 하나"에 모든 걸 최적화하고 나머지를 포기한 구조다. 그리고 대기열은 하필 그 "나머지"(중간 순위 조회)를 제일 많이 쓴다.
Skip list = "완전 정렬 + 고속도로"
바닥층은 그냥 정렬된 연결 리스트(전체가 항상 순서대로 누워 있음). 그 위에 확률적으로(보통 p=0.25) 노드를 승격시켜 만든 익스프레스 레인이 여러 층 얹혀 있다.
L3: 1 ─────────────────────────────▶ 50
L2: 1 ──────────▶ 20 ──────────────▶ 50 ────────▶ 90
L1: 1 ─▶ 7 ─▶ 20 ─▶ 35 ─▶ 50 ─▶ 71 ─▶ 90 (바닥층: 완전 정렬)
탐색은 꼭대기에서 시작해서 규칙 하나만 반복:
"다음 노드가 목표보다 크면 → 한 층 내려가기. 아니면 → 오른쪽으로 전진."
이건 정렬된 리스트 위에서 이진 탐색을 흉내내는 것이라 기대 시간복잡도 O(log N).
핵심 대비:
| heap | skip list | |
|---|---|---|
| 정렬 정도 | 느슨 (부모-자식만) | 완전 정렬 (바닥층) |
| 최적화 대상 | 최솟값 1개 | 전 구간 탐색/순회 |
| 값으로 노드 찾기 | 불가 (선형 탐색) | O(log N) |
| 범위 순회 | 불가 (파괴적) | 바닥층 따라가기 |
§2. 연산별 비교 (대기열 기준)
| 연산 | Redis 커맨드 | Heap | Skip list |
|---|---|---|---|
| 진입 | ZADD |
O(log N) | O(log N) |
| 최상위 꺼내기 | ZPOPMIN |
O(log N) ✓ | O(log N) |
| 내 순번 확인 | ZRANK |
O(N) ✗ | O(log N) ✓ |
| 상위 k명 조회 | ZRANGE 0 k |
O(k log N)* | O(log N + k) |
| 특정 유저 제거(이탈) | ZREM |
O(N) 탐색 필요 ✗ | O(log N) |
| 점수 갱신 | ZADD(기존) |
O(N) + O(log N) | O(log N) |
* heap으로 상위 k명 "조회"는 pop k번 후 되돌려 넣거나 힙 전체 복사 — 어느 쪽이든 파괴적이거나 비싸다.
heap이 이기는 칸이 한 칸도 없다. ZPOPMIN조차 비김. 대기열의 킬러 연산인 ZRANK/ZREM에서 O(N)으로 무너진다.
§3. 핵심 메커니즘 1 — heap은 왜 ZRANK가 O(N)인가
user:777의 순위를 heap에서 구하려면?
- 위치조차 못 찾는다. heap엔 "값으로 노드를 찾는" 능력 자체가 없다 → 배열 선형 탐색이 유일. O(N).
- 설령 인덱스를 찾아도 그 인덱스가 순위가 아니다. 형제는 무순서니까.
- "이 값보다 작은 원소가 몇 개인가"를 알려면 → 결국 전부 세봐야 한다. O(N) 확정.
ZREM(이탈 유저 삭제)도 같은 병에 걸린다. 지우려면 먼저 O(N)으로 찾아야 하니까. 삭제 자체(sift)는 O(log N)이지만 앞단 탐색이 발목을 잡는다.
heap의 O(1)
peek은 "최솟값 하나"에만 주어진 특권이다. 나머지 N-1개 원소는 heap 입장에서 주소 없는 익명 집합이다.
§4. 핵심 메커니즘 2 — skip list는 왜 O(log N)에 순위가 나오나 (span)
주의: 순수(교과서) skip list도 사실 순위는 못 구한다. 탐색 경로만으로는 "내가 몇 칸째 노드인지"를 알 방법이 없다.
Redis가 쓰는 건 각 forward 포인터에 span(그 점프가 바닥층 기준 몇 칸을 건너뛰는지)을 저장한 변형이다.
L2: 1 ──(span 2)──▶ 20 ──(span 2)──▶ 50
L1: 1 ─(1)─▶ 7 ─(1)─▶ 20 ─(1)─▶ 35 ─(1)─▶ 50
50을 탐색하면서 지나온 span을 누적하면:
1 → 20 (span 2) → 50 (span 2) 누적 = 2 + 2 = 4
∴ 50은 4번째 (0-based rank = 3)
탐색 경로가 곧 순위 계산이라 추가 비용이 0이다. 이게 span의 마법.
ZRANGE start k도 마찬가지:
- span 누적으로 시작 위치까지 점프 (O(log N))
- 바닥층 forward 포인터 따라 k개 수집 (O(k)) → O(log N + k).
삽입/삭제 시 span 갱신 (버그 최다 발생 지점 ⚠️)
새 노드를 삽입하면, 탐색하며 지나온 각 층의 직전 노드들의 span이 이렇게 바뀐다:
삽입 전: A ──(span 5)──────────────▶ B
삽입 후 (내가 A에서 3칸 뒤에 들어감):
· 내가 승격된 층: A ─(span 3)─▶ [나] ─(span 3)─▶ B (5가 3+3으로 쪼개짐, 총합 유지 → 새 노드 만큼 +1 반영)
· 내가 승격 안 된 상위층: A ──(span 6)──▶ B (그냥 span만 +1, 아래에 노드 하나 늘었으니)
- 승격된 층: 직전 노드 span이 "내 앞까지 / 내 뒤부터"로 쪼개진다.
- 승격 안 된 상위층: 그 구간 아래에 노드가 하나 늘었으니 span만 +1.
삭제는 반대로 span을 합친다(내 앞 span + 내 뒤 span - 1).
🔒 불변식 테스트 (MyRedis에 꼭 넣을 것)
"모든 층에서 (그 층 각 노드의 span 합) == 바닥층 노드 수"
삽입/삭제 직후 이 불변식을 검증하는 assert를 넣어두면 span 갱신 버그를 조기에 잡는다. 각 층은 결국 바닥층 전체를 "몇 칸씩 건너뛰며 완전히 덮는" 파티션이어야 하기 때문.
// 테스트 골격
for (int level = 0; level < maxLevel; level++) {
long sum = 0;
for (Node n = head; n.forward[level] != null; n = n.forward[level])
sum += n.span[level];
assert sum == bottomLevelCount : "span 불변식 깨짐 @ level " + level;
}
§5. 핵심 메커니즘 3 — hash table 병행 (dict + skiplist)
Redis zset은 skip list 단독이 아니다. dict(member → score) + skiplist의 **쌍(pair)**이다.
| 연산 | 어디서 처리 | 복잡도 |
|---|---|---|
ZSCORE (내 점수) |
dict | O(1) |
ZRANK / ZRANGE |
skip list | O(log N) |
ZADD (기존 유저 점수 변경) |
dict → skiplist | O(log N) |
ZADD로 기존 유저 점수를 바꿀 때의 흐름:
1. dict에서 옛 score를 O(1)로 조회
2. skip list에서 (옛 score, member)로 노드 삭제 ─┐ O(log N)
3. 새 score로 재삽입 ─┘
4. dict의 score 갱신
dict가 없으면 1번(옛 score 찾기)부터 막힌다. skip list에서 member로 노드를 찾는 건 O(N)이니까. 즉 dict는 "모든 연산의 시작점을 O(1)로 만들어주는" 장치다.
트레이드오프: 메모리를 약 2배 쓴다(같은 member/score를 양쪽에 보관). 대신 모든 연산의 진입점이 상수 시간. → MyRedis에도 똑같이 dict를 병행해야 한다.
§6. 그럼 balanced tree(AVL/RB)는 왜 아닌가
RB-tree에 **서브트리 크기(size)**를 달면 순위도 O(log N)이 된다(order-statistics tree). 성능만 보면 skip list와 대등하다. 그런데 Redis 저자 antirez가 skip list를 고른 이유:
- 구현이 압도적으로 단순. RB-tree의 회전 + 리컬러링 지옥 vs skip list의 "코인 던지기(랜덤 레벨)". 디버깅 난이도 차이가 크다.
- 범위 순회가 자연스럽다.
ZRANGE가 바닥층 리스트를 그냥 따라가면 끝. 트리는 in-order 순회 상태를 들고 다녀야 한다. - 단일 스레드 + 락-프리라 확률적 균형으로 충분. 동시성 경합이 없으니 "최악의 경우 O(N)" 확률(사실상 0에 수렴)을 감수할 여유가 있다. → thread의 단일 스레드 이벤트 루프 맥락과 연결.
요지: 성능이 대등할 땐 "구현·유지보수 단순함"이 자료구조를 고른다. antirez의 실용주의.
§7. heap의 제자리 — 도구는 워크로드가 결정한다
heap이 나쁜 자료구조라는 게 아니다. heap이 압승하는 워크로드가 분명히 있다:
- 순수 우선순위 큐 — "최솟값 pop만 하고 중간 조회가 없는" 경우
- Kafka의 타이머(지연 메시지), OS 스케줄러의 ready queue, Dijkstra 최단 경로
- 캐시 지역성 — 배열 기반이라 포인터 추적이 없어 CPU 캐시에 친화적 → 상수 인자가 작다.
- 메모리 — 포인터/레벨 오버헤드가 없어 skip list보다 가볍다.
| 워크로드 | 승자 | 이유 |
|---|---|---|
| 최솟값만 계속 pop (스케줄러/타이머) | heap | O(log N) pop + 캐시 지역성 + 저메모리 |
| 중간 순위 조회가 대부분 (대기열) | skip list | ZRANK/ZREM O(log N) |
| 범위 순회 (리더보드 Top-N) | skip list | ZRANGE O(log N + k) |
→ queue 노트의 "우선순위 큐 = 내부적으로 heap" 항목과 짝지어 읽으면, **"같은 heap이 어디선 정답이고 어디선 오답인지"**가 완성된다.
§8. 벤치마크 설계 — 무엇을 측정할 것인가
이론을 "몇 배"라는 숫자로 바꾸는 단계. 가설을 먼저 적어두고 실측과 비교하는 형식으로 쓰면 글 완성도가 확 오른다.
① N 스케일링 (메인 샷) 📈
- N = 1만 / 10만 / 100만 채워두고
ZRANK를 10만 번 → 평균 / p99 비교. - 예상: heap은 N에 선형으로 악화, skip list는 거의 평평.
- 그래프에서 **직선(heap) vs 수평선(skip list)**으로 극적으로 갈릴 것.
- 가설: N=100만에서 ZRANK 수백~수천 배 차이.
② 혼합 워크로드 (현실성) 🎯
- 실제 비율로 섞기:
ZADD 5% + ZRANK 90% + ZPOPMIN 5% - 전체 처리량(ops/sec) 비교 → "이론이 아니라 대기열 워크로드에서 몇 배"를 뽑는다.
③ 대조군 (서사 완성) ⚖️
ZPOPMIN만 단독 비교 → 여기선 heap도 안 밀린다는 걸 보여준다.- 이게 있어야 "무조건 skip list 승"이 아니라 **"워크로드가 자료구조를 결정한다"**는 서사가 완성됨.
④ 진짜 Redis 대조 (겸손 + 다음 숙제) 🪞
- 같은 벤치를 실제 Redis에도 돌려서 MyRedis와의 갭 확인.
- 갭의 원인(직렬화, 자료구조 상수 인자, JIT 등)이 곧 다음 개선 과제.
도구
- JVM이면 JMH — 워밍업/측정 반복/데드코드 제거를 알아서 처리. 손으로
System.nanoTime()재면 JIT 워밍업 때문에 숫자가 거짓말을 한다. - 측정 대상 N을 파라미터화(
@Param), 각 연산을 별도@Benchmark로.
가설표 (실측 채우기 전에 먼저 작성)
┌──────────┬───────────┬──────────────┬─────────────┐
│ N │ heap ZRANK│ skiplist ZRANK│ 예상 배수 │
├──────────┼───────────┼──────────────┼─────────────┤
│ 10,000 │ ? │ ? │ ~수십 배 │
│ 100,000 │ ? │ ? │ ~수백 배 │
│ 1,000,000│ ? │ ? │ ~수천 배 │
└──────────┴───────────┴──────────────┴─────────────┘
§9. MyRedis 구현 체크리스트
- dict(member→score) 병행 — 모든 연산 진입점 O(1) (§5)
- skip list 노드에 span 필드 (레벨별) — ZRANK/ZRANGE용 (§4)
- 삽입 경로의
update[](각 층 직전 노드) +rank[](각 층까지 누적 순위) 추적 - 삽입 시: 승격층 span 쪼개기, 미승격 상위층 span +1 (§4)
- 삭제 시: span 합치기 (앞 + 뒤 - 1)
-
ZADD기존 유저: dict로 옛 score 조회 → 삭제 → 재삽입 (§5) - 랜덤 레벨 생성기 (
p=0.25, 최대 레벨 상한) - 불변식 assert: 층별 span 합 == 바닥층 노드 수 (§4)
- 동점(score 같을 때) 처리 — member 사전순 tie-break (Redis 규약)
§10. 토론 주제 모음
Q1. skip list는 확률적 자료구조인데, 최악의 경우 O(N)이 될 수 있다. 프로덕션에서 왜 문제 안 되나? → 힌트: N=100만에서 최악 케이스가 나올 확률은 사실상 0에 수렴. 게다가 단일 스레드라 한 요청이 잠깐 느려도 락 경합으로 번지지 않음(thread). 확률적 보장 vs 결정적 보장의 실무적 타협.
Q2. span을 안 쓰고도 순위를 구하는 방법이 있을까? → 힌트: 매번 바닥층을 처음부터 세면 O(N) — 그럼 heap과 똑같아진다. span은 "탐색하면서 공짜로 순위를 계산"하는 게 핵심. 순위가 필요 없는 워크로드면 span은 오버헤드.
Q3. dict 없이 skip list만으로 zset을 구현하면 뭐가 깨지나?
→ 힌트: ZSCORE가 O(1)→O(log N), ZADD 기존 유저의 "옛 score 찾기"가 O(N)으로 붕괴. 메모리는 아끼지만 진입점을 다 잃음.
Q4. 대기열에 유저가 100만 명일 때, 모두가 1초마다 ZRANK 폴링하면?
→ 힌트: 초당 100만 ZRANK. skip list라도 log N × 100만 = 부담. 폴링을 pub/sub 푸시로 바꾸거나, 순위를 근사치(버킷)로 주거나, 클라이언트 폴링 주기를 늘리는 설계 레벨 최적화가 필요. 자료구조만으론 못 막는 지점.
Q5. heap이 이기는 ZPOPMIN 대조군을 굳이 벤치에 넣는 이유는?
→ 힌트: "skip list 만능"이라는 인상은 오히려 신뢰를 깎는다. heap이 이기는 지점을 정직하게 보여줘야 "워크로드가 도구를 결정한다"는 결론에 설득력이 생김. 반례를 포함한 주장이 강한 주장.
Q6. 진짜 Redis가 MyRedis보다 빠르다면, 그 갭의 정체는? → 힌트: 자료구조는 같아도 상수 인자가 다름 — C vs JVM(GC, 박싱), 커맨드 파싱/직렬화, ziplist/listpack 같은 작은 zset 최적화(원소 적을 땐 아예 배열로), 메모리 레이아웃. 알고리즘 복잡도가 같아도 승부는 상수에서 갈린다.
아이디,비밀번호, 이름, 이메일
qatest01,qatest1234,QA테스트1, qatest01@hbrc-qa.test
qatest02,qatest1234,QA테스트02,qatest02@hbrc-qa.test
qatest03,qatest1234,QA테스트03,qatest03@hbrc-qa.test
qatest04,qatest1234,QA테스트04,qatest04@hbrc-qa.test
qatest05,qatest1234,QA테스트05,qatest05@hbrc-qa.test