Deterministic Simulation Testing: Metodologia di Iniezione Guasti in TigerBeetle e FoundationDB
Perché Testare i Sistemi Distribuiti È Così Difficile
Il problema fondamentale è il non-determinismo. Un sistema distribuito ne ha molteplici fonti:
- Scheduling dei thread: L'OS decide quale thread eseguire e quando
- Timing di rete: I pacchetti arrivano in ordine imprevedibile con latenza variabile
- Timing I/O disco: Letture e scritture si completano a velocità variabili
- Skew dell'orologio: Gli orologi di sistema su macchine diverse derivano indipendentemente
- Timing dei guasti: Crash, partizioni di rete ed errori disco avvengono in momenti arbitrari
Un bug che richiede una combinazione specifica di questi eventi non-deterministici potrebbe richiedere miliardi di esecuzioni di test per manifestarsi con testing casuale. E anche se lo trovi, non puoi riprodurlo perché non controlli lo scheduler dell'OS, la rete, o il disco.
I test di integrazione tradizionali provano a gestire questo con sleep e retry:
# Così la maggior parte della gente testa i sistemi distribuiti (non fatelo)
def test_leader_election():
cluster.start(3)
time.sleep(5) # "aspetta che l'elezione completi" 🤞
leader = cluster.get_leader()
assert leader is not None
cluster.kill(leader)
time.sleep(10) # "aspetta la ri-elezione" 🤞🤞
new_leader = cluster.get_leader()
assert new_leader is not None
assert new_leader != leader
Questo test passa il 99% delle volte e manca ogni bug interessante.
La Metodologia di FoundationDB
FoundationDB è stato pioniere nel simulation testing per database di produzione. Il loro insight chiave: se controlli tutte le fonti di non-determinismo, puoi esplorare l'intero spazio degli stati sistematicamente.
L'architettura ha tre pilastri:
1. Core Single-Threaded, Event-Driven
L'intero database gira in un singolo thread. Non c'è concorrenza a livello OS. Tutte le operazioni asincrone sono modellate come eventi in una coda di priorità:
Coda Eventi (ordinata per tempo simulato):
t=100ms: Nodo A riceve AppendEntries dal Nodo B
t=102ms: Timeout elezione del Nodo C scatta
t=103ms: Scrittura disco su Nodo A completa
t=105ms: Timer heartbeat del Nodo B scatta
t=108ms: Partizione di rete inizia (guasto iniettato)
Il simulatore estrae eventi in ordine, li esegue, e qualsiasi evento risultante torna nella coda. Poiché la coda è deterministica (stesso seed -> stesso stato iniziale -> stesso ordine eventi), l'esecuzione è perfettamente riproducibile.
2. Layer I/O Astratto
Ogni interazione con il mondo esterno passa attraverso un'interfaccia:
class INetwork {
virtual Future<Void> connect(NetworkAddress addr) = 0;
virtual Future<Void> send(Connection conn, Bytes data) = 0;
virtual Future<Bytes> receive(Connection conn) = 0;
};
class IDisk {
virtual Future<Void> write(FileHandle fh, Offset off, Bytes data) = 0;
virtual Future<Bytes> read(FileHandle fh, Offset off, Size len) = 0;
virtual Future<Void> sync(FileHandle fh) = 0;
};
class IClock {
virtual double now() = 0;
virtual Future<Void> delay(double seconds) = 0;
};
In produzione, questi chiamano syscall reali. In simulazione, sono sostituiti con fake che introducono ritardi controllati, guasti e riordinamenti.
3. Iniezione di Guasti Basata su Seed
Dato un seed casuale, il simulatore decide:
class FaultInjector:
def __init__(self, seed):
self.rng = Random(seed)
def should_drop_packet(self) -> bool:
return self.rng.random() < 0.01
def network_delay_ms(self) -> float:
return self.rng.exponential(scale=5.0)
def should_inject_partition(self, time) -> bool:
return self.rng.random() < (1.0 / 3600000.0) * time_step_ms
def should_crash_node(self, node_id) -> bool:
return self.rng.random() < 0.0001
def disk_write_should_fail(self) -> bool:
return self.rng.random() < 0.001
L'Approccio di TigerBeetle: VOPR
TigerBeetle (un database di transazioni finanziarie scritto in Zig) ha preso le idee di FoundationDB e ha costruito VOPR — il simulatore di Viewstamped Operation Replication. Ciò che rende distintivo l'approccio di TigerBeetle è quanto profondamente la simulazione è integrata nel codebase.
In TigerBeetle, l'astrazione I/O non è un ripensamento — è la fondazione:
const IO = if (is_simulation)
@import("io_simulation.zig").IO
else
@import("io_uring.zig").IO;
L'I/O di simulazione sostituisce io_uring con un event loop deterministico:
pub const IO = struct {
prng: std.rand.DefaultPrng,
event_queue: PriorityQueue(Event),
tick: u64,
pub fn submit_write(self: *IO, buffer: []const u8, offset: u64) Completion {
const delay = self.prng.random_int(u64) % 10 + 1;
const completion = Completion{
.result = if (self.should_inject_fault())
error.DiskError
else
.success,
};
self.event_queue.insert(.{
.tick = self.tick + delay,
.completion = completion,
});
return completion;
}
fn should_inject_fault(self: *IO) bool {
return self.prng.random_int(u64) % 1000 == 0;
}
};
Il runner VOPR esegue l'intero cluster TigerBeetle in un singolo processo:
pub fn run(seed: u64) !void {
var prng = std.rand.DefaultPrng.init(seed);
var cluster = Cluster.init(&prng, .{
.replica_count = 6,
.standby_count = 2,
.client_count = 3,
});
var tick: u64 = 0;
while (tick < 10_000_000) : (tick += 1) {
if (prng.random_int(u64) % 100 == 0) {
const fault = random_fault(&prng);
cluster.inject_fault(fault);
}
cluster.tick();
cluster.check_invariants();
}
}
La chiamata check_invariants() è la chiave. Dopo ogni singolo tick della simulazione — non solo alla fine — TigerBeetle verifica che tutte le proprietà di sicurezza siano rispettate.
Costruire il Proprio Harness di Simulazione
Questa metodologia può essere applicata anche a progetti di scala minore. Ecco l'architettura pratica:
Passo 1: Definisci il Confine del Determinismo
Fonti di non-determinismo:
✅ Orologio di sistema → avvolgere con interfaccia Clock iniettabile
✅ Numeri casuali → usare PRNG con seed ovunque
✅ I/O di rete → avvolgere con interfaccia Network iniettabile
✅ I/O disco → avvolgere con interfaccia Storage iniettabile
✅ Scheduling thread → usare event loop single-threaded in simulazione
❌ Ordine allocazione memoria → generalmente deterministico, ma attenzione alle hash map
❌ Gestione segnali → disabilitare in simulazione
Passo 2: Costruisci il Layer I/O Astratto
type Clock interface {
Now() time.Time
After(d time.Duration) <-chan time.Time
}
type Network interface {
Send(to NodeID, msg Message) error
Receive() <-chan Message
}
type Storage interface {
Append(entries []LogEntry) error
ReadRange(start, end uint64) ([]LogEntry, error)
Sync() error
}
type SimClock struct {
current time.Time
}
func (c *SimClock) Now() time.Time { return c.current }
func (c *SimClock) Advance(d time.Duration) { c.current = c.current.Add(d) }
Passo 3: Il Runner di Simulazione
type Simulator struct {
seed int64
rng *rand.Rand
clock *SimClock
network *SimNetwork
nodes []*RaftNode
events *PriorityQueue
}
func (s *Simulator) Run(ticks int) error {
for i := 0; i < ticks; i++ {
s.clock.Advance(time.Millisecond)
s.maybeInjectFault()
s.network.DeliverPending(s.rng)
for _, node := range s.nodes {
node.Tick()
}
if err := s.checkInvariants(); err != nil {
return fmt.Errorf("invariante violato al tick %d (seed %d): %w",
i, s.seed, err)
}
}
return nil
}
Passo 4: Integrazione CI
simulation-test:
strategy:
matrix:
seed-range: ["0-100", "100-200", "200-300", "300-400", "400-500"]
steps:
- run: |
START=$(echo ${{ matrix.seed-range }} | cut -d- -f1)
END=$(echo ${{ matrix.seed-range }} | cut -d- -f2)
for seed in $(seq $START $END); do
echo "Esecuzione simulazione con seed $seed"
./bin/simulation-test --seed=$seed --ticks=1000000
done
Bug che Questa Metodologia Ha Trovato
Nella pratica, il simulation testing trova costantemente bug in queste categorie:
Scritture di leader stale: Un nodo crede di essere il leader ma è stato deposto. Accetta una scrittura che viene persa quando il log del vero leader la sovrascrive.
Split-brain durante guarigione partizione: Quando una partizione di rete guarisce, due sotto-cluster hanno stato divergente. Il protocollo di riconciliazione ha una finestra dove entrambi credono di avere il quorum.
Riordinamento scritture disco: Su hardware reale, write(A); write(B); non garantisce che A sia persistito prima di B. La simulazione inietta riordinamento delle scritture per trovare assunzioni sull'ordine di persistenza.
Race condition dei timer: Quando due timer scattano allo stesso istante simulato, l'ordine conta. La simulazione esplora entrambi gli ordinamenti per ogni seed.
Un harness di simulazione può trovare bug complessi di interleaving in secondi che richiederebbero settimane per essere scoperti tramite debugging manuale. Il contrasto tra settimane di indagine manuale e secondi di esecuzione della simulazione sottolinea il valore della metodologia.
Per sistemi che devono essere corretti sotto guasti — database, protocolli di consenso, processori di transazioni, lock distribuiti — il deterministic simulation testing non è opzionale. È l'unica metodologia che trova sistematicamente i bug che contano di più: quelli che corrompono i dati.