Consistency model

fdyno executes every API operation as a single FoundationDB transaction. Because FoundationDB provides strict serializability (serializable isolation together with a real-time order on transactions), and fdyno inherits that guarantee for every operation it serves. This page defines the guarantee precisely, states the anomalies it rules out, and is explicit about where it stops.

It uses the vocabulary of the Jepsen consistency reference and the formal isolation literature, so fdyno's behavior can be compared, in the same terms, against any other database.

The guarantee

Every fdyno operation appears to execute atomically, at a single instant between the moment the request is accepted and the moment its response is returned, in an order consistent with real time.

That is strict serializability, the strongest model in the standard hierarchy. It is the conjunction of two independent properties:

• Serializability: a multi-object, transactional property. The operations admit a total order, and each appears to execute without interleaving against any other, over the database as a whole. This covers predicate operations such as a Query or Scan, not only the individual keys a transaction names.¹
• Linearizability: a real-time property. If operation A returns before operation B is submitted, A is ordered before B. A client never sees the database move backwards in time.²

Serializability on its own permits orderings that are internally consistent yet disagree with wall-clock reality: a transaction may be placed in the order as though it ran in the past, missing a write that had already committed before it began.³ Strict serializability forbids exactly those orderings. fdyno provides the strict form because each FoundationDB transaction reads at a version no earlier than any commit that has already returned, and commits at a later version still.

Where fdyno sits

Strict serializability implies every weaker model beneath it. A system that is strictly serializable is automatically serializable, sequentially consistent, linearizable, snapshot-isolated, repeatable-read, read-committed, and causally consistent. fdyno satisfies all of them.

graph TD
    SS["Strict Serializable<br/><b>fdyno</b>"]:::me
    SER["Serializable"]
    LIN["Linearizable"]
    SEQ["Sequential"]
    SI["Snapshot Isolation"]
    RR["Repeatable Read"]
    RC["Read Committed"]
    CAUSAL["Causal"]
    RU["Read Uncommitted"]

    SS --> SER
    SS --> LIN
    LIN --> SEQ
    SEQ --> CAUSAL
    SER --> SI
    SI --> RR
    RR --> RC
    RC --> RU
    CAUSAL --> RC

    classDef me fill:#b8ff36,stroke:#6fae00,stroke-width:3px,color:#0a0f08;

An arrow reads "is at least as strong as." Everything fdyno sits above is provided for free; the table of anomalies below is, in effect, empty.

Phenomena ruled out

Isolation levels are defined by the phenomena they forbid, concrete patterns of reads and writes. Strict serializability forbids all of them. The standard anomalies (Berenson et al.; Adya; Bailis et al.) and the mechanism that prevents each in fdyno:

Phenomenon	The anomaly	Why it cannot occur in fdyno
G0: Dirty write	Two transactions interleave writes to the same keys.	Buffered writes apply atomically at one commit version; the version order is the global commit order, so no interleaving can form a write-write cycle.
G1a: Aborted read	A transaction reads a value an aborted transaction wrote.	Uncommitted writes are never visible; reads see only a committed snapshot.
G1b: Intermediate read	A transaction reads a non-final value of another.	Only the committed end state is visible; buffered intermediate writes are private.
G1c: Circular information flow	A dependency cycle among committed transactions.	A serializable history has an acyclic dependency graph by definition.
P4: Lost update	Both transactions read a key, both write it, one update is silently dropped.	The second committer's read of that key is invalidated by the first commit, forcing a re-run.
G-single: Read skew	A read observes one transaction's write but not another, related one.	All reads in one operation come from a single MVCC snapshot version.
G2: Write skew	Each transaction reads what the other writes; both commit and break an invariant.	FoundationDB detects the read–write (anti-dependency) conflict and re-runs one transaction.
Phantom	A predicate read returns a different set when re-evaluated.	A range read registers a read-conflict range; a concurrent insert into that range conflicts.
Fractured read	A reader sees some, but not all, of a transaction's writes.	Commit is atomic and reads are snapshot-isolated: a multi-key write is all-or-nothing to any reader.

Each anomaly requires a non-serializable history. FoundationDB rejects any transaction whose read set was invalidated by a concurrent commit and re-runs it transparently, so none of these is observable.

Dependencies

The phenomena above are defined more precisely in terms of dependencies between transactions, the formalism behind Adya's Direct Serialization Graph (DSG). Each object x has a sequence of versions x₀, x₁, x₂, …; a transaction reads some versions and installs new ones. Three kinds of edge connect transactions:

• Write–read (wr): Tᵢ → Tⱼ when Tⱼ reads a version that Tᵢ wrote. Tⱼ observed Tᵢ's effect.
• Write–write (ww): Tᵢ → Tⱼ when Tⱼ installs the version of x that immediately follows Tᵢ's. Tⱼ overwrote Tᵢ.
• Read–write anti-dependency (rw): Tᵢ → Tⱼ when Tᵢ reads a version of x and Tⱼ installs the next version. Tᵢ's read is stale with respect to Tⱼ's write.

A consistency model is a rule about which cycles this graph may contain. Serializability is the strongest: it forbids every cycle. Weaker models permit specific ones: snapshot isolation, for instance, permits a cycle of two rw edges between two transactions, which is exactly write skew:

graph LR
    T1["T₁ · read y, write x"] -. rw .-> T2["T₂ · read x, write y"]
    T2 -. rw .-> T1

fdyno forbids all cycles because FoundationDB's conflict detection corresponds directly to these edges:

• A transaction declares a read-conflict range for every key or range it reads and a write-conflict range for every key it writes.
• At commit, the resolver checks the committing transaction's read-conflict ranges against the write-conflict ranges of every transaction that committed after its read version. An overlap is exactly an rw anti-dependency from a newer write into the committing transaction, the edge that would close a cycle. That commit is rejected and re-run.
• ww edges cannot form a cycle on their own: buffered writes apply atomically at a single commit version, and the version order is the total order of commit versions, which is acyclic by construction.

The only edges that could create a cycle (anti-dependencies against a concurrently committed write) are precisely the ones FoundationDB refuses to admit. The DSG over committed transactions therefore stays acyclic, which is the graph-theoretic statement of serializability; the commit-version order is what additionally makes it strict. This is the same guarantee as the phenomena above, read off the dependency graph instead of pattern by pattern. See Jepsen's Dependencies reference for the general theory.

Reads are always current

DynamoDB offers two read modes: eventually consistent (the default, cheaper, and permitted to return stale data) and strongly consistent (ConsistentRead = true). fdyno reads from a FoundationDB snapshot taken at a version that reflects every prior commit, so:

• a GetItem returns the latest committed value whether or not ConsistentRead is set, so there is no separate eventually-consistent path;
• there is no replica lag to observe, because reads are served from the transactional snapshot rather than from a follower.

fdyno still honors the flag where DynamoDB attaches meaning to it. For instance, it rejects ConsistentRead = true against a global secondary index with the same ValidationException DynamoDB returns, but the underlying read is consistent either way.

Secondary indexes share the write's transaction

A base-item write and all of its global and local secondary-index entries commit at a single FoundationDB version. No reader can interleave between the base write and its index updates: a query against an index reflects a write the instant that write commits. This is strictly stronger than DynamoDB, whose global secondary indexes are eventually consistent and may briefly omit a just-written item. The cost, index maintenance on the write's critical path, is examined in Secondary indexes that never lag.

Streams are a total order

Change-stream records are written with a FoundationDB versionstamp in the same transaction as the data change. A versionstamp is unique and monotonic, assigned at commit, so stream order equals commit order equals the serialization order. A consumer reading the stream in versionstamp order observes exactly the sequence of committed states, with no gaps, duplicates, or reordering. Each table's stream is a single logical shard. See Change streams.

Boundaries

Strict serializability is a guarantee about a single operation. Three consequences follow directly and are worth stating plainly.

Multi-request sequences are ordered by real time, not grouped into one transaction. Two separate API calls are two transactions. They are individually strict serializable and real-time ordered relative to each other, but fdyno does not place them in a shared transaction. To make several reads and writes atomic, use TransactWriteItems / TransactGetItems, which run as one FoundationDB transaction.

A paginated Query or Scan is consistent per page, not across pages. Each page is one read transaction at its own version, so a scan spanning multiple round-trips (via LastEvaluatedKey) may reflect writes that committed between pages. DynamoDB carries the same caveat. A Query or Scan whose entire result fits in one response is a single consistent snapshot.

fdyno is CP: consistent, but not available under a partition. Serializability is incompatible with total availability: a database cannot both guarantee a serial order and let every node make progress while the network is partitioned.⁴ FoundationDB needs a quorum to assign read and commit versions; during a partition the minority cannot commit, and the cluster pauses writes until it recovers. fdyno chooses consistency over availability, the same tradeoff DynamoDB makes for its strongly-consistent and transactional operations.

Compared to DynamoDB

Property	fdyno	DynamoDB
Single-item read	Strict serializable (always current)	Eventually consistent by default; strongly consistent on request
Conditional / single-item write	Strict serializable	Linearizable per item
Secondary-index read	Strict serializable (GSI and LSI)	LSI strong; GSI eventually consistent
Multi-item transaction	Strict serializable	Serializable (TransactWriteItems)
Cross-page scan	Per-page snapshot	Per-page snapshot
Availability under partition	CP (writes pause)	CP for strong & transactional operations

On every row, fdyno is at least as strong as DynamoDB. This is a deliberate point in the design space, not a verdict on DynamoDB: eventually-consistent reads and indexes are what let DynamoDB serve some reads from any replica and keep indexing off the write path, which buys availability and throughput that a strictly-serializable store gives up.

How FoundationDB provides it

fdyno adds no consistency machinery of its own; it delegates to FoundationDB. Each request runs through Transact (read-write) or ReadTransact (read-only):

1. Read version. The transaction obtains a read version that is at least the commit version of every transaction that has already returned success. All reads observe a single MVCC snapshot at that version.
2. Buffered writes. Writes (base item, index entries, stream record, idempotency token) accumulate in the transaction and stay invisible to others until commit.
3. Conflict resolution. At commit, FoundationDB's resolver checks the transaction's read set against every commit in the window after its read version. If a read was invalidated, the commit is rejected and Transact transparently re-runs the whole function. This optimistic concurrency control is what makes the order serializable.
4. Durable, ordered commit. Accepted transactions receive a commit version from a single sequencer, a global total order, and are persisted on the transaction logs before success is returned. The commit version exceeds the read version, which is what makes the order strict (real-time-respecting).

The practical price is contention-dependent retries and a per-transaction size and time budget. Hot keys raise the conflict rate, and a single transaction must fit FoundationDB's limits; fdyno surfaces these as the same TransactionConflictException, ValidationException, and item-size errors a DynamoDB client already handles.

References

• Maurice P. Herlihy and Jeannette M. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM TOPLAS, 1990.
• Christos Papadimitriou. The Serializability of Concurrent Database Updates. JACM, 1979.
• Hal Berenson, Phil Bernstein, Jim Gray, Jim Melton, Elizabeth O'Neil, Patrick O'Neil. A Critique of ANSI SQL Isolation Levels. SIGMOD, 1995.
• Atul Adya. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. PhD thesis, MIT, 1999.
• Atul Adya, Barbara Liskov, Patrick O'Neil. Generalized Isolation Level Definitions. ICDE, 2000. (The Direct Serialization Graph and the G0/G1/G2 phenomena.)
• Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica. Highly Available Transactions: Virtues and Limitations. VLDB, 2014.
• Kyle Kingsbury. Consistency Models. jepsen.io/consistency
• Jingyu Zhou et al. FoundationDB: A Distributed Unbundled Transactional Key Value Store. SIGMOD, 2021.

---

1. Serializability applies to the system as a whole, including predicates ("the set of items where status = 'open'"), not only to the keys a transaction explicitly reads. This is what makes phantom prevention part of the guarantee rather than an add-on. ↩

2. Linearizability is a single-object model in its original formulation; strict serializability extends the same real-time intuition to multi-object transactions. ↩

3. A purely serializable database is, for example, permitted to answer every read with the empty state by ordering all reads before all writes, a legal serial order that is useless in practice. Real-time order is what rules this out. ↩

4. Bailis et al. show that serializability, snapshot isolation, and several other models cannot be provided by a totally-available system: under a partition, a serializable database must sacrifice availability on at least one side. ↩