From e02e9e035e269cd6b660c92706db424a2edb5306 Mon Sep 17 00:00:00 2001
From: Alex Auvolat <alex@adnab.me>
Date: Fri, 20 Nov 2020 21:15:24 +0100
Subject: Begin improve model to use better CRDTs

---
 src/model/key_table.rs | 121 +++++++++++++++++++++----------------------------
 1 file changed, 51 insertions(+), 70 deletions(-)

(limited to 'src/model')

diff --git a/src/model/key_table.rs b/src/model/key_table.rs
index 05b938ce..2b825aa3 100644
--- a/src/model/key_table.rs
+++ b/src/model/key_table.rs
@@ -2,9 +2,12 @@ use async_trait::async_trait;
 use serde::{Deserialize, Serialize};
 
 use garage_table::*;
-use garage_util::data::*;
+use garage_table::crdt::CRDT;
+
 use garage_util::error::Error;
 
+use model010::key_table as prev;
+
 #[derive(PartialEq, Clone, Debug, Serialize, Deserialize)]
 pub struct Key {
 	// Primary key
@@ -14,83 +17,56 @@ pub struct Key {
 	pub secret_key: String,
 
 	// Name
-	pub name: String,
-	pub name_timestamp: u64,
+	pub name: crdt::LWW<String>,
 
 	// Deletion
-	pub deleted: bool,
+	pub deleted: crdt::Bool,
 
 	// Authorized keys
-	authorized_buckets: Vec<AllowedBucket>,
+	pub authorized_buckets: crdt::LWWMap<String, PermissionSet>,
+
+	// CRDT interaction: deleted implies authorized_buckets is empty
 }
 
 impl Key {
-	pub fn new(name: String, buckets: Vec<AllowedBucket>) -> Self {
+	pub fn new(name: String) -> Self {
 		let key_id = format!("GK{}", hex::encode(&rand::random::<[u8; 12]>()[..]));
 		let secret_key = hex::encode(&rand::random::<[u8; 32]>()[..]);
-		let mut ret = Self {
+		let ret = Self {
 			key_id,
 			secret_key,
-			name,
-			name_timestamp: now_msec(),
-			deleted: false,
-			authorized_buckets: vec![],
+			name: crdt::LWW::new(name),
+			deleted: crdt::Bool::new(false),
+			authorized_buckets: crdt::LWWMap::new(),
 		};
-		for b in buckets {
-			ret.add_bucket(b)
-				.expect("Duplicate AllowedBucket in Key constructor");
-		}
 		ret
 	}
 	pub fn delete(key_id: String) -> Self {
 		Self {
 			key_id,
 			secret_key: "".into(),
-			name: "".into(),
-			name_timestamp: now_msec(),
-			deleted: true,
-			authorized_buckets: vec![],
+			name: crdt::LWW::new("".to_string()),
+			deleted: crdt::Bool::new(true),
+			authorized_buckets: crdt::LWWMap::new(),
 		}
 	}
 	/// Add an authorized bucket, only if it wasn't there before
-	pub fn add_bucket(&mut self, new: AllowedBucket) -> Result<(), ()> {
-		match self
-			.authorized_buckets
-			.binary_search_by(|b| b.bucket.cmp(&new.bucket))
-		{
-			Err(i) => {
-				self.authorized_buckets.insert(i, new);
-				Ok(())
-			}
-			Ok(_) => Err(()),
-		}
-	}
-	pub fn authorized_buckets(&self) -> &[AllowedBucket] {
-		&self.authorized_buckets[..]
-	}
-	pub fn clear_buckets(&mut self) {
-		self.authorized_buckets.clear();
-	}
 	pub fn allow_read(&self, bucket: &str) -> bool {
 		self.authorized_buckets
-			.iter()
-			.find(|x| x.bucket.as_str() == bucket)
+			.get(&bucket.to_string())
 			.map(|x| x.allow_read)
 			.unwrap_or(false)
 	}
 	pub fn allow_write(&self, bucket: &str) -> bool {
 		self.authorized_buckets
-			.iter()
-			.find(|x| x.bucket.as_str() == bucket)
+			.get(&bucket.to_string())
 			.map(|x| x.allow_write)
 			.unwrap_or(false)
 	}
 }
 
-#[derive(PartialEq, Clone, Debug, Serialize, Deserialize)]
-pub struct AllowedBucket {
-	pub bucket: String,
-	pub timestamp: u64,
+#[derive(PartialOrd, Ord, PartialEq, Eq, Clone, Debug, Serialize, Deserialize)]
+pub struct PermissionSet {
 	pub allow_read: bool,
 	pub allow_write: bool,
 }
@@ -104,35 +80,15 @@ impl Entry<EmptyKey, String> for Key {
 	}
 
 	fn merge(&mut self, other: &Self) {
-		if other.name_timestamp > self.name_timestamp {
-			self.name_timestamp = other.name_timestamp;
-			self.name = other.name.clone();
-		}
+		self.name.merge(&other.name);
+		self.deleted.merge(&other.deleted);
 
-		if other.deleted {
-			self.deleted = true;
-		}
-		if self.deleted {
+		if self.deleted.get() {
 			self.authorized_buckets.clear();
 			return;
 		}
 
-		for ab in other.authorized_buckets.iter() {
-			match self
-				.authorized_buckets
-				.binary_search_by(|our_ab| our_ab.bucket.cmp(&ab.bucket))
-			{
-				Ok(i) => {
-					let our_ab = &mut self.authorized_buckets[i];
-					if ab.timestamp > our_ab.timestamp {
-						*our_ab = ab.clone();
-					}
-				}
-				Err(i) => {
-					self.authorized_buckets.insert(i, ab.clone());
-				}
-			}
-		}
+		self.authorized_buckets.merge(&other.authorized_buckets);
 	}
 }
 
@@ -150,6 +106,31 @@ impl TableSchema for KeyTable {
 	}
 
 	fn matches_filter(entry: &Self::E, filter: &Self::Filter) -> bool {
-		filter.apply(entry.deleted)
+		filter.apply(entry.deleted.get())
+	}
+
+	fn try_migrate(bytes: &[u8]) -> Option<Self::E> {
+		let old = match rmp_serde::decode::from_read_ref::<_, prev::Key>(bytes) {
+			Ok(x) => x,
+			Err(_) => return None,
+		};
+		let mut new = Self::E {
+			key_id: old.key_id.clone(),
+			secret_key: old.secret_key.clone(),
+			name: crdt::LWW::migrate_from_raw(old.name_timestamp, old.name.clone()),
+			deleted: crdt::Bool::new(old.deleted),
+			authorized_buckets: crdt::LWWMap::new(),
+		};
+		for ab in old.authorized_buckets() {
+			let it = crdt::LWWMap::migrate_from_raw_item(
+				ab.bucket.clone(),
+				ab.timestamp,
+				PermissionSet{
+					allow_read: ab.allow_read,
+					allow_write: ab.allow_write,
+				});
+			new.authorized_buckets.merge(&it);
+		}
+		Some(new)
 	}
 }
-- 
cgit v1.2.3