1. 요구사항 정리
•
온라인 게임의 리더보드 설계
•
순위표에 상위 10명의 플레이어를 표시한다.
•
특정 사용자의 순위를 표시한다.
•
어떤 사용자보다 4순위 위와 아래에 있는 사용자를 표시한다. (보너스 문제)
1.1. 비기능 요구사항
•
점수 업데이트는 실시간으로 순위표에 반영한다.
•
일반적인 확장성, 가용성 및 안정성 요구사항
1.2. 개략적 규모추정
•
DAU = 500만
•
초당 평균 사용자 = 50명
•
평균 값으로 추정하되 최대 부하는 평균의 5배로 가정
최대 부하량 = 5,000,000 / 10^5 X 5 = 250
Plain Text
복사
•
사용자 점수 획득 QPS = 500
•
한 사용자가 하루 평균 10개의 게임을 플레이한다고 가정
최대 QPS = 500 X 5 = 2,500
Plain Text
복사
•
각 사용자가 하루에 한 번 게임을 연다고 가정
•
상위 10명 순위표는 사용자가 처음 게임을 열 때만 표시한다고 가정
상위 10명 순위표 가져오기 QPS = 50
Plain Text
복사
2. 청사진 그리기
•
클라이언트가 순위표 서비스와 직접 통신하면 보안 문제(중간자 공격)가 있어서 게임 서비스에서 갱신한다.
•
게임 데이터를 다양하게 사용하기 위해서 메시지 큐를 사용할 수 있다.
2.1. 데이터베이스
•
RDB를 사용하면 지속적으로 변화하는 랭킹 시스템에 신속하게 대응하지 못한다.
◦
기본적으로 랭킹 데이터는 중요하지 않은 데이터에 속한다.
◦
캐시를 쓰는게 좋지 않겠는가?
•
그러니 우리는 레디스를 쓸꺼다.
◦
랭킹 시스템에 적합한 정렬 집합 자료형을 사용한다.
▪
내부적으로 해시테이블과 스킵 리스트를 가져서 사용자의 점수를 기준으로 미리 정렬해놓을 수 있다.
•
연결 리스트에 연산을 하면 O(n)만큼의 시간 복잡도를 가진다.
◦
더 빠르게 하기 위해서 이진 검색 알고리즘과 비슷하게 노드를 구성해서 만들자.
◦
1차 색인과 2차 색인을 나누어 중간 값을 통해서 더 적은 연산으로 결과에 도달할 수 잇다.
◦
그런데 데이터가 작으면 효과가 크게 체감되지 않는다.
•
레디스 정렬 집합 사용시?
◦
ZADD = 새로운 사용자의 집합 삽입 ( O(log(n) )
◦
ZINCRBY = 특정 사용자의 점수를 값만큼 증가시킴 ( O(log(n) )
◦
ZRANGE/ZREVANGE = 특정 범위에 드는 자들을 가져옴 ( O(log(n) + M )
▪
n = 정렬 집합의 크기
▪
m = 가져 올 항목 수
◦
ZRANK/ZREVRANK = 오름/내림차순 정렬 시 특정 사용자의 위치를 가져옴 ( O(log(n) )
•
저장소 요구사항
◦
ID가 24자 문자열이고 점수가 16비트 정수라고 한다면 순위표 한 항목당 26바이트가 필요
◦
최악을 가정하면 26바이트 X 2,500만 = 650M의 저장공간이 필요
◦
레디스 사용시 걱정해야할 부분은 영속성인데 레디스도 영속성을 지원하긴 한다.
▪
그런데 레디스 디스크도 장애가 날 수 있어서 사본 서버를 만들어서 방지해두자~
3. 실제 설계
3.1. 클라우드 사용?
자체 IDC이용
클라우드 사용
•
특별히 설명할 사항은 없는것 같다.
3.2. 레디스 규모 확장
•
5억 DAU 사용시 65GB의 저장공간 / 250,000QPS의 질의 처리가 가능해야함
◦
1대로는 역부족
3.2.1. 데이터 샤딩 방안
•
고정 파티션을 통한 방안
◦
말 그대로 고정된 파티션으로 나누는 방식
◦
적절히 조정해서 고르게 분포됐다고 가정
◦
어디에 어느 사용자가 있는지 2차 캐시를 사용하면 보다 빠르게 갱신이 가능
◦
상위 사용자는 가장 점수가 높은 샤드만 찾으면 됨
•
해시 파티션을 통한 방안
◦
각 키가 특정한 해시 슬록에 속하도록 하는 샤딩 기법
◦
총 16384개의 해시 슬롯이 있으며, CRC16(key) % 16384의 연산을 통해 어느 슬롯에 속할지 계산함
◦
k개의 결과를 반환하는 경우 각 샤드에서 읽고 정렬해야 해서 지연이 발생
◦
특정 사용자의 순위를 결정할 간단한 방법이 없음
⇒ 결론 : 고정파티션 사용
•
NoSQL을 대안으로 사용할 수 있다.
◦
쓰기 연산 최적화, 파티션 내 항목 점수를 효율적으로 정렬 가능
