Redis 정렬 집합

Redis 정렬 집합 (Redis sorted sets)

Redis **정렬 집합(sorted set)**은 연관된 점수(score)에 따라 정렬된 고유 문자열(member) 컬렉션이에요. 리더보드(leaderboard)나 슬라이딩 윈도우 기반 레이트 리미터처럼 "정렬된 상태를 유지해야 하는" 작업에 딱 맞아요. 집합과 해시의 특징을 섞은 타입이라고 생각하면 이해가 빨라요.

출처: Redis 공식 문서 — Redis sorted sets

정렬 집합이란?

Redis 정렬 집합은 연관된 점수(score)에 따라 정렬된 고유 문자열(member) 컬렉션이에요. 둘 이상의 문자열이 같은 점수를 가지면, 그 문자열들은 사전식(lexicographically)으로 정렬돼요.

정렬 집합의 사용 사례로는:

  • 리더보드(Leaderboards) — 예: 대규모 온라인 게임에서 최고 점수 목록을 쉽게 유지할 수 있어요.
  • 레이트 리미터(Rate limiters) — 특히 슬라이딩 윈도우 방식 레이트 리미터를 만들어 과도한 API 요청을 막을 수 있어요.

정렬 집합은 집합(Set)과 해시(Hash)의 중간이라고 생각할 수 있어요.

  • 집합처럼 정렬 집합은 고유하고 반복되지 않는 문자열 요소로 이뤄져요. 어떤 의미에서 정렬 집합도 집합이에요.
  • 하지만 집합의 요소는 순서가 없는데 비해, 정렬 집합의 모든 요소는 **부동 소수점 값인 점수(score)**와 연결돼요(그래서 해시와도 비슷하죠 — 요소마다 값이 매핑되니까요).
  • 게다가 정렬 집합의 요소는 항상 정렬된 상태로 저장돼요. 요청 시에 정렬하는 게 아니라, 정렬이 데이터 구조 자체의 특성인 거예요.

정렬 규칙은 다음과 같아요.

  • B와 A가 다른 점수를 가지면, A.score > B.score일 때 A > B.
  • B와 A가 정확히 같은 점수를 가지면, A의 문자열이 B의 문자열보다 사전식으로 더 크다면 A > B. (집합은 고유 요소만 가지므로 B와 A의 문자열은 같을 수 없어요.)

튜토리얼 (Tutorial)

모든 레이서와 그들이 첫 경주에서 얻은 점수를 추가해 볼게요.

> ZADD racer_scores 10 "Norem"
(integer) 1
> ZADD racer_scores 12 "Castilla"
(integer) 1
> ZADD racer_scores 8 "Sam-Bodden" 10 "Royce" 6 "Ford" 14 "Prickett"
(integer) 4

ZADD는 SADD와 비슷하지만, 추가할 요소 앞에 점수 인자를 하나 더 받아요. ZADD는 variadic이라 여러 score-value 쌍을 한 번에 지정할 수 있어요 (위 예제처럼요).

정렬 집합에서는 이미 정렬되어 있으므로, 점수순 레이서 목록을 반환하는 게 아주 간단해요.

구현 노트: 정렬 집합은 스킵 리스트(skip list)와 해시 테이블을 모두 포함하는 이중 포트 데이터 구조로 구현돼요. 그래서 요소를 추가할 때마다 Redis는 O(log(N)) 연산을 수행해요. 덕분에 정렬된 요소를 요청할 때 Redis는 아무 작업도 하지 않아도 돼요 — 이미 정렬되어 있거든요.

ZRANGE는 낮은 점수부터 높은 점수 순서(오름차순)이고, ZREVRANGE는 높은 점수부터 낮은 점수 순서(내림차순)예요.

> ZRANGE racer_scores 0 -1
1) "Ford"
2) "Sam-Bodden"
3) "Norem"
4) "Royce"
5) "Castilla"
6) "Prickett"
> ZREVRANGE racer_scores 0 -1
1) "Prickett"
2) "Castilla"
3) "Royce"
4) "Norem"
5) "Sam-Bodden"
6) "Ford"

참고: 0과 -1은 요소 인덱스 0부터 마지막 요소(-1)까지를 의미해요. -1은 LRANGE 명령과 동일하게 동작해요.

점수도 함께 반환하려면 WITHSCORES 인자를 사용해요.

> ZRANGE racer_scores 0 -1 withscores
 1) "Ford"
 2) "6"
 3) "Sam-Bodden"
 4) "8"
 5) "Norem"
 6) "10"
 7) "Royce"
 8) "10"
 9) "Castilla"
10) "12"
11) "Prickett"
12) "14"

범위 연산 (Operating on ranges)

정렬 집합은 범위(range) 연산도 할 수 있어요. 점수가 10 이하인 모든 레이서를 얻으려면 ZRANGEBYSCORE를 사용해요.

> ZRANGEBYSCORE racer_scores -inf 10
1) "Ford"
2) "Sam-Bodden"
3) "Norem"
4) "Royce"

음의 무한대(-inf)와 10 사이(양쪽 극단 포함)의 점수를 가진 요소를 모두 반환하라고 요청한 거예요.

요소를 제거하려면 ZREM에 레이서 이름을 넘기면 돼요. 요소의 범위를 제거하는 것도 가능해요. Castilla를 제거하고, 10점 미만인 모든 레이서도 제거해 볼게요.

> ZREM racer_scores "Castilla"
(integer) 1
> ZREMRANGEBYSCORE racer_scores -inf 10
(integer) 3

ZRANK 명령은 요소의 순위(rank)를 반환해요. 마지막 요소의 인덱스는 -1로 접근할 수 있어요.

> ZRANK racer_scores "Norem"
(integer) 2

사전식 점수 (Lexicographical scores)

모든 요소가 같은 점수를 가지면, 정렬 집합은 사전식 정렬된 문자열로 동작해요. 같은 점수일 때 요소는 사전식으로 정렬되니까요. ZRANGEBYLEX, ZREVRANGEBYLEX, ZRANGESTORE 같은 명령을 쓸 수 있어요.

> ZADD myzset 0 a 0 b 0 c 0 d
(integer) 4
> ZRANGEBYLEX myzset - + 
1) "a"
2) "b"
3) "c"
4) "d"
> ZRANGEBYLEX myzset [b [c
1) "b"
2) "c"

참고: 사전식 연산은 요소들이 전부 같은 점수를 가질 때만 잘 정의돼요(확인 필요). 실제로 이 명령들은 같은 점수를 가진 요소 집합에서 문자열 비교를 기준으로 동작해요.

ZRANGE 명령에 BYLEX 옵션을 쓰는 방식으로도 사전식 연산을 할 수 있어요 (Redis 6.2+). 이 문법은 스코어 범위(BYSCORE) 대신 사전식 범위를 쓸 때 사용해요.

> ZRANGE myzset - + BYLEX
1) "a"
2) "b"
3) "c"
4) "d"

예제 (Examples)

리더보드를 표현하는 방법은 두 가지예요.

  • 레이서의 새 점수를 아는 경우: ZADD로 직접 갱신해요.
  • 기존 점수에 점수를 더하는 경우: ZINCRBY를 사용해요.
> ZADD racer_scores 100 "Wood"
(integer) 1
> ZADD racer_scores 100 "Henshaw"
(integer) 1
> ZADD racer_scores 150 "Henshaw"
(integer) 0
> ZINCRBY racer_scores 50 "Wood"
"150"
> ZINCRBY racer_scores 50 "Henshaw"
"200"

여기서 볼 수 있듯이 ZADD는 멤버가 이미 존재하면 0을 반환해요(점수는 갱신돼요). 반면 ZINCRBY는 새 점수를 반환해요. Henshaw의 점수는 100에서 시작해, 기존 값과 상관없이 150으로 바뀌고, 다시 50만큼 증가해 200이 됐어요.

비슷한 방식으로, 점수 순으로 정렬된 사용자와 get-rank 연산을 조합하면, 상위 N명 사용자와 사용자 본인의 순위를 리더보드에 보여줄 수 있어요 (예: "당신은 여기 #4932번째 최고 점수예요").

성능 (Performance)

  • 대부분의 정렬 집합 연산은 O(log(n)) 이에요. 여기서 n은 멤버 수예요.
  • ZRANGE 명령은 큰 반환 값(예: 수만 개 이상)을 다룰 때 주의해야 해요. 이 명령의 시간 복잡도는 O(log(n) + m) 이에요. 여기서 m은 반환되는 결과 수예요.

대안 (Alternatives)

  • Redis 정렬 집합은 다른 Redis 데이터 구조를 인덱싱하는 데 때때로 사용돼요. 데이터를 인덱싱하고 쿼리해야 한다면 JSON 데이터 타입과 Redis Search 기능을 고려해 보세요.

더 알아보기 (Learn more)