Layer 01: the KV abstraction

Source: rad/01_kv (package kv), with subpackages keyenc, kvslate, and kvtest. This is the bottom of the layer stack described in rad/doc.go and enforced by scripts/check_layers.sh: a package under rad/NN_* may import only same-or-lower-numbered layers, so kv imports nothing from the rest of Rad. Everything above it — catalog, IR, planner, executor, frontend — reaches storage exclusively through the interfaces defined here.

What the layer is, and is not

Package kv defines a minimal ordered key-value store with optimistic transactions. Its entire vocabulary is []byte keys, []byte values, and half-open key ranges. It knows nothing about the catalog, tables, rows, columns, indexes, or the IR's value model; the words "table" and "row" do not appear in its API. The one semantic commitment it makes is ordering: keys iterate in ascending lexicographic byte order, which is what lets the layers above encode tuples such that a range scan returns rows in semantic order.

The companion subpackage keyenc is the other half of that commitment. It is still storage vocabulary — bytes and Go primitives, no rows or types — but it provides the order-preserving encodings (EncodeInt64, EncodeFloat64, EncodeString, EncodeBool, EncodeNull) that layer 05 composes into row-key tuples. Splitting them this way keeps the contract clean: kv promises byte order, keyenc makes byte order coincide with value order.

The KV interface

kv.KV is the plain read/write surface:

type KV interface {
    Get(ctx context.Context, key []byte) ([]byte, bool, error)
    Put(ctx context.Context, key []byte, value []byte) error
    Delete(ctx context.Context, key []byte) error
    Scan(ctx context.Context, start, end []byte) (Iterator, error)
}

Get distinguishes "missing" from "error" with its boolean: a missing key is (nil, false, nil), never an error. Put overwrites unconditionally. Delete of a missing key is not an error. There is no compare-and-swap and no versioning at this level; conditional logic belongs in transactions.

Scan iterates keys in [start, end) — start inclusive, end exclusive — in ascending lexicographic order. A nil start means "from the beginning" and a nil end means "to the end"; Scan(ctx, nil, nil) walks the whole store. There is no descending scan and no prefix parameter: a prefix scan is spelled Scan(ctx, prefix, keyenc.PrefixEnd(prefix)). PrefixEnd returns the smallest key greater than every key with the given prefix (increment the last non-0xFF byte, truncate after it), and returns nil — meaning "unbounded" — when no such key exists (empty or all-0xFF prefix). That nil return composes correctly with Scan's nil-end convention, so the prefix idiom is total.

Iterators

type Iterator interface {
    Next() bool
    Key() []byte
    Value() []byte
    Err() error
    Close() error
}

The usage protocol is the standard Go iterator dance: loop on Next, then check Err, then Close. Key and Value are documented valid only until the next Next; callers that hold data across steps must copy (05_exec/scanrange.go does exactly this before its interleaved Get).

Interleaving other operations with an open iterator is part of the de facto contract even though kv.go does not spell it out: the executor's indexRangeIterator performs a point Get against the same view between every Next while walking an index range, and the whole engine test suite exercises this against SlateDB. What is not defined is the visibility of writes made to the same transaction after Scan returned — a Txn scan reflects the transaction's buffered writes as of the Scan call (the conformance suite's ScanSeesOwnWrites pins this), but nothing tests or promises what an already-open iterator shows if you Put mid-iteration. Upper layers do not do that; new code should not either.

One lifecycle rule is explicit: iterators obtained from a Txn must be closed before Commit.

Errors

The package defines exactly one sentinel, kv.ErrConflict, checked with errors.Is (layer 05 re-exports the check as exec.IsConflict). Everything else is an opaque implementation error. Absence is signalled by boolean returns, never by error values, so there is no ErrNotFound to forget to check.

Transactions

kv.TransactionalKV is what backends implement: the plain KV surface plus Begin(ctx, level) (Txn, error). Plain operations on the store are implicitly single-op transactional. A Txn is itself a KV — this embedding is the load-bearing design decision of the layer, because it means every function above that takes a kv.KV "view" works identically inside or outside a transaction. The catalog's DDL helpers and the executor's constraint checks are all written against kv.KV and get transactionality for free (see catalog.Catalog.ddl, exec.Engine.Txn).

A Txn reads from a stable snapshot taken at Begin, overlaid with its own buffered writes: its own Puts appear in its Gets and Scans, its own Deletes hide keys, and concurrent commits by others are invisible until it finishes. Writes are buffered in memory and applied atomically and durably at Commit. A Txn is not safe for concurrent use by multiple goroutines.

Concurrency control is optimistic, with the isolation level chosen at Begin:

• kv.Snapshot — detects write-write conflicts only: two transactions that both write the same key cannot both commit; the second gets ErrConflict. Susceptible to write skew (the conformance suite deliberately proves the skew is allowed at this level).
• kv.SerializableSnapshot — additionally detects read-write conflicts. Both point reads and the requested bounds of scans are validated at commit against keys committed by others after Begin. The bounds rule is what makes phantom detection work: scanning an empty range records the range itself, so a concurrent insert anywhere in it conflicts even though the scan returned nothing. This is precisely what makes optimistic unique-index existence checks sound (kvtest.testPhantomRangeConflict models one).

Conflicts surface only at Commit, as an error wrapping ErrConflict; there is no locking and no early abort. The transaction is unusable after Commit returns, success or failure. Rollback discards the transaction and is a no-op after Commit or a prior Rollback, so defer txn.Rollback() is always safe — every caller in the tree uses that pattern.

Writes always run under SerializableSnapshot: catalog.Catalog.ddl and exec.Engine.Begin both hard-code it. Snapshot is the read-side level — 05_exec opens one per autocommit statement (Engine.Execute, GetByPrimaryKey, ScanTable, ScanIndex) so schema resolution and data reads share a single storage moment, then discards it with Rollback.

The SlateDB adapter

kvslate.Store adapts SlateDB, via the slatedb.io/slatedb-go uniffi bindings, to kv.TransactionalKV. The mapping is nearly one-to-one because SlateDB already speaks the same language: raw byte keys in lexicographic order, range scans with inclusive-start/exclusive-end bounds (kvslate.keyRange), and native transactions. kv.Txn maps onto slatedb.DbTransaction; kv.Snapshot and kv.SerializableSnapshot map onto SlateDB's identically-named isolation levels; commit-time slatedb.ErrErrorTransaction is wrapped as kv.ErrConflict. Commit uses SlateDB's default write options, which await durability.

kvslate.Open(name, storeURL) opens a database on an object store resolved from a URL — "file:///path" for a real deployment, "memory:///" for tests. Context handling in the adapter is entry-only: every method checks ctx.Err() before calling into SlateDB, but a running scan or commit is not interruptible mid-flight, and iterator Next does not consult the context at all. The adapter also carries uniffi lifecycle chores (Destroy on transactions, iterators, and commit handles) that the kv interfaces deliberately hide.

There is no pure-Go in-memory implementation of kv.TransactionalKV. The "in-memory test double" that rad/doc.go mentions is SlateDB itself on a memory:/// object store — which means every test in the repository that touches storage, from 02_catalog up through e2e, needs the native SlateDB library (CGO_LDFLAGS="-L<repo>/lib -Wl,-rpath,<repo>/lib", per the kvslate package comment).

Key encoding

keyenc implements CockroachDB-style order-preserving encodings. Every encoded value starts with a type tag (TagNull 0x01 < TagBool 0x02 < TagInt64 0x03 < TagFloat64 0x04 < TagText 0x05), so mixed-type sequences order deterministically — NULL before everything — and decode unambiguously via Peek. Within a type, byte order matches value order: integers flip the sign bit and store big-endian; floats flip the sign bit when non-negative and all bits when negative (callers must reject NaN — its ordering is undefined and nothing here checks); strings escape interior NUL as {0x00, 0xFF} and terminate with {0x00, 0x01}, which both preserves order ("app" < "apple") and prevents prefix collisions between distinct tuples.

Encodings are self-delimiting, so values concatenate into tuple keys with no separator, and the decoders (DecodeInt64, DecodeString, …) each return the byte count consumed so tuples split back apart. Note the tag ordering's corollary: int64 and float64 are different types to the encoding, so a key position that mixes them does not sort numerically across the two — every encoded float sorts after every encoded int. A column must encode with one consistent tag; that discipline belongs to layer 05, not here.

Invariants downstream layers rely on

Three properties of this layer are load-bearing for correctness above it. First, ascending lexicographic scan order plus keyenc's order preservation is why 05_exec can serve an ordered or range-bounded query as a single Scan over /rad/data/<table>/... keys with no sort. Second, SerializableSnapshot's validation of scan bounds (not just returned keys) is why the executor's read-then-write patterns — unique-index existence checks, foreign-key checks — are sound without locks; a phantom insert into a checked range forces ErrConflict and the caller retries the whole exec.Engine.Txn callback. Third, Txn being a kv.KV is why the entire catalog and executor codebase is written once against views rather than twice against store-vs-transaction.

Testing

kvtest.Run is the executable definition of the transaction semantics: a conformance suite over any kv.TransactionalKV, covering commit visibility, rollback idempotence (including rollback-after-commit being a no-op), snapshot read stability, scans seeing own writes and hiding own deletes, write-write conflicts under both levels, read-key conflicts, phantom range conflicts, and the write-skew pair (allowed under Snapshot, blocked under SerializableSnapshot). kvslate_test.go runs the suite against SlateDB on memory:/// (TestTransactionConformance) and adds adapter-specific checks: lexicographic ordering with binary keys, [start, end) bound semantics, and the PrefixEnd prefix-scan idiom against realistically shaped /rad/data/... keys.

keyenc is tested three ways: ordered fixtures plus randomized order-agreement checks (bytes.Compare of encodings must agree with value comparison over a thousand random pairs), round-trip decoding including random binary strings with NUL and 0xFF edge cases, and testable examples (example_test.go) that double as usage documentation for order preservation, self-delimiting tuples, and PrefixEnd. Cross-type tag ordering and the embedded-NUL prefix-safety property each have a dedicated test, since index correctness depends on both.