Expand description
VClock is a vector clock implementated in Rust.
It offers a partial order of events in a distributed system. In practice, it implements the rust partial order trait over hash maps which maintain an integer count of each modification, per key.
§Examples
Basic usage:
use vclock::VClock;
let c1 = VClock::<&str, u64>::new("a"); // c1 is now a:0
let mut c2 = VClock::new("b"); // c2 is now b:0
c2.incr(&"a"); // c1 is now a:0,b:0
assert!(c1 < c2, "c1 should be a child of c2");Here is how to generate a conflict:
use vclock::VClock;
let mut c1: VClock<&str>=VClock::default();
c1.incr(&"a");
c1.incr(&"a");
c1.incr(&"a");
c1.incr(&"a");
c1.incr(&"b"); // c1 is now a:3, b:0
let c2 = c1.clone().next(&"a"); // c2 is now a:4,b:0
let c3 = c1.clone().next(&"b"); // c3 is now a:3,b:1
// Now let's assert there is a relationship c1 -> c2 and c1 -> c3.
// By relationship, we mean that there is a forward path of updates
// using incr() or next() from one member to the other.
assert!(c1<=c2, "c1={} should be a child of c2={}", c1, c2);
assert!(c2>=c1, "c2={} should be a parent of c1={}", c2, c1);
assert!(c1<=c3, "c1={} c1 should be a child of c3={}", c1, c3);
assert!(c3>=c1, "c3={} c1 should be a parent of c1={}", c3, c1);
// But there is no relationship between c2 and c3.
// In a distributed system with concurrent updates of an object,
// this allows the detection of a conflict.
assert!(!(c2<=c3), "c2={} should not be a child of c3={}", c2, c3);
assert!(!(c2>=c3), "c2={} should not be a parent of c3={}", c2, c3);
assert!(!(c3<=c2), "c3={} should not be a child of c2={}", c3, c2);
assert!(!(c3>=c2), "c3={} should not be a parent of c2={}", c3, c2);Also, two objects having a different history path, but the same final state, will be considered the same. It is up to the program to ensure only one agent updates a given key:
use vclock::VClock;
let mut c1 = VClock::<&str, u64>::new("a"); // c1 is now a:0
let mut c2 = VClock::<&str, u64>::new("b"); // c2 is now b:0
c1.incr(&"c"); // c1 is now a:0, c:0
c1.incr(&"b"); // c1 is now a:0, b:0, c:0
c2.incr(&"a"); // c2 is now a:0, b:0, which is a value c1 never had
c2.incr(&"c"); // c2 is now a:0, b:0, c:0
// The following test shows clocks are considered the same.
// In a distributed system using vector clocks, only one agent
// would update a given key, and when updating this key, it should
// ensure than there is no conflict with the latest version it had locally.
assert_eq!(c1, c2, "c1={} and c2={} represent the same final state", c1, c2);A typical conflict resolution:
use std::collections::HashMap;
use vclock::VClock;
// A dummy object with maintains a vector clock along with some data,
// here just a byte, to avoid complexifying the example with other issues.
#[derive(Default)]
struct Obj {
vc: VClock<String>,
val: u8,
}
impl Obj {
// Update the data stored within the object. If there's no conflict,
// the data is updated, the clock is set to the last value received,
// and the function returns None.
// If there is a conflict, then the previous data is returned, along
// with the merged clock.
fn update(
&mut self,
remote_clock: &VClock<String>,
val: u8,
) -> Option<(u8, VClock<String>)> {
if &self.vc < remote_clock {
// Update value, no conflict
self.vc = remote_clock.clone();
self.val = val;
None
} else {
// History conflict, update the clock, return the value,
// and let the caller deal with it.
Some((self.val, self.vc.clone().combine(remote_clock)))
}
}
}
let mut obj = Obj::default();
let mut h1 = HashMap::<String, usize>::new();
h1.insert("a".to_string(), 42);
let c1 = VClock::<String>::from(h1);
assert_eq!(None, obj.update(&c1, 10), "no history, no problem");
let mut h2 = HashMap::<String, usize>::new();
h2.insert("a".to_string(), 42);
h2.insert("b".to_string(), 10);
let c2 = VClock::<String>::from(h2);
assert_eq!(None, obj.update(&c2, 100), "forward history, updating");
let mut h3 = HashMap::<String, usize>::new();
h3.insert("a".to_string(), 43);
h3.insert("b".to_string(), 9);
let c3 = VClock::<String>::from(h3);
let mut h4 = HashMap::<String, usize>::new();
h4.insert("a".to_string(), 43);
h4.insert("b".to_string(), 10);
let c4 = VClock::<String>::from(h4);
assert_eq!(Some((100, c4)), obj.update(&c3, 50), "conflict between keys");Use custom types:
use vclock::VClock;
use num_bigint::BigUint;
use std::hash::Hash;
#[derive(Hash, Eq, PartialEq, Clone)]
struct Coord{
x: isize,
y: isize,
}
let key = Coord{x: 1, y: 2};
let mut c1 = VClock::<Coord, BigUint>::default();
c1.incr(&key); // BigUint, can grow infinitely... (almost)Modules§
Structs§
- VClock
- Vector clock with generic types.