Observed-Removed Sets (OR-Set) & Element Tagging
Basic CRDT sets cannot re-add an item once deleted. The Observed-Removed Set (OR-Set) attaches a unique tag to every addition. Deletion only tombstones currently observed tags, allowing concurrent or subsequent re-adds to survive with new tags 🏷️📦.
import uuid
class ORSet:
def __init__(self):
self.add_set = set() # (element, tag)
self.rem_set = set() # (element, tag)
def add(self, item):
tag = uuid.uuid4().hex[:8]
self.add_set.add((item, tag))
def remove(self, item):
# Tombstone all currently known tags for item:
for elem, tag in self.add_set:
if elem == item:
self.rem_set.add((elem, tag))
def read(self):
# Active items: added minus removed tags
return {elem for elem, tag in (self.add_set - self.rem_set)}
def merge(self, other):
self.add_set.update(other.add_set)
self.rem_set.update(other.rem_set)
s = ORSet()
s.add("python")
print(f"Set contents: {s.read()} 🚀")
# 36. Observed-Removed Sets (OR-Set) & Element Tagging In naive distributed systems, if User A deletes an item from a shared todo list and User B adds it back, or if a network partition delays a delete packet, simple boolean flags cause items to permanently disappear or get stuck forever 🛑. ```python # Naive Set: # items = {"buy_milk"} # deleted = {"buy_milk"} # Once in deleted, buy_milk is dead forever! ``` ### The OR-Set Tagging Solution 1. **Unique Tag per Add**: Calling `add("milk")` generates `("milk", UUID_1)`. If called again, it stores `("milk", UUID_2)`. 2. **Observed Removals**: Calling `remove("milk")` does not ban `"milk"` globally. It only copies the tags of `"milk"` that this node currently knows about into its `rem_set`. 3. **Concurrent Re-Add**: If another replica adds `"milk"` with `UUID_3` concurrently, that new tag was never observed by the delete operation. When the replicas merge, `UUID_3` remains untouched in `adds - rems`, ensuring the item survives 🏷️. --- ### Interactive Pop-Quiz 🧠 #### How does an OR-Set solve the classic 2P-Set limitation where an item could never be re-added after removal? - [ ] Each addition generates a unique tag; removals only tombstone tags observed at the moment of deletion 🏷️ - [ ] It rolls back the file system transaction log using SQLite WAL - [ ] It re-encrypts the element hash with a fresh public key - [ ] It waits for an external NTP synchronization pulse before deleting --- ### Practical Challenge 🎯 Implement `ORSet` with `add(elem, tag)`, `remove(elem)`, `read()`, and `merge(other)`. Node 1 adds `'item1'` with `'t1'`. Node 2 merges Node 1, then removes `'item1'`. Meanwhile, Node 1 adds `'item1'` again with `'t2'`. Merge Node 2 into Node 1, assert `'item1'` is in `read()`, and print the resulting set. <details> <summary>Solution</summary> ```python class ORSet: def __init__(self): self.adds = set() self.rems = set() def add(self, elem, tag): self.adds.add((elem, tag)) def remove(self, elem): for e, tag in self.adds: if e == elem: self.rems.add((e, tag)) def read(self): return {e for e, tag in (self.adds - self.rems)} def merge(self, other): self.adds.update(other.adds) self.rems.update(other.rems) n1 = ORSet() n2 = ORSet() n1.add("item1", "t1") n2.merge(n1) n2.remove("item1") n1.add("item1", "t2") n1.merge(n2) assert n1.read() == {"item1"} print(n1.read()) ``` </details>