Optimistic vs pessimistic concurrency control: Exercises

Deriving the optimistic cost — where does $R \cdot \frac{p}{1 - p}$ come from?

We build the formula from a picture rather than dropping it on you.

The figure below draws that ladder so you can see each step shrinking — the total area of the bars is exactly the sum above.

Figure — Optimistic vs pessimistic concurrency control

Reading the ladder figure (walk-through). Each pink bar is one rung of the ladder: the first rung has height $p$ (probability a first retry is needed), the second has height $p^{2}$ , the third $p^{3}$ , and so on — each rung a fraction $p$ shorter than the one before, so they shrink toward zero. Stack (add) all the bar heights and you get $p + p^{2} + p^{3} + \dots = \frac{p}{1 - p}$ , marked by the yellow bracket. Multiply the whole stack by the cost-per-retry $R$ and you have $E [opt]$ . The picture makes the "geometric" nature visible: the bars form a shrinking staircase, never quite ending but summing to a finite total whenever $p < 1$ .

Formula The two expected costs (conflict overhead only)

$E [pess] = L E [opt] = R \cdot \frac{p}{1 - p}$ These count only the conflict-related overhead, not the base work $W$ . Break-even happens where they are equal. Setting $L = R \cdot \frac{p}{1 - p}$ and solving step by step: $L (1 - p) = R p (multiply both sides by 1 - p)$ $L - L p = R p (expand the left bracket)$ $L = R p + L p (add L p to both sides so all p -terms sit together on the right)$ $L = (L + R) p (factor out the common p)$ $p^{*} = \frac{L}{L + R} (divide both sides by L + R)$ Why add $L p$ to both sides? We want every term containing $p$ on one side so we can factor $p$ out and isolate it; moving $- L p$ across the equals sign flips its sign to $+ L p$ , gathering both $p$ -terms on the right. If your real conflict rate $p < p^{*}$ , optimistic (MVCC-style version checks, Compare-and-Swap (CAS)) is cheaper on average; if $p > p^{*}$ , pessimistic (Two-Phase Locking (2PL), SELECT ... FOR UPDATE) is cheaper.

Reading the cost-curve figure (walk-through). The horizontal axis is $p$ , the conflict probability, running $0 \to 1$ . The vertical axis is expected overhead per transaction in milliseconds. The blue flat line is $E [pess] = L = 2$ — it never moves because a lock is paid no matter what $p$ is. The pink rising curve is $E [opt] = R \frac{p}{1 - p}$ with $R = 8$ : it starts at $0$ when $p = 0$ , stays low while conflicts are rare, then bends upward and rockets toward infinity as $p \to 1$ (the "cost explodes" arrow). They cross at the yellow dashed line $p^{*} = \frac{L}{L + R} = 0.2$ ; left of it the pink curve is below the blue line (optimistic cheaper), right of it pink is above (pessimistic cheaper). That single crossing point is the whole decision.

Level 1 — Recognition

Recall Solution 1.1

Pessimistic. The clue is FOR UPDATE, which acquires an exclusive (X) lock on the selected rows before any work is done — the transaction assumes a conflict will happen and locks first. The mechanism is locking, typically under Two-Phase Locking (2PL).

Recall Solution 1.2

Optimistic. No lock is taken during read/compute. The WHERE version = 7 is the validation step: if another transaction bumped the version first, this update matches 0 rows and we know to retry. This is the version-check flavour of OCC.

Recall Solution 1.3

Write skew. Two transactions read overlapping data but write to different rows, so a plain single-row lock or single-row version check does not catch it. See Write Skew and Phantoms.

Level 2 — Application

Recall Solution 2.1

$p^{*} = \frac{L}{L + R} = \frac{3}{3 + 9} = \frac{3}{12} = 0.25.$ Meaning: if fewer than $25%$ of transactions conflict, optimistic is cheaper on average.

Recall Solution 2.2

$E [pess] = L = 3 ms .$ $E [opt] = R \cdot \frac{p}{1 - p} = 9 \cdot \frac{0.10}{0.90} = 9 \cdot 0.1111 \dots = 1.0 ms .$ $E [opt] = 1.0 < 3 = E [pess]$ , so optimistic wins. Sanity check: $p = 0.10 < p^{*} = 0.25$ , exactly as the threshold predicts.

Recall Solution 2.3

$E [pess] = 3 ms .$ $E [opt] = 9 \cdot \frac{0.40}{0.60} = 9 \cdot 0.6667 = 6.0 ms .$ $6.0 > 3$ , so pessimistic wins. And $p = 0.40 > p^{*} = 0.25$ , consistent with the threshold.

Level 3 — Analysis

Recall Solution 3.1

$E [opt] = 8 \cdot \frac{0.95}{0.05} = 8 \cdot 19 = 152 ms .$ That is 76× the pessimistic cost of $2$ ms. Why livelock: almost every transaction fails validation and retries, its retry fails again, and the useful lock-free work is thrown away over and over — the system spins without making progress. Use a lock, a queue, or an atomic decrement instead.

Recall Solution 3.2

No deadlock. OCC takes no long-held locks, so there is nothing to wait on. Both transactions do their work on private copies. At commit, at most one validates cleanly; the loser sees a version mismatch and aborts and retries. OCC trades waiting (deadlock risk, see Deadlocks) for retrying (livelock risk). Only one failure mode at a time.

Recall Solution 3.3

No, it does not. Each transaction updates a different row (its own doctor), so both version checks succeed independently — neither row was touched by the other transaction. The conflict lives in a predicate ("count of on-call doctors ≥ 1") spanning multiple rows, not in any single cell. You need predicate/range locking or serializable isolation (Serializability and Isolation Levels, Write Skew and Phantoms).

Level 4 — Synthesis

Recall Solution 4.1

Use an atomic increment / Compare-and-Swap (CAS) loop, or UPDATE ... SET likes = likes + 1. The row is a single hot cell so $p$ is high, which would make a general OCC retry-then-rerun-all-work loop expensive. But CAS's "retry" is just a re-read + re-compare of one integer, whereas general OCC's retry re-runs the whole transaction's read/compute/I/O. Concrete comparison. Suppose a general OCC transaction re-runs $R_{gen} = 8$ ms of work per retry, while a CAS spin costs $R_{cas} \approx 0.05$ ms (a couple of CPU instructions). Even at a brutal $p = 0.9$ : $E_{gen} = 8 \cdot \frac{0.9}{0.1} = 72 ms, E_{cas} = 0.05 \cdot \frac{0.9}{0.1} = 0.45 ms .$ Same $\frac{p}{1 - p} = 9$ multiplier, but because $R_{cas} ≪ R_{gen}$ the CAS scheme is 160× cheaper. That is why atomic ops thrive on hot counters where general OCC dies. If contention is truly extreme, shard the counter per-thread and sum on read.

Recall Solution 4.2

Threshold $p^{*} = \frac{2}{2 + 8} = 0.2$ .

Reports, $p = 0.02$ : $E [opt] = 8 \cdot \frac{0.02}{0.98} = 0.1633$ ms vs $E [pess] = 2$ ms → optimistic (MVCC snapshot reads). $0.02 < 0.2$ .
Inventory, $p = 0.6$ : $E [opt] = 8 \cdot \frac{0.6}{0.4} = 12$ ms vs $2$ ms → pessimistic (SELECT ... FOR UPDATE). $0.6 > 0.2$ .

Same database, opposite strategies — chosen per-workload by comparing $p$ to $p^{*}$ .

Recall Solution 4.3

Old $p^{*} = \frac{2}{2 + 8} = 0.2$ . New $p^{*} = \frac{2}{2 + 4} = \frac{1}{3} \approx 0.333$ . The threshold rises from $0.2$ to $0.333$ , so a wider band of workloads (those with $0.2 < p < 0.333$ ) now flip to favouring optimistic. Cheaper retries push the boundary right, making the optimistic region larger. What this means for your workload mix: any workload whose conflict rate sits in that newly-captured band $0.2 < p < 0.333$ — previously assigned to pessimistic locking — is now cheaper under optimistic control and should be migrated. In practice, investing engineering effort to make retries cheaper pays off twice: it lowers the cost of the retries you already do, and it enlarges the set of workloads that qualify for the lock-free (higher-throughput) path.

Level 5 — Mastery

Recall Solution 5.1

Not necessarily true. MVCC is a storage technique — keep multiple versions so readers see a consistent snapshot and don't block writers. It is orthogonal to the conflict-handling philosophy.

MVCC + pessimistic writes: PostgreSQL's default — readers use MVCC snapshots, but writers still take row locks (e.g. SELECT ... FOR UPDATE, UPDATE).
MVCC + optimistic validation: Serializable Snapshot Isolation (SSI) layers an optimistic conflict-check on top of MVCC and aborts offenders at commit. Conclusion: MVCC ≠ OCC. It can serve either.

Recall Solution 5.2

Set $R \cdot \frac{p}{1 - p} = L$ with $L = R$ : cancel to $\frac{p}{1 - p} = 1$ , so $p = 1 - p$ , giving $p^{*} = \frac{1}{2} = 0.5$ . Interpretation: when a lock costs exactly as much as a retry, the fair coin-flip point is $50%$ conflict. Below half the transactions conflicting, optimistic; above, pessimistic. This is the only case where the popular " $50%$ rule of thumb" is actually correct — it silently assumes $L = R$ .

Recall Solution 5.3

$lim_{p \to 1^{-}} R \cdot \frac{p}{1 - p} = R \cdot \frac{1}{0 ^{+}} = + \infty.$ Why it diverges: the expected number of retries is $\frac{p}{1 - p}$ ; a retry only succeeds with probability $1 - p$ , and as $1 - p \to 0$ the expected count of attempts before a success grows without bound — the transaction can never "get through the door." Pessimistic contrast: $E [pess] = L$ is a constant, independent of $p$ . Locking serializes the crowd so each transaction waits its finite turn and then succeeds once. This flat-versus-explodes divergence (visible as the right edge of the s02 figure) is the deepest reason to prefer locks under heavy contention.

Recall One-line summary to lock in

Pessimistic cost is a flat line $L$ ; optimistic cost is a curve $R \frac{p}{1 - p}$ that starts near $0$ and explodes at $p = 1$ . They cross at $p^{*} = \frac{L}{L + R}$ — everything on this page is a consequence of that one picture.