diff options
Diffstat (limited to 'src/table/crdt/crdt.rs')
-rw-r--r-- | src/table/crdt/crdt.rs | 71 |
1 files changed, 0 insertions, 71 deletions
diff --git a/src/table/crdt/crdt.rs b/src/table/crdt/crdt.rs deleted file mode 100644 index a8f1b9aa..00000000 --- a/src/table/crdt/crdt.rs +++ /dev/null @@ -1,71 +0,0 @@ -use garage_util::data::*; - -/// Definition of a CRDT - all CRDT Rust types implement this. -/// -/// A CRDT is defined as a merge operator that respects a certain set of axioms. -/// -/// In particular, the merge operator must be commutative, associative, -/// idempotent, and monotonic. -/// In other words, if `a`, `b` and `c` are CRDTs, and `⊔` denotes the merge operator, -/// the following axioms must apply: -/// -/// ```text -/// a ⊔ b = b ⊔ a (commutativity) -/// (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c) (associativity) -/// (a ⊔ b) ⊔ b = a ⊔ b (idempotence) -/// ``` -/// -/// Moreover, the relationship `≥` defined by `a ≥ b ⇔ ∃c. a = b ⊔ c` must be a partial order. -/// This implies a few properties such as: if `a ⊔ b ≠ a`, then there is no `c` such that `(a ⊔ b) ⊔ c = a`, -/// as this would imply a cycle in the partial order. -pub trait Crdt { - /// Merge the two datastructures according to the CRDT rules. - /// `self` is modified to contain the merged CRDT value. `other` is not modified. - /// - /// # Arguments - /// - /// * `other` - the other CRDT we wish to merge with - fn merge(&mut self, other: &Self); -} - -/// All types that implement `Ord` (a total order) can also implement a trivial CRDT -/// defined by the merge rule: `a ⊔ b = max(a, b)`. Implement this trait for your type -/// to enable this behavior. -pub trait AutoCrdt: Ord + Clone + std::fmt::Debug { - /// WARN_IF_DIFFERENT: emit a warning when values differ. Set this to true if - /// different values in your application should never happen. Set this to false - /// if you are actually relying on the semantics of `a ⊔ b = max(a, b)`. - const WARN_IF_DIFFERENT: bool; -} - -impl<T> Crdt for T -where - T: AutoCrdt, -{ - fn merge(&mut self, other: &Self) { - if Self::WARN_IF_DIFFERENT && self != other { - warn!( - "Different CRDT values should be the same (logic error!): {:?} vs {:?}", - self, other - ); - if other > self { - *self = other.clone(); - } - warn!("Making an arbitrary choice: {:?}", self); - } else if other > self { - *self = other.clone(); - } - } -} - -impl AutoCrdt for String { - const WARN_IF_DIFFERENT: bool = true; -} - -impl AutoCrdt for bool { - const WARN_IF_DIFFERENT: bool = true; -} - -impl AutoCrdt for FixedBytes32 { - const WARN_IF_DIFFERENT: bool = true; -} |