diff options
| -rw-r--r-- | src/model/bucket_table.rs | 3 | ||||
| -rw-r--r-- | src/table/crdt.rs | 61 |
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)>, |