mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
Every page now loads /webmcp.js, scripts/webmcp.ts with its types stripped (npm run webmcp). Where the browser has document.modelContext it registers two read-only tools: search_skills over the published skills index, and get_skill, which returns a skill's markdown checked against the index digest. The markdown alternate link moves from build.py to site.py, so CI holds every page to it. The API catalog gains the site itself (llms.txt and the skills index) and hanzo.ai/agents; the live discovery check now fetches every catalog link. tests/site.mjs drives the tools through a recording modelContext, and checks a browser without one loads clean.
669 lines
31 KiB
HTML
669 lines
31 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-dotted-version-vectors</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="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/distributed-systems-dotted-version-vectors">
|
||
<link rel="alternate" type="text/markdown" href="/distributed-systems-dotted-version-vectors.md">
|
||
<script type="module" src="/webmcp.js"></script>
|
||
</head>
|
||
<!-- Reading this with a machine? Every page here is also plain markdown.
|
||
This one: https://hanzoskills.com/distributed-systems-dotted-version-vectors.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-dotted-version-vectors</h1><p class="lede">Dotted version vectors for efficient sibling management, compact causality tracking, reducing metadata overhead compared to pure vector clocks</p><h1>Dotted Version Vectors</h1>
|
||
<p><strong>Scope</strong>: Dotted version vectors (DVV), sibling management, compact causality, optimized vector clocks <strong>Lines</strong>: ~380 <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>Building Riak-like key-value stores</li><li>Managing concurrent siblings efficiently</li><li>Reducing vector clock metadata overhead</li><li>Implementing optimized causality tracking</li><li>Avoiding false conflicts in distributed databases</li><li>Understanding Riak's sibling resolution</li><li>Tracking only active writers</li><li>Optimizing storage for versioned data</li></ul>
|
||
<h2>Core Concepts</h2>
|
||
<h3>The Problem with Vector Clocks</h3>
|
||
<p><strong>Vector clocks grow unbounded</strong>:</p>
|
||
<pre><code>3 replicas write to same key:
|
||
Version 1: {A:1, B:0, C:0}
|
||
Version 2: {A:1, B:1, C:0}
|
||
Version 3: {A:1, B:1, C:1}
|
||
|
||
After 1000 writes across replicas:
|
||
{A:342, B:401, C:257} ← Metadata grows forever!</code></pre>
|
||
<p><strong>False siblings problem</strong>:</p>
|
||
<pre><code>Client writes via replica A:
|
||
Value 1: {A:1, B:0} "Alice"
|
||
|
||
Client writes again via A:
|
||
Value 2: {A:2, B:0} "Alice Smith"
|
||
|
||
Vector clocks say: NOT concurrent (A:1 < A:2)
|
||
But system treats as siblings because client ID changed!</code></pre>
|
||
<h3>Dotted Version Vectors Solution</h3>
|
||
<p><strong>Key insight</strong>: Separate <strong>event</strong> (dot) from <strong>context</strong> (causal history)</p>
|
||
<pre><code>DVV = (dot, context)
|
||
|
||
dot = (node_id, counter) ← The write event
|
||
context = {node → counter} ← Causal history seen</code></pre>
|
||
<p><strong>Properties</strong>:</p>
|
||
<ol><li><strong>Compact</strong>: Only track active writes, not full history</li><li><strong>Precise</strong>: Distinguish updates from concurrent writes</li><li><strong>Efficient</strong>: Prune dominated versions automatically</li></ol>
|
||
<hr>
|
||
<h2>Algorithm</h2>
|
||
<h3>Data Structure</h3>
|
||
<pre><code class="lang-python">from typing import Dict, Tuple, Set
|
||
|
||
class Dot:
|
||
"""Single event identifier"""
|
||
def __init__(self, node_id: str, counter: int):
|
||
self.node_id = node_id
|
||
self.counter = counter
|
||
|
||
def __eq__(self, other):
|
||
return self.node_id == other.node_id and self.counter == other.counter
|
||
|
||
def __hash__(self):
|
||
return hash((self.node_id, self.counter))
|
||
|
||
def __repr__(self):
|
||
return f"({self.node_id}:{self.counter})"
|
||
|
||
class DottedVersionVector:
|
||
"""Dotted version vector for causality tracking"""
|
||
|
||
def __init__(self, node_id: str):
|
||
self.node_id = node_id
|
||
self.context = {} # node_id → max_counter seen
|
||
|
||
def new_dot(self) -> Dot:
|
||
"""Create new dot for a write event"""
|
||
current = self.context.get(self.node_id, 0)
|
||
new_counter = current + 1
|
||
self.context[self.node_id] = new_counter
|
||
return Dot(self.node_id, new_counter)
|
||
|
||
def update_context(self, other_context: Dict[str, int]):
|
||
"""Merge contexts (element-wise max)"""
|
||
for node, counter in other_context.items():
|
||
self.context[node] = max(self.context.get(node, 0), counter)
|
||
|
||
def dot_in_context(self, dot: Dot) -> bool:
|
||
"""Check if dot is in causal history"""
|
||
return self.context.get(dot.node_id, 0) >= dot.counter
|
||
|
||
def is_concurrent(self, dot1: Dot, dot2: Dot, context1: Dict[str, int],
|
||
context2: Dict[str, int]) -> bool:
|
||
"""Check if two dotted values are concurrent"""
|
||
# dot1 concurrent with dot2 if:
|
||
# - dot1 not in context2, AND
|
||
# - dot2 not in context1
|
||
dot1_seen = context2.get(dot1.node_id, 0) >= dot1.counter
|
||
dot2_seen = context1.get(dot2.node_id, 0) >= dot2.counter
|
||
return not dot1_seen and not dot2_seen</code></pre>
|
||
<h3>Versioned Value</h3>
|
||
<pre><code class="lang-python">class DottedValue:
|
||
"""Value with its causal dot"""
|
||
def __init__(self, value, dot: Dot, context: Dict[str, int]):
|
||
self.value = value
|
||
self.dot = dot
|
||
self.context = context.copy()
|
||
|
||
def __repr__(self):
|
||
return f"DottedValue({self.value}, {self.dot}, ctx={self.context})"
|
||
|
||
class DottedVersionStore:
|
||
"""Key-value store using dotted version vectors"""
|
||
|
||
def __init__(self, node_id: str):
|
||
self.node_id = node_id
|
||
self.dvv = DottedVersionVector(node_id)
|
||
self.store = {} # key → set of DottedValue
|
||
|
||
def write(self, key: str, value, context: Dict[str, int] = None):
|
||
"""Write value with new dot"""
|
||
# Update context with client's causal knowledge
|
||
if context:
|
||
self.dvv.update_context(context)
|
||
|
||
# Create new dot for this write
|
||
dot = self.dvv.new_dot()
|
||
|
||
# Create dotted value
|
||
dotted = DottedValue(value, dot, self.dvv.context)
|
||
|
||
if key not in self.store:
|
||
self.store[key] = {dotted}
|
||
else:
|
||
# Remove values dominated by this write
|
||
self.store[key] = {
|
||
v for v in self.store[key]
|
||
if not self._is_dominated(v.dot, v.context, dot, dotted.context)
|
||
}
|
||
self.store[key].add(dotted)
|
||
|
||
return dotted
|
||
|
||
def read(self, key: str):
|
||
"""Read value(s) and context"""
|
||
if key not in self.store:
|
||
return [], {}
|
||
|
||
values = list(self.store[key])
|
||
|
||
# Compute merged context from all siblings
|
||
merged_context = {}
|
||
for v in values:
|
||
for node, counter in v.context.items():
|
||
merged_context[node] = max(merged_context.get(node, 0), counter)
|
||
|
||
return values, merged_context
|
||
|
||
def _is_dominated(self, dot1: Dot, ctx1: Dict[str, int],
|
||
dot2: Dot, ctx2: Dict[str, int]) -> bool:
|
||
"""Check if (dot1, ctx1) is dominated by (dot2, ctx2)"""
|
||
# dot1 dominated if dot1 is in ctx2's causal past
|
||
return ctx2.get(dot1.node_id, 0) >= dot1.counter
|
||
|
||
def merge(self, key: str, remote_values: Set[DottedValue]):
|
||
"""Merge values from replica"""
|
||
if key not in self.store:
|
||
self.store[key] = remote_values
|
||
# Update context
|
||
for v in remote_values:
|
||
self.dvv.update_context(v.context)
|
||
return
|
||
|
||
# Merge local and remote
|
||
all_values = self.store[key] | remote_values
|
||
|
||
# Remove dominated versions
|
||
result = set()
|
||
for v1 in all_values:
|
||
dominated = False
|
||
for v2 in all_values:
|
||
if v1 != v2 and self._is_dominated(v1.dot, v1.context, v2.dot, v2.context):
|
||
dominated = True
|
||
break
|
||
if not dominated:
|
||
result.add(v1)
|
||
|
||
self.store[key] = result
|
||
|
||
# Update context from all values
|
||
for v in result:
|
||
self.dvv.update_context(v.context)</code></pre>
|
||
<hr>
|
||
<h2>Practical Example: Riak-Style KV Store</h2>
|
||
<h3>Complete Implementation</h3>
|
||
<pre><code class="lang-python">class RiakStyleKVStore:
|
||
"""Riak-inspired key-value store with DVV"""
|
||
|
||
def __init__(self, node_id: str, replicas: list):
|
||
self.node_id = node_id
|
||
self.replicas = replicas
|
||
self.store = DottedVersionStore(node_id)
|
||
|
||
def put(self, key: str, value, context: Dict[str, int] = None):
|
||
"""
|
||
Put value with optional causal context
|
||
|
||
Args:
|
||
key: The key to write
|
||
value: The value to write
|
||
context: Causal context from previous read (for updates)
|
||
|
||
Returns:
|
||
DottedValue with dot and updated context
|
||
"""
|
||
dotted = self.store.write(key, value, context)
|
||
|
||
# In real system: replicate to other nodes
|
||
# self._replicate_to_nodes(key, dotted)
|
||
|
||
return dotted
|
||
|
||
def get(self, key: str):
|
||
"""
|
||
Get value(s) for key
|
||
|
||
Returns:
|
||
(values, context) tuple
|
||
- If no conflict: single value
|
||
- If conflict: list of siblings
|
||
- context: causal context for next write
|
||
"""
|
||
values, context = self.store.read(key)
|
||
|
||
if not values:
|
||
return None, context
|
||
elif len(values) == 1:
|
||
return values[0].value, context
|
||
else:
|
||
# Multiple siblings - client must resolve
|
||
return [v.value for v in values], context
|
||
|
||
def resolve_siblings(self, key: str, resolved_value, context: Dict[str, int]):
|
||
"""
|
||
Resolve sibling conflict by writing resolution
|
||
|
||
Args:
|
||
key: The key with siblings
|
||
resolved_value: The resolved value
|
||
context: Context from get() that returned siblings
|
||
"""
|
||
return self.put(key, resolved_value, context)
|
||
|
||
# Usage Example
|
||
store_a = RiakStyleKVStore('A', ['A', 'B', 'C'])
|
||
store_b = RiakStyleKVStore('B', ['A', 'B', 'C'])
|
||
|
||
# Write on replica A
|
||
dotted1 = store_a.put('user:1', {'name': 'Alice', 'age': 30})
|
||
print(f"Write 1: {dotted1}")
|
||
# Output: DottedValue({'name': 'Alice', 'age': 30}, (A:1), ctx={'A': 1})
|
||
|
||
# Read and update on replica A
|
||
value, context = store_a.get('user:1')
|
||
dotted2 = store_a.put('user:1', {'name': 'Alice', 'age': 31}, context)
|
||
print(f"Update: {dotted2}")
|
||
# Output: DottedValue({'name': 'Alice', 'age': 31}, (A:2), ctx={'A': 2})
|
||
|
||
# Concurrent write on replica B (without seeing A's updates)
|
||
dotted3 = store_b.put('user:1', {'name': 'Alice', 'email': '[email protected]'})
|
||
print(f"Concurrent write: {dotted3}")
|
||
# Output: DottedValue({...}, (B:1), ctx={'B': 1})
|
||
|
||
# Merge at replica A
|
||
store_a.store.merge('user:1', {dotted3})
|
||
|
||
# Now reading shows siblings
|
||
siblings, ctx = store_a.get('user:1')
|
||
print(f"Siblings detected: {siblings}")
|
||
# Output: [{'name': 'Alice', 'age': 31}, {'name': 'Alice', 'email': '[email protected]'}]
|
||
|
||
# Resolve conflict
|
||
merged = {'name': 'Alice', 'age': 31, 'email': '[email protected]'}
|
||
resolved = store_a.resolve_siblings('user:1', merged, ctx)
|
||
print(f"Resolved: {resolved}")
|
||
# Output: DottedValue({...}, (A:3), ctx={'A': 3, 'B': 1})</code></pre>
|
||
<hr>
|
||
<h2>Comparison: Vector Clocks vs DVV</h2>
|
||
<h3>Memory Overhead</h3>
|
||
<pre><code class="lang-python"># Vector Clock approach
|
||
class VectorClockedValue:
|
||
def __init__(self, value, vc):
|
||
self.value = value
|
||
self.vector_clock = vc # Full vector: {A:342, B:401, C:257, ...}
|
||
|
||
# Dotted Version Vector approach
|
||
class DottedValue:
|
||
def __init__(self, value, dot, context):
|
||
self.value = value
|
||
self.dot = dot # Single dot: (A:343)
|
||
self.context = context # Pruned context: {A:342, B:401, C:257}
|
||
|
||
# Example after 1000 writes:
|
||
# VC: Every value carries full vector (3 nodes × 8 bytes × 1000 values = 24KB)
|
||
# DVV: Each value carries 1 dot + shared context (8 bytes + 24 bytes = 32 bytes)
|
||
# Savings: ~99% metadata reduction!</code></pre>
|
||
<h3>False Siblings</h3>
|
||
<pre><code class="lang-python"># Vector Clock: False siblings from client ID changes
|
||
vc_store = VectorClockStore('A', ['A', 'B'])
|
||
|
||
# Client 1 writes via A
|
||
vc_store.put('key', 'v1') # VC: {A:1, B:0}
|
||
|
||
# Same client writes again via A (new client connection)
|
||
vc_store.put('key', 'v2') # VC: {A:2, B:0}
|
||
|
||
# Result: May create siblings even though v2 supersedes v1!
|
||
|
||
# DVV: Correct handling
|
||
dvv_store = DottedVersionStore('A')
|
||
|
||
# Client writes
|
||
dotted1 = dvv_store.write('key', 'v1') # Dot: (A:1), ctx: {A:1}
|
||
|
||
# Client updates with context
|
||
dotted2 = dvv_store.write('key', 'v2', context={'A': 1}) # Dot: (A:2), ctx: {A:2}
|
||
|
||
# Result: v1 correctly pruned, no false siblings</code></pre>
|
||
<hr>
|
||
<h2>Real-World Use Case: Riak</h2>
|
||
<p><strong>Riak's DVV implementation</strong>:</p>
|
||
<pre><code class="lang-python">class RiakDVV:
|
||
"""Simplified Riak DVV logic"""
|
||
|
||
@staticmethod
|
||
def reconcile(local_values: Set[DottedValue],
|
||
remote_values: Set[DottedValue]) -> Set[DottedValue]:
|
||
"""Riak's sibling reconciliation"""
|
||
all_values = local_values | remote_values
|
||
|
||
# Compute global context
|
||
global_context = {}
|
||
for v in all_values:
|
||
for node, counter in v.context.items():
|
||
global_context[node] = max(global_context.get(node, 0), counter)
|
||
|
||
# Keep only values not in global context
|
||
survivors = set()
|
||
for v in all_values:
|
||
# Keep if dot not dominated by global context
|
||
if global_context.get(v.dot.node_id, 0) < v.dot.counter:
|
||
survivors.add(v)
|
||
# Update context to global
|
||
v.context = global_context.copy()
|
||
|
||
return survivors if survivors else {max(all_values, key=lambda v: (v.dot.node_id, v.dot.counter))}
|
||
|
||
# Riak's anti-entropy (read repair)
|
||
def read_repair(replicas: list, key: str) -> DottedValue:
|
||
"""Fetch from multiple replicas and repair inconsistencies"""
|
||
all_values = set()
|
||
for replica in replicas:
|
||
values, _ = replica.read(key)
|
||
all_values.update(values)
|
||
|
||
# Reconcile
|
||
reconciled = RiakDVV.reconcile(all_values, set())
|
||
|
||
# Write reconciled values back to out-of-date replicas
|
||
for replica in replicas:
|
||
replica.store.store[key] = reconciled
|
||
|
||
return reconciled</code></pre>
|
||
<hr>
|
||
<h2>Performance Characteristics</h2>
|
||
<p>| Aspect | Vector Clocks | Dotted Version Vectors | |--------|--------------|----------------------| | <strong>Write latency</strong> | O(1) | O(1) | | <strong>Read latency</strong> | O(siblings) | O(siblings) | | <strong>Metadata size</strong> | O(N × writes) | O(N) + dot | | <strong>Sibling detection</strong> | Accurate | More accurate | | <strong>Pruning</strong> | Manual/periodic | Automatic | | <strong>False siblings</strong> | Common | Rare | | <strong>Memory</strong> | High (unbounded) | Low (bounded) |</p>
|
||
<p><strong>Space complexity</strong>:</p>
|
||
<ul><li>Vector clock: O(N) per version, grows with writes</li><li>DVV: O(N) shared context + O(1) per version</li></ul>
|
||
<hr>
|
||
<h2>Advanced: Causal Stability</h2>
|
||
<pre><code class="lang-python">class CausallyStableDVV:
|
||
"""DVV with causal stability detection"""
|
||
|
||
def __init__(self, node_id: str):
|
||
self.dvv = DottedVersionVector(node_id)
|
||
self.stable_context = {} # Causally stable events
|
||
|
||
def mark_stable(self, node_id: str, counter: int):
|
||
"""Mark events up to counter as stable"""
|
||
self.stable_context[node_id] = counter
|
||
|
||
def prune_stable(self, key: str):
|
||
"""Prune values dominated by stable context"""
|
||
if key not in self.store:
|
||
return
|
||
|
||
self.store[key] = {
|
||
v for v in self.store[key]
|
||
if self.stable_context.get(v.dot.node_id, 0) < v.dot.counter
|
||
}
|
||
|
||
def compute_stability(self, replicas: list) -> Dict[str, int]:
|
||
"""Compute causally stable frontier across replicas"""
|
||
# Stable = min counter across all replicas
|
||
stability = {}
|
||
for node_id in self.dvv.context.keys():
|
||
min_counter = min(
|
||
r.dvv.context.get(node_id, 0) for r in replicas
|
||
)
|
||
stability[node_id] = min_counter
|
||
return stability</code></pre>
|
||
<hr>
|
||
<h2>Testing DVV</h2>
|
||
<pre><code class="lang-python">import unittest
|
||
|
||
class TestDottedVersionVector(unittest.TestCase):
|
||
def test_update_supersedes(self):
|
||
"""Test that update with context supersedes previous"""
|
||
store = DottedVersionStore('A')
|
||
|
||
# Write
|
||
v1 = store.write('key', 'value1')
|
||
|
||
# Update with context
|
||
v2 = store.write('key', 'value2', context=v1.context)
|
||
|
||
# Only v2 should remain
|
||
values, _ = store.read('key')
|
||
self.assertEqual(len(values), 1)
|
||
self.assertEqual(values[0].value, 'value2')
|
||
|
||
def test_concurrent_creates_siblings(self):
|
||
"""Test that concurrent writes create siblings"""
|
||
store_a = DottedVersionStore('A')
|
||
store_b = DottedVersionStore('B')
|
||
|
||
# Concurrent writes
|
||
v1 = store_a.write('key', 'value_a')
|
||
v2 = store_b.write('key', 'value_b')
|
||
|
||
# Merge at A
|
||
store_a.merge('key', {v2})
|
||
|
||
# Should have siblings
|
||
values, _ = store_a.read('key')
|
||
self.assertEqual(len(values), 2)
|
||
|
||
def test_no_false_siblings(self):
|
||
"""Test that sequential updates don't create false siblings"""
|
||
store = DottedVersionStore('A')
|
||
|
||
# First write
|
||
v1 = store.write('key', 'v1')
|
||
|
||
# Update with same key (simulating client getting context)
|
||
v2 = store.write('key', 'v2', context=v1.context)
|
||
|
||
# Should only have v2
|
||
values, _ = store.read('key')
|
||
self.assertEqual(len(values), 1)
|
||
self.assertEqual(values[0].value, 'v2')</code></pre>
|
||
<hr>
|
||
<h2>Related Skills</h2>
|
||
<ul><li><code>distributed-systems-vector-clocks</code> - Foundation causality tracking</li><li><code>distributed-systems-interval-tree-clocks</code> - Dynamic process IDs</li><li><code>distributed-systems-conflict-resolution</code> - Handling siblings</li><li><code>distributed-systems-eventual-consistency</code> - Consistency models</li><li><code>distributed-systems-crdt-fundamentals</code> - Convergent data structures</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-dotted-version-vectors.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
||
</footer>
|
||
</div></body></html> |