IF Commons GitHub

governance/merge

Written to: 5 requirements: 5 proved, 0 partly, 0 failing, 0 with no test recorded. 0007-anyfs-merge-governance FR-001, 0007-anyfs-merge-governance FR-002, 0007-anyfs-merge-governance FR-003, 0007-anyfs-merge-governance FR-004, 0007-anyfs-merge-governance FR-005

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"; // true

Source: commons/anyfs/src/governance/merge.ts

20 of 36 exports are imported by a test of the run. A test that imports an export may not call it or check what it returns.

ReplicaIdtype
type 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.

Imported by 30 tests of the run (30 passed, 0 failed): the library's results

parseReplicaIdfunction
function parseReplicaId(text: string): Result<ReplicaId, string>

A replica identity from text, or why it is not one.

Imported by 14 tests of the run (14 passed, 0 failed): the library's results

replicaIdOfBytesfunction
function replicaIdOfBytes(bytes: Uint8Array<ArrayBufferLike>): Result<ReplicaId, string>

A replica identity from 16 random bytes.

Imported by 35 tests of the run (35 passed, 0 failed): the library's results

VersionIdtype
type 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.

Imported by 5 tests of the run (5 passed, 0 failed): the library's results

parseVersionIdfunction
function parseVersionId(text: string): Result<VersionId, string>

A version identity from text, or why it is not one.

Imported by 19 tests of the run (19 passed, 0 failed): the library's results

MAX_ID_MSconstno test imports it
const MAX_ID_MS: number

The largest time an id holds: 48 bits of milliseconds.

MAX_ID_COUNTERconstno test imports it
const MAX_ID_COUNTER: 4095

The largest counter of an id: 12 bits.

IdTimetype
type IdTime = { readonly ms: number; readonly counter: number };

The time of an id: the milliseconds and the counter that orders ids of one millisecond.

Imported by 5 tests of the run (5 passed, 0 failed): the library's results

ID_RANDOM_BYTESconstno test imports it
const ID_RANDOM_BYTES: 8

The bytes an id takes for its random part: 62 bits are used, from 8 bytes.

MAX_COUNTER_SEEDconst
const MAX_COUNTER_SEED: 2047

The 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).

Imported by 5 tests of the run (5 passed, 0 failed): the library's results

randomIdBytesfunction
function randomIdBytes(length?: number): Uint8Array<ArrayBufferLike>

Random bytes from the CSPRNG of the runtime (RFC 9562 section 6.9 and 8).

Imported by 5 tests of the run (5 passed, 0 failed): the library's results

randomCounterSeedfunction
function randomCounterSeed(): number

A counter seed from the CSPRNG: a number from 0 to MAX_COUNTER_SEED.

Imported by 5 tests of the run (5 passed, 0 failed): the library's results

makeVersionIdfunction
function makeVersionId(time: IdTime, random?: Uint8Array<ArrayBufferLike>): VersionId

An 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.

Imported by 19 tests of the run (19 passed, 0 failed): the library's results

timeOfIdfunction
function timeOfId(id: VersionId): IdTime

The time of an id.

Imported by 19 tests of the run (19 passed, 0 failed): the library's results

compareTimefunction
function compareTime(a: IdTime, b: IdTime): number

The order of two times: the milliseconds and then the counter.

Imported by 19 tests of the run (19 passed, 0 failed): the library's results

VersionVectortypeno test imports it
type 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 it
const 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 it
type VersionKind = (typeof VERSION_KINDS)[number];

One kind of version.

Versiontype
type 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.

Imported by 19 tests of the run (19 passed, 0 failed): the library's results

DELTA_FORMATconstno test imports it
const DELTA_FORMAT: 1

The format of a delta on the wire: the only one so far.

BlobWiretypeno test imports it
type BlobWire = { readonly sha: string; readonly bytes: string };

The bytes of a blob on the wire: base64.

Deltatype
type 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.

Imported by 19 tests of the run (19 passed, 0 failed): the library's results

SIGNATURE_VERDICTSconstno test imports it
const 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 it
type SignatureVerdict = (typeof SIGNATURE_VERDICTS)[number];

One verdict of a verifier.

Trusttype
type 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.

Imported by 5 tests of the run (5 passed, 0 failed): the library's results

defaultTrustconst
const defaultTrust: (self: ReplicaId) => Trust

The trust a replica has until it is told otherwise: itself alone.

Imported by 14 tests of the run (14 passed, 0 failed): the library's results

MERGE_REFUSAL_KINDSconst
const 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.

Imported by 14 tests of the run (14 passed, 0 failed): the library's results

MergeRefusalKindtypeno test imports it
type MergeRefusalKind = (typeof MERGE_REFUSAL_KINDS)[number];

One reason a delta is refused.

MergeRefusaltypeno test imports it
type MergeRefusal = { readonly kind: MergeRefusalKind; readonly message: string };

A delta that was not applied, and why.

MergeOutcometypeno test imports it
type 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_KINDSconst
const 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.

Imported by 14 tests of the run (14 passed, 0 failed): the library's results

MergeFindingKindtypeno test imports it
type MergeFindingKind = (typeof FINDING_KINDS)[number];

One kind of finding.

MergeFindingtypeno test imports it
type 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.

describeMergeRefusalfunction
function describeMergeRefusal(refusal: MergeRefusal): string

One sentence for a refusal.

Imported by 14 tests of the run (14 passed, 0 failed): the library's results

Fingerprinttype
type 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.

Imported by 5 tests of the run (5 passed, 0 failed): the library's results

parseFingerprintfunctionno test imports it
function parseFingerprint(text: string): Result<Fingerprint, string>

A fingerprint from text, or why it is not one.

Titles, headings, exports, tables, columns and requirements. Esc closes.