s4ql

A simulator of the storage design

This page runs a model of s4ql's storage design in your browser. Instances of one database share a bucket in S3. They write, read, and take turns with the lease while you crash them, pause them, cut them off, lose answers from S3, fail disks, and set clocks wrong.

A checker looks at the state after every step and tells you when a rule of the design breaks. Plant a bug to see it do that.

The model is JavaScript, written from the spec, the notes of the storage core, and the Go code. It is not the Go code, which is tested in a simulation of its own. Where the model is simpler than the design, the list at the end says so.

One seed drives every random choice. The seed and your actions are kept in the link, so you can share a run and replay it step for step.

Things to try

  1. Stall the instance that serves. A spare takes the lease once the manifest has stood still for 33 seconds. Resume the stalled one: its next swap fails, and it refuses reads.
  2. Lose the answer of the next swap of manifest.json, then write. The instance asks S3 again and finds its commit in the log.
  3. Crash the instance that serves, then start it again. It waits for its old lease to time out, because its holder ID was in memory. The next holder catches up from the log.
  4. Make a spare's monotonic clock run twice as fast. It can take the lease early, and a read on the old holder can miss a commit. The spec allows that: clocks affect only reads. No acknowledged write is lost.
  5. Plant a bug, turn on random faults, and wait for the checker to stop the run.
0:00.000
Checker

Instances

Each instance is one process with a random holder ID in memory, a cache on its own disk, a wall clock, and a monotonic clock. The one that holds the lease and is caught up serves.

The bucket

S3 is strongly consistent. manifest.json is replaced only by a compare-and-swap on its version, which S3 makes from its content. A commit object is created only if nothing is at its key, under its SHA-256.

manifest.json

Not written yet.

    Workload and faults

    Faults of one instance are on its card under "Instances". These act on S3, on the network, and on the run.

    Workload

    Writes and reads from the application, to random instances. A write inserts one value.

    S3 and the network

    Buggify and planted bugs

    Buggify makes marked points of the model do legal but unusual things, from the seed. A planted bug is one wrong decision.

    This seed switches on these points:

      The checker

      After every step of the model, it checks the rules again on what changed.

      Invariants and how often each was checked

      What happened

      Times are virtual, from the start of the run. Newest first.

      Timeline

        Requests to S3

          Where the model is simpler

          Commit objects
          JSON, not Protocol Buffers. A write inserts one value into one table, and the commit object contains that row and the statement as an annotation.
          Reads
          A read is one step: the check of the lease by both clocks and the read of the cache happen together. The Go code checks the lease before it fixes the state that the read sees, and once more after.
          Catch-up
          Each missing commit object is downloaded once, checked against its name, and applied. The Go code downloads it a second time to apply it.
          Timeouts
          Every request to S3 times out after 5 seconds. In the Go code, uploads and downloads of commit objects have 5 minutes. The application gives up on a write after 45 seconds, longer than a takeover, so that a write that is open while its instance stalls can still reach its swap.
          The cache
          A list of values and the name of the last commit it applied, changed in one step. SQLite's own behaviour, such as its locks and its log, is not modelled. A failed disk fails the next local read or write, and a restart clears it.
          S3
          Requests are applied one at a time as they arrive. Each way of a request takes 8 to 60 ms. Under buggify, S3 refuses a correct swap with 409 at random, where real S3 does it while another write to the key is on its way.
          Shutdown
          The instance releases the lease and ends, without waiting for calls that still run.
          Clocks
          A stale read counts as allowed while an instance measures time wrongly, and for two lease durations after every clock runs true again. Other clock faults never excuse anything.
          Not in the design yet
          Snapshots, garbage collection, and branches other than main. A commit object that was uploaded and never committed stays in the bucket.