mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
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]>
669 lines
29 KiB
HTML
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:
|
|
"""Last-Write-Wins Register"""
|
|
|
|
def __init__(self, replica_id):
|
|
self.replica_id = replica_id
|
|
self.value = None
|
|
self.timestamp = 0
|
|
|
|
def set(self, value):
|
|
"""Set value with current timestamp"""
|
|
self.value = value
|
|
self.timestamp = time.time()
|
|
|
|
def merge(self, other):
|
|
"""Merge with another replica (latest timestamp wins)"""
|
|
result = LWWRegister(self.replica_id)
|
|
|
|
if other.timestamp > self.timestamp:
|
|
result.value = other.value
|
|
result.timestamp = other.timestamp
|
|
else:
|
|
result.value = self.value
|
|
result.timestamp = self.timestamp
|
|
|
|
return result
|
|
|
|
# Usage
|
|
r1 = LWWRegister('A')
|
|
r2 = LWWRegister('B')
|
|
|
|
r1.set('value1') # timestamp: t1
|
|
time.sleep(0.001)
|
|
r2.set('value2') # timestamp: t2 (t2 > t1)
|
|
|
|
merged = r1.merge(r2)
|
|
print(merged.value) # 'value2' (latest)</code></pre>
|
|
<p><strong>Problem</strong>: Concurrent writes may be lost</p>
|
|
<pre><code>Replica A: set('A') at t=100.001
|
|
Replica B: set('B') at t=100.002
|
|
|
|
Result: 'B' wins (but 'A' 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:
|
|
"""Multi-Value Register (keeps concurrent values)"""
|
|
|
|
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):
|
|
"""Set value with vector clock"""
|
|
# 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):
|
|
"""Get all concurrent values"""
|
|
return {v for (v, vc) in self.values}
|
|
|
|
def merge(self, other):
|
|
"""Merge preserving concurrent values"""
|
|
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):
|
|
"""Check if vc1 dominates vc2"""
|
|
return all(vc1.get(k, 0) >= 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:
|
|
"""Observed-Remove Set"""
|
|
|
|
def __init__(self):
|
|
self.elements = {} # element → set of unique IDs
|
|
|
|
def add(self, element):
|
|
"""Add element with unique tag"""
|
|
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):
|
|
"""Remove element (all current tags)"""
|
|
if element in self.elements:
|
|
removed_tags = self.elements[element].copy()
|
|
del self.elements[element]
|
|
return removed_tags
|
|
return set()
|
|
|
|
def lookup(self, element):
|
|
"""Check if element exists"""
|
|
return element in self.elements and len(self.elements[element]) > 0
|
|
|
|
def merge(self, other):
|
|
"""Merge two OR-Sets"""
|
|
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('apple')
|
|
set2.add('banana')
|
|
set1.remove('apple')
|
|
set1.add('apple') # Can re-add after remove!
|
|
|
|
merged = set1.merge(set2)
|
|
print(merged.lookup('apple')) # True (re-added)
|
|
print(merged.lookup('banana')) # True</code></pre>
|
|
<p><strong>Key insight</strong>: Remove only affects observed adds (hence "Observed-Remove")</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:
|
|
"""Replicated Growable Array"""
|
|
|
|
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):
|
|
"""Insert value after given position"""
|
|
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):
|
|
"""Insert at beginning"""
|
|
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):
|
|
"""Delete by marking as tombstone"""
|
|
if node_id in self.nodes:
|
|
self.nodes[node_id].tombstone = True
|
|
|
|
def to_list(self):
|
|
"""Convert to list (excluding tombstones)"""
|
|
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):
|
|
"""Merge with another RGA"""
|
|
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:
|
|
"""Position identifier between existing positions"""
|
|
|
|
def __init__(self, identifiers):
|
|
self.identifiers = identifiers # List of (int, replica_id)
|
|
|
|
def __lt__(self, other):
|
|
return self.identifiers < other.identifiers
|
|
|
|
def __eq__(self, other):
|
|
return self.identifiers == other.identifiers
|
|
|
|
@staticmethod
|
|
def between(pos1, pos2, replica_id):
|
|
"""Generate position between pos1 and pos2"""
|
|
# 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:
|
|
"""Collaborative text editor using Logoot"""
|
|
|
|
def __init__(self, replica_id):
|
|
self.replica_id = replica_id
|
|
self.chars = [] # Sorted list of LogootChar
|
|
|
|
# Sentinels
|
|
self.begin = LogootPosition([(0, 'BEGIN')])
|
|
self.end = LogootPosition([(float('inf'), 'END')])
|
|
|
|
def insert(self, index, char):
|
|
"""Insert character at index"""
|
|
# Get positions before and after insertion point
|
|
pos_before = self.chars[index - 1].position if index > 0 else self.begin
|
|
pos_after = self.chars[index].position if index < 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):
|
|
"""Delete character at index"""
|
|
if 0 <= index < len(self.chars):
|
|
deleted = self.chars.pop(index)
|
|
return deleted
|
|
|
|
def to_string(self):
|
|
"""Get document as string"""
|
|
return ''.join(c.char for c in self.chars)
|
|
|
|
def merge(self, other):
|
|
"""Merge with another document"""
|
|
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:
|
|
"""Simplified Yjs-like text CRDT"""
|
|
|
|
def __init__(self, client_id):
|
|
self.client_id = client_id
|
|
self.clock = 0
|
|
self.items = {} # id → YjsChar
|
|
|
|
def insert(self, index, char):
|
|
"""Insert character at index"""
|
|
self.clock += 1
|
|
|
|
items_list = self._to_list()
|
|
|
|
yjs_char = YjsChar(char, self.clock, self.client_id)
|
|
|
|
if index > 0:
|
|
yjs_char.left_id = items_list[index - 1].id
|
|
if index < 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):
|
|
"""Delete character at index"""
|
|
items_list = self._to_list()
|
|
if 0 <= index < len(items_list):
|
|
items_list[index].deleted = True
|
|
|
|
def _to_list(self):
|
|
"""Reconstruct ordered list"""
|
|
# 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 ''.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:
|
|
"""Map with OR-Set semantics for keys"""
|
|
|
|
def __init__(self):
|
|
self.keys = ORSet() # Keys as OR-Set
|
|
self.values = {} # key → CRDT value
|
|
|
|
def set(self, key, value_crdt):
|
|
"""Set key to CRDT value"""
|
|
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):
|
|
"""Remove key"""
|
|
self.keys.remove(key)
|
|
# Keep value for potential re-add
|
|
|
|
def get(self, key):
|
|
"""Get value for key"""
|
|
if self.keys.lookup(key):
|
|
return self.values.get(key)
|
|
return None
|
|
|
|
def merge(self, other):
|
|
"""Merge two OR-Maps"""
|
|
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):
|
|
"""Remove tombstones that all replicas have seen"""
|
|
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):
|
|
"""Check if all replicas have seen this deletion"""
|
|
node_time, node_replica, _ = node.id
|
|
return min_vc.get(node_replica, 0) >= 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:
|
|
"""RGA with run-length compression"""
|
|
|
|
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):
|
|
"""Insert multiple values as single run"""
|
|
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> |