실시간 리더보드 만들어보기

 

이 글은 아래의 글을 바탕으로 작성하였습니다.

Design a Real-Time Leaderboard system for millions of users

 

들어가며

안녕하세요. 오늘은 Medium 글에서 흥미로운 주제를 발견하여 직접 따라 해보고, 이에 대해소개하고자 합니다.  

이번에 다룰 주제는 게임이나 검색어 분야에서 흔히 사용되는 '랭킹 시스템 구축'입니다.
게임 유저의 점수를 실시간으로 수집하여 랭킹을 보여주는 시스템을 설계하고 이를 유저에게 보여줘야합니다.
이 과정을 통해 랭킹 시스템 설계의 핵심 개념과 실제 구현 방법에 대해 설명하겠습니다.

 

 

결과물

 

 

 

요구사항 분석

시스템 설계를 시작하기 전에 요구사항을 분석하는 것은 중요합니다. 

요구사항을 이해할 때 개발자의 머리에는 자연스럽게 해결책이 떠오르기 마련이지만, 성급하게 결론을 내리기보다는 문제를 깊이 이해하고 구체적인 요구에 부합하는 솔루션을 마련하는 것이 핵심입니다.

 

주요 요구사항은 다음과 같습니다

활성 시스템 사용자 수: 5,000만 명
일일 활성 사용자 수: 1,000만 명
리더보드 업데이트 주기: 실시간 또는 거의 실시간
데이터 일관성: 최종 일관성은 허용 가능
UI의 요구사항: 상위 10명의 사용자와 그들의 순위를 보여주는 기능

 

부하 계산

시스템의 성능을 계획할 때는 예상되는 부하를 미리 계산해보는 것이 중요합니다. 

예를 들어, 일일 활성 사용자 수가 1,000만 명이라고 가정할 때 초당 요청 수(RPS)를 계산해 보겠습니다.

 

(일일 활성 사용자)/(24*60*60) => 10,000,000/24*60*60 = 115RPS

더욱 극단적인 상황을 대비하기 위해 평균 부하의 10배를 적용하여 1,150 RPS를 기준으로 설계를 고려해 보겠습니다. 

이는 최악의 경우에도 시스템이 안정적으로 운영될 수 있도록 합니다

 

 

 

기본적인 시스템 구성

https://medium.com/@mayilb77/design-a-real-time-leaderboard-system-for-millions-of-users-08b96b4b64ce

 

시스템의 기본 구조는 다음과 같은 흐름으로 구성됩니다:

 

• 게임 점수 이벤트 발행 서비스: 유저의 점수를 이벤트로 발행합니다.
• RDB 저장 서비스: 기본 데이터를 관계형 데이터베이스에 저장합니다.
• Redis 저장 및 리더보드 변경 이벤트 발행 서비스: 점수를 Redis에 기록하고 리더보드 업데이트 이벤트를 발행합니다.
• 리더보드 변경 이벤트 수신 및 리더보드 업데이트 이벤트 발행 서비스: 변경된 데이터를 바탕으로 리더보드를 갱신합니다.
• 리더보드 업데이트 이벤트 수신 및 소켓 연결 서비스: 최종 리더보드 데이터를 클라이언트에 실시간으로 전달합니다.

 

 

 

데이터베이스 선택

시스템 설계 시 데이터의 특성과 요구사항에 맞게 데이터베이스를 선택하는 것이 중요합니다.

RDBMS는 데이터의 안정적인 보관과 복잡한 쿼리를 지원하지만, 성능 측면에서 모든 요구를 충족하지 못할 수도 있습니다.

예를 들어, RDB에 사용자의 점수를 저장하고 랭킹을 집계한다고 가정해 보겠습니다

 

SELECT user_id, SUM(score_amount) AS total_score
FROM user_score
GROUP BY user_id
LIMIT 10;

 

 

실제로, 수천만 명의 사용자가 활성화된 환경에서는 각 점수를 매번 정렬하는 작업이 성능의 병목이 될 수 있습니다. 

따라서 RDBMS는 데이터 저장에는 적합하지만, 실시간 집계는 더 빠른 성능을 요구하기 때문에 Redis와 같은 인메모리 데이터베이스를 사용하는 것이 효율적입니다.

RDB는 안정적인 데이터 보관소로서의 역할을 담당하고, 실시간 집계는 Redis로 옮겨서 수행하는 방안을 선택하였습니다.

 

 

RDB에서의 데이터 Sum 시간 테스트 

-- user_score 테이블 생성
CREATE TABLE user_score (
  score_id INT AUTO_INCREMENT PRIMARY KEY,
  user_id INT NOT NULL,
  score_date DATE NOT NULL,
  score_amount DECIMAL(10, 2) NOT NULL
);

-- 데이터 삽입 스크립트
DELIMITER //

CREATE PROCEDURE populate_user_score_bulk()
BEGIN
    DECLARE i INT DEFAULT 1;
    DECLARE bulk_insert_size INT DEFAULT 500;  -- 한 번에 삽입할 행 수를 500으로 설정
    DECLARE insert_statement TEXT;  -- TEXT 타입으로 선언

    SET insert_statement = 'INSERT INTO user_score (user_id, score_date, score_amount) VALUES ';

    WHILE i <= 10000000 DO
        SET insert_statement = CONCAT(insert_statement,
            '(', FLOOR(RAND() * 10000) + 1, ', ',
            'DATE_ADD("2020-01-01", INTERVAL FLOOR(RAND() * 1000) DAY), ',
            ROUND(RAND() * 1000 + 1, 2), '),' );

        IF i MOD bulk_insert_size = 0 OR i = 10000000 THEN
            -- 마지막 쉼표 제거 후 세미콜론 추가
            SET insert_statement = LEFT(insert_statement, CHAR_LENGTH(insert_statement) - 1);
            SET @final_query = insert_statement;  -- 변수를 통해 전달
            PREPARE stmt FROM @final_query;
            EXECUTE stmt;
            DEALLOCATE PREPARE stmt;

            -- 초기화
            SET insert_statement = 'INSERT INTO user_score (user_id, score_date, score_amount) VALUES ';
        END IF;

        SET i = i + 1;
    END WHILE;
END;
//

DELIMITER ;


-- 프로시저 실행
CALL populate_user_score_bulk();

-- 인덱스 생성
CREATE INDEX idx_user_id ON user_score (user_id);

-- 사용자별 총점 조회
SELECT user_id, SUM(score_amount) AS total_score
FROM user_score
GROUP BY user_id
LIMIT 10;

 

약 3,000만 건의 데이터와 계속해서 새로운 데이터가 들어오는 상황에서의 쿼리 실행 시간입니다.
MySQL에서 인덱스가 적용된 상태로 동일한 쿼리를 3번 실행했을 때, 최악의 경우 26초가 소요되었습니다

 

 

 

Redis SortedSet을 활용한 랭킹 시스템

Redis는 인메모리 데이터베이스로서 높은 성능을 제공합니다. 

여기서는 랭킹을 계산하기 위해 Redis의 자료구조인 SortedSet을 사용합니다. 

SortedSet은 각 요소가 점수(score)에 따라 정렬된 컬렉션으로, 점수 기반의 랭킹 시스템 구현에 적합합니다.

Redis SortedSet의 장점

이전에 언급한 RDB의 한계를 보완하기 위해 Redis의 SortedSet 구조를 사용하면, 유저의 점수 합계를 사전에 저장하고 효율적으로 집계할 수 있습니다.

인메모리 구조이므로 RDB보다 많은 데이터를 더 빠르게 처리할 수 있으며, 5천만 명의 사용자를 다루는 시스템에서도 성능을 보장할 수 있습니다.

 

시간 복잡도 분석

많은 데이터를 처리할 때는 사용되는 연산의 시간 복잡도를 이해하고 최적화하는 것이 필수적입니다. 

Redis의 SortedSet에서 점수를 증가시킬 때는 ZINCRBY 연산을 사용하며, 이 연산은 O(log(N))의 시간 복잡도를 가집니다.

여기서 N은 집합의 요소 수입니다.

랭킹을 구할 때는 ZRANGE key start stop 연산을 사용하며, 시간 복잡도는 O(log(N) + M)입니다.

M은 반환되는 요소의 수를 나타냅니다.

이처럼 O(N)의 복잡도를 가지는 연산을 피하고 효율적인 메서드를 사용하는 것이 중요합니다.

 

 

배달의 민족에서도 대기열을 구현할 때 SortedSet을 사용해 구현했다고 하네요.

 

 

 

캐시 전략의 도입

 

 

시스템 설계에서 성능 최적화를 위해 캐시를 도입할 수 있습니다. 

유저 요청이 초당 1150건이라면, 초당 1150번의 랭킹 업데이트 요청을 UI에 반영할 필요는 없습니다. 

따라서 캐시 전략을 사용해 효율성을 높입니다.

캐시 전략의 개념

leaderboard_change 이벤트 수신 & leaderboard_update 이벤트 발행 서비스에서는 랭킹 데이터를 주기적으로 갱신하고, 이를 캐시에 저장해 일정 시간 동안 동일한 데이터를 사용합니다. 

이를 통해 모든 유저가 실시간으로 업데이트되는 대신, 주기적으로 업데이트된 데이터를 UI에 반영할 수 있습니다.

캐시의 throttle시간을 설정해, 캐시에 저장된 데이터의 최신 업데이트 시간을 확인하고 필요할 때만 갱신을 수행합니다.
미래에는 랭킹에 변화가 있을 때만 UI를 업데이트하는 방향으로 발전할 수도 있습니다.

 

효율적인 조회

랭킹 10명의 데이터를 Redis에 캐시하면 O(1) 시간 복잡도의 조회가 가능합니다.

즉, 매우 빠른 속도로 사용자 랭킹을 확인할 수 있어 UI 반응 속도를 높이고 시스템 부하를 줄일 수 있습니다.

 

 

추가 이점캐시의 추가 이점

캐시 전략은 성능을 높이는 또 다른 이점도 제공합니다.

예를 들어, 초당 1,000번의 랭킹 요청이 발생하는 상황에서, Redis 인스턴스에 모든 요청을 처리하게 하는 것은 비효율적일 수 있습니다.

Redis는 싱글 스레드로 동작하기 때문에 많은 유저가 동시에 접근하면 성능 저하가 발생할 수 있습니다.

따라서 Redis 인스턴스를 캐시 서버와 별개로 분리해 운영하면 유저는 정렬된 랭킹 보드만 확인하게 되어, 더 높은 성능을 유지할 수 있습니다. 이 방법은 병목을 방지하고 서비스의 안정성을 강화하는 데 기여합니다.

 

 

 

마치며

Medium 글에서는 흥미로운 주제들이 많이 다뤄지고 있습니다. 

이러한 주제들을 따라 해보면 개발에 더욱 재미를 느낄 수 있는 것 같습니다. 

실무에서 경험하지 못한 문제들에 대해서도 고민하고 다른 사람들의 노하우를 접하며 학습할 수 있어 좋은 기회라고 생각합니다.

한국의 테크 회사들이 발행한 기술 글들도 매우 유익하여 따라 해보는 것이 좋습니다.

 

 

Sample Code

위의 내용을 기반으로 코드를 작성했습니다.

GitHub - ChoiGiSung/real-time-leader-board: This project is a real-time leaderboard application built with Spring Boot, WebSocke