pub struct OrSWotSet<const N: usize = 1> { /* private fields */ }Expand description
A CRDT which supports purging of deleted entry tombstones.
This implementation is largely based on the Riak DB implementations of CRDTs. This set in particular is built around the HLCTimestamp which uses the uniqueness guarantees provided by the timestamp to resolve conflicts.
Entries can be marked as deleted via the standard delete method
which internally marks the key as a tombstone.
The tombstones can be purged safely once the set has observed other,
newer operations from the original node which the entry is tied to.
(This is tracked by checking the node field of the timestamp.)
§Sources
Sources are a way of separating two asynchronous operations which both guarantee the order of the operations is correct, but may not be ordered relative to each other.
I.e. if we have the following sources:
Source 1: [1, 2, 4, 5] Source 2: [2, 3, 8]
If we observe the operations from source 2 before source 1 or vice versa, we may miss
operations if we assume one source, this is because of our observer pattern.
Sources allow us to negate this issue while still keeping the observer pattern.
§Last write wins conditions
If two operations occur at the same effective time, i.e. the seconds and counter are the
same on two timestamps. The timestamp with the largest node_id wins.
Consistency is not guaranteed in the event that two operations with the same timestamp from the same node occur on the same key. This means that the node is not generating it’s HLCTimestamp monotonically which is incorrect.
The set may converge in it’s current state with the above situation, but this is not guaranteed
or tested against. It is your responsibility to ensure that timestamps from the same node are
monotonic (as ensured by HLCTimestamp’s send method.)
§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 have only 1 source.
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());
// 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.");Implementations§
Source§impl<const N: usize> OrSWotSet<N>
impl<const N: usize> OrSWotSet<N>
Sourcepub fn diff(&self, other: &OrSWotSet<N>) -> (StateChanges, StateChanges)
pub fn diff(&self, other: &OrSWotSet<N>) -> (StateChanges, StateChanges)
Calculates the deterministic difference between two sets, returning the modified keys and the deleted keys.
This follows the same logic as set.merge(&other) but does not modify
the state of the main set.
NOTE: The difference is not the symmetric difference between the two sets.
Sourcepub fn merge(&mut self, other: OrSWotSet<N>)
pub fn merge(&mut self, other: OrSWotSet<N>)
Merges another set with the current set.
In this case any conflicts are deterministically resolved via the key’s HLCTimestamp any deletes are tracked or ignored depending on this timestamp due to the nature of the ORSWOT CRDT.
Sourcepub fn get(&self, k: &Key) -> Option<&HLCTimestamp>
pub fn get(&self, k: &Key) -> Option<&HLCTimestamp>
Get an entry from the set.
If the entry exists it’s associated HLCTimestamp is returned.
Sourcepub fn purge_old_deletes(&mut self) -> StateChanges
pub fn purge_old_deletes(&mut self) -> StateChanges
Purges and returns any safe to remove tombstone markers from the set.
This is useful for conserving memory and preventing an infinitely growing tombstone state.
Sourcepub fn add_raw_tombstones(&mut self, tombstones: StateChanges)
pub fn add_raw_tombstones(&mut self, tombstones: StateChanges)
Adds a set of tombstones to the state tombstone list.
This bypasses the observation timestamp check, which is useful for replaying purges which may not have been successful.
WARNING: If you do not know where to use this, you do not wan’t to use this.
Sourcepub fn will_apply(&self, key: Key, ts: HLCTimestamp) -> bool
pub fn will_apply(&self, key: Key, ts: HLCTimestamp) -> bool
Checks if the given operation will be applied if it is in fact carried out.
Sourcepub fn insert(&mut self, k: Key, ts: HLCTimestamp) -> bool
pub fn insert(&mut self, k: Key, ts: HLCTimestamp) -> bool
Insert a key into the set with a given timestamp.
If the set has already observed events from the timestamp’s node, this operation is ignored. It is otherwise inserted.
Returns if the value has actually been inserted/updated
in the set. If false, the set’s state has not changed.
Sourcepub fn insert_with_source(
&mut self,
source: usize,
k: Key,
ts: HLCTimestamp,
) -> bool
pub fn insert_with_source( &mut self, source: usize, k: Key, ts: HLCTimestamp, ) -> bool
Insert a key into the set with a given timestamp with a source.
If the set has already observed events from the timestamp’s node, this operation is ignored. It is otherwise inserted.
Returns if the value has actually been inserted/updated
in the set. If false, the set’s state has not changed.
Sourcepub fn delete(&mut self, k: Key, ts: HLCTimestamp) -> bool
pub fn delete(&mut self, k: Key, ts: HLCTimestamp) -> bool
Attempts to remove a key from the set with a given timestamp.
If the set has already observed events from the timestamp’s node, this operation is ignored. It is otherwise inserted.
Returns if the value has actually been inserted/updated
in the set. If false, the set’s state has not changed.
Sourcepub fn delete_with_source(
&mut self,
source: usize,
k: Key,
ts: HLCTimestamp,
) -> bool
pub fn delete_with_source( &mut self, source: usize, k: Key, ts: HLCTimestamp, ) -> bool
Attempts to remove a key from the set with a given timestamp.
If the set has already observed events from the timestamp’s node, this operation is ignored. It is otherwise inserted.
Returns if the value has actually been inserted/updated
in the set. If false, the set’s state has not changed.