In this post, we’ll explore how Serializable Snapshot Isolation (SSI) addresses concurrency anomalies under Snapshot Isolation (SI). Although SI already provides good performance in many systems, it can still lead to anomalies such as Write Skew. We’ll walk through why SI can fail in certain cases and how SSI fixes these issues with a relatively small overhead and a clever conflict detection mechanism.

Introduction

This post focuses on Isolation in the context of single-node databases (i.e., local concurrency control), rather than distributed consistency. Although the “C” in ACID stands for Consistency, it traditionally means database constraints remain valid before and after a transaction—not the same as consistency in distributed systems¹. Often, when people talk about “consistency,” they actually refer to isolation.

Here are two extreme approaches to help you think about this:

• Big Fucking Lock: One simple but impractical approach is to use a single global lock on the entire database. This ensures strictly serial transaction execution—no concurrency anomalies occur, but throughput is severely limited.
• No Concurrency Control: On the opposite extreme, letting transactions freely read/write data leads to well-known issues such as lost updates or dirty reads.

Our goal is to allow correct transactional logic while maximizing concurrency. The rest of this post discusses how we identify and avoid concurrency anomalies under Snapshot Isolation, then extend SI to Serializable Snapshot Isolation for stronger guarantees.

Redefine Isolation Level

ANSI attempted to define isolation levels using several anomaly types, but this has recently been considered insufficient. Different mainstream databases implement these isolation levels differently, rendering ANSI’s isolation levels meaningless². Here, we redefine the isolation levels.

Isolation Levels can be seen as sets of possible histories (executions). A database system promises that any observed transaction history will belong to the set that matches its stated isolation level. We say Isolation Level $L_1 ; \bold{stronger than} ; L_2 \iff L_1 \subset L2$, If an isolation level (L_1) only allows a subset of the histories allowed by (L_2), then (L_1) is considered stronger than (L_2). Stronger isolation = fewer possible histories = more robust guarantees but potentially lower concurrency.

• Serializable have a declarative definition: A history is serializable if its committed transactions can be totally ordered in a way that produces a result equivalent to a purely sequential execution.
• Snapshot Isolation (SI) is defined in an imperative way: The set of all histories produced by the algorithm called SI. Well it has a declarative definition here³.

We’ll see next how SI can fail due to Write Skew.

Write Skew (The Infamous Doctor’s On-Call Shift)

A classic Write Skew example occurs in a hospital’s on-call scheduling database, where two doctors are on duty, and at least one must always remain on call.

Suppose a table doctors_on_call:

+----+--------+
| id | on_call|
+----+--------+
| 1  | yes    |
| 2  | yes    |
+----+--------+

Each doctor wants to end their shift and uses this logic:

-- 1. Check if there’s at least one other doctor on call:
SELECT COUNT(*) 
FROM doctors_on_call 
WHERE on_call = 'yes';

-- (If it returns 2, each doctor "thinks" it's safe to go off duty.)

-- 2. Update their own status:
UPDATE doctors_on_call
SET on_call = 'no'
WHERE id = <their_id>;

Under Snapshot Isolation, both doctors might:

1. Execute the SELECT COUNT(*) concurrently and each sees 2 doctors on call.
2. Both decide it’s safe to go off duty.
3. Each issues an UPDATE ... SET on_call='no'.

Because there’s no strict blocking here, both updates commit. Result: no doctors left on call—violating the constraint.

Other Examples:

• Hotel rooms: There are 5 rooms left. Two concurrent transactions each check “Is there enough space for 3 rooms?” Both see “true,” then both proceed to book 3 rooms → 6 rooms booked in total, over the limit.
• Simultaneous transfers: You initiate two transfers from the same account using different apps or ATMs; each sees \$500 balance, and each transfers out \$500, ending up with \$1000 withdrawn.

In short, Write Skew often appears when:

1. Multiple transactions make decisions based on the same read predicate.
2. Each transaction updates different (non-conflicting) rows.
3. The global logical constraint (e.g., “there must be at least one doctor on call”) gets violated.

Conflict Dependency Graph

To reason about serializability, we use a conflict dependency graph (sometimes called a precedence graph). Each transaction is a node; edges represent conflicting read-write or write-write dependencies. If this graph forms a cycle, the schedule cannot be serialized.

Key insight: The dependency graph focuses on causal relationships, not the real-time start/end of transactions. Under SI, many transactions run in parallel, but as long as their read-write relationships form an acyclic graph, the result is equivalent to a serial schedule.

From SI to SSI

Although SI avoids many anomalies, Write Skew can still break global constraints. To fix this, Serializable Snapshot Isolation (SSI) monitors transaction dependencies in real-time. Whenever a cycle is about to form, SSI aborts one of the transactions to preserve serializability.

A well-known result⁴ shows that every non-serializable SI anomaly involves a cycle with two consecutive read-write (rw) dependencies among concurrent transactions. SSI adds extra conflict checks and aborts one transaction whenever it detects such a pattern.

Each transaction (T) has two boolean flags:

• T.inConflict: Indicates some concurrent transaction depends on (T) via a read-write edge.
• T.outConflict: Indicates (T) depends on some concurrent transaction via a read-write edge.

When both flags are true, (T) is part of a potential cycle and must be aborted.

But, instead of doing a full cycle check in the graph (which could be expensive), SSI only checks for consecutive rw-dependency edges among concurrent transactions. This can produce false positives (aborting when no real cycle would form), but in practice, the overhead remains acceptable.

Tracking Read-Write Dependencies in SSI

Case 1: Read happens after a write

When (T) reads an older version of some item x (i.e., not the latest version), it means another transaction (U) must have written a newer version after (T) started but is still active:

1. Set T.outConflict = true (because (T) depends on an older version, overshadowed by (U)).
2. Set U.inConflict = true (because (U) wrote a value that (T) is effectively ignoring).

Case 2: Read happens before a write

To detect the scenario “Transaction X reads a value that Transaction Y later overwrites”, SSI uses a non-blocking lock approach:

• SIREAD lock: When a transaction reads an item, it acquires an SIREAD lock on it. This is purely logical (non-blocking): other transactions can still write.
• WRITE lock: When a transaction writes to an item, it acquires a WRITE lock.

When both SIREAD and WRITE locks are present on the same item (from different transactions), that indicates a read-write dependency:

• Reader’s outConflict = true
• Writer’s inConflict = true

Noticed that if the reading transaction finishes, its SIREAD lock is retained until all concurrent transactions complete. This is needed so that any transaction writing the same item later can detect the earlier read dependency.

SSI Pseudocode

Below is some simplified pseudocode showing how existing SI logic is combined with SSI conflict detection:

# BEGIN
def begin(T):
    existing_si_begin(T)
    T.inConflict = False
    T.outConflict = False

# READ
def read(T, x):
    get_lock(x, T, mode="SIREAD")
    
    # Check if there's already a WRITE lock: indicates a read-write conflict
    for wl in get_locks(x, "WRITE"):
        wl.owner.inConflict = True
        T.outConflict = True

    # Standard SI read logic here
    existing_si_read(T, x)
    
    # Also check if there is a newer version created after T started
    # If that version belongs to a concurrent transaction that T depends on,
    # mark outConflict/inConflict or abort as needed
    newer_versions = get_newer_versions(x, T.snapshot)
    for newv in newer_versions:
        newv.creator.inConflict = True
        T.outConflict = True

# WRITE
def write(T, x, xNew):
    get_lock(x, T, mode="WRITE")

    # Check if there's an existing SIREAD lock from another concurrent T'
    for rl in get_locks(x, "SIREAD"):
        rl.owner.outConflict = True
        T.inConflict = True

    # Standard SI write logic
    existing_si_write(T, x, xNew)

# COMMIT
def commit(T):
    # If both flags are true, we likely have a cycle => abort
    if T.inConflict and T.outConflict:
        abort(T)
        return

    existing_si_commit(T)
    release_locks(T, mode="WRITE")

    # Retain SIREAD locks until all concurrent transactions finish
    # so that later writes can still detect read dependencies

1. begin(T): Initializes T.inConflict and T.outConflict, then calls the usual SI logic.
2. read(T, x):
   • Acquire an SIREAD lock.
   • If a WRITE lock is present from another concurrent transaction, mark the necessary conflicts.
   • Read under standard SI.
   • Check for any newer version of x created during (T)’s lifetime (potential write after read).
3. write(T, x, xNew):
   • Acquire a WRITE lock.
   • If a SIREAD lock is active from another transaction, mark conflicts.
   • Perform the SI write.
4. commit(T):
   • If both inConflict and outConflict are true, abort.
   • Otherwise commit, release WRITE locks, but keep SIREAD locks for concurrency detection with any concurrent transactions.

Concluding Remarks

• SSI is a practical extension to SI that prevents anomalies like Write Skew by detecting and aborting potential cycles in real time.
• This approach sometimes overreacts (false positives) but generally offers high concurrency with strong guarantees.
• PostgreSQL is a well-known production system that implements this idea for its highest isolation level, SERIALIZABLE.
• While Snapshot Isolation alone is often sufficient in many workloads, if you require true serializability without giving up SI’s performance characteristics, SSI is a compelling solution.

Further exploration could discuss:

• Performance overhead of maintaining these locks and version checks.
• Optimizations to reduce false positives or cut down on conflict tracking.
• Comparisons with other methods like Two-Phase Locking (2PL) or advanced MVCC variants.

References