crdt

package
v0.0.0-...-e628794 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 26, 2026 License: Apache-2.0 Imports: 12 Imported by: 0

Documentation

Overview

Package crdt defines the public replication values and canonical codecs shared by Syzy database engines, transports, journals, and object storage.

The package contains pure values and arbitration helpers; it has no database dependency and performs no I/O. Engine modules map native transactions and catalogs to these types, then realize accepted records through their own transactional apply paths.

Specifications

The authoritative shared documents are:

  • docs/CRDT.md: consistency guarantees, named invariants, causal length, and the row, cell, range, counter, and unique layers;
  • docs/PROTOCOL.md: the changeset envelope, record and value encoding, HLC packing, and engine durability obligations; and
  • docs/SCHEMA.md: catalog-operation meaning, stable identities, and schema dependency ordering.

Mechanical Go detail lives with the type or function it describes: 

identity.go    Origin, Seq, Dot, Clock, Stamp
causal.go      SeqRange, SeqSet
deps.go        Deps and schema-chain dependencies
changeset.go   Changeset and DML record values
codec.go       canonical changeset encoding and decoding
catalog_op.go  stable schema catalog operations
state.go       RowState, causal-generation transitions, effective stamps
interval.go    byte-range conflict layer

Schema-chain totality, invariant (8), is enforced by schemalog compare-and- swap append and catalog sequence apply. Unique-key exclusivity, invariant (10), is enforced by the admitted engine apply or coordination path. Their shared meaning is specified here even though enforcement crosses package boundaries.

SQLite boundary

The shared package specifies what a changeset means, while the SQLite module owns capture, apply, and physical recovery. Its linked and extension runtimes must preserve the transaction identity, encoding, arbitration, and durable-frontier ordering defined here.

Producer, apply, metadata, and recovery implementations are deliberately outside this package.

Index

Constants

View Source 
const (
	FormatText   uint8 = 0
	FormatBinary uint8 = 1
	// FormatDelta marks a counter-column contribution: Bytes is a signed
	// int64 adjustment (TypeTag ColInt layout) summed into the current
	// cell value instead of overwriting it. CRDT.md F_counter.
	FormatDelta uint8 = 2
)

ColValue.Format values. The codec round-trips Format untouched; the apply path interprets it.

View Source 
const MaxCatalogOpVersion = catalogOpMaxVersion

MaxCatalogOpVersion is the newest envelope version this build decodes. Exported so fail-closed tests and diagnostics can name "newer than this binary" without hardcoding a number that goes stale the moment the wire gains a version.

View Source 
const WireVersion uint8 = 2

WireVersion is the current Changeset wire-format version. Producers always emit this constant. Receivers accept it plus wireVersionV1; any other version is rejected.

Variables

View Source 
var (
	ErrShortBuffer    = errors.New("crdt: short buffer")
	ErrUnknownVersion = errors.New("crdt: unknown wire version")
	ErrCRCMismatch    = errors.New("crdt: CRC mismatch")
	ErrUnknownOp      = errors.New("crdt: unknown record op")
	// ErrUnknownColType is surfaced by the predicate literal codec, whose
	// tag space is the four SQLite storage classes (the changeset codec
	// treats TypeTag as opaque and never validates it).
	ErrUnknownColType = errors.New("crdt: unknown column type tag")
	ErrOriginMismatch = errors.New("crdt: Stamp.Origin must equal Dot.Origin")
)

Errors surfaced by Decode.

View Source 
var ErrCatalogOpKind = errors.New("crdt: CatalogOp kind not supported")

ErrCatalogOpKind is returned when an op names a kind this decoder does not implement. Like ErrCatalogOpVersion it means "cannot participate": the kind carries semantics, so skipping the event would apply a partial catalog.

View Source 
var ErrCatalogOpVersion = errors.New("crdt: CatalogOp version not supported")

ErrCatalogOpVersion is returned when an op's version postdates this decoder. Callers must treat it as "cannot participate" (schema unhealthy / quarantine), never skip the event.

View Source 
var ErrCounterValue = errors.New("crdt: counter value")

ErrCounterValue marks a value that cannot participate in counter summation: a counter cell that is not an 8-byte integer, or a difference that overflows int64. Producers surface it as a hard stop (a wrong delta would apply everywhere); receivers route it to quarantine.

Functions

func ColValueEqual 

func ColValueEqual(a, b ColValue) bool

ColValueEqual reports whether two values carry the same logical content — the diff predicate cell-group producers use to decide which columns a transaction actually changed.

func CoversAllNonPK 

func CoversAllNonPK(t CellTable, writes []ColValue) bool

CoversAllNonPK reports whether writes covers every active non-PK column of t. A cell-group update covering every column absorbs the row back into its baseline (opportunistic collapse).

func EncodeCatalogOp 

func EncodeCatalogOp(op CatalogOp) ([]byte, error)

EncodeCatalogOp returns the canonical framed bytes for op. Errors only for unsupported kinds or oversized strings (uvarint length tags are generous; the limits exist to fail loudly on malformed input rather than silently truncate).

func EncodeUniquePredicate 

func EncodeUniquePredicate(p UniquePredicate) []byte

EncodeUniquePredicate returns the canonical bytes for p (a nil Root encodes as a single present=0 byte). Used to persist a partial index's predicate in metadata; the catalog-op wire path uses appendPredicate directly.

Types

type BlobPatch 

type BlobPatch struct {
	Table  TableID
	PK     PKBlob
	CL     uint64
	Col    ColumnID
	Ranges []BlobPatchRange
}

BlobPatch carries non-overlapping per-byte updates to a single blob column on a single row, scoped to the row's current CL on the writer. See BLOB_PATCH.md for the full algorithm.

func (BlobPatch) Header 

func (r BlobPatch) Header() RecordHeader

type BlobPatchRange 

type BlobPatchRange struct {
	Offset uint64
	Bytes  []byte
}

BlobPatchRange is one (offset, bytes) sub-range inside a BlobPatch.

func (BlobPatchRange) End 

func (r BlobPatchRange) End() uint64

End returns Offset + len(Bytes).

type ByteRange 

type ByteRange struct {
	Start, End uint64
}

ByteRange is a half-open byte interval [Start, End) used by the per-byte-range layer. End == Start denotes the empty range.

func (ByteRange) Empty 

func (r ByteRange) Empty() bool

Empty reports whether r covers no bytes.

func (ByteRange) Length 

func (r ByteRange) Length() uint64

Length returns r's length in bytes (0 if empty).

func (ByteRange) Overlaps 

func (r ByteRange) Overlaps(other ByteRange) bool

Overlaps reports whether r and other share any bytes.

type CatalogColumn 

type CatalogColumn struct {
	ID         ColumnID
	Name       string
	Ordinal    int
	Type       string // declared SQLite type, e.g. "INTEGER", "TEXT", "BLOB", "" for typeless.
	NotNull    bool
	Default    string // SQL default expression, "" for none.
	IsPK       bool   // true if column is part of the PK
	PKPos      int    // 1-indexed PK position; meaningful only when IsPK.
	ClockGroup string // "row" (default) or "cell".
	Generated  bool   // STORED or VIRTUAL generated column; receivers recompute.
	// Collation is the column's text collating sequence. The zero value
	// (CollBinary) is SQLite's default.
	Collation Collation
}

CatalogColumn describes one column inside CreateTable / AddColumn. Default carries the textual default expression as it appears in the declaration (or the empty string for none); receivers re-emit it verbatim.

type CatalogKey 

type CatalogKey struct {
	KeyID   KeyID
	Members []CatalogKeyMember
	// Coordinated marks a CP unique key (NOT NULL UNIQUE) whose global
	// uniqueness is enforced by reservation before commit. Always false
	// for the PK and for eventual (loser-null) unique keys. See
	// docs/SCHEMA.md#unique-keys.
	Coordinated bool
	// Predicate is the compiled WHERE clause of a partial unique index
	// (zero/nil Root for a total key). A partial key is always
	// Coordinated. See
	// docs/SCHEMA.md#unique-keys.
	Predicate UniquePredicate
}

CatalogKey describes one key (PK or unique) inside CatalogOp.Keys.

type CatalogKeyMember 

type CatalogKeyMember struct {
	ColumnID ColumnID
	Ordinal  int
}

CatalogKeyMember names one member column of a unique key.

type CatalogOp 

type CatalogOp struct {
	Kind CatalogOpKind

	// CreateTable, DropTable, RenameTable, AddColumn, DropColumn,
	// RenameColumn, AddUniqueKey, DropUniqueKey: target table.
	TableID   TableID
	TableName string // post-rename name for RenameTable; declared name for CreateTable; ignored otherwise.

	// AddColumn, DropColumn, RenameColumn: target column.
	ColumnID   ColumnID
	ColumnName string // post-rename name for RenameColumn; new column name for AddColumn.

	// CreateTable: full column list (declared order). AddColumn: a
	// single-element column descriptor.
	Columns []CatalogColumn
	// CreateTable: render the receiver table with WITHOUT ROWID.
	WithoutRowid bool

	// CreateTable, AddUniqueKey: key membership. CreateTable always
	// includes the PK at KeyID = PKKeyID (all-zero). Unique keys appear
	// at distinct KeyIDs.
	Keys []CatalogKey

	// AddUniqueKey / DropUniqueKey: key id.
	KeyID KeyID

	// CreateIndex, DropIndex, CreateView, DropView,
	// CreateVirtualTable, DropVirtualTable: opaque SQL replayed
	// verbatim on receivers. Replicated views/vtables are not typed.
	RawSQL string

	// CreateView/DropView/CreateVirtualTable/DropVirtualTable/
	// CreateTrigger/DropTrigger: the object's name. Used by receivers
	// to re-prepare structural state checks (e.g. DROP VIEW IF EXISTS).
	//
	// On CreateTrigger/DropTrigger, TableID doubles as a marker: zero
	// means a user-written trigger; non-zero means a cascade-
	// synthesized trigger owned by that child table (apply path
	// registers/unregisters syzy_synth_trigger accordingly).
	ObjectName string

	// Bundle: ordered list of sub-ops applied atomically on receivers
	// in a single metadata txn. Used for compound DDL (e.g. CREATE
	// TABLE plus its synthesized cascade triggers). Bundles do not
	// nest; SubOps must not contain another OpBundle.
	SubOps []CatalogOp

	// SetClockGroup: the table's new default_clock_group ('row' or
	// 'cell'). Target table in TableID.
	ClockGroup string
}

CatalogOp is the typed catalog mutation written to the schema log and replayed by every node's apply path. The Kind tag selects which fields are meaningful; encoding is dense.

All op variants share two header fields so the decoder can dispatch without looking inside each variant's body. Fields that don't apply to a given Kind are ignored on encode and zero on decode.

func DecodeCatalogOp 

func DecodeCatalogOp(buf []byte) (CatalogOp, error)

DecodeCatalogOp parses the bytes produced by EncodeCatalogOp, current or legacy.

type CatalogOpKind 

type CatalogOpKind uint8

CatalogOpKind tags one shape of CatalogOp on the wire and in syzy_schema_event.catalog_op. Values are durable; never reuse or reorder them. Allocation plan: 1–31 core relational ops, 32–63 reserved for engine-specific ops (each engine's typed DDL shapes, ordinal claims), 64+ unassigned. Kinds are encoded as uvarint in the framed format, so the space is open-ended. 

const (
	OpUnknown            CatalogOpKind = 0
	OpCreateTable        CatalogOpKind = 1
	OpAddColumn          CatalogOpKind = 2
	OpRenameTable        CatalogOpKind = 3
	OpRenameColumn       CatalogOpKind = 4
	OpDropColumn         CatalogOpKind = 5
	OpDropTable          CatalogOpKind = 6
	OpAddUniqueKey       CatalogOpKind = 7
	OpDropUniqueKey      CatalogOpKind = 8
	OpCreateIndex        CatalogOpKind = 9
	OpDropIndex          CatalogOpKind = 10
	OpCreateView         CatalogOpKind = 11
	OpDropView           CatalogOpKind = 12
	OpCreateVirtualTable CatalogOpKind = 13
	OpDropVirtualTable   CatalogOpKind = 14
	OpCreateTrigger      CatalogOpKind = 15
	OpDropTrigger        CatalogOpKind = 16
	OpBundle             CatalogOpKind = 17
	OpSetClockGroup      CatalogOpKind = 18
	OpAlterColumn        CatalogOpKind = 19
)

func (CatalogOpKind) String 

func (k CatalogOpKind) String() string

String returns a stable human-readable name for the op kind. Used by logging, status output, and catalog_op debug dumps.

type CellTable 

type CellTable interface {
	// ColumnRole classifies an active column as PK member and/or
	// declared counter. Unknown or dropped columns report both false.
	ColumnRole(ColumnID) (pk, counter bool)
	// NonPKColumns lists the table's active non-PK column IDs.
	NonPKColumns() []ColumnID
}

CellTable is the table shape cell-group normalization consults: per-column roles and the active non-PK column set. Each engine's catalog implements it.

type ChainID 

type ChainID uint16

ChainID identifies one of (potentially several) totally-ordered CAS chains a Changeset can causally depend on. v1 uses one chain only:

  • SchemaChain (= 0): the schema log.

The shape allows v2 chains (FK targets, application-defined causal barriers, blob_patch base rows) at no encoding cost. 

const (
	SchemaChain ChainID = 0
)

Reserved chain IDs.

type Changeset 

type Changeset struct {
	Dot       Dot
	Stamp     Stamp
	Deps      Deps
	ClusterID ClusterID
	Records   []Record
	// contains filtered or unexported fields
}

Changeset is the replicated unit: one committed local transaction's DML records, framed with identity (Dot), arbitration (Stamp), dependencies (Deps), and integrity (CRC). Immutable after construction.

Build encodes a Changeset from typed records (used by the producer at commit time). Decode parses wire/storage bytes (used by the broker on inbound apply and by recovery's mirror-journal replay). The Encoded field caches the canonical bytes; a Changeset's Encoded is identical to its journal-record payload and to its on-the-wire bytes.

func Build 

func Build(dot Dot, stamp Stamp, deps Deps, cluster ClusterID, records []Record) (*Changeset, error)

Build encodes a Changeset from typed inputs and returns the immutable result. The producer calls Build at commit time.

func Decode 

func Decode(buf []byte) (*Changeset, error)

Decode parses canonical bytes into a Changeset. The broker calls Decode on inbound delivery; the recovery path uses it when replaying mirror journals. The returned Changeset's Encoded field points into a copy of buf, owned by the Changeset.

func (*Changeset) CRC 

func (c *Changeset) CRC() uint64

CRC returns the 64-bit integrity checksum carried in the header.

func (*Changeset) Encoded 

func (c *Changeset) Encoded() []byte

Encoded returns the canonical wire/storage bytes. Caller must not mutate the returned slice.

type Clock 

type Clock struct {
	WallTime int64 // unix epoch milliseconds
	Logical  int32 // tiebreaker for equal wall times
}

Clock is a Hybrid Logical Clock value: 47-bit physical milliseconds in the high bits of WallTime, 16-bit logical counter in the low bits, with bit 63 reserved zero. Logical is exposed as a separate field so callers don't need bit-twiddling for the common case.

Implementation mirrors CockroachDB pkg/util/hlc. There is intentionally no Synthetic field — CRDB removed it for soundness; Syzy never adds it.

func UnpackClock 

func UnpackClock(v uint64) Clock

UnpackClock reverses Pack: extracts WallTime and Logical from the 8-byte wire form. Bit 63 is ignored (reserved zero).

func (Clock) Equal 

func (c Clock) Equal(other Clock) bool

Equal reports whether c and other carry the same WallTime and Logical.

func (Clock) Forward 

func (c Clock) Forward(other Clock) Clock

Forward returns max(c, other). Pure; does not mutate the receiver.

func (Clock) IsZero 

func (c Clock) IsZero() bool

IsZero reports whether c is the zero value (used as the implicit Stamp for never-existed RowState).

func (Clock) Less 

func (c Clock) Less(other Clock) bool

Less reports whether c < other under strict lex on (WallTime, Logical).

func (Clock) Pack 

func (c Clock) Pack() uint64

Pack returns the 8-byte wire form: 47-bit WallTime in the high bits + 16-bit Logical in the low bits, with bit 63 reserved zero. Panics on out-of-range inputs, which would only occur from buggy callers.

type ClusterID 

type ClusterID [16]byte

ClusterID is a 16-byte cluster-wide UUID. Receivers reject Changesets whose ClusterID does not match their configured cluster (mis-route defense — see ARCHITECTURE.md).

type ColType 

type ColType = uint32

ColType names the canonical storage-class TypeTag values shared by shipping engines. It is an alias for uint32 (the ColValue.TypeTag width). The core never interprets a nonzero TypeTag; arbitration is over Stamps. 

const (
	ColNull ColType = 0
	ColInt  ColType = 1
	ColReal ColType = 2
	ColText ColType = 3
	ColBlob ColType = 4
)

Well-known TypeTag values. ColNull (0) is reserved cluster-wide as the NULL tag, so zero unambiguously means "SQL NULL, no bytes".

type ColValue 

type ColValue struct {
	Column ColumnID
	// TypeTag is an opaque, engine-defined type discriminator the core never
	// interprets. Shipping engines use the canonical storage-class tags
	// (ColInt/ColReal/ColText/ColBlob). TypeTag == 0 (ColNull) means the
	// value is SQL NULL and carries no Bytes.
	TypeTag uint32
	// Format is the byte encoding of Bytes: FormatText (0, the canonical
	// OID-free external form — the default), FormatBinary (1, a future
	// cluster-wide mode), or FormatDelta (2, a signed additive adjustment
	// to a counter column — same 8-byte int64 layout as an absolute
	// ColInt, applied as `col = col + ?`; see sqlite/docs/DDL.md#counter-columns).
	// It rides with every value so the decoder is unambiguous.
	Format uint8
	// Bytes carries the raw encoded value (empty when TypeTag == 0). For the
	// canonical tags: ColInt = 8-byte big-endian int64, ColReal = 8-byte big-endian
	// IEEE 754 binary64, ColText = UTF-8, and ColBlob = raw bytes.
	Bytes []byte
}

ColValue is one column-id → typed-value pair carried inside an Insert.Image or Update.Changed slice (§4 / wire-v2).

func CounterDelta 

func CounterDelta(old, new ColValue) (ColValue, error)

CounterDelta returns the FormatDelta contribution NEW − OLD for one counter cell: receivers sum it (CRDT.md F_counter), so concurrent increments merge instead of stomping each other. Both sides must be 8-byte ColInt values, and the subtraction is checked — a wrapped delta would apply as arithmetically wrong on every node, so it fails loudly (ErrCounterValue) rather than silently. Callers wrap the error with their table and column names.

func IntColValue 

func IntColValue(v int64) ColValue

IntColValue builds an integer ColValue (8-byte big-endian two's-complement) — the canonical capture encoding. Used to construct predicate literals.

func RealColValue 

func RealColValue(f float64) ColValue

RealColValue builds a real ColValue (8-byte big-endian IEEE 754 binary64) — the canonical capture encoding.

type Collation 

type Collation uint8

Collation identifies a SQLite text collating sequence. Only the three built-ins are representable — they are the only collations that can be replayed identically on every replica without shipping a comparison function. A column or predicate that needs a custom (registered) collation is rejected at admission. 

const (
	CollBinary Collation = 0 // memcmp; the default
	CollNocase Collation = 1 // ASCII case-folded (A–Z only), then memcmp
	CollRtrim  Collation = 2 // trailing spaces ignored, then memcmp
)

func CollationFromName 

func CollationFromName(name string) (Collation, bool)

CollationFromName normalizes a SQLite collation name. ok is false for a custom/unknown collation (the caller rejects it). The empty name and "BINARY" both map to CollBinary.

func (Collation) CompareText 

func (c Collation) CompareText(a, b []byte) int

CompareText orders two text/blob byte strings under the collation, matching SQLite's built-in collating functions exactly: NOCASE folds only ASCII A–Z, RTRIM ignores trailing 0x20 spaces, both then memcmp with shorter-is-less on a common prefix.

func (Collation) Name 

func (c Collation) Name() string

Name returns the canonical SQLite collation name, or "" for BINARY (the default, which a column omits).

type ColumnID 

type ColumnID [16]byte

ColumnID is a 16-byte stable identifier for a column. Names survive RENAME COLUMN; IDs persist tombstoned beyond DROP COLUMN so late DML can be deterministically ignored.

type Delete 

type Delete struct {
	Table TableID
	PK    PKBlob
	CL    uint64
}

Delete tombstones a row keyed by (Table, PK) at the post-DELETE CL. No column payload.

func (Delete) Header 

func (r Delete) Header() RecordHeader

type Deps 

type Deps map[ChainID]Seq

Deps is the one-hop minimal causal dependency set carried by a Changeset. Per Lloyd et al. COPS (SOSP 2011) / Eiger (NSDI 2013): each Changeset carries the transitive reduction of its causal dependencies — entries not already implied by other carried deps or by the receiver's frontier. The receiver checks every dep before applying — invariant (3) in CRDT.md (causal closure of Deps).

At apply time the receiver enforces the Almeida δ-state causal-merging condition (Almeida et al. 2016, Def. 6): a delta is applied only when every dependency it references is already satisfied locally. The schema chain is the one cross-chain Dep; the broker gates on Deps[SchemaChain] against local schema_seq.

nil and empty Deps are equivalent: no dependencies.

func (Deps) Clone 

func (d Deps) Clone() Deps

Clone returns a deep copy. Useful before passing to a caller that may mutate.

func (Deps) Equal 

func (d Deps) Equal(other Deps) bool

Equal reports whether d and other carry the same chain→seq mappings.

func (Deps) Satisfied 

func (d Deps) Satisfied(have map[ChainID]Seq) bool

Satisfied reports whether every dep in d is covered by have: have[chain] >= d[chain] for every chain in d.

have may safely be nil; missing chains are treated as Seq(0).

func (Deps) Set 

func (d Deps) Set(chain ChainID, seq Seq)

Set assigns d[chain] = seq. Panics on a Seq lower than an existing entry (deps are intended to be the maximum required position per chain; lowering would violate the one-hop minimal property).

type Dot 

type Dot struct {
	Origin Origin
	Seq    Seq
}

Dot is the identity of a single replication event (Preguiça et al., Dotted Version Vectors, 2010). Producer-enforced: invariant (1) (Dot uniqueness) and invariant (2) (per-origin Clock monotonicity). Spec: CRDT.md.

func (Dot) String 

func (d Dot) String() string

String renders a Dot as "origin/seq" in decimal. Cheap and unambiguous; useful for logs and error messages.

type Insert 

type Insert struct {
	Table TableID
	PK    PKBlob
	CL    uint64
	Image []ColValue
}

Insert carries a full row image of active non-generated columns plus the post-INSERT CL.

func (Insert) Header 

func (r Insert) Header() RecordHeader

type IntervalEntry 

type IntervalEntry struct {
	Range ByteRange
	Stamp Stamp
}

IntervalEntry is one (range, stamp) pair in an IntervalMap.

func (IntervalEntry) Equal 

func (e IntervalEntry) Equal(o IntervalEntry) bool

Equal reports whether e and o have the same range and stamp.

type IntervalMap 

type IntervalMap interface {
	// At returns the effective Stamp at byte offset off. If no entry
	// covers off, returns the zero Stamp (caller falls through to the
	// parent layer per RowState.EffectiveStamp).
	At(off uint64) Stamp

	// Apply integrates a write of Stamp c over [start, end), with the
	// caller's claimed parent baseline. It returns the sub-ranges where
	// c won — only those bytes need to be written through to the blob
	// itself. Existing entries that c does not strictly dominate are
	// preserved; gaps where c does not strictly dominate baseline are
	// not added.
	Apply(start, end uint64, c, baseline Stamp) []ByteRange

	// Prune drops every entry with Stamp <= floor. Called after the
	// parent row/cell Stamp advances past a stable horizon.
	Prune(floor Stamp)

	// Clip drops entries with Start >= maxEnd and truncates entries
	// with End > maxEnd to End = maxEnd.
	Clip(maxEnd uint64)

	// IsEmpty reports whether the map holds no entries. When true, the
	// caller deletes the blob_range_clock row entirely.
	IsEmpty() bool

	// Entries returns the underlying entries in ascending Start order
	// for inspection / serialization. Caller must not mutate.
	Entries() []IntervalEntry
}

IntervalMap is the byte-range layer's CRDT primitive: per-row, per-blob-column, mapping disjoint byte intervals to the Stamp of the patch that wrote them. See BLOB_PATCH.md for the full algorithm and the Layers section of CRDT.md for the byte-range layer's (vis, ar) form.

Invariants:

  • Stored entries are sorted by Start, non-overlapping, and (under the run-coalescing invariant) byte-contiguous neighbours with equal Stamps are merged into one entry.
  • Every entry strictly Dominates the effective parent Stamp at construction time. Apply enforces this.

func NewIntervalMap 

func NewIntervalMap() IntervalMap

NewIntervalMap returns an empty IntervalMap. Callers create one lazily — most rows have no entries and the table-level row stays absent in blob_range_clock.

type KeyID 

type KeyID [16]byte

KeyID is a 16-byte stable identifier for a key (PK or unique key) in a table. The all-zero value (PKKeyID in the metadata package) denotes the primary key tuple; every other value identifies one unique constraint or unique index. See docs/SCHEMA.md#stable-catalog-identity.

type Origin 

type Origin uint64

Origin identifies a replica's local-write epoch. Producer rotates the origin on unclean restart so post-recovery writes cannot reuse a Seq already visible under the previous origin.

Restricted to [0, 2^63): the wire format reserves bit 63 zero. Allocators must mask the high bit at generation time.

type PKBlob 

type PKBlob []byte

PKBlob is the canonical encoded primary key blob. Encoding rules and rejected types are specified in docs/PROTOCOL.md#value-encoding.

type PredExpr 

type PredExpr struct {
	Op   PredOp
	Col  ColumnID
	Lits []ColValue
	Kids []*PredExpr
	// Coll is the collating sequence for a text comparison/IN node
	// (CollBinary for numeric comparisons and the structural ops). It is
	// baked in at admission from the column's declared collation so Eval
	// is self-contained and the rebuild path can emit an explicit COLLATE.
	Coll Collation
}

PredExpr is one node of a UniquePredicate. The meaningful fields depend on Op: leaf NULL tests use Col; comparisons use Col+Lits[0]; IN/NOT IN use Col+Lits; AND/OR use Kids (n≥1); NOT uses Kids[0].

type PredOp 

type PredOp uint8

PredOp tags a node in a UniquePredicate tree. Encoded values are stable. 

const (
	PredIsNull    PredOp = 1 // <col> IS NULL
	PredIsNotNull PredOp = 2 // <col> IS NOT NULL
	PredEq        PredOp = 3 // <col> =  <lit>
	PredNe        PredOp = 4 // <col> <> <lit>
	PredLt        PredOp = 5 // <col> <  <lit>
	PredLe        PredOp = 6 // <col> <= <lit>
	PredGt        PredOp = 7 // <col> >  <lit>
	PredGe        PredOp = 8 // <col> >= <lit>
	PredIn        PredOp = 9 // <col> IN (<lit>, …)
	PredNotIn     PredOp = 10
	PredAnd       PredOp = 11 // all Kids
	PredOr        PredOp = 12 // any Kids
	PredNot       PredOp = 13 // single Kid
)

type Record 

type Record interface {
	Header() RecordHeader
}

Record is the sealed-sum DML record carried inside a Changeset. Implementations: Insert, Update, Delete, BlobPatch.

Every record carries the CL (causal length) it applies under — the writer's view of the row's generation at write time:

  • Insert: the post-INSERT CL (writer's NextLiveCL — always odd).
  • Update: the row's current CL on the writer (must be odd; UPDATE does not bump CL).
  • Delete: the post-DELETE CL (writer's NextTombCL — always even).
  • BlobPatch: the row's current CL on the writer (must be odd).

Receivers apply a record iff its (CL, Stamp) lex-dominates the receiver's current (RowState.CL, RowState.Base) — see CRDT.md#causal-length-cl.

type RecordHeader 

type RecordHeader struct {
	Op    recordOp
	Table TableID
	PK    PKBlob
	CL    uint64
}

RecordHeader is the per-record prefix shared by every Record: the wire op tag, the (Table, PK) key, and the writer's view of the post-op CL.

type RowState 

type RowState struct {
	CL     uint64
	Base   Stamp
	Cells  map[ColumnID]Stamp
	Ranges map[ColumnID]IntervalMap
}

RowState is the per-row CRDT state for a single (TableID, PKBlob). Stored in the metadata; reconstructed on apply from row_clock, cell_clock, and blob_range_clock rows.

CL is the cr-sqlite causal length (parity = liveness). Base is the row's baseline LWW Stamp at this CL. Cells and Ranges are sparse overrides scoped to (CL, Base); bumping CL on resurrection implicitly tombstones prior-generation overrides.

func (RowState) DominatedBy 

func (r RowState) DominatedBy(incCL uint64, inc Stamp) bool

DominatedBy reports whether (incCL, inc) wins LWW against r's (CL, Base): strictly greater CL wins; tied CL goes to Stamp.Dominates. Spec: CRDT.md#causal-length-cl.

func (RowState) EffectiveStamp 

func (r RowState) EffectiveStamp(col ColumnID, rng ByteRange) Stamp

EffectiveStamp returns the LWW Stamp governing reads of (col, rng). Fall-through order per CRDT.md#layer-composition:

  1. Ranges[col].At(rng.Start) if set and the IntervalMap covers rng.
  2. Cells[col] if a sparse override exists.
  3. Base — the row's baseline.

rng with Empty() == true is treated as "no range constraint" — the fall-through skips the Ranges layer and goes straight to Cells/Base.

On a never-existed row (CL == 0) the returned Stamp is the zero value, which is dominated by every real write.

func (RowState) IsLive 

func (r RowState) IsLive() bool

IsLive reports whether r currently represents a live row at its generation (CL is odd).

func (RowState) IsNeverExisted 

func (r RowState) IsNeverExisted() bool

IsNeverExisted reports whether r represents a pk that has never had any write applied (CL == 0).

func (RowState) IsTombstoned 

func (r RowState) IsTombstoned() bool

IsTombstoned reports whether r is currently a tombstone (CL is even and non-zero).

func (RowState) NextLiveCL 

func (r RowState) NextLiveCL() uint64

NextLiveCL returns the smallest odd CL strictly greater than r.CL — the value an INSERT (or resurrecting INSERT) must take. Producer-side helper.

func (RowState) NextTombCL 

func (r RowState) NextTombCL() uint64

NextTombCL returns the smallest even CL strictly greater than r.CL — the value a DELETE on a live row must take. Calling on a non-live row returns r.CL unchanged (DELETE is a no-op on a tombstone or never- existed row at the producer; receivers handle missing-row DELETEs by recording a tombstone).

type Seq 

type Seq uint64

Seq is a per-origin monotonic counter. The pair (Origin, Seq) is a Dot.

type SeqRange 

type SeqRange struct {
	Lo, Hi Seq
}

SeqRange is an inclusive [Lo, Hi] window of Seqs from one Origin. Lo > Hi is treated as the empty range.

func (SeqRange) Contains 

func (r SeqRange) Contains(s Seq) bool

Contains reports whether s ∈ [Lo, Hi].

func (SeqRange) Empty 

func (r SeqRange) Empty() bool

Empty reports whether r covers no Seqs.

func (SeqRange) String 

func (r SeqRange) String() string

String formats r as "[Lo,Hi]".

type SeqSet 

type SeqSet struct {
	// contains filtered or unexported fields
}

SeqSet is a sparse set of Seqs, stored as sorted, non-overlapping, non-adjacent inclusive ranges. The zero value is the empty set.

Used for the applied frontier's out-of-order exception set (nodestate.Cache: received Dots above each origin's contiguous head) and for gap-fill planning (internal/antientropy, internal/gapfillerchain).

func (*SeqSet) Add 

func (s *SeqSet) Add(v Seq)

Add inserts v into the set, coalescing with neighbours. No-op if already present.

func (SeqSet) Clone 

func (s SeqSet) Clone() SeqSet

Clone returns a deep copy of s.

func (SeqSet) Contains 

func (s SeqSet) Contains(v Seq) bool

Contains reports whether v is in the set.

func (SeqSet) IsEmpty 

func (s SeqSet) IsEmpty() bool

IsEmpty reports whether s holds no Seqs.

func (*SeqSet) PromoteContiguous 

func (s *SeqSet) PromoteContiguous(above Seq) Seq

PromoteContiguous returns the highest Seq forming a contiguous prefix from above+1 onward, removing those Seqs from the set. If no such prefix exists, returns above unchanged. Used by nodestate.Cache.MarkApplied to promote out-of-order receives into the contiguous frontier head.

func (SeqSet) Ranges 

func (s SeqSet) Ranges() []SeqRange

Ranges returns the underlying ranges in ascending order. The caller must not mutate the returned slice.

type Stamp 

type Stamp struct {
	Clock
	Origin Origin
}

Stamp is the LWW arbitration key: a Clock paired with the Origin that produced it. Total order on (Clock.WallTime, Clock.Logical, Origin) by construction — invariant (5) in CRDT.md.

Stamp is the lattice key from Almeida et al. δ-state §7.1 (LexPair<Clock, Origin>); its Dominates relation makes the per-cell layer a register CRDT.

func (Stamp) Dominates 

func (a Stamp) Dominates(b Stamp) bool

Dominates reports whether a strictly dominates b: a > b in lex order on (WallTime, Logical, Origin). Equal Stamps return false.

func (Stamp) Equal 

func (a Stamp) Equal(b Stamp) bool

Equal reports whether a and b are byte-identical Stamps.

func (Stamp) IsZero 

func (s Stamp) IsZero() bool

IsZero reports whether s is the zero value.

func (Stamp) String 

func (s Stamp) String() string

String renders a Stamp as "wall.logical@origin"; matches the lex order.

type TableID 

type TableID [16]byte

TableID is a 16-byte stable identifier for a replicated table. Names are presentation metadata; IDs survive RENAME and uniquely identify a table-generation across a DROP/CREATE cycle.

type UniquePredicate 

type UniquePredicate struct {
	Root *PredExpr
}

UniquePredicate is the compiled WHERE clause of a partial unique index (`CREATE UNIQUE INDEX … WHERE <predicate>`). It is keyed by ColumnID, not column name, so it survives column renames, and supports a restricted, deterministic grammar (boolean combinations of NULL tests and column-vs-literal comparisons) that both:

  • evaluates against a row image at the writer's reserve path (UniquePredicate.Eval), deciding whether a row participates in the coordinated reservation, and
  • renders back to SQL against current column names at the leaseholder's rebuild path (UniquePredicate.SQL), used as a WHERE filter when reconstructing the taken-set.

The grammar is restricted so the Go-side Eval and SQLite's own partial index agree on participation byte-for-byte: admission rejects anything outside it, anything collation-dependent, and any literal whose storage class would force an affinity coercion. A nil/zero UniquePredicate means "not partial" — every row participates.

func DecodeUniquePredicate 

func DecodeUniquePredicate(b []byte) (UniquePredicate, error)

DecodeUniquePredicate parses bytes produced by EncodeUniquePredicate and rejects trailing garbage.

func (UniquePredicate) Columns 

func (p UniquePredicate) Columns() []ColumnID

Columns returns the distinct ColumnIDs the predicate references, in first-seen order. Used by admission (dependency validation) and the rebuild path.

func (UniquePredicate) Eval 

func (p UniquePredicate) Eval(lookup func(ColumnID) ColValue) bool

Eval reports whether a row participates in the partial index: the predicate evaluates to TRUE (UNKNOWN/NULL counts as not-participating, matching SQLite WHERE semantics). lookup returns the row image's value for a column; it must return a ColNull ColValue for an absent column.

func (UniquePredicate) SQL 

func (p UniquePredicate) SQL(quoteName func(ColumnID) string) (string, error)

SQL renders the predicate as a parenthesized SQL boolean expression, resolving each ColumnID to a quoted identifier via quoteName. It is the inverse of admission's compile step and is stable under column renames (the tree holds IDs, quoteName supplies the current name). quoteName must return an already-quoted identifier.

type Update 

type Update struct {
	Table   TableID
	PK      PKBlob
	CL      uint64
	Changed []ColValue
}

Update carries only columns whose final value differs from first-touch evidence, plus the row's current CL on the writer.

func AsCellUpdate 

func AsCellUpdate(t CellTable, rec Record, rs RowState) (Update, bool)

AsCellUpdate normalizes a cell-group record into the Update shape the per-column arbitration paths consume. An Insert landing on a live row at the same CL is semantically an update (an UPSERT on the producer): its image arbitrates per column so it can't absorb columns it loses. A counter column's image value becomes a FormatDelta contribution — within a generation the cell is the sum of all contributions, so a concurrent same-PK insert adds its opening value instead of stomping increments already applied (CRDT.md F_counter). Returns ok=false for records that stay on the row-level path (Delete; Insert that bumps CL).

func (Update) Header 

func (r Update) Header() RecordHeader

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.