Squashing the Heisenbug with Deterministic Simulation Testing by Dominik Tornow

Distributed systems are hard to test, with bugs that are difficult to reproduce and diagnose. This talk introduces Deterministic Simulation Testing, a technique that removes non-determinism to enable exhaustive, reproducible tests. We’ll walk through building a custom simulator, from controlling time to orchestrating concurrency and failures, and share practical strategies for applying this approach to your own systems.

1. A ScyllaDB
Community
Squashing the Heisenbug
Dominik Tornow
CEO

2. Resonate HQ
Dominik Tornow
CEO at Resonate HQ
■Focus on concurrent, distributed systems
■Software Engineer by day
■Author by night

3. Complex Problems. Simple Code.
Rest in Peace

4. Distributed Async Await
A language integrated programming model for
concurrent, distributed applications

5. Concurrency
Non-deterministic partial order
Distribution
Non-deterministic partial failure

6. P = a • b • c
Q = x • y • z

7. Sequential Composition
P ; Q

8. a • b • c • x • y • z

9. Concurrent Composition
P | Q

10. a • b • c • x • y • z
a • b • x • c • y • z
a • b • x • y • c • z
a • b • x • y • z • c
a • x • b • c • y • z
a • x • b • y • c • z
a • x • b • y • z • c
a • x • y • b • c • z
a • x • y • b • z • c
a • x • y • z • b • c
x • a • b • c • y • z
x • a • b • y • c • z
x • a • b • y • z • c
x • a • y • b • c • z
x • a • y • b • z • c
x • a • y • z • b • c
x • y • a • b • c • z
x • y • a • b • z • c
x • y • a • z • b • c
x • y • z • a • b • c

11. Distributed Composition
P | Q | ⊥

12. a • ⊥
x • ⊥
a • b • ⊥
a • x • ⊥
x • a • ⊥
x • y • ⊥
a • b • c • ⊥
a • b • x • ⊥
a • x • b • ⊥
a • x • y • ⊥
x • a • b • ⊥
x • a • y • ⊥
x • y • a • ⊥
x • y • z • ⊥
a • b • c • x • ⊥
a • b • x • c • ⊥
a • b • x • y • ⊥
a • x • b • c • ⊥
a • x • b • y • ⊥
a • x • y • b • ⊥
a • x • y • z • ⊥
x • a • b • c • ⊥
x • a • b • y • ⊥
x • a • y • b • ⊥
x • a • y • z • ⊥
x • y • a • b • ⊥
x • y • a • z • ⊥
x • y • z • a • ⊥
a • b • c • x • y • ⊥
a • b • x • c • y • ⊥
a • b • x • y • c • ⊥
a • b • x • y • z • ⊥
a • x • b • c • y • ⊥
a • x • b • y • c • ⊥
a • x • b • y • z • ⊥
a • x • y • b • c • ⊥
a • x • y • b • z • ⊥
a • x • y • z • b • ⊥
x • a • b • c • y • ⊥
x • a • b • y • c • ⊥
x • a • b • y • z • ⊥
x • a • y • b • c • ⊥
x • a • y • b • z • ⊥
x • a • y • z • b • ⊥
x • y • a • b • c • ⊥
x • y • a • b • z • ⊥
x • y • a • z • b • ⊥
x • y • z • a • b • ⊥
a • b • c • x • y • z
a • b • x • c • y • z
a • b • x • y • c • z
a • b • x • y • z • c
a • x • b • c • y • z
a • x • b • y • c • z
a • x • b • y • z • c
a • x • y • b • c • z
a • x • y • b • z • c
a • x • y • z • b • c
x • a • b • c • y • z
x • a • b • y • c • z
x • a • b • y • z • c
x • a • y • b • c • z
x • a • y • b • z • c
x • a • y • z • b • c
x • y • a • b • c • z
x • y • a • b • z • c
x • y • a • z • b • c
x • y • z • a • b • c

13. a • ⊥
x • ⊥
a • b • ⊥
a • x • ⊥
x • a • ⊥
x • y • ⊥
a • b • c • ⊥
a • b • x • ⊥
a • x • b • ⊥
a • x • y • ⊥
x • a • b • ⊥
x • a • y • ⊥
x • y • a • ⊥
x • y • z • ⊥
a • b • c • x • ⊥
a • b • x • c • ⊥
a • b • x • y • ⊥
a • x • b • c • ⊥
a • x • b • y • ⊥
a • x • y • b • ⊥
a • x • y • z • ⊥
x • a • b • c • ⊥
x • a • b • y • ⊥
x • a • y • b • ⊥
x • a • y • z • ⊥
x • y • a • b • ⊥
x • y • a • z • ⊥
x • y • z • a • ⊥
a • b • c • x • y • ⊥
a • b • x • c • y • ⊥
a • b • x • y • c • ⊥
a • b • x • y • z • ⊥
a • x • b • c • y • ⊥
a • x • b • y • c • ⊥
a • x • b • y • z • ⊥
a • x • y • b • c • ⊥
a • x • y • b • z • ⊥
a • x • y • z • b • ⊥
x • a • b • c • y • ⊥
x • a • b • y • c • ⊥
x • a • b • y • z • ⊥
x • a • y • b • c • ⊥
x • a • y • b • z • ⊥
x • a • y • z • b • ⊥
x • y • a • b • c • ⊥
x • y • a • b • z • ⊥
x • y • a • z • b • ⊥
x • y • z • a • b • ⊥
a • b • c • x • y • z
a • b • x • c • y • z
a • b • x • y • c • z
a • b • x • y • z • c
a • x • b • c • y • z
a • x • b • y • c • z
a • x • b • y • z • c
a • x • y • b • c • z
a • x • y • b • z • c
a • x • y • z • b • c
x • a • b • c • y • z
x • a • b • y • c • z
x • a • b • y • z • c
x • a • y • b • c • z
x • a • y • b • z • c
x • a • y • z • b • c
x • y • a • b • c • z
x • y • a • b • z • c
x • y • a • z • b • c
x • y • z • a • b • c
!
!
!

14. Software Systems
Thinking about Correctness

15. Specification
Implementation

19. Software Verification
aims to proof
all traces are within the specification
Software Testing
aims to find
some traces are outside the specification

20. Software Verification
Will prove the absence of bugs
Software Testing
Can prove the presence of bugs

21. Software Testing
Thinking about Deterministic Simulation Testing

22. Increase number
of distinct traces
Increase length
of distinct traces
Ensure reproducibility
of distinct traces

23. System

24. SystemApplicationEnvironmentState State

25. ApplicationEnvironmentState StateAPISimulator

26. ApplicationSimulatorState StateAPI
The trace is determined by
the initial state of the simulator and the initial state of the system

27. Simulator
Seed
Simulator
Step
Simulator
Next State
Input
Application
Init State
Application
Step
Application
Next State
Input
Simulator
Step
Simulator
Next State
Application
Step
Application
Next State

28. Deterministic Simulation Testing
Distributed Async Await

30. Server Worker1
Worker2 Worker3
Worker4 Worker5
Network

31. Server Worker1
Worker2 Worker3
Worker4 Worker5
NetworkSimulator

32. const simulator = new Simulator(options);
simulator.register(new WorkerProcess("worker-1", "default"));
simulator.register(new WorkerProcess("worker-2", "default"));
simulator.register(new ServerProcess("server"));

33. Simulator.send(
Message.Request(unicast(“user"), unicast("server"), {
...
param: { func: "fibonacci", args: [10] }
...
})
);

34. {
seed: 21, // Random Seed
delay: 0.75, // Message Delay
dropProb: 0.25, // Message Drop
duplProb: 0.25, // Message Duplication
flipProb: 0.25 // Message Modification
}

35. {
“params”: {
“func”: “factorial”
}
}

36. {
“params”: {
“func”: “factorial”
}
}
invalid format

37. {
“params”: {
“func”: “factorial”
}
}
valid format, invalid schema

38. {
“params”: {
“func”: “factorial”
}
}
valid format, valid schema, invalid payload

39. export interface Network {
send(req: Req, callback: (timeout: boolean, res: Res) => void): void;
recv(msg: Msg): void;
}

40. git clone https://github.com/resonatehq/resonate-sdk-ts.git

44. Conclusion
Deterministic Simulation Testing

45. Correct programs are more elegant than incorrect ones
Barton P. Miller

46. Thank you! Let’s connect.
Dominik Tornow
[email protected]
@DominikTornow
https://resonatehq.io
Resonate HQ