Redis Sorted Set으로 랭킹보드 구현

서론

랭킹 보드를 구현해야 하는 요구사항이 있을 때, 이를 어떻게 효율적으로 구현할 수 있을까? 가장 단순하게는 데이터베이스에서 집계성 테이블이나 배치 과정을 통해 랭킹 정보를 가져오는 방법이 있을 것이다. 주간 또는 일간 랭킹 정보를 특정한 간격마다 배치 작업을 통해 갱신하는 방식은 비교적 낮은 DB 비용으로 처리할 수 있다.

하지만, 실시간으로 변경되는 데이터를 정렬하고자 한다면 어떻게 해야 할까? 수많은 데이터가 쌓인 DB 테이블에서 쿼리를 날려 집계하는 방법이 과연 효율적일까? 다음은 특정 로그나 정보가 담긴 테이블(row size = 40,000)에서 주간 value를 합산하여 랭킹을 가져오는 쿼리의 예시다.

explain analyze
SELECT user_id, nickname, SUM((log->> 'value')::int) AS totalValue
FROM SOME_TABLE
LEFT JOIN 
    user ON SOME_TABLE.user_id = user.user_id,
    jsonb_array_elements(SOME_TABLE.log)
WHERE date > (CURRENT_DATE - INTERVAL '7 days')
GROUP BY SOME_TABLE.user_id, user.nickname
ORDER BY totalValue DESC;

-> 
Sort (cost=5664.97..5759.22 rows=40000 width=25) (actual time=6.340..6.342 rows=2 loops=1)

이 쿼리는 40,000개의 row에서 주간 value를 집계하는 데 적지 않은 비용과 시간이 소요됨을 보여준다. 비록 실행된 이후에는 메모리에서 캐싱되어 빠르게 처리될 수 있지만(버퍼 풀), 데이터가 더 쌓이게 되면 이러한 방법은 최선의 선택이 아닐 수 있다.

그렇다면, 실시간으로 데이터를 집계하고 랭킹 보드를 관리하는 더 효율적인 방법은 무엇일까?

해당 포스트에서는 Redis의 Sorted Set을 활용한 효율적인 랭킹 보드 구현 방법을 다루고자 한다.

 

Sorted Set은 집합(Set)과 정렬된 리스트(Sorted List)의 기능을 결합한 강력한 데이터 구조이다. 정렬된 집합을 사용하면 고유한 요소 컬렉션을 저장하면서 각 요소에 점수 또는 순위를 할당할 수 있다. 이 점수는 집합 내 요소의 순서를 결정하는 데 사용되며, 정렬된 데이터가 필요한 응용 프로그램에 적합하다.

 

해시 테이블과 스킵 리스트 데이터 구조를 조합하여 구현된다. 해시 테이블은 값에 따라 요소에 빠르게 접근할 수 있도록 하며, 스킵 리스트는 점수를 기준으로 요소의 정렬 순서를 유지한다. 이러한 이중 구조 덕분에 Redis는 Sorted Set에서 효율적으로 작업을 수행할 수 있다.

실서버 환경에서는 해당 redis 데이터에 대해 백업이나, 랭킹 정보를 db에서 가져올 수 있도록 해야 한다.
(메모리 환경에서 랭킹 정보가 휘발되더라도 가져올 수 있기 위함.)

Sorted Set

Sorted Set의 특징

Sorted Set의 주요 특징 중 하나는 정렬된 순서를 유지하면서 요소를 동적으로 추가, 제거 또는 업데이트할 수 있다는 것. 요소를 부동 소수점 수로 된 점수와 함께 정렬된 집합에 삽입할 수 있으며, Redis는 이 점수를 사용하여 요소의 위치를 정렬된 집합 내에 배치한다. 동일한 값의 요소가 이미 존재하는 경우 해당 요소의 점수가 업데이트된다.

 

Redis의 Sorted Sets는 하나의 key에 여러 score와 value를 저장할 수 있는 데이터 구조이다. 여기서 value는 score에 따라 정렬되며, 중복되지 않는다. 만약 score가 같다면 value 자체로 정렬. Sorted Sets에서는 집합이라는 의미에서 value를 member라고 부른다. Sorted Sets는 주로 정렬이 필요한 경우에 사용된다.

 

• 고유성: 각 member는 고유해야 한다.
• 정렬: 각 member는 score에 따라 정렬되며, score가 동일한 경우 member 값에 따라 정렬
• 유연한 쿼리: 특정 범위의 score를 가진 member를 효율적으로 검색할 수 있다.

 

동일한 점수를 가진 요소가 있다면?

모든 요소가 고유하므로 동일한 요소가 반복될 수는 없지만, 동일한 점수를 가진 여러 다른 요소를 추가하는 것은 가능하다. 여러 요소가 동일한 점수를 가질 때, 이들은 사전순으로 정렬
(여전히 점수가 첫 번째 키로 사용되어 정렬되지만, 동일한 점수를 가진 모든 요소는 사전순으로 상대적으로 정렬된다.)

사용되는 사전순 정렬은 이진 정렬로, 문자열을 바이트 배열로 비교한다.

사용자가 모든 요소를 동일한 점수(예: 0)로 정렬된 집합에 삽입하면, 정렬된 집합의 모든 요소는 사전순으로 정렬된다. 그리고 ZRANGEBYLEX 명령어를 사용하여 요소에 대한 범위 쿼리가 가능하다.
(참고: ZRANGEBYSCORE 명령어를 사용하여 점수 범위에 따라 정렬된 집합을 쿼리 하는 것도 가능하다.)

ZADD

 

ZADD key [NX|XX] [GT|LT] [CH] [INCR] score member [score member ...] [ex seconds]

시간복잡도: O(log(N)), N은 sorted set의 집합 수

score의 정수 범위는 - (2^53)부터 +(2^53)이고, double 64-bit floating point number를 사용한다.

> 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

ZRANGE

ZRANGE key start stop [REV] [[BYSCORE|BYLEX] [LIMIT offset count]] [withscores]

score가 적은 것부터 조회된다. score가 같으면 member로 비교한다.
전체를 조회할 때는 0 -1을 사용한다.

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

역순으로 조회하려면 REV 옵션

> ZRANGE racer_scores 0 -1 REV

1) "Prickett"
2) "Castilla"
3) "Royce"
4) "Norem"
5) "Sam-Bodden"
6) "Ford"

(withscores 옵션을 사용하면 score가 표시)

> 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"

ZREVRANGE

 

위에서 ZRANGE는 작은 순으로부터 정렬하여 반환한다. 즉 점수가 낮은 요소가 제일 처음 반환되는데 점수가 높은 순으로 정렬하기 위해서는 ZREVRANGE 명령어를 사용할 수 있지만 6.2.0 버전부터 deprecated 되었으니 ZRANGE에 REV flag를 주어 사용하는 것이 좋을 듯하다.

시간복잡도: O(log(N)+M)

As of Redis version 6.2.0, this command is regarded as deprecated.
It can be replaced by ZRANGE with the REV argument when migrating or writing new code.

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

ZSCORE

요소의 score 조회
(예를 들어 내 점수 조회를 하고자 한다면 사용자의 user_id를 기입하여 조회할 수 있겠다.)

ZSCORE key member
시간 복잡도: O(1)

 

> ZSCORE racer_scores "Ford"
"6"
> ZSCORE racer_scores "Prickett"
"14"

ZRANK

ZRANK key member [WITHSCORE]
요소의 rank 반환
O(log(N))

 

ZREVRANK

ZREVRANK key member [WITHSCORE]
요소의 rank 반환(역순)

O(log(N))

> ZRANK racer_scores "Norem"
(integer) 0


> ZREVRANK racer_scores "Norem"
(integer) 3