분산 데이터베이스를 브라우저에 넣어 봤습니다 – 그리고 게임으로 만들었죠!

2023년 7월 11일

TigerBeetle은 미션 크리티컬한 안전성을 위해 설계된 분산 금융 트랜잭션 데이터베이스입니다. 이렇게 중요한 무언가를 어떻게 테스트할까요? 글로 설명할 수도 있고(실제로 할 겁니다), 그런데 왜 보여주지 않을까요?

TLDR: 이제 TigerBeetle을… WebAssembly로 컴파일해서… 브라우저에서 실행할 수 있습니다! 완벽한 네트워크 조건에서 시작해, 그다음엔 그리 완벽하지 않은 Jepsen 스타일의 조건으로, 마지막엔 전례 없는(우주적) 수준의 디스크 손상까지.

이것은 Viewstamped Replication과 합의 기반 스토리지를 위한 프로토콜 인지 복구(Protocol-Aware Recovery)에 대한 우리의 해석입니다. 디버깅 속도를 높이기 위해 시간을 가속하고 시나리오를 재생할 수 있는 결정론적 시뮬레이터에서 돌아가며, Zig의 툴체인 덕분에 WebAssembly로 컴파일되었습니다. 그리고 우리 모두 마음속에 있는 ‘아이’를 위한 그래픽 게임 프런트엔드까지 얹었습니다.

A Deterministic Simulator Called The VOPR

Viewstamped Operation Replicator(VOPR)는 영화 WarGames에 나오는 WOPR 시뮬레이터에서 이름을 따왔고, 퍼징에 대한 우리의 애정, Dropbox의 Nucleus 테스트, FoundationDB의 결정론적 시뮬레이션 테스트에서 영감을 받았습니다.

VOPR의 출발점은 이렇습니다. 복잡한 분산 시스템의 버그는 찾아내는 데 시간이 걸리고, 한번 찾고 나면 다시는 재현되지 않을 수도 있습니다. 결정론적 시뮬레이션 테스트는 퍼저(fuzzer)에 시뮬레이션된 시간 팽창(time dilation)과 재현 가능한 실패를 결합함으로써 이 문제를 해결합니다.

VOPR 시뮬레이션 3.3초는 현실 세계 테스트 시간 39분에 해당합니다. 1시간이면 한 달, 하루면 2년. 그리고 우리는 이런 VOPR 시뮬레이터 10개를 24/7로 돌립니다.

VOPR은 개발자 머신의 단일 프로세스 안에서 TigerBeetle의 여러 레플리카(replica) 클러스터와 클라이언트가 TigerBeetle의 Viewstamped Replication 합의 프로토콜(VSR)을 통해 상호작용하도록 퍼징합니다. 모든 I/O는 모킹됩니다. 다양한 네트워크 장애와 지연을 시뮬레이션하는 네트워크 시뮬레이터와, 다양한 스토리지 장애와 지연을 시뮬레이션하는 인메모리 스토리지 시뮬레이터가 있습니다.

VOPR은 장애 주입의 강도를 제어할 수 있고, 적용되는 장애의 종류를 선택할 수 있으며, 선형화 가능성(linearizability)을 검증할 수 있습니다. 그리고 다양한 시나리오를 가진 이 시뮬레이터가 바로 지금 여러분이 브라우저에서 보고 있는 것입니다!

Level 1: City Breeze

City Breeze에서는 완벽한 환경을 시뮬레이션합니다. 네트워크 파티션 없음. 패킷 유실이나 재전송 없음. 크래시나 디스크 손상 없음. 그리고 당연히 네트워크/디스크 I/O 지연도 낮습니다.

클러스터가 기동되면, 화면 상단의 클라이언트들이 _프라이머리(primary)_에 새 메시지를 보냅니다. 프라이머리는 클라이언트에게 응답하기 전에 이 메시지들을 내구성을 위해 백업(backup) 레플리카로 복제합니다.

각 레플리카에 메시지가 복제되면서 레플리카의 op number(각 메시지의 일련 식별자)가 증가하고, 복제된 메시지가 비즈니스 로직을 통해 실행되면 _commit number_가 증가하는 것을 볼 수 있을 겁니다.

이것이 가장 최적(그리고 가장 직관적)인 형태의 복제입니다. 적어도 안전을 위해 엄격 직렬화 가능성(strict serializability)으로 트랜잭션을 커밋하기 전에 데이터가 두 대 이상의 머신에 있어야 한다고 요구한다면 말이죠.

이처럼 쉬운 시나리오에서는 뷰 변경(view change)(클러스터가 새로운 프라이머리 레플리카에 합의해야 하는 상황)을 보기 어려울 겁니다. 즉, 레플리카 0이 프라이머리로 시작해 대부분의 시간 동안 프라이머리로 남을 가능성이 큽니다.

다시 말하지만, 이건 실제 TigerBeetle 코드이며, ‘Beetle’ 클러스터를… 브라우저에서 실행하는 것입니다!

Level 2: Red Desert

두 번째 레벨부터는 진짜입니다. Jepsen급 네메시스(nemeses)를 말하는 거죠.

스토리지/네트워크의 높은 지연, 프로세스 크래시, 불안정한 네트워크를 도입하지만 디스크 손상은 없습니다.

프라이머리가 크래시하거나 파티션되면 _뷰 변경_이 발생하고, 새 프라이머리가 확립될 때까지 레플리카들 사이에서 VSR 특유의 ‘라운드 로빈’ 방식으로 새 프라이머리가 순환하는 것을 보게 될 겁니다. 이는 프라이머리를 무작위로 선출하지만, 이후 ‘리더 간 경쟁(dueling leaders)’의 위험(또는 이를 완화하기 위한 증가한 지연)을 겪는 Raft와 대조적입니다.

이 더 험난한 환경에서는 메시지 복제에 더 오래 걸리므로 커밋된 op number가 더 천천히 증가할 겁니다. 하지만 괜찮습니다. 이것보다 더 나쁠 수는… 없으니까요?

물론 아직 스토리지 장애를 주입하진 않지만, Raft나 Paxos 같은 프로토콜의 형식적 증명은 디스크가 완벽하다고 가정하고, 정합성을 위해 그 가정에 의존하잖아요? 어차피 데이터베이스를 RAID 위에서 돌리면 되지 않나요? 그렇죠?

만약 여러분의 분산 데이터베이스가 2018년 이전에 설계되었다면, 할 수 있는 게 많지 않았을 겁니다. 관련 연구가 존재하지 않았으니까요.

욕조에서 안대를 한 저 교수는 대체 누구죠?

Level 3: Radioactive

SimTigerBeetle의 마지막 레벨은 재앙적 실패를 시뮬레이션합니다. 네트워크/프로세스 장애뿐 아니라, 각 레플리카마다 스토리지 읽기 경로에서 최대 8%의 손상 확률, 쓰기 경로에서 9%의 손상 확률까지 주입합니다! 다시 말해, 이는 Jepsen(그리고 일반적으로 대부분의 데이터베이스)이 아직 완전히 테스트하지 못하는(또는 복구하지 못하는) 영역입니다.

그리고 이건 천문학적인 수준의 실패입니다. 디스크가 8%의 데이터를 손상시키고 있다면 즉시 버리겠죠. 하지만 TigerBeetle은 실제로 이런 시나리오를 처리하고 복구합니다.

The Matrix

VOPR 덕분에 우리는 시뮬레이션 자체에서 시간의 흐름을 문자 그대로 가속함으로써, 짧은 시간에 엄청난 상태 공간(state space)에서 TigerBeetle을 탐색하고 테스트할 수 있었습니다. 마치 매트릭스처럼요.

VOPR은 TigerBeetle을 테스트하는 여러 방법 중 하나일 뿐입니다. 하지만 이렇게 짧은 시간에 우리 시스템에 대한 확신을 쌓을 수 있었던 가장 큰 이유이기도 합니다.

Evolution

우리는 2022년 7월에 이 프로젝트를 시작했습니다. Joran이 일러스트레이터 Joy Machs와 게임 개발자 Fabio Arnold에게 아이디어의 와이어프레임을 제시했죠. TigerBeetle이 어떻게 동작하는지 설명할 수 있는 인터랙티브 데모를 원했습니다. 아이가 봐도 이해하고, 신나할 수 있을 만큼 단순한 것으로요.

이미지 13: Joy가 그린 레플리카 간 통신의 초기 스케치.

Joy가 그린 레플리카 간 통신의 초기 스케치.

Zig는 WebAssembly로 쉽게 컴파일되지만, WebAssembly는 32비트 아키텍처이고 TigerBeetle은 64비트 아키텍처만 지원합니다. 시뮬레이터의 메모리 사용량을 2GiB(클러스터 전체!) 아래로 낮추는 것이 Fabio가 브라우저에서 돌아가게 만들기 위해 풀어야 했던 과제 중 하나였습니다.

그래픽은 WebGL로 렌더링되며, Fabio가 만든 nanovg의 Zig 포트를 사용합니다.

이미지 14: Joy가 그린 레벨의 초기 스케치.

Joy가 그린 레벨의 초기 스케치.

Joy Machs는 2021년부터 Zig 커뮤니티를 위해 일러스트를 해왔는데, 시작은 마스코트 Suzie였습니다. 그리고 같은 해부터 TigerBeetle과 함께 일하며, 여러분이 보고 있는 모든 아트워크로 우리의 이야기를 전해왔습니다.

Here’s to the Pioneers

TigerBeetle은 Martin Thompson의 LMAX, UW-Madison의 Remzi & Andrea Arpaci-Dusseau(그리고 Ramnatthan Alagappan, Aishwarya Ganesan)의 스토리지 장애 연구, Brian M. Oki/Barbara Liskov/James Cowling의 Viewstamped Replication, 그리고 그 밖의 많은 작업에서 영감을 받았습니다(TigerBeetle 뒤에 있는 전체 논문 모음도 확인해 보세요).

마지막으로, 그동안 우리에게 영감을 주고 응원해 준 여러분 모두에게—이건 여러분의 게임입니다.