Redis 정렬 집합

Redis 정렬 집합 (Redis sorted sets) (sorted-sets)

Redis 정렬 집합(sorted sets)에 대한 소개를 정리할게요.

Redis 정렬 집합은 연관된 점수(score) 로 정렬되는 고유한 문자열(멤버)의 모음이에요. 둘 이상의 문자열이 같은 점수를 가지면 문자열이 사전식(lexicographically)으로 정렬됩니다. 정렬 집합의 사용 사례로는 다음이 있어요.

리더보드(Leaderboards). 예를 들어 정렬 집합을 사용하면 대규모 온라인 게임에서 최고 점수 목록을 쉽게 유지할 수 있어요.
레이트 리미터(Rate limiters). 특히 정렬 집합을 사용해 슬라이딩 윈도우 레이트 리미터를 만들어 과도한 API 요청을 막을 수 있습니다.

정렬 집합은 Set과 Hash 사이의 혼합체라고 생각할 수 있어요. 집합처럼 정렬 집합은 고유하고 반복되지 않는 문자열 원소로 구성되므로, 어떤 의미에서는 정렬 집합도 집합입니다.

다만 집합 안의 원소는 정렬되어 있지 않은 반면, 정렬 집합의 모든 원소는 점수(score) 라고 하는 부동소수점 값과 연관되어 있어요(모든 원소가 값에 매핑되므로 타입이 해시와도 비슷한 이유입니다).

게다가 정렬 집합의 원소는 순서대로 놓입니다(요청할 때 정렬되는 것이 아니라, 원소가 이미 순서대로 있다는 게 정렬 집합을 표현하는 데이터 구조의 특징입니다). 원소는 다음 규칙에 따라 정렬됩니다.

B와 A가 다른 점수를 가지는 두 원소라면, A.score > B.score일 때 A > B 입니다.
B와 A가 정확히 같은 점수를 가지면, A 문자열이 B 문자열보다 사전식으로 더 크면 A > B 입니다. 정렬 집합은 고유한 원소만 가지므로 B와 A 문자열은 같을 수 없어요.

간단한 예시부터 시작할게요. 모든 레이서(racer)와 첫 레이스에서 얻은 점수를 추가해 볼게요.

기초: 점수와 함께 정렬 집합에 멤버 추가하기(새 멤버 생성 또는 기존 멤버 갱신)

res1 = r.zadd("racer_scores", {"Norem": 10})
print(res1)  # >>> 1

res2 = r.zadd("racer_scores", {"Castilla": 12})
print(res2)  # >>> 1

res3 = r.zadd(
    "racer_scores",
    {"Sam-Bodden": 8, "Royce": 10, "Ford": 6, "Prickett": 14, "Castilla": 12},
)
print(res3)  # >>> 4

보시다시피 ZADD는 SADD와 비슷하지만, 추가할 원소 앞에 점수라는 인수를 하나 더 받아요. ZADD는 가변 인자(variadic)이기도 해서 위 예시처럼 여러 개의 점수-값 쌍을 자유롭게 지정할 수 있습니다.

정렬 집합에서는 점수 순으로 정렬된 레이서 목록을 반환하는 것이 매우 쉽습니다. 실제로 이미 정렬되어 있기 때문이에요.

구현 참고: 정렬 집합은 스킵 리스트(skip list)와 해시 테이블을 모두 담은 이중 포트(dual-ported) 데이터 구조로 구현되므로, 원소를 추가할 때마다 Redis는 O(log(N)) 연산을 수행합니다. 이는 좋은 점인데, 정렬된 원소를 요청할 때 Redis는 아무 작업도 하지 않아도 이미 정렬되어 있기 때문이에요. 참고로 ZRANGE 순서는 낮은 점수에서 높은 점수로, ZREVRANGE 순서는 높은 점수에서 낮은 점수로입니다.

ZRANGE와 ZREVRANGE로 오름차순 또는 내림차순 멤버 조회하기(이미 정렬되어 있어 정렬 불필요)

res4 = r.zrange("racer_scores", 0, -1)
print(res4)  # >>> ['Ford', 'Sam-Bodden', 'Norem', 'Royce', 'Castilla', 'Prickett']

res5 = r.zrevrange("racer_scores", 0, -1)
print(res5)  # >>> ['Prickett', 'Castilla', 'Royce', 'Norem', 'Sam-Bodden', 'Ford']

참고: 0과 -1은 원소 인덱스 0부터 마지막 원소까지를 의미합니다(-1은 LRANGE 명령에서처럼 동작해요).

WITHSCORES 인수를 사용하면 점수도 함께 반환할 수 있어요.

멤버와 연관 점수를 모두 필요로 할 때 WITHSCORES로 점수와 함께 멤버 조회하기

res6 = r.zrange("racer_scores", 0, -1, withscores=True)
print(
    res6
)
# >>> [
#       ('Ford', 6.0), ('Sam-Bodden', 8.0), ('Norem', 10.0), ('Royce', 10.0),
#       ('Castilla', 12.0), ('Prickett', 14.0)
# ]

정렬 집합은 이것보다 훨씬 강력해요. 범위(range)로 연산할 수 있습니다. 점수가 10 이하인 모든 레이서를 가져와 볼게요. ZRANGEBYSCORE 명령을 사용합니다.

점수 범위로 쿼리: 숫자 값으로 필터링해야 할 때 ZRANGEBYSCORE로 점수 범위 내 멤버 조회하기

res7 = r.zrangebyscore("racer_scores", "-inf", 10)
print(res7)  # >>> ['Ford', 'Sam-Bodden', 'Norem', 'Royce']

Redis에 음의 무한대에서 10 사이(양 끝 포함)의 점수를 가진 모든 원소를 반환하라고 요청한 것입니다.

원소를 제거하려면 레이서 이름과 함께 ZREM을 호출하면 돼요. 원소 범위를 제거하는 것도 가능합니다. 레이서 Castilla와 10점보다 엄격히 적게 가진 모든 레이서를 제거해 볼게요.

개별 원소는 ZREM, 점수 범위는 ZREMRANGEBYSCORE를 사용해 데이터를 삭제할 때 멤버 제거하기

res8 = r.zrem("racer_scores", "Castilla")
print(res8)  # >>> 1

res9 = r.zremrangebyscore("racer_scores", "-inf", 9)
print(res9)  # >>> 2

res10 = r.zrange("racer_scores", 0, -1)
print(res10)  # >>> ['Norem', 'Royce', 'Prickett']

ZREMRANGEBYSCORE는 그다지 좋은 명령 이름은 아닐지 몰라도 아주 유용하며, 제거된 원소의 개수를 반환합니다.

정렬 집합 원소에 대해 정의된 또 하나의 매우 유용한 연산은 랭크(rank) 가져오기입니다. 정렬된 원소 집합에서 어떤 원소의 위치(position)를 물어볼 수 있어요. 원소를 내림차순으로 정렬해 랭크를 얻는 ZREVRANK 명령도 있습니다.

멤버 위치 가져오기: 리더보드에 유용한 ZRANK와 ZREVRANK로 정렬 집합에서 멤버 위치 찾기

# Recreate the three remaining racers so this example runs on its own.
r.delete("racer_scores")
r.zadd(
    "racer_scores",
    {"Norem": 10, "Royce": 10, "Prickett": 14},
)

res11 = r.zrank("racer_scores", "Norem")
print(res11)  # >>> 0

res12 = r.zrevrank("racer_scores", "Norem")
print(res12)  # >>> 2

사전식 점수 (Lexicographical scores)

Redis 2.8 버전에서, 정렬 집합의 모든 원소가 동일한 점수로 삽입된다는 가정하에 사전식으로 범위를 얻을 수 있는 새로운 기능이 도입됐어요(원소는 C memcmp 함수로 비교되므로, 콜레이션(collation)이 없고 모든 Redis 인스턴스가 동일한 출력으로 응답함이 보장됩니다).

사전식 범위로 연산하는 주요 명령은 ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX, ZLEXCOUNT입니다.

예를 들어, 유명한 레이서 목록을 다시 추가하되 이번에는 모든 원소에 점수 0을 사용해 볼게요. 정렬 집합의 정렬 규칙 때문에 원소가 이미 사전식으로 정렬되어 있음을 알 수 있어요. ZRANGEBYLEX를 사용해 사전식 범위를 요청할 수 있습니다.

사전식 쿼리: 동일한 점수로 멤버를 추가하고 ZRANGEBYLEX로 문자열 범위로 쿼리하기(일반 인덱싱을 가능하게 함)

res13 = r.zadd(
    "racer_scores",
    {
        "Norem": 0,
        "Sam-Bodden": 0,
        "Royce": 0,
        "Ford": 0,
        "Prickett": 0,
        "Castilla": 0,
    },
)
print(res13)  # >>> 3

res14 = r.zrange("racer_scores", 0, -1)
print(res14)  # >>> ['Castilla', 'Ford', 'Norem', 'Prickett', 'Royce', 'Sam-Bodden']

res15 = r.zrangebylex("racer_scores", "[A", "[L")
print(res15)  # >>> ['Castilla', 'Ford']

범위는 (첫 문자에 따라) 포함하거나 배타적일 수 있고, 문자열 무한대와 음의 무한대는 각각 +와 - 문자열로 지정합니다. 자세한 내용은 문서를 참조하세요.

이 기능은 정렬 집합을 일반 인덱스(generic index) 로 사용할 수 있게 해주기 때문에 중요합니다. 예를 들어 128비트 부호 없는 정수 인수로 원소를 인덱싱하려면, 같은 점수(예: 0)를 가진 정렬 집합에 원소를 추가하되 빅 엔디안(big endian)의 128비트 숫자로 된 16바이트 접두사를 붙이기만 하면 되어요. 빅 엔디안 숫자는 (원시 바이트 순서로) 사전식으로 정렬하면 실제로 숫자적으로도 정렬되므로, 128비트 공간에서 범위를 요청하고 접두사를 버리면 원소의 값을 얻을 수 있습니다.

점수 갱신: 리더보드

다음 주제로 넘어가기 전에 정렬 집합에 대한 마지막 참고사항을 하나 남길게요. 정렬 집합의 점수는 언제든지 갱신할 수 있어요. 정렬 집합에 이미 포함된 원소에 대해 ZADD를 호출하기만 하면 O(log(N)) 시간 복잡도로 그 점수(와 위치)가 갱신됩니다. 따라서 정렬 집합은 갱신이 아주 많이 일어나는 상황에 적합합니다.

이 특징 때문에 대표적인 사용 사례가 리더보드입니다. 전형적인 예는 Facebook 게임으로, 최고 점수 순으로 정렬된 사용자를 가져오는 기능과 랭크 가져오기 기능을 결합해 상위 N명의 사용자와 사용자의 리더보드 순위를 보여줍니다(예: "여기서 당신은 #4932번째 최고 점수입니다").

예시

리더보드를 표현하기 위해 정렬 집합을 사용하는 방법은 두 가지가 있어요. 레이서의 새 점수를 안다면 ZADD 명령으로 직접 갱신할 수 있습니다. 다만 기존 점수에 점수를 더하고 싶다면 ZINCRBY 명령을 사용할 수 있어요.

실용 패턴: 원자적 연산으로 리더보드를 갱신해야 할 때 점수 설정은 ZADD, 증가는 ZINCRBY 사용하기

res16 = r.zadd("racer_scores", {"Wood": 100})
print(res16)  # >>> 1

res17 = r.zadd("racer_scores", {"Henshaw": 100})
print(res17)  # >>> 1

res18 = r.zadd("racer_scores", {"Henshaw": 150})
print(res18)  # >>> 0

res19 = r.zincrby("racer_scores", 50, "Wood")
print(res19)  # >>> 150.0

res20 = r.zincrby("racer_scores", 50, "Henshaw")
print(res20)  # >>> 200.0

ZADD는 멤버가 이미 존재할 때 0을 반환하고(점수가 갱신됨), ZINCRBY는 새 점수를 반환한다는 점을 보시면 돼요. 레이서 Henshaw의 점수는 100에서 시작해, 이전 점수가 무엇이든 상관없이 150으로 바뀌고, 그다음 50만큼 증가해 200이 됐습니다.

성능 (Performance)

대부분의 정렬 집합 연산은 O(log(n))입니다. 여기서 n은 멤버 수예요.

큰 반환 값(예: 수만 개 이상)을 가진 ZRANGE 명령을 실행할 때는 주의해야 합니다. 이 명령의 시간 복잡도는 O(log(n) + m)이며, 여기서 m은 반환되는 결과 수입니다.

대안 (Alternatives)

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

더 알아보기 (Learn more)

Redis Sorted Sets Explained — Redis의 정렬 집합에 대한 재미있는 소개 영상입니다.
Redis University의 RU101 — Redis 정렬 집합을 자세히 다룹니다.

출처: 공식문서