aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/model/bucket_table.rs3
-rw-r--r--src/table/crdt.rs61
2 files changed, 60 insertions, 4 deletions
diff --git a/src/model/bucket_table.rs b/src/model/bucket_table.rs
index b7f24d71..11f103ff 100644
--- a/src/model/bucket_table.rs
+++ b/src/model/bucket_table.rs
@@ -8,6 +8,9 @@ use garage_util::error::Error;
use crate::key_table::PermissionSet;
+// We import the same file but in its version 0.1.0.
+// We can then access v0.1.0 data structures.
+// We use them to perform migrations.
use model010::bucket_table as prev;
#[derive(PartialEq, Clone, Debug, Serialize, Deserialize)]
diff --git a/src/table/crdt.rs b/src/table/crdt.rs
index 2b903cf0..b0323a66 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,24 @@ where
// ---- LWW Register ----
+/// Last Write Win (LWW)
+///
+/// LWW is based on time, the most recent write wins.
+/// As multiple computers clocks are always desynchronized,
+/// when operations are close enough, it is equivalent to
+/// take one copy and drop the other one.
+///
+/// Given that clocks are not too desynchronized, this assumption
+/// is enough for most cases, as there is few chance that two humans
+/// coordonate themself faster than the time difference between two NTP servers.
+///
+/// As a more concret example, let's suppose you want to upload a file
+/// with the same key (path) in the same bucket at the very same time.
+/// For each request, the file will be timestamped by the receiving server
+/// and may differ from what you observed with your atomic clock!
+///
+/// This scheme is used by AWS S3 or Soundcloud and often without knowing
+/// in entreprise when reconciliating databases with ad-hoc scripts.
#[derive(Clone, Debug, Serialize, Deserialize, PartialEq)]
pub struct LWW<T> {
ts: u64,
@@ -29,22 +66,36 @@ impl<T> LWW<T>
where
T: CRDT,
{
+ /// Creates a new CRDT
+ ///
+ /// CRDT's internal timestamp is set with current node's clock.
pub fn new(value: T) -> Self {
Self {
ts: now_msec(),
v: value,
}
}
+
+ /// Build a new CRDT from a previous non-compatible one
+ ///
+ /// Compared to new, the CRDT's timestamp is not set to now
+ /// but must be set to the previous, non-compatible, CRDT's timestamp.
pub fn migrate_from_raw(ts: u64, value: T) -> Self {
Self { ts, v: value }
}
+
+ /// Update the LWW CRDT while keeping some causal ordering.
pub fn update(&mut self, new_value: T) {
self.ts = std::cmp::max(self.ts + 1, now_msec());
self.v = new_value;
}
+
+ /// Get the CRDT value
pub fn get(&self) -> &T {
&self.v
}
+
+ /// Get a mutable value for the CRDT
pub fn get_mut(&mut self) -> &mut T {
&mut self.v
}
@@ -64,8 +115,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 +139,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)>,