ReplicaIdtypetype ReplicaId = Brand<string, "anyfs replica id">;The identity of one copy of a database: 32 lower case hexadecimal digits, random, never reused. Made only by parseReplicaId.
What a merge is made of, as types. The source of truth of a merged store is a set of immutable version rows: each write or delete of a path is a new row, with an identity that is a UUID version 7 made by a hybrid clock (so that ids made by one replica never go backwards, and ids of all replicas sort by time), the replica that made it and its number in that replica's rows, the version it replaced, and a digest of all of it (so that a row is its own checksum). The bytes of a put are in a blob named by their SHA-256. Two stores merge by taking the union of their rows and blobs; what a path holds now is a function of the rows alone. Each identity is made only by its parser, so that a text that is not one cannot be a replica or a version.
import { parseReplicaId, parseVersionId } from "./merge.ts";
const r = parseReplicaId("0123456789abcdef0123456789abcdef");
const v = parseVersionId("018f3a6e-7c00-7000-8123-456789abcdef");
r.kind === "ok" && v.kind === "ok"; // trueReplicaIdtypetype ReplicaId = Brand<string, "anyfs replica id">;The identity of one copy of a database: 32 lower case hexadecimal digits, random, never reused. Made only by parseReplicaId.
parseReplicaIdfunctionfunction parseReplicaId(text: string): Result<ReplicaId, string>A replica identity from text, or why it is not one.
replicaIdOfBytesfunctionfunction replicaIdOfBytes(bytes: Uint8Array<ArrayBufferLike>): Result<ReplicaId, string>A replica identity from 16 random bytes.
VersionIdtypetype VersionId = Brand<string, "anyfs version id">;The identity of one version of a path: a UUID version 7 as 36 lower case characters. Made only by parseVersionId or by the hybrid clock. Ids sort as text in the order they were made.
parseVersionIdfunctionfunction parseVersionId(text: string): Result<VersionId, string>A version identity from text, or why it is not one.
MAX_ID_MSconstno test imports itconst MAX_ID_MS: numberThe largest time an id holds: 48 bits of milliseconds.
MAX_ID_COUNTERconstno test imports itconst MAX_ID_COUNTER: 4095The largest counter of an id: 12 bits.
IdTimetypetype IdTime = { readonly ms: number; readonly counter: number };The time of an id: the milliseconds and the counter that orders ids of one millisecond.
ID_RANDOM_BYTESconstno test imports itconst ID_RANDOM_BYTES: 8The bytes an id takes for its random part: 62 bits are used, from 8 bytes.
MAX_COUNTER_SEEDconstconst MAX_COUNTER_SEED: 2047The largest counter seed: the counter of a new millisecond starts at a random number below this, so that its top bit is a guard against the counter rolling over (RFC 9562 section 6.2).
randomIdBytesfunctionfunction randomIdBytes(length?: number): Uint8Array<ArrayBufferLike>Random bytes from the CSPRNG of the runtime (RFC 9562 section 6.9 and 8).
randomCounterSeedfunctionfunction randomCounterSeed(): numberA counter seed from the CSPRNG: a number from 0 to MAX_COUNTER_SEED.
makeVersionIdfunctionfunction makeVersionId(time: IdTime, random?: Uint8Array<ArrayBufferLike>): VersionIdAn id from its time: a UUID version 7 as RFC 9562 section 5.7 lays it out, 48 bits of milliseconds, the version 0111, rand_a of 12 bits that hold the counter (section 6.2, method 1), the variant 10 and rand_b of 62 bits that are random for each id, from random where given (the first 8 bytes; a missing byte is zero) and from the CSPRNG where not. The id holds nothing of the replica that made it: the replica is the field of the row. Two ids of one replica differ by their time and counter, and ids of two replicas at one time differ by their 62 random bits.
timeOfIdfunctionfunction timeOfId(id: VersionId): IdTimeThe time of an id.
compareTimefunctionfunction compareTime(a: IdTime, b: IdTime): numberThe order of two times: the milliseconds and then the counter.
VersionVectortypeno test imports ittype VersionVector = { readonly [replica: string]: number };What a replica has: for each replica, the number of the last row it holds with all the rows before it of that replica (the rows of a replica are numbered from 1 with none missing). Keys are replica ids.
VERSION_KINDSconstno test imports itconst VERSION_KINDS: readonly ["put", "tombstone"]The kinds of a version: a put holds a blob, a tombstone says the path is not there.
VersionKindtypeno test imports ittype VersionKind = (typeof VERSION_KINDS)[number];One kind of version.
Versiontypetype Version = {
readonly id: VersionId;
readonly replica: ReplicaId;
readonly seq: number;
readonly path: string;
readonly parent: VersionId | null;
readonly merged: readonly VersionId[];
readonly kind: VersionKind;
readonly blob: string | null;
readonly sum: string;
};A version row: immutable, and its own checksum. parent is the version the writer replaced, null for the first of a path; merged holds the other versions the writer saw at the head of the path and replaced as well, empty where there were none. sum is the SHA-256 of the canonical text of every other field. The primary key of the row is id with sum, so that the same row from two databases is one row, and a row with the same id and another sum is a finding.
DELTA_FORMATconstno test imports itconst DELTA_FORMAT: 1The format of a delta on the wire: the only one so far.
BlobWiretypeno test imports ittype BlobWire = { readonly sha: string; readonly bytes: string };The bytes of a blob on the wire: base64.
Deltatypetype Delta = {
readonly format: typeof DELTA_FORMAT;
readonly origin: ReplicaId;
readonly versions: readonly Version[];
readonly blobs: readonly BlobWire[];
/** What a signing replica says of the identity of the delta, where it signs. */
readonly signature?: string;
};A delta: version rows and the blobs they name that a replica holds, that another takes. It is immutable and its identity is the SHA-256 of its canonical text, so that it can be kept in any store and applied twice with the effect of once. A delta is applied whole or not at all: where a row's parent or a put's blob is neither in the delta nor held, the delta waits. A SQL dump of the rows is a delta in another encoding.
SIGNATURE_VERDICTSconstno test imports itconst SIGNATURE_VERDICTS: readonly ["ok", "bad-signature", "unknown-key"]What a verifier says of a signature: it holds, it does not hold for the key it names, or no key of that replica is known for it at that time.
SignatureVerdicttypeno test imports ittype SignatureVerdict = (typeof SIGNATURE_VERDICTS)[number];One verdict of a verifier.
Trusttypetype Trust =
| { readonly kind: "open" }
| { readonly kind: "allowlist"; readonly replicas: ReadonlySet<ReplicaId> }… (623 characters)type Trust =
| { readonly kind: "open" }
| { readonly kind: "allowlist"; readonly replicas: ReadonlySet<ReplicaId> }
| {
readonly kind: "signed";
readonly replicas?: ReadonlySet<ReplicaId>;
/** The replicas whose keys the verifier knows: a database that cannot check a signature itself (a raw SQL import) still refuses rows of any other replica. */
readonly signers?: ReadonlySet<ReplicaId>;
readonly verify: (id: string, signature: string, origin: ReplicaId, at: number, domain: "anyfs-delta/1" | "anyfs-epoch/1" | "anyfs-dump/1") => SignatureVerdict | Promise<SignatureVerdict>;
};Whom a replica takes changes from: open takes any, allowlist only the replicas named (the default, and itself alone by default), signed only deltas whose signature a verifier accepts and, where replicas is given, only from those replicas as well (a replica must be on the list and its signature must hold). at is the time of the newest row of the delta in milliseconds, so that a key has a window in which it speaks for a replica.
defaultTrustconstconst defaultTrust: (self: ReplicaId) => TrustThe trust a replica has until it is told otherwise: itself alone.
MERGE_REFUSAL_KINDSconstconst MERGE_REFUSAL_KINDS: readonly ["trust", "unsigned", "bad-signature", "unknown-key", "future-id", "malformed", "too-large", "bad-sum", "bad-blob", "forged"]The reasons a delta is refused: a closed list.
MergeRefusalKindtypeno test imports ittype MergeRefusalKind = (typeof MERGE_REFUSAL_KINDS)[number];One reason a delta is refused.
MergeRefusaltypeno test imports ittype MergeRefusal = { readonly kind: MergeRefusalKind; readonly message: string };A delta that was not applied, and why.
MergeOutcometypeno test imports ittype MergeOutcome =
| { readonly kind: "applied"; readonly versions: number; readonly blobs: number; readonly findings: readonly MergeFinding[] }
| { readonly kind: "duplicate" }
| { readonly kind: "deferred"; readonly missing: readonly string[] }
| { readonly kind: "refused"; readonly refusal: MergeRefusal };What applying a delta ended with: a closed union. deferred names the versions and blobs the delta waits for.
FINDING_KINDSconstconst FINDING_KINDS: readonly ["duplicate-id", "duplicate-seq", "bad-sum", "bad-blob", "future-id", "untrusted-replica", "dangling-parent", "missing-blob", "bad-id"]The kinds of finding of a merge: things a person should know that are not conflicts.
MergeFindingKindtypeno test imports ittype MergeFindingKind = (typeof FINDING_KINDS)[number];One kind of finding.
MergeFindingtypeno test imports ittype MergeFinding = { readonly kind: MergeFindingKind; readonly subject: string; readonly message: string };A finding about a row or a blob: its kind, what it is about and one sentence.
describeMergeRefusalfunctionfunction describeMergeRefusal(refusal: MergeRefusal): stringOne sentence for a refusal.
Fingerprinttypetype Fingerprint = Brand<string, "anyfs fingerprint">;How a copy of a database is told from the one it was made from: a text the host makes of what it cannot copy, such as the identity of the file system object.
parseFingerprintfunctionno test imports itfunction parseFingerprint(text: string): Result<Fingerprint, string>A fingerprint from text, or why it is not one.