Files
skills/public/distributed-systems-crdt-types.html
zeekayandHanzo Dev 9e10c1c10e Each llms index points at the other two
hanzoskills.com/llms.txt now opens with the install line, the API
reference index and the company index, so an agent that lands on any
one of the three can find the rest.

robots.txt claimed 537 documents while llms.txt counts 920. The number
is gone from robots.txt; llms.txt derives it.

public/ is regenerated from scripts/site.py, which it had fallen
behind: the copy-prompt menu and agent bar were in the generator and
not in the committed pages. tests/site.mjs passes against the result.

Co-authored-by: Hanzo Dev <[email protected]>
2026-09-11 00:27:59 -07:00

669 lines
29 KiB
HTML

<!doctype html>
<html lang="en"><head>
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
<title>distributed-systems-crdt-types</title>
<meta name="color-scheme" content="dark">
<style>
/* Committed to one visual world: a dark instrument panel. No light variant —
the dot field and the hairline rules only read on black, and a naive
inversion would wash both out. Every colour is painted explicitly so the page
never borrows a host background. */
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
:root{
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
--font-zen-pixel-square:'Zen Pixel Square',monospace;
--mono:var(--font-zen-mono);
--sans:var(--font-zen-sans);
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
--r:999px; --r-soft:14px;
}
*{box-sizing:border-box}
html{-webkit-text-size-adjust:100%}
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
/* The dot field. A halftone made of one repeating radial-gradient, faded out
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
/* No overflow clip here: the dot field is inset to the box already, and a clip
would cut off the copy-prompt menu. */
.hero{position:relative;border-bottom:1px solid var(--line)}
.hero::before{content:"";position:absolute;inset:0;
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
background-size:7px 7px;
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
pointer-events:none}
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
nav{border-bottom:1px solid var(--line)}
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
justify-content:space-between;align-items:center;gap:1rem}
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--ink);text-decoration:none;
display:inline-flex;align-items:center;gap:.6rem}
.brand i{font-style:normal;color:var(--faint)}
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
text-transform:uppercase;color:var(--soft);text-decoration:none}
nav a.up:hover{color:var(--ink)}
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
h1 em{font-style:normal;color:var(--faint)}
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
line-height:1.2;font-weight:400}
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
.btn.solid:hover{background:#d8d8d4}
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
/* Copy-prompt selector. Each row copies the prompt for its own target. */
.copy{position:relative;display:inline-flex}
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
padding:.4rem;display:flex;flex-direction:column;
box-shadow:0 12px 32px rgba(0,0,0,.75)}
.menu[hidden]{display:none}
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
white-space:nowrap}
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
.mi:hover .mark{color:var(--ink)}
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
letter-spacing:.1em;text-transform:uppercase}
/* Works-with bar: one scrolling row, name and mark per agent. */
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
display:flex;align-items:center}
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
-webkit-overflow-scrolling:touch;
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
.bar::-webkit-scrollbar{display:none}
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
text-decoration:none;background:var(--ground)}
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
.agent .mark{width:.95rem;height:.95rem}
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
p{margin:0 0 1rem;max-width:70ch}
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
li{margin:.22rem 0}
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
text-decoration-color:var(--line-hi)}
a:hover{text-decoration-color:var(--ink)}
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
display:block;overflow-x:auto}
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
.curl{display:block;background:var(--panel);border:1px solid var(--line);
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
white-space:pre;line-height:1.9}
.curl b{color:var(--ink);font-weight:400}
.curl i{font-style:normal;color:var(--faint)}
/* index */
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
#q:focus{outline:none;border-color:var(--soft)}
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
text-transform:uppercase;margin:0 0 2rem}
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
padding-bottom:.45rem}
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
border-radius:var(--r-soft);text-decoration:none}
.row:hover{background:#0a0a0a}
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
color:var(--faint);font-size:.85rem}
footer a{color:var(--soft)}
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
margin:0 0 2rem;font-size:.85rem}
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
border-bottom:1px solid var(--line);padding-bottom:.4rem}
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
.fmap a:hover{text-decoration:underline}
.fmap div{color:var(--faint);line-height:1.5}
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
@media (max-width:640px){
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
.btns{gap:.5rem}
.btn{padding:.75rem 1.15rem;font-size:.68rem}
.copy,.copy .btn{width:100%;justify-content:center}
.menu{left:0;right:0;min-width:0}
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
.strip b{border-right:0;padding-right:0}
.bar{width:100%}
}
</style>
<link rel="alternate" type="text/markdown" href="/distributed-systems-crdt-types.md">
<link rel="icon" href="/favicon.svg">
<link rel="canonical" href="https://hanzoskills.com/distributed-systems-crdt-types">
</head>
<!-- Reading this with a machine? Every page here is also plain markdown.
This one: https://hanzoskills.com/distributed-systems-crdt-types.md
Index: https://hanzoskills.com/llms.txt
Corpus: https://hanzoskills.com/all.md
Append .md to any path for the markdown twin. -->
<body>
<nav><div class="in">
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
<a class="up" href="/">All skills</a>
</div></nav>
<div class="wrap">
<h1>distributed-systems-crdt-types</h1><p class="lede">Specific CRDT implementations including LWW-Register, OR-Set, RGA, and collaborative text editing CRDTs</p><h1>CRDT Types</h1>
<p><strong>Scope</strong>: Specific CRDT implementations, LWW, OR-Set, sequences, collaborative editing <strong>Lines</strong>: ~370 <strong>Last Updated</strong>: 2025-10-27 <strong>Format Version</strong>: 1.0 (Atomic)</p>
<hr>
<h2>When to Use This Skill</h2>
<p>Activate this skill when:</p>
<ul><li>Implementing specific CRDT data structures</li><li>Building collaborative editing features</li><li>Choosing appropriate CRDT for use case</li><li>Understanding Yjs, Automerge internals</li><li>Implementing distributed sets</li><li>Building real-time synchronization</li><li>Handling complex conflict resolution</li><li>Optimizing CRDT performance</li></ul>
<h2>Register CRDTs</h2>
<h3>LWW-Register (Last-Write-Wins)</h3>
<p><strong>Approach</strong>: Use timestamps to resolve conflicts (latest wins)</p>
<pre><code class="lang-python">import time
class LWWRegister:
&quot;&quot;&quot;Last-Write-Wins Register&quot;&quot;&quot;
def __init__(self, replica_id):
self.replica_id = replica_id
self.value = None
self.timestamp = 0
def set(self, value):
&quot;&quot;&quot;Set value with current timestamp&quot;&quot;&quot;
self.value = value
self.timestamp = time.time()
def merge(self, other):
&quot;&quot;&quot;Merge with another replica (latest timestamp wins)&quot;&quot;&quot;
result = LWWRegister(self.replica_id)
if other.timestamp &gt; self.timestamp:
result.value = other.value
result.timestamp = other.timestamp
else:
result.value = self.value
result.timestamp = self.timestamp
return result
# Usage
r1 = LWWRegister(&#x27;A&#x27;)
r2 = LWWRegister(&#x27;B&#x27;)
r1.set(&#x27;value1&#x27;) # timestamp: t1
time.sleep(0.001)
r2.set(&#x27;value2&#x27;) # timestamp: t2 (t2 &gt; t1)
merged = r1.merge(r2)
print(merged.value) # &#x27;value2&#x27; (latest)</code></pre>
<p><strong>Problem</strong>: Concurrent writes may be lost</p>
<pre><code>Replica A: set(&#x27;A&#x27;) at t=100.001
Replica B: set(&#x27;B&#x27;) at t=100.002
Result: &#x27;B&#x27; wins (but &#x27;A&#x27; is lost!)</code></pre>
<h3>MV-Register (Multi-Value Register)</h3>
<p><strong>Approach</strong>: Keep all concurrent values, resolve externally</p>
<pre><code class="lang-python">from typing import Set, Tuple
class MVRegister:
&quot;&quot;&quot;Multi-Value Register (keeps concurrent values)&quot;&quot;&quot;
def __init__(self, replica_id):
self.replica_id = replica_id
self.values = set() # Set of (value, vector_clock) tuples
def set(self, value, vector_clock):
&quot;&quot;&quot;Set value with vector clock&quot;&quot;&quot;
# Remove dominated values
self.values = {
(v, vc) for (v, vc) in self.values
if not self._dominates(vector_clock, vc)
}
self.values.add((value, vector_clock.copy()))
def get(self):
&quot;&quot;&quot;Get all concurrent values&quot;&quot;&quot;
return {v for (v, vc) in self.values}
def merge(self, other):
&quot;&quot;&quot;Merge preserving concurrent values&quot;&quot;&quot;
result = MVRegister(self.replica_id)
result.values = self.values | other.values
# Remove dominated values
result.values = {
(v1, vc1) for (v1, vc1) in result.values
if not any(
self._dominates(vc2, vc1) and (v1, vc1) != (v2, vc2)
for (v2, vc2) in result.values
)
}
return result
def _dominates(self, vc1, vc2):
&quot;&quot;&quot;Check if vc1 dominates vc2&quot;&quot;&quot;
return all(vc1.get(k, 0) &gt;= vc2.get(k, 0) for k in vc2) and vc1 != vc2</code></pre>
<hr>
<h2>Set CRDTs</h2>
<h3>OR-Set (Observed-Remove Set)</h3>
<p><strong>Approach</strong>: Each element tagged with unique ID, can be re-added after remove</p>
<pre><code class="lang-python">import uuid
from typing import Set, Tuple
class ORSet:
&quot;&quot;&quot;Observed-Remove Set&quot;&quot;&quot;
def __init__(self):
self.elements = {} # element → set of unique IDs
def add(self, element):
&quot;&quot;&quot;Add element with unique tag&quot;&quot;&quot;
tag = str(uuid.uuid4())
if element not in self.elements:
self.elements[element] = set()
self.elements[element].add(tag)
return tag # Return for tracking
def remove(self, element):
&quot;&quot;&quot;Remove element (all current tags)&quot;&quot;&quot;
if element in self.elements:
removed_tags = self.elements[element].copy()
del self.elements[element]
return removed_tags
return set()
def lookup(self, element):
&quot;&quot;&quot;Check if element exists&quot;&quot;&quot;
return element in self.elements and len(self.elements[element]) &gt; 0
def merge(self, other):
&quot;&quot;&quot;Merge two OR-Sets&quot;&quot;&quot;
result = ORSet()
# Union of all elements and their tags
all_elements = set(self.elements.keys()) | set(other.elements.keys())
for elem in all_elements:
my_tags = self.elements.get(elem, set())
other_tags = other.elements.get(elem, set())
combined_tags = my_tags | other_tags
if combined_tags:
result.elements[elem] = combined_tags
return result
# Usage
set1 = ORSet()
set2 = ORSet()
set1.add(&#x27;apple&#x27;)
set2.add(&#x27;banana&#x27;)
set1.remove(&#x27;apple&#x27;)
set1.add(&#x27;apple&#x27;) # Can re-add after remove!
merged = set1.merge(set2)
print(merged.lookup(&#x27;apple&#x27;)) # True (re-added)
print(merged.lookup(&#x27;banana&#x27;)) # True</code></pre>
<p><strong>Key insight</strong>: Remove only affects observed adds (hence &quot;Observed-Remove&quot;)</p>
<hr>
<h2>Sequence CRDTs</h2>
<h3>RGA (Replicated Growable Array)</h3>
<p><strong>Approach</strong>: Each element has unique ID and knows its predecessor</p>
<pre><code class="lang-python">import uuid
from typing import Optional
class RGANode:
def __init__(self, value, timestamp, replica_id):
self.id = (timestamp, replica_id, str(uuid.uuid4()))
self.value = value
self.prev_id = None
self.tombstone = False # For deletion
class RGA:
&quot;&quot;&quot;Replicated Growable Array&quot;&quot;&quot;
def __init__(self, replica_id):
self.replica_id = replica_id
self.nodes = {} # id → RGANode
self.root_id = None
self.timestamp = 0
def insert_after(self, prev_id, value):
&quot;&quot;&quot;Insert value after given position&quot;&quot;&quot;
self.timestamp += 1
node = RGANode(value, self.timestamp, self.replica_id)
node.prev_id = prev_id
self.nodes[node.id] = node
return node.id
def insert_at_start(self, value):
&quot;&quot;&quot;Insert at beginning&quot;&quot;&quot;
self.timestamp += 1
node = RGANode(value, self.timestamp, self.replica_id)
node.prev_id = None
self.root_id = node.id
self.nodes[node.id] = node
return node.id
def delete(self, node_id):
&quot;&quot;&quot;Delete by marking as tombstone&quot;&quot;&quot;
if node_id in self.nodes:
self.nodes[node_id].tombstone = True
def to_list(self):
&quot;&quot;&quot;Convert to list (excluding tombstones)&quot;&quot;&quot;
if not self.nodes:
return []
# Build list by following prev_id links
result = []
current_id = self.root_id
while current_id:
node = self.nodes[current_id]
if not node.tombstone:
result.append(node.value)
# Find next node (node where prev_id == current_id)
next_nodes = [
(nid, n) for nid, n in self.nodes.items()
if n.prev_id == current_id and not n.tombstone
]
if next_nodes:
# Resolve conflicts by ID ordering
next_nodes.sort(key=lambda x: x[1].id)
current_id = next_nodes[0][0]
else:
break
return result
def merge(self, other):
&quot;&quot;&quot;Merge with another RGA&quot;&quot;&quot;
result = RGA(self.replica_id)
result.nodes = {**self.nodes, **other.nodes} # Union of nodes
result.timestamp = max(self.timestamp, other.timestamp)
return result</code></pre>
<hr>
<h2>Collaborative Text Editing</h2>
<h3>Logoot CRDT</h3>
<p><strong>Approach</strong>: Assign each character a unique position identifier</p>
<pre><code class="lang-python">import random
class LogootPosition:
&quot;&quot;&quot;Position identifier between existing positions&quot;&quot;&quot;
def __init__(self, identifiers):
self.identifiers = identifiers # List of (int, replica_id)
def __lt__(self, other):
return self.identifiers &lt; other.identifiers
def __eq__(self, other):
return self.identifiers == other.identifiers
@staticmethod
def between(pos1, pos2, replica_id):
&quot;&quot;&quot;Generate position between pos1 and pos2&quot;&quot;&quot;
# Simplified: add random component
new_id = pos1.identifiers + [(random.randint(1, 100), replica_id)]
return LogootPosition(new_id)
class LogootChar:
def __init__(self, position, char):
self.position = position
self.char = char
class LogootDocument:
&quot;&quot;&quot;Collaborative text editor using Logoot&quot;&quot;&quot;
def __init__(self, replica_id):
self.replica_id = replica_id
self.chars = [] # Sorted list of LogootChar
# Sentinels
self.begin = LogootPosition([(0, &#x27;BEGIN&#x27;)])
self.end = LogootPosition([(float(&#x27;inf&#x27;), &#x27;END&#x27;)])
def insert(self, index, char):
&quot;&quot;&quot;Insert character at index&quot;&quot;&quot;
# Get positions before and after insertion point
pos_before = self.chars[index - 1].position if index &gt; 0 else self.begin
pos_after = self.chars[index].position if index &lt; len(self.chars) else self.end
# Generate position between them
new_pos = LogootPosition.between(pos_before, pos_after, self.replica_id)
# Insert character
logoot_char = LogootChar(new_pos, char)
self.chars.insert(index, logoot_char)
self.chars.sort(key=lambda c: c.position) # Maintain sorted order
return logoot_char
def delete(self, index):
&quot;&quot;&quot;Delete character at index&quot;&quot;&quot;
if 0 &lt;= index &lt; len(self.chars):
deleted = self.chars.pop(index)
return deleted
def to_string(self):
&quot;&quot;&quot;Get document as string&quot;&quot;&quot;
return &#x27;&#x27;.join(c.char for c in self.chars)
def merge(self, other):
&quot;&quot;&quot;Merge with another document&quot;&quot;&quot;
result = LogootDocument(self.replica_id)
result.chars = sorted(
self.chars + other.chars,
key=lambda c: c.position
)
return result</code></pre>
<h3>Yjs-like CRDT</h3>
<p><strong>Simplified Yjs approach</strong>:</p>
<pre><code class="lang-python">class YjsChar:
def __init__(self, char, clock, client_id):
self.char = char
self.id = (client_id, clock)
self.left_id = None # ID of left neighbor
self.right_id = None # ID of right neighbor
self.deleted = False
class YjsText:
&quot;&quot;&quot;Simplified Yjs-like text CRDT&quot;&quot;&quot;
def __init__(self, client_id):
self.client_id = client_id
self.clock = 0
self.items = {} # id → YjsChar
def insert(self, index, char):
&quot;&quot;&quot;Insert character at index&quot;&quot;&quot;
self.clock += 1
items_list = self._to_list()
yjs_char = YjsChar(char, self.clock, self.client_id)
if index &gt; 0:
yjs_char.left_id = items_list[index - 1].id
if index &lt; len(items_list):
yjs_char.right_id = items_list[index].id
self.items[yjs_char.id] = yjs_char
return yjs_char.id
def delete(self, index):
&quot;&quot;&quot;Delete character at index&quot;&quot;&quot;
items_list = self._to_list()
if 0 &lt;= index &lt; len(items_list):
items_list[index].deleted = True
def _to_list(self):
&quot;&quot;&quot;Reconstruct ordered list&quot;&quot;&quot;
# Build from left/right relationships
result = []
for item in self.items.values():
if not item.deleted:
result.append(item)
# Sort by causal relationships and IDs
result.sort(key=lambda x: x.id)
return result
def to_string(self):
return &#x27;&#x27;.join(item.char for item in self._to_list())</code></pre>
<hr>
<h2>Map CRDTs</h2>
<h3>OR-Map (Observed-Remove Map)</h3>
<pre><code class="lang-python">class ORMap:
&quot;&quot;&quot;Map with OR-Set semantics for keys&quot;&quot;&quot;
def __init__(self):
self.keys = ORSet() # Keys as OR-Set
self.values = {} # key → CRDT value
def set(self, key, value_crdt):
&quot;&quot;&quot;Set key to CRDT value&quot;&quot;&quot;
self.keys.add(key)
if key not in self.values:
self.values[key] = value_crdt
else:
# Merge with existing value
self.values[key] = self.values[key].merge(value_crdt)
def remove(self, key):
&quot;&quot;&quot;Remove key&quot;&quot;&quot;
self.keys.remove(key)
# Keep value for potential re-add
def get(self, key):
&quot;&quot;&quot;Get value for key&quot;&quot;&quot;
if self.keys.lookup(key):
return self.values.get(key)
return None
def merge(self, other):
&quot;&quot;&quot;Merge two OR-Maps&quot;&quot;&quot;
result = ORMap()
result.keys = self.keys.merge(other.keys)
# Merge values for all keys
all_keys = set(self.values.keys()) | set(other.values.keys())
for key in all_keys:
if key in self.values and key in other.values:
result.values[key] = self.values[key].merge(other.values[key])
elif key in self.values:
result.values[key] = self.values[key]
else:
result.values[key] = other.values[key]
return result</code></pre>
<hr>
<h2>Performance Optimization</h2>
<h3>Tombstone Garbage Collection</h3>
<p><strong>Problem</strong>: Deleted items accumulate as tombstones</p>
<p><strong>Solution</strong>: Periodic GC when safe</p>
<pre><code class="lang-python">class RGAWithGC(RGA):
def garbage_collect(self, min_vector_clock):
&quot;&quot;&quot;Remove tombstones that all replicas have seen&quot;&quot;&quot;
self.nodes = {
nid: node for nid, node in self.nodes.items()
if not node.tombstone or not self._all_replicas_seen(node, min_vector_clock)
}
def _all_replicas_seen(self, node, min_vc):
&quot;&quot;&quot;Check if all replicas have seen this deletion&quot;&quot;&quot;
node_time, node_replica, _ = node.id
return min_vc.get(node_replica, 0) &gt;= node_time</code></pre>
<h3>Compression</h3>
<p><strong>Approach</strong>: Merge consecutive inserts from same replica</p>
<pre><code class="lang-python">class CompressedRGA:
&quot;&quot;&quot;RGA with run-length compression&quot;&quot;&quot;
def __init__(self, replica_id):
self.replica_id = replica_id
self.runs = [] # List of (values, id, prev_id)
def insert_run(self, prev_id, values):
&quot;&quot;&quot;Insert multiple values as single run&quot;&quot;&quot;
run_id = self._generate_id()
self.runs.append((values, run_id, prev_id))
return run_id</code></pre>
<hr>
<h2>Choosing the Right CRDT</h2>
<p>| Use Case | CRDT Type | Why | |----------|-----------|-----| | Configuration value | LWW-Register | Simple, last write wins acceptable | | Feature flags | OR-Set | Enables/disables need conflict handling | | Shopping cart | OR-Set or OR-Map | Items can be added/removed by multiple devices | | Like counter | PN-Counter | Increments/decrements commute | | Collaborative text | Logoot or Yjs | Preserves user intent in concurrent edits | | Chat messages | RGA | Insertion order matters | | User presence | LWW-Register or G-Set | Recent status most relevant |</p>
<hr>
<h2>Related Skills</h2>
<ul><li><code>distributed-systems-crdt-fundamentals</code> - CRDT basics</li><li><code>distributed-systems-vector-clocks</code> - Causality tracking</li><li><code>distributed-systems-conflict-resolution</code> - Conflict handling</li><li><code>distributed-systems-eventual-consistency</code> - Consistency models</li></ul>
<hr>
<p><strong>Last Updated</strong>: 2025-10-27</p>
<footer>
<div class="fmap">
<div><b>Build</b>
<a href="https://hanzo.app">hanzo.app</a> app builder
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
<div><b>Run</b>
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
<div><b>Account</b>
<a href="https://hanzo.id">hanzo.id</a> sign in
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
<div><b>Company</b>
<a href="https://hanzo.ai">hanzo.ai</a> canonical
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
</div>
<div class="fend"><a href="/distributed-systems-crdt-types.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
</footer>
</div></body></html>