aboutsummaryrefslogtreecommitdiff
path: root/src/table
diff options
context:
space:
mode:
authorQuentin <quentin@deuxfleurs.fr>2020-11-23 17:49:21 +0100
committerQuentin <quentin@deuxfleurs.fr>2020-11-23 17:49:21 +0100
commit8722e27600ddc3ba869cebc388214f3fabb0ca57 (patch)
tree96a3b7841c05a8eed65c9e5b7a0e04501c84ae06 /src/table
parentba1f8060fe88e9eef97757d33bcc0972a2e327d9 (diff)
downloadgarage-8722e27600ddc3ba869cebc388214f3fabb0ca57.tar.gz
garage-8722e27600ddc3ba869cebc388214f3fabb0ca57.zip
CRDT doc
Diffstat (limited to 'src/table')
-rw-r--r--src/table/crdt.rs32
1 files changed, 28 insertions, 4 deletions
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<T> {
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<K, V> {
vals: Vec<(K, u64, V)>,