SD4.6 · LESSON 6 OF 6

Optimistic concurrency

Explain how indexes change work and how transactions protect application invariants under concurrency.

THE IDEA

Optimistic concurrency

Optimistic concurrency assumes conflicts are rare and detects them instead of preventing them. Every row carries a version; an update says "set the value if the version is still 1". The second of two concurrent callers is rejected, rereads (11, version 2) and retries, ending at 12, version 3. The check and the update must be one atomic database operation, otherwise another writer can slip into the gap.

Step 1 of 4

1. both callers read count = 10, version 1

final: count 12, version 3

A version check rejects a stale update so the caller rereads and retries. The comparison and the write must be one atomic database operation: reading a version and then writing unconditionally later leaves a gap for another writer.

Compare unconditional writes with the version check.

Predict first. Is reading a version then unconditionally writing later equivalent to compare-and-swap?

Chapter context

Databases execute concurrent requests against shared state. Fast lookup and correct updates are separate concerns: an index can improve a query while the application still loses updates or violates a cross-row rule.

TRY IT YOURSELF

Part 1. Do it hands-on

Replay the two callers by hand, then write compare-and-swap with a bounded retry loop.

Step 1 of 4

1. both callers read count = 10, version 1

final: count 12, version 3

final count, unconditional writes final count with the check final version read-then-write-later = CAS? (yes/no)

To do: Two callers read count = 10 (version 1) and each writes count + 1 unconditionally. Final count?
To do: With an atomic expected-version check, the first caller wins (11, version 2); the second is rejected, rereads and retries. Final count?
To do: Final version number?
To do: Is reading a version and then unconditionally writing later equivalent to compare-and-swap? Type yes or no

Part 2. Do it in code

class Row with .value and .version (start version 1).
read(): return (value, version).
write_unconditional(new_value): set the value and increase the version by 1.
cas(expected_version, new_value): ONE atomic step: if version == expected_version set the value, bump the version and return True; otherwise change nothing and return False.
update_with_retry(fn, max_tries): loop: read (value, version), compute fn(value), try cas; return the final value on success; raise RuntimeError after max_tries rejections.
two_callers(row, use_cas): both callers read first, then both try to add 1: with use_cas False each writes read_value + 1 unconditionally; with use_cas True the second attempt's cas is rejected and it rereads and retries. Return (final value, final version).

class Row:
    def __init__(self, value):
        self.value = value
        self.version = 1

    def read(self):
        pass

    def write_unconditional(self, new_value):
        pass

    def cas(self, expected_version, new_value):
        pass

def update_with_retry(row, fn, max_tries=3):
    pass

def two_callers(row, use_cas):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is reading a version then unconditionally writing later equivalent to compare-and-swap?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For an idealized search tree with effective fanout f and N distinguishable leaves, log base f of N gives a rough depth scale. Actual pages, occupancy and row-pointer costs differ. For an optimistic update, change value and version only when the stored version equals the version read by the caller.

Worked example

Two callers read count=10 at version 1 and each intends to increment. Unconditional writes of 11 lose one increment. With an atomic expected-version check, the first writes 11/version 2; the second stale attempt is rejected. After rereading, it can write 12/version 3. The model below demonstrates the condition, not database transaction implementation.

Reference code

The following example uses the Python standard library and does not call a remote service.

state={'count':10,'version':1}
def update(expected):
    if state['version'] != expected: return False
    state['count']+=1
    state['version']+=1
    return True
assert update(1)
assert not update(1)
assert update(2)
assert state == {'count':12,'version':3}

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A transaction's isolation level matters. A unique application-side check is race-prone without a database-enforced invariant. Index depth estimates are not actual query-latency measurements.