[시스템 디자인] 10. 실시간 게임 순위표

시스템 디자인 시리즈의 글입니다.

온라인 게임의 리더보드 (=순위표)를 설계해보자

0. 미리 설계해보기

시스템 구성도

개인 / 랭킹을 따로 집계해야될거같다
- → 메세지큐를 사용하면 좋을듯
- 예전 주변친구만들기 시스템 설계에서 개인 이력을 따로 집계했던 구성에서 착안함
- 매번정렬할때 시간어느정도? → 요즘 컴퓨터 기준으로 1억~10억 operation 1초정도 걸린다고 가정하면.. realtime에서 매번 정렬 어려움.
규모도 생각해야하나? 어느정도 규모로 잡아야할지 감이 안잡힘..
- → 배그같은거 동접자수 참고하면좋을듯
쓰기가 많을까? RDB로 조회해도 충분할거같음..
segment tree등의 알고리즘

1. 문제 이해 및 설계 범위 확정

기능 요구사항

순위표에 상위 10명의 플레이어 표시
특정 사용자의 순위 표시
(보너스) 어떤 사용자의 순위 +,- 4위 사용자 표시

비기능 요구사항

점수업데이트를 실시간으로 순위표에 반영
일반적인 확장성, 가용성, 안정성

개략적 규모 추정

면접관과 규모를 맞추면 좋음
DAU 5M (500만), MAU 25M (2500만)으로 가정
초당 5*10\^6 / 10\^5 ~= 50명의 사용자 게임
사용자 점수 획득 QPS
- 한 사용자가 하루 평균 10게임 플레이한다고 했을때,
- QPS = 50 * 10 ~= 500 가량.
- 최대부하 = 평균의 다섯배로 가정 ~= 500 * 5 = 2,500QPS
상위 10명 순위표 가져오기 QPS
- 사용자가 처음 게임 열때만 표시한다고 가정
- QPS ~= 50

2. 개략적 설계

API 설계

사용자 순위갱신 API
- POST /v1/scores
- request : user_id, points
- response : status code
상위 10명의 플레이어 조회 API
- GET /v1/scores
- response : user_id, user_name, rank, score
특정 사용자의 순위 조회 API
- GET /v1/scores/{:user_id}
- request : user_id
- response : user_id, score, rank

개략적 설계안

서비스
- 게임서비스 : 사용자가 게임을 플레이할수있는 서비스
- 순위표 서비스 : 순위표를 생성, 표시하는 서비스
flow
1. 사용자 게임 승리
2. 게임서비스에 점수 갱신 요청
3. 게임서비스는 순위표서비스에 점수갱신 요청
4. 순위표서비스는 저장소의 점수를 갱신
5. 클라에서 갱신된 정보를 조회
쟁점
- 클라가 순위표서비스와 직접 통신?
  - 클라가 점수를 정하는것도 가능하지만, 중간자공격에 취약함
  - 따라서 점수는 서버가 설정하는게 맞음
- 메세지큐 필요여부
  - 게임점수가 활용방식에 따라 필요할수도 있음
  - 점수가 다른곳에도 이용되고 여러기능을 지원하면 큐를 쓰는게 합리적
  - 본 설계안에서는 포함 X

데이터 모델

RDS
- 규모확장성이 중요하지않고 사용자수가 적다면 괜찮은 선택
- 사용자가 점수를 따면 upsert로 DB갱신
- 특정 사용자 순위를 검색할때는 테이블을 score기준으로 sorting하여 순위매김
- 데이터가 적을때는 효과적이지만 수백만개 이상으로 넘어가면 성능이 매우 나빠짐
- 지속적으로 변화하는 대량의 정보를 신속하게 처리하지못함
Redis
- 메모리기반 키-값 저장소시스템
- 빠른 읽기 및 쓰기 가능
- 정렬집합(sorted set) 자료형 제공
  - 집합과 유사한 자료형이지만 원소를 정렬할수있음
  - 내부적으로 해시테이블과 스킵리스트를 사용
  - 스킵리스트는 sorted linked list에 다단계 index를 두는 구조
  - 시간복잡도 O(log(n)) 으로 원소를 검색할수있음
- 사용자가 점수를 따면 ZINCRBY <키> <증분> <사용자> 로 갱신
- 사용자가 순위표 상위 10명을 조회하면 ZREVRANGE <키> <offset> <limit> WITHSCORES 로 조회
- 사용자가 자기 순위를 조회하는경우 ZREVRANK <키> <사용자> 로 조회
- 여기서 가져온 offset으로 일정범위 사용자 ZREVRANGE <키> <offset> <limit> 로 조회
저장소 요구사항
- 사용자ID, 점수 저장
- ID 24byte + 점수 2byte = 26byte
- 26byte * 25M (DAU) = 650MB → 저장소 레디스 한대로도 충분
- QPS 2500/sec → CPU , I/O 레디스 한대로 충분
- 데이터 영속성 → 레디스 읽기 사본
- RDB에 사용자 승리 로그를 저장하면 레디스 순위표 복구에 활용가능
- 자주검색되는 상위 10명 사용자정보를 캐싱하면 성능최적화에 굿

3. 상세설계

클라우드 서비스 사용 여부

자체서비스(on-prem) 이용
- 매월 정렬집합을 생성해 해당 기간의 순위표 저장
- 해당 순위표에는 사용자 및 점수정보 저장
- 사용자프로필 캐시 저장
- RDB에는 사용자정보 저장
- API서버에서 위 데이터 활용
클라우드서비스 이용 방안
- AWS API gateway와 lambda 사용
- 서버리스 운영 가능

레디스 규모 확장

100배 DAU를 감당한다면? 아무래도 샤딩이 필요해지겠다.

고정파티션 샤딩
- 순위표에 등장하는 점수 범위에 따라 파티션을 나누는 방안
- 순위표 전반에 점수가 고르게 등장해야함.
- 점수가 특정 범위에 쏠린다면 올바른 샤딩이 안될수있음 → 이럴경우 어플리케이션이 점수범위를 조정하여 고르게 분포하도록 샤딩을 처리함
- 특정 사용자의 점수 입력 및 갱신때 사용자 정보가 어느 샤드에있는지 검색하는 비용이 듬
- 사용자 ID - 점수 저장하는 2차캐시를 둔다면 좀 나을듯.
- 사용자 점수구간이 변경되어 샤드 구간이 바뀌는경우 기존샤드 제거 → 새 샤드에 생성하는 과정을 거쳐야함
- 특정 사용자의 순위를 알려면 해당 샤드뿐 아니라 해당 점수 이상의 모든 샤드의 사용자수를 알아야함.
- 다행히 info keyspace 명령어로 샤드 사용자수는 O(1) 시간복잡도로 알수있음
해시파티션
- 레디스 클러스터 사용
- 사용자들의 점수범위상관없이 자동으로 레디스 해시키로 샤딩해줌
- 키를 재분배하지않아도 쉽게 노드 추가/제거 가능
- 단 상위 10명을 수집하기가 까다로움
- 분산-수집(scatter-gather)접근법으로 각 샤드의 상위사용자를 다 가져와서 새로 정렬해야함 ⇒ 본 설계안에서는 고정파티션샤딩을 더 적절한 방법으로 판단하고, 이를 사용할것임

NoSQL

NoSQL DB는 새로운 대안이 될수있음. 다음과 같은 특징을 가지고있는 DB가 이상적임

쓰기연산에 최적화
같은 파티션 내의 항목을 점수에 따라 효율적으로 정렬 가능 ⇒ DynamoDB, Cassandra, MongoDB 등.

DynamoDB를 예로 들어 설계해보자.

순위표와 사용자테이블을 비정규화
리더보드 시간값을 파티션키로, 점수를 정렬키로 사용
핫파티션 문제가 생길수있음 (최근것만 많이 조회)
- 핫 파티션 (핫스팟)문제에대한 정형적인 해결방법 한번 정리하기
데이터를 n개파티션으로 분할하고 파티션키에 파티션번호를 추가해서 해결가능.
상위10명사용자를 가져오려면 scatter-gather사용해야함.
파티션 갯수는 DAU기준으로 읽기복잡도를 판단하여 정하면 좋다.
각 샤드의 점수분포를 분석한 결과를 캐시하는 크론잡을 통해 백분위를 계산해 보여주는 방식도 좋은 대안