[가상면접 사례로 배우는 대규모 시스템 설계 기초2] 10장. 실시간 게임 순위표

10장. 실시간 게임 순위표 

1단계 : 문제 이해 및 설계 범위 확장 

기능 요구사항

• 순위표에 상위 10명의 플레이어를 표시한다.
• 특정 사용자의 순위를 표시한다. 
• 어떤 사용자보다 4순위 위와 아래에 있는 사용자를 표시한다. (보너스 문제)

비기능 요구사항

• 점수 업데이트는 실시간으로 순위표에 반영한다. 
• 일반적인 확장성, 가용성 및 안정성 요구사항 

개략적 규모 측정 

• 사용자수
  • 게임을 하는 사용자가 24시간 동안 고르게 분포한다고 자정하면 DAU가 500만 명인 게임의 경우 초당 평균 50명의 사용자가 게임을 플레이하게 된다. 
  • 하지만 그렇게 사용량이 균등한 경우는 별로 없으며, 서로 다른 시간대의 사람들이 동시에 게임할 수 있는 북미 지역 기준 저녁 시간이 피크 시간대일 가능성이 높다. 
  • 이를 고려하기 위해 최대 부하는 평균의 다섯 배라고 가정한다. 
  • 따라서 초당 250명의 사용자를 감당할 수 있어야 한다. 
• 사용자 점수 획득 QPS : 한 사용자가 하루 평균 10개의 게임을 플레이한다고 가정하면, 점수를 획득하는 이벤트가 발생하는 QPS는 50 * 10 = 500가량이다. 최대 QPS가 평균의 5배이므로 500 * 5 = 2500 QPS 이다. 
  • 책에서는 이렇게 이야기하지만, 정확하게는 2500 / 
• 상위 10명 순위표 가져오기 QPS : 각 사용자가 하루에 한 번 게임을 열고 상위 10명 순위표는 사용자가 처음 게임 열때만 표시한다고 가정하면, QPS는 약 50이다. 

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

개략적 설계안 

• 게임 서비스 : 사용자가 게임을 플레이할 수 있도록 한다.
• 순위표 서비스 : 순위표를 생성하고 표시하는 역할을 담당한다. 

 

클라이언트가 순위표 서비스와 직접 통신해야 하나 ?

• 중간자 공격 (man-in-the-middle at-tack)을 할 수 있기 때문에 보안상 안전하지 않다. 
• 따라서 점수는 서버가 설정해야 한다. 

 

게임 서비스와 순위표 서버 사이에 메시지 큐가 필요한가 ?

• 이 질문에 대한 답은 게임 점수가 어떻게 사용되는지에 따라 크게 달라진다. 
  • 해당 데이터가 다른 곳에서도 이용되거나 여러 기능을 지원해야 한다면 카프카에 데이터를 넣는 것이 합리적일 수 있다. 
  • (순위표 서비스, 분석 서비스, 푸시 알림 서비스 등)

 

 

데이터 모델 

관계형 데이터베이스의 한계 

• 관계형 데이터베이스는  데이터가 많지 않을 때는 효과적이지만,
• 레코드가 수백만 개 정도로 많아지면 성능이 너무 나빠지는 문제가 있다. 
• 사용자의 순위를 파악하려면 모든 플레이어를 순위표의 정확한 위치에 정렬해야 한다.
• 수백만 개 레코드에 순위를 매기려면 대략 수십 초 정도가 걸리므로, 실시간성 요구하는 애플리케이션에 적합하지 않다. 
• 데이터가 지속적으로 변경되기 때문에 캐시 도입도 불가능하다. 

 

레디스

• 레디스는 메모리 기반 키-값 저장소 시스템이다. 
• 메모리에서 동작하므로 빠른 읽기 및 쓰기가 가능하다. 
• 정렬 집합 (sort-set) 이라는 자료형을 제공한다. 

 

정렬 집한이란 ?

• 정렬 집합은 집합과 유사한 자료형이다. 
• 정렬 집합은 내부적으로 해시 테이블과 스킵 리스트라는 두 가지 자료 구조를 사용한다. 
  • 해시 테이블은 사용자의 점수를 저장하기 위해서,
  • 스킵 리스트는 특정 점수를 딴 사용자들의 목록을 저장하기 위해 쓰인다. 

 

 

 

Redis Sorted Set으로 랭킹보드 구현

 

저장소 요구사항

 

저장공간

• 최소한 사용자 ID와 점수는 저장해야 한다. 
  • ID가 24자 문자열이고 점수가 16비트라고 하면, 순위표당 26바이트가 필요하다. 
• 최악의 시나리오는 월간 활성 사용자 2,500만 명 모두가 최소 한 번 이상 게임에서 승리하는 바람에 모두 월 순위표에 올라야 하는 경우이다. 
  
  • 26 바이트 * 2,500만 = 6억 5,000만 바이트 (약 650MB의 저장공간이 필요하다(

CPU 및 I/O 사용량

• 갱신 연산의 최대 QPS는 2500/초 정도였다. 이는 단일 레디스 서버로도 충분히 감당할 수 있는 부하다. 

 

데이터의 영속성 

• 레디스에도 장애가 발생할 수 있다. 
• 데이터를 디스크에 영속적으로 보관하는 옵션을 지원하므로 사용하면 된다. 그러나 디스크에서 데이터를 읽어 대규모 레디스 인스턴스를 재시작하려면 시간이 걸린다. 
• 그래서 보통은 레디스에 읽기 사본을 두는 식으로 구성한다. 

 

3단계 : 상세 설계 

레디스 규모 확장

• 데이터 샤딩 방안 
  • 고정 파티션
    • 순위표 등장하는 점수의 범위에 따라 파티션을 나눈다. 
    • 순위표 전반에 점수가 고르게 분포되어야 한다. 
  • 해시 파티션 
    • 사용자들의 점수가 특정 대역에 과도하게 모여 있는 경우에 효과적이다. 
    • 각각의 키가 특정한 해시 슬롯에 속하도록 하는 샤딩 기법을 사용한다. 
    • 상위 10명을 검색하는 것이 까다롭다. 
      • 모든 샤드에서 상위 10명을 받아 애플리케이션 내에서 다시 정렬해야 한다. 
    • 다음과 같은 문제가 발생한다. 
      • 상위 k개의 결과를 반환해야 하는 경우, 각 샤드에서 많은 데이터를 읽고 또 정렬해야 하므로 지연 시간이 늘어난다. 
      • 가장 느린 파티션에서 데이터 다 읽고 나서야 질의 결과를 계산할 수 있으므로 지연 시간이 길어진다. 
      • 특정 사용자의 순위를 결정할 간단한 방법이 없다. 
  • 따라서 고정 파티션 방안을 사용한다. 

 

대안 : NoSQL

• 다음과 같은 데이터베이스가 이상적이다. 
  • 쓰기 연산에 최적화되어 있다. 
  • 같은 파티션 내의 항목을 점수에 따라 효율적으로 정렬 가능하다. 
• 좋은 후보로는 아마존의 DynamoDB, 카산드라 또는 MongoDB 등이 있다. 

 

4단계 : 마무리 

• 다음 몇 가지 주제를 살펴볼 수 있다. 
  • 더 빠른 조회 및 동점자 순위 판정 방안 
  • 시스템 장애 복구