Redis Sorted Set (ZSet) 들여다 보기

들어가며

개발을 하다보면 "정렬된 상태를 유지해야 하는" 상황을 꽤 자주 마주친다.

이런 문제를 처음 마주쳤을 때 "DB에서 ORDER BY 하면 되지 않나?"라는 생각이 들게 되는데,

트레픽이 많은 경우에 매번 테이블을 조회하여 정렬된 데이터를 가져오는 것은 부담이 될 수 있다.

 

Redis의 Sorted Set(ZSet)을 활용하면 이러한 문제에서 조금 자유로울 수 있다.

데이터를 넣는 순간부터 항상 정렬된 상태를 유지하여 따로 정렬할 필요가 없다.

---

ZSet이란 무엇인가

ZSet은 각 멤버(member)에 score라는 숫자 값을 부여하고, 항상 score 기준으로 정렬된 상태를 유지하는 자료구조다. 일반 Set에 "순서"라는 차원이 하나 더 추가된 것이라고 봐도 된다.

	Set	ZSet
중복 허용	❌	❌
순서 보장	❌	✅ (score 기준)
score	❌	✅

 

ZSet이 항상 보장하는 두 가지 성질이 있다.

유일성 — 같은 멤버는 하나만 존재한다. 이미 있는 멤버를 추가하면 score만 갱신

정렬 — 멤버는 score 오름차순으로 정렬된다. score가 동일하면 멤버 이름을 사전순으로 비교해 순서를 결정

 

단순해 보이지만, 이 두 성질을 삽입, 삭제가 발생할 때 마다 이를 위지하느 것은 꽤 부담이되어 보인다.

어떻게 이를 해결했을까?

---

내부 자료구조

ZSet의 성능 비결은 내부에서 두 가지 자료구조를 동시에 유지한다는 데 있다. 그 전에, 데이터 크기에 따라 구조 자체가 달라진다는 점을 먼저 이해하면 좋다.

인코딩 전략 — 작을 때와 클 때

ZSet은 데이터 규모에 따라 내부의 방식을 자동 전환한다.

멤버 수 ≤ 128  AND  각 멤버 크기 ≤ 64 bytes
  → listpack  (연속된 메모리 블록, 오버헤드 최소화)

그 외
  → skiplist + hashtable  (빠른 탐색과 조회를 위한 구조)

데이터가 적을 때는 단순한 연속 메모리 구조인 listpack을 써서 메모리를 절약한다.

그러다 임계값을 넘는 순간 자동으로 skiplist 기반 구조로 전환된다.

이 임계값은 zset-max-listpack-entries와 zset-max-listpack-value 설정으로 조정할 수 있다.

 

실제로 운영 환경에서 ZSet을 쓰다 보면 어느 시점부터 메모리 사용량이 갑자기 늘어나는 것처럼 보이는 경우

대부분 이 인코딩 전환이 일어난 시점이다.

---

Skip List — 정렬과 범위 조회 담당

임계값을 넘어서면 ZSet은 Skip List로 전환된다.

Skip List는 연결 리스트에 "지름길" 역할을 하는 포인터를 여러 레벨로 추가한 자료구조다.

레벨 4 │ ──────────────────────────────────── [100]
레벨 3 │ ─────────── [30] ────────────────── [100]
레벨 2 │ ──── [10] ─ [30] ──── [60] ───────── [100]
레벨 1 │ [5]─[10]─[20]─[30]─[40]─[60]─[80]─[100]
                       ↑ score 오름차순

탐색할 때는 레벨이 높은 곳에서 시작해 목표 범위를 빠르게 좁힌다.

노드의 레벨은 삽입 시 확률적으로 결정되는데, Redis는 레벨업 확률로 25%를 사용한다.

이 덕분에 균형 트리(AVL, Red-Black Tree)와 비슷한 O(log N) 성능을 내면서도 구현이 훨씬 단순하다.

 

Skip List는 범위 기반 탐색에 특히 강하다.

"score가 100 이상 500 이하인 멤버 전부"를 가져오는 ZRANGEBYSCORE 같은 명령이 빠른 이유다.

연결 리스트 특성상 범위 내 다음 노드를 순서대로 따라가면 되기 때문이다.

 

span 필드

Redis의 Skip List는 각 포인터에 span이라는 값을 저장한다.

span은 그 포인터가 건너뛰는 노드 수를 의미한다. 포인터를 따라 이동하면서 span 값을 누적하면,

별도의 계산 없이 탐색과 동시에 rank(순위)를 구할 수 있다.

이 덕분에 ZRANK나 ZREVRANK가 O(log N)에 동작할 수 있다.

---

 

Hash Table — score 단건 조회 담당

Skip List는 범위 조회에 강하지만, "alice의 score가 정확히 얼마냐"는 질문에는 O(log N)이 걸린다.

전체 리스트를 탐색해야 하기 때문이다.

 

이걸 해결하기 위해 Redis는 member → score 매핑을 담은 Hash Table을 병행해서 유지한다.

Hash Table 덕분에 ZSCORE 명령은 O(1)에 답을 준다.

Hash Table │ { "alice": 1500.0, "bob": 1320.0, "carol": 1750.0 }
Skip List  │ bob(1320) → alice(1500) → carol(1750)

두 구조는 쓰기(삽입·삭제·갱신)가 일어날 때마다 함께 업데이트 된다.

쓰기 비용이 조금 늘어나지만, 읽기 패턴이 다양한 ZSet의 특성에 적합한 트레이드오프로 볼 수 있다.

 

결과적으로

범위 조회는 Skip List가, score 단건 조회는 Hash Table이 담당한다.

---

/* check if the element is too large or the list
 * becomes too long *before* executing zzlInsert. */
if (zzlLength(zobj->ptr)+1 > server.zset_max_listpack_entries ||
    sdslen(ele) > server.zset_max_listpack_value ||
    !lpSafeToAdd(zobj->ptr, sdslen(ele)))
{
    zsetConvertAndExpand(zobj, OBJ_ENCODING_SKIPLIST, zsetLength(zobj) + 1);
} else {
    zobj->ptr = zzlInsert(zobj->ptr,ele,score);
    if (newscore) *newscore = score;
    *out_flags |= ZADD_OUT_ADDED;
    return 1;
}

 

위 소스는 실제 레디스 소스를 일부 가져온 것인데, 특정 임계 치를 넘어가게 되면 Zset의 구조를 전환하는 코드를 확인할 수 있다(zsetConvertAndExpand)

---

 

 

마치며

ZSet은 정렬된 데이터를 빠르게 가져올 때 쉽게 사용하는데, 그 안에는 Skip List와 Hash Table을 역할에 따라 나눠 쓰는 꽤 정교한 설계가 들어 있다.

동작 구조를 살펴보니 해당 자료구조에 대한 이해도를 높일 수 있었고, 이를 통해 개발이나 운영 때 이러한 전환 구조에 따른 변화를 고려하고 참고 할 수 있을 것 같다.

 

 

참고

1) https://redis.io/docs/latest/develop/data-types/sorted-sets

2) https://github.com/redis/redis/blob/unstable/src/t_zset.c