대규모 시스템 설계 - 실시간 게임 순위표

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

기능 요구사항

1. 상위 10명 플레이어 표시: 순위표에 가장 높은 점수를 가진 10명의 플레이어를 표시함.
2. 특정 사용자 순위 표시: 특정 사용자의 현재 순위를 표시함.
3. 주변 사용자 순위 표시 (보너스): 특정 사용자보다 4순위 위와 아래에 있는 사용자들을 표시할 수 있어야 함.

비기능 요구사항 및 규모 추정

1. 실시간 갱신: 점수 업데이트는 실시간 또는 가능한 실시간에 가깝게 순위표에 반영되어야 함.
2. 규모 확장성: 일반적인 확장성, 가용성 및 안정성 요구사항 충족.
3. 사용자 규모: 평균 일간 활성 사용자 수(DAU) 500만 명, 월간 활성 사용자 수(MAU) 2,500만 명 가정.
4. 최대 부하 추정:
   1. 사용자 점수 획득 QPS: 최대 부하 시간대(평균의 5배)를 고려하여 초당 최대 2,500회의 점수 획득 이벤트(QPS) 감당.
   2. 상위 10명 순위표 가져오기 QPS: QPS 약 50 수준.

2. 개략적 설계안 제시 및 동의 구하기

API 설계

시스템은 세 가지 주요 API를 통해 순위표 기능을 제공함.

1. POST /v1/scores (점수 갱신):
   • 사용자가 게임에서 승리하면 순위표에서 순위를 갱신하는 내부 API임.
   • 요청 인자는 user_id와 획득한 points
2. GET /v1/scores (상위 10명 조회):
   • 순위표에서 상위 10명의 플레이어 목록을 가져옴.
3. GET /v1/scores/{:user_id} (특정 사용자 순위 조회):
   • 특정 사용자의 순위 정보를 가져옴.

개략적 아키텍처

1. 서비스 구성: 설계안은 게임 서비스와 순위표 서비스 두 가지 서비스로 구성됨.
2. 점수 갱신 흐름:
   1. 사용자가 승리하면 클라이언트가 게임 서비스에 요청함.
   2. 게임 서비스는 승리의 유효성을 확인한 후 순위표 서비스에 점수 갱신을 요청함.
   3. 순위표 서비스는 순위표 저장소의 사용자 점수를 갱신함.
3. 순위표 조회 흐름: 클라이언트가 순위표 서비스에 직접 요청하여 상위 10명 순위표나 해당 사용자 순위를 가져옴.
4. 보안 고려사항: 클라이언트가 점수를 직접 설정하는 방식은 중간자 공격에 취약하므로, 점수 설정은 반드시 서버가 담당해야 함.
5. 메시지 큐 (선택 사항): 게임 점수 데이터가 분석, 푸시 알림 등 여러 기능을 지원해야 한다면 카프카(Kafka)와 같은 메시지 큐를 도입하여 여러 서비스가 동일한 데이터를 소비하도록 하는 방안 고려.

데이터 모델: 관계형 데이터베이스 (RDS)의 한계

1. RDS 모델: 사용자 ID와 점수 열을 가진 leaderboard 테이블을 만들어 점수에 따라 내림차순으로 정렬하여 순위를 결정함.
2. 점수 갱신: 새로운 레코드를 삽입하거나, 기존 레코드의 점수를 UPDATE 명령으로 1씩 증가시킴.
3. 순위 검색: 순위를 가져오려면 테이블을 점수 기준으로 정렬한 후 순위를 매겨야 함.
4. RDS의 문제점 (규모 확장성 부족):
   1. 성능 저하: 레코드가 수백만 개로 많아지면 순위를 매기기 위해 전체 테이블을 정렬해야 하므로 성능이 수십 초 정도로 나빠짐.
   2. 실시간성 미흡: 지속적으로 데이터가 변경되므로 캐시 도입이 불가능하며, 실시간성을 요구하는 애플리케이션에 부적합함.
   3. 특정 사용자 순위 조회 어려움: LIMIT 절을 사용해도 특정 사용자의 순위를 알아내려면 기본적으로 전체 테이블을 훑어야 하므로 성능이 떨어짐.

데이터 모델: 레디스 정렬 집합 (Redis Sorted Set) 활용

레디스 정렬 집합의 특징

1. 고성능: 메모리 기반 키-값 저장소로, 빠른 읽기 및 쓰기 가능.
2. 정렬 집합 (Sorted Set): 순위표 시스템 설계에 이상적인 자료형으로, 각 원소(사용자 ID)는 점수(Score)에 연결되어 있으며, 점수를 기준으로 오름차순 정렬됨.
3. 내부 구조: 정렬 집합은 내부적으로 해시 테이블 (사용자 점수 저장)과 스킵 리스트 (정렬 및 빠른 검색)를 사용함.
4. 스킵 리스트: 정렬된 연결 리스트에 다단계 색인(index)을 두어 검색, 삽입, 삭제 연산의 시간 복잡도를 O(log(n)) 으로 개선함.

레디스 정렬 집합을 사용해 요구사항 구현하기

1. 점수 갱신 (ZADD/ZINCRBY):
   • ZADD는 기존 사용자의 점수를 업데이트하거나 새로운 사용자를 삽입함.
   • ZINCRBY는 사용자 점수를 지정된 값만큼 증가시킴.
   • 실행 시간은 O(log(n))
   • ZINCRBY leaderboard_feb_2021 1 'mary1934'
2. 상위 N명 조회 (ZREVRANGE):
   • ZREVRANGE를 호출하여 내림차순으로 정렬된 사용자 중 특정 범위(예: 0부터 9까지)에 드는 사용자 목록과 점수를 가져옴.
   • 실행 시간은 O(log(n) + m) (m은 가져올 항목 수)
   • ZREVRANGE leaderboard_feb_2021 0 9 WITHSCORES
3. 특정 사용자 순위 조회 (ZREVRANK):
   • ZREVRANK를 호출하여 내림차순 정렬을 기준으로 특정 사용자의 위치(순위)를 가져옴.
   • 실행 시간은 O(log(n))
   • ZREVRANK leaderboard_feb_2021 1 'mary9341'
4. 주변 사용자 조회: 특정 사용자의 순위(랭크)를 기준으로 ZREVRANGE를 활용하여 전/후 순위 사용자 목록을 얻을 수 있음.
5. ZREVRANGE leaderboard_feb_2021 357 365

저장소 요구사항 및 영속성

1. 저장 용량 추정: MAU 2,500만 명 기준, 순위표 한 항목당 26바이트 가정 시 총 약 650MB의 저장공간 필요.
2. 단일 서버 가능성: 스킵 리스트 오버헤드를 고려해 메모리 사용량을 두 배로 늘려도 최신 레디스 서버 한 대로 충분히 데이터 저장 가능.
3. CPU/I/O 부하: 최대 갱신 QPS 2,500/초는 단일 레디스 서버로 감당 가능한 부하
4. 영속성 (Persistence): 레디스 노드 장애에 대비하여 데이터를 디스크에 영속적으로 보관하는 옵션 지원. 일반적으로 읽기 사본(Read Replica)을 두어 주 서버 장애 시 승격시키는 방식으로 구성함.
5. 보조 데이터베이스 (MySQL): 레디스 순위표 복구 및 다른 게임 기능(경연 기록) 구현을 위해 사용자 ID, 점수, 타임스탬프 등의 정보를 MySQL에 저장

3. 상세 설계

3.1. 클라우드 서비스 사용 여부

자체 서비스를 이용하는 방안

1. 구성: 매월 정렬 집합을 생성하여 순위표를 저장하고, 사용자 이름 및 프로필 이미지와 같은 세부 정보는 MySQL 데이터베이스에 저장함.
2. 성능 최적화: 순위표를 가져올 때 DB에 저장된 사용자 세부 정보도 함께 가져와야 하므로, 장기적으로 비효율적일 경우 상위 10명의 세부 정보를 저장하는 프로필 캐시를 두어 해결 가능.

클라우드 서비스를 이용하는 방안 (AWS 예시)

1. 서버리스 아키텍처: AWS API 게이트웨이와 AWS 람다(Lambda)를 사용하여 서버리스 방식으로 순위표를 구축함.
2. 작동 원리: API 게이트웨이가 클라이언트 요청을 받아 적절한 람다 함수(예: LeaderboardFetchTop10, LeaderboardUpdateScore)를 호출함.
3. 장점: 람다는 서버를 직접 관리할 필요가 없으며, 트래픽에 따라 규모가 자동으로 확장되므로 DAU 성장세에 맞춰 서비스 규모를 확장하기 용이함.
   1. 각종 서비스를 호출하는 웹 서버 단의 확장성을 고려하지 않아도 됨

3.2. 레디스 규모 확장 (샤딩)

500만 dau는 단일 레디스 서버로 충분하지만, 5억 dau(저장 용량 65GB, 최대 qps 250,000)를 처리하려면 샤딩이 필요

고정 파티션 (Fixed Partition)

1. 원리: 순위표에 등장하는 점수의 범위에 따라 파티션을 나눔 (예: 1100점, 101200점 등).
2. 전제 조건: 순위표 전반에 점수가 고르게 분포되어야 하며, 그렇지 않다면 샤드에 할당되는 점수 범위를 조정해야 함.
3. 점수 갱신: 사용자의 점수가 높아져 다른 샤드로 옮겨야 할 경우, 기존 샤드에서 제거하고 새 샤드로 옮기는 작업 필요.
4. 상위 10명 조회: 가장 높은 점수가 저장되는 샤드(정렬 집합)에서 상위 10명을 가져옴.
5. 특정 사용자 순위 조회: 해당 사용자가 속한 샤드 내 순위와, 그보다 높은 점수를 커버하는 모든 샤드의 사용자 수를 합산하여 최종 순위를 결정함.

해시 파티션 (Hash Partition)

1. 원리: 레디스 클러스터를 사용하여 키(사용자 ID)를 해시 슬롯(총 16384개)에 따라 여러 노드에 자동으로 분산함.
2. 점수 갱신: 사용자의 샤드를 찾아 점수를 변경하기만 하면 됨.
3. 상위 10명 검색의 어려움: 모든 샤드에서 상위 10명을 받아 애플리케이션 내에서 다시 정렬하는 분산-수집(scatter-gather) 접근법을 사용해야 함.
4. 해시 파티션의 문제점:
   1. 지연 시간 증가: 상위 k개 결과를 반환해야 할 때, 각 샤드에서 많은 데이터를 읽고 정렬해야 하므로 지연 시간이 늘어남.
   2. 순위 결정의 어려움: 특정 사용자의 정확한 순위를 결정할 간단한 방법이 없음.
5. 결론: 해시 파티션의 문제점 때문에 고정 파티션 방안을 사용하기로 함.

레디스 노드 크기 조정

• 쓰기 작업에는 최대 2개 더 많은 메모리가 필요
  • 디스크 영속 시 부모 프로세스를 fork 하여 자식 프로세스를 만들고,
  • 부모 프로세스에서 변경이 필요하면 페이지를 복사해서 사용하기 때문
• 이를 고려하여 메모리를 결정해야 함

3.3. 대안: NoSQL 데이터베이스 (DynamoDB)

레디스 외의 대안으로 dynamodb와 같은 nosql 데이터베이스 사용 가능.

1. DynamoDB 특징: 안정적인 성능과 확장성을 제공하는 완전 관리형 NoSQL 데이터베이스임.
2. 데이터 모델링: 순위표와 사용자 테이블을 비정규화하여 하나의 테이블에 필요한 모든 정보를 담음.
3. 전역 보조 색인 (Global Secondary Index, GSI) 활용:
   • GSI를 사용하여 파티션 키를 game_name#{year-month}로, 정렬 키를 score로 설정하면 점수 기준으로 효율적인 정렬이 가능함.
4. 핫 파티션 문제 및 쓰기 샤딩:
   • 위 모델은 최근 한 달치 데이터가 동일한 파티션에 저장되어 핫 파티션(hot partition)이 될 수 있음.
   • 이를 해결하기 위해 파티션 키에 파티션 번호를 추가하는 쓰기 샤딩(write sharding) 패턴을 사용함 (game_name#{year-month}#p{partition_number}).
5. 읽기 복잡성: 쓰기 샤딩을 사용하면 한 파티션의 부하는 낮아지지만, 특정 달의 데이터를 읽으려면 모든 파티션을 질의한 결과를 합쳐야 하므로 구현이 복잡해짐.
6. 상위 10명 조회: 레디스와 마찬가지로, n개의 파티션에서 상위 10개 결과를 가져온 다음(분산), 애플리케이션에서 모아 정렬하는(수집) 분산-수집 접근법을 사용해야 함.
7. 상대적 순위 결정: DynamoDB 접근법으로는 사용자의 정확한 상대적 순위를 쉽게 정할 수 없지만, 대신 사용자의 위치 백분위수를 구하는 것은 가능함.
8. 10번째 백분위수 = 점수 < 100 20번째 백분위수 = 점수 < 500 ... 90번째 백분위수 = 점수 < 6500

4. 마무리

더 빠른 조회 및 동점자 순위 판정 방안

1. 사용자 정보 조회 개선: 레디스 해시(Redis Hash)를 사용하여 사용자 ID와 사용자 객체 사이의 대응 관계를 저장하면, 데이터베이스에 질의하지 않고도 빠르게 사용자 정보 확인 가능.
2. 동점자 순위 판정: 두 사용자의 점수가 같을 경우, 레디스 해시에 사용자 ID와 마지막으로 승리한 경기의 타임스탬프를 저장하여, 타임스탬프 값이 낮은(오래된) 사용자에게 더 높은 순위를 부여함.

시스템 장애 복구

1. 복구 시스템: 대규모 레디스 클러스터에 장애가 발생할 경우, MySQL 데이터베이스에 사용자가 게임에서 이길 때마다 타임스탬프와 함께 기록된 사실을 활용함.
2. 복구 절차: MySQL의 사용자별 레코드를 훑으면서, 레코드당 한 번씩 ZINCRBY 명령을 호출하는 오프라인 스크립트를 실행하여 대규모 순위표 복구 가능.