Crate vclock

VClock is an experimental 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::new("a");     // c1 is now a:1
let mut c2 = VClock::new("b"); // c2 is now b:1
c2.incr("a");                  // c1 is now a:1,b:1
assert!(c1 < c2, "c1 is a parent 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:4, b:1

let c2 = c1.next("a"); // c2 is now a:5,b:1
let c3 = c1.next("b"); // c3 is now a:4,b:2

// 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={} is a parent of c2={}", c1, c2);
assert!(c2>=c1, "c2={} is a child of c1={}", c2, c1);
assert!(c1<=c3, "c1={} c1 is a parent of c3={}", c1, c3);
assert!(c3>=c1, "c3={} c1 is a child 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={} is not a parent of c3={}", c2, c3);
assert!(!(c2>=c3), "c2={} is not a child of c3={}", c2, c3);
assert!(!(c3<=c2), "c3={} is not a parent of c2={}", c3, c2);
assert!(!(c3>=c2), "c3={} is not a child 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::new("a"); // c1 is now a:1
let mut c2 = VClock::new("b"); // c2 is now b:1
c1.incr("c"); // c1 is now a:1, c:1
c1.incr("b"); // c1 is now a:1, b:1, c:1
c2.incr("a"); // c2 is now a:1, b:1, which is a value c1 never had
c2.incr("c"); // c2 is now a:1, b:1, c:1

// 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<'a> {
    vc: VClock<&'a str>,
    val: u8,
}

impl<'a> Obj<'a> {
    // 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<&'a str>,
        val: u8,
    ) -> Option<(u8, VClock<&str>)> {
        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.merge(remote_clock)))
        }
    }
}

let mut obj = Obj::default();
let mut h1 = HashMap::<&str,u64>::new();
h1.insert("a", 42);
let c1 = VClock::<&str>::from(h1);
assert_eq!(None, obj.update(&c1, 10), "no history, no problem");

let mut h2 = HashMap::<&str,u64>::new();
h2.insert("a", 42);
h2.insert("b", 10);
let c2 = VClock::<&str>::from(h2);
assert_eq!(None, obj.update(&c2, 100), "forward history, updating");

let mut h3 = HashMap::<&str,u64>::new();
h3.insert("a", 43);
h3.insert("b", 9);
let c3 = VClock::<&str>::from(h3);
let mut h4 = HashMap::<&str,u64>::new();
h4.insert("a", 43);
h4.insert("b", 10);
let c4 = VClock::<&str>::from(h4);
assert_eq!(Some((100, c4)), obj.update(&c3, 50), "conflict between keys");

Structs

VClock

VClock encapsulates the vector clock data. Internally it's just a simple hash map containing integers.