KDBS

One row, one name, for life: why KDBS keys never change

KDBS binds a primary key to one row for the life of the table. What that rule says, what it makes possible, and what it costs.

K KDBS team · · 5 min read
CHOI UK JIN

In most relational databases a primary key is a column with a uniqueness rule attached. You can update it. Once a row is deleted, its value is free, and the next insert may take it. Two rows can hold the same key at different times, and nothing in the database remembers that they were different rows.

KDBS treats the key as the row’s identity, not one of its fields. This post covers the rule, what follows from it, and what it costs.

The invariant

A primary key is bound to at most one committed row for the life of the table. It is never updated, and it is never given to another row, except after an explicit PURGE.

Every row begins with a 64-bit Keystone word, and the key lives in its lower 48 bits. It is stored there and nowhere else. Every write path enforces three rules:

  • An update cannot assign the key. The statement is refused when it is compiled, before anything is written.
  • A deleted row keeps its key. DELETE marks the row deleted and leaves it in place. The key stays taken.
  • An issued key is never issued again. Each table keeps a high-water mark, next_id. It is stored, never computed as max(id) + 1, so deleting the highest row does not make its key available again.

In the sandbox, each of these is a refusal. The engine’s messages call the key the tuple key:

kdbs> UPDATE accounts SET id = 9 WHERE id = 1
                          ^
ERR tuple key column 'id' cannot be updated at byte 20; it is the tuple's identity, not a field of it

kdbs> INSERT INTO accounts VALUES (100, 'grace', 300)
INSERTED oid=4002 id=100 page=132 slot=3
kdbs> DELETE FROM accounts WHERE id = 100
DELETED 1
kdbs> INSERT INTO accounts VALUES (100, 'grace', 300)
                                   ^
ERR duplicate tuple key 100: a row with this key was deleted; PURGE frees its key (page 132 slot 3) (byte 29)

A rolled-back insert does not bind its key. Only a commit does. The only way back is PURGE, an explicit, admin-only statement. It frees the keys of deleted rows once no open transaction can still see them.

What the rule buys

A stored key never points at the wrong row

A key copied out of the database ends up in many places: a URL, a cache entry, a log line, an event on a queue, a support ticket, an agent’s memory of what it did. With reusable keys, each copy can silently start pointing at a different record. Customer 1042 is deleted, a new customer gets 1042, and an old email link opens the new customer’s account.

In KDBS a stored key can dangle: its row may have been deleted. It cannot be misdirected. That difference is easy to handle. “Not found” is an honest answer. “Found, but someone else” is a bug no code downstream can detect.

Structures can hold keys instead of addresses

Inside the engine, many structures need to remember rows: secondary indexes, Cabins, Waystone trails, and the per-group totals behind assertions. All of them store the key.

Because a key always names the same row, each structure can verify what it finds cheaply. A reader compares the stored key with the key in the slot it reached. If they match, the row is the right one. If not, the reader takes the normal path. This check is what makes the learned structures in KDBS advisory. A stale trail or location hint costs a lookup, and it can never return the wrong row. The engine can therefore build them, trust them for speed and throw them away without any risk to correctness.

Rows stay where they are

KDBS rows have a fixed length per table, and an UPDATE writes the new version in the same page and slot. Together with stable keys, a structure that remembers “key 42 was at page 130, slot 3” stays right far more often than it would on an engine where updates relocate rows. When it is wrong, the key check catches it.

Rules about history become checkable

A rule like “an order is never FINALIZED without first being CHECKED” is about a row’s history. KDBS can enforce it without storing any history, because a row’s history cannot restart under the same identity. The next post on Transitions shows how. They depend on this invariant so directly that PURGE is refused on any table that carries one.

Logs and audits mean what they say

When a log line says “row 1042 changed”, there is exactly one row it can mean, for as long as the table exists. An auditor does not need to work out which 1042 it was.

What it costs

Each of these follows from the rule, and the documentation states them directly:

  • Keys are unique, not gapless. A failed insert can use up an issued key. Nothing in the engine depends on keys being consecutive, and applications should not either.
  • Deleted rows keep their keys and their space until PURGE runs. A deleted key cannot be reused before that.
  • PURGE is deliberate. It runs in autocommit only, needs the admin role, and waits up to one second for older readers before refusing with a retryable error. No background task purges for you.
  • A purged key is a new identity. A system outside the database that recorded the old key must treat a row inserted later under it as a different record. The purge is written to the log.
  • No key changes. To give a row a new key, delete it and insert a new row.
  • One integer key per table. The key is the first column and an integer up to 2^48 − 1. There are no composite or text primary keys. A natural key, such as an email address, belongs in an ordinary column with an index.

Try it

The sandbox runs a real KDBS instance. Delete a row, then try to insert its key again. Then run SHOW BUDGET and look at next_id for accounts. The mark only moves forward.

For the complete rules, see Row identity and primary keys.

More from the blog