File size: 3,150 Bytes
c3209f9
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
"""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)