CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 6 of 7 · 5 min read

Phantoms and how to defend

When the row that would have been locked does not exist yet.

Phantoms and how to defend

Think of a car park attendant who checks that space 12 is empty, then writes the car in. The check is about a thing that does not exist (a car in space 12). Two attendants can check at the same moment, see nothing, and both write a car in. There was nothing to lock, because the thing being checked for was absent.

The write skew examples share a pattern, which the book spells out:

  1. A SELECT checks whether some requirement holds (two doctors on call, no booking for this room and time, the username is free).
  2. Depending on the result, the application decides whether to go on.
  3. If it goes on, it writes (an INSERT, UPDATE or DELETE) that changes the premise of step 2. If step 2 were run again after the write, it would give a different result.

In the doctors case the rows read could be locked with FOR UPDATE. In others, the check is for the absence of rows, and there is nothing to lock.

Phantom

A phantom is a write in one transaction that changes the result of a search query in another transaction. The new row did not exist when the search was run, so no lock could cover it.

Example: two transactions search for bookings of room 3 at 10:00 and find none. Each inserts a booking. Together they created two bookings, each of which "should have" appeared in the other's search.

The book's remedy when serializable isolation is not available is to materialise conflicts: create rows that can be locked. For the room booking, make a table of all possible room and time slots in advance (for example every 15 minutes for the next six months). A transaction that wants to book a room takes a lock on the matching slot rows (SELECT ... FOR UPDATE), then inserts the booking. Two bookings for the same slot now compete for the same locked row, so one waits and then sees the other's booking. This turns a phantom into a lock on a real row.

The book mentions its downside: it is hard and error-prone to work out how to materialise conflicts, and it puts a concurrency-control mechanism in the data model. It should be a last resort. A serializable isolation level is preferred.

A worked example. A room has 15-minute slots from 09:00 to 17:00: 32 slots per day. For six months (about 180 days) that is 32 × 180 = 5,760 slot rows per room. For 50 rooms: 288,000 rows. To book 10:00 to 11:00, lock 4 rows, check for existing bookings, insert. Two people booking 10:30 to 11:30 lock rows that overlap on 10:30 and 10:45 and one waits.

Other defences:

  • A unique constraint on (room, slot) lets the database stop a double booking by itself. For user names, a unique constraint on the name makes the second insert fail. This is the best fix when the rule is a simple uniqueness.
  • Serializable isolation (module 3).
  • Application checks after the write: write, then re-check, and roll back if the rule broke. It is racy and needs care.
Anomaly Allowed under read committed Allowed under snapshot isolation Prevented by serializable
Dirty read No No Yes
Dirty write No No Yes
Read skew Yes No Yes
Lost update Yes Depends (detected in some databases) Yes
Write skew Yes Yes Yes
Phantom Yes Yes (for write skew cases) Yes

Common mistake

Assuming that "repeatable read" or "serializable" in a database's settings means true serializability. The names differ between products, and Oracle's "serializable" is snapshot isolation.

Interview angle

Answer in your head first, then open it.

What is the default isolation level and what can go wrong?

Usually read committed or a snapshot level. Name read skew, lost updates and write skew, and which your design could meet.

How do you avoid lost updates?

Atomic update statements first, then FOR UPDATE, automatic detection or compare-and-set with retries.

What is write skew?

Two transactions check a shared condition and write different rows. Give the doctors on call. Fixes: lock the rows read, a constraint, materialised conflicts or true serializable.

Why do two orders for the last item both succeed?

A lost update or write skew. Show an atomic decrement with a check (WHERE stock > 0).

What is MVCC?

Several versions of each row so readers and writers do not block each other and each transaction sees a consistent snapshot.

Check yourself:

  • How does a unique constraint stop two users getting the same user name?
  • What is the cost of materialising conflicts?

Words you will meet

Word Plain meaning
Isolation level How much concurrent transactions may see of each other
Read committed No dirty reads and no dirty writes
Dirty read Seeing another transaction's uncommitted write
Dirty write Overwriting another transaction's uncommitted write
Read skew (non-repeatable read) Seeing different values for the same data within one transaction
Snapshot isolation (repeatable read) Each transaction sees a consistent snapshot from its start
MVCC Keeping several versions of each row
Lost update Two read-modify-write cycles overwrite each other
Atomic write operation A change done by the database in one indivisible step
Explicit lock (FOR UPDATE) Locking rows read so others must wait
Compare-and-set Write only if the value is unchanged
Write skew Two transactions each break a shared rule by changing different rows
Phantom A new row that would have changed another transaction's search result
Materialising conflicts Adding rows that can be locked to represent the missing ones