Datastore의 신속하고 안정적인 순위 구현

순위: 단순하지만 매우 까다로운 문제

Applibot에서 App Engine 책임 엔지니어로 근무하고 있는 Tomoaki Suzuki(그림 1)는 모든 대규모 게임 서비스에서 공통적으로 직면하고 있는 순위라는 까다로운 문제를 해결하기 위해 노력하고 있습니다.

그림 1: Applibot, Inc.에서 App Engine 책임 엔지니어로 근무 중인 Tomoaki Suzuki

Applibot은 일본의 대형 소셜 애플리케이션 제공업체 중 하나입니다. 이 기업의 차별성은 Google의 Platform as a Service(PaaS)인 Google App Engine을 기반으로 확장성이 매우 우수한 소셜 게임 서비스를 빌드하는 데 폭넓은 지식과 경험을 갖추고 있다는 점입니다. Applibot은 이 플랫폼의 기능을 활용하여 일본뿐 아니라 미국에서도 소셜 게임 시장의 비즈니스 기회를 잡는 데 성공했습니다. Applibot은 수치로 그 성공을 입증할 수 있습니다. Legend of the Cryptids(그림 2)는 이 기업의 대표적인 인기 게임 타이틀로, 2012년 Apple AppStore North America 게임 카테고리에서 1위에 올랐습니다. Legend 시리즈는 470만 회의 다운로드를 기록한 바 있으며 다른 타이틀인 Gang Road는 2012년 12월에 AppStore Japan에서 총매출 1위를 차지하기도 했습니다.

그림 2: Legend of the Criptids(2012년 10월 Apple AppStore에서 1위에 오른 게임)

이러한 게임 타이틀은 원활한 확장을 통해 급증하는 트래픽을 처리할 수 있었습니다. Applibot은 가상 서버 또는 분할 데이터베이스의 복잡한 클러스터를 구축하느라 어려움을 겪을 필요가 없었습니다. App Engine의 성능을 활용한 결과 확장성과 가용성을 모두 효율적으로 달성할 수 있었습니다.

그러나 플레이어의 순위를 업데이트하는 것은 간단한 문제가 아닙니다. Tomoaki뿐 아니라 특히 이 정도 규모라면 어느 개발자에게도 마찬가지입니다. 요구사항 자체는 단순합니다.

플레이어 수십만 명 이상이 게임을 진행함
플레이어가 적과 싸우거나 다른 활동을 할 때마다 점수가 바뀜
웹 포털 페이지에서 플레이어의 최신 순위를 표시해야 함

순위 계산 방식

그림 3: 플레이어마다 점수가 있습니다. 그렇다면 순위를 어떻게 계산할까요?

확장성과 신속성에 대한 기대만 없다면 순위를 구하는 방법은 간단합니다. 예를 들면 다음과 같은 쿼리를 실행할 수 있습니다.

SELECT count(key) FROM Players WHERE Score > YourScore

이 쿼리는 나보다 점수가 높은 모든 플레이어를 집계합니다(그림 4). 하지만 포털 페이지의 모든 요청에 대해 이 쿼리를 실행해야 할까요? 플레이어가 100만 명에 달한다면 얼마나 오랜 시간이 걸릴까요?

Tomoaki도 처음에는 이 방식을 도입했으나 매번 응답을 받는 데 수 초가 걸렸습니다. 속도는 느렸고 비용은 높았으며 규모가 커짐에 따라 성능도 점점 저하되었습니다.

Tomoaki는 차선으로 Memcache에 순위 데이터를 유지하려 했습니다. 속도는 빨랐지만 안정성이 떨어졌습니다. Memcache 항목은 언제든 삭제될 수 있었고 때로는 Memcache 자체 서비스가 중단되는 일도 있었습니다. 인메모리 키-값에만 의존한 순위 서비스로는 일관성과 가용성을 유지하기가 힘들었습니다.

임시방편으로 Tomoaki는 서비스 수준을 낮추기로 결정했습니다. 매 요청마다 순위를 계산하는 대신 한 시간에 한 번씩 모든 플레이어의 순위를 스캔하고 업데이트하도록 예약 작업을 설정한 것입니다. 이 방법으로 포털 페이지의 요청은 플레이어 순위를 즉시 가져올 수 있었지만 최대 1시간 전의 정보일 수도 있었습니다.

결국 Tomoaki는 초당 300회의 점수 업데이트 요청을 수락하고 수백 밀리초 내에 각 플레이어의 순위를 가져올 수 있으며 지속성, 트랜잭션 기반, 속도, 확장성을 두루 갖춘 순위 구현 방식을 찾아야 했습니다. 솔루션을 찾기 위해 Tomoaki는 SA(솔루션 아키텍처)인 Kaz Sato에게 도움을 청했고 Kaz Sato는 Google Cloud Platform팀의 TAM(기술계정 관리자)으로서 프리미엄 레벨의 지원 계약을 맺은 Applibot을 담당하게 되었습니다.

문제를 해결하는 지름길

Applibot과 같은 Google Cloud Platform의 많은 대기업 고객 또는 파트너는 프리미엄 레벨의 지원 계약에 가입합니다. 이러한 지원 계약을 맺는 경우 Google은 Cloud 고객지원팀의 연중무휴 24시간 지원 및 Cloud Sales팀의 비즈니스 지원과 더불어, 각 고객에게 TAM(기술계정 관리자)을 할당합니다.

TAM은 고객의 대리인이 되어 실제 클라우드 인프라를 빌드하는 Google Engineering팀과 협업합니다. TAM은 고객의 시스템과 아키텍처를 상세히 파악합니다. 그리고 고객이 중요 사안을 제기하면 기업의 Google Engineering 담당자로서 지니고 있는 지식과 네트워크를 동원해 문제를 해결하는 역할을 합니다. TAM은 팀 내 솔루션 아키텍처 또는 Cloud Platform 팀의 소프트웨어 엔지니어에게 이 문제를 이관할 수 있습니다. 이와 같은 프리미엄 레벨 지원이야말로 Google Cloud Platform의 솔루션을 찾을 수 있는 지름길입니다.

Kaz는 Applibot을 담당하는 TAM으로서, 순위가 모든 확장형 분산 서비스에 늘 있어온 문제이지만 해결이 어렵다는 사실을 인지하고 있었습니다. 그는 Applibot의 요구사항을 만족하는 솔루션을 찾기 위해 앞서 Google Cloud Datastore와 기타 NoSQL 데이터 저장소를 기반으로 순위를 구현한 사례를 살펴보았습니다.

O(log n) 알고리즘 모색

단순한 쿼리 솔루션에서는 특정 플레이어의 순위를 계산하기 위해 점수가 더 높은 모든 플레이어를 검색해야 했습니다. 이 알고리즘의 시간 복잡성이 O(n)입니다. 즉, 쿼리 실행에 필요한 시간이 플레이어 수에 비례하여 늘어난다는 의미이며 실제로는 알고리즘이 확장 불가능하다는 의미이기도 합니다. 그보다는 플레이어 수가 늘어남에 따라 시간이 대수적으로 늘어나는 O(log n) 또는 그보다 신속한 알고리즘이 필요합니다.

컴퓨터 공학 강의를 들어본 적이 있다면 이진 트리, 레드-블랙 트리, B-트리와 같은 트리 알고리즘이 O(log n) 시간 복잡도로 요소를 찾는 작업을 수행할 수 있다는 사실을 기억할 것입니다. 집계된 값을 각 브랜치 노드에 포함하는 방식으로 집계, 최대/최소, 평균값과 같은 다양한 요소의 집계 값을 계산하는 데에도 트리 알고리즘을 사용할 수 있습니다. 이 기술을 사용하면 O(log n) 성능으로 순위 알고리즘을 적용하는 것이 가능합니다.

Kaz는 Google 엔지니어가 작성한 오픈소스 구현 사례 중 Datastore를 위한 트리 기반 순위 알고리즘인 Google Code Jam 순위 라이브러리를 발견했습니다.

이 Python 기반의 라이브러리에서는 두 가지 메서드가 있습니다.

SetScore는 플레이어의 점수를 설정합니다.
FindRank는 특정 점수의 순위를 가져옵니다.

플레이어 점수 쌍은 SetScore 메서드를 통해 생성 및 업데이트되므로 Code Jam 순위 라이브러리는 N항 트리를 빌드합니다¹. 점수가 0~80점인 플레이어 수를 셀 수 있는 3단 트리(그림 5)를 예로 들어보겠습니다. 라이브러리는 3개 숫자를 하나의 항목으로 보유하는 루트 노드를 저장합니다. 각 숫자는 점수가 각각 0~26, 27~53, 54~80의 하위 범위인 플레이어 수에 해당됩니다. 루트 노드에는 각 범위마다 하위 노드가 있으며 하위 범위의 하위 범위에는 플레이어의 값 3개가 존재합니다. 이 계층구조는 서로 다른 점수 값 81개에 해당하는 플레이어 수를 저장하도록 4층 레벨로 구성되어야 합니다.

점수가 30점인 플레이어의 순위를 확인하려면 라이브러리는 4가지 항목(도식에서 점선 동그라미로 표시된 노드)만 읽어 점수가 30점이 넘는 플레이어의 수를 더해야 합니다. 4개 항목에서 '오른쪽'에 있는 플레이어가 22명이므로 해당 플레이어의 순위는 23위가 됩니다.

마찬가지로 SetScore 호출도 4개 항목만 업데이트하면 됩니다. 엄청나게 많은 각종 점수가 있지만 Datastore 액세스는 O(log n)의 수만 늘리고 플레이어 수와는 상관이 없습니다. 실제로 Code Jam 순위 라이브러리는 노드당 기본값으로 3 대신 100을 사용하므로 단 2개 항목(점수 범위가 10만 점 초과이면 3개)을 액세스해야 합니다.

Kaz는 인기 있는 로드 테스트 도구인 Apache JMeter를 사용하여 Code Jam 순위 라이브러리에 대한 로드 테스트를 수행하고 라이브러리의 응답 속도가 빠름을 확인했습니다. SetScore 및 FindRank 모두 O(log n) 시간 복잡도로 작동하는 N항 트리 알고리즘을 사용하여 수백 밀리초 내에 작업을 마칠 수 있습니다.

확장성을 제한하는 동시 실행 업데이트

그러나 로드 테스트 도중 Kaz는 Code Jam 순위 라이브러리의 치명적인 제약을 발견했습니다. 업데이트를 처리하는 확장성이 매우 낮았던 것입니다. 로드를 초당 업데이트 3회까지 높이자 라이브러리에서 트랜잭션 재시도 오류를 반환하기 시작했습니다. 라이브러리가 초당 300회 업데이트라는 Applibot의 요구사항을 충족하지 못하는 것은 당연했습니다. 필요한 처리량의 약 1%밖에 처리할 수 없었습니다.

그 이유는 트리의 일관성을 유지한 데 따른 대가였습니다. Datastore에서는 트랜잭션 중 여러 항목을 업데이트할 때 strong consistency를 확보하도록 항목 그룹을 사용해야 합니다('Google Cloud Datastore에서 strong consistency와 eventual consistency 간에 균형 유지' 참조). Code Jam 순위 라이브러리는 트리 요소 개수의 일관성을 유지하기 위해 단일 항목 그룹에 전체 트리를 보유합니다.

그러나 Datastore의 항목 그룹에는 성능 제한이 있습니다. Datastore는 항목 그룹에서 초당 약 1회의 트랜잭션만 지원합니다. 그뿐만 아니라 동시 실행 트랜잭션에서 동일한 항목 그룹이 수정되면 실패할 확률이 높아 다시 시도해야 합니다. Code Jam 순위 라이브러리는 강력한 일관성, 트랜잭션, 빠른 속도를 지녔지만 대량의 동시 실행 업데이트는 지원하지 못합니다.

Datastore팀의 솔루션: 작업 집계

Kaz는 Datastore팀의 소프트웨어 엔지니어가 항목 그룹에서 초당 1회의 업데이트보다 훨씬 높은 처리량을 기록한 기술에 대해 했던 이야기를 기억했습니다. 각 업데이트를 별도의 트랜잭션으로 실행하기보다는 일괄 업데이트를 하나의 트랜잭션으로 집계하는 방식이었습니다. 그러나 트랜잭션에 많은 수의 업데이트가 포함되기 때문에 각 트랜잭션 시간이 오래 걸려 동시 실행 트랜잭션의 충돌 가능성이 높아집니다.

Kaz의 요청에 따라 Datastore팀에서 이 문제를 논의한 결과 Megastore와 함께 사용한 설계 패턴 중 하나인 작업 집계를 사용해 보라는 조언을 해주었습니다.

Megastore는 Datastore의 기본 스토리지 레이어로서 항목 그룹의 일관성과 트랜잭션 특성을 관리합니다. 초당 1회의 업데이트 제한은 이 레이어로 인한 것입니다. Megastore가 다양한 Google 서비스에서 광범위하게 사용되는 만큼 엔지니어는 이 NoSQL 데이터 저장소를 이용해 확장 가능하고 일관된 시스템을 빌드하기 위해 우수사례와 설계 패턴을 수집하고 내부적으로 공유하고 있습니다.

작업 집계의 기본적인 개념은 일괄 업데이트를 처리하는 데 단일 스레드를 사용하는 것입니다. 항목 그룹에는 단 하나의 스레드와 트랜잭션만 열려있는 상태이므로 동시 실행 업데이트로 인한 트랜잭션 장애는 없습니다. VoltDb 및 Redis와 같은 다른 스토리지 제품에서도 유사한 아이디어를 찾아볼 수 있습니다.

그러나 작업 집계 패턴에도 단점이 있습니다. 모든 업데이트를 집계하는 데 단 하나의 스레드만 사용한다는 것입니다. 이 점은 Datastore에 업데이트를 전송할 수 있는 속도에 제약으로 작용했습니다. 따라서 작업 집계가 초당 300회의 업데이트라는 Applibot의 처리량 요건을 충족할 수 있는지 여부를 결정하는 것이 중요했습니다.

가져오기 대기열을 통한 작업 집계

Datastore팀의 조언을 기반으로 Kaz는 Code Jam 순위 라이브러리와 작업 집계 패턴을 조합하는 PoC(개념 증명) 코드를 작성했습니다. PoC에는 다음과 같은 구성요소가 있습니다.

프런트엔드: 사용자로부터 SetScore 요청을 수락하고 pull 큐에 태스크로 추가합니다.
pull 큐: 프런트엔드로부터 SetScore 업데이트 요청을 받아 유지합니다.
백엔드: 큐에서 업데이트 요청을 가져와서 Code Jam 순위 라이브러리로 실행하는 단일 스레드로 무한 루프를 실행합니다.

PoC는 pull 큐를 만듭니다. 이 큐는 App Engine 태스크 큐의 한 종류로, 개발자는 이 큐를 사용하여 큐에 추가된 태스크를 사용하는 작업자를 한 개 이상 구현할 수 있습니다. 백엔드 인스턴스는 단일 스레드를 무한 루프로 돌려 대기열에서 가능한 한 많은 작업(최대 1,000개)을 계속 가져옵니다. 스레드는 각 업데이트 요청을 Code Jam 순위 라이브러리로 전달하고 이 라이브러리는 단일 트랜잭션에서 이 요청을 일괄 실행합니다. 트랜잭션이 열리는 데 1초 이상 걸릴 수도 있지만 단일 스레드가 라이브러리 및 Datastore를 구동하고 있기 때문에 경합 및 수정이 동시에 실행되는 문제가 없습니다.

백엔드 인스턴스는 모듈로 정의됩니다. App Engine의 기능인 이 모듈은 개발자가 다양한 특성으로 애플리케이션 인스턴스를 정의하도록 허용하는 역할을 합니다. 이 PoC에서 백엔드 인스턴스는 수동 확장 인스턴스로 정의됩니다. 이러한 단 하나의 인스턴스는 언제든 실행됩니다.

Kaz는 JMeter를 사용하여 이 PoC에 대한 로드 테스트를 실시했습니다. 그 결과 해당 PoC가 트랜잭션당 500~600회 업데이트 배치에 대해 초당 200개의 SetScore 요청을 처리할 수 있는 것을 확인했습니다. 작업 집계가 효과가 있는 것입니다.

안정적인 성능을 위한 대기열 분할

하지만 얼마 지나지 않아 Kaz는 다른 문제를 발견했습니다. 몇 분 정도 테스트를 계속 실행하자 가져오기 대기열의 처리량이 수시로 변동된 것입니다(그림 6). 특히 수 분간 초당 태스크 200개씩 큐에 요청을 계속 추가했더니 큐가 갑자기 백엔드에 대한 태스크 전달을 중지했고 각 태스크의 지연 시간이 현저하게 증가했습니다.

Kaz는 이 문제의 원인을 찾기 위해 태스크 큐팀에 자문을 요청했습니다. 작업 대기열 팀에 따르면 현재 가져오기 대기열 구현에서 영구 레이어로 Bigtable을 사용하는 경우 발생하는 알려진 동작이었습니다. Bigtable 태블릿이 지나치게 커지면 여러 태블릿으로 분할됩니다. 태블릿이 분할되는 동안에는 작업이 전달되지 않고, 대기열이 작업을 수신하는 속도가 높아지면 성능 변동으로 이어지는 것입니다. 작업 대기열 팀에서 이러한 성능 특성을 개선하기 위한 작업이 아직 끝나지 않은 상태였습니다.

이때 솔루션 아키텍처인 Michael Tang이 대기열 분할을 사용한 해결책을 제시했습니다. 단 하나의 대기열을 사용하는 대신 여러 대기열에 로드를 분산하라는 조언이었습니다. 태블릿 분할의 영향을 최소화하고 높은 작업 처리 속도를 유지하기 위해 각 대기열을 여러 Bigtable 태블릿 서버에 저장할 수 있습니다. 하나의 대기열이 분할을 처리하는 동안에도 다른 대기열이 작업을 계속하고, 분할로 인해 각 대기열의 로드가 낮아지므로 태블릿이 분할되는 빈도도 낮아지게 됩니다.

이와 같이 개선된 백엔드 인스턴스 루프는 다음과 같은 알고리즘을 실행합니다.

큐 10개에서 SetScore 태스크를 임대합니다.
태스크로 SetScores 메서드를 호출합니다.
대여한 태스크를 큐에서 삭제합니다.

1단계에서는 플레이어의 이름과 점수를 보유한 각 작업을 큐당 최대 1,000개씩 공급합니다. 모든 플레이어-점수 쌍을 사전에 집계한 후 2단계에서 Code Jam 순위 라이브러리의 SetScores 메서드로 일괄 업데이트를 전달하면 이를 Datastore에 저장하는 트랜잭션이 열립니다. 메서드를 실행하는 데 어떠한 오류도 발생하지 않았으면 3단계에서는 대여한 태스크를 큐에서 삭제합니다.

루프 또는 백엔드 인스턴스에 오류 또는 예기치 않은 종료가 발생하면 작업 대기열에 업데이트 작업이 남아있게 되므로 인스턴스 재시작 시 처리될 수 있습니다. 프로덕션 시스템에서는 첫 번째 인스턴스가 실패하면 인계받을 수 있도록 감시자 역할을 하는 다른 백엔드를 대기 모드로 준비시켜 놓을 수도 있습니다.

제안 솔루션: 초당 300회로 업데이트를 지속적으로 실행²

그림 7은 대기열 분할을 도입한 최종 PoC 구현의 로드 테스트 결과를 보여줍니다. 대기열의 성능 변동을 효과적으로 억제하고 몇 시간이나 초당 300회의 업데이트 속도를 유지할 수 있음을 볼 수 있습니다. 평상시 로드 조건에서도 요청을 수신한 후 몇 초 내에 각 업데이트가 Datastore에 적용되었습니다.

이 솔루션은 다음과 같은 Applibot의 원래 요건을 모두 충족합니다.

수만 명의 플레이어를 처리할 수 있는 확장성
Datastore 트랜잭션에서 모든 업데이트가 실행되는 동안의 지속성 및 일관성
초당 300회의 업데이트를 처리할 수 있을 만큼 빠른 속도

Kaz는 로드 테스트 결과와 PoC 코드를 기반으로 Tomoaki와 다른 Applibot 엔지니어에게 솔루션을 제안했습니다. Tomoaki는 이 솔루션을 프로덕션 시스템에 통합할 계획을 세우고 있으며, 순위 정보 업데이트의 지연 시간을 1시간에서 수 초로 낮춰 사용자 경험을 대폭 높이는 효과가 있을 것으로 기대합니다.

작업 집계를 통한 순위 트리 요약

제안된 솔루션에는 여러 장점과 하나의 단점이 있습니다.

장점:

빠른 속도: FindRank 호출에 소요되는 시간이 수백 밀리초 이하입니다.
빠른 속도: SetScore에서 방금 발송한 태스크가 수 초 내에 백엔드에서 처리됩니다.
Datastore의 strong consistency 및 지속성
정확한 순위 정보
플레이어의 수에 상관없이 확장 가능

단점:

처리량에 한계가 있음(현재 구현에서는 초당 약 300회의 업데이트 가능)

이 솔루션은 작업 집계 패턴을 사용하므로 모든 업데이트를 집계하는 데 단일 스레드를 이용합니다. App Engine 인스턴스 및 Datastore 성능의 현재 CPU 사양으로 초당 300회 업데이트보다 높은 처리량을 달성하려면 추가 작업이나 복잡성이 필요합니다.

분할 트리를 통해 확장성을 높인 솔루션

더 높은 업데이트 처리량이 필요한 경우에는 순위 트리를 분할해야 할 수 있습니다. 위 시스템의 구현을 여러 개 생성하고 각 세트의 대기열은 자체 순위 트리를 업데이트하는 백엔드 모듈을 구동하도록 합니다.

일반적으로는 트리 간 조정이 필요하지 않거나 기대되지 않습니다. 가장 단순한 사례에서는 각 SetScore업데이트가 임의로 큐에 발송됩니다. 자체 Datastore 항목 그룹과 백엔드 서버가 있는 이러한 트리가 3개 있으면 예상 업데이트 처리량이 3배 증가합니다. 대신 FindRank는 점수 순위를 가져오기 위해 각 순위 트리를 쿼리한 후 각 트리의 순위를 합쳐 실제 순위를 찾아야 하므로 시간이 좀 더 오래 걸립니다. Memcache에 항목을 유지하면 FindRank의 쿼리 시간이 크게 줄어들 수 있습니다.

이 방법은 샤딩된 카운터를 사용하는 유명한 접근 방식과 유사합니다. 각 카운터는 독립적으로 증분되며 총합계는 클라이언트에서 필요할 경우에만 계산됩니다.

FindRank(865)가 3개의 트리에서 124, 183, 156의 3개 순위를 찾은 경우를 예로 들어보겠습니다. 즉, 각 트리가 865보다 높은 점수를 몇 개 보유하고 있는지를 나타냅니다. 865보다 높은 점수의 총계를 계산하면 124+183+156=463이 됩니다.

이 접근 방식이 모든 유형의 분산 알고리즘에 효과를 발휘하는 것은 아니지만 순위는 근본적으로 가환적 집계 문제이므로 많은 순위 문제를 해결할 수 있습니다.

근사치 접근 방식을 통한 솔루션 확장성 증가

애플리케이션의 우선순위가 순위의 정확성보다 확장성에 있고 어느 정도의 부정확성이나 근사치를 감수할 수 있다면 다음과 같은 확률적 접근 방식을 사용할 수 있습니다.

버킷에 대한 전역 쿼리
손실형 집계 메소드
절약형 스트리밍

이와 같은 근사치 접근 방식은 순위 정확성 감소를 어느 정도 감수하면서 순위 정보 스토리지를 최소화하기 위한 아이디어를 각자 다르게 구현한 것입니다.

버킷에 대한 전역 쿼리는 Datastore팀과 TAM인 Alex Amies가 제안한 솔루션입니다. Alex는 Datastore팀의 아이디어를 기반으로 PoC를 구현했으며 광범위한 성능 분석을 수행했습니다. 그 결과 버킷에 대한 전역 쿼리가 순위 정확도 감소를 최소화하는 확장 가능한 순위 솔루션이며 Code Jam 순위 라이브러리보다 높은 처리량이 필요한 애플리케이션에 적합하다는 사실을 증명했습니다. 자세한 설명과 테스트 결과는 부록을 참조하세요.

손실형 집계 메서드 및 절약형 스트리밍은 온라인 알고리즘 및 스트리밍 알고리즘이라고도 합니다. 이 알고리즘에서는 메모리 내 스토리지를 매우 적게 사용하여 플레이어-점수 쌍의 스트림에서 상위 순위의 확률적 예상치를 계산할 수 있습니다. 이러한 알고리즘은 초당 수천 회의 업데이트가 이루어져 낮은 지연 시간과 초고속 대역폭이 필요한 애플리케이션에 적합하며, 순위 결과의 정확도와 적용 범위는 보다 제한적입니다. 예를 들어 소셜 네트워킹 스트림에 입력된 인기 키워드 100개 순위를 보여주는 실시간 대시보드를 만들길 원하는 경우 이 알고리즘이 도움이 될 수 있습니다.

결론

순위는 늘 있어온 문제이지만, 확장성, 일관성, 빠른 속도를 갖춘 알고리즘을 원한다면 까다로운 문제이기도 합니다. 이 문서에서는 이러한 과제를 해결하고 순위 업데이트 지연 시간을 1시간에서 수 초로 줄이는 솔루션을 제공하기 위해 Google Engineering팀이 고객과 어떻게 긴밀히 공조했는지 설명했습니다. 이 과정에서 살펴본 작업 집계 및 대기열 분할과 같은 설계 패턴은 강력한 일관성을 유지하면서도 초당 수백 회의 업데이트를 필요로 하는 다른 Datastore 기반 시스템 설계에서 겪는 공통된 문제에도 적용할 수 있습니다.

참고사항

Code Jam 순위 라이브러리에는 각 항목당 몇 개의 점수를 보유할지를 지정하는 '분기 계수'라는 매개변수가 필요합니다. 기본적으로 라이브러리에서 사용하는 매개변수는 100입니다. 이 경우, 0~9999 범위의 점수는 루트 노드 하위의 100개 항목에 저장됩니다. 더 넓은 범위의 점수를 처리해야 하는 경우에는 분기 계수의 값을 높게 변경하여 항목 액세스 수를 최적화할 수 있습니다.
이 문서에서 설명하는 모든 성능 수치는 참고용으로 샘플링된 값으로, App Engine, Datastore 또는 기타 서비스의 절대적인 성능을 보장하는 것은 아닙니다.

부록: 버킷에 대한 전역 쿼리 솔루션

순위 계산 방식 섹션의 설명처럼 순위 요청이 있을 때마다 데이터베이스를 쿼리하면 비용이 많이 발생합니다. 이 방식에서는 정기적으로 모든 점수 개수를 가져오고 선택한 점수의 순위를 계산한 후 이러한 데이터 포인트를 특정 플레이어의 순위 계산에 사용합니다. 전체 점수 범위는 '버킷'으로 분할됩니다. 각 버킷은 하위 범위의 점수와 점수 범위에 있는 플레이어의 수를 특성으로 합니다. 이러한 데이터를 통해 모든 점수의 순위를 근사치까지 확인할 수 있습니다. 이러한 버킷은 순위 트리의 상위 레벨 노드와 유사하지만 이 알고리즘은 노드가 점차 세분화되는 하향 방식이 아닌 버킷을 단순히 보간하는 방식입니다.

프런트엔드의 사용자별 순위를 가져오는 작업이 백엔드의 버킷에서 이루어지는 순위 계산과 분리되어 있어 순위를 찾는 시간이 최소화됩니다. 플레이어의 순위가 요청되면 플레이어의 점수를 기반으로 적절한 버킷이 검색됩니다. 버킷에는 순위 상한 및 이 버킷 내의 플레이어 수가 포함되어 있습니다. 버킷 내 플레이어의 순위를 예측하는 데에는 버킷 내 선형 보간이 사용됩니다. 당사의 테스트에서는 전체 HTTP 왕복 시 플레이어의 순위를 가져오는 데 일관적으로 400밀리초 미만의 시간이 소요되었습니다. FindRank 메서드의 비용은 모집단 내 플레이어 수와 관계없습니다.

특정 점수의 순위 계산

각 버킷마다 개수 및 최상위 순위(즉, 이 버킷에서 가능한 최고 순위)가 기록됩니다. 버킷 내의 하한 및 상한 점수 사이의 점수에 대해 선형 보간법을 사용하여 순위를 예상합니다. 예를 들어 점수가 60점인 플레이어가 있는 경우 개수(버킷 내 플레이어/점수 수)(42)와 최상위 순위(5)를 사용하여 [50, 74] 버킷을 살펴보면 다음과 같은 수식으로 플레이어 순위를 계산할 수 있습니다.

    rank = 5  + (74 - 60)*42/(74 - 50) =  30

각 버킷의 개수와 범위 계산

크론 작업 또는 작업 대기열을 사용하는 배후에서는 모든 버킷에서 반복하여 각 버킷의 개수가 계산되고 저장됩니다. 모든 플레이어의 점수를 조사하여 순위를 예상하는 데 필요한 매개변수를 계산하므로 이를 전역 쿼리라 합니다. 아래에는 각 버킷의 [low_score, high_score] 범위 점수별로 이 작업을 수행하는 Python 샘플 코드가 나와 있습니다.

next_upper_rank = 1
for b in buckets:
  count = GetCountInRange(b.low_score, b.high_score)
  b.count = count
  b.upper_rank = next_upper_rank
  b.put()
  next_upper_rank += count

GetCountInRange() 메서드는 버킷에 해당되는 점수 범위에 있는 각 플레이어 수를 계산합니다. Datastore는 플레이어 점수의 정렬 색인을 유지하므로 이 집계는 효율적으로 계산됩니다.

특정 플레이어의 순위를 찾아야 하는 경우에는 아래와 같은 코드를 사용하면 됩니다.

b = GetBucketByScore(score)
rank = RankInBucket(b, score)
return rank + b.upper_rank - 1

GetBucketByScore(score) 메서드는 지정된 점수가 포함된 버킷을 검색합니다. RankInBucket() 메서드는 버킷 내에서 순위 예상을 계산합니다. 플레이어 순위는 버킷의 최상위 순위와 플레이어 점수가 포함된 특정 버킷 내 순위의 합계입니다. 상단 버킷의 최상위 순위는 1이고 특정 버킷 내 상위 플레이어 순위도 1이므로 결과에서 1을 빼야 합니다.

버킷은 Datastore와 Memcache 모두에 저장됩니다. 순위를 계산하려면 Memcache(또는 Memcache에 데이터가 없는 경우 Datastore)에서 버킷을 읽습니다. 이 알고리즘의 자체 구현에서 당사는 Datastore에 저장된 데이터를 캐시하기 위해 Memcache를 사용하는 Python NDB 클라이언트 라이브러리를 사용했습니다.

버킷(또는 다른 메소드)을 통해 데이터를 압축하여 나타내기 때문에 산출되는 순위가 정확하지는 않습니다. 버킷 내 순위는 선형 보간법을 이용한 근사치입니다. 회귀 공식과 같이 보다 정확도가 높은 보간 방법을 사용하면 버킷 내 근사치의 정확도가 높아질 수 있습니다.

비용

순위를 찾고 플레이어의 점수를 업데이트하는 비용은 플레이어 수와 관계없이 둘 다 0(1)입니다.

전역 쿼리 작업 비용은 O(플레이어 수) * 캐시 업데이트 빈도입니다.

집계 쿼리가 각 버킷마다 수행되므로 백엔드 작업의 버킷 데이터를 계산하는 비용은 버킷 수와도 관련이 있습니다. 집계 쿼리는 키 전용 쿼리를 사용하도록 최적화되어 있지만 그래도 전체 키 목록을 검색해야 합니다.

장점

이 메소드는 점수의 순위를 찾는 것은 물론 플레이어 점수를 업데이트하는 작업을 모두 신속하게 수행합니다. 배후 작업을 기반으로 결과가 산출되지만 플레이어의 점수가 변경되면 순위가 적절한 방향으로 변경사항을 즉시 보여줍니다. 버킷 내에 사용되는 보간법 때문입니다.

예약된 작업을 통해 버킷의 최상위 순위 계산이 배후에서 수행되므로 버킷 데이터를 계속 동기화하지 않아도 플레이어의 점수를 업데이트할 수 있습니다. 따라서 이 접근 방식에서는 플레이어 점수 업데이트 처리량에 제한이 없습니다.

단점

모든 플레이어의 점수를 계산하고, 전 세계 순위를 계산하고, 버킷을 업데이트하는 데 소요되는 시간을 고려해야 합니다. 당사의 테스트에 따르면 사용 인구의 플레이어 수가 1,000만 명인 경우 App Engine상의 테스트 시스템에서 소요되는 시간은 8분 34초였습니다. 각 플레이어의 순위를 계산하는 데 소요되는 시간보다는 빠르지만 각 버킷 내 점수의 근사치라는 점은 감수해야 할 부분입니다. 반면 트리 알고리즘은 '버킷 범위'(트리의 상단 노드)를 매초마다 증분식으로 계산하지만 구현하기가 매우 복잡하고 처리량이 제한됩니다.

모든 경우에서 FindRank에 소요되는 시간은 Memcache의 데이터(버킷 또는 트리 노드)를 검색하는 속도와도 연관됩니다. 데이터가 Memcache에서 삭제되면 Datastore에서 다시 가져온 후 후속 FindRank 요청에 사용할 수 있도록 다시 캐시해야 합니다.

정확성

버킷 메소드의 정확도는 버킷 수, 플레이어 순위, 점수 분포와 상관이 있습니다. 그림 9에는 버킷의 수를 다르게 하여 순위 근사치의 정확도를 조사한 연구 결과가 나와 있습니다.

테스트는 [0-9999] 범위에 점수가 균등하게 분포된 플레이어 10,000명을 대상으로 진행되었습니다. 버킷이 단 5개인 경우 상대 오차는 약 1%에 불과합니다.

상위 점수만 대상으로 할 때는 대수 법칙이 적용되지 않으므로 상위권 플레이어에 대한 정확도가 낮아집니다. 대체로 1~2천 명의 최상위 점수 플레이어 순위를 유지하려면 보다 정확한 알고리즘을 사용하는 것이 좋습니다. 추적할 플레이어 수가 적고 업데이트의 집계율 역시 함께 낮아지기 때문에 문제 가능성이 훨씬 줄어듭니다.

균일하게 분포된 임의의 숫자를 사용하고 누적 분포 함수가 선형인 위의 테스트에서는 버킷 내 선형 보간법 사용이 선호되지만 점수가 치밀하게 분포된 경우에는 여러 버킷 내 보간법도 효과가 있습니다. 그림 10에는 대략적인 점수 정규 분포에 따른 예상 순위 및 실제 순위를 비교한 결과가 나와 있습니다.

이 실험에서는 플레이어 100명을 대상으로 소량 데이터 세트의 정확도를 테스트했습니다. 0부터 100 사이의 정규 점수 분포를 대략적으로 나타내는 4개의 임의 숫자 평균을 구해 각 점수를 생성했습니다. 예상 순위는 10개 버킷을 기준으로 선형 보간법과 함께 전역 쿼리 메소드를 사용하여 계산합니다. 소량의 데이터 세트와 균일하지 않은 분포에서도 정확도가 매우 우수하다는 사실을 알 수 있습니다.