aboutsummaryrefslogtreecommitdiff
path: root/src/model/k2v/causality.rs
diff options
context:
space:
mode:
authorAlex Auvolat <alex@adnab.me>2023-01-10 11:59:57 +0100
committerAlex Auvolat <alex@adnab.me>2023-01-10 11:59:57 +0100
commit789540ca379efd710f1e2699fd458b4821f36a5b (patch)
treef4791548e2b2f660a957e01fab14ddd1454a76e2 /src/model/k2v/causality.rs
parent9f5419f465de3ddbb9afc91464d0eb00636049b9 (diff)
downloadgarage-789540ca379efd710f1e2699fd458b4821f36a5b.tar.gz
garage-789540ca379efd710f1e2699fd458b4821f36a5b.zip
Type definition for range seen marker
Diffstat (limited to 'src/model/k2v/causality.rs')
-rw-r--r--src/model/k2v/causality.rs39
1 files changed, 30 insertions, 9 deletions
diff --git a/src/model/k2v/causality.rs b/src/model/k2v/causality.rs
index 9a692870..665b02b2 100644
--- a/src/model/k2v/causality.rs
+++ b/src/model/k2v/causality.rs
@@ -1,3 +1,13 @@
+//! Implements a CausalContext, which is a set of timestamps for each
+//! node -- a vector clock --, indicating that the versions with
+//! timestamps <= these numbers have been seen and can be
+//! overwritten by a subsequent write.
+//!
+//! The textual representation of a CausalContext, which we call a
+//! "causality token", is used in the API and must be sent along with
+//! each write or delete operation to indicate the previously seen
+//! versions that we want to overwrite or delete.
+
use std::collections::BTreeMap;
use std::convert::TryInto;
@@ -9,23 +19,36 @@ use garage_util::data::*;
/// of full Garage node IDs which are 256-bit UUIDs.
pub type K2VNodeId = u64;
+pub type VectorClock = BTreeMap<K2VNodeId, u64>;
+
pub fn make_node_id(node_id: Uuid) -> K2VNodeId {
let mut tmp = [0u8; 8];
tmp.copy_from_slice(&node_id.as_slice()[..8]);
u64::from_be_bytes(tmp)
}
-#[derive(PartialEq, Eq, Debug, Serialize, Deserialize)]
+pub fn vclock_gt(a: &VectorClock, b: &VectorClock) -> bool {
+ a.iter().any(|(n, ts)| ts > b.get(n).unwrap_or(&0))
+}
+
+pub fn vclock_max(a: &VectorClock, b: &VectorClock) -> VectorClock {
+ let mut ret = a.clone();
+ for (n, ts) in b.iter() {
+ let ent = ret.entry(*n).or_insert(0);
+ *ent = std::cmp::max(*ts, *ent);
+ }
+ ret
+}
+
+#[derive(PartialEq, Eq, Debug, Serialize, Deserialize, Default)]
pub struct CausalContext {
- pub vector_clock: BTreeMap<K2VNodeId, u64>,
+ pub vector_clock: VectorClock,
}
impl CausalContext {
/// Empty causality context
- pub fn new_empty() -> Self {
- Self {
- vector_clock: BTreeMap::new(),
- }
+ pub fn new() -> Self {
+ Self::default()
}
/// Make binary representation and encode in base64
pub fn serialize(&self) -> String {
@@ -72,9 +95,7 @@ impl CausalContext {
}
/// Check if this causal context contains newer items than another one
pub fn is_newer_than(&self, other: &Self) -> bool {
- self.vector_clock
- .iter()
- .any(|(k, v)| v > other.vector_clock.get(k).unwrap_or(&0))
+ vclock_gt(&self.vector_clock, &other.vector_clock)
}
}