Set과 Sorted Set — 집합 연산과 랭킹 시스템

수백만 명의 게임 유저 순위를 실시간으로 계산하려면, 어떤 자료구조가 필요할까요?

개념 정의

Set 은 중복 없는 문자열의 비순서 컬렉션입니다. 수학의 집합과 같이 합집합, 교집합, 차집합 연산을 지원합니다.

Sorted Set(ZSet) 은 각 멤버에 score(점수) 가 부여되어 score 기준으로 자동 정렬되는 컬렉션입니다. 내부적으로 skiplist + hashtable의 이중 구조를 사용하여 O(log N) 삽입/삭제와 O(1) 점수 조회를 동시에 제공합니다.

Set — 집합 연산

기본 명령어

BASH

# 멤버 추가
SADD tags:post:1 "redis" "database" "nosql"
SADD tags:post:2 "redis" "caching" "performance"

# 멤버 제거
SREM tags:post:1 "nosql"

# 멤버 존재 확인 — O(1)
SISMEMBER tags:post:1 "redis"     # 1 (존재)
SMISMEMBER tags:post:1 "redis" "java"  # [1, 0] (6.2+)

# 전체 멤버 조회 — O(N)
SMEMBERS tags:post:1    # {"redis", "database"}

# 멤버 수 — O(1)
SCARD tags:post:1       # 2

# 랜덤 멤버
SRANDMEMBER tags:post:1      # 랜덤 1개
SRANDMEMBER tags:post:1 3    # 랜덤 3개 (중복 없이)
SRANDMEMBER tags:post:1 -3   # 랜덤 3개 (중복 가능)

# 랜덤 멤버 꺼내기 (제거 포함)
SPOP tags:post:1             # 랜덤 1개 제거 후 반환
SPOP tags:post:1 2           # 랜덤 2개 제거 후 반환

집합 연산

BASH

SADD set:a "1" "2" "3" "4"
SADD set:b "3" "4" "5" "6"

# 교집합
SINTER set:a set:b          # {"3", "4"}

# 합집합
SUNION set:a set:b          # {"1", "2", "3", "4", "5", "6"}

# 차집합 (A - B)
SDIFF set:a set:b           # {"1", "2"}

# 결과를 새로운 키에 저장
SINTERSTORE result set:a set:b   # result = {"3", "4"}
SUNIONSTORE result set:a set:b
SDIFFSTORE result set:a set:b

# 교집합 카디널리티만 확인 (7.0+)
SINTERCARD 2 set:a set:b         # 2
SINTERCARD 2 set:a set:b LIMIT 1 # 1 (1개 찾으면 조기 종료)

Set의 내부 인코딩

조건	인코딩	특성
모든 원소가 정수, ≤512개	intset	정렬된 정수 배열, 매우 컴팩트
원소 ≤128개, 각 ≤64바이트	listpack	순차 저장 (7.2+)
그 외	hashtable	O(1) 조회, 포인터 오버헤드

BASH

# intset 확인
SADD numbers 1 2 3 4 5
OBJECT ENCODING numbers   # "intset"

# 문자열 추가 시 전환
SADD numbers "hello"
OBJECT ENCODING numbers   # "hashtable"

Sorted Set — 점수 기반 정렬

기본 명령어

BASH

# 멤버 추가 (score가 필수)
ZADD leaderboard 100 "alice" 85 "bob" 92 "charlie"

# 옵션
ZADD leaderboard NX 80 "dave"    # 멤버가 없을 때만 추가
ZADD leaderboard XX 95 "alice"   # 멤버가 있을 때만 업데이트
ZADD leaderboard GT 90 "alice"   # 새 score가 더 클 때만 업데이트
ZADD leaderboard LT 90 "alice"   # 새 score가 더 작을 때만 업데이트

# 점수 조회 — O(1)
ZSCORE leaderboard "alice"       # "95"

# 여러 멤버 점수 한 번에 조회 (6.2+)
ZMSCORE leaderboard "alice" "bob"  # ["95", "85"]

# 점수 원자적 증가
ZINCRBY leaderboard 10 "bob"     # "95"

# 멤버 수 — O(1)
ZCARD leaderboard                # 4

범위 쿼리

BASH

# 순위(rank) 기준 조회 (0-indexed, score 오름차순)
ZRANGE leaderboard 0 -1 WITHSCORES
# charlie: 92, alice: 95, bob: 95, dave: 80
# → 실제로는 score 오름차순: dave(80), bob(85→95), charlie(92), alice(95)

# 역순 (score 내림차순)
ZRANGE leaderboard 0 2 REV WITHSCORES
# alice: 95, bob: 95, charlie: 92

# score 범위 조회
ZRANGE leaderboard 90 100 BYSCORE WITHSCORES
# charlie: 92, alice: 95, bob: 95

# score 범위 + LIMIT
ZRANGE leaderboard 0 100 BYSCORE LIMIT 0 10
# 상위 10명

# 사전순 범위 (score가 같을 때)
ZRANGE leaderboard "[a" "[d" BYLEX
# score가 동일한 멤버들 중 사전순 a~d

# 멤버 순위 조회 — O(log N)
ZRANK leaderboard "alice"        # 3 (0-indexed, 오름차순)
ZREVRANK leaderboard "alice"     # 0 (내림차순 1등)

삭제

BASH

# 멤버 삭제
ZREM leaderboard "dave"

# 순위 범위 삭제
ZREMRANGEBYRANK leaderboard 0 1    # 하위 2명 삭제

# score 범위 삭제
ZREMRANGEBYSCORE leaderboard 0 50  # score 50 이하 삭제

# 사전순 범위 삭제
ZREMRANGEBYLEX leaderboard "[a" "[c"

집합 연산

BASH

ZADD team:a 100 "alice" 80 "bob"
ZADD team:b 90 "alice" 70 "charlie"

# 합집합 (score 합산)
ZUNIONSTORE result 2 team:a team:b
# alice: 190, bob: 80, charlie: 70

# 합집합 (score 최댓값)
ZUNIONSTORE result 2 team:a team:b AGGREGATE MAX
# alice: 100, bob: 80, charlie: 70

# 교집합
ZINTERSTORE result 2 team:a team:b
# alice: 190

# 가중치 적용
ZUNIONSTORE result 2 team:a team:b WEIGHTS 2 1
# alice: 200+90=290, bob: 160, charlie: 70

# 카디널리티만 확인 (7.0+)
ZINTERCARD 2 team:a team:b    # 1

Sorted Set의 내부 구조

listpack (소규모)

BASH

# 기본 조건: 원소 ≤128개, 각 멤버 ≤64바이트
ZADD small 1.0 "a" 2.0 "b" 3.0 "c"
OBJECT ENCODING small    # "listpack"

listpack에서는 [member, score, member, score, ...] 형태로 score 순서대로 저장됩니다.

skiplist + hashtable (대규모)

BASH

# 원소가 많아지면 자동 전환
# 또는 멤버가 64바이트를 초과하면 전환
OBJECT ENCODING leaderboard    # "skiplist"

skiplist만으로는 특정 멤버의 score를 O(1)에 조회할 수 없고, hashtable만으로는 범위 쿼리를 효율적으로 처리할 수 없습니다. 이 두 한계 때문에 Sorted Set은 두 자료구조를 함께 사용하며, ** 그 결과** 각각의 강점을 살린 성능을 제공합니다.

PLAINTEXT

skiplist: score 기준 정렬 → 범위 쿼리 O(log N + M)
hashtable: member → score 매핑 → 점수 조회 O(1)

ZSCORE: hashtable에서 O(1)
ZRANK: skiplist에서 O(log N) — 각 노드가 span(건너뛰는 원소 수)을 저장
ZRANGE: skiplist에서 시작점 O(log N) + 순회 O(M)
ZADD: skiplist O(log N) + hashtable O(1)

실전 패턴

패턴 1: 리더보드

PYTHON

class Leaderboard:
    def __init__(self, name, redis_client):
        self.key = f"leaderboard:{name}"
        self.r = redis_client

    def update_score(self, user_id, score):
        """점수 업데이트"""
        self.r.zadd(self.key, {user_id: score})

    def increment_score(self, user_id, delta):
        """점수 증가"""
        return self.r.zincrby(self.key, delta, user_id)

    def get_rank(self, user_id):
        """순위 조회 (1-indexed)"""
        rank = self.r.zrevrank(self.key, user_id)
        return rank + 1 if rank is not None else None

ZREVRANK는 score 내림차순 기준의 0-indexed 순위를 반환하므로, 사용자에게 보여줄 때는 +1을 해야 합니다. 주변 순위 조회는 내 rank를 기준으로 앞뒤 N명을 ZRANGE로 가져옵니다.

PYTHON

    def get_top(self, count=10):
        """상위 N명"""
        return self.r.zrange(
            self.key, 0, count - 1,
            desc=True, withscores=True
        )

    def get_around_me(self, user_id, count=5):
        """내 주변 순위"""
        rank = self.r.zrevrank(self.key, user_id)
        if rank is None:
            return []
        start = max(0, rank - count)
        end = rank + count
        return self.r.zrange(
            self.key, start, end,
            desc=True, withscores=True
        )

패턴 2: 태그 기반 검색 (Set 교집합)

PYTHON

def add_post_tags(post_id, tags):
    """게시물에 태그 추가"""
    pipe = r.pipeline()
    for tag in tags:
        pipe.sadd(f"tag:{tag}", post_id)
    pipe.sadd(f"post:{post_id}:tags", *tags)
    pipe.execute()

def search_by_tags(tags):
    """모든 태그를 가진 게시물 검색 (교집합)"""
    keys = [f"tag:{tag}" for tag in tags]
    return r.sinter(*keys)

def search_by_any_tag(tags):
    """하나 이상의 태그를 가진 게시물 검색 (합집합)"""
    keys = [f"tag:{tag}" for tag in tags]
    return r.sunion(*keys)

패턴 3: 시간 윈도우 기반 이벤트

PYTHON

def record_event(user_id, event_type):
    """타임스탬프를 score로 사용한 이벤트 기록"""
    key = f"events:{user_id}:{event_type}"
    now = time.time()
    r.zadd(key, {f"{event_type}:{now}": now})
    # 24시간 이전 이벤트 정리
    r.zremrangebyscore(key, 0, now - 86400)

def count_recent_events(user_id, event_type, window_seconds=3600):
    """최근 N초 이내 이벤트 수"""
    key = f"events:{user_id}:{event_type}"
    now = time.time()
    return r.zcount(key, now - window_seconds, now)

패턴 4: 친구 추천 (Set 차집합)

PYTHON

def suggest_friends(user_id, count=10):
    """친구의 친구 중 아직 친구가 아닌 사람 추천"""
    my_friends = f"friends:{user_id}"
    candidates = set()

    for friend_id in r.smembers(my_friends):
        # 친구의 친구 집합에서 내 친구를 빼기
        fof = r.sdiff(f"friends:{friend_id}", my_friends)
        candidates.update(fof)

    candidates.discard(user_id)  # 자기 자신 제거
    return list(candidates)[:count]

ZRANGESTORE / ZDIFF (6.2+)

BASH

# 범위 결과를 새 키에 저장
ZRANGESTORE dest src 0 9 REV
# src의 상위 10개를 dest에 저장

# 차집합 (7.0+)
ZDIFF 2 team:a team:b WITHSCORES
# team:a에만 있는 멤버와 score

성능 주의사항

BASH

# 위험: 대규모 집합의 SMEMBERS
SMEMBERS huge_set  # 100만 개 → 블로킹

# 안전: SSCAN으로 점진적 순회
SSCAN huge_set 0 COUNT 100

# 위험: 대규모 ZUNIONSTORE
ZUNIONSTORE result 3 large_set1 large_set2 large_set3
# 모든 원소를 순회하므로 시간이 걸림

# 안전: ZRANGE에 LIMIT 사용
ZRANGE leaderboard 0 100 BYSCORE LIMIT 0 20

함정/Pitfall

1. SMEMBERS와 ZUNIONSTORE는 대규모에서 서버를 블로킹한다

SMEMBERS는 O(N)으로 전체 멤버를 반환하고, ZUNIONSTORE는 모든 입력 집합을 순회합니다. 멤버가 수십만 개 이상이면 다른 요청이 블로킹됩니다. SSCAN으로 점진적 순회하거나, SINTERCARD로 카디널리티만 확인하는 것이 안전합니다.

2. Sorted Set에서 같은 score의 멤버는 사전순으로 정렬된다

리더보드에서 동점일 때 "먼저 달성한 사람이 위"를 기대하지만, Redis는 사전순(lexicographic)으로 정렬합니다. 동점 처리가 중요하다면 score에 타임스탬프를 결합(예: score * 10^13 + (MAX_TIMESTAMP - timestamp))하는 설계가 필요합니다.

3. intset→hashtable 전환은 문자열 하나로 트리거된다

Set의 모든 원소가 정수일 때 intset으로 메모리 효율적인 인코딩을 사용하지만, 정수가 아닌 원소가 단 하나라도 추가되면 hashtable로 전환되어 메모리 사용량이 급증합니다.

정리

항목	핵심 내용
Set	중복 제거, 교집합/합집합/차집합 연산 최적화
Sorted Set	score 기반 자동 정렬, O(log N) 삽입/삭제, O(1) 점수 조회
내부 구조	Sorted Set은 skiplist + hashtable 이중 구조
활용 패턴	리더보드, 시간 윈도우 이벤트, 태그 검색
성능 주의	대규모 집합 연산 시 LIMIT, SSCAN, SINTERCARD 활용