Ownership

Copy Markdown View Source

For evaluators and users who want the mental model of how Fief derives ownership before writing code. Assumes the overview and guarantees.

Fief never stores a key→node map, and never gossips one. Ownership is derived from a single small table by a pure function every node computes locally:

owner(key) = table[hash(key)]

There is no CRDT to merge, no registry to replicate, no conflict to resolve after a partition — because there is nothing shared at the key granularity to conflict. This page walks the four moving parts: the hash into vnodes, the one authoritative table, the epoch-fenced writes that mutate it, and why the receiving node — not the sender — is the arbiter of truth. Then it explains the one thing Fief pointedly refuses to replicate.

Keys hash to vnodes

The keyspace is split into a fixed number of virtual nodes (vnodes) by a pure hash. A vnode is a partition of the keyspace; a key belongs to exactly one vnode for the life of the instance, and the assignment is deterministic — hash(key) returns the same vnode on every machine, every OTP release, and every Fief version. That determinism is not incidental: nodes disagreeing on where a key hashes is the double-ownership hazard, so the hash is pinned with frozen known-answer values, and the hasher module forms a cluster-wide compatibility fingerprint validated at join (a mismatch is fatal before the node touches shared state).

This hash-and-fingerprint machinery is shared substrate, not Fief.Key- specific: Fief.Hasher backs both first-class surfaces, and Fief.Cache fingerprints the hasher module at join exactly as Fief.Key does. The hasher seam, custom hashers, and the immutability of the hasher are covered in the key guide — see Keys are binaries rather than duplicated here.

Why a fixed layer of vnodes at all, instead of hashing keys straight to nodes? Because nodes come and go and keys must not: vnodes are the stable unit that gets assigned to nodes, so a rebalance moves a few thousand vnode assignments rather than rehashing millions of keys. The vnode count is the one irreversible choice — see instances for why, and tuning for how to size it.

Verified by:

  • test/fief/key_test.exs — describe "hashing (Fief.Hasher.Default, pinned)": known-answer values that may never change (for example vnode!(Default, "user:42", 1024, _) == 19) and determinism across inputs.
  • test/fief/cache_test.exs — describe "Fief.Hasher.vnode!/4 (Fief.Hasher.Default, pinned)": the same pinned hash, exercised from the second surface.

One authoritative table

The only shared coordination state at the ownership layer is the vnode→node assignment table: one row per vnode, naming its current owner. It is a few kilobytes regardless of key count, held in the arbiter (Postgres, in the default deployment), and versioned by a monotonically increasing epoch.

Every node caches this table locally and reconciles its owned set from it: when a vnode is assigned to a node, that node's runtime starts serving the vnode; when it is assigned away, the node stops. Ownership is thus a derived consequence of the table, computed the same way everywhere — not a fact pushed around and reconciled after the fact.

Verified by:

  • test/fief/vnode_test.exs — describe "assignment → agent lifecycle": a fresh assignment plus a refresh brings the vnode's runtime up on the assigned node and it begins serving; ownership follows the table.

Design notes: docs/design.md §4 (ownership is derived, not stored), §5.1 (the vnode-table contract: read_table / cas_assign / cas_settle).

Writes are epoch-fenced CAS

The table has exactly one writer discipline. Every mutation is a single- statement compare-and-swap conditioned on the expected epoch (and, for the rebalancer's writes, a monotonic leader term). Every successful write bumps the epoch — the epoch exists precisely to make the CAS safe, so there are no non-bumping writes to the table.

This is what lets Fief avoid barriers and distributed locks entirely. Any component acting on a stale view of the table fails loudly at the CAS — the write is rejected as stale rather than applied — instead of silently corrupting ownership. A momentarily-duplicated or deposed rebalancer cannot double-assign a vnode: its write carries an old term and the arbiter rejects it atomically with the compare. Correctness does not depend on there being one writer; it depends on the fence rejecting every writer whose view is behind.

Because each write is one short statement, every arbiter interaction is a sub- millisecond transaction, and the arbiter is off the message hot path — it is consulted for leases, membership, and rebalancing, never to route a message.

Design notes: docs/design.md §4 (the fenced-CAS arbiter), §5.1 (fencing-token validation: epoch and term monotonic, no stale-token write ever succeeds); docs/implementation.md §3 (cas_assign/cas_settle signatures, one statement per transaction).

Receivers hold truth; senders hold hints

A node's cached copy of the table is explicitly a routing hint, and may be stale without harm. The split that makes this safe:

  • A sender hashes the key, looks up the presumed owner in its cached table, and sends directly to that node. No sender-side bottleneck process, no synchronized table distribution.
  • The receiver — which authoritatively knows its own lease state and which vnodes it currently owns — validates every inbound message against its own truth before delivering it. A node that does not own the target vnode answers {:moved, epoch, delta} instead of processing anything; the sender patches its cache from the delta and retries at the corrected owner.

Validation is against ownership, not raw epoch equality: an epoch bumps on every table write anywhere in the cluster, so a message tagged with an old epoch is fine as long as the target vnode did not move in between. Rejecting on epoch mismatch alone would turn every rebalance into a cluster-wide retry storm proportional to total traffic rather than to moved traffic.

The consequence: convergence is a performance property, not a safety one. Every hint channel can be severed and the answers stay correct — just slower to settle. This is the mechanism behind guarantee 2, agreed ownership.

Verified by:

  • test/fief/vnode_test.exs — describe "ownership validation": a node that has observed a vnode move away answers {:moved, ...} and the implementation never sees the message; the stale-table window (an un-refreshed old owner still serving, safe because per-key authority transfers at handover) closes on the next observation; a fenced node whose lease died drops messages rather than serving them.
  • test/fief/router_test.exs — describe "call": the moved/retry loop patches a stale cache and lands on the true owner.

Design notes: docs/design.md §4 ("receivers hold truth; senders hold hints"), §5.4 (the router and the :moved protocol).

PIDs are never replicated

Key→PID mappings live in plain local state on the owning node and are never shared. Cross-node messages are addressed to {vnode, key} at a node, and the receiving node resolves the PID locally. A PID is the worst possible thing to replicate — it churns on every process restart, and a stale PID is a silent drop rather than a loud failure — so Fief simply does not.

This is also why the design scales in keys rather than nodes: per-key state is never replicated or agreed upon, so millions of keys cost only local memory on their owners, while the shared table stays kilobytes. The node count is the axis that is deliberately modest — see guarantee 4, scale in keys, not nodes for the scope condition (a full distribution mesh, roughly ≤ 50–60 nodes).

Design notes: docs/design.md §4 (why PIDs are never replicated), §2 (scale in keys), §5.5 (local Registry, resolve on the receiver).

What this means for you

  • You never build a key→node map, and you never wait for one to converge. You hash and send; if you guessed the owner wrong, the moved/retry loop corrects you transparently. The only thing shared is a kilobyte-scale table you never touch directly.
  • A stale local view is harmless, so you never coordinate around a rebalance. Routing on an out-of-date table costs at most one extra hop, not a wrong answer — receivers reject what they no longer own.
  • The vnode count you pick at instance creation is permanent, because keys hash to vnodes with a pinned function. Getting it right up front matters; changing it later is a migration, not a config change — see instances.
  • Fief moves and fences processes; it does not persist their state. Because PIDs and per-key state never leave their owning node, a node's death takes its keys' in-memory state with it. Durable truth is your job — see the key lifecycle and what Fief never promises.