Strict serializability on FoundationDB

A DynamoDB-compatible API can be implemented over almost any storage engine, and the isolation a client actually gets is decided entirely by that engine. fdyno runs on FoundationDB, which provides strict serializability, the strongest model in the standard hierarchy. This post traces how that guarantee reaches the wire, what it rules out, and what it costs.

What "strict serializable" means

Two properties have to hold at once.

Serializability says the operations admit some total order in which each runs without interleaving, equivalent to having executed one at a time. Linearizability adds a real-time constraint: if operation A returns before operation B begins, A precedes B in that order. A database that is serializable but not linearizable is allowed to answer a read as though it ran in the past, missing a write that had already committed. Strict serializability is the conjunction: a total order that also respects wall-clock time.

It is the model most people assume a database has and most distributed databases do not provide, because the real-time constraint is the expensive half.

The path to the wire

Every fdyno request (a PutItem, a conditional UpdateItem, a Query page, a TransactWriteItems) runs inside one FoundationDB transaction:

val, err := s.db.Transact(func(tr fdb.Transaction) (any, error) {
    // read current item, evaluate the condition expression,
    // write the base item, every GSI/LSI entry, the stream
    // record, and the idempotency token, all on tr.
    return result, nil
})

Transact is not a thin wrapper. It encloses FoundationDB's optimistic concurrency protocol:

1. Read version. The transaction is stamped with a read version at least as large as the commit version of any transaction that has already returned. Reads observe a single MVCC snapshot at that version, never a half-applied write, never a follower's stale copy.
2. Private writes. Mutations buffer on the transaction object and are invisible to everyone else until commit.
3. Resolution. At commit, the resolver compares the transaction's read set against every commit in the window after its read version. If a key it read was overwritten in that window, the commit is rejected.
4. Re-run. On rejection, Transact calls the function again with a fresh read version. The application code is idempotent by construction; it recomputes from the new snapshot, so the retry is invisible above the storage layer.
5. Ordered commit. An accepted transaction gets a commit version from a single sequencer (a global total order) and is made durable on the transaction logs before success returns. The commit version is strictly greater than the read version, which is what makes the order real-time-respecting.

Steps 3–4 are serializability; step 5's version ordering is linearizability. Together they are strict serializability, and fdyno gets them by delegation, not by building a concurrency-control layer of its own.

Two anomalies that cannot happen

Lost update. Two clients read the same counter and each write back an incremented value:

T1: read x=5 ............................ write x=6
T2:        read x=5 ... write x=6

Under read-committed or snapshot isolation this can lose an update. In fdyno, whichever transaction commits second had read x=5, but x was overwritten after its read version, so the resolver rejects it, Transact re-runs against x=6, and it writes x=7. No update is lost. (The DynamoDB-idiomatic form, an ADD update expression, avoids the read entirely and is also atomic.)

Write skew. Two transactions each read a shared invariant and write different keys in a way that, together, breaks it, the classic "at least one doctor on call" example. Snapshot isolation famously permits this, because the two transactions touch disjoint keys and never write-conflict. FoundationDB tracks read–write conflicts, not only write–write, so each transaction's read of the other's written key is a conflict: one is re-run and the invariant holds.

The same mechanism prevents phantoms. A range read registers a read-conflict range over the whole scanned interval, so an insert into that range by a concurrent transaction conflicts. Serializability over predicates is part of the guarantee, not an extra.

Where it stops

Strict serializability is a property of a single operation. It does not silently extend across requests:

• A multi-call sequence is not one transaction. Two API calls are two transactions, individually strict serializable and real-time ordered, but not atomic together. The primitive for "all of these or none" is TransactWriteItems, which is one FoundationDB transaction.
• A paginated scan is consistent per page, not across pages. Each page is its own read transaction at its own version, so a multi-round-trip Scan can observe writes that landed between pages. DynamoDB has the same boundary. A result that fits in one response is a single snapshot.

What it costs

The real-time half is not free, and it is worth being precise about the bill.

• Availability. Strict serializability cannot be totally available: under a network partition the minority side cannot assign commit versions and must stop accepting writes. fdyno is CP. This is the same choice DynamoDB makes for its strongly-consistent and transactional operations, and the opposite of the choice that eventually-consistent reads exist to offer.
• Contention. Optimistic concurrency converts contention into retries. A hot key raises the conflict rate; fdyno surfaces it as TransactionConflictException, which a DynamoDB client already retries.
• Budgets. A transaction must fit FoundationDB's size and time limits, which is part of why TransactWriteItems is capped and why very large items are chunked.

None of these is a defect to be engineered away; they are the price of the model. The point of building on FoundationDB is that the price is paid by a storage engine that was designed, and is tested, to pay it correctly, leaving fdyno to translate the DynamoDB wire protocol on top.