분산 시스템 버그가 왜 재현하기 어렵고, 단일 스레드·통제된 난수/시간·결함 주입을 통해 결정론적으로 시뮬레이션하며 속성 기반 테스트를 하는 기법인 DST가 무엇을 가능하게 하는지와 그 한계를 정리한다.
URL: https://notes.eatonphil.com/2024-08-20-deterministic-simulation-testing.html
분산 시스템의 버그는 찾기 어렵다. 시스템들이 혼돈스럽게 상호작용하기 때문이다. 그리고 설령 버그를 찾아도, 그 버그를 재현하는 건 쉬울 수도 있지만 불가능에 가까울 때도 많다. 이는 이상적인 테스트 환경—순수 함수를 속성 기반 테스트(property testing)하는 것—과는 정반대에 가깝다.
하지만 만약 테스트 중에 분산 시스템의 혼돈스러운 측면을 분리할 수 있다면 어떨까? 여러 시스템이 서로 통신하되 _단일 스레드_에서 실행되게 하고, 각 시스템의 모든 랜덤성을 제어할 수 있다면? 그리고 제어된 랜덤성을 가진 이 단일 스레드 버전의 분산 시스템을 속성 기반 테스트하되, 현실 세계에서 볼 수 있는 결함(불행 경로 동작—에러와 지연 같은 것—을 멋지게 부르는 말)을 계속 주입한다면?
말도 안 되는 소리 같지만, 실제로 사람들은 이런 일을 한다. 이를 결정론적 시뮬레이션 테스트(Deterministic Simulation Testing, DST)라고 부른다. 그리고 FoundationDB, Antithesis, TigerBeetle, Polar Signals, WarpStream 같은 스타트업뿐 아니라 Tyler Neely, Pekka Enberg 같은 사람들이 이 기법을 이야기하고 활용하면서 점점 더 대중화됐다.
내가 있는 분야에서는 DST가 워낙 자주 언급되다 보니, 너무 마법 같고 약간 과대광고처럼 들릴 위험이 있다고 걱정된다. 장점뿐 아니라 한계까지 더 잘 이해해볼 가치가 있다.
이 글의 한 버전을 리뷰해준 Alex Miller와 Will Wilson에게 감사한다.
비즈니스 로직에서 비결정성(non-determinism)의 큰 원천 중 하나는 난수 사용이다—직접 작성한 코드에서든, 전이 의존성(transitive dependencies)에서든, 언어 런타임에서든, 운영체제에서든.
중요하게도, DST는 랜덤성을 쓸 수 없다는 뜻이 아니다! DST는 단지 프로그램 전체의 랜덤성이 전역 시드(global seed)에 의해 결정되며, 시뮬레이터가 그 시드를 제어한다고 가정할 뿐이다. 시뮬레이터 실행(run)마다 시드는 달라질 수 있다.
어떤 랜덤 시드로 시뮬레이션을 돌리다가 나쁜 상태(bad state)를 관찰하면, 사용자가 같은 시드를 다시 입력하게 할 수 있다. 그러면 그 나쁜 상태로 이어진 전체 프로그램 실행을 그대로 재현할 수 있다. 사용자는 그 실행을 손쉽게 디버깅할 수 있게 된다.
비결정성의 또 다른 큰 원천은 시간(time)에 의존하는 것이다. 랜덤성과 마찬가지로, DST는 시간이 필요 없다는 뜻이 아니다. DST는 시뮬레이션 중에 시계를 제어할 수 있어야 한다는 뜻이다.
랜덤성이나 시간을 “제어한다”는 것은 기본적으로 의존성 주입(dependency injection)을 지원한다는 의미다. 혹은 의존성 주입의 옛 방식인 _의존성을 명시적 파라미터로 전달하기_를 의미한다. 전역 시계나 전역 시드를 참조하는 대신, 누군가로부터 시계나 시드를 받아야 한다.
예를 들어 애플리케이션의 동작을 언어의 main() 엔트리포인트와 실제 애플리케이션 start() 엔트리포인트로 분리할 수 있다.
text# app.pseudocode def start(clock, seed): # 시간에 의존하거나 랜덤 동작을 할 수도 있는 많은 비즈니스 로직 def main: clock = time.clock() seed = time.now() app.start(clock, seed)
애플리케이션 엔트리포인트는, 실제 시계나 실제 난수 시드를 시뮬레이터가 제어하는 것으로 교체할 수 있어야 하는 지점이다.
text# sim.pseudocode import "app.pseudocode" def main: sim_clock = make_sim_clock() sim_seed = os.env.DST_SEED or time.now() try: app.start(sim_clock, sim_seed) catch(e): print("Bad execution at seed: %s", sim_seed) throw e
다른 예도 보자.
성공할 때까지 함수를 계속 호출하되, 백오프(backoff)를 두는 헬퍼 메서드가 있다고 하자.
text# retry.pseudocode class Backoff: def init: this.rnd = rnd.new(seed = time.now()) this.tries = 0 async def retry_backoff(f): while this.tries < 3: if f(): return await time.sleep(this.rnd.gen()) this.tries++
여기 비결정성의 원천은 하나뿐인데, 시드를 생성하는 부분이다. 시드를 파라미터로 받을 수도 있겠지만, time.sleep()을 호출하고 있고 DST에서는 시간을 제어하니 time 자체를 파라미터화하면 된다.
text# retry.psuedocode class Backoff: def init(this, time): this.time = time this.rnd = rnd.new(seed = this.time.now()) this.tries = 0 async def retry_backoff(this, f): while this.tries < 3: if f(): return await this.time.sleep(this.rnd.gen()) this.tries++
이제 이를 테스트하는 작은 시뮬레이터를 쓸 수 있다.
text# sim.psuedocode import "retry.pseudocode" sim_time = { now: 0 sleep: (ms) => { await future.wait(ms) } tick: (ms) => now += ms } backoff = Backoff(sim_time) while true: failures = 0 f = () => { if rnd.rand() > 0.5: failures++ return false return true } try: while sim_time.now < 60min: promise = backoff.retry_backoff(f) sim_time.tick(1ms) if promise.read(): break assert_expect_failure_and_expected_time_elapse(sim_time, failures) catch(e): print("Found logical error with seed: %d", seed) throw e
이는 DST의 핵심 측면 몇 가지를 보여준다.
첫째, 시뮬레이터 자체가 랜덤성에 의존한다. 하지만 사용자가 시드를 제공하게 해서 버그를 발견한 시뮬레이션을 재생(replay)할 수 있다. 시뮬레이터의 통제된 랜덤성 덕분에 속성 기반 테스트를 할 수 있다.
둘째, 시뮬레이션 워크로드는 사용자가 작성해야 한다. Antithesis처럼 DST 환경을 제공하는 플랫폼이 있더라도, 애플리케이션을 실제로 “운동(exercise)”시키는 건 당신의 몫이다.
이제 더 복잡한 사례로 가보자.
여러 스레드의 결정성은 운영체제/에뮬레이터/하이퍼바이저 계층에서만 제어할 수 있다. 현실적으로는 Antithesis나 Hermit 같은 서드파티 시스템(참고로 Hermit은 활발히 개발되지 않으며 내 흥미로운 프로그램에서는 아직 동작한 적이 없다) 혹은 rr 같은 것이 필요하다.
이 시스템들은 멀티스레드 코드를 투명하게 단일 스레드 코드로 변환한다. 하지만 Hermit과 rr은 결함 주입(fault injection) 능력이 제한적이기도 하다(결정론적 실행뿐 아니라 결함 주입도 목표이기 때문이다). 그리고 mac에서는 실행할 수 없고, ARM에서는 실행할 수 없다고도 한다.
하지만 우리는 새 운영체제나 에뮬레이터, 하이퍼바이저를 만들지 않고, 그리고 서드파티 시스템 없이도 시뮬레이터를 만들고 싶다. 그러려면 단일 스레드로 “접힐 수 있는(collapse)” 코드만 작성해야 한다. 특히, 블로킹 IO를 사용하면 단일 스레드 시뮬레이터에서 발견할 수 없는 동시성 버그의 한 부류가 생기므로, 비동기 IO로 제한해야 한다.
단일 스레드와 비동기 IO. 이것만으로도 이미 두 가지 큰 제약이다.
Go 같은 언어는 투명한 멀티스레딩과 블로킹 IO를 중심으로 설계됐다. Polar Signals는 애플리케이션을 WASM으로 컴파일해 단일 스레드에서 돌리는 방식으로 DST를 해결했다. 하지만 그것만으로는 충분하지 않았다. 단일 스레드에서도 Go 런타임은 고루틴(goroutine)을 의도적으로 랜덤하게 스케줄링한다. 그래서 Polar Signals는 환경 변수를 통해 이 랜덤성을 제어하기 위해 Go 런타임을 포크했다. 꽤 미친 일이다. Resonate는 다른 접근을 택했는데 이것도 번거로워 보인다. 여기서 설명하려고 하진 않겠다. DST를 하고 싶다면 Go는 어려운 선택처럼 보인다.
Go와 마찬가지로 Rust도 기본 내장 async IO가 없다. 가장 성숙한 async IO 라이브러리는 tokio다. tokio 팀은 모든 비결정성 원천을 제거한 tokio 호환 시뮬레이터를 제공하려 했지만, 내가 보기엔 끝내 완전히 성공하지 못했다. 그 저장소는 이제 “매우 실험적”이라고 하는 tokio-rs 프로젝트 turmoil로 대체됐다. turmoil은 결정론적 실행과 네트워크 결함 주입을 제공한다. (하지만 디스크 결함 주입은 제공하지 않는다. 이건 뒤에서 더 이야기하겠다.) 결정론을 위해 설계되지 않은 IO 라이브러리에 결정론적 실행을 제공하는 것이 어렵다는 건 놀랍지 않다. tokio는 많은 전이 의존성을 가진 큰 프로젝트다. 비결정성을 찾기 위해 모두 샅샅이 훑어야 한다.
반면 Pekka는 시뮬레이션 테스트를 염두에 두고 설계된 더 단순한 Rust async IO 라이브러리를 어떻게 만들 수 있을지 이미 보여줬다. 이는 TigerBeetle의 설계를 모델로 했고, King과 내가 약 2년 전에 글로 정리한 바 있다.
이제 버그가 있는 IO 프로그램을 하나 그려보고, DST를 어떻게 적용할 수 있는지 보자.
text# readfile.pseudocode def read_file(io, name, into_buffer): f = await io.open(name) read_buffer = [4096]u8{} while true: err, n_read = await f.read(&read_buffer) if err == io.EOF: into_buffer.copy_maybe_allocate(read_buffer[0:sizeof(read_buffer)]) return if err: throw err into_buffer.copy_maybe_allocate(read_buffer[0:sizeof(read_buffer)])
시뮬레이터에서는 IO 시스템을 목(mock)으로 제공하고, 다양한 에러를 랜덤하게 주입하면서 사전/사후 조건을 검증할 것이다.
text# sim.psuedocode import "readfile.pseudocode" seed = if os.env.DST_SEED ? int(os.env.DST_SEED) : time.now() rnd = rnd.new(seed) while true: sim_disk_data = rnd.rand_bytes(10MB) sim_fd = { pos: 0 EOF: Error("eof") read: (fd, buf) => { partial_read = rnd.rand_in_range_inclusive(0, sizeof(buf)) memcpy(sim_disk_data, buf, fd.pos, partial_read) fd.pos += partial_read if fd.pos == sizeof(sim_disk_data): return io.EOF, partial_read return partial_read } } sim_io = { open: (filename) => sim_fd } out_buf = Vector<u8>.new() try: read_file(sim_io, "somefile", out_buf) assert_bytes_equal(out_buf.data, sim_disk_data) catch (e): print("Found logical error with seed: %d", seed) throw e
이 시뮬레이터로 우리는 결국 부분 읽기(partial read) 버그를 잡았을 것이다! 원래 프로그램에서 다음과 같이 썼던 부분:
textinto_buffer.copy_maybe_allocate(read_buffer[0:sizeof(read_buffer)])
은 사실 이렇게 써야 했다:
textinto_buffer.copy_maybe_allocate(read_buffer[0:n_read])
좋다! 더 복잡하게 가보자.
서두에서 이미 말했듯이, 분산 시스템을 DST로 테스트하는 요지는 시스템의 모든 노드를 같은 프로세스 안에서 실행시키는 것이다. 애플리케이션 + Kafka + Postgres + Redis 같은 조합을 테스트하려 한다면 거의 불가능하겠지만, Raft 라이브러리를 내장해 고가용성을 제공하는 애플리케이션처럼 “자급자족(self-contained)” 분산 시스템이라면, 여러 노드를 같은 프로세스에 띄울 수 있다!
이런 시스템에서 시뮬레이터는 대략 이렇게 생길 수 있다.
text# sim.pseudocode import "distsys-node.pseudocode" seed = if os.env.DST_SEED ? int(os.env.DST_SEED) : time.now() rnd = rnd.new(seed) while true: sim_fd = { send(fd, buf) => { # 랜덤 실패 주입. if rnd.rand() > .5: throw Error('bad write') # 랜덤 지연 주입. if rnd.rand() > .5: await time.sleep(rnd.rand()) n_written = assert_ok(os.fd.write(buf)) return n_written }, recv(fd, buf) => { # 랜덤 실패 주입. if rnd.rand() > .5: throw Error('bad read') # 랜덤 지연 주입. if rnd.rand() > .5: await time.sleep(rnd.rand()) return os.fd.read(buf) } } sim_io = { open: (filename) => { # 랜덤 실패 주입. if rnd.rand() > .5: throw Error('bad open') # 랜덤 지연 주입. if rnd.rand() > .5: await time.sleep(rnd.rand()) return sim_fd } } all_ports = [6000, 6001, 6002] nodes = [ await distsys-node.start(sim_io, all_ports[0], all_ports), await distsys-node.start(sim_io, all_ports[1], all_ports), await distsys-node.start(sim_io, all_ports[2], all_ports), ] history = [] try: key = rnd.rand_bytes(10) value = rnd.rand_bytes(10) nodes[rnd.rand_in_range_inclusive(0, len(nodes)].insert(key, value) history.add((key, value)) assert_valid_history(nodes, history) # 가끔 프로세스를 크래시시킴 if rnd.rand() > 0.75: node = nodes[rnd.rand_in_range_inclusive(0, 3)] node.restart() catch (e): print("Found logical error with seed: %d", seed) throw e
여기서는 특정 분산 시스템에 대한 구체적인 테스트 전략이 아니라, 더 큰 요점을 보여주기 위해 엄청 대충(손을 흔들며) 설명했다. 중요한 점은 이 세 노드가 같은 프로세스에서, 서로 다른 포트로 실행된다는 것이다.
우리는 디스크 IO를 제어한다. 네트워크 IO를 제어한다. 시간이 흐르는 방식도 제어한다. 그리고 디스크/네트워크/프로세스 결함을 주입하면서, 3노드 시스템에 결정론적인 시뮬레이션 워크로드를 실행한다.
또한 지속적으로 잘못된 상태(invalid state)를 검사한다. 잘못된 상태가 나오면, 사용자가 그 상태를 쉽게 재현할 수 있음을 확신할 수 있다.
어느 정도 오차를 감안하면, 대부분의 CPU 명령과 CPU 동작은 결정론적이라고 여겨진다. 하지만 확실히 그렇지 않은 특정 CPU 명령들이 있다. 불행히도 여기에는 시스템 콜이 포함될 수도 있다. malloc도 포함될 수 있다. 믿을 게 별로 없다.
Antithesis를 일단 제외하면, DST를 하는 사람들은 이런 작은 비결정성 조각들은 크게 걱정하지 않는 듯하다. 그럼에도 DST가 여전히 가치 있다는 데에는 대체로 동의한다. 직관은 이렇다: 비결정성을 조금이라도 더 제거할수록, 버그를 발견했을 때 재현하기가 그만큼 쉬워진다.
다르게 말하면: DST 실무자들 사이에서도 결정론은 스펙트럼이다.
위의 의사코드들에서 이미 느꼈겠지만, DST는 만병통치약이 아니다.
첫째, 코드의 비결정적 부분을 교체해야 하므로, 실제로는 코드 전체를 테스트하고 있는 게 아니다. 결정론적 커널(deterministic kernel)을 크게 유지하는 것이 권장되지만, 비결정적 엣지는 항상 존재한다.
Antithesis처럼 전체를 결정론적으로 만드는 머신을 제공하는 시스템이 없다면, 프로그램 전체를 테스트할 수 없다.
또 Antithesis가 있더라도, 시스템과 외부 시스템 간 _통합(integration)_을 테스트할 수는 없다. 외부 시스템은 목으로 대체해야 한다.
시뮬레이션을 주입할 수 있는 계층도 다양하다는 점은 짚고 넘어갈 만하다. 고수준 RPC/스토리지 계층에서 주입하면 더 단순하고 이해하기 쉽다. 하지만 그러면 더 낮은 수준의 오류와 에러 핸들링 테스트는 빠지게 된다.
DST는 다른 종류의 테스트나 벤치마크만큼이나, 워크로드를 얼마나 창의적이고 꼼꼼하게 작성하느냐에 달려 있다.
애플리케이션 평가를 위해 단 하나의 벤치마크에 의존하지 않듯이, 단 하나의 시뮬레이션 워크로드에만 의존하고 싶지 않을 수도 있다.
Will Wilson이 내게 이렇게 표현했다:
내 경험상 DST의 가장 큰 도전은 모든 랜덤 분포, 시스템 파라미터, 워크로드, 결함 주입 등을 튜닝해서 흥미로운 동작을 만들어내는 것이 매우 어렵고 노동 집약적이라는 점이다. 퍼징(fuzzing)이나 PBT처럼, 엄청난 테스트를 하는 것처럼 보이지만 실제로는 시스템 상태 공간(state space)의 아주 일부만 탐색하는 DST 시스템을 만드는 것은 무서울 정도로 쉽다. FoundationDB에서는 시뮬레이터에 투입한 작업의 대부분이, 테스트에서 무엇이 커버되지 않는지 추적하고 테스트를 더 좋게 만드는 방법을 찾아내는 반복적 과정이었다. 이 과정은 종종 공학이라기보다는 과학에 더 가깝다.
불행히도 퍼징과 달리, 코드의 단순 분기 커버리지(branch coverage)는 DST로 테스트하려는 시스템에서는 보통 그다지 좋은 신호가 아니다. Antithesis에서는 이를 Sometimes assertions로 다루고, FDB에서도 비슷한 것을 했으며, TigerBeetle 등도 각자 버전이 있을 거라 생각한다. 하지만 궁극적인 성과 지표는 DST가 당신의 버그를 100% 찾아내고 있느냐이다. 그 수준에 도달하는 것은 꽤 어렵다. Antithesis에서 진짜 야심 찬 부분은 하이퍼바이저가 아니라, 최소한의 인간 가이드나 감독으로도 훨씬 더 어려운 “내 DST가 제대로 작동하고 있나?” 문제를 풀려고 한다는 점이다.
디스크나 네트워크 IO 동작을 목으로 대체할 때, DST의 효용은 현실에서 일어날 수 있는 동작 스펙트럼을 얼마나 이해하고 있느냐에 달려 있다.
가능한 모든 오류 조건은 무엇인가? 원래 메서드의 극단적 지연(latency) 경계는 어디인가? 데이터 손상(corruption)이나 잘못된 대상에 대한 IO(misdirected IO)는?
반대로, 결정론적 시뮬레이션 테스트에서는 이런 미친 시나리오를 _설정 가능한 빈도_로 발생시키도록 구성할 수 있다. IO 지연이 특히 높은 실행들, 혹은 손상된 읽기/쓰기가 특히 많이 발생하는 실행들만 모아서 돌릴 수 있다. Joran과 나는 1년 전 TigerBeetle 시뮬레이터가 정확히 이를 어떻게 하는지 글로 썼다.
결정적으로, DST의 재현성은 _코드가 변하지 않을 때_에만 도움이 된다. 코드가 바뀌는 순간, 그 시드는 버그가 드러났던 상태에 더 이상 도달하지 못할 수도 있다. 따라서 DST의 재현성은, 그 시드에서의 시뮬레이션 실행을 코드가 바뀌어도 유지되는 통합 테스트(integration test)로 변환하는 데 도움이 된다는 의미에 더 가깝다.
고려사항 4 때문에, 새로운 시드와 새로운 히스토리를 찾기 위해서만이 아니라, 코드 변경 때마다 시드와 히스토리가 달라질 수 있기 때문에 시뮬레이터를 계속 다시 돌려야 한다.
Jepsen은 선형화 가능성(linearizability)을 테스트하면서 제한적인 프로세스/네트워크 결함 주입을 한다. 훌륭한 프로젝트다.
하지만 (위에서 설명한 노력들을 실제로 들인다면) DST가 가능한 것의 부분집합에 해당한다.
더 중요한 점은, Jepsen은 결정론적 실행과는 아무 관련이 없다는 것이다. Jepsen이 버그를 찾아도, 시스템이 결정론적 실행을 할 수 없다면 그 Jepsen 버그를 재현할 수도 있고 못할 수도 있다.
Will Wilson이 Jepsen과 FoundationDB에 대해 말한 또 다른 인용을 보자:
어쨌든 우리는 한동안 [결정론적 시뮬레이션 테스트]를 했고 데이터베이스의 모든 버그를 찾아냈다. 알아, 알아, 미친 소리처럼 들리지. 하지만 어느 정도 사실이야. 회사 역사 전체를 통틀어 고객이 보고한 버그는 한두 건뿐이었던 것 같다. 단 한 번도. “aphyr”로 알려진 Kyle Kingsbury는 Jepsen으로 테스트하는 것조차 귀찮아했는데, 뭘 찾아낼 수 있을 거라 생각하지 않았기 때문이야.
DST만으로(프로덕션에서의 시간 투자 없이) 얼마나 믿음을 둘 수 있는지는 한계가 있다. 하지만 DST를 도입하는 것이 해가 되지는 않는다. 그리고 위에서 말한 고려사항들을 제외하면, 제품의 커널을 훨씬 더 안정적으로 만들 가능성이 높다. 또한 DST를 사용하는 사람들은 이런 고려사항을 이미 알고 있다. 다만 DST를 모르는 사람들이 DST가 무엇에 탁월한지 직관을 쌓는 데 도움이 되도록, 이를 나열해볼 가치가 있다고 생각한다.
추가 읽을거리:
