시간 여행 디버거를 위해 지수 감쇠 버퍼를 구현하고, 적은 공간으로 깊은 실행 이력을 유지하는 방법을 설명합니다.
저는 WASM 인터프리터를 처음부터 직접 만들고 있었습니다. 독특한 기능은 명령어 수준까지 완전히 스냅샷 가능하다는 점입니다. 실행 도중 어느 시점에서든 snapshot()을 호출하면 전체 실행 상태를 바이트 목록으로 기록해서, 정확히 그 명령어까지의 모든 것을 캡처할 수 있습니다. 나중에 이를 복원하면 실행은 멈췄던 바로 그 지점에서 다시 이어집니다.
여기 Conway’s Game of Life를 실행하는 데모가 있습니다. 시뮬레이션을 틱 중간에 스냅샷하고, 새 프로세스로 포크한 뒤, 같은 상태에서 두 실행이 서로 다르게 전개되는 모습을 볼 수 있습니다:
저는 스냅샷 기능이 시간 여행 디버거와 아주 잘 맞물리기 때문에 구현해볼 만한 흥미로운 기능이라고 생각했습니다. 예를 들어 버그를 추적하려고 프로그램을 한 단계씩 실행하고 있다고 해봅시다. 일반 디버거에서는 명령어를 한 단계라도 너무 멀리 진행하면 전체 세션을 다시 시작하고, 원래 있던 지점까지 조심스럽게 다시 밟아가야 합니다. 시간 여행 디버거에서는 그냥 뒤로 한 단계씩 가거나, 프로그램 실행 이력의 아무 지점으로나 점프할 수 있습니다.
시간 여행 디버거를 만들려면, 먼저 이력을 저장할 방법이 필요합니다.
제가 떠올린 가장 순진한 구현은 모든 명령어마다 모든 스냅샷을 저장하는 것이었습니다. 당연히 이건 확장성이 좋지 않습니다. Game of Life 데모에서 각 스냅샷은 대략 1.2 MB입니다. RAM이 16 GB인 MacBook Air에서는 OOM이 나기 전까지 약 13,000개의 스냅샷만 저장할 수 있습니다. WASM 프로그램은 몇 밀리초 만에 13,000개의 명령어를 태워버릴 수 있습니다. 가장 최근 N N개의 스냅샷만 유지할 수도 있겠지만, 프로그램이 빡빡한 루프에 들어가면 N N개의 스냅샷이 전부 그 루프 안에만 쌓여서 바깥쪽 문맥을 전부 잃게 됩니다.
우리는 모든 스냅샷을 저장할 필요가 없습니다. 어떤 스냅샷이든 하나만 있으면, 거기서부터 다시 앞으로 재생해서 같은 실행 상태에 도달할 수 있습니다. 그래서 명령어 100으로 되돌아가고 싶은데 가장 가까운 스냅샷이 명령어 90에 있다면, 10개 명령어를 앞으로 재생해서 상태를 재구성하면 됩니다.
도전 과제는 어떤 스냅샷을 유지하고 어떤 것을 버릴지 결정하는 데 있습니다. 최근 이력은 촘촘해야 해서 1개나 2개 명령어 뒤로 가는 일이 즉시 이루어져야 합니다. 하지만 동시에 더 과거로도 멀리 도달할 수 있어야 하며, 그쪽에서는 간격이 더 커져도 괜찮습니다.
제가 프로젝트를 lobste.rs에 공유했을 때, 누군가 정말 놀라운 블로그 글을 알려주었습니다. 저자 David Barbour는 지수 감쇠 버퍼라는 자료구조를 소개합니다. 아이디어는 단순합니다. 최근 스냅샷은 많이 유지하고, 더 과거로 갈수록 점점 적게 유지하는 것입니다. Barbour는 이어서, 과거로 갈수록 중간 세부 정보는 잃게 되는 대신 아주 적은 공간으로도 깊은 이력을 보관할 수 있다는 통찰을 풀어냅니다.
스냅샷의 밀도는 반감기라고 부르는 고정 간격마다 절반으로 줄어듭니다. 이 방식은 공간 효율이 놀라울 정도로 좋습니다. 반감기 한 단위만큼 저장 공간을 더할 때마다 도달 범위가 두 배가 되기 때문입니다. 반감기가 50일 때 스냅샷 1,000개를 보관할 수 있다면, 단순히 최근 1,000개 명령어만 덮는 것이 아닙니다. 2 1000/50=2 20≈2^{1000/50} = 2^{20} \approx 백만 개 명령어를 덮게 됩니다. 2,000개의 스냅샷을 저장하면 2 40 2^{40}, 대략 1조 개 명령어에 이릅니다.
아래 슬라이더를 움직여 스냅샷 수와 반감기가 도달 범위에 어떤 영향을 주는지 살펴보세요:
snapshots: 1000
half life: 50
2 2^{,}1000 / 50 = 2 2^{,}20 = 1.0 million
매 50개 스냅샷마다 그보다 더 과거에는 절반만 유지하는 방식으로 1,000개의 스냅샷을 보관하면, 최근
1.0 million instructions
을 디버깅할 수 있습니다.
실제로는 버퍼 크기와 반감기를 처음에 정해 둡니다. 그리고 매 명령어마다 새 스냅샷을 넣습니다. 버퍼가 가득 차면 새 스냅샷 하나가 들어올 때마다 오래된 것 하나를 내보내야 합니다.
결정론적으로 스냅샷을 내보낼 수도 있습니다. 예를 들어 N N번째로 오래된 스냅샷을 제거하는 식입니다. 하지만 그러면 Barbour가 _temporal aliasing_이라고 부르는 문제에 부딪히게 됩니다. 제거가 결정론적이면 프로그램의 주기적 동작과 동기화될 수 있습니다. 빡빡한 루프에 갇혀 있다면 매번 루프의 같은 위상에서 스냅샷이 제거되어, 이력에 사각지대가 생깁니다. 제거를 확률적으로 만들면 이런 동기화를 깨뜨릴 수 있습니다. 오래된 스냅샷이 제거될 가능성은 여전히 훨씬 높지만, 매번 정확히 어떤 것이 버려질지는 달라집니다.
Barbour는 반감기, 제거 전략, 버퍼 크기가 모두 애플리케이션마다 조정 가능하다고 설명합니다. 그리고 글의 마지막에는 Haskell로 지수 버퍼를 구현한 코드도 던져줍니다.
이 글의 나머지 부분에서는 제 시간 여행 디버거에 맞춰서, 지수 버퍼를 어떻게 구현했는지 살펴보겠습니다.
우리의 제거 전략은 기하 샘플링을 사용합니다. 버퍼가 가득 차면, 다음 식으로 제거할 스냅샷을 샘플링합니다:
i=⌊log(U)log(1−ln2 h)⌋i = \left\lfloor \frac{\log(U)}{\log\left(1 - \frac{\ln 2}{h}\right)} \right\rfloor
여기서 U∼Uniform(0,1)U \sim \text{Uniform}(0, 1) 이고 h h는 반감기입니다. 더 낮은 인덱스(오래된 항목)일수록 더 높은 인덱스(최근 항목)보다 지수적으로 제거될 가능성이 큽니다. 반감기 매개변수 h h가 곡선을 제어합니다. 인덱스 i i의 항목은, 최신 쪽으로 h h 인덱스 더 가까운 항목보다 제거될 가능성이 두 배입니다.
아래 시각화는 크기 100인 버퍼에서 각 슬롯의 제거 확률을 보여줍니다. 슬라이더를 움직여 반감기를 바꾸고 분포가 어떻게 이동하는지 보세요. 왼쪽 슬롯은 더 오래된 항목이라 더 자주 제거되고(막대가 더 높음), 오른쪽 슬롯은 더 새로운 항목이라 거의 건드리지 않습니다.
**buffer capacity:100half life:**50
half_life: 50
← older (more likely to evict)newer (less likely to evict) →
디버거에서는 반감기를 50으로, 버퍼 용량을 스냅샷 1,000개로 설정했습니다. 그러면 2 1000/50=2 20≈1,048,576 2^{1000/50} = 2^{20} \approx 1{,}048{,}576개 명령어의 이력에 도달할 수 있습니다. 그리고 제거 곡선은 가파릅니다. 오래된 스냅샷은 공격적으로 쳐내는 반면, 최근 이력은 거의 손대지 않습니다.
**buffer capacity:1,000half life:**50
← older (more likely to evict)newer (less likely to evict) →
아래가 구현의 핵심입니다. 각 스냅샷은 그 시점의 명령어 수와 함께 저장됩니다. 명령어 수는 오직 증가만 하므로, 버퍼는 별도 비용 없이 항상 정렬된 상태를 유지합니다. 즉, 이력의 어떤 지점으로든 점프하는 작업은 이진 탐색이 됩니다. 목표 명령어 이전의 가장 가까운 스냅샷을 찾고, 거기서부터 앞으로 다시 재생하면 됩니다. 난수는 이렇게 작은 일에 의존성을 끌어오고 싶지 않아서 단순한 xorshift PRNG를 사용했습니다.
type Snapshot = Vec<u8>;
struct ExponentialDecayBuffer {
// stores a list of tuples of (instruction_count, snapshot data)
buf: Vec<(u64, Snapshot)>,
capacity: usize,
half_life: f32,
rng: u64
}
impl ExponentialDecayBuffer {
pub fn new(capacity: usize) -> Self {
Self {
buf: Vec::with_capacity(capacity),
capacity,
half_life: 50.0,
// the seed
rng: 0xABBA_ABBA,
}
}
pub fn find_nearest_before(&self, instruction_count: u64) -> Option<&Snapshot> {
match self.buf.binary_search_by_key(&instruction_count, |(t, _)| *t) {
Ok(i) => Some(&self.buf[i]),
Err(0) => None,
Err(i) => Some(&self.buf[i - 1]),
}
}
pub fn push(&mut self, instruction_count: u64, snapshot: Snapshot) {
let entry = (instruction_count, snapshot);
if self.buf.len() < self.capacity {
self.buf.push(entry);
return;
}
let i = self.sample_geometric_index();
let i = i.clamp(0, self.buf.len() - 2);
self.buf.remove(i + 1);
self.buf.push(entry);
}
fn sample_geometric_index(&mut self) -> usize {
let u = self.generate_random_f32();
let i = u.log(1.0 - 2_f32.ln() / self.half_life);
i.floor() as usize
}
fn generate_random_f32(&mut self) -> f32 {
self.rng ^= self.rng << 13;
self.rng ^= self.rng >> 7;
self.rng ^= self.rng << 17;
(self.rng >> 40) as f32 / (0xFF_FFFF as f32)
}
}
이 버퍼의 좋은 점은 깔끔한 추상화라는 것입니다. 디버거는 무엇을 남기고 무엇을 버릴지 고민할 필요가 없습니다. 그저 스냅샷과 함께 push를 호출하면, 버퍼가 내부적으로 제거를 처리합니다. 디버거가 뒤로 이동해야 할 때는 find_nearest_before를 호출해서 사용할 수 있는 최선의 스냅샷을 받습니다. 까다로운 부분들, 즉 기하 샘플링, 확률적 제거, 반감기 조정 같은 것들은 두 메서드 뒤에 숨겨져 있습니다.
디버거에 이것을 연결하는 일도 꽤 단순합니다. 매 N N개 명령어마다 스냅샷을 떠서 버퍼에 넣습니다. 앞으로 한 단계 가는 것은 명령어 하나를 실행하는 일입니다. 뒤로 한 단계 가는 것은 가장 가까운 이전 스냅샷을 찾고, 그것을 복원한 다음, 원하는 지점까지 앞으로 다시 재생하는 것입니다. 궁금하다면, 제 프로젝트에서 사용한 실제 디버거와 감쇠 버퍼를 볼 수 있습니다. 다만 아래는 핵심을 전달하기 위한 단순화된 버전입니다.
struct Interpreter;
impl Interpreter {
fn is_completed(&self) -> bool { todo!() }
fn run_one_instruction(&mut self) { todo!() }
fn replay_forward(&mut self, n: u64) { todo!() }
fn snapshot(&self) -> Vec<u8> { todo!() }
fn restore(&mut self, snapshot: &[u8]) { todo!() }
}
enum StepResult {
Stepped,
ReachedStart,
Completed,
}
struct Debugger {
interpreter: Interpreter,
buffer: ExponentialDecayBuffer,
instruction_count: u64,
}
impl Debugger {
pub fn new(interpreter: Interpreter, mut buffer: ExponentialDecayBuffer) -> Self {
// snapshot at instruction 0 so step_back always has a base to replay from
let snapshot = interpreter.snapshot();
buffer.push(0, snapshot);
Self {
interpreter,
buffer,
instruction_count: 0,
}
}
pub fn step_forward(&mut self) -> StepResult {
if self.interpreter.is_completed() {
return StepResult::Completed;
}
self.interpreter.run_one_instruction();
self.instruction_count += 1;
// periodically snapshot
if self.instruction_count.is_multiple_of(1_000) {
let snapshot = self.interpreter.snapshot();
self.buffer.push(self.instruction_count, snapshot);
}
StepResult::Stepped
}
pub fn step_back(&mut self) -> StepResult {
if self.instruction_count == 0 {
return StepResult::ReachedStart;
}
let target = self.instruction_count - 1;
// find the latest snapshot before our target
let (snapshot_ic, snapshot) = self
.buffer
.find_nearest_before(target)
.expect("we snapshot at instruction 0");
// restore that snapshot, then replay forward to the target
self.interpreter.restore(snapshot);
self.interpreter.replay_forward(target - snapshot_ic);
self.instruction_count = target;
StepResult::Stepped
}
}