Redis Sorted Set - 이중 구조, 왜 이렇게 설계했을까?

들어가며

Redis는 String, List, Hash, Set, Sorted Set 이렇게 다섯 가지 기본 자료구조를 제공합니다. 이 중에서 Sorted Set은 가장 강력하면서도 오해받기 쉬운 자료구조입니다. 단순히 "정렬된 Set"이라고 생각하기 쉽지만, 실제로는 Skip List와 Hash Table이 결합된 복합 구조이며, 이 설계 덕분에 다른 자료구조로는 어려운 연산들을 효율적으로 수행할 수 있습니다.

이 글에서는 Sorted Set의 정의부터 내부 구현, 다른 자료구조와의 비교, 트레이드오프까지 학습한 내용을 차근차근 정리해보겠습니다.

---

Sorted Set이란?

Sorted Set은 member(고유한 문자열)와 score(부동소수점 숫자)의 쌍으로 구성된 집합입니다.

• member는 유일(unique) 값이며 같은 값을 다시 추가하면 score만 갱신
• score 기준으로 자동 정렬되며 score가 같으면 member의 사전순(lexicographical)
• score는 IEEE 754 64bit double 값으로 음수, 양수, 무한대 가능

member: "alice"  score: 100
member: "bob"    score: 85
member: "carol"  score: 95

위 데이터를 ZADD로 넣으면 내부적으로 score 오름차순으로 정렬되어 저장됩니다.

[bob:85] → [carol:95] → [alice:100]

이 한 줄 정의에서 Sorted Set의 모든 특성이 파생됩니다.

특성	파생되는 동작
member uniqueness	같은 값 재추가 시 score 업데이트 (Set의 성질)
score 정렬	범위 쿼리, 순위 조회 가능
양방향 매핑	member로 score 조회 O(1), score 범위로 member 조회 O(log N)

---

내부 구현 - 왜 두 자료구조를 같이 쓰일까?

Sorted Set은 단일 자료구조가 아닙니다. Skip List와 Hash Table 두 개를 동시에 운영합니다.

이중 구조

    ┌──────────────────────────────────────────┐
    │           Sorted Set                     │
    │                                          │
    │  ┌─────────────────┐  ┌───────────────┐  │
    │  │  Hash Table     │  │  Skip List    │  │
    │  │                 │  │               │  │
    │  │ member -> score │  │ score 순 정렬   │  │
    │  │   O(1) 조회      │  │    범위 쿼리    │  │
    │  └─────────────────┘  └───────────────┘  │
    └──────────────────────────────────────────┘

• Hash Table: member → score 매핑. ZSCORE alice 같은 단건 조회를 O(1)로 처리
• Skip List: score 순서로 노드를 정렬 보관. ZRANGEBYSCORE 80 100 같은 범위 쿼리를 O(log N + M)로 처리

두 구조는 항상 동기화된 상태를 유지합니다. ZADD 한 번에 양쪽 모두 갱신되므로 메모리는 더 쓰지만 모든 연산이 빨라집니다.

Skip List 구조

Skip List는 여러 레벨의 연결 리스트를 쌓아 만든 확률적 자료구조입니다.

Level 3:  HEAD ──────────────────→ [100] ──→ NIL
Level 2:  HEAD ──────→ [85] ─────→ [100] ──→ NIL
Level 1:  HEAD ──→ [70] → [85] ─→ [100] ──→ NIL
Level 0:  HEAD ──→ [70] → [85] → [95] → [100] → NIL

• 각 노드는 무작위로 레벨을 부여받음 (보통 평균 1.33 레벨)
• 상위 레벨에서 빠르게 점프해 검색 → 평균 O(log N)
• Balanced Tree와 달리 회전(rotation) 같은 복잡한 연산 불필요

listpack ↔ skiplist 자동 전환

데이터가 적을 때는 Skip List가 오히려 비효율적입니다. Redis는 작은 Sorted Set을 listpack(이전 버전의 ziplist)이라는 압축된 단일 메모리 블록에 저장하다가, 임계값을 넘으면 자동으로 skiplist 구조로 전환합니다.

설정	기본값	의미
zset-max-listpack-entries	128	항목 수가 이 값 이하면 listpack 사용
zset-max-listpack-value	64	한 member 크기(byte)가 이 값 이하면 listpack 사용

둘 중 하나라도 초과하면 skiplist로 전환되며, 한 번 전환된 후에는 다시 줄어들어도 listpack으로 돌아가지 않습니다.

Skip List를 선택한 이유

Redis 저자 antirez는 Balanced Tree(예: Red-Black Tree) 대신 Skip List를 선택한 이유를 다음과 같이 설명했습니다.

1. 메모리 효율: 메모리 효율 파라미터를 조정 가능 (확률 p, 평균 레벨)
2. 범위 쿼리 친화적: 가장 낮은 레벨이 그대로 정렬된 연결 리스트라 ZRANGE가 자연스럽게 빠름
3. 구현 단순성: RB-Tree의 회전 로직 없이 무작위 레벨링으로 균형 유지
4. lock-free 친화적: 동시성 확장이 비교적 단순

주요 연산 시간복잡도

연산	복잡도	설명
ZADD	O(log N)	Skip List에 삽입
ZREM	O(log N)	Skip List에서 제거
ZSCORE	O(1)	Hash Table 조회
ZRANGE	O(log N + M)	M = 반환 항목 수
ZRANGEBYSCORE	O(log N + M)	score 범위 조회
ZRANK	O(log N)	순위 조회
ZINCRBY	O(log N)	score 증감 (재정렬 포함)
ZREMRANGEBYRANK	O(log N + M)	범위로 일괄 삭제
ZCARD	O(1)	전체 개수

---

다른 자료구조와의 비교

Sorted Set이 강력한 이유는 다른 자료구조의 한계를 보면 명확해집니다.

요구사항	String	List	Hash	Set	Sorted Set	Stream
순서 유지	X	O (삽입순)	X	X	O (score순)	O (시간순)
범위 쿼리	X	인덱스만	X	X	O (score)	O (ID)
중복 제거	-	X	key 단위	O	O	X
점수 기반 정렬	X	X	X	X	O	X
임의 위치 효율 삭제	-	O(N)	O(1)	O(1)	O(log N)	제한적
영속성/Consumer	X	X	X	X	X	O

각 자료구조가 어디서 무너지는지 살펴보면 아래와 같습니다.

• List: 삽입순 보장은 되지만 "score 80 이상" 같은 조건 검색이 안 됨. 전체 스캔 필요
• Hash: 빠른 조회는 되지만 정렬·범위 개념 자체가 없음
• Set: 중복 제거는 되지만 순서가 없음
• Stream: ID 기반 시간순 조회는 가능하지만 임의 점수 기반 정렬, 점수 갱신 같은 동작은 부적합

"정렬된 상태로 무언가를 유지하고, 범위 또는 순위로 조회하고 싶다." 이 요구가 있으면 Sorted Set 외에는 답이 없습니다.

---

주요 연산과 사용 패턴

Sorted Set의 활용은 결국 score를 무엇으로 정의하느냐에 따라 달라집니다. 언제 사용하는지 사례를 통해 살펴봅시다.

1. 실시간 랭킹 (게임 리더보드)

• score = 점수, member = 유저 ID

ZADD leaderboard 1500 user:alice
ZADD leaderboard 2200 user:bob
ZADD leaderboard 1800 user:carol

ZREVRANGE leaderboard 0 9 WITHSCORES   # 상위 10명
ZREVRANK leaderboard user:alice        # alice의 순위
ZINCRBY leaderboard 100 user:alice     # alice 점수 +100, 자동 재정렬

수십만 명의 랭킹도 모든 연산이 O(log N)에 동작합니다.

2. 우선순위 큐 (Delayed Job Queue)

• score = 실행 예정 시각(unix timestamp), member = job ID

ZADD jobs 1735689600 job:001
ZADD jobs 1735689660 job:002

# 워커가 "지금 실행해야 할 작업" 조회
ZRANGEBYSCORE jobs -inf <현재시각>

가장 오래된 작업부터 자연스럽게 가져옵니다. RDB 폴링 방식보다 훨씬 가볍습니다.

3. 시계열 인덱싱

• score = timestamp, member = 이벤트 ID 또는 직렬화된 데이터

ZRANGEBYSCORE events <from_ts> <to_ts>
ZREMRANGEBYSCORE events -inf <만료_ts>   # 오래된 이벤트 정리

특정 시간 구간 이벤트를 빠르게 조회하거나, 오래된 데이터만 일괄 삭제할 때 유용합니다.

4. 슬라이딩 윈도우 Rate Limiter

• score = 요청 시각, member = 요청 ID(또는 timestamp 자체)

# 1분 동안 100회 제한
ZADD rate:user:123 <now> <now>
ZREMRANGEBYSCORE rate:user:123 -inf <now - 60>
ZCARD rate:user:123   # 100 초과면 거부

고정 윈도우 카운터의 경계 문제를 피할 수 있습니다.

5. 최근 N개 캐시

• score = sequence 또는 timestamp, member = 데이터

ZADD recent:session:42 17 "<event_payload_json>"
ZREMRANGEBYRANK recent:session:42 0 -51   # 최신 50개만 유지

ZADD로 추가 후 ZREMRANGEBYRANK로 오래된 항목을 잘라내면 항상 최신 N개만 유지됩니다.

---

트레이드오프와 함정

그렇다면, 실제로 어떤 트레이드오프가 있고 주의할점이 있을지 살펴보도록 합시다.

메모리 오버헤드

Skip List는 평균 1.33개의 포인터를 노드마다 저장하고, Hash Table까지 함께 운영하므로 단순 List/Hash 대비 메모리를 더 사용합니다. 데이터가 작을 때는 listpack으로 자동 최적화되지만, 임계값을 넘는 순간 메모리 사용량이 급증합니다.

멀티 명령은 원자적이지 않음

ZADD 후 ZREMRANGEBYRANK로 윈도우를 유지하는 패턴은 두 번의 네트워크 왕복이며, 그 사이에 다른 클라이언트가 끼어들 수 있습니다. 엄격한 원자성이 필요하면 MULTI/EXEC 또는 Lua 스크립트로 묶어야 합니다.

-- 원자적으로 추가 + 윈도우 유지
redis.call('ZADD', KEYS[1], ARGV[1], ARGV[2])
redis.call('ZREMRANGEBYRANK', KEYS[1], 0, -ARGV[3]-1)

score double 정밀도 한계

score는 IEEE 754 double이므로 정수는 2^53(약 9×10^15)까지만 정확히 표현됩니다. timestamp(밀리초 단위)나 일반적인 sequence라면 충분하지만, 나노초 단위 + 큰 base를 더하는 식으로 score를 만들면 정밀도 손실이 발생할 수 있습니다.

Cluster 환경의 단일 키 hot spot

Redis Cluster는 키를 슬롯에 분산시키지만, 하나의 Sorted Set은 하나의 슬롯에만 집중됩니다. 단일 키에 트래픽이 몰리면 해당 노드가 병목이 됩니다.

해결 방법

• 키를 도메인 단위로 분할 (예: leaderboard:region:KR, leaderboard:region:US)
• 읽기 부하면 Replica로 분산
• 키 자체가 핫하면 샤딩 키 설계 재검토

동일 score 처리

score가 같으면 member의 사전순(lexicographical)으로 정렬됩니다. 이를 활용한 ZRANGEBYLEX 연산도 있지만, 의도하지 않은 정렬 동작에 주의해야 합니다. 시간순을 보장하고 싶다면 score에 timestamp를 사용하거나 member에 정렬 가능한 prefix를 붙이는 방식이 안전합니다.

---

전체적으로 정리를 해보자면..

구분	내용
본질	member(unique) + score(double) 쌍의 정렬된 집합
내부 구현	Hash Table + Skip List 이중 구조 (작을 때는 listpack)
강점	정렬 유지, 범위 쿼리, 순위 조회를 O(log N)에 처리
약점	메모리 오버헤드, 멀티 명령 비원자성, 단일 키 hot spot

Sorted Set을 고려해볼 상황

• 정렬된 상태로 데이터를 유지해야 함
• score(점수, 시각, 우선순위) 기반 범위 쿼리가 필요
• 순위 조회나 점수 갱신이 빈번
• 항목 중복은 막되 score는 갱신해야 함

Sorted Set 굳이? 싶은 상황

• 단순 캐시 (String/Hash로 충분)
• FIFO/LIFO 큐 (List가 더 가벼움)
• 영속 메시지 큐 (Stream/Kafka가 적합)
• 단순 중복 체크 (Set으로 충분)

---

참고문서

• Redis 공식 문서