CockroachDB의 전례 없는 희귀 버그를 추적하며, 분산 시스템에서 비결정성과 결정론적 디버깅, 그리고 Antithesis 플랫폼을 활용한 실질적 버그 분석 및 수정을 소개합니다.
비결정성은 다음 가능한 상태들 중 어디로도 갈 수 있는 성질로, 양날의 검입니다. 컴퓨터 과학(CS)에서 비결정성의 개념은 상태 공간에 대한 복잡성을 다루는 데 핵심적입니다. 비결정성의 가장 초기 활용은 [Chomsky, 1959]와 [Rabin and Scott, 1959]에 등장합니다. 전자는 간결한 컨텍스트 프리 문법(CFG), 예를 들면 산술 표현식을 소개했습니다.
S ::= x | y | z | S + S | S * S | (S)
후자는 비결정적 유한 오토마타(NFA), 즉 정규 표현식을 제시했죠. 두 개념 모두 거의 모든 CS 졸업생이 아는 기본 개념입니다.
물론, P = NP 문제([Cook, 1971 그리고 Levin, 1973])와 NP-완전성 길들이기를 향한 영원한 탐구도 있습니다. 예시로, 커밋된 트랜잭션 히스토리의 "직렬 가능성" 테스트 문제는 NP-완전입니다(Testing Distributed Systems for Linearizability). 그러나 각 오브젝트별 완전한 순서를 안다면, 검증 문제는 이제 P에 속합니다. 실제로 Elle 체커는 선형 시간 안에 동작합니다.
소프트웨어 검증에서 비결정성은, 예를 들어 CockroachDB 같은 현대 분산 시스템 거의 모두에서 불가능한 전체 상태 열거 대신, 심볼릭 모델 검증(SMC) 같은 기법을 가능하게 합니다. 최근 대규모 SMC 적용 사례로 AWS 데이터센터의 부트 코드 모델 검증이 있습니다. TLA+ 역시 비결정성을 통해 더 표현력이 커집니다. 아래 논의할 백만 분의 일 버그 역시 ParallelCommits.tla 모델 구현의 부산물입니다.
CS 이론가들은 주로 비결정성의 좋은 면을 보지만, 분산 시스템의 실무자들은 종종 나쁜 면—(분산) 장애 재현의 악몽—에 시달립니다. 정말로 다른 이들도 지적했듯, “비결정성은 분산 시스템 개발을 어렵게 한다” 합니다. 버그 재현 불능은 분산 시스템 디버깅이 악명 높게 힘든 주된 원인 중 하나입니다. 이런 비결정성을 데모닉 비결정성이라 부릅니다. (직관적으로, "최악의" 가능한 선택이 일어남.) 예를 들어 Go의 select 문은 Dijkstra의 가드 명령과 비슷합니다. 데모닉 비결정성을 무시하면 이런 버그가 나옵니다. (또 다른 예시에서는 여러 고루틴이 default 절에 동시에 진입하면 트리거됩니다.)
수십 년 동안 연구개발이 이어졌지만 "백만 분의 일" 버그의 디버깅과 재현에 실질적 도움을 주는 도구는 명백히 부족합니다. 이런 버그는 실패 확률이 극히 낮으며, 대개 여러 내부 상태 전이(예, 레이스 컨디션, 간헐적(하드웨어) 장애 등)가 맞물려야 발생합니다. 최근까지 CockroachDB에도 그런 버그가 숨어 있었습니다. 최고급 내결함성을 목표로, FoundationDB 창업자들이 설립한 Antithesis의 도움으로, 이 난해한 버그를 거의 결정론적으로 추적·재현할 수 있었습니다! (분산) 트레이스 추가, 수많은 재실행, 로그 분석을 통해 Alex Sarkesian(이 글 공동 저자, Cockroach Labs 전 KV 엔지니어)가 버그를 고쳤습니다.
결정적 재현 없이는 기존 디버깅·(스트레스) 테스트로는 실질적 해법이 나오지 않습니다. "백만 분의 일" 버그라면 사실상 거의 운에 맡기는 셈입니다. 유감스럽게도 결정적 디버깅 도구의 수준은 여전히 아쉽습니다.
아래에서 기존 도구들을 살피고, 이어서 Antithesis의 자율 테스트 시스템 경험을 소개합니다. 마지막으로 발견된 버그와 그 수정에 대한 직관적 설명이 있습니다.(기술적 상세는 부록 참고.)
“결정적 디버깅” 개념은 새롭지 않습니다. Debug Determinism(2011)는 “효과적인 디버깅은 _동일한 실패_와 _동일한 근본 원인_의 재현을 전제한다”는 새로운 결정론 모델을 제안합니다. 개념적으로 우리가 원하는 것이죠. 하지만 실제로 달성은 어렵습니다. 왜 그런지, 현재 무엇이 있는지 빠르게 훑어봅시다.
CockroachDB처럼 상태를 가진 분산 시스템이 다양한 배포 환경에서 실행될 때, 비결정성의 원천은 끝이 없어 보입니다. 예기치 않은 네트워크 지연, 스레드 타이밍, 디스크 오류 등은 시스템에 숨어있는 희귀한 버그를 (거의 항상 재현·진단·수정이 불가능한 방법으로) 만듭니다.
특히 통합 테스트 같은 _플레이키(불안정) 테스트_는 비결정성 때문에 드러난 버그 예시가 많습니다. 대표적 원인은 TCP 포트 충돌, 파일 디스크립터 부족 등 리소스 한계에서 비롯되거나, 레이스 컨디션 및 타임아웃처럼 스케줄러 비결정성에서 비롯됩니다(플레이키 테스트 설문, Reproducible Containers 참고).
하드웨어(인터럽트), 시계(예: clock_gettime), /dev/(u)random, CPU 명령(예: RDRAND) 등도 그렇습니다. 단일 주소 공간(프로세스) 너머로는 네트워크가 비결정성의 큰 원천입니다.
ptrace의 구원ptrace는 Version 6 Unix(1975년경)부터 있는 시스템 호출입니다. 원래 디버깅(중단점)을 지원하려고 추가됐으나, 오늘날에는 syscall 추적(strace), 기록·재생(rr)까지 다양한 용도에 쓰입니다. 본질적으로 ptrace는 원래의 syscall을 가로채고 결과를 수정해 어떤 syscall도 모방할 수 있게 해줍니다(strace in Go 예제). 이 덕분에 clock_gettime같은 비결정적 syscall도 논리적 시계를 써서 결정론적으로 모방할 수 있습니다.
사실 싱글 머신 환경에서 결정론적 디버깅엔 ptrace, 논리적 시계, 단일 스레드 스케줄러, RAM 디스크만 있으면 충분합니다. 단일 머신 넘어서면 네트워크가 가장 큰 비결정성 공급자입니다. 논리적 시계는 CPU 하드웨어 퍼포먼스 카운터—retired conditional branches (RCB)—로 효과적으로 추출할 수 있습니다.
이미지 참고: 다양한 결정론적 디버깅 도구 타임라인
지금까지 결정론적 디버깅 도구는 꽤 드물고 실험적입니다. 지난 20년간 등장한 주목할 만한 도구들의 타임라인입니다. valgrind는 엄밀히 말해 결정론적이진 않지만, 단일 스레드 (공정) 스케줄러를 구현해 rr의 영감을 주었습니다. 가장 최근의 발전은 hermit, dettrace에서 영감을 받았습니다.
rr이 아마 가장 널리 알려진 결정론적 디버거일 것입니다. 하지만 이전 기록을 결정론적으로 재생할 수 있을 뿐입니다; hermit는 임의의 바이너리를 결정론적으로 실행할 수 있습니다. (rr의 경우 같은 바이너리와 입력으로 실행해도 각기 다른 기록이 남음. 관련 설명 참고.)
hermit는 아직 매우 실험적이고, rr는 CPU 퍼포먼스 카운터를 지원하는 클라우드 VM에서 production-grade로 쓸 수 있습니다.
하이젠베르크의 불확정성 원리를 상기하십시오. 물리학자들은 컴퓨터 과학자보다 훨씬 전에 비결정성의 어두운 면을 발견했습니다. 결정론적 디버거도 양자역학처럼 결정론적 기록이 원래 실행을 바꾼다는 부작용을 보입니다.
상기 모든 도구는 ptrace에 의존하기에 2~3배 정도의 큰 오버헤드(추가 syscall, 컨텍스트 스위칭 등)를 야기합니다. seccomp+eBPF로 비모방 syscall 오버헤드는 제거할 수 있지만, 남은 오버헤드도 rr의 다양한 최적화(예, syscall 버퍼링)에도 여전히 상당합니다. 결국, ptrace는 "가난한 자의 결정론적 디버거"에 가깝습니다. 대신, 하이퍼바이저 차원에서 결정성을 내장할 수 있다면 어떨까요?
Antithesis 플랫폼은 FoundationDB의 결정론적 시뮬레이션 프레임워크에서 영감을 받았습니다. FoundationDB는 네트워크/디스크 I/O 시뮬레이션과 장애 주입 기능이 데이터베이스 코드에 촘촘히 내장돼 있습니다. 예를 들어 이 코드는 시뮬레이터에서 무결성 검사기 실행 시 손상된 키를 삽입할 수 있습니다. 이때 전체 데이터베이스 클러스터가 단일 주소 공간 내 단일 스레드로 동작합니다. 모든 하드웨어 I/O 및 비결정적 syscall이 시뮬레이션되므로 실질적으로 화이트박스 결정론적 디버거입니다. 단, RocksDB 같은 외부 코드는 비결정성의 원인이 됩니다.
FoundationDB처럼 처음부터 결정론적 시뮬레이션이 장착된 DB도 드물고, 기존 대규모 코드베이스에 이런 프레임워크를 이식하는 건 지나치게 어렵습니다. Antithesis는 결정론적 하이퍼바이저를 써서 어떤 바이너리든 사실상 결정론적 시뮬레이션 테스트를 가능하게 합니다.
FoundationDB와 마찬가지로, 장애 주입이 기본 탑재되어 있습니다. Antithesis는 프로세스 실패(panic 등) 감시, 로그상의 invariant 위배 감시, 사용자 정의 메시지 패턴(regexp)을 통한 자동 실패 탐지 등으로 다양한 장애를 찾습니다. 하나의 실험(시나리오)은 결정론적 무작위 장애 하에 시뮬레이터 실행 한 번을 뜻하며, 테스트 한 세션에 수천 번 반복 실행되어 많은 고유 경로(코드 엣지)가 탐색되도록 최적화됩니다. 아래는 25시간에 걸쳐 수천 개 시나리오가 실행된 예시입니다.
Antithesis는 단순한 결정론적 시뮬레이터를 넘습니다. 퍼저를 이용해 "흥미로운" 시나리오를 찾고, 커버리지 도구가 있다면 최대한 다양한 코드 분기를 탐색하도록 주입 위치를 안내합니다. 위 그래프처럼, 첫 5시간 급격히 커버리지가 늘다 그 다음은 주로 안정화됩니다(분산 시스템 공통 패턴).
이제 알 수 있듯, Antithesis는 _커버리지 기반 장애 주입 결론론적 그레이박스 시뮬레이터_라 요약할 수 있죠. 즉, 퍼저와 결정론적 디버거의 결합물입니다.
이 희귀 버그가 처음 발각된 건 2021년이었습니다. 고객 제보로가 아닌, Sentry 크래시 리포팅 모듈에 자동 등록된 건입니다. 스택트레이스만 놓고는 invariant 위배—정의되지 않은 상태—임을 알 수 있었고, 이는 CockroachDB 코드가 패닉을 일으켜 crash + 진단 정보 수집을 유도한 상황입니다. 스택 외엔 아무 정보도 없었으며, 내부 대규모 테스트에서도 재현된 적이 없었습니다.
KV팀 엔지니어들은 이 희귀 크래시 리포트로부터 모호한 오류(분산 SQL 요청 재시도 중 발생)를 의심하게 됐습니다. 2023년, Antithesis 플랫폼에 평가를 시작합니다. 행운이 좋게도 시나리오 하나가 정확히 해당 상태에서 종료되는 것을 로그로 확인합니다.
에러 메시지 "transaction unexpectedly committed"는 이미 커밋된 트랜잭션에 추가 연산(쓰기 등)이 불가해야 한다는 규칙을 어겼음을 뜻합니다. 원자성 보장 트랜잭션의 데이터는 곧바로 다른 트랜잭션이 읽을 수 있으므로, 이후 데이터 변경 시도는 트랜잭션 격리 모델 위반이 됩니다. 위 로그를 분석해 몇 가지 실마리를 얻었죠(스택트레이스만 있었던 크래시 리포트와 달리).
실패 메시지는 inflight 요청 배치(ba), 트랜잭션 레코드(txn), 관련된 키 범위를 보여줍니다. EndTxn(commit)과 Put 요청이 섞인 배치가 이미 커밋된 트랜잭션 대상으로 평가되어 거부됩니다—특히 이전에 commit 상태 불확정(indeterminate commit)으로 기록된 경우입니다. 오류 바로 직전에는 트랜잭션 복구 메시지가, 이후에는 RPC 에러가 나타나며, 이는 네트워크 장애 시뮬레이션에 의한 것인지 버그 원인과 직접적 관련이 있는지는 불확실합니다.
이 새로운 통찰을 바탕으로 근본 원인을 곧 밝힐 것 같았지만, 실제 원인 규명에는 상당한 시간이 걸렸습니다. 분산 트레이스와 결정적 재현 반복을 통해 "transaction unexpectedly committed"에 필요한 상태머신 조건이 드러났고, 반복하며 원인, 수정, 재현 유닛 테스트가 완성됐습니다.
(자세한 분석은 부록 참고.) 범인은 모호한(불확정하게 커밋) write 재시도를 높은 타임스탬프로 시도하는 과정에서 _비멱등성_이 위배된 것입니다. 일반적으로, 트랜잭션 조정자는 비멱등 재시도가 모호한 실패(RPC 에러 등)를 초래할 경우를 방지해야 하며, 해당 fix가 이를 구현합니다. 비멱등 재시도를 명시적으로 추적하여, 재시도 실행 중 비멱등 조건(예: write 타임스탬프 변경) 발생 시 SQL 클라이언트에 result is ambiguous 에러를 응답합니다.
이게 가장 우아한 복구법처럼 보이진 않아도, 사실상 비멱등 트랜잭션 재시도 처리를 SQL 클라이언트 쪽으로 옮긴 겁니다. CAP 이론 상 모든 걸 동시에 가져갈 순 없으니, 네트워크 가용성 일부 상실 상황에서 트랜잭션 커밋 여부를 결정론적으로 확인할 방법이 없기 때문입니다. 마지막으로, Parallel Commit 프로토콜은 TLA+로 검증됐으나 실제 구현의 _보수적 언더앱록시메이션(underapproximation)_을 모델링하지 않는다는 점을 밝힙니다. (TLA+ 명세 참고)
분산 시스템에서 노드 수가 늘어날수록 각자의 스레드 타이밍, 네트워크 조건, 하드웨어 등으로 인한 비결정성도 늘어나 실질적으로 버그 수가 기하급수적으로 늘어납니다. 이를 찾고 고치려면 새로운 테스트·디버깅 접근이 필요합니다. 최근 데이터베이스 신뢰성 및 강건성 세미나에서 실무자들은 이렇게 요약했습니다:
현 시점 산업계에서의 표준은 보통 테스트를 (예: 1000회) 많이 반복 실행하는 것이며, 여기에 추가 로깅, 약간 조정된 설정, 런타임 검증기, 또는 문제 발생 확률을 높이기 위한 환경/워크로드 변경을 곁들입니다.
새로운 기술답게 Antithesis 플랫폼도 미완성인 부분이 있습니다. 결정론적 재생만으로 항상 문제를 재현할 수 있는 것은 아니며, 특히 코드가 바뀌면(유닛/통합 테스트와 달리) 재현성이 보장되지 않습니다. 로그 추가, 장애 상태 추론, 상태머신 복원에 상당한 노력이 필요했고, 그 과정에서 바이너리(로깅 추가한 새 바이너리)가 항상 똑같은 terminal state에 도달하지 않을 수도 있습니다. 단, 수정 범위가 지역적이라면 실제 실행 결정성은 매우 높습니다(직선형 코드는 RCB 카운터 기반 논리적 시계 덕분에 결정성 보존).
rr와 달리 Antithesis는 재생 중 스텝 바이 스텝 디버깅이 안 됩니다. 즉 내부 상태를 관찰하는 건 로그에 의존하는데, 피드백 루프가 좀 짧아진다면 재현까지 소요 시간을 줄일 수 있을 것입니다.
그럼에도 Antithesis는 많은 난해 버그를 무력화할 수 있는 큰 가능성을 보입니다. 결정론적 디버깅이 미래임을 믿으며, Antithesis가 그 길을 선도하는 중이라 생각합니다.
시퀀스 다이어그램은 버그 상황을 설명합니다. 핵심은 모호한 쓰기(첫 txn.Batch{CPut(200, ‘y’)} 시도)입니다. 즉, y키에 대한 RPC가 타임아웃되거나 실패할 경우, 해당 RPC가 쓴 결과를 트랜잭션 조정자는 알지 못합니다.
첫 쓰기 실패 후 즉시 leaseholder가 n2에서 n3으로 이동합니다. 두 번째 쓰기가 새로운 leaseholder로 가면서, 조정자 쪽에서 트랜잭션 타임스탬프를 read refresh 방식으로 조정해야 합니다. 네트워크 장애 주입은 트랜잭션 heartbeat 신호도 놓치게 만듭니다. 동시에 경쟁 트랜잭션이 트랜잭션 상태 복구를 유발해 조정자의 재시도와 경주를 벌이고, 이쪽이 이기면 트랜잭션이 선명하게 "committed"가 됩니다. 반면, 원래 트랜잭션 조정자는 뒤늦게 이 상태를 발견하고 패닉을 냅니다.
조금 더 기술적으로 들어가면, CockroachDB에서 사용하는 Parallel Commits 프로토콜의 트랜잭션 복구 매커니즘과 그로 인한 레이스 컨디션을 주목해야 합니다. 다음 SQL 문처럼 암묵적 트랜잭션을 예로 들어봅시다.
INSERT INTO accounts (account_id, name) VALUES (100, ‘x’), (200, ‘y’);
CockroachDB는 행을 키-값 쌍으로 저장하며, 여러 범위로 파티셔닝합니다. 예를 들어 100 <= account_id < 200은 한 범위, 200 <= account_id < 300은 또 다른 범위, 그리고 이 각 범위는 클러스터의 서로 다른 노드에 leaseholder가 있습니다. 이 구조 때문에 원자적으로 보장하면서 다른 트랜잭션이 동시에 볼 수 있게 하려면 명시적 트랜잭션 레코드가 필요합니다—즉, 커밋 시점 타임스탬프를 갖는 것입니다.
TransactionRecord{
Status: COMMITTED,
Timestamp: 5,
...
}
이 프로토콜에 대해선 이전 블로그글을 참고하세요. 짧게 요약해, 전통적 투페이즈 커밋은 모든 쓰기가 완료되고 난 뒤 트랜잭션 레코드를 COMMITTED로 바꿔서 데이터의 가시성을 결정합니다. 반면 CockroachDB Parallel Commits 프로토콜은 여기에 쓰기 레코드가 명시적(COMMITTED)이 아닌 묵시적(STAGING)으로도, 단 모든 writes가 확인됐으면 읽기가 가능하게 합니다.
TransactionRecord{
Status: STAGING,
Timestamp: 30,
Writes: []Key{100, 200, ...},
...
}
트랜잭션 조정자가 트랜잭션 레코드와 writes를 동시에 병렬로 쓸 수 있고, 마지막 단계는 비동기적으로 추후에 COMMITTED로 승격시키는 것입니다. 이로써 클라이언트 체감 트랜잭션 지연을 낮추고 처리량을 증가시킵니다.
CockroachDB KV 연산 기준으로는 대략 이런 과정입니다.
모든 트랜잭션이 결국 명시적으로(COMMITTED) 승격되도록 하기 위해 “Transaction Status Recovery Procedure”가 필요합니다. TLA+ 명세로 모든 묵시적 커밋 상태가 종국적으로 명시적으로 변경됨을 형식적으로 보장합니다. 복구 로직은 조정자가 죽으면, 추후 이 레코드를 목격하는 다른 연산이 복구를 촉진하도록 설계되었습니다. 복구 절차가 시작되면, 레코드에 기록된 키들이 정말로 영구적으로 쓰였는지 확인되어, 맞으면 COMMITTED, 아니면 ABORTED로 처리합니다. 트랜잭션 원자성을 위해 반드시 all-or-none입니다.
조정자가 트랜잭션 커밋 사실을 인지하지 못하는 버그는 어떻게 생길까요? 위에서 말한 RPC 오류 때문입니다. 트랜잭션의 writes 중 한 RPC가 실패하면, 조정자는 해당 쓰기의 durability를 몰라요. 실제 해당 노드에서는 성공적으로 쓰고, 네트워크가 끊겨서 응답만 못 돌아왔을 수도 있습니다. 2PC 용어로, acknowledgment가 빠진 채 write가 durability는 된 상태입니다. 그래서 조정자는 write를 다시 시도하게 됩니다. 이미 쓰기가 durability가 되어 있으면 검증(멱등 재시도)만 하면 됩니다. 안 되어 있으면 다시 쓰기를 시도하죠.
하지만, 한번 writes가 durability를 확보하고 레코드가 STAGING이 되면 다른 트랜잭션은 이것을 묵시적 커밋으로 봅니다. 결과적으로, 쓰기 RPC 실패가 조정자의 상태를 DB 내 다른 트랜잭션이 보는 상태와 불일치 시킬 수 있습니다. 더불어, 묵시적 커밋이 되면, 다른 연산에 의해 복구 절차가 시작될 수도 있습니다. 즉, 조정자는 모호한 상태가 되고, 다른 연산이 이를 명확히 커밋으로 해석해 트랜잭션을 승격시키면 조정자는 뒤늦게 "unexpectedly committed"에 빠지는 것이죠.
커밋된 트랜잭션(명시적이건, 묵시적이건)은 이후 변경이 불가능하며, 이는 트랜잭션 원자성 및 격리 규칙 유지에 필수적입니다. 즉, 다음과 같은 결과—
> SELECT account_id, value FROM accounts;
account_id | value
------------+-------
100 | x
200 | y
(2 rows)
txnID=1이 account_id=100에 x를 썼다면, 이후 동일 txn이 다시 값을 z로 바꿀 수 없습니다. 마찬가지로 타임스탬프를 더 나중으로 옮겨서도 안 됩니다. 만약 그게 가능하면,
> SELECT account_id, value FROM accounts;
account_id | value
------------+-------
(0 rows)
위처럼 결과가 바뀌겠죠. CockroachDB는 이런 동작을 허용하지 않습니다.
여기서 핵심은 _멱등 재시도(idempotent replay)_의 정의입니다. 보통, 아직 미커밋 상태에서는 write의 타임스탬프 변경(read refresh 이후)은 괜찮으나, 커밋 후에는 write에 일관성이 생기므로 timestamp 변경이 비멱등적 부작용이 됩니다.
고치려면? 조정자가 RPC 실패로 인해 모호한 상태일 때, 멱등성 체크에서 타임스탬프 변경 등의 비멱등 상황을 탐지해, "SQL error 40003 statement_completion_unknown"을 클라이언트에 반환하게 합니다. 이는 클라이언트가 RPC 장애에 유연하게 대응하도록 돕습니다.
