Crate datacake_crdt

source ·
Expand description

Datacake CRDT

An implementation of Riak’s ORSWOT CRDT which is a CRDT which allows for removal of old tombstones once a new event has been observed.

The set is built upon the second supported structure HLCTimestamp which is a Hybrid Logical Clock which guarantees the timestamp will always be unique and monotonic (providing it’s used correctly.)

Basic Example

use std::time::Duration;
use datacake_crdt::{OrSWotSet, HLCTimestamp};

let mut node_a = HLCTimestamp::now(0, 0);

// Simulating a node begin slightly ahead.
let mut node_b = HLCTimestamp::new(node_a.datacake_timestamp() + Duration::from_secs(5), 0, 1);

// We only have one effective source here.
let mut node_a_set = OrSWotSet::<1>::default();
let mut node_b_set = OrSWotSet::<1>::default();

// Insert a new key with a new timestamp in set A.
node_a_set.insert(1, node_a.send().unwrap());

// Insert a new entry in set B.
node_b_set.insert(2, node_b.send().unwrap());

// Let some time pass for demonstration purposes.
std::thread::sleep(Duration::from_millis(500));

// Set A has key `1` removed.
node_a_set.delete(1, node_a.send().unwrap());

// Merging set B with set A and vice versa.
// Our sets are now aligned without conflicts.
node_b_set.merge(node_a_set.clone());
node_a_set.merge(node_b_set.clone());

// Set A and B should both see that key `1` has been deleted.
assert!(node_a_set.get(&1).is_none(), "Key should be correctly removed.");
assert!(node_b_set.get(&1).is_none(), "Key should be correctly removed.");

Inspirations

Structs

  • HLCTimestamp
    A HLC (Hybrid Logical Clock) timestamp implementation.
  • InvalidFormat
    The provided timestamp in the given string format is invalid and unable to be parsed.
  • OrSWotSet
    A CRDT which supports purging of deleted entry tombstones.

Enums

  • TimestampError
    The clock was unable to produce a timestamp due to an error.

Constants

  • DATACAKE_EPOCH
    The UNIX timestamp which datacake timestamps start counting from.
  • TIMESTAMP_MAX
    The maximum timestamp value in seconds that the timestamp can support (32 bits.)

Functions

Type Definitions