From 8722e27600ddc3ba869cebc388214f3fabb0ca57 Mon Sep 17 00:00:00 2001 From: Quentin Date: Mon, 23 Nov 2020 17:49:21 +0100 Subject: CRDT doc --- src/table/crdt.rs | 32 ++++++++++++++++++++++++++++---- 1 file changed, 28 insertions(+), 4 deletions(-) (limited to 'src/table') diff --git a/src/table/crdt.rs b/src/table/crdt.rs index 2b903cf0..3e5e8317 100644 --- a/src/table/crdt.rs +++ b/src/table/crdt.rs @@ -2,7 +2,26 @@ use serde::{Deserialize, Serialize}; use garage_util::data::*; +/// Conflict-free replicated data type (CRDT) +/// +/// CRDT are a type of data structures that do not require coordination. +/// In other words, we can edit them in parallel, we will always +/// find a way to merge it. +/// +/// A general example is a counter. Its initial value is 0. +/// Alice and Bob get a copy of the counter. +/// Alice does +1 on her copy, she reads 1. +/// Bob does +3 on his copy, he reads 3. +/// Now, it is easy to merge their counters, order does not count: +/// we always get 4. +/// +/// Learn more about CRDT [on Wikipedia](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type) pub trait CRDT { + /// Merge the two datastructures according to the CRDT rules + /// + /// # Arguments + /// + /// * `other` - the other copy of the CRDT fn merge(&mut self, other: &Self); } @@ -19,6 +38,9 @@ where // ---- LWW Register ---- +/// Last Write Win (LWW) +/// +/// LWW is a very simple #[derive(Clone, Debug, Serialize, Deserialize, PartialEq)] pub struct LWW { ts: u64, @@ -64,8 +86,9 @@ where } } -// ---- Boolean (true as absorbing state) ---- - +/// Boolean +/// +/// with True as absorbing state #[derive(Clone, Copy, Debug, Serialize, Deserialize, PartialEq)] pub struct Bool(bool); @@ -87,8 +110,9 @@ impl CRDT for Bool { } } -// ---- LWW Map ---- - +/// Last Write Win Map +/// +/// #[derive(Clone, Debug, Serialize, Deserialize, PartialEq)] pub struct LWWMap { vals: Vec<(K, u64, V)>, -- cgit v1.2.3