FoundationDB: The Database That Powers Cloud Giants

The most valuable property a database can offer isn't speed, scale, or feature richness—it's correctness. A faster database that occasionally loses data or returns wrong results is worse than a slower one that's always right. Yet achieving correctness in distributed systems is extraordinarily difficult, and most databases make compromises that push complexity onto application developers.

FoundationDB takes an uncompromising stance: strict serializability for all transactions, with no exceptions. This isn't marketing language—it's a technical claim backed by the most rigorous testing methodology in the database industry. Every read, every write, every transaction—no matter how many keys it touches, no matter how many concurrent transactions are running—behaves as if it executed in complete isolation, in some total order consistent with real time.

This guarantee simplifies application development dramatically. You don't need to reason about race conditions, lost updates, phantom reads, or write skew. If your logic is correct for a single-threaded, single-user scenario, it's correct for millions of concurrent users. The database handles concurrency; you handle business logic.

In this page, we'll explore what strict serializability means, how FoundationDB achieves it, and why this guarantee—rare among distributed databases—is worth its cost.

Before appreciating FoundationDB's guarantees, we need to understand the landscape of transaction isolation—what guarantees are possible, what anomalies each level prevents, and where most databases fall in this hierarchy.

The Problem: Concurrent Transactions

When multiple transactions execute concurrently, they can interfere with each other in subtle ways. Consider two transactions running simultaneously:

• T1: Reads account balance, adds $100, writes new balance
• T2: Reads account balance, subtracts $50, writes new balance

If the initial balance is $1000, and both transactions read $1000 before either writes:

• T1 writes $1100
• T2 writes $950 (based on its read of $1000)

The final balance is $950 or $1100 (depending on who writes last), but it should be $1050. This is a lost update—one of many possible concurrency anomalies.

The Isolation Level Hierarchy:

Database isolation levels define which anomalies are prevented. Each level trades correctness for performance:

Defining the Anomalies:

• Dirty Read: Transaction reads uncommitted data from another transaction
• Lost Update: Two transactions read-modify-write; one update is overwritten
• Non-Repeatable Read: Same query returns different results within one transaction
• Phantom Read: Range query returns different rows due to inserts by another transaction
• Write Skew: Two transactions read overlapping data, make disjoint updates, collectively violate a constraint

Serializability vs. Strict Serializability:

Regular serializability guarantees that the outcome of concurrent transactions is equivalent to some serial execution. But that serial order might not respect real time—a transaction that started and finished before another might appear to execute after it in the serialization order.

Strict serializability (also called linearizability for single objects, or external consistency) adds the constraint that if transaction T1 commits before transaction T2 starts, then T1 must appear before T2 in the serialization order. The database's behavior respects real-time ordering.

This distinction matters for user expectations. If I transfer money and you refresh the page, you should see the transfer. Strict serializability guarantees this; plain serializability does not.

FoundationDB uses optimistic concurrency control (OCC) to achieve serializable transactions. Unlike pessimistic approaches (locks), optimistic control allows transactions to proceed without coordination, validating at commit time that no conflicts occurred.

How OCC Works in FoundationDB:

1. Transaction Start: Client begins a transaction, receiving a read version (a timestamp in the transaction log)

2. Read Phase: Client reads keys from the database. FoundationDB tracks all keys read by the transaction (the read set) and their versions.

3. Write Phase: Client accumulates writes locally (the write set). Writes are not sent to the database until commit.

4. Commit: Client sends the entire write set to a special node called the proxy. The proxy forwards to the resolver for conflict checking.

5. Conflict Check: The resolver checks if any key in the read set was modified by another transaction that committed after this transaction's read version but before now. If so, the transaction conflicts and must abort.

6. Commit or Abort: If no conflicts, the transaction is assigned a commit version and written to the transaction log. If conflicts, the client receives an error and must retry from scratch.

Why Optimistic over Pessimistic?

Optimistic concurrency control has several advantages for FoundationDB's design goals:

1. No Distributed Locking: Pessimistic locking in a distributed system requires coordinating lock acquisition across nodes—expensive and deadlock-prone.

2. Low Latency for Non-Conflicting Transactions: Most transactions in well-designed applications don't conflict. OCC allows these to proceed without any coordination overhead.

3. Simple Client Model: The client library is stateless. Reads and writes are just data; there's no lock state to manage or clean up on failure.

4. Natural Retry Semantics: When conflicts occur, the client simply retries the entire transaction. The @fdb.transactional decorator handles this automatically.

The Cost of Optimism:

The downside is wasted work on conflicts. If transactions frequently conflict, each abort means throwing away computation and retrying. For workloads with high contention (many transactions accessing the same keys), this can be problematic.

FoundationDB mitigates this through:

• Short transactions: The 5-second transaction time limit encourages small, focused transactions
• Conflict ranges: Read entire ranges to avoid false conflicts on specific keys
• Atomic operations: Operations like add() don't require reading, reducing conflict potential

Conflict management is central to effective FoundationDB use. Understanding exactly when conflicts occur—and when they don't—enables designing schemas and access patterns that maximize throughput.

Precise Conflict Rules:

1. Read-Write Conflict: Transaction T1 reads key K at version V. Transaction T2 writes K and commits with version V' > V. T1 tries to commit → CONFLICT.

2. Write-Write Conflict: Transaction T1 writes key K. Transaction T2 writes K. Both try to commit → one succeeds, one conflicts.

3. No Read-Read Conflict: Multiple transactions can read the same key at the same version. This never causes conflicts.

4. No Write-Only Conflict with Unrelated Reads: T1 reads key A. T2 writes key B. No conflict (their key sets are disjoint).

Range Conflicts:

FoundationDB also supports conflict ranges for range reads:

Strategies for Reducing Conflicts:

1. Shard Hot Keys

A single counter that every transaction increments will conflict constantly. Shard it:

# Instead of one key that everyone fights over:
tr.add(b'page_views', pack((1,)))  # High contention!

# Spread across shards:
shard = random.randint(0, 99)
tr.add(pack(('page_views', shard)), pack((1,)))  # Low contention

2. Use Atomic Operations

Atomic operations (add, min, max, and, or) don't require reading the current value. They add to the write set but not the read set, meaning:

• Two add operations on the same key don't conflict
• An add won't conflict with a transaction that only reads the key

# DON'T (creates read-write conflict):
count = int(tr[b'counter'] or 0)
tr[b'counter'] = str(count + 1).encode()

# DO (atomic, no read conflict):
tr.add(b'counter', pack((1,)))

3. Minimize Transaction Duration

Longer transactions have more time for conflicts to accumulate. FoundationDB enforces a 5-second maximum, but aim for milliseconds:

• Pre-fetch data before the transaction
• Do computation outside the transaction
• Use the transaction only for the atomic read-modify-write

4. Use Versionstamps for Unique Keys

Inserting with unique keys eliminates write-write conflicts:

# Events with unique, time-ordered keys never conflict on insert:
tr.set_versionstamped_key(
    pack(('events', Versionstamp())),
    event_data
)

How do you know a database's correctness claims are true? This is a profound challenge. Distributed systems have astronomical numbers of possible states—testing every scenario is impossible. Bugs may lurk in rare race conditions that occur once in a million operations, in failures that happen only during recovery, or in interactions between seemingly unrelated components.

FoundationDB's answer is deterministic simulation testing—a revolutionary testing methodology that has found bugs that conventional testing would never catch. This approach is so effective that FoundationDB's developers have stated they "would rather run simulations than have more users" for finding bugs.

The Core Insight:

Traditional distributed systems testing is non-deterministic. You run the system, inject failures, and hope to trigger bugs. If a test fails, you often can't reproduce it—the exact timing of events is different each run.

FoundationDB takes a different approach:

1. Single-Threaded Simulation: The entire distributed system—multiple nodes, network, disk I/O—runs in a single thread, with a custom scheduler controlling event ordering.

2. Deterministic Pseudo-Random: All randomness (timings, failures, scheduling decisions) comes from a seeded PRNG. Given the same seed, the exact same execution replays.

3. Fault Injection: The simulator can inject any failure—network partitions, disk errors, machine crashes, Byzantine behavior—at any point in execution.

4. Invariant Checking: After every state change, the simulator verifies that all system invariants hold (no lost writes, no inconsistent reads, etc.).

What Makes This Work:

1. Flow: FoundationDB is written in Flow, a custom C++ extension that adds actor-model concurrency with explicit suspension points. All I/O is asynchronous, and the simulator intercepts all async operations.

2. No Hidden State: The simulator controls all sources of non-determinism: time, random numbers, network, disk. There's nothing the code can do that the simulator doesn't observe.

3. Full System Simulation: Unlike unit tests that mock components, simulation runs the actual production code—just with simulated I/O. If it works in simulation, it works in production.

4. Massive Parallelism: Simulations are fast (no real I/O waits) and independent. FoundationDB runs thousands of simulation hours daily across their test cluster.

A Concrete Example: Finding Rare Bugs

Consider a bug that only manifests when:

• Node A commits a transaction
• Node B receives partial replication
• A network partition occurs for exactly 3-7 seconds
• Node A crashes during partition
• Node C attempts to read during recovery

In real testing, this sequence might occur once in billions of runs—effectively never. In simulation:

1. The fault injector can schedule exactly this sequence
2. When invariant checking catches the bug, the seed is saved
3. Re-running with that seed reproduces the bug instantly
4. Developers step through the exact sequence of events
5. The fix is verified against the same seed

Strict serializability changes how you write applications. Many patterns and defensive techniques common in eventual-consistency systems become unnecessary—while some new considerations emerge.

What You No Longer Need:

1. Explicit Locking

With strict serializability, transactions are the locking mechanism. You don't need:

# NOT NEEDED in FoundationDB
acquire_lock("resource_123")
try:
    do_work()
finally:
    release_lock("resource_123")

# Instead, just do your work in a transaction:
@fdb.transactional
def do_work(tr):
    # Automatically serialized with other transactions
    data = tr[b'resource_123']
    # ... process ...
    tr[b'resource_123'] = new_data

2. Read-Your-Writes Workarounds

In eventually consistent systems, you often need session tracking or sticky routing to ensure users see their own writes. Not needed in FoundationDB—every read after a committed write sees that write.

3. Conflict Retry Logic

The @fdb.transactional decorator handles retries automatically. You don't need retry loops, exponential backoff, or idempotency keys (mostly—see below).

4. Data Versioning for Consistency

Patterns like optimistic locking with version numbers are unnecessary:

# NOT NEEDED in FoundationDB
data, version = get_with_version("doc_123")
# ... modify data ...
update_if_version_matches("doc_123", new_data, version)

# Instead:
@fdb.transactional
def update_doc(tr):
    data = tr[b'doc_123']  # Read creates conflict range
    # ... modify data ...
    tr[b'doc_123'] = new_data  # Conflicts if someone else modified

What You Still Need:

1. Idempotency for Non-Database Side Effects

If your transaction has side effects outside FoundationDB (sending emails, calling APIs, charging credit cards), you still need idempotency. The transaction might commit, but your client might crash before receiving confirmation:

@fdb.transactional
def process_order(tr, order_id):
    # Check if already processed (idempotency key)
    status = tr[pack(('orders', order_id, 'status'))]
    if status == b'completed':
        return  # Already done, skip
    
    # Mark as processing (prevents duplicate processing)
    tr[pack(('orders', order_id, 'status'))] = b'processing'
    
    # Database work is safe within the transaction
    deduct_inventory(tr, order_id)
    
    # External side effect - needs its own protection
    # Often done AFTER transaction commits, with status tracking
    
    tr[pack(('orders', order_id, 'status'))] = b'completed'

# For truly external operations:
@fdb.transactional
def request_external_processing(tr, order_id):
    # Record intent in database
    tr[pack(('pending_external', order_id))] = b'pending'

# Separate worker processes pending_external entries
# with its own idempotency and retry logic

2. Transaction Size Limits

FoundationDB transactions are limited:

• 5 seconds maximum duration
• 10 MB total data read and written
• 10,000 keys modified (default, configurable)

Large batch operations must be split into multiple transactions:

def delete_old_events(before_timestamp):
    """Delete events older than timestamp in batches."""
    
    while True:
        deleted_count = delete_batch(before_timestamp, batch_size=1000)
        if deleted_count == 0:
            break
        print(f"Deleted {deleted_count} events")

@fdb.transactional
def delete_batch(tr, before_timestamp, batch_size):
    prefix = pack(('events',))
    count = 0
    to_delete = []
    
    for key, value in tr.get_range(prefix, prefix + b'\xff', limit=batch_size):
        event_time = unpack(key)[1]  # Assuming (events, timestamp, ...)
        if event_time < before_timestamp:
            to_delete.append(key)
            count += 1
    
    for key in to_delete:
        del tr[key]
    
    return count

We've explored FoundationDB's approach to transaction isolation—strict serializability achieved through optimistic concurrency control and validated through deterministic simulation testing. This guarantee is the bedrock that makes everything else possible.

What's Next:

The ordered key-value store with strict serializability is powerful, but for many use cases, raw key-value access isn't ergonomic. FoundationDB addresses this through its layer architecture—the ability to build higher-level abstractions (document databases, SQL databases, graph databases) on top of the core primitives. In the next page, we'll explore how layers work and why this architecture enables unprecedented flexibility.