Instalar com Codex ou Claude Copie este prompt, cole no Codex, Claude ou outro assistente e deixe que ele revise a página da skill e instale para você.
Um comando direto ignora o prompt de revisão. Verifique a origem antes de executá-lo.
Instruções da origem · Visualização somente leitura
name
distributed-systems-dotted-version-vectors
description
Dotted version vectors for efficient sibling management, compact causality tracking, reducing metadata overhead compared to pure vector clocks
Dotted Version Vectors
Scope: Dotted version vectors (DVV), sibling management, compact causality, optimized vector clocks
Lines: ~380
Last Updated: 2025-10-27
Format Version: 1.0 (Atomic)
When to Use This Skill
Activate this skill when:
Building Riak-like key-value stores
Managing concurrent siblings efficiently
Reducing vector clock metadata overhead
Implementing optimized causality tracking
Avoiding false conflicts in distributed databases
Understanding Riak's sibling resolution
Tracking only active writers
Optimizing storage for versioned data
Core Concepts
The Problem with Vector Clocks
Vector clocks grow unbounded:
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!
False siblings problem:
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!
Dotted Version Vectors Solution
Key insight: Separate event (dot) from context (causal history)
DVV = (dot, context)
dot = (node_id, counter) ← The write event
context = {node → counter} ← Causal history seen
:
Properties
Compact: Only track active writes, not full history
Precise: Distinguish updates from concurrent writes
Efficient: Prune dominated versions automatically
Algorithm
Data Structure
from typing importDict, Tuple, SetclassDot:
"""Single event identifier"""def__init__(self, node_id: str, counter: int):
self.node_id = node_id
self.counter = counter
def__eq__(self, other):
returnself.node_id == other.node_id andself.counter == other.counter
def__hash__(self):
returnhash((self.node_id, self.counter))
def__repr__(self):
returnf"({self.node_id}:{self.counter})"classDottedVersionVector:
"""Dotted version vector for causality tracking"""def__init__(self, node_id: str):
self.node_id = node_id
self.context = {} # node_id → max_counter seendefnew_dot(self) -> Dot:
"""Create new dot for a write event"""
current = self.context.get(self.node_id, 0)
new_counter = current + 1self.context[self.node_id] = new_counter
return Dot(self.node_id, new_counter)
defupdate_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)
defdot_in_context(self, dot: Dot) -> bool:
"""Check if dot is in causal history"""returnself.context.get(dot.node_id, 0) >= dot.counter
defis_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
returnnot dot1_seen andnot dot2_seen
Versioned Value
classDottedValue:
"""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):
returnf"DottedValue({self.value}, {self.dot}, ctx={self.context})"classDottedVersionStore:
"""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 DottedValuedefwrite(self, key: str, value, context: Dict[str, int] = None):
"""Write value with new dot"""# Update context with client's causal knowledgeif 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 notinself.store:
self.store[key] = {dotted}
else:
# Remove values dominated by this writeself.store[key] = {
v for v inself.store[key]
ifnotself._is_dominated(v.dot, v.context, dot, dotted.context)
}
self.store[key].add(dotted)
return dotted
defread(self, key: str):
"""Read value(s) and context"""if key notinself.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 pastreturn ctx2.get(dot1.node_id, 0) >= dot1.counter
defmerge(self, key: str, remote_values: Set[DottedValue]):
"""Merge values from replica"""if key notinself.store:
self.store[key] = remote_values
# Update contextfor 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 = Falsefor v2 in all_values:
if v1 != v2 andself._is_dominated(v1.dot, v1.context, v2.dot, v2.context):
dominated = Truebreakifnot dominated:
result.add(v1)
self.store[key] = result
# Update context from all valuesfor v in result:
self.dvv.update_context(v.context)
Practical Example: Riak-Style KV Store
Complete Implementation
classRiakStyleKVStore:
"""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)
defput(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
defget(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)
ifnot values:
returnNone, context
eliflen(values) == 1:
return values[0].value, context
else:
# Multiple siblings - client must resolvereturn [v.value for v in values], context
defresolve_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
"""returnself.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': 'alice@example.com'})
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': 'alice@example.com'}]# Resolve conflict
merged = {'name': 'Alice', 'age': 31, 'email': 'alice@example.com'}
resolved = store_a.resolve_siblings('user:1', merged, ctx)
print(f"Resolved: {resolved}")
# Output: DottedValue({...}, (A:3), ctx={'A': 3, 'B': 1})
Comparison: Vector Clocks vs DVV
Memory Overhead
# Vector Clock approachclassVectorClockedValue:
def__init__(self, value, vc):
self.value = value
self.vector_clock = vc # Full vector: {A:342, B:401, C:257, ...}# Dotted Version Vector approachclassDottedValue:
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!
False Siblings
# 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
Real-World Use Case: Riak
Riak's DVV implementation:
classRiakDVV:
"""Simplified Riak DVV logic""" @staticmethoddefreconcile(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 contextif 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)defread_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 replicasfor replica in replicas:
replica.store.store[key] = reconciled
return reconciled
Performance Characteristics
Aspect
Vector Clocks
Dotted Version Vectors
Write latency
O(1)
O(1)
Read latency
O(siblings)
O(siblings)
Metadata size
O(N × writes)
O(N) + dot
Sibling detection
Accurate
More accurate
Pruning
Manual/periodic
Automatic
False siblings
Common
Rare
Memory
High (unbounded)
Low (bounded)
Space complexity:
Vector clock: O(N) per version, grows with writes
DVV: O(N) shared context + O(1) per version
Advanced: Causal Stability
classCausallyStableDVV:
"""DVV with causal stability detection"""def__init__(self, node_id: str):
self.dvv = DottedVersionVector(node_id)
self.stable_context = {} # Causally stable eventsdefmark_stable(self, node_id: str, counter: int):
"""Mark events up to counter as stable"""self.stable_context[node_id] = counter
defprune_stable(self, key: str):
"""Prune values dominated by stable context"""if key notinself.store:
returnself.store[key] = {
v for v inself.store[key]
ifself.stable_context.get(v.dot.node_id, 0) < v.dot.counter
}
defcompute_stability(self, replicas: list) -> Dict[str, int]:
"""Compute causally stable frontier across replicas"""# Stable = min counter across all replicas
stability = {}
for node_id inself.dvv.context.keys():
min_counter = min(
r.dvv.context.get(node_id, 0) for r in replicas
)
stability[node_id] = min_counter
return stability
Testing DVV
import unittest
classTestDottedVersionVector(unittest.TestCase):
deftest_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')
deftest_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)
deftest_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')
Related Skills
distributed-systems-vector-clocks - Foundation causality tracking
distributed-systems-interval-tree-clocks - Dynamic process IDs
