lww_register.py
python
| 1 | """Last-Write-Wins Register — a CRDT for single scalar values. |
| 2 | |
| 3 | A LWW-Register stores one value tagged with a timestamp and an author ID. |
| 4 | On ``join``, the value with the *higher* timestamp wins. When two writes |
| 5 | carry the same timestamp, the author with the lexicographically greater ID |
| 6 | wins (tiebreaker — deterministic and bias-free). |
| 7 | |
| 8 | Use cases in Muse: |
| 9 | - Scalar metadata fields (tempo, key signature, time signature). |
| 10 | - Plugin configuration values that change infrequently. |
| 11 | - Any dimension where "whoever wrote last" is the correct merge policy. |
| 12 | |
| 13 | **Correctness guarantee**: ``join`` satisfies the three CRDT lattice laws: |
| 14 | |
| 15 | 1. **Commutativity**: ``join(a, b) == join(b, a)`` |
| 16 | 2. **Associativity**: ``join(join(a, b), c) == join(a, join(b, c))`` |
| 17 | 3. **Idempotency**: ``join(a, a) == a`` |
| 18 | |
| 19 | Proof sketch: ``join`` computes ``argmax`` on ``(timestamp, author)`` — a |
| 20 | total order — which is trivially commutative, associative, and idempotent. |
| 21 | |
| 22 | Public API |
| 23 | ---------- |
| 24 | - :class:`LWWValue` — ``TypedDict`` wire format. |
| 25 | - :class:`LWWRegister` — the register itself. |
| 26 | """ |
| 27 | |
| 28 | |
| 29 | from __future__ import annotations |
| 30 | |
| 31 | import logging |
| 32 | from typing import TypedDict |
| 33 | |
| 34 | logger = logging.getLogger(__name__) |
| 35 | |
| 36 | |
| 37 | class LWWValue(TypedDict): |
| 38 | """Wire format for a :class:`LWWRegister`. |
| 39 | |
| 40 | ``value`` is the stored payload (a JSON-serialisable string). |
| 41 | ``timestamp`` is a monotonically increasing float (Unix seconds or logical |
| 42 | clock value). ``author`` is the agent ID used as a lexicographic |
| 43 | tiebreaker when two writes carry equal timestamps. |
| 44 | """ |
| 45 | |
| 46 | value: str |
| 47 | timestamp: float |
| 48 | author: str |
| 49 | |
| 50 | |
| 51 | class LWWRegister: |
| 52 | """A register where the last write (by timestamp) always wins on merge. |
| 53 | |
| 54 | Instances are **immutable** from the outside: :meth:`write` and |
| 55 | :meth:`join` both return new registers. |
| 56 | |
| 57 | The ``author`` field is used solely as a deterministic tiebreaker for |
| 58 | equal timestamps; it confers no editorial priority. |
| 59 | |
| 60 | Example:: |
| 61 | |
| 62 | a = LWWRegister.from_dict({"value": "C major", "timestamp": 1.0, "author": "agent-1"}) |
| 63 | b = LWWRegister.from_dict({"value": "G major", "timestamp": 2.0, "author": "agent-2"}) |
| 64 | assert a.join(b).read() == "G major" # higher timestamp wins |
| 65 | assert b.join(a).read() == "G major" # commutative |
| 66 | """ |
| 67 | |
| 68 | def __init__(self, value: str, timestamp: float, author: str) -> None: |
| 69 | """Construct a register directly. |
| 70 | |
| 71 | Args: |
| 72 | value: The stored payload string. |
| 73 | timestamp: Write time (Unix seconds or logical clock). |
| 74 | author: Agent ID that performed the write. |
| 75 | """ |
| 76 | self._value = value |
| 77 | self._timestamp = timestamp |
| 78 | self._author = author |
| 79 | |
| 80 | # ------------------------------------------------------------------ |
| 81 | # Read / write |
| 82 | # ------------------------------------------------------------------ |
| 83 | |
| 84 | def read(self) -> str: |
| 85 | """Return the current stored value. |
| 86 | |
| 87 | Returns: |
| 88 | The payload string of the winning write. |
| 89 | """ |
| 90 | return self._value |
| 91 | |
| 92 | def write(self, value: str, timestamp: float, author: str) -> LWWRegister: |
| 93 | """Return a new register with the given write applied. |
| 94 | |
| 95 | The returned register holds *value* if *timestamp* is strictly greater |
| 96 | than the current timestamp, or equal with a greater author ID. |
| 97 | Otherwise ``self`` is returned unchanged. |
| 98 | |
| 99 | Args: |
| 100 | value: New payload string. |
| 101 | timestamp: Write time of the new value. |
| 102 | author: Agent performing the write. |
| 103 | |
| 104 | Returns: |
| 105 | A :class:`LWWRegister` holding whichever value wins. |
| 106 | """ |
| 107 | candidate = LWWRegister(value, timestamp, author) |
| 108 | return self.join(candidate) |
| 109 | |
| 110 | # ------------------------------------------------------------------ |
| 111 | # CRDT join |
| 112 | # ------------------------------------------------------------------ |
| 113 | |
| 114 | def join(self, other: LWWRegister) -> LWWRegister: |
| 115 | """Return the lattice join — the value with the higher timestamp. |
| 116 | |
| 117 | Tiebreaks on equal timestamps by taking the lexicographically greater |
| 118 | ``author`` string. When both ``timestamp`` and ``author`` are equal |
| 119 | (rare in practice but possible in tests), the value string itself is |
| 120 | used as the final tiebreaker, ensuring commutativity is preserved even |
| 121 | in this degenerate case. |
| 122 | |
| 123 | Args: |
| 124 | other: The register to merge with. |
| 125 | |
| 126 | Returns: |
| 127 | A new :class:`LWWRegister` holding the winning value. |
| 128 | """ |
| 129 | # Include value as the final tiebreaker so that join is commutative even |
| 130 | # when two writes carry identical (timestamp, author) metadata. |
| 131 | self_key = (self._timestamp, self._author, self._value) |
| 132 | other_key = (other._timestamp, other._author, other._value) |
| 133 | if other_key > self_key: |
| 134 | return LWWRegister(other._value, other._timestamp, other._author) |
| 135 | return LWWRegister(self._value, self._timestamp, self._author) |
| 136 | |
| 137 | # ------------------------------------------------------------------ |
| 138 | # Serialisation |
| 139 | # ------------------------------------------------------------------ |
| 140 | |
| 141 | def to_dict(self) -> LWWValue: |
| 142 | """Return a JSON-serialisable ``LWWValue`` dict. |
| 143 | |
| 144 | Returns: |
| 145 | ``{"value": ..., "timestamp": ..., "author": ...}`` |
| 146 | """ |
| 147 | return {"value": self._value, "timestamp": self._timestamp, "author": self._author} |
| 148 | |
| 149 | @classmethod |
| 150 | def from_dict(cls, data: LWWValue) -> LWWRegister: |
| 151 | """Reconstruct a :class:`LWWRegister` from its wire representation. |
| 152 | |
| 153 | Args: |
| 154 | data: Dict as produced by :meth:`to_dict`. |
| 155 | |
| 156 | Returns: |
| 157 | A new :class:`LWWRegister`. |
| 158 | """ |
| 159 | return cls(data["value"], data["timestamp"], data["author"]) |
| 160 | |
| 161 | # ------------------------------------------------------------------ |
| 162 | # Python dunder helpers |
| 163 | # ------------------------------------------------------------------ |
| 164 | |
| 165 | def equivalent(self, other: LWWRegister) -> bool: |
| 166 | """Return ``True`` if both registers hold identical state. |
| 167 | |
| 168 | Args: |
| 169 | other: The register to compare against. |
| 170 | |
| 171 | Returns: |
| 172 | ``True`` when value, timestamp, and author are all equal. |
| 173 | """ |
| 174 | return ( |
| 175 | self._value == other._value |
| 176 | and self._timestamp == other._timestamp |
| 177 | and self._author == other._author |
| 178 | ) |
| 179 | |
| 180 | def __repr__(self) -> str: |
| 181 | return ( |
| 182 | f"LWWRegister(value={self._value!r}, " |
| 183 | f"timestamp={self._timestamp}, author={self._author!r})" |
| 184 | ) |