Design Real-time Game Leaderboard

요구사항

• 상위 플레이어의 순위 실시간 제공
• 특정 사용자의 일정 범위의 순위 제공
• DAU 500만 명, MAU 2,500만 명
• 하루 평균 10 게임 플레이
• 순위 반영은 가능한 실시간에 가깝게 처리

위 요구 사항을 만족하기 위해 다음과 같은 개략적인 규모를 추정할 수 있다.

• 초당 평균 유저: 500만 명 / 24 / 3600 = 57.87 (24시간 고르게 분포되어 있다고 가정)
• 진행 게임: 57.87 * 10 = 578.7 (하루 평균 10게임 플레이한다고 가정)
• 사용자 점수 획득 QPS: 578.7 * 5 = 2,893.5 (피크 시간에 5배의 트래픽이 발생한다고 가정)
• 순위 조회 QPS: 57.87 (최초 접속 시 조회한다고 가정)

API 단위 기능 정의

• POST /scores: 게임 플레이 후 점수를 기록하는 API
• GET /scores: 상위 플레이어의 순위를 조회하는 API
• GET /scores/{user_id}: 특정 사용자의 순위를 조회하는 API

개략적 설계안

게임 서비스와 순위표 서비스로 나누어 아래와 같은 흐름으로 설계할 수 있다.

1. 사용자가 게임을 플레이하고 점수를 획득 후 게임 서비스에 요청
2. 게임 서비스는 점수가 유효한지 확인 후 순위표 서비스에 점수 기록 요청
3. 순위표 서비스는 점수를 기록하고, 해당 사용자의 순위를 갱신
   • 순위 갱신 시 Redis의 Sorted Set을 사용하여 점수를 내림차순으로 정렬
4. 사용자는 지속적으로 순위표 서비스에 플레이어의 순위를 조회

게임 서비스와 순위표 서비스 간 통신에는 상황에 따라 REST API 또는 메시지 큐를 사용할 수 있다.

저장소 요구사항 - Redis Sorted Set 사용

순위 정보를 Redis의 Sorted Set을 사용하여 저장한다고 가정하고, 다음과 같은 요구 사항이 있다고 가정하자.

• 사용자 ID - 점수 형태로 저장
• 월간 활성 사용자 2,500만 명 모두 순위에 포함
• ID 24 character 문자열 / 점수 16비트 정수 = 26바이트
• 26바이트 * 2,500만 명 = 약 650MB

650MB는 오버헤드와 정렬 집합 해시를 고려해 두 배를 사용한다고 가정하더라도, 한 대의 Redis 인스턴스에 충분히 저장할 수 있으며, 2,900 QPS도 한 대의 Redis에서 처리할 수 있는 범위이다.

Redis Sorted Set 동작 방식

Redis의 Sorted Set은 해시 테이블과 스킵 리스트 두 가지 자료구조를 사용하여 구현된다.

• 해시 테이블: 사용자의 점수 저장
• 스킵 리스트: 특정 점수를 딴 사용자들의 목록을 저장

이 중 스킵리스트는 빠른 검색을 가능하게 하는 자료 구조로, 정렬된 연결 리스트에 다단계 색인을 두어 검색 속도를 높인다.

1 -------------- 15 ---------------- 60
|                |                   |
1 ----- 8 ------ 15 ------ 36 ------ 60
|       |        |         |         |
1 - 4 - 8 - 10 - 15 - 26 - 36 - 45 - 60 - 68

이진 검색 트리처럼 중간 지점에 더 빨리 도달할 수 있도록 n차의 색인을 추가하여, 검색 속도를 O(log n)으로 줄일 수 있다.

Redis Sorted Set 명령어

Redis Sorted Set에서 사용하게 되는 명령어는, 다음과 같이 활용할 수 있다.

• ZADD: 기존에 없던 사용자를 집합에 추가하거나, 기존 사용자 점수를 갱신
• ZINCRBY: 기존 사용자 점수 증감
• ZRANGE / ZREVRANGE: 특정 범위에 있는 사용자 조회
• ZRANK / ZREVRANK: 특정 사용자의 순위 조회

상세 설계

클라우드 서비스 사용

자체 서비스를 구축하는 경우, Redis와 MySQL를 직접 사용하여 구현할 수 있지만, 클라우드 서비스를 사용한다고 가정하면 API Gateway와 AWS 람다 기술을 사용해볼 수 있다.

1. API Gateway를 호출하고, 해당 게이트웨이는 적절한 AWS 람다 함수를 호출
2. 람다 함수는 스토리지 계층의 명령을 호출하여 얻은 결과를 API Gateway에 반환
3. API Gateway는 람다 함수의 응답을 클라이언트에 반환

이렇게 하면, 서버 인스턴스를 만들지 않아도 API를 제공할 수 있으며, 서버 관리의 부담을 줄일 수 있다.

레디스 규모 확장

기존 규모보다 더 큰 규모로 확장하기 위해선 샤딩이 필요한데, 고정 파티션과 해시 파티션 두 가지 방법이 있다.

• 고정 파티션: 점수 범위에 따라 파티션을 나누는 방법
  • 0100점은 파티션 A, 101200점은 파티션 B 등
  • 해당 사용자가 어느 파티션에 속하는지 알아야 함(사용자ID-점수를 저장하는 2차 캐시를 통해 성능을 높일 수 있음)
  • 점수가 고르게 분포되어 있어야 기대하는 성능을 낼 수 있음
• 해시 파티션: 레디스 클러스터가 자동으로 샤딩
  • 각각의 키가 특정한 해시 슬롯에 속하도록 하는 샤딩 기법 사용
    • 16,384개의 해시 슬롯이 있으며, CRC16(key) % 16384로 해시 슬롯을 계산
    • 노드 별로 해시 슬롯 범위를 할당(0 - 5500은 노드 A, 5501 - 11000은 노드 B 등)
    • 해당 슬롯에 속하는 레디스 노드로 요청을 전달
  • 점수 분포가 고르지 않아도 성능을 유지할 수 있음
  • 상위 N명의 사용자 조회 시, 모든 노드에 요청을 보내고 응답을 합쳐야 하므로 성능이 저하될 수 있음

서비스 특성상 상위 N명의 사용자 조회가 빈번하게 발생하기 때문에, 고정 파티션을 사용하는 것이 더 적합할 수 있다.

추가 고려사항

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

레디스 해시를 사용하면 문자열 필드와 값 상의 대응관계를 저장하여 활용할 수 있다.

1. 순위표에 표시할 사용자 ID와 사용자 객체 사이의 대응 관계를 저장
   • 데이터베이스에 질의 하지 않고, 빠르게 사용자 정보를 조회할 수 있음
2. 두 사용자 점수가 같은 경우 누가 먼저 점수를 획득했는지 판별하기 위해, 사용자 ID와 점수 획득 시간을 함께 저장
   • 동점자 순위 판별을 위해 시간 정보를 추가하여, 동일 점수의 사용자 중 먼저 점수를 획득한 사용자가 상위 순위를 차지하도록 함

시스템 장애 복구

시스템 장애가 발생했을 때, 다음과 같은 복구 방법을 고려할 수 있다.

• RDB 스냅샷 / AOF(Append Only File) 로그를 사용하여 Redis 데이터를 복구
• MySQL에 점수 증감 이력을 저장하여, ZADD / ZINCRBY 명령어를 사용해 점수를 복구

참고자료

• 가상 면접 사례로 배우는 대규모 시스템 설계 기초 2