모범답안 — 랭킹/리더보드 자료구조와 저장 설계

난이도: 중

1. 매번 ORDER BY 의 문제와 정렬 자료구조

• 매 조회 ORDER BY 의 문제: 점수가 자주 바뀌는데 조회마다 수백만 행을 정렬하면 비용이 크다. 인덱스가 있어도 "특정 플레이어의 순위(rank)"는 "나보다 점수 높은 사람 수 세기(COUNT)"라, 정렬 인덱스만으로 O(log n)에 안 나오고 보통 스캔/집계가 필요하다. 갱신이 잦으면 캐시 무효화도 빈번.
• 정렬 자료구조(스킵 리스트/균형 트리): 원소를 정렬 상태로 유지하며 삽입·삭제·점수변경이 O(log n), 순위 조회(rank)·범위 조회(top N)도 보조 카운트를 갖춘 구조면 O(log n) 또는 O(log n + k). 즉 "갱신 즉시 정렬 유지 + 순위/범위 즉답"이 가능해 랭킹에 적합하다. Redis ZSET이 내부적으로 스킵 리스트 + 해시로 이를 구현한다.

2. Redis Sorted Set(ZSET) 구현

• (a) 점수 갱신: ZADD season:S <score> <playerId> — 있으면 갱신, 없으면 추가. O(log n).
• (b) 내 점수/순위: ZSCORE season:S <playerId> (점수, O(1)), ZREVRANK season:S <playerId> (높은 점수가 1위인 순위, O(log n)).
• (c) Top N: ZREVRANGE season:S 0 99 WITHSCORES — 상위 100. O(log n + k).
• (d) 내 주변 순위: 내 rank r = ZREVRANK ... 를 구한 뒤 ZREVRANGE season:S r-5 r+5 WITHSCORES. O(log n + k).
• 점수 구간 인원수는 ZCOUNT, 구간 조회는 ZREVRANGEBYSCORE 등.

3. 동점 처리와 페이지네이션

• 동점 안정화: 점수가 같으면 순위가 흔들리지 않도록 보조 기준(예: 먼저 그 점수에 도달한 사람이 위)을 하나의 정렬 키에 인코딩한다. 흔한 기법:
  • 정렬키 = score * C - timestamp (C는 충분히 큰 상수). 점수가 1순위, 같은 점수면 작은 timestamp(먼저 도달) 가 더 큰 정렬키 → 위로.
  • 부동소수 정밀도 한계가 걱정되면 정수 비트패킹((score << 32) | (maxTime - t))을 써 64비트 정수 하나로 합친다. Redis ZSET score는 double이라 큰 정수 정밀도(2^53 초과)에 주의 — 필요하면 score 동률 시 멤버 사전순(lexicographical)으로 깨지는 점을 고려해 멤버에 보조 키를 함께 인코딩.
• 대규모 페이지네이션 비용: ZREVRANGE 50000 50099 처럼 깊은 오프셋은 스킵 리스트를 그만큼 타고 들어가야 해 오프셋에 비례한 비용이 든다. 완화책: score 기반 커서(마지막으로 본 score/member 이후부터 ZREVRANGEBYSCORE ... LIMIT 로 이어가기 = keyset pagination), 페이지 깊이 제한(보통 상위 N위까지만 정밀 제공), 하위권은 근사.

4. 영속화·정합성·확장

• 갱신 흐름: 게임 로직이 점수를 바꾸면 (1) 원본 DB(권위)와 (2) Redis ZSET 둘 다 갱신해야 한다. 이중 쓰기 일관성은 이 저장소 concurrency_memory/problem13(캐시-DB 이중 쓰기), persistence_data/problem1(복제 지연)과 같은 문제다. 보통 DB를 진실원천으로 두고 ZSET은 파생 캐시로 취급: 변경 이벤트로 ZSET을 갱신하고, 어긋나면 DB에서 재구성.
• 시즌 마감: 마감 시 ZSET을 스냅샷으로 DB에 영속화(최종 순위 확정), 보상 지급은 멱등하게(중복 지급 방지, problem17 계열). 마감 순간의 늦은 점수 갱신 경합 처리(시즌 경계).
• 장애 복구: Redis는 휘발 위험이 있으니 ZSET을 언제든 DB로부터 재구축 가능하게 설계(재구축 스크립트/배치). AOF/RDB 영속화는 보조.
• 확장(수천만): 단일 ZSET은 메모리·단일 노드 처리량 한계가 있다. 대안:
  • 샤딩: 지역/티어/버킷별로 ZSET을 나누고, 전역 Top N은 각 샤드 상위 일부를 병합(merge). 단 전역 "정확한 내 순위"는 샤드 합산이 필요해 비싸짐.
  • 근사 랭킹(approximate rank): 점수 분포 히스토그램/버킷으로 "대략 상위 X%" 를 O(1)에 제공하고, 정밀 순위는 상위권에만. 대규모 하위권은 근사로 충분한 경우가 많다.
  • 상위권만 실시간 ZSET, 전체는 주기적 배치 집계로 분리.

핵심 요약

랭킹은 정렬 유지 + 순위/범위 즉답이 필요하므로 ZSET(스킵 리스트) 류가 적합(주요 연산 O(log n)). 동점은 점수+시간을 한 정렬 키에 인코딩해 안정화하고, 깊은 페이지네이션은 keyset 커서로 완화. DB를 진실원천, ZSET을 재구축 가능한 파생 캐시로 두고, 수천만 규모는 샤딩/근사 랭킹으로 확장한다.