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]>
560 lines
27 KiB
HTML
560 lines
27 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-vector-clocks</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-vector-clocks.md">
|
|
|
|
<link rel="icon" href="/favicon.svg">
|
|
<link rel="canonical" href="https://hanzoskills.com/distributed-systems-vector-clocks">
|
|
</head>
|
|
<!-- Reading this with a machine? Every page here is also plain markdown.
|
|
This one: https://hanzoskills.com/distributed-systems-vector-clocks.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-vector-clocks</h1><p class="lede">Vector clocks for tracking causality in distributed systems, detecting concurrent events, and resolving conflicts</p><h1>Vector Clocks</h1>
|
|
<p><strong>Scope</strong>: Vector clocks, causality tracking, happens-before relationships, conflict detection <strong>Lines</strong>: ~310 <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>Tracking causality in distributed systems</li><li>Detecting concurrent events</li><li>Implementing conflict resolution</li><li>Understanding Dynamo, Riak internals</li><li>Building distributed databases</li><li>Implementing version control</li><li>Detecting data races</li><li>Ordering distributed events</li></ul>
|
|
<h2>Core Concepts</h2>
|
|
<h3>The Problem: Physical Time Unreliable</h3>
|
|
<pre><code>Server A (clock slow): t=100 → Write X=1
|
|
Server B (clock fast): t=105 → Write X=2
|
|
|
|
Which happened first? Can't tell from timestamps!</code></pre>
|
|
<h3>Lamport Clocks (Logical Time)</h3>
|
|
<p><strong>Single counter per system</strong>:</p>
|
|
<pre><code class="lang-python">class LamportClock:
|
|
def __init__(self):
|
|
self.time = 0
|
|
|
|
def increment(self):
|
|
"""Increment on local event"""
|
|
self.time += 1
|
|
return self.time
|
|
|
|
def update(self, received_time):
|
|
"""Update on receiving message"""
|
|
self.time = max(self.time, received_time) + 1
|
|
return self.time</code></pre>
|
|
<p><strong>Problem</strong>: Can't detect concurrency</p>
|
|
<pre><code>A: t=1 → t=2 → t=3
|
|
B: t=1 → t=2
|
|
|
|
A:t=2 and B:t=2 concurrent? Can't tell!</code></pre>
|
|
<h3>Vector Clocks (Track All Processes)</h3>
|
|
<p><strong>One counter per process</strong>:</p>
|
|
<pre><code class="lang-python">class VectorClock:
|
|
def __init__(self, process_id, num_processes):
|
|
self.process_id = process_id
|
|
self.clock = [0] * num_processes
|
|
|
|
def increment(self):
|
|
"""Increment local counter"""
|
|
self.clock[self.process_id] += 1
|
|
return self.clock.copy()
|
|
|
|
def update(self, received_clock):
|
|
"""Merge with received clock"""
|
|
for i in range(len(self.clock)):
|
|
self.clock[i] = max(self.clock[i], received_clock[i])
|
|
self.clock[self.process_id] += 1
|
|
return self.clock.copy()
|
|
|
|
def compare(self, other_clock):
|
|
"""Compare vector clocks"""
|
|
less_than = any(self.clock[i] < other_clock[i] for i in range(len(self.clock)))
|
|
greater_than = any(self.clock[i] > other_clock[i] for i in range(len(self.clock)))
|
|
|
|
if less_than and not greater_than:
|
|
return "BEFORE" # self happened before other
|
|
elif greater_than and not less_than:
|
|
return "AFTER" # self happened after other
|
|
elif not less_than and not greater_than:
|
|
return "EQUAL" # same event
|
|
else:
|
|
return "CONCURRENT" # concurrent events</code></pre>
|
|
<hr>
|
|
<h2>Happens-Before Relationship</h2>
|
|
<h3>Definition</h3>
|
|
<p><strong>Event A happens-before event B</strong> if:</p>
|
|
<ol><li>A and B on same process, A before B</li><li>A is send, B is receive of same message</li><li>Transitive: A → B and B → C implies A → C</li></ol>
|
|
<p><strong>Vector clock property</strong>: A happens-before B ⟺ VC(A) < VC(B)</p>
|
|
<h3>Example</h3>
|
|
<pre><code>Process A: [1,0,0] → send msg → [2,0,0]
|
|
Process B: [0,1,0] → receive → [2,2,0] → [2,3,0]
|
|
Process C: [0,0,1] → [0,0,2]
|
|
|
|
Relationships:
|
|
[1,0,0] happens-before [2,3,0] (A:send before B:receive)
|
|
[1,0,0] concurrent with [0,0,1] (different processes, no communication)</code></pre>
|
|
<hr>
|
|
<h2>Implementation</h2>
|
|
<h3>Full Implementation</h3>
|
|
<pre><code class="lang-python">from typing import Dict, List, Tuple
|
|
|
|
class VectorClock:
|
|
"""Vector clock for distributed system"""
|
|
|
|
def __init__(self, node_id: str, nodes: List[str]):
|
|
self.node_id = node_id
|
|
self.nodes = nodes
|
|
self.clock = {node: 0 for node in nodes}
|
|
|
|
def tick(self) -> Dict[str, int]:
|
|
"""Increment local clock on local event"""
|
|
self.clock[self.node_id] += 1
|
|
return self.get_clock()
|
|
|
|
def send_event(self) -> Dict[str, int]:
|
|
"""Prepare vector clock for sending"""
|
|
return self.tick()
|
|
|
|
def receive_event(self, received_clock: Dict[str, int]) -> Dict[str, int]:
|
|
"""Update clock on receiving message"""
|
|
# Merge clocks (element-wise max)
|
|
for node in self.nodes:
|
|
self.clock[node] = max(
|
|
self.clock.get(node, 0),
|
|
received_clock.get(node, 0)
|
|
)
|
|
# Increment local clock
|
|
self.clock[self.node_id] += 1
|
|
return self.get_clock()
|
|
|
|
def get_clock(self) -> Dict[str, int]:
|
|
"""Get current clock value"""
|
|
return self.clock.copy()
|
|
|
|
def happens_before(self, vc1: Dict[str, int], vc2: Dict[str, int]) -> bool:
|
|
"""Check if vc1 happens before vc2"""
|
|
# vc1 ≤ vc2 for all components, and vc1 < vc2 for at least one
|
|
less_or_equal = all(vc1.get(n, 0) <= vc2.get(n, 0) for n in self.nodes)
|
|
strictly_less = any(vc1.get(n, 0) < vc2.get(n, 0) for n in self.nodes)
|
|
return less_or_equal and strictly_less
|
|
|
|
def concurrent(self, vc1: Dict[str, int], vc2: Dict[str, int]) -> bool:
|
|
"""Check if vc1 and vc2 are concurrent"""
|
|
return not self.happens_before(vc1, vc2) and not self.happens_before(vc2, vc1)
|
|
|
|
# Usage Example
|
|
nodes = ['A', 'B', 'C']
|
|
vc_a = VectorClock('A', nodes)
|
|
vc_b = VectorClock('B', nodes)
|
|
vc_c = VectorClock('C', nodes)
|
|
|
|
# Process A: local event
|
|
clock_a1 = vc_a.tick() # A: {A:1, B:0, C:0}
|
|
|
|
# Process A: send to B
|
|
msg_clock = vc_a.send_event() # A: {A:2, B:0, C:0}
|
|
|
|
# Process B: receive from A
|
|
vc_b.receive_event(msg_clock) # B: {A:2, B:1, C:0}
|
|
|
|
# Process B: local event
|
|
clock_b1 = vc_b.tick() # B: {A:2, B:2, C:0}
|
|
|
|
# Process C: independent event
|
|
clock_c1 = vc_c.tick() # C: {A:0, B:0, C:1}
|
|
|
|
# Check relationships
|
|
print(vc_a.happens_before(clock_a1, clock_b1)) # True (A's event before B's)
|
|
print(vc_a.concurrent(clock_a1, clock_c1)) # True (independent)</code></pre>
|
|
<hr>
|
|
<h2>Practical Applications</h2>
|
|
<h3>Application 1: Distributed Key-Value Store</h3>
|
|
<pre><code class="lang-python">class VersionedValue:
|
|
"""Value with vector clock version"""
|
|
|
|
def __init__(self, value, vector_clock):
|
|
self.value = value
|
|
self.vector_clock = vector_clock
|
|
|
|
class DistributedKVStore:
|
|
"""Key-value store with vector clock versioning"""
|
|
|
|
def __init__(self, node_id, nodes):
|
|
self.node_id = node_id
|
|
self.vc = VectorClock(node_id, nodes)
|
|
self.store = {} # key → list of VersionedValue
|
|
|
|
def put(self, key, value):
|
|
"""Write value with current vector clock"""
|
|
clock = self.vc.tick()
|
|
versioned = VersionedValue(value, clock)
|
|
|
|
if key not in self.store:
|
|
self.store[key] = [versioned]
|
|
else:
|
|
# Remove versions that this one supersedes
|
|
self.store[key] = [
|
|
v for v in self.store[key]
|
|
if not self.vc.happens_before(v.vector_clock, clock)
|
|
]
|
|
self.store[key].append(versioned)
|
|
|
|
return clock
|
|
|
|
def get(self, key):
|
|
"""Get value(s) for key"""
|
|
if key not in self.store:
|
|
return None
|
|
|
|
# Return all concurrent versions (siblings)
|
|
versions = self.store[key]
|
|
if len(versions) == 1:
|
|
return versions[0].value
|
|
else:
|
|
# Multiple concurrent versions - conflict!
|
|
return [v.value for v in versions]
|
|
|
|
def merge_from_replica(self, key, versioned_values):
|
|
"""Merge values from another replica"""
|
|
if key not in self.store:
|
|
self.store[key] = versioned_values
|
|
return
|
|
|
|
# Merge versions
|
|
all_versions = self.store[key] + versioned_values
|
|
|
|
# Remove dominated versions
|
|
result = []
|
|
for v1 in all_versions:
|
|
dominated = False
|
|
for v2 in all_versions:
|
|
if v1 != v2 and self.vc.happens_before(v1.vector_clock, v2.vector_clock):
|
|
dominated = True
|
|
break
|
|
if not dominated:
|
|
result.append(v1)
|
|
|
|
self.store[key] = result
|
|
|
|
# Usage
|
|
store_a = DistributedKVStore('A', ['A', 'B'])
|
|
store_b = DistributedKVStore('B', ['A', 'B'])
|
|
|
|
# A writes
|
|
store_a.put('user:1', {'name': 'Alice', 'age': 30})
|
|
|
|
# B writes concurrently (before seeing A's write)
|
|
store_b.put('user:1', {'name': 'Alice', 'age': 31})
|
|
|
|
# Now A and B sync - conflict detected!
|
|
# Both versions present with concurrent vector clocks</code></pre>
|
|
<h3>Application 2: Causal Delivery</h3>
|
|
<pre><code class="lang-python">class CausalBroadcast:
|
|
"""Ensure messages delivered in causal order"""
|
|
|
|
def __init__(self, node_id, nodes):
|
|
self.node_id = node_id
|
|
self.vc = VectorClock(node_id, nodes)
|
|
self.pending = [] # Messages waiting for causal delivery
|
|
self.delivered = []
|
|
|
|
def broadcast(self, message):
|
|
"""Broadcast message with vector clock"""
|
|
clock = self.vc.send_event()
|
|
return (message, clock)
|
|
|
|
def receive(self, message, sender_clock):
|
|
"""Receive message, deliver when causal order satisfied"""
|
|
self.pending.append((message, sender_clock))
|
|
self._try_deliver()
|
|
|
|
def _try_deliver(self):
|
|
"""Try to deliver pending messages in causal order"""
|
|
delivered_any = True
|
|
|
|
while delivered_any:
|
|
delivered_any = False
|
|
|
|
for msg, msg_clock in self.pending[:]:
|
|
if self._can_deliver(msg_clock):
|
|
self.pending.remove((msg, msg_clock))
|
|
self._deliver(msg, msg_clock)
|
|
delivered_any = True
|
|
|
|
def _can_deliver(self, msg_clock):
|
|
"""Check if message can be delivered"""
|
|
# Can deliver if all causally preceding messages delivered
|
|
for node, count in msg_clock.items():
|
|
if node == self.node_id:
|
|
continue # Skip own clock
|
|
if count > self.vc.clock.get(node, 0):
|
|
return False # Missing causal predecessor
|
|
return True
|
|
|
|
def _deliver(self, message, sender_clock):
|
|
"""Deliver message and update vector clock"""
|
|
self.vc.receive_event(sender_clock)
|
|
self.delivered.append(message)
|
|
print(f"Delivered: {message}")</code></pre>
|
|
<hr>
|
|
<h2>Optimizations</h2>
|
|
<h3>Problem: Vector Clock Size</h3>
|
|
<p><strong>Growth</strong>: O(number of processes)</p>
|
|
<p><strong>Solutions</strong>:</p>
|
|
<ol><li><strong>Pruning</strong>: Remove inactive processes</li></ol>
|
|
<pre><code class="lang-python">def prune_clock(self, min_activity_time):
|
|
"""Remove processes inactive for too long"""
|
|
current_time = time.time()
|
|
self.clock = {
|
|
node: count for node, count in self.clock.items()
|
|
if self.last_activity.get(node, 0) > current_time - min_activity_time
|
|
}</code></pre>
|
|
<ol><li><strong>Use Dotted Version Vectors</strong> (see related skill)</li></ol>
|
|
<ol><li><strong>Dynamic process IDs</strong>: Short-lived IDs instead of permanent process IDs</li></ol>
|
|
<hr>
|
|
<h2>Comparison with Alternatives</h2>
|
|
<p>| Mechanism | Size | Detects Concurrency | Complexity | |-----------|------|-------------------|------------| | <strong>Timestamps</strong> | O(1) | ❌ No | Simple | | <strong>Lamport Clocks</strong> | O(1) | ❌ No | Simple | | <strong>Vector Clocks</strong> | O(N) | ✅ Yes | Medium | | <strong>Dotted Version Vectors</strong> | O(active writers) | ✅ Yes | Medium | | <strong>Interval Tree Clocks</strong> | O(log N) | ✅ Yes | Complex |</p>
|
|
<hr>
|
|
<h2>Testing Vector Clocks</h2>
|
|
<pre><code class="lang-python">import unittest
|
|
|
|
class TestVectorClock(unittest.TestCase):
|
|
def test_happens_before(self):
|
|
"""Test happens-before relationship"""
|
|
vc = VectorClock('A', ['A', 'B'])
|
|
|
|
vc1 = {'A': 1, 'B': 0}
|
|
vc2 = {'A': 2, 'B': 1}
|
|
|
|
self.assertTrue(vc.happens_before(vc1, vc2))
|
|
self.assertFalse(vc.happens_before(vc2, vc1))
|
|
|
|
def test_concurrent(self):
|
|
"""Test concurrent events"""
|
|
vc = VectorClock('A', ['A', 'B'])
|
|
|
|
vc1 = {'A': 1, 'B': 0}
|
|
vc2 = {'A': 0, 'B': 1}
|
|
|
|
self.assertTrue(vc.concurrent(vc1, vc2))
|
|
|
|
def test_message_passing(self):
|
|
"""Test vector clock update on message passing"""
|
|
vc_a = VectorClock('A', ['A', 'B'])
|
|
vc_b = VectorClock('B', ['A', 'B'])
|
|
|
|
# A sends
|
|
sent_clock = vc_a.send_event()
|
|
|
|
# B receives
|
|
vc_b.receive_event(sent_clock)
|
|
|
|
# B's clock should reflect A's event
|
|
self.assertEqual(vc_b.clock['A'], 1)
|
|
self.assertEqual(vc_b.clock['B'], 1)</code></pre>
|
|
<hr>
|
|
<h2>Related Skills</h2>
|
|
<ul><li><code>distributed-systems-dotted-version-vectors</code> - Optimized vector clocks</li><li><code>distributed-systems-interval-tree-clocks</code> - Scalable causality tracking</li><li><code>distributed-systems-logical-clocks</code> - Lamport clocks</li><li><code>distributed-systems-crdt-fundamentals</code> - Using clocks in CRDTs</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-vector-clocks.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
|
</footer>
|
|
</div></body></html> |