Snapshot Isolation - Learning Module

Loading content...

0/241

Write Skew Anomaly

When Snapshots Aren't Enough

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.\n\nBut 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.\n\nWrite 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.

What You Will Learn

By the end of this page, you will: understand exactly what write skew is and why it occurs; see concrete examples from real-world domains; learn why snapshot isolation's conflict detection cannot prevent it; recognize the patterns that lead to write skew in application code; and understand the available mitigation strategies.

What Is Write Skew?

Write skew is a concurrency anomaly where two transactions:\n\n1. Each read from an overlapping set of data items\n2. Each make decisions based on what they read\n3. Each write to different (non-overlapping) data items\n4. Both commit successfully under snapshot isolation\n5. The combined result violates some integrity constraint\n\nFormal Definition:\n\nA write skew occurs in a schedule $S$ with transactions $T_1$ and $T_2$ when:\n\n- $T_1$ reads items $\{x, y\}$ and writes item $x$\n- $T_2$ reads items $\{x, y\}$ and writes item $y$\n- Both transactions make modifications based on a constraint involving both $x$ and $y$\n- The constraint holds for each transaction's snapshot view\n- But the constraint is violated in the final committed state\n\nCritically, 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.

The Key Insight

Write skew is like two people independently deciding to take the last cookie from a shared jar. Each looks, sees one cookie, thinks 'I'll leave it for the other person,' and takes nothing. But if they both see one cookie and both think they're leaving it, they might both take it. The constraint (at least one cookie left) is violated even though each person acted correctly based on their observation.

Why FCW Doesn't Help:\n\nFirst-Committer-Wins detects when two transactions try to modify the same row. It prevents this schedule:\n\n\nT1: Read X → Write X\nT2: Read X → Write X (CONFLICT: same item X)\n\n\nBut write skew involves writing different items:\n\n\nT1: Read {X, Y} → Write X\nT2: Read {X, Y} → Write Y (NO CONFLICT: different items)\n\n\nThere's no write-write conflict because $X \neq Y$. Both transactions can commit under SI, even if the combination of their writes violates a constraint on $\{X, Y\}$.

Classic Example: The On-Call Doctors Problem

The most famous illustration of write skew is the on-call doctors problem, described in the seminal paper on snapshot isolation.\n\nThe Scenario:\n\nA hospital requires that at least one doctor is always on call. The oncall table tracks which doctors are currently on duty:\n\nsql\nCREATE TABLE oncall (\n doctor_id INTEGER PRIMARY KEY,\n name VARCHAR(100),\n is_oncall BOOLEAN\n);\n\n-- Initial state: Alice and Bob are both on call\nINSERT INTO oncall VALUES (1, 'Alice', TRUE);\nINSERT INTO oncall VALUES (2, 'Bob', TRUE);\n\n-- Constraint: At least one doctor must always be on call\n-- COUNT(*) WHERE is_oncall = TRUE >= 1\n\n\nThe Write Skew Scenario:

Write Skew: Both Doctors Go Off-Call
Time	Transaction T1 (Alice)	Transaction T2 (Bob)	Database State
0	—	—	Alice: TRUE, Bob: TRUE (2 on-call)
1	BEGIN (snapshot)	—	Snapshot: Alice=TRUE, Bob=TRUE
2	—	BEGIN (snapshot)	Snapshot: Alice=TRUE, Bob=TRUE
3	count = 2 (both on-call)	—	T1 sees 2 doctors on-call
4	—	count = 2 (both on-call)	T2 sees 2 doctors on-call
5	count > 1, safe to leave	—	T1 decides Alice can leave
6	—	count > 1, safe to leave	T2 decides Bob can leave
7	UPDATE: Alice = FALSE	—	Alice goes off-call
8	—	UPDATE: Bob = FALSE	Bob goes off-call
9	COMMIT ✓	—	T1 commits successfully
10	—	COMMIT ✓	T2 commits successfully
11	—	—	Alice: FALSE, Bob: FALSE (0 on-call) ❌

Analysis:\n\n1. Both transactions took snapshots when 2 doctors were on-call\n2. Each saw that going off-call would leave 1 doctor (safe)\n3. Each modified a different row (Alice's row vs Bob's row)\n4. No write-write conflict (different rows)\n5. Both committed successfully\n6. Constraint violated: Zero doctors on-call\n\nEach transaction acted correctly according to its snapshot. The constraint was satisfied before each write. But the combined effect violates the constraint.

Why This Is Dangerous

This isn't just a theoretical concern. Real systems have similar constraints: at least one replica must be available, account balances can't go negative across related accounts, inventory can't go below zero. Write skew can cause real-world failures—missed on-call coverage, oversold tickets, double-booked resources.

More Write Skew Patterns

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

Scenario: A meeting room booking system where the same time slot cannot be double-booked.\n\nThe Constraint: No two bookings can overlap for the same room.\n\nWrite Skew:\n\n\nT1: Check if Room A is free 2-3pm → Yes (empty)\n INSERT booking for Room A, 2-3pm\n\nT2: Check if Room A is free 2-3pm → Yes (T1's insert not visible)\n INSERT booking for Room A, 2-3pm\n\nBoth commit → Double booking!\n\n\nBoth transactions inserted different rows (different booking IDs), so no write-write conflict. But the constraint (no overlapping bookings) is violated.

The Common Pattern

All write skew patterns share this structure: (1) Read multiple items to evaluate a constraint, (2) Make a decision based on that constraint being satisfied, (3) Write to ONE of those items. The write changes the data in a way that would affect the constraint evaluation—but the other transaction doesn't see this change.

Why Snapshot Isolation Allows Write Skew

To understand why SI allows write skew, we need to examine what SI's conflict detection actually checks.\n\nWhat SI Checks:\n\n1. 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.\n\n2. Reading Your Own Writes: A transaction sees its own uncommitted modifications.\n\n3. Snapshot Consistency: All reads see a consistent point-in-time view.\n\nWhat SI Does NOT Check:\n\n1. Read-Write Dependencies Across Items: SI doesn't track that T1 read Y before writing X.\n\n2. Constraint Validation Across Transactions: SI doesn't know that there's a constraint linking X and Y.\n\n3. Dangerous Structure Detection: SI doesn't identify the "read overlapping, write different" pattern.

write_skew_structure.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# The write skew structure in serialization graph terms:
 
TRANSACTION T1:
    READ(Y)     # T1 depends on Y's value
    WRITE(X)    # T1 modifies X
 
TRANSACTION T2:
    READ(X)     # T2 depends on X's value  
    WRITE(Y)    # T2 modifies Y
 
# The problem:
# - T1 reads Y, so T1 should see T2's write to Y (if T2 is ordered first)
# - T2 reads X, so T2 should see T1's write to X (if T1 is ordered first)
# - This creates a CYCLE in the serialization graph!
 
# Serialization Graph:
#   T1 --rw--> T2  (T1 reads X, T2 writes X - but T2 doesn't conflict)
#   T2 --rw--> T1  (T2 reads Y, T1 writes Y - but T1 doesn't conflict)
#
# These are "rw-antidependencies" (read-write conflicts)
# SI detects ww-conflicts but NOT rw-antidependencies
 
# Result: Both T1 and T2 can commit, creating a cycle
# This cycle means no serial order exists → NOT serializable

The Serialization Graph Perspective:\n\nFor a schedule to be serializable, its serialization graph must be acyclic. Write skew creates cycles:\n\n- T1 → T2: T1 read Y before T2 wrote Y (rw-dependency)\n- T2 → T1: T2 read X before T1 wrote X (rw-dependency)\n\nThis bidirectional dependency forms a cycle: T1 → T2 → T1\n\nSI 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.\n\nContrast with Strict 2PL:\n\nUnder strict two-phase locking:\n- T1 reading Y would acquire S(Y)\n- T2 writing Y would need X(Y) and block on T1's S(Y)\n- Alternatively, T2 reading X while T1 holds a write intent would block\n- Either way, the cycle is broken by lock waits\n\nThis is why 2PL guarantees serializability but SI does not.

SI Is NOT Serializable

This is the fundamental limitation: Snapshot Isolation allows schedules that are not serializable. Write skew is the canonical example. If your application requires serializability, standard SI is insufficient. You need either SERIALIZABLE isolation (with SSI checking) or application-level protections.

Detecting Write Skew Vulnerabilities

How do you identify code patterns that are vulnerable to write skew? Look for these warning signs:\n\nRed Flag #1: Read-Check-Write Pattern\n\nsql\n-- Vulnerable pattern\nSELECT COUNT(*) FROM oncall WHERE is_oncall = TRUE;\n-- Application checks: if count > 1, proceed\nUPDATE oncall SET is_oncall = FALSE WHERE doctor_id = ?;\n\n\nThe 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.\n\nRed Flag #2: Aggregate-Based Decisions\n\nsql\n-- Vulnerable pattern \nSELECT SUM(balance) FROM accounts WHERE customer_id = ?;\n-- Application checks: if sum >= withdrawal_amount, proceed\nUPDATE accounts SET balance = balance - ? WHERE account_id = ?;\n\n\nThe decision depends on an aggregate (SUM) over multiple rows, but the write affects only one row. Other transactions can modify the other rows.

Write Skew Warning Signs

•Multi-row reads followed by single-row writes — Reading several rows to make a decision, then updating one
•Constraint checks in application code — Validating constraints that span multiple rows without database enforcement
•INSERT after SELECT for uniqueness — Checking for existence then inserting without a unique constraint
•Range queries before point updates — SELECT ... WHERE range followed by UPDATE ... WHERE specific_row
•Cross-row totals or counts — Decisions based on SUM, COUNT, MAX, MIN across rows
•Mutual exclusion logic in app — Application logic like 'only one of A or B can be true'

Code Review Checklist:\n\nWhen reviewing code for write skew vulnerabilities:\n\n1. Identify the constraint: What invariant must hold? (e.g., at least one on-call)\n\n2. Trace the data flow: Which rows are read? Which is written?\n\n3. Check for overlap: Does the read set include rows other than the write target?\n\n4. Consider concurrent execution: What if two instances run simultaneously?\n\n5. Verify enforcement mechanism: Is the constraint enforced by the database or only by application logic?\n\nIf a constraint spans multiple rows and is only enforced by application code, you likely have a write skew vulnerability.

The Golden Rule

If your transaction reads from a set and writes to a proper subset while enforcing a constraint on the full set, you're vulnerable to write skew under snapshot isolation. The solution is to either use SERIALIZABLE isolation or force the read and write sets to overlap.

Mitigation Strategies

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

Solution: Use SERIALIZABLE isolation level instead of REPEATABLE READ.\n\nsql\nBEGIN ISOLATION LEVEL SERIALIZABLE;\nSELECT COUNT(*) FROM oncall WHERE is_oncall = TRUE;\n-- Application checks count\nUPDATE oncall SET is_oncall = FALSE WHERE doctor_id = 1;\nCOMMIT;\n\n\nHow It Works:\n\nPostgreSQL's Serializable Snapshot Isolation (SSI) tracks read-write dependencies. If it detects a cycle (the structure that causes write skew), it aborts one of the transactions with a serialization failure.\n\nPros:\n- Comprehensive protection\n- No application changes needed (just change isolation level)\n- Correctness guaranteed\n\nCons:\n- Higher overhead (dependency tracking)\n- More transaction aborts (must retry)\n- Some false positives (safe schedules may be rejected)

Choose Based on Your Needs

SERIALIZABLE is the most comprehensive but has overhead. SELECT FOR UPDATE is precise but requires careful coding. Materialized conflicts are simple but add schema complexity. Database constraints are robust but limited in expressiveness. Most production systems use a combination based on specific needs.

Serializable Snapshot Isolation (SSI)

PostgreSQL's SERIALIZABLE isolation level uses Serializable Snapshot Isolation (SSI), an elegant extension of SI that detects write skew without blocking reads.\n\nHow SSI Works:\n\nSSI extends SI by tracking rw-antidependencies (read-write conflicts):\n\n1. When T1 reads data that T2 later writes, record T1 → T2 (rw-conflict)\n2. When T2 reads data that T1 later writes, record T2 → T1 (rw-conflict)\n3. At commit time, check for cycles involving rw-antidependencies\n4. If a "dangerous structure" (two consecutive rw-edges) is detected, abort one transaction

ssi_detection.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# SSI tracks "SIREAD locks" - virtual locks for reads
# These don't block but record what was read
 
TRANSACTION T1:
    SIREAD(Y)    # Record that T1 read Y
    WRITE(X)     # Record that T1 wrote X
 
TRANSACTION T2:
    SIREAD(X)    # Record that T2 read X
    WRITE(Y)     # Record that T2 wrote Y
 
# At commit time, SSI checks:
# 1. Did T1 read something that T2 wrote? 
#    T1 read X, T2 didn't write X → No
#    T1 read Y, T2 wrote Y → Yes! rw-antidependency T1 → T2
#
# 2. Did T2 read something that T1 wrote?
#    T2 read Y, T1 didn't write Y → No
#    T2 read X, T1 wrote X → Yes! rw-antidependency T2 → T1
#
# 3. Cycle detected: T1 → T2 → T1 (via rw-antidependencies)
#
# 4. Abort one transaction with "serialization failure"
 
# SSI success: One transaction commits, one retries
# The retry will see the committed data and either:
#   - Proceed correctly with updated view
#   - Choose not to proceed (constraint would be violated)

SSI Implementation Details:\n\nSIREAD Locks:\n\nSSI 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.\n\nConflict Bookkeeping:\n\nFor each transaction, SSI maintains:\n- List of rw-conflicts where this transaction has an outgoing edge\n- List of rw-conflicts where this transaction has an incoming edge\n\nDangerous Structure Detection:\n\nA commit is rejected if it would create a "dangerous structure"—specifically, a pivot transaction with both:\n- An incoming rw-antidependency from a committed transaction\n- An outgoing rw-antidependency to a committed or committing transaction\n\nFalse Positives:\n\nSSI is conservative. Some schedules it aborts would actually be serializable. But false positives are better than false negatives (allowing non-serializable schedules).

SSI vs 2PL

SSI provides serializability like 2PL but with key differences: readers never block writers and vice versa (high concurrency), but serialization failures require retries. For read-heavy workloads with occasional write conflicts, SSI often outperforms 2PL. For write-heavy workloads with frequent conflicts, 2PL may be better.

Summary: Understanding Write Skew

Write skew is the canonical anomaly that separates snapshot isolation from full serializability. Understanding it is essential for designing correct concurrent applications.

Key Takeaways

•Write skew occurs when transactions read overlapping data but write different items — This bypasses FCW detection since there's no write-write conflict
•Common patterns include on-call scheduling, booking systems, and multi-row constraints — Any constraint spanning multiple rows is vulnerable
•SI doesn't track read-write antidependencies — It only detects write-write conflicts on the same item
•Multiple mitigation strategies exist — SERIALIZABLE isolation, SELECT FOR UPDATE, materialized conflicts, database constraints
•SSI extends SI with rw-antidependency tracking — PostgreSQL's SERIALIZABLE level uses this to prevent write skew
•Code review can identify vulnerable patterns — Look for read-check-write patterns where read and write sets differ
•Choose mitigation based on requirements — Consider overhead, retry rates, and implementation complexity

What's Next:\n\nThe next page compares Snapshot Isolation vs Serializable Isolation in depth, examining the full spectrum of trade-offs between these isolation levels.

Page Complete

You now understand write skew—what it is, why it occurs under snapshot isolation, how to detect vulnerable code patterns, and how to prevent it. This knowledge is critical for building correct applications on databases that use MVCC and snapshot-based isolation.