CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 4 of 7 · 4 min read

Lost updates

Two read-modify-write cycles that overwrite each other, and four ways to prevent it.

Think of two people editing a shared shopping list on paper. Both copy the list, add an item and put their copy back. The second copy replaces the first, and the first person's item is gone.

The book defines the lost update problem. It occurs when an application reads a value, changes it and writes it back (a read-modify-write cycle). If two transactions do this at once, the second write does not include the first change, so one modification is lost. It appears when:

  • Incrementing a counter or balance.
  • Changing part of a complex value, such as adding an item to a list inside a JSON document.
  • Two users editing a wiki page and each saving the whole page.

Lost update

A lost update happens when two concurrent read-modify-write cycles overwrite each other, so that one change disappears.

Example: stock is 10. Two orders each read 10, subtract 1, and write 9. Stock should be 8.

The book gives four preventions.

1. Atomic write operations. Let the database do the change in one step, with no read-modify-write in the application. UPDATE counters SET value = value + 1 WHERE key = 'foo' is safe in most relational databases. MongoDB has atomic updates on parts of a document, and Redis has atomic operations on data structures. This is usually the best choice when it fits. It is typically implemented with an exclusive lock on the object (called cursor stability), or by running all such operations on one thread. The book warns that ORMs make it easy to write unsafe read-modify-write code by accident.

2. Explicit locking. When atomic operations are not enough, the application locks the rows. The book's example is a game where moves must follow rules that cannot be written as one query:

BEGIN TRANSACTION;
SELECT * FROM figures WHERE name = 'robot' AND game_id = 222 FOR UPDATE;
-- check the move is valid, then update the position
UPDATE figures SET position = 'c4' WHERE id = 1234;
COMMIT;

FOR UPDATE tells the database to lock the returned rows. It works, but it is easy to forget the lock somewhere and introduce a race.

3. Automatic detection. Let the transactions run in parallel, and if the database finds a lost update, abort one and make it retry. This works well with snapshot isolation. PostgreSQL's repeatable read, Oracle's serializable and SQL Server's snapshot isolation detect lost updates automatically. MySQL InnoDB's repeatable read does not. Some authors argue a database must prevent lost updates to count as snapshot isolation, so MySQL does not qualify under that definition. Automatic detection is less error-prone because the application needs no special code.

4. Compare-and-set. In databases without transactions, write only if the value is unchanged since it was read: UPDATE wiki_pages SET content = 'new' WHERE id = 1234 AND content = 'old'. If it changed, no row is updated and the client retries. The book warns it may be unsafe if the database lets the condition read from an old snapshot. Check before relying on it.

With replication. The book notes that locks and compare-and-set assume one up-to-date copy. Multi-leader and leaderless stores allow concurrent writes on different nodes, so those methods do not apply. Instead such stores keep conflicting versions (siblings) and merge them in application code or with special data structures (Level 4, module 3). Atomic operations that are commutative [can be applied in any order with the same result], such as incrementing a counter or adding to a set, work well, as in Riak 2.0's data types. Last write wins is prone to lost updates, and is the default in many replicated databases.

A worked example. Stock is 10. Two orders, T1 and T2.

Method What happens
Plain read-modify-write Both read 10, both write 9. One order is lost. Stock 9, should be 8
Atomic stock = stock - 1 The database serialises the two updates. Stock 8
SELECT ... FOR UPDATE T2 waits for T1's lock, reads 9, writes 8
Automatic detection Both run, T2's commit is found to overwrite T1's change, T2 aborts and retries, reads 9, writes 8
Compare-and-set (WHERE stock = 10) T2's update matches no row, T2 retries with 9, writes 8

Check yourself:

  • Why does the safe atomic update not need the application to read the value first?
  • Why can locks and compare-and-set not stop lost updates across leaders in a multi-leader store?