CSE Roadmap

Common tier · about 3 hours · 6 parts

Part 2 of 6 · 1 min read

The promise and the three recipes

What serializable means and the three ways to get it.

Think of a shop with one till. Customers may crowd the shop, but the till serves one at a time, so the order of sales is always clear. Serializable isolation gives every transaction that feel: the end result matches some one-at-a-time order, even though the work overlaps.

Serializable isolation

Serializable isolation guarantees that even when transactions run in parallel, the end result is the same as if they had run one at a time, in some order, with no overlap.

Example: the two doctors of module 2 both try to go off call. A serializable database acts as if one went first, so the second sees one doctor left and is refused.

The consequence, in the book's words in short: if each transaction is correct alone, it stays correct when run together. The database prevents all race conditions, not only the ones the developer thought of.

Why weak levels are a problem, per the book: levels are hard to understand and named differently across databases; application code alone does not show whether it is safe at a given level; and there are no good tools to find race conditions. Tests rarely catch them, since problems appear only when timing is unlucky.

Most databases that offer serializability use one of three recipes:

Recipe Idea Style
Actual serial execution Run one transaction at a time on one thread Pessimistic to the extreme
Two-phase locking (2PL) Lock everything read or written until the end Pessimistic
Serializable snapshot isolation (SSI) Run freely on snapshots, check at commit Optimistic

Check yourself:

  • If every transaction is correct on its own, what does serializable isolation add?
  • Name the three recipes.