120만 개의 동시 접속 상황에서 보물찾기 엔진이 계속 충돌했던 이유

우리가 실제로 해결하려 했던 문제는 보물찾기를 어떻게 더 재미있게 만들 것인가가 아니라, 매주 화요일 오후 3시 17분 정각에 120만 명의 플레이어가 Redis 클러스터(cluster)를 몰아칠 때 어떻게 리더보드(leaderboard)가 힙(heap)을 폭발시키지 않게 유지할 것인가였습니다. 마케팅 팀은 이를 '피크 참여(peak engagement)'라고 불렀지만, 저는 이를 '메모리 눈사태(memory avalanche)'라고 불렀습니다. 우리는 32GB RAM 인스턴스에서 Veltrix의 오픈 소스 보물찾기 엔진을 실행하고 있었는데, 스파이크(spike)가 발생할 때마다 노드는 스왑(swap)으로 인해 죽어가는 좀비 상태가 되었습니다. 리더보드 티어(tier)는 Redis가 연산당 O(log N)이라고 광고하는 인메모리 정렬된 집합(sorted set)을 사용했지만, N=120만일 때 상수 계수(constant factor)가 너무 높아 Lua 스크립트가 점수를 업데이트하는 시간보다 컨텍스트 스위칭(context-switching)에 더 많은 시간을 소비했습니다. 프로세스당 400MB의 RESident 메모리에 도달했고, Go 가비지 컬렉터(garbage collector)가 420ms 동안 일시 중지되자 TCP 백로그(backlog)가 넘쳐흘러 37,000개의 ZADD 요청이 유실되었습니다. CEO가 '캐시(cache)'라는 단어에 주목한 것은 그때가 처음이었습니다.

우리가 처음 시도했던 것 (그리고 실패한 이유)

우리는 당연한 것부터 시작했습니다. Redis 인스턴스를 128GB로 업그레이드하고, 리더보드를 별도의 노드로 이동시킨 뒤, 앞에 읽기 복제본(read replica)을 배치하는 것이었습니다. 운영 문서에서는 이를 수평 확장(horizontal scaling)이라고 불렀습니다. 하지만 그들이 언급하지 않은 점은 Redis 클러스터(cluster)가 정렬된 집합(sorted set)을 슬롯(slot)에 걸쳐 분할한다는 것이었습니다. 따라서 단일 플레이어의 점수 업데이트가 세 개의 서로 다른 프라이머리(primaries)로 팬아웃(fan out)될 수 있었습니다. 리더보드 상위권에 근접한 플레이어들이 점수를 업데이트할 때, 클러스터는 네트워크 카드를 병목 현상(bottleneck)으로 만드는 급격한 크로스 슬롯(cross-slot) 트래픽 급증을 경험했습니다. 실제 게임 업데이트는 3Gbps였지만, 클러스터 내부 트래픽은 8Gbps에 달했습니다. Redis 클러스터 버스 프로토콜(bus protocol)은 가십 메시지(gossip messages)를 드롭하기 시작했고, 클러스터는 11초 동안 슬롯 소유권(slot ownership)에 대한 뷰(view)를 잃었습니다. 그 11초는 24개의 노드가 새로운 선거 주기(election cycle)를 시작하기에 충분한 시간이었고, 슬롯 맵(slot map)이 다시 수렴(reconverge)되는 동안 리더보드는 얼어붙었습니다.

아키텍처 결정

우리는 Redis의 sorted set을 완전히 제거하고 Go로 구축된 2계층 리더보드(two-tiered leaderboard)를 만들었습니다. 첫 번째 계층은 쓰기 통과(write-through) 방식의 샤딩된 맵(sharded map)입니다. 64개의 샤드(shard)로 구성되며, 각 샤드는 플레이어 ID를 키로 하는 인메모리 라딕스 트리(radix tree)입니다. 각 샤드는 하나의 고루틴(goroutine)으로 동작하며, 쓰기 작업을 4 KB 버퍼에 배치(batch)한 뒤 샤드 ID와 날짜별로 파티셔닝된 단일 PostgreSQL 테이블로 비동기적으로 플러시(flush)합니다. 우리가 PostgreSQL을 선택한 이유는 그것이 빨라서가 아니라—절대 그렇지 않습니다—실제 트랜잭션 로그(transaction log)를 제공하기 때문입니다. 프로세스가 충돌하더라도 WAL(Write-Ahead Log) 덕분에 마지막으로 커밋된 배치를 100ms 이내에 복구할 수 있음이 보장됩니다. 두 번째 계층은 지난 몇 시간 동안의 파티션에 대해 윈도우 SQL 쿼리(windowed SQL query)를 실행하는 워커(worker)에 의해 30초마다 재구축되는 구체화된 뷰(materialized view)입니다. 우리는 구체화된 뷰에서 읽기 작업을 처리하므로, 트래픽 급증(spike) 시에도 리더보드 쿼리가 인메모리 트리에 직접 닿는 일이 없습니다.

우리는 한 가지 트릭을 더 추가했습니다. 라딕스 트리 앞에 작은 LRU 캐시(LRU cache)를 배치한 것입니다. 캐시 엔트리는 5분의 TTL(Time To Live)을 가지지만, 점수 자체에 내장된 버전 벡터(version vector)를 사용합니다. 플레이어의 점수가 어떤 양으로든 변경되면, 버전을 증가시키고 새로운 점수를 커밋하는 동일한 PostgreSQL 트랜잭션 내에서 원자적(atomically)으로 캐시 엔트리를 무효화합니다. 캐시 히트율(cache hit rate)은 72%에서 78% 사이를 유지하지만, 캐시 미스(miss)가 발생하더라도 읽기 경로는 전체 집합을 스캔하는 대신 단일 라딕스 조회와 단일 해시 조회를 수행합니다.

변경 후의 수치들

변경 이후 99번째 백분위수(99th percentile) 리더보드 지연 시간(latency)은 420ms에서 3ms로 감소했습니다. 샤드당 피크 메모리 사용량(peak memory footprint)은 200MB 미만으로 유지되었으며, Go 프로세스의 GC(Garbage Collection) 일시 중단(pause) 시간은 140만 개의 동시 접속 상황에서도 평균 1.2ms를 기록했습니다. 쓰기 처리량(write throughput)은 초당 2.1k ops에서 초당 220k ops로 증가했으며, 모든 업데이트가 단일 PostgreSQL 연결 내에서 유지되었기 때문에 샤드 간 트래픽(cross-shard traffic)은 사라졌습니다. 화요일 트래픽 급증 동안 PostgreSQL CPU 사용률은 피크 시 35%를 기록했으며, 이는 클러스터를 다시 건드리지 않고도 향후 3배의 성장을 수용할 수 있는 여유 공간(headroom)을 제공했습니다.

내가 다르게 했을 일

네트워크 장애(network hiccups)가 발생하는 동안 Redis Cluster 슬롯 맵(slot map)이 일관성을 유지할 것이라고 신뢰하지 않았을 것입니다. 만약 다시 해야 한다면, PostgreSQL 워커(worker)를 pg_logical을 통해 쓰기 로그(write-ahead log)를 직접 소비하고 구체화된 뷰(materialized view)를 점진적으로 구축하는 스트리밍 작업(streaming job)으로 교체했을 것입니다. 그렇게 하면 뷰가 샤딩된 인메모리 트리(sharded in-memory trees)보다 몇 백 밀리초 이상 뒤처지는 일이 발생하지 않을 것이며, 30초의 데이터 정체(staleness) 구간을 피할 수 있었을 것입니다.

또한, 조회(lookup)당 포인터 역참조(pointer dereference) 횟수를 기록하는 Prometheus 히스토그램(histogram)을 사용하여 라딕스 트리(radix tree)를 계측(instrument)했을 것입니다. 해당 지표는 트리가 충분히 조밀하여 6단계 이상의 탐색을 거의 수행하지 않는다는 것을 알려주었지만, 히스토그램은 핫 샤드(hot shard)가 예측 불가능하게 커지기 시작할 때 이를 명확하게 보여주었을 것입니다. 그러한 가시성(visibility)이 없었다면, 몇 주간의 변동(churn) 이후 12단계의 탐색을 수행하게 된 4%의 쿼리를 놓쳤을 것입니다.