DataDrivenAlex's picture
Publish Concurrency Control Lab
c3209f9 verified
Raw History Blame Contribute Delete
3.15 kB
"""Small deterministic model for comparing stale-write policies."""
from dataclasses import dataclass
from typing import Iterable, Literal
Policy = Literal["last_write_wins", "optimistic_locking"]
@dataclass(frozen=True)
class Edit:
client: str
delta: int
base_version: int
@dataclass(frozen=True)
class Event:
client: str
kind: str
before: int
after: int
version: int
note: str
@dataclass(frozen=True)
class Result:
value: int
version: int
accepted: int
conflicts: int
retries: int
lost_updates: int
events: tuple[Event, ...]
def simulate(initial: int, edits: Iterable[Edit], policy: Policy, retry_conflicts: bool = True) -> Result:
"""Apply edits that all read an initial snapshot, in submission order.
last_write_wins writes each client's stale computed value, so later commits can
overwrite earlier changes. optimistic_locking rejects stale versions; optional
retries recompute the edit against the latest value and version.
"""
if policy not in ("last_write_wins", "optimistic_locking"):
raise ValueError("policy must be last_write_wins or optimistic_locking")
edits = tuple(edits)
value, version = initial, 0
accepted = conflicts = retries = lost_updates = 0
events: list[Event] = []
for edit in edits:
if edit.base_version < 0:
raise ValueError("base_version cannot be negative")
if policy == "last_write_wins":
before = value
stale_value = initial + edit.delta
if accepted:
lost_updates += 1
value = stale_value
version += 1
accepted += 1
events.append(Event(edit.client, "write", before, value, version,
f"stale snapshot v{edit.base_version}; overwrote current value"))
continue
if edit.base_version == version:
before = value
value += edit.delta
version += 1
accepted += 1
events.append(Event(edit.client, "commit", before, value, version,
f"version matched v{edit.base_version}"))
else:
conflicts += 1
events.append(Event(edit.client, "conflict", value, value, version,
f"expected v{edit.base_version}, found v{version}"))
if retry_conflicts:
before = value
value += edit.delta
version += 1
accepted += 1
retries += 1
events.append(Event(edit.client, "retry", before, value, version,
f"re-read v{version - 1}; recomputed edit"))
return Result(value, version, accepted, conflicts, retries, lost_updates, tuple(events))
def concurrent_edits(initial: int, deltas: Iterable[tuple[str, int]]) -> tuple[Edit, ...]:
"""Build edits whose clients all read the same initial version."""
if initial < 0:
raise ValueError("initial value cannot be negative")
return tuple(Edit(client, delta, 0) for client, delta in deltas)