Write Skew Anomaly

Snapshot isolation is remarkably powerful—it eliminates dirty reads, non-repeatable reads, and even phantom reads for read-only transactions. It enables high concurrency by letting readers and writers operate without blocking each other. It feels like we've solved the concurrency problem.

But there's a catch. A subtle, dangerous catch that has caused countless bugs in production systems, corrupted data in financial applications, and violated constraints in booking systems worldwide. This catch is called the Write Skew Anomaly.

Write skew occurs when two transactions read overlapping data, make decisions based on that data, and then write to non-overlapping data items—with the final result violating some constraint that neither transaction individually violated. It's the signature weakness of snapshot isolation, and understanding it is essential for any engineer working with databases.

Write skew is a concurrency anomaly where two transactions:

1. Each read from an overlapping set of data items
2. Each make decisions based on what they read
3. Each write to different (non-overlapping) data items
4. Both commit successfully under snapshot isolation
5. The combined result violates some integrity constraint

Formal Definition:

A write skew occurs in a schedule $S$ with transactions $T_1$ and $T_2$ when:

• $T_1$ reads items $\{x, y\}$ and writes item $x$
• $T_2$ reads items $\{x, y\}$ and writes item $y$
• Both transactions make modifications based on a constraint involving both $x$ and $y$
• The constraint holds for each transaction's snapshot view
• But the constraint is violated in the final committed state

Critically, because $T_1$ writes $x$ and $T_2$ writes $y$, there's no write-write conflict. Snapshot isolation's First-Committer-Wins (FCW) rule only detects conflicts on the same data item. Write skew slips through because each transaction writes a different item.

Why FCW Doesn't Help:

First-Committer-Wins detects when two transactions try to modify the same row. It prevents this schedule:

T1: Read X → Write X
T2: Read X → Write X  (CONFLICT: same item X)

But write skew involves writing different items:

T1: Read {X, Y} → Write X
T2: Read {X, Y} → Write Y  (NO CONFLICT: different items)

There's no write-write conflict because $X eq Y$. Both transactions can commit under SI, even if the combination of their writes violates a constraint on $\{X, Y\}$.

The most famous illustration of write skew is the on-call doctors problem, described in the seminal paper on snapshot isolation.

The Scenario:

A hospital requires that at least one doctor is always on call. The oncall table tracks which doctors are currently on duty:

CREATE TABLE oncall (
    doctor_id INTEGER PRIMARY KEY,
    name VARCHAR(100),
    is_oncall BOOLEAN
);

-- Initial state: Alice and Bob are both on call
INSERT INTO oncall VALUES (1, 'Alice', TRUE);
INSERT INTO oncall VALUES (2, 'Bob', TRUE);

-- Constraint: At least one doctor must always be on call
-- COUNT(*) WHERE is_oncall = TRUE >= 1

The Write Skew Scenario:

Analysis:

1. Both transactions took snapshots when 2 doctors were on-call
2. Each saw that going off-call would leave 1 doctor (safe)
3. Each modified a different row (Alice's row vs Bob's row)
4. No write-write conflict (different rows)
5. Both committed successfully
6. Constraint violated: Zero doctors on-call

Each transaction acted correctly according to its snapshot. The constraint was satisfied before each write. But the combined effect violates the constraint.

Write skew appears in many real-world scenarios. Recognizing these patterns is crucial for designing correct applications.

To understand why SI allows write skew, we need to examine what SI's conflict detection actually checks.

What SI Checks:

1. Write-Write Conflicts on Same Item: If T1 and T2 both write to item X, FCW ensures only one can commit with its version of X.

2. Reading Your Own Writes: A transaction sees its own uncommitted modifications.

3. Snapshot Consistency: All reads see a consistent point-in-time view.

What SI Does NOT Check:

1. Read-Write Dependencies Across Items: SI doesn't track that T1 read Y before writing X.

2. Constraint Validation Across Transactions: SI doesn't know that there's a constraint linking X and Y.

3. Dangerous Structure Detection: SI doesn't identify the "read overlapping, write different" pattern.

The Serialization Graph Perspective:

For a schedule to be serializable, its serialization graph must be acyclic. Write skew creates cycles:

• T1 → T2: T1 read Y before T2 wrote Y (rw-dependency)
• T2 → T1: T2 read X before T1 wrote X (rw-dependency)

This bidirectional dependency forms a cycle: T1 → T2 → T1

SI doesn't detect these read-write antidependencies. It only enforces that write-write conflicts are resolved by FCW. The cycle goes undetected, and both transactions commit.

Contrast with Strict 2PL:

Under strict two-phase locking:

• T1 reading Y would acquire S(Y)
• T2 writing Y would need X(Y) and block on T1's S(Y)
• Alternatively, T2 reading X while T1 holds a write intent would block
• Either way, the cycle is broken by lock waits

This is why 2PL guarantees serializability but SI does not.

How do you identify code patterns that are vulnerable to write skew? Look for these warning signs:

Red Flag #1: Read-Check-Write Pattern

-- Vulnerable pattern
SELECT COUNT(*) FROM oncall WHERE is_oncall = TRUE;
-- Application checks: if count > 1, proceed
UPDATE oncall SET is_oncall = FALSE WHERE doctor_id = ?;

The read (COUNT) and write (UPDATE) operate on related but potentially different rows. Other transactions can modify rows that affect the COUNT while this transaction proceeds.

Red Flag #2: Aggregate-Based Decisions

-- Vulnerable pattern  
SELECT SUM(balance) FROM accounts WHERE customer_id = ?;
-- Application checks: if sum >= withdrawal_amount, proceed
UPDATE accounts SET balance = balance - ? WHERE account_id = ?;

The decision depends on an aggregate (SUM) over multiple rows, but the write affects only one row. Other transactions can modify the other rows.

Code Review Checklist:

When reviewing code for write skew vulnerabilities:

1. Identify the constraint: What invariant must hold? (e.g., at least one on-call)

2. Trace the data flow: Which rows are read? Which is written?

3. Check for overlap: Does the read set include rows other than the write target?

4. Consider concurrent execution: What if two instances run simultaneously?

5. Verify enforcement mechanism: Is the constraint enforced by the database or only by application logic?

If a constraint spans multiple rows and is only enforced by application code, you likely have a write skew vulnerability.

Several strategies can prevent write skew, each with different trade-offs.

PostgreSQL's SERIALIZABLE isolation level uses Serializable Snapshot Isolation (SSI), an elegant extension of SI that detects write skew without blocking reads.

How SSI Works:

SSI extends SI by tracking rw-antidependencies (read-write conflicts):

1. When T1 reads data that T2 later writes, record T1 → T2 (rw-conflict)
2. When T2 reads data that T1 later writes, record T2 → T1 (rw-conflict)
3. At commit time, check for cycles involving rw-antidependencies
4. If a "dangerous structure" (two consecutive rw-edges) is detected, abort one transaction

SSI Implementation Details:

SIREAD Locks:

SSI uses "predicate locks" or "SIREAD locks" to track what transactions have read. These don't block other transactions—they just record the read for later conflict detection.

Conflict Bookkeeping:

For each transaction, SSI maintains:

• List of rw-conflicts where this transaction has an outgoing edge
• List of rw-conflicts where this transaction has an incoming edge

Dangerous Structure Detection:

A commit is rejected if it would create a "dangerous structure"—specifically, a pivot transaction with both:

• An incoming rw-antidependency from a committed transaction
• An outgoing rw-antidependency to a committed or committing transaction

False Positives:

SSI is conservative. Some schedules it aborts would actually be serializable. But false positives are better than false negatives (allowing non-serializable schedules).