lww_register.py
python
sha256:e8214e0062ef8ef0af999937df2731655b6082781fc22bc563f58db2f42b1de9
Merge 'bump/muse-v0.2.1' into 'dev' — proposal: chore: bump…
Human
8 days ago
| 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 | import logging |
| 29 | from typing import TypedDict |
| 30 | |
| 31 | logger = logging.getLogger(__name__) |
| 32 | |
| 33 | class LWWValue(TypedDict): |
| 34 | """Wire format for a :class:`LWWRegister`. |
| 35 | |
| 36 | ``value`` is the stored payload (a JSON-serialisable string). |
| 37 | ``timestamp`` is a monotonically increasing float (Unix seconds or logical |
| 38 | clock value). ``author`` is the agent ID used as a lexicographic |
| 39 | tiebreaker when two writes carry equal timestamps. |
| 40 | """ |
| 41 | |
| 42 | value: str |
| 43 | timestamp: float |
| 44 | author: str |
| 45 | |
| 46 | class LWWRegister: |
| 47 | """A register where the last write (by timestamp) always wins on merge. |
| 48 | |
| 49 | Instances are **immutable** from the outside: :meth:`write` and |
| 50 | :meth:`join` both return new registers. |
| 51 | |
| 52 | The ``author`` field is used solely as a deterministic tiebreaker for |
| 53 | equal timestamps; it confers no editorial priority. |
| 54 | |
| 55 | Example:: |
| 56 | |
| 57 | a = LWWRegister.from_dict({"value": "C major", "timestamp": 1.0, "author": "agent-1"}) |
| 58 | b = LWWRegister.from_dict({"value": "G major", "timestamp": 2.0, "author": "agent-2"}) |
| 59 | assert a.join(b).read() == "G major" # higher timestamp wins |
| 60 | assert b.join(a).read() == "G major" # commutative |
| 61 | """ |
| 62 | |
| 63 | def __init__(self, value: str, timestamp: float, author: str) -> None: |
| 64 | """Construct a register directly. |
| 65 | |
| 66 | Args: |
| 67 | value: The stored payload string. |
| 68 | timestamp: Write time (Unix seconds or logical clock). |
| 69 | author: Agent ID that performed the write. |
| 70 | """ |
| 71 | self._value = value |
| 72 | self._timestamp = timestamp |
| 73 | self._author = author |
| 74 | |
| 75 | # ------------------------------------------------------------------ |
| 76 | # Read / write |
| 77 | # ------------------------------------------------------------------ |
| 78 | |
| 79 | def read(self) -> str: |
| 80 | """Return the current stored value. |
| 81 | |
| 82 | Returns: |
| 83 | The payload string of the winning write. |
| 84 | """ |
| 85 | return self._value |
| 86 | |
| 87 | def write(self, value: str, timestamp: float, author: str) -> LWWRegister: |
| 88 | """Return a new register with the given write applied. |
| 89 | |
| 90 | The returned register holds *value* if *timestamp* is strictly greater |
| 91 | than the current timestamp, or equal with a greater author ID. |
| 92 | Otherwise ``self`` is returned unchanged. |
| 93 | |
| 94 | Args: |
| 95 | value: New payload string. |
| 96 | timestamp: Write time of the new value. |
| 97 | author: Agent performing the write. |
| 98 | |
| 99 | Returns: |
| 100 | A :class:`LWWRegister` holding whichever value wins. |
| 101 | """ |
| 102 | candidate = LWWRegister(value, timestamp, author) |
| 103 | return self.join(candidate) |
| 104 | |
| 105 | # ------------------------------------------------------------------ |
| 106 | # CRDT join |
| 107 | # ------------------------------------------------------------------ |
| 108 | |
| 109 | def join(self, other: LWWRegister) -> LWWRegister: |
| 110 | """Return the lattice join — the value with the higher timestamp. |
| 111 | |
| 112 | Tiebreaks on equal timestamps by taking the lexicographically greater |
| 113 | ``author`` string. When both ``timestamp`` and ``author`` are equal |
| 114 | (rare in practice but possible in tests), the value string itself is |
| 115 | used as the final tiebreaker, ensuring commutativity is preserved even |
| 116 | in this degenerate case. |
| 117 | |
| 118 | Args: |
| 119 | other: The register to merge with. |
| 120 | |
| 121 | Returns: |
| 122 | A new :class:`LWWRegister` holding the winning value. |
| 123 | """ |
| 124 | # Include value as the final tiebreaker so that join is commutative even |
| 125 | # when two writes carry identical (timestamp, author) metadata. |
| 126 | self_key = (self._timestamp, self._author, self._value) |
| 127 | other_key = (other._timestamp, other._author, other._value) |
| 128 | if other_key > self_key: |
| 129 | return LWWRegister(other._value, other._timestamp, other._author) |
| 130 | return LWWRegister(self._value, self._timestamp, self._author) |
| 131 | |
| 132 | # ------------------------------------------------------------------ |
| 133 | # Serialisation |
| 134 | # ------------------------------------------------------------------ |
| 135 | |
| 136 | def to_dict(self) -> LWWValue: |
| 137 | """Return a JSON-serialisable ``LWWValue`` dict. |
| 138 | |
| 139 | Returns: |
| 140 | ``{"value": ..., "timestamp": ..., "author": ...}`` |
| 141 | """ |
| 142 | return {"value": self._value, "timestamp": self._timestamp, "author": self._author} |
| 143 | |
| 144 | @classmethod |
| 145 | def from_dict(cls, data: LWWValue) -> LWWRegister: |
| 146 | """Reconstruct a :class:`LWWRegister` from its wire representation. |
| 147 | |
| 148 | Args: |
| 149 | data: Dict as produced by :meth:`to_dict`. |
| 150 | |
| 151 | Returns: |
| 152 | A new :class:`LWWRegister`. |
| 153 | """ |
| 154 | return cls(data["value"], data["timestamp"], data["author"]) |
| 155 | |
| 156 | # ------------------------------------------------------------------ |
| 157 | # Python dunder helpers |
| 158 | # ------------------------------------------------------------------ |
| 159 | |
| 160 | def equivalent(self, other: LWWRegister) -> bool: |
| 161 | """Return ``True`` if both registers hold identical state. |
| 162 | |
| 163 | Args: |
| 164 | other: The register to compare against. |
| 165 | |
| 166 | Returns: |
| 167 | ``True`` when value, timestamp, and author are all equal. |
| 168 | """ |
| 169 | return ( |
| 170 | self._value == other._value |
| 171 | and self._timestamp == other._timestamp |
| 172 | and self._author == other._author |
| 173 | ) |
| 174 | |
| 175 | def __repr__(self) -> str: |
| 176 | return ( |
| 177 | f"LWWRegister(value={self._value!r}, " |
| 178 | f"timestamp={self._timestamp}, author={self._author!r})" |
| 179 | ) |
File History
4 commits
sha256:e8214e0062ef8ef0af999937df2731655b6082781fc22bc563f58db2f42b1de9
Merge 'bump/muse-v0.2.1' into 'dev' — proposal: chore: bump…
Human
8 days ago
sha256:8de4334a98c945aace420969d389ad678aa926d4ab4e886b2ac4c4241cb3bf2b
revert: keep pyproject.toml in canonical PEP 440 form
Sonnet 4.6
patch
66 days ago
sha256:a317886dc0496c4af7b285b3e41c86c4c34ea2e79afc63b8829aadb1ada7903f
chore: bump version to 0.2.0rc15 to match musehub#113 fix release
Sonnet 4.6
patch
66 days ago
sha256:f3b726b50f0aee3622bba751e0a67aa7ae4cf75a798477dbce581940b6a9cf70
feat: migrate invariants cache to .muse/cache/invariants.ms…
Sonnet 4.6
patch
133 days ago