How felixd works
This page follows one workload from the moment it is submitted to the moment a second node takes it over and an operator replays it. Each part says what happens and why it is built that way. Terms are defined in Terminology.
Two ideas carry everything. The first is that a workload is
deterministic: the same inputs give the same
outputs and the same state on any node. The second is that every write a node
makes to a workload’s streams is a publish_if
at the tail the node expects, so a node that is behind is refused instead of
interleaving with the node that took over.
What lives where
Section titled “What lives where”Everything is in one Felix tenant, in one namespace.
| Resource | Kind | Key or name | Holds | Written by |
|---|---|---|---|---|
workloads |
cache | workload id | the spec | felixd run, and the owner when the workload fails |
modules |
cache | sha256 of the module | the module’s bytes | felixd run |
leases |
cache, with a TTL | workload id | owner node id and epoch | agents, with cache_put_if |
epochs |
cache | workload id | the last epoch handed out, as a decimal number | agents, with cache_put_if |
nodes |
cache, with a TTL | node id | felixd version, max_workloads, workloads held |
each agent |
wl.<id>.out |
durable stream, one shard | output, claim, failure and rejection records | the lease holder, with publish_if |
|
wl.<id>.snap |
durable stream, one shard | snapshot chunks and manifests | the lease holder, with publish_if |
A workload’s input is any durable stream that exists before the workload is
submitted. It can be another workload’s .out stream.
felixd run creates the caches and the two streams through the control plane,
with three replicas and Quorum consistency unless --replication-factor says
otherwise. Agents never create streams. Both workload streams have one shard
because publish_if orders one shard only.
The spec
Section titled “The spec”A workload is a spec in the workloads cache, a JSON value with the fields
below.
| Field | Meaning |
|---|---|
module |
sha256 of the module in hex, the key in the modules cache |
input |
the stream the workload reads |
output |
wl.<id>.out |
snapshot_every |
a snapshot after this many inputs, 1000 by default |
snapshot_every_ms |
also a snapshot at the first input of each interval of this many milliseconds, absent unless set |
state |
running, stopped or failed |
limits |
fuel_per_call (50,000,000), max_memory_bytes (64 MiB) and snapshot_fuel (500,000,000), the defaults |
failure |
why the workload failed, present only when state is failed |
The limits live in the spec and not in node configuration, so every node runs the
workload under the same ones and fails it at the same step. felixd run writes
the spec last, after the module, the streams and the caches exist, so an agent
that sees the spec finds everything else.
Submitting work shows how to write and submit one.
Running felixd run again for the same id replaces the spec, and a running
workload restarts under the new one. A new module or a new input is refused
once the output or snapshot stream holds a record, because the next owner would
find the streams diverged from what the new code produces. New code goes under
a new id.
Claiming a workload
Section titled “Claiming a workload”Every agent watches the workloads cache. For each spec in state running it
waits until the workload’s lease looks free, then tries to claim it.
Placement is first claim wins. Before a claim an agent waits a random time of
up to --claim-delay-ms (1 second by default), so the first agent to see a
workload does not take everything. An agent that already holds --max-workloads
(64 by default) claims nothing more until one of its workloads ends. The agent
sees placement through one trait, so a smarter policy can replace it without
touching the lease code. nodes records which agents are up and how full they
are, but nothing reads it to decide yet.
The claim is a conditional put. The agent writes a lease with
cache_put_if on “absent”, with the lease TTL (10 seconds by default, at least
2 seconds). The broker grants it only once it counts the previous lease as
expired or deleted. If the answer to a claim is lost, the agent does not adopt
the lease. It expires unused and the workload waits one TTL.
The winner then takes an epoch. The epoch is one more than the larger of the
last number in the epochs cache and the epochs on the last records of the
workload’s output and snapshot streams. The claimer writes it to epochs with
cache_put_if at the version it read, then rewrites the lease to carry the
epoch, again with cache_put_if, and only then runs anything. A claimer that
was frozen after winning, and lost its lease meanwhile, fails one of the two
writes and gives up. The counter makes epochs unique and growing. Taking the
maximum with the streams keeps a new epoch above everything already written even
if the epochs cache is recreated.
The holder renews every third of the TTL, with cache_put_if at the version
it last wrote. A refused renewal means the lease is gone and the agent stops the
workload at once. A renewal whose answer is lost is read back. The agent also
stops on its own if two thirds of the TTL have passed, by a monotonic clock,
since it sent its last successful renewal. That is a third of a TTL before any
other node can claim, which covers a renewal’s round trip and the scheduler’s
delay.
Takeover does not depend on an expiry event. Agents watch leases with
retained values and know when each lease expires. After that time each tries a
claim, waiting at most one TTL between tries, so a missed event or a slow local
clock costs at most a TTL. A clock ahead of the broker’s costs a refused claim,
never a second owner, because only the broker decides that a lease is gone.
Restart and shutdown. An agent never adopts a lease it finds under its own
node id. A restarted agent waits for its old leases to expire, so two processes
configured with the same id cannot both believe they hold a workload. On Ctrl-C
or SIGTERM an agent deletes its leases with cache_delete_if, waiting up to two
seconds for its workloads to let go, so other nodes can claim at once.
Epochs and the fence
Section titled “Epochs and the fence”The lease is not what keeps the output correct. Lease exclusivity depends on
clocks: the broker leading the leases shard decides when a TTL has passed, and
a leader whose clock jumps forward expires leases early. Two agents can
therefore each believe they hold the same workload for a while. What keeps the
output right is a fence on the output stream itself.
Before a new owner reads anything to resume from, it appends a claim record
carrying its epoch to wl.<id>.out, with publish_if at the output tail it read
along with the epoch floor. After that:
- If a stale owner wakes up and writes, its write is refused, because the claim moved the tail past what the stale owner expects. The records it finds there include the claim, from a later epoch, so it stops without writing anything more. This holds even when the new owner has written no output, for example because its input is idle.
- If the stale owner wrote before the claim landed, the claim is refused and lands after those outputs. The new owner then resumes past them like any others. Because the workload is deterministic they are what it would have written.
Writing the claim at the tail read with the floor, not at a fresh tail, matters: a claimer frozen between taking its epoch and writing its claim would otherwise land its claim after a later owner’s.
sequenceDiagram
participant A as Node A
participant L as leases and epochs caches
participant B as Node B
participant O as wl.w.out
participant S as wl.w.snap
participant I as input stream
A->>L: renew lease
Note over A: node A freezes
Note over L: the lease expires
B->>L: cache_put_if absent, with TTL
B->>L: take epoch 8, rewrite the lease with it
B->>O: publish_if claim record, epoch 8, at the tail
B->>S: read the latest snapshot manifest
B->>O: read the last output, compute the fold
B->>S: read the chunks and restore them
B->>I: subscribe_from the next input
B->>O: publish_if outputs at the tail
Note over A: node A wakes up
A->>O: publish_if output, epoch 7, at the old tail
O-->>A: refused, the tail has moved
A->>O: read from the tail it expected
O-->>A: a claim from epoch 8
Note over A: node A stops without writing
One step, and exactly-once output
Section titled “One step, and exactly-once output”For each input record the owner runs the workload’s step and gets back outputs
or a rejection. Each output becomes a record on wl.<id>.out with a small
header: the input offset that produced it, its index among that step’s
outputs, and the owner’s epoch. Its name and key come from the workload. A
rejection is written as that input’s only output, at index 0.
The owner appends all of one step’s records as one batch with publish_if at
the tail it expects. If the write is acknowledged, it moves its tail. If it is
refused, or the answer is lost, the owner never retries blindly. It reads the
stream from the offset it expected and decides on what is there:
- Its own records, or an earlier owner’s identical ones: the write landed. It skips them and writes the rest.
- A record from a later epoch: someone else owns the workload. It stops and writes nothing more. A later epoch wins over everything else, including identical records, because otherwise a stale owner would skip the new owner’s records and write after them, and the two would take turns on the stream.
- A failure record for its spec: the workload has failed, and it stops.
- Nothing: the write did not land, or has not yet. It sends the batch again at the same offset. If the first lands after all, one of the two is refused and the next read finds it.
A batch is not all or nothing. Felix ships a Quorum stream’s records to
followers by bytes, so a follower promoted mid-batch can keep part of a batch.
The writer gets an error. felixd relies on two things. An owner whose append
fails reads the tail it expected and skips the records of its batch that it
finds there. An owner that dies leaves the prefix to the next one: the resume
skips outputs by input offset and index, not by whole inputs, so the next owner
runs that step again, drops the outputs already on the stream and writes the
rest. A resume can start in the middle of a step. Whether Felix should make a
conditional batch all or nothing is
GetFelix/felix#1630; see also
what atomic covers.
A step whose outputs total more than 8 MiB cannot be written in one
publish_if and fails the workload.
Snapshots
Section titled “Snapshots”A snapshot is the workload’s state saved so that a new owner does not have to run the whole input again.
When one is taken. After every snapshot_every inputs (1000 by default), and
with snapshot_every_ms also at the first input of each interval of that
length. An interval is counted from the Unix epoch, and an input starts a new one
when its append time falls in a later interval than the previous input’s. The
time is the broker’s stamp on the input record, not the node’s clock, so every
node picks the same inputs and a slow input still gets snapshots. Taking a
snapshot for either reason restarts the count of inputs.
Never while replaying. After a takeover the owner may run inputs whose outputs are already on the stream. During that time the output stream’s tail is ahead of the workload’s state, so a snapshot would claim outputs it does not cover, and an owner that crashed right after writing it would resume past them and write them again. The owner takes no snapshot until it has passed the last output on the stream.
Chunks and a manifest. The workload returns its state as a list of chunks,
each at most 4 MiB, at most 65,536 of them. The host takes the sha256 of each
chunk and compares it with the previous snapshot’s manifest, so a chunk that did
not change is not written again. New chunks go to wl.<id>.snap as chunk
records, as many to one publish_if as fit in 8 MiB. The manifest goes last,
in the same write as the last chunks when it fits. It records the input offset the
state includes, the output stream’s next offset at that moment, and for each chunk
its sha256 and the offset on .snap of a record holding it. Only a manifest makes
a snapshot. Chunks that land without one, after a crash or a partial batch, are
never read. A manifest may point at chunk records written for an earlier
snapshot.
The same fence. Every snapshot record carries the writer’s epoch and is
written with publish_if at the snapshot stream’s tail. A refused write rereads
the records past that tail. A record from a later epoch means this owner is
superseded and stops. Records from its own epoch or earlier are a stale owner’s
that landed first, which determinism makes correct, so it writes after them.
The snapshot stream has no claim record of its own, so a stale owner can still
append a snapshot after a new owner’s claim until the new owner writes one. That
snapshot is of a correct state.
Running out of fuel. A snapshot, every snapshot and snapshot-chunk call
together, runs under snapshot_fuel, separate from the fuel a step gets. A
snapshot that runs out is abandoned, not a failure. Nothing is written, the
previous snapshot stays current, the agent logs it and counts it, and it will not
try again until snapshot_every more inputs have passed. The trap leaves the
instance unusable, so the agent drops it and resumes from the previous snapshot.
Fuel is metered deterministically, so every node skips the same snapshots. A
restore that runs out of fuel is different, and is described under
Resume.
flowchart TD
A["An input has been stepped and its outputs are written"] --> B{"snapshot_every inputs, or a new snapshot_every_ms interval?"}
B -- no --> Z["Next input"]
B -- yes --> C{"Still replaying outputs that are already on the stream?"}
C -- yes --> Z
C -- no --> D["Call snapshot and snapshot-chunk under snapshot_fuel"]
D --> E{"Out of fuel?"}
E -- yes --> F["Write nothing, keep the previous snapshot, wait snapshot_every more inputs, resume from the previous snapshot"]
E -- no --> G["Hash each chunk and drop the ones the previous manifest holds"]
G --> H["publish_if the new chunks, then the manifest, at the snapshot tail"]
H --> I{"Refused?"}
I -- no --> Z
I -- "later epoch found" --> J["Superseded, stop"]
I -- "earlier epoch found" --> H
Resume
Section titled “Resume”A new owner picks a workload up in this order.
- Append the claim record, as above.
- Read the latest manifest on
wl.<id>.snap, passing over chunk records, and stop if its last record is from a later epoch than the owner’s own. No chunk is read yet. - Read the last output or rejection record on
wl.<id>.out, passing over claims and failures, and stop if it is from a later epoch. - Compute the fold: which input offset to subscribe from (the snapshot’s input offset plus one, or 0 with no snapshot), and which outputs the stream already holds, those at or before the last record’s input offset and index, starting at the snapshot’s output tail. The fold’s checks below run here, before any chunk is read.
- With a snapshot, restore it: read each chunk at the offset the manifest
names, check its sha256, and hand the chunks to
restoreon a fresh instance. A chunk that does not match its hash fails the workload. Without one the workload starts from its initial state. - Subscribe to the input with
subscribe_from. For inputs the stream already has outputs for, runstep, compare each output with the record in its place, and drop it. From the first missing output on, write.
The fold refuses a state no correct owner could have produced: an output stream shorter than the snapshot expects, or whose newest output belongs to an input the snapshot already covers. A replayed output that differs from the record in its place also fails the workload, because it means the workload is not deterministic or something else wrote the stream.
The fold compares the last output’s offset, never the stream’s tail, with the snapshot’s output tail. The tail can be past the last output because claims, and the generation-start record Felix appends when a broker starts leading a shard, take offsets that hold no output.
flowchart TD
A["Claim record appended"] --> B["Read the latest snapshot manifest"]
B --> F["Read the last output record on wl.id.out"]
F --> G["Fold: next input, which outputs are already written, consistency checks"]
G --> C{"A snapshot?"}
C -- yes --> D["Read its chunks, check each sha256, restore on a fresh instance"]
C -- no --> E["Start from the initial state at input 0"]
D --> H["subscribe_from the next input"]
E --> H
H --> I{"Output already on the stream?"}
I -- yes --> J["Run step, compare with the record in its place, drop the output"]
I -- no --> K["Run step, publish_if the output"]
J --> H
K --> H
Dropped inputs. Felix drops records for a slow subscriber by default, and a jump in offsets is how that shows. Offsets that hold no event jump too, so when the next input offset is past the expected one, the owner reads the range in between and runs whatever records it finds first. It never steps past a missing record. A read that makes no progress is tried again and is an error after 20 seconds.
A restore that runs out of fuel puts the workload in the
needs-operator state, not
failed: the limit can be raised and the workload resumed. The holder writes a
needs-operator record to the output stream and releases the lease, and
felixd ps shows the reason. Raising
--snapshot-fuel with felixd run for the same id writes a new spec, and the
agent restarts the workload under it.
When a workload fails
Section titled “When a workload fails”A workload fails when its step traps, runs out of fuel, returns poison,
breaks the contract, or when its streams are in a state no node can resume from
(a record that does not decode, a replayed output that differs, a chunk with the
wrong hash). It would fail the same way on any node, so it is not retried.
Only the holder fails a workload, and the failure is fenced like an output. The
holder first renews its lease and gives up if that is refused. Then it appends a
failure record to the output stream with publish_if at the tail it just
read, unless the last record there is from a later epoch. The record names the
spec version and the reason. Only after it lands does the holder write failed
and the reason into the spec, with cache_put_if on that version so a later
edit is not overwritten. A node frozen after its renewal while another took over
cannot fail the workload the other now runs, because its append is refused. An
owner that finds a failure record for its own spec version while claiming writes
failed into the spec instead of running, which covers a holder that crashed
between the two writes. A failure record under an older spec version is from a
run before felixd run wrote the spec again, and is passed over.
A failed workload stays failed until felixd run writes a new spec for it.
A module built against contract 0.1 is a different case. No node claims the workload and nothing is marked failed. The workload is recorded once on its output stream as needing an operator, and agents leave it alone until its spec changes. A module built against a contract version newer than the node knows is treated the same way.
Replay
Section titled “Replay”felixd replay rebuilds a workload’s state at a past point. It takes no lease and
writes nothing.
felixd replay --id <workload> --to <offset or time>:
- Turns a time into an input offset with
offset_for_time. The state as of a time includes every input appended before it. An offset includes that input. - Picks the snapshot with the highest input offset at or before that point and restores it on a fresh instance, under the limits in the spec. Without one it starts from the initial state.
- Range-reads the inputs after the snapshot up to the target, runs
stepon each, and prints whatinspectreturns.
It uses the same fold as a failover, so a replay lands on the state the live workload had.
--diff replays a range (--from, --to, by default every input with a recorded
output) and compares each output it produces with the one on the stream, by input
offset, index, name, key and the sha256 of the payload. It stops at the first
divergence and reports the input offset, the record’s epoch, the node its epoch’s
claim names, and both digests, and the command exits with 1. That checks
determinism. CI runs it on every example workload after a takeover.
--module <hash> runs a different module from the modules cache over the
recorded inputs instead, from its initial state, because the snapshots hold the
old version’s state. With --diff it shows where the new version’s outputs
differ from what is recorded, which checks an upgrade before it goes live. Without
--diff it prints the new version’s state.
Until Felix can report a stream’s tail to a reader
(Felix #1621), replay needs
publish grants on the streams it reads, as check does.
Checking
Section titled “Checking”felixd check replays each workload’s module over its whole input, from the
initial state, and lines the outputs it produces up with the records on the
output stream by their headers. It reports:
- a gap: a replayed output missing from the stream while a later one is there;
- a duplicate: a second record for the same input offset and index;
- a record out of order;
- an epoch regression: a record whose epoch is below an earlier record’s;
- a record that differs from the replay, one the replay did not produce, or one that does not decode;
- a snapshot whose output tail does not split the output stream at its input offset, which would make a resume skip or repeat outputs.
Claims hold no output, so only their epochs are checked. With --complete it
also reports outputs missing from the end of the stream, for when the workloads
should have caught up. It exits with 1 if it finds anything and writes nothing.
Why the guarantees hold
Section titled “Why the guarantees hold”The safety argument has two layers.
The fence alone guarantees that nothing from a lower epoch lands after a claim, so the epochs on the stream never decrease and two owners never take turns.
Determinism adds that what a stale owner wrote before the claim equals what the new owner would have written, so skipping it is correct.
Determinism is enforced, not requested. The runtime refuses a component that
imports anything, so a workload has no clock, randomness, files or network, and
anything from outside arrives as an input record. NaN bit patterns are
canonicalized and relaxed SIMD is off. Fuel, memory, the Wasm stack, and the
number of tables, instances and memories are limited identically on every node.
Every field of a step’s input is a function of the input streams, the merge log
and the spec, so a live step, a resume, check and replay pass identical values.
That includes the publisher of a record, which the host reads from the stored record
and never from the node it runs on.
What breaks determinism:
- A different felixd build. Where fuel runs out and where the stack overflows depend on the code wasmtime generates, so they can move between versions. Every node must run the same felixd build. Recording the build in the spec is an open question (#62).
- A different machine architecture, possibly. Stack depth can depend on the instruction set. The stack size is fixed, but a cluster that mixes architectures is not covered yet (#62).
- A changed module or input under a workload that already has output.
felixd runrefuses it. A spec written to the cache by other means is not checked, and the workload fails with the divergence the next time it resumes. - A workload that is not a pure function of its inputs. The sandbox removes
the sources it can. A bug that still makes a workload behave differently on a
second run shows up as a divergence in
felixd replay --diffandfelixd check, or fails the workload on resume.
A workload with several inputs steps their records in an order the lease holder
chose, which is not a function of the inputs. The holder appends that order to the
workload’s merge log, wl.<id>.merge, before it steps anything, fenced like the
output stream. A new owner, a replay and felixd check read the log and step the
same records in the same order. An effect’s response, which would be a recorded
input too, does not exist yet.
The model in specs/ checks the lease, epoch, claim, snapshot and failure paths
with TLC, in several configurations that each turn one mechanism off and must
find the matching violation. It states seven invariants, including that the
output records are a prefix of the deterministic outputs with no duplicate and no
gap, that epochs never decrease, and that no owner’s writes interleave with an
earlier epoch’s after it has begun. Its
description lists
what it leaves out.
Where to read more
Section titled “Where to read more”- The workload contract for what a step receives and may return.
- Record formats for the bytes.
- Running felixd for the commands.
- The full design, which also covers what is not built.
