Replication

A primary sends its replicas the writes that have reached its disk, and each applies them to a file of its own and serves reads from it.

A replica is a whole fenec-server: every read works on it, subscriptions included, from its own copy in memory, and a write gets 403. GET /_replication says which role a server has, so a client or a load balancer can tell a replica from the primary.

A fenecdb file is already a log: an image, then every write appended as a record. A replica is sent those records, whole and in order, and applies each the way the write path made it — the document, and the upkeep of every index on it — and appends it to its own file. Its file therefore ends as the primary's does, and a replica stopped and started again reopens where it was and asks only for what came after. The primary keeps the last 64 MiB of writes for this (--replication-buffer); a replica further behind than that is sent an image of the whole database instead, and follows write by write from there.

Only writes on the primary's disk are sent. A write enters the feed when it is appended and leaves it once an fsync has covered it, so a primary that crashes comes back holding every write any replica was sent, and a replica never has to be told to forget one. The price is latency, set by the primary's --sync: under always a write goes out right after its own fsync, under 250 up to 250 ms later. Under off nothing is on disk before shutdown, so a server with a replication token refuses to start with it.

Every write moves the change counter by one, on the primary and on each replica alike, so a replica's position is its own counter and a subscriber's cursor means the same change on either. A block — the writes of one statement, a /batch — is one record numbered by its last write, and is sent and applied whole: a replica never stands inside one. A replica of a replica is fed exactly as its primary was.

Numbers alone stop being enough once a history forks. A replica promoted after its primary died writes its own change 1 001; the old primary, or a second replica that had got further along, may hold a different 1 001. Streaming the new primary's 1 002 on top of that would go unnoticed. So each fork gets a fresh id and remembers the change where it left its parent, as PostgreSQL numbers its timelines, and a replica is continued only from a position the primary's own history passed through, as the table above shows.

The history lives in the file (record kind 8), and the first time a primary serves replicas it draws an id of its own — the root history is every database's, so it names none.

A replica is behind its primary by the time a write takes to reach it — 0.04 ms at the median under --sync always, up to the sync interval otherwise — so a client that writes on the primary and reads on a replica can read from before its own write. Over HTTP a write's answer names the change it left the database at, Fenec-Seq; a request sent to a replica with Fenec-After: <that number> is served once the replica holds it, and answered 504 with where the replica stands if it does not within the wait — never from before the write.

A change number names a write within one history. A promotion forks the history where the replica promoted stood: a write the old primary answered and the replica never got is lost, the new primary's next write takes its number, and a replica still following the old primary holds a change of that number — the lost write. So an answer of a database that has had a replica also names its history, Fenec-History: <term>-<id>, the term one more at each promotion; a read sent with it beside Fenec-After is served once the replica holds that change of that history — a replica on the old branch waits until it follows the new primary and takes its image. A primary asked for a position its history does not hold — the write lost — answers 504 at once, with its own seq and history, which a client takes as where it stands from then — over the position it sent that read after alone, and never an earlier term of the same lineage, which only a fenced old primary names. A history's lineage is the top half of its id: every promotion and restore keeps it, and a database made anew — a tenant deleted and made again under its name, starting again at term 1 — has another, whose position a client takes, its term lower or not.

The wait is 5 seconds unless Fenec-Wait gives it in milliseconds, 30 seconds at most, and a replica waits on the same Condvar its subscriptions do, so nothing polls. On a tenant node a wait takes one of the tenant's streams, but only once it must wait: a read after a write the node holds already takes none, as a tenant whose streams its own subscriptions fill still reads its writes. Writing the header costs the server nothing measurable; a client that parses every header, as Python's http.client does, reads one more.

Either way forks the history where the replica stands and turns writes on. A replica's file does not open any other way — started with neither flag, fenec-server refuses and says which to give — because a replica taking writes without a fork would continue its primary's history with writes the primary never made.

Making sure the old primary takes no more writes is the operator's part, as it is with PostgreSQL: nothing here fences it. Brought back, it rejoins under the new primary with --replica-of, and is sent an image if it wrote past the fork.

How it was measured: a primary killed with SIGKILL while one client writes to it as fast as it answers, the replica promoted half a second later, ten times per policy; counted are the writes the client was told succeeded that the promoted replica does not hold (make replica-bench, macOS, loopback).

Under 250 the loss is the policy's own: those writes were answered before any fsync and were not on the primary's disk either. Under always a write is answered after its fsync and once the stream to each replica has written it into its socket, which the kernel delivers after the process that wrote it is killed. Sent after the answer, as it was before, a write answered in the fraction of a millisecond before it was sent was lost: none of these ten failovers caught one, while a node of the SaaS example killed under eight writers lost one in 3 of 60 runs, and none in 120 since. A stream that has not sent a write within a second is not waited for until it catches up again, so a stalled replica costs the writes one wait. A machine that dies takes its sockets with it: this holds for a process killed, not for a power loss. No failover left the replica holding a write the client had not been answered for.

How it was measured: primary and replica in one process over loopback, each over its own file; lag is from a write's answer on the primary to the write being readable on the replica, over 1 000 writes.

A replica keeps up with a bulk load: 100 000 documents of 128 dimensions with an HNSW index, which the primary wrote in 23.4 s in statements of 1 000, were applied from the stream in 19.7 s — 5 088 writes a second, the graph built as they arrive. A new replica of that database sent it as an image — 58.3 MB, the graph in it — answered from it 0.17 s after it connected.

The primary keeps the writes in memory up to its buffer, and copies the image it sends; a replica holds the database in memory as a primary does. The replica's HNSW graph is built from the same vectors in the same order, but not in the same batches, so an approximate near can rank a close call the other way on the two; everything else answers identically.

The same stream written to a directory instead of applied is an archive: base images, and every write after them with the time the primary appended it. The fenec command line writes and reads one.

A restore takes the latest image at or before the point asked for and appends the archived writes after it up to there — a fenecdb file is an image and the writes after it, so that is the whole restore — then opens the result to check it, forks its history and checkpoints it. --to keeps every write the primary appended at or before that moment and stops at the first one after it; --to-change stops after that change. A statement writes each document as a change of its own, so a del of ten documents is ten changes.

The archive is fed as a replica is: only writes that were on the primary's disk, so none a crash took back, and a compact on the primary loses it nothing — the writes were archived before a compact folded them into an image. An archiver that falls further behind than the primary keeps writes for takes a new image and goes on from there; the archive then holds no write between the two images, and a restore to a point in that gap says so rather than inventing one. Restoring the 100 000 × 128 load above from an image and its 100 000 writes took 19.9 s, most of it building the graph for them, and the file then opened in 63 ms; to the load's middle, 7.8 s. A base image a day keeps a restore to a day of writes.

image-<change>-<time>.fenec   a base image: the database at that change
writes-<first change>.log      per record, the time it was appended and the record
history                        the history the archive is on

An archive takes images of its own: every --image-every (an hour unless given), once a write came after the last one, it opens its last image and the writes after it and adds an image of the database there — the primary is asked for nothing — named by the time of its last write, and the segment being written ends so that the writes before the image are in segments of their own. A restore then replays at most that much. With --keep, what no restore within that window needs goes after each image: the images before the newest one taken by the window's start, which a restore to that moment starts from, and the segments whose writes all came before the oldest image kept — never the one being written. fenec prune <dir> --keep 7d does the same once.

fenec verify <dir> reads the archive as a restore would: every image opens at the change its name says, the segments run on from the oldest image with no change missing, only the last segment may end in a record cut short, and a restore to the end opens. It prints from when to when the archive can restore, names any gap — changes in no segment between two images, where a restore to the end passes but a restore to a moment inside cannot — and exits 1 when no restore can be made.

A tenant's own stream (/t/<tenant>/_replication) is a connection and a thread on the node for as long as it runs, one of --max-connections, and it holds its tenant open the while. Archived that way, a node of a thousand tenants holds a thousand of each and every tenant open for good — and at the default of 100 connections it cannot be archived at all. fenec archive --tenants asks the node for POST /_replication/tenants instead, with the replication token: every tenant's writes over one stream, each message led by its tenant's name. Its body says where each archive under the root stands; the node says hello to every tenant it holds — where the archive goes on from, or an image where its place does not lead to the tenant's writes — and that every tenant the archive lists and the node does not hold is gone.

The stream sends a tenant's writes from its feed while it is open, and nothing while it is closed, whose file does not change. A tenant closes only once the stream has sent what its disk holds — closed with writes unsent, its feed would go with it and they would come again as an image — and is looked at again at the next pass, never waited for. Under --sync always a write waits for the stream as for a replica while the stream keeps up; whatever can keep it busy — reading or opening a closed tenant, waiting for a tenant's lock, which its longest write holds (a /batch, a compact under the lock), an image's snapshot and its sending, an archiver reading slower than the stream writes — it does held up, and no write waits for it then. One stream for every tenant held each tenant's next write for a second while it opened another one; each tenant's own stream holds up its own tenant alone. An image waits for its tenant's disk without holding up the stream — and is taken again, from the tenant as it is then, where the tenant closed and opened again meanwhile — and the node's syncer and a closing tenant wait for no stream at all, since no client's answer waits on them.

So the archive of a node is synchronous only while its stream keeps up, and under load it is not: a write answered while the stream was held up, or behind after an image, is on the node's disk and not yet in the archive. It is sent once the stream comes back to its tenant, or, where the stream fell behind the tenant's feed, as part of an image; if the node's disk is lost before that, the archive does not have it. A replica's own stream (/t/<tenant>/_replication) keeps a write's answer waiting for it, up to a second.

Which tenants have writes is told, not polled: a tenant's feed tells the stream as its writes reach the disk — with no stream connected a sync pays two loads, the same 13 ns a durable advance either way — and a tenant made, installed, deleted, promoted or made to follow tells it too; one released from under the stream is looked at again until it is gone or back. Where a closed tenant stands is known where it closed in the node's process, and read from its file otherwise — the first stream after the node starts: 1 001 tenants in 0.29–0.33 s, where an open, which fsyncs the file first, was 6.3 ms a tenant. A closed tenant the stream is told of is read again rather than taken where it closed, since a holder of its database — the @ttl sweeper — may have written it since; one with a sync log beside it, after the machine went down, is opened.

A tenant's archive is <root>/<tenant>/, written as fenec archive writes one; its segment file is open only while the tenant writes, so the archiver holds a descriptor a writing tenant, not a tenant. When the node says a tenant is gone — deleted, or moved to another node, whose own archiver takes it up from its image on the same history — the archive is kept as it stands and <root>/<tenant>/presence notes the time; a tenant that comes back is followed again and noted back, the time it was away a gap. The times are the node's clock, as its writes' are: gone is when the node deleted the tenant, though the stream was busy or the archiver away when it did — or, where the node does not know (it restarted since), when the stream saw it go — and back is when the node said hello to it again. A tenant deleted and made again while the stream was busy is noted gone at the delete before the new copy's hello; one deleted and made again while the archiver was away is heard of as the new copy alone, and the line it moves aside (below) is noted gone by that hello at the latest, so a moment between the delete and then restores the old copy. A tenant whose copy on the node no longer leads from its archive's place, at or before it — restored there to an earlier moment, or another tenant made under the name — would land its writes among changes of the same numbers: the line so far is moved aside to <root>/<tenant>.<history>/ and a new one begins. (fenec archive of one database refuses such a primary instead, and leaves its archive as it was.) A promotion's new history reaches the archive before the writes after it, so a promoted tenant's archive goes on without an image. <root>/archiving.lock keeps a second archiver off a root.

fenec restore --tenants <root> <dir> writes <dir>/<tenant>.fenec for each tenant the node held at --to — from the line of its history that began last by then, so a line moved aside answers for the time before the next began — or at each archive's end. A tenant the node said was gone then, deleted or living on another node, is passed over, and so is one archived only after it; one whose moment --keep let go of is refused, and the restore exits 1 — each line knows when it began, which the prune that lets its first image go writes down first (began). --to-change names one database's change, and is refused. fenec verify --tenants and fenec prune --tenants run on every line, those moved aside too, and verify names a gap an image alone ends.

Measured with make node-archive-bench: a node of 1 000 tenants of ten rows each and one of 64 MB, closed when idle, ten of them written ten times a second from before the archiver connected and for 20 s after, under --sync always, in turns, on this M1:

The archiver's process runs the bench's writers as well. A write's time under --sync always is the Mac's F_FULLFSYNC; a write waits for the node's stream as for a replica, and the stream sends within the fsync's noise. While the first images were taken no write waited for the node's stream; held up as a replica's stream is, it held every written tenant's next write for a second whenever it opened another tenant. A stream each held the writes up as images went out over a thousand sockets at once, the build before alike (p99 86–351 ms, at most 110–994). The node's stream takes a new archive's first images one tenant at a time, each tenant opened — an fsync — and its image written: about 15 s for the thousand and one, once, the 64 MB one among them. After the node restarted, the archiver connecting again, the stream said hello to all 1 001 tenants in 0.29–0.33 s, each read from its file rather than opened; a thousand streams opened every tenant again and held it.

Under --sync 250 (node_archive_passes: eight tenants written every 5 ms, eight more opened, written and closed in turn, one of 32 MB closed) the syncer's pass took 52 ms at the median beside the node's stream against 31–33 with none: the archiver writes the same disk, and the passes are its fsyncs and the node's together. Before the syncer and a close stopped waiting for streams, a stream busy with one tenant held a pass for a second a tenant, 5.06 s over five, and a close under its lock for 1.01 s. Against the build before, in turns: with no archiver the syncer's pass took 31.0–31.4 ms at the median and a close 3.6–3.9 ms, and with a stream each the pass 67–73 ms, as here; the writes with no archiver or a stream each as in the table.

fenecdb speaks no TLS, and S3, R2 and GCS speak only HTTPS, so an archive goes there the way any directory does: a sync tool beside the archiver.

Every file but the segment being written is written once: a segment is closed and fsynced before the next begins, and an image is written beside and renamed into place. A sync tool lists the directory and then copies each file as it stands, so the copy it leaves is the archive up to a moment, its last segment at most cut in a record's middle — which verify reports and a restore passes over. A test copies an archive a file at a time while writes and images go on, and every copy verifies and restores to a prefix of what the primary wrote. --delete, or rclone sync's own, carries a prune over to the copy; without it the copy keeps everything.

A copy in a bucket or on another disk is out of reach of the machine's disk encryption. With a key every file of an archive — its images, its segments, its history — and a backup file are sealed: encrypted and authenticated with ChaCha20-Poly1305 (RFC 8439), a random nonce a frame, each frame's place in the file and whether it is the last under its tag. A byte changed, a frame moved or dropped, a file cut short where it was sealed whole, or the wrong key, and the file is refused — never read as something else. A segment is sealed a frame for each batch of writes the primary sends, so a crash cuts off at most the frame being written, as it cut a record short before.

An archive is sealed or it is not; a file of the other kind in it is refused. FENEC_KEY_FILE names the key file too. Sealing and opening run at about 400 MB/s on one core, where writing the archive waits on the network and the disk. The database file itself stays plain: it is mapped and read where it lies, which encryption would take away — encrypt the disk it is on (LUKS, FileVault, an encrypted cloud volume).

All of them want Authorization: Bearer <replication token>, not the --http-token: the token is for replicas and for whoever promotes them. The status of a replica names its primary and says whether it is connected, how many writes it is behind the primary's disk, and how long ago it last heard from it; a primary's lists the replicas it is feeding and how far each has been sent.