mitbringsl/docs/SYNC.md

Mitbringsl – Synchronization Protocol & Conflict Resolution

1. Synchronization Model

Mitbringsl uses an Append-Only Operation Log (op_log) with Hybrid Logical Clock (HLC) timestamps and Last-Write-Wins (LWW) projections.

---

2. Hybrid Logical Clock (HLC)

Every operation carries a 64-bit integer timestamp hlc_ts:

\text{hlc\_ts} = (\text{wall\_ms} \ll 16) \mid \text{counter}

• wall_ms (48 bits): Unix epoch milliseconds.
• counter (16 bits): Logical counter disambiguating events produced within the same millisecond.

Guarantees

1. Strict Monotonicity: t_{n+1} > t_n for all events generated on the same device.
2. Causal Ordering: If event B was generated after observing event A, then HLC(B) > HLC(A).

---

3. Operations (op_log)

All state modifications are represented as structured operations:

op_type	Target	Description	Payload Example
list_create	List UUID	Create list	{"name":"Wocheneinkauf"}
list_rename	List UUID	Rename list	{"name":"Supermarkt"}
list_delete	List UUID	Delete list	{}
item_add	Item UUID	Add item	{"name":"Milch","quantity":"2L"}
item_update	Item UUID	Update item	{"name":"Hafermilch","checked":true}
item_remove	Item UUID	Delete item	{}

---

4. Conflict Resolution (LWW & Tombstones)

1. Projection Updates: Database tables (items, lists) are projections of op_log. When an op arrives:

   UPDATE items
   SET name = $1, hlc_ts = $2, updated_at = now()
   WHERE id = $3 AND hlc_ts < $2 AND deleted_at IS NULL;
   

2. Tombstones (deleted_at): When an item or list is deleted (item_remove, list_delete), a tombstone is set (deleted_at = now()). Late-arriving offline item_update operations with smaller hlc_ts values will never revive a tombstoned entity.

---

5. Idempotent Push & Cursor Pull

• Idempotent Push (POST /api/lists/{id}/ops): Each operation carries a (client_id, client_seq) tuple enforced by a UNIQUE constraint in Postgres (op_log). Re-sent requests return previous (seq, hlc_ts) assignments without duplicating side effects.
• Cursor Pull (GET /api/lists/{id}/ops?since={seq}): Clients track max(server_seq) locally. Incremental sync fetches ops where seq > cursor, sorted by monotonic server sequence seq ASC.
• Client pull loop: The SyncWorker pulls for every tracked list on each run (not only lists with pending outbox ops), so remote edits on "quiet" (e.g. shared/joined) lists arrive reliably. Old synced op_log rows are pruned locally to bound growth.

Client HLC discipline

On every incoming server op the client advances its local HLC with tick(op.hlc_ts). This is essential for LWW correctness across devices with skewed clocks: without it, a fast-clock device would permanently win conflicts while a slow-clock device's own edits would be silently rejected by the hlc_ts < projection guard. The same rule applies on the server (opstore ticks the server HLC per incoming op).

---

6. Shared Lists

Since shared lists were introduced, ops flow between all members of a list, not just its owner:

• Membership: A list has an owner (lists.owner_id, role owner) and any number of members (list_members, role member). Members join via an 8-character invite code (POST /api/lists/join); owner and members can read the code (POST /api/lists/{id}/invite) to share it.
• Sync scope: Push and Pull verify on every request that the caller is owner or member of the list — non-members receive 404 (not 403, so membership cannot be probed). Once joined, a member pulls the full op history (?since=0) and applies the same LWW projection locally.
• Conflict semantics are unchanged: With multiple writers the LWW register (hlc_ts, client_id) resolves concurrent edits; the HLC guarantees that ops from different clients that observed each other are still causally ordered. Concurrent edits to the same item converge to the highest hlc_ts on every device — last write wins, no data merge.