//! pardes-replicas: one authority and several replicas of a session in one //! process (src/replica.zig), each client typing at once over its own //! delayed, jittered link, as monkey.zig's scripts type at a tty, each in a //! view of its own (src/views.zig) over the text they share; `--shared` //! puts them all in one, where they clash at every key: a stress of //! correctness, not a picture of a session. //! //! zig build replicas -Dplatform=tty -- [--seeds N] [--steps M] [--clients C] [--rtt 30,80,207] [--first K] [--shared] //! //! Gates, per seed and RTT: no replica diverges (every confirmed unit's //! digests agree as it is replayed), and at quiescence every replica's //! digest is the authority's. Reported per RTT: how inputs went (applied at //! once, stopped at a host call, left to the authority), how units were //! taken (fast path, rollback for a misprediction or another's input), and //! what a speculative apply, a copy and a rollback cost against a frame. const std = @import("std"); const libc = std.c; const pardes = @import("pardes"); const replica = pardes.replica; const Key = pardes.Key; const gpa = std.heap.c_allocator; var trace = false; const frame_us = 16_667; /// The authority's host: no frames drawn (a replica draws its own), and a /// pty that echoes what it is written, 2 ms later, as a shell's. const Host = struct { echo: std.ArrayListUnmanaged(struct { pane: u8, bytes: []u8 }) = .empty, fn watched(_: ?*anyopaque) bool { return false; } fn ptyWrite(ctx: ?*anyopaque, pane: u8, bytes: []const u8) void { const h: *Host = @ptrCast(@alignCast(ctx.?)); h.echo.append(gpa, .{ .pane = pane, .bytes = gpa.dupe(u8, bytes) catch return }) catch {}; } fn ignore(_: ?*anyopaque, _: []const u8) void {} const vtable: pardes.Host.VTable = .{ .watched = watched, .pty_write = ptyWrite, .set_clipboard = ignore }; fn host(h: *Host) pardes.Host { return .{ .ctx = h, .vtable = &vtable }; } }; const Kind = enum { input, to_authority, to_replica, echo }; const Msg = struct { at: u64, n: u64, kind: Kind, who: u16, bytes: []u8, fn order(_: void, a: Msg, b: Msg) std.math.Order { if (a.at != b.at) return std.math.order(a.at, b.at); return std.math.order(a.n, b.n); } }; const Link = struct { last: u64 = 0, /// When a message sent at `now` arrives: half the RTT, jitter on top, /// and never before the one sent ahead of it (a stream keeps order). fn arrive(l: *Link, random: std.Random, now: u64, one_way: u64, jitter: u64) u64 { const at = @max(l.last + 1, now + one_way + random.uintLessThan(u64, jitter + 1)); l.last = at; return at; } }; const Totals = struct { inputs: u64 = 0, speculated: u64 = 0, stopped: u64 = 0, unspeculated: u64 = 0, units: u64 = 0, fast: u64 = 0, mispredicted: u64 = 0, foreign: u64 = 0, rebases: u64 = 0, copies: u64 = 0, copy_bytes: u64 = 0, divergences: u64 = 0, unequal: u64 = 0, spec_ns: std.ArrayListUnmanaged(u64) = .empty, copy_ns: std.ArrayListUnmanaged(u64) = .empty, rollback_ns: std.ArrayListUnmanaged(u64) = .empty, fn add(t: *Totals, s: *const replica.Stats) !void { t.inputs += s.inputs; t.speculated += s.speculated; t.stopped += s.stopped; t.unspeculated += s.unspeculated; t.units += s.units; t.fast += s.fast; t.mispredicted += s.mispredicted; t.foreign += s.foreign; t.rebases += s.rebases; t.copies += s.copies; t.copy_bytes += s.copy_bytes; try t.spec_ns.appendSlice(gpa, s.spec_ns.items); try t.copy_ns.appendSlice(gpa, s.copy_ns.items); try t.rollback_ns.appendSlice(gpa, s.rollback_ns.items); } }; /// One client's next input: monkey.zig's mix, as events. fn nextEvent(random: std.Random, buf: *[64]u8) pardes.Event { const typed = "abcdefghijklmnopqrstuvwxyz0123456789 -_=+,:;()"; const normal = "hjklwbe0$xpuyoOiaAIdcv.nN%sC"; switch (random.uintLessThan(u8, 40)) { 0...15 => { buf[0] = typed[random.uintLessThan(usize, typed.len)]; return .{ .key = .{ .cp = buf[0], .text = buf[0..1] } }; }, 16...27 => { buf[0] = normal[random.uintLessThan(usize, normal.len)]; return .{ .key = .{ .cp = buf[0], .text = buf[0..1] } }; }, 28...31 => return .{ .key = .{ .cp = Key.escape } }, 32 => return .{ .key = .{ .cp = Key.enter } }, 33 => return .{ .key = .{ .cp = Key.backspace } }, 34 => return .{ .key = .{ .cp = switch (random.uintLessThan(u8, 4)) { 0 => Key.up, 1 => Key.down, 2 => Key.left, else => Key.right, } } }, 35 => { const n = random.intRangeAtMost(usize, 1, 24); for (buf[0..n]) |*c| c.* = typed[random.uintLessThan(usize, typed.len)]; return .{ .paste = buf[0..n] }; }, 36 => return .{ .command = switch (random.uintLessThan(u8, 4)) { 0 => "Newcol", 1 => "Zerox", 2 => "Undo", else => "Redo", } }, 37 => return .{ .resize = .{ .cols = @intCast(random.intRangeAtMost(u16, 60, 120)), .rows = @intCast(random.intRangeAtMost(u16, 16, 40)) } }, 38 => return .{ .mouse = .{ .button = .left, .kind = .press, .col = random.uintLessThan(u16, 80), .row = random.uintLessThan(u16, 24) } }, else => return .{ .mouse = .{ .button = .left, .kind = .release, .col = random.uintLessThan(u16, 80), .row = random.uintLessThan(u16, 24) } }, } } fn writeFile(path: [:0]const u8, lines: usize) !void { const fd = libc.open(path, .{ .ACCMODE = .WRONLY, .CREAT = true, .TRUNC = true }, @as(libc.mode_t, 0o644)); if (fd < 0) return error.OpenFailed; defer _ = libc.close(fd); var line: [80]u8 = undefined; for (0..lines) |n| { const text = try std.fmt.bufPrint(&line, "const value_{d:0>4} = {d}; // a line to edit\n", .{ n, n *% 7919 }); if (libc.write(fd, text.ptr, text.len) != @as(isize, @intCast(text.len))) return error.WriteFailed; } } const Run = struct { seed: u64, rtt_ms: u64, steps: usize, clients: u16, shared: bool }; fn run(r: Run, dir: []const u8, totals: *Totals) !void { if (trace) std.debug.print("seed {d} rtt {d} ms\n", .{ r.seed, r.rtt_ms }); var prng = std.Random.DefaultPrng.init(r.seed *% 0x9e3779b97f4a7c15 +% r.rtt_ms); const random = prng.random(); var host: Host = .{}; defer { for (host.echo.items) |e| gpa.free(e.bytes); host.echo.deinit(gpa); } var paths: [3][256:0]u8 = undefined; for (&paths, 0..) |*p, i| { const path = try std.fmt.bufPrintSentinel(p, "{s}/f{d}.zig", .{ dir, i }, 0); try writeFile(path, 60 + 40 * i); } // The tty's own boot (a raw shell, a text pane under it), then three // files looked at: keys go to the last, a pane's shell echoes. const a = try replica.Authority.init(gpa, .{ .cols = 100, .rows = 30, .boot = .tty }, host.host()); defer a.deinit(); const first = try gpa.dupe(u8, try a.unit(0, 0)); defer gpa.free(first); var reps: [8]*replica.Replica = undefined; for (reps[0..r.clients], 1..) |*rp, id| rp.* = try replica.Replica.init(gpa, @intCast(id), first); defer for (reps[0..r.clients]) |rp| rp.deinit(); for (&paths) |*path| { var line: [300]u8 = undefined; const unit = try a.local(.{ .command = try std.fmt.bufPrint(&line, "Look {s}", .{std.mem.sliceTo(path, 0)}) }); for (reps[0..r.clients]) |rp| rp.confirm(unit); } // Each client a view of its own (src/views.zig), the first the // session's; or, --shared, every client in the one. if (!r.shared) for (reps[1..r.clients], 2..) |rp, id| { const opened = try a.openView(@intCast(id)); rp.view = opened.view; for (reps[0..r.clients]) |each| each.confirm(opened.unit); }; var queue: std.PriorityQueue(Msg, void, Msg.order) = .empty; defer queue.deinit(gpa); var n: u64 = 0; const one_way = r.rtt_ms * 1000 / 2; const jitter = one_way / 10; var up: [8]Link = @splat(.{}); var down: [8]Link = @splat(.{}); var left: [8]usize = @splat(r.steps); // Each client's first input, soon. for (0..r.clients) |c| { try queue.push(gpa, .{ .at = random.uintLessThan(u64, 200_000), .n = n, .kind = .input, .who = @intCast(c + 1), .bytes = &.{} }); n += 1; } while (queue.pop()) |m| { defer if (m.bytes.len > 0) gpa.free(m.bytes); switch (m.kind) { .input => { const c = m.who - 1; var buf: [64]u8 = undefined; const ev = nextEvent(random, &buf); const before = reps[c].stats; const msg = try gpa.dupe(u8, try reps[c].input(ev)); if (trace) std.debug.print("{d} ms client {d}: {t} {s} -> {s}\n", .{ m.at / 1000, m.who, ev, switch (ev) { .key => |k| k.text, .paste => |t| t, .command => |t| t, else => "", }, if (reps[c].stats.speculated > before.speculated) "applied" else if (reps[c].stats.stopped > before.stopped) "STOPPED" else if (reps[c].stats.unspeculated > before.unspeculated) "view" else "waits" }); try queue.push(gpa, .{ .at = up[c].arrive(random, m.at, one_way, jitter), .n = n, .kind = .to_authority, .who = m.who, .bytes = msg }); n += 1; left[c] -= 1; if (left[c] > 0) { // A typist: keys 50-200 ms apart, a pause now and then. const gap: u64 = if (random.uintLessThan(u8, 12) == 0) random.intRangeAtMost(u64, 300_000, 1_500_000) else random.intRangeAtMost(u64, 50_000, 200_000); try queue.push(gpa, .{ .at = m.at + gap, .n = n, .kind = .input, .who = m.who, .bytes = &.{} }); n += 1; } }, .to_authority, .echo => { const unit = if (m.kind == .echo) try a.local(.{ .output = .{ .pane = @intCast(m.who), .bytes = m.bytes } }) else try a.take(m.bytes); for (0..r.clients) |c| { const copy = try gpa.dupe(u8, unit); try queue.push(gpa, .{ .at = down[c].arrive(random, m.at, one_way, jitter), .n = n, .kind = .to_replica, .who = @intCast(c + 1), .bytes = copy }); n += 1; } for (host.echo.items) |e| { try queue.push(gpa, .{ .at = m.at + 2_000, .n = n, .kind = .echo, .who = e.pane, .bytes = e.bytes }); n += 1; } host.echo.clearRetainingCapacity(); }, .to_replica => { const rp = reps[m.who - 1]; rp.confirm(m.bytes); rp.settle(); }, } } const want = replica.digestOf(a); for (reps[0..r.clients], 1..) |rp, id| { try totals.add(&rp.stats); if (rp.diverged) |why| { totals.divergences += 1; std.debug.print("seed {d} rtt {d} ms: replica {d} diverged: {s}\n", .{ r.seed, r.rtt_ms, id, why }); } else if (!rp.quiet() or rp.digest() != want) { totals.unequal += 1; std.debug.print("seed {d} rtt {d} ms: replica {d} at quiescence: {s}\n", .{ r.seed, r.rtt_ms, id, if (rp.quiet()) "another digest" else "inputs still pending" }); } } } fn pct(samples: []u64, p: usize) u64 { if (samples.len == 0) return 0; std.mem.sort(u64, samples, {}, std.sort.asc(u64)); return samples[@min(samples.len - 1, samples.len * p / 100)]; } pub fn main(init: std.process.Init) !void { const args = try init.minimal.args.toSlice(init.arena.allocator()); var seeds: u64 = 4; var first: u64 = 0; var steps: usize = 120; var clients: u16 = 3; var rtts: []const u64 = &.{ 30, 80, 207 }; var shared = false; var rtt_buf: [8]u64 = undefined; var i: usize = 1; while (i < args.len and std.mem.eql(u8, args[i], "--shared")) : (i += 1) shared = true; while (i + 1 < args.len) : (i += 2) { while (i < args.len and std.mem.eql(u8, args[i], "--shared")) : (i += 1) shared = true; if (i + 1 >= args.len) break; const name = args[i]; const value = args[i + 1]; if (std.mem.eql(u8, name, "--seeds")) seeds = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--first")) first = try std.fmt.parseInt(u64, value, 10) else if (std.mem.eql(u8, name, "--steps")) steps = try std.fmt.parseInt(usize, value, 10) else if (std.mem.eql(u8, name, "--clients")) clients = @min(8, try std.fmt.parseInt(u16, value, 10)) else if (std.mem.eql(u8, name, "--rtt")) { var it = std.mem.tokenizeScalar(u8, value, ','); var k: usize = 0; while (it.next()) |v| : (k += 1) rtt_buf[k] = try std.fmt.parseInt(u64, v, 10); rtts = rtt_buf[0..k]; } else return error.UnknownOption; } trace = libc.getenv("PARDES_REPLICA_TRACE") != null; if (libc.getenv("PARDES_REPLICA_FILL")) |b| pardes.rollback.Epoch.fill = std.fmt.parseInt(u8, std.mem.span(b), 0) catch 0xff; var dir_buf: [256]u8 = undefined; const tmp = std.mem.span(libc.getenv("TMPDIR") orelse "/tmp"); const dir = try std.fmt.bufPrint(&dir_buf, "{s}/replicas-{d}", .{ tmp, @as(u32, @intCast(libc.getpid())) }); try std.Io.Dir.createDirAbsolute(init.io, dir, .default_dir); defer std.Io.Dir.cwd().deleteTree(init.io, dir) catch {}; var failed = false; std.debug.print("{d} seeds x {d} inputs from each of {d} clients, {s}; costs in us (frame {d})\n", .{ seeds, steps, clients, if (shared) "sharing one view" else "a view each", frame_us }); std.debug.print(" rtt inputs at-once stopped view units fast rollback(mis+foreign) rate rebase spec p50/p99 copy p50/p99 (KB) rollback p50/p99 diverged unequal\n", .{}); for (rtts) |rtt| { var t: Totals = .{}; for (first..first + seeds) |seed| try run(.{ .seed = seed, .rtt_ms = rtt, .steps = steps, .clients = clients, .shared = shared }, dir, &t); const rollbacks = t.mispredicted + t.foreign; std.debug.print("{d:>4} {d:>6} {d:>7} {d:>7} {d:>4} {d:>6} {d:>6} {d:>6} ({d}+{d}) {d:>5.1}% {d:>6} {d:>5}/{d:<6} {d:>5}/{d:<5} ({d}) {d:>7}/{d:<7} {d:>8} {d:>7}\n", .{ rtt, t.inputs, t.speculated, t.stopped, t.unspeculated, t.units, t.fast, rollbacks, t.mispredicted, t.foreign, @as(f64, @floatFromInt(rollbacks)) * 100 / @as(f64, @floatFromInt(@max(t.inputs, 1))), t.rebases, pct(t.spec_ns.items, 50) / 1000, pct(t.spec_ns.items, 99) / 1000, pct(t.copy_ns.items, 50) / 1000, pct(t.copy_ns.items, 99) / 1000, t.copy_bytes / @max(t.copies, 1) / 1024, pct(t.rollback_ns.items, 50) / 1000, pct(t.rollback_ns.items, 99) / 1000, t.divergences, t.unequal, }); if (t.divergences > 0 or t.unequal > 0) failed = true; } if (failed) std.process.exit(1); }