#crdt #distributed-database #distributed-systems #timestamp #clock #consistent #store

datacake-crdt

A conflict free replicated datatype based on a hybrid logical clock implementation for building eventually consistent data stores

5 unstable releases

0.4.1 Jun 22, 2023
0.4.0 Jan 5, 2023
0.3.0 Dec 6, 2022
0.1.2 Oct 1, 2022

#155 in Concurrency

Download history 1/week @ 2023-11-20 1/week @ 2023-11-27 7/week @ 2024-02-12 15/week @ 2024-02-19 27/week @ 2024-02-26 13/week @ 2024-03-04

62 downloads per month
Used in 7 crates (6 directly)

MIT license

64KB
1K SLoC

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};

fn main() {        
    let mut node_a = HLCTimestamp::now(0, 0);
    
    // Simulating a node begin slightly ahead in time.
    let mut node_b = HLCTimestamp::new(node_a.datacake_timestamp() + Duration::from_secs(5), 0, 1);
    
    let mut node_a_set = OrSWotSet::default();
    let mut node_b_set = OrSWotSet::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

Dependencies

~0.3–1MB
~23K SLoC