walknot
A knot based on walgit / s3 compare and swap that supports HA and Kubernetes
Star 4
Fork 0
Watch
walknot docs DESIGN.md
10 kB · 184 lines
Markdown
at master

walknot design #

walknot is knot2 — Tangled's git + atproto knot — with its storage rebuilt on the design of walgit: an S3 bucket is the only source of truth, and every pod's disk is a disposable cache. It runs as N interchangeable replicas on Kubernetes.

Upstream: tangled.org/core @ ab1baed311194dcbef9aaac1131f81ce2cc94671 (knot2 v1.20.0). See UPSTREAM.md for what was imported and how to port upstream changes.

Goals #

  1. Drop-in knot. Same XRPC surface, git transports (HTTP + SSH), firehose, record and COB formats as knot2. The Tangled appview, knotmirror, hydrant and spindle cannot tell the difference.
  2. Bucket is the truth. Every acknowledged write (push, record, COB, chain commit, setting) is durable in the bucket before the client hears "ok". Wiping every pod loses nothing but warmth.
  3. N replicas, no coordinator. Any pod serves any request. Coordination is through object-store primitives only (conditional PUT = compare-and-swap, create-if-absent), plus an optional Redis for things that are allowed to be lost (caches, fan-out).
  4. Any S3-compatible store that implements conditional writes (If-None-Match: * and If-Match: <etag> on PutObject): AWS S3, R2, MinIO, Ceph RGW, rustfs, Garage, … walknot probes this at boot and refuses to start on a store that silently ignores the preconditions.

Non-goals (for now) #

Repositories larger than a pod's disk (walgit's remote range reader), packfile-URI delivery, a filesystem store backend, GCS.

Bucket layout #

Everything lives under one configurable prefix:

repos/<shard>/                     one directory per repository (shard = knot2's DID sharding)
  manifest.json                    the commit point; rewritten with compare-and-swap
  log/<seq:016x>-<id>.json         immutable WAL entries (create-if-absent)
  checkpoints/<seq:016x>-<id>.json.zst   every ref at a seq
  packs/<pack-stem>.pack|.idx      immutable, named by pack checksum
  files/<sha256>                   sidecar file contents, content addressed
leases/repo/<shard>.json           per-repository write lease (CAS, TTL)
leases/leader.json                 knot-wide singleton lease
leases/pods/<pod>.json             each replica's liveness lease
lfs/objects/<pool>/<shard>/aa/bb/<oid>   LFS + attachment objects
lfs/touched/…                      touch markers (recency for garbage collection)
outbox/<pod>.json                  each replica's spindle notification queue
knot/sealed-keys                   the sealed key store (encrypted with KNOT_MASTER_KEY)
knot/ssh-host-key.sealed           the SSH host key, sealed with KNOT_MASTER_KEY

Manifest #

Small; rewritten on every commit with If-Match on its ETag (If-None-Match: * on create). It holds: format version, object format, head_seq, the live pack set, the checkpoint pointer, the symbolic HEAD, repository config (hideRefs, blobPackfileUri, remote.origin.url), sidecar files (import/handover state, outbox), and a deleted tombstone.

Log entries #

One entry per commit, written create-if-absent at log/<seq> before the manifest CAS that makes it visible. An entry carries the ref edits (name, old, new; symbolic HEAD changes), packs added/removed, config/sidecar changes and provenance (pod, actor, time). Readers fold checkpoint + log[checkpoint.seq+1 ..= head_seq]. An orphan entry (written, then lost the CAS) is overwritten by nobody (create-if-absent), and is never referenced by a manifest — the writer deletes it and retries at the next seq.

Commit protocol (writer) #

1. sync(strict)            – conditional GET of the manifest; apply anything new
2. validate                – every ref edit's `old` must equal the durable value
3. upload packs            – new local objects (pushed pack, or loose objects packed)
4. PUT log/<head_seq+1>    – If-None-Match: *
5. PUT manifest            – If-Match: <etag>   ← linearization point
6. apply locally           – refs/HEAD/config in the local cache repository

A failed or ambiguous swap is resolved by re-reading the manifest, never by guessing: the manifest lists the last 256 committed (seq, id) pairs, so a writer whose response was lost (or whose client retried a swap that had already succeeded) can see its own entry. If the manifest moved on without it, the attempt can never land: re-sync, re-validate, retry at the next seq (bounded). If the manifest is still at our base, the same swap is sent again. If the store cannot be read at all, the write fails with CommitUnknown.

A commit packs only the loose objects reachable from the refs it writes (the walk stops at packs, which are durable or published by the same commit), so an abandoned attempt's objects are never published. Once a dozen small packs accumulate, they are folded into one and published as a single add-and-retire commit.

Read protocol #

Every Layout::open does a conditional GET manifest.json (If-None-Match: <etag>, optionally skipped within wal.freshness_ms). A 304 serves the local cache. A 200 folds the new entries into the local bare repository: download missing packs (.idx last), rewrite packed-refs + HEAD + config, drop loose refs, bump the ref-advertisement generation. Superseded packs are removed only after a grace period so readers holding an open handle are not broken.

Concurrency: one writer per repository, by a lease that moves #

knot2 serializes writes per repository with in-process locks (Repo::with_ref_lock, CobLocks) and keeps in-memory projections (knot-index) that multi-step writes rely on (issue/PR numbering, ACL checks). walknot keeps that code correct across pods by making those lock points also take a bucket lease for the repository:

  • The lease is per pod and re-entrant; the in-process mutex still serializes within a pod.
  • On acquire, the pod strictly syncs the repository and refreshes the repository's index projections, so in-memory state is current while it is the writer.
  • The lease is renewed while held and released after a short idle linger, so it moves to whichever pod needs to write next. A pod that wants a held lease waits (bounded exponential backoff) for release or expiry.
  • The manifest CAS is the safety net: a pod that lost its lease (GC pause, partition) cannot commit over someone else's write — its old values no longer validate.

The meta repository (the knot's own DID: members, blocklist, registry, PLC queue, outbox) is just another repository with its own lease.

The leader lease elects one pod to run singleton background work: maintenance and compaction, the PLC sweeper, the spindle outbox drain, import and handover workers, the keep/grant sweeps, boot-time surface materialization, foster GC, crawler pings and persisting the firehose floor.

Firehose across pods #

subscribeRepos cursors are unix-microsecond sequence numbers, strictly increasing, and a subscriber must never see seq n+1 before n is settled. knot2 enforces this inside one process (knot-events::EventLog: reserve → fulfil, stable head = min pending − 1).

  • Single pod, no Redis: unchanged.
  • Multiple pods (Redis required): reservation and settlement move into Redis Lua scripts — reserve returns max(now, last+1, floor+1) and records a pending entry with a deadline; fulfil stages the frame and drains every staged frame below the lowest pending reservation into a Redis Stream, in order. Each pod tails the stream into its local ring, from which its subscribers are served exactly as before. Commit frames are durable in the repositories' atproto chains, so a Redis loss only shortens the replay window of non-commit frames — the same guarantee knot2's bounded ring gives today.

What Redis is (and is not) used for #

Optional for one pod, required for several. Only state that may be lost: firehose sequencing and fan-out, single-use jti replay protection, rate limits, the SSH-key cache, invite codes and key reservations, index invalidation notifications. Durable truth never lives in Redis.

Secrets #

KNOT_MASTER_KEY is the only secret. The sealed key store and the SSH host key are kept sealed in the bucket, created with create-if-absent so that N pods booting at once converge on one knot identity instead of minting N.

Other knot-wide state #

  • Sidecar files (import, handover, keep-sweep state) are manifest files: read without fetching packs, written as WAL commits. Boot-time recovery scans iterate the index rather than the (cache) directory tree; an import's fetching replica is recorded so recovery never fails a fetch another live replica is running.
  • The spindle outbox is per replica (outbox/<pod>.json): the replica that takes a push delivers its notifications and prints the CI reply. The leader adopts the outboxes of replicas whose liveness lease lapsed.
  • LFS keeps every object in the bucket; the local tree is a write-through cache trimmed by age. Garbage collection uses upload time or the latest touch marker.
  • The in-memory index drops a repository's projections when a sync brings in another replica's writes, revalidates repositories before trusting cached collaborators, and each replica polls the meta repository to rebuild knot-wide projections.

Testing #

  • Store contract suite — every guarantee walknot needs from a store (CAS on create and update, conditional GET, listing, deletion) — run against the in-memory store and, when WALKNOT_TEST_S3_* is set, a real S3-compatible store (MinIO in CI).
  • Fault injection — a store wrapper that fails, delays, or performs-then-errors any operation, driving the commit protocol through every ambiguous outcome.
  • Concurrency — many writers on one bucket (threads and processes), asserting linearizability of the ref history and that no acknowledged write is lost.
  • Equivalence — knot-sim seeds run on local storage and on the bucket must produce identical trace digests.
  • Upstream suites — knot2's unit/integration tests and Go interop tests, run with the bucket backend.
  • Cluster — a kind cluster with MinIO, Redis and 3 replicas running the interop suite while pods are killed.