Deterministic simulation (test sim, [С §18.4])

Stage 4, wave 2 (agent SIM, D-4100..D-4110). Code: runtime/src/sim/, C ABI runtime/include/oxl_sim.h, OxL controls std/test/test.oxl, runner compiler/src/driver/TestRunner.cpp, tests tests/unit/runtime/sim_test.cpp, conformance/§18.4/.

What it is#

One oxl::sim::World = N virtual nodes in one thread with virtual time. Nothing in it touches the wall clock, threads, the real network or the real disk, so the outcome of a run is a function of (seed, configuration, protocol code) only. A failing seed reproduces exactly: oxl test --seed N.

Writing a protocol for the simulation (Raft / SWIM authors)#

A node is a Process created by a factory on every boot. All its inputs arrive as callbacks; all its effects go through NodeCtx.

#include "sim/world.h"
using namespace oxl::sim;

class MyProto : public Process {
 public:
  explicit MyProto(NodeCtx& c) { /* recover durable state from c.disk() (a SimDisk or MemEnvDisk) */ }
  void on_start(NodeCtx& c) override { c.set_timer(150 * kMs, [this, c] { NodeCtx cc = c; tick(cc); }); }
  void on_message(NodeCtx& c, NodeId from, const std::string& bytes) override { /* decode, act, c.send(...) */ }
};

World w({.seed = 42});
NodeId a = w.add_node("a", [](NodeCtx& c) { return std::make_unique<MyProto>(c); });

Rules that keep a protocol deterministic and simulation-friendly:

1. No ambient state. No std::chrono, time(), rand(), std::random_device, threads, sockets, files, getenv inside protocol code. Time is c.now() (the node's own, possibly skewed clock), randomness is c.rng(), persistence is c.disk(), the network is c.send/broadcast, delays are c.set_timer. Iterating unordered_map/pointer-keyed containers is fine only if the order does not matter (or is sorted) - it is the one way a protocol can still be nondeterministic.
2. A crash destroys the Process. Whatever is not on the disk (and synced) is lost. Keep durable state behind c.disk(); call sync before acknowledging. Timers and messages of the dead incarnation are discarded; an old NodeCtx copy becomes a no-op (alive() == false), so a "zombie" cannot act. Messages in flight to a node reach its next incarnation if it is up by then.
3. Keep the NodeCtx by value in timer lambdas ([this, c]); it is a cheap handle (world, id, incarnation). Do not keep raw references to other nodes' Process objects - go through the network (the test harness may use w.process_as<T>(id)).
4. Faults are the test's job, not the protocol's: w.net().partition/block/drop/duplicate/reorder/latency, w.kill/restart/crash_for, w.set_clock_skew, w.set_disk_fail_rate, all schedulable with w.at/after. Randomise them from w.rng() (separate stream, so adding a fault does not change the network's dice).
5. Check with oracles. w.add_invariant(name, fn) runs after every event (Raft: at most one leader per term, log matching, committed entries never lost); NodeCtx::fail(msg) / World::fail(msg) stop the run. For client-visible behaviour record a History and call check_register (linearizable register). Add your own checker for lists/queues/sagas.
6. Sweep seeds: sweep(body, {.first = 1, .count = 500}) where body(World&) builds the scenario, runs it, returns "" or the failure text. The report names each failing seed, whether it reproduced (same trace hash), the trace tail and the command. tests/unit/runtime/sim_toy_register.h is a complete small example (ABD register + a deliberately buggy variant).
7. Debugging: World::trace().render(40) shows the last events (send/deliver/drop/part/heal/kill/start/note); Trace::first_divergence(a, b) locates where two runs of "the same" seed differ (a nondeterminism bug in the protocol). Use ctx.trace("...") for protocol notes. Set WorldOptions::trace_messages = false for long sweeps (faster; hash still covers faults).

WorldOptions::randomize_ties (default on) runs events with equal timestamps in a seeded random order. This is what makes a single-threaded simulation explore interleavings; leave it on.

Storage engine on a simulated node#

w.add_node("n1", factory, oxl::sim::memenv_disks()) gives the node a store::MemEnv (fault-injecting, deterministic crash model of the LSM store). w.disk_as<MemEnvDisk>(id)->env() is the store::Env* to open the store with; kill calls MemEnv::Crash(), restart calls Restart(), set_disk_fail_rate sets write_error/sync_error, and virtual time advances MemEnv's clock. (The adapter is header-only and compiled only when store/env_mem.h is on the include path - i.e. after the LSM branch is merged; it was checked against that branch's headers but is not built in this tree.)

oxl test --kind sim#

use std.test { net, node, disk, clock, sim }

test sim "checkout under faults" seeds 1..=500 {
  net.partition(["api"], ["storage"], for: 2s)
  net.latency(10ms, 300ms)       // the Standard's `10ms..300ms` needs Duration ranges (D-4109)
  node.kill("saga-0", after: 1s)
  clock.advance(1h)
  assert checkout(cart) is Order | PayError
}

• oxl test --kind sim runs the sim tests; for each seed of the seeds range the test binary is started as its own process with OXL_TEST_SEED=<n>. seeds must be a literal range (a..=b, a..b); without it the range is 1..=100.
• The run stops at the first failing seed and prints seed N failed (K of M seeds run) and reproduce: oxl test <pkg> --exact '<name>' --seed N. The failing seed is re-run once with OXL_SIM_REPORT=1; if the second run does not fail identically (different exit code or trace hash) the report adds a not deterministic warning.
• --seed N runs exactly that seed (and implies --kind sim). --seeds a..b (inclusive; or a count N = 1..N) overrides the range of every sim test. Both combine with --exact, -f, -t.
• While a process has a sim session (OXL_TEST_SEED set): std.time now()/Instant.now() read the world's virtual clock (starting at 2026-01-01T00:00:00Z), the program runs on the deterministic scheduler (below), sleep(d) parks the task until virtual time now + d, and rand is seeded. std.test controls: net.{latency,drop,duplicate,reorder,partition,block,heal,isBlocked}, node.{kill,restart,isUp}, disk.fail, clock.{advance,set,now}, sim.{seed,rand,note,traceHash}.

The deterministic scheduler (stage 5, wave 1: D-6200..D-6209)#

A test sim process runs its whole OxL program on the deterministic scheduler (runtime/src/sched/det.h/.cpp): the root task and every task it spawns run on the main thread, one at a time; nothing else in the process runs OxL code.

Consequences:

• Same seed => same interleaving, same rand/sim.rand/select choices, same virtual times, same output. The runner's check of a failing seed (OXL_SIM_REPORT=1, oxl-sim: ... trace=<hash> switches=<n>) now covers the task schedule as well as the world (D-6204), so a nondeterministic program is reported as such.
• Concurrent sleeps overlap: three tasks sleeping 1 s each take 1 s of virtual time (the legacy mode advanced the world by every sleep in turn, and crashed with tasks sleeping on several worker threads).
• clock.advance(d) / clock.set(t) from a task = sleeping until then (other tasks run at their own times, D-6206); sleep and clock.advance panic with simulation failed: <reason> when a world invariant broke meanwhile.
• All tasks blocked and no event pending => the program panics deadlock: every task of the deterministic simulation is blocked ... (exit 101); a program still waiting after 24 h of virtual time (OXL_SIM_TIME_LIMIT=<seconds>) panics likewise. A busy loop that polls now() never sees time move (time only advances when everyone waits) - use sleep.
• OXL_SIM_SCHED=0 restores the legacy mode (normal scheduler + sleep advances the world, D-4102) - an escape hatch only.
• C++: oxl::rt::det::run(fn, {.seed, .timeLimit, .preemptMin/Max, .recordSchedule, .maxSwitches}) returns a Result (finished/deadlock/timeLimit/livelock/worldFailed, traceHash, switches, schedule, foreignWakeups); it uses the current session's world or makes one. Tests: tests/unit/runtime/det_sched_test.cpp, tests/unit/runtime/node_state_test.cpp, tests/sim/sim_determinism.py (ctest sim_determinism), conformance §18.4/sim-concurrent-tasks-share-virtual-time.

Logical nodes in one process: NodeState (D-6210..D-6215)#

runtime/src/node_state.h: a NodeState (id, name, data dir, roles, simNode) is one logical node. A task belongs to a node (Task::node, inherited by every child, also by tasks of the background scope); spawnOnNode(n, fn) starts a task on a node; outside tasks NodeScope sets the thread's current node. nullptr = the process node = the original process-wide registries (a program that never creates a node behaves as before). On the deterministic scheduler "switching the current node" is implicit: it is the running task's node.

A registry is made per node by routing its accessor through nodeLocal<T>() (T per node, created on first use; nullptr for the process node). Converted so far:

Process-global state (inventory, stage 5 wave 1)#

Taken from nm of liboxlrt.a (every mutable data/bss symbol incl. function-local statics and thread-locals) plus the threads the runtime starts. Classes: share = fine to share between simulated nodes; node = must be per node for several nodes in one process; det = a nondeterminism source under simulation; done = converted in this wave.

OxL services on simulated nodes (stage 5 wave 2, S2, D-6250..D-6262)#

Code: runtime/src/sim/oxl_nodes.{h,cpp}, the layout in compiler/src/codegen/CGTest.cpp (simLayout), gtests tests/unit/runtime/sim_nodes_test.cpp, conformance §18.4/sim-services-on-simulated-nodes, §18.4/sim-node-crash-during-a-call, ctest shop_sim (tests/shop/run_shop_sim.py).

• Layout (D-6252): test sim … with cluster(nodes: n, roles: [...]) makes nodes n0..n{n-1} (body on n0). Without the clause, a package with a cluster declaration gets one node <role>-0 per role and a second <role>-1 for roles that run sagas or leader tasks (the shop: api-0, storage-0, saga-0, saga-1, gpu-0, ml-0; body on api-0). Each node is a NodeState + a World node.
• Boot: config, the layout's roles (fixed: the program's assign by is ignored), provide (the first node that may provide a value does; values are process-wide, D-6253), oxl_rpc_register, saga / pipeline recovery loops - the generated startup (oxl.test.startup), run in a task of the node.
• Calls (D-6258): a call that the calling node does not serve goes to a live node that does (seeded choice) as a World message; the receiving node runs the rpc's wire entry (decode, policy, idempotency, handler, encode) in a task of its own and answers with another message. Latency, drop, duplicate, reorder and partitions apply; a lost message ends at the caller's deadline. The caller is a trusted cluster peer (x-oxl-via, D-6259).
• Crash / restart (D-6254): node.kill(name) cancels every task of the node and fails what it waits for; its answers are lost. node.restart(name) drops its registries and boots it again. Stores are shared by all nodes and survive (D-6256).
• Membership (D-6257): cluster.nodes() lists the logical nodes; alive / dead come from the World at once.
• Debugging: OXL_SIM_NODES_DEBUG=1 (one line per boot / call / reply / crash), OXL_TEST_KEEP_BINARY=<path> (keep the test binary; run one seed with OXL_TEST_RUN=<index> OXL_TEST_SEED=<n>; use a fresh OXL_DATA_DIR per run, D-6255).

Still missing (open items):

• Storage is one shared, reliable store (no Raft replication of the storage role, no per-node disk, disk.fail does not reach stores, D-4109 (d)); membership is an exact oracle (no SWIM); cluster.leader is not elected (runs as on a single node).
• The router's EWMA / breaker / retry-on-another-node (route.cpp) is not used by the simulated transport; streaming rpcs (server / client / bidi streams) between simulated nodes are not carried (unary only); S.connect(addr) clients use the real network, which the deterministic scheduler refuses - mock them.
• Process-wide flags of rpc (g_testMode, g_listening), runtime_flags / argv, KMS, telemetry, logs, cron registrations are still process-wide (one value for every node).

A full example: Raft#

tests/unit/raft/ is the largest protocol written for the kernel so far (stage 4, D-4340..D-4343): raft_harness.h (the RaftNode process, oracle, parameters), raft_scenario.h (invariants checked after every event, clients, fault schedule, end-of-run checks), raft_kv_check.h (linearizability of put/get/cas) and raft_sim_test.cpp (the sweeps and the injected-bug tests). More seeds: OXL_RAFT_SEEDS=500 OXL_RAFT_FIRST_SEED=1000 test_raft --gtest_filter='RaftSim.Sweep*'. A failing seed prints the reproduction command; describe(cl) in the failure text shows every node's role, term, commit, log range, configuration and the leader's per-follower progress.

Исходник: docs/testing/simulation.md