[pbs-devel] [PATCH proxmox-backup 2/4] datastore: add namespace/group/snapshot indices for reverse lookups

[Christian Ebner]

Adds in-memory indices for namespace, group and snapshots, storing
them in a hashmap for fast lookup based on a generated 64 bit key.

These structs will be used to reference namespaces, groups and
snapshots based on the respective key (NKey, GKey, SKey) in reverse
chunk digest lookup table for better memory allocation.

While namespaces and groups store the plain contents, the snapshot
index in addition to storing the identifying timestamp only, stores
the namespace and group index key, thereby keeping the datastore's
hierarchy context while minimizing memory requirements.

Signed-off-by: Christian Ebner <c.ebner at proxmox.com>
---
 pbs-datastore/src/lib.rs                |   1 +
 pbs-datastore/src/reverse_digest_map.rs | 104 ++++++++++++++++++++++++
 2 files changed, 105 insertions(+)
 create mode 100644 pbs-datastore/src/reverse_digest_map.rs

diff --git a/pbs-datastore/src/lib.rs b/pbs-datastore/src/lib.rs
index 1f7c54ae8..82c0e33d6 100644
--- a/pbs-datastore/src/lib.rs
+++ b/pbs-datastore/src/lib.rs
@@ -225,6 +225,7 @@ pub use hierarchy::{
     ListGroups, ListGroupsType, ListNamespaces, ListNamespacesRecursive, ListSnapshots,
 };
 
+mod reverse_digest_map;
 mod snapshot_reader;
 pub use snapshot_reader::SnapshotReader;
 
diff --git a/pbs-datastore/src/reverse_digest_map.rs b/pbs-datastore/src/reverse_digest_map.rs
new file mode 100644
index 000000000..323e7315d
--- /dev/null
+++ b/pbs-datastore/src/reverse_digest_map.rs
@@ -0,0 +1,104 @@
+use std::collections::{BTreeMap, HashMap};
+use std::hash::BuildHasher;
+
+use pbs_api_types::{BackupDir, BackupGroup, BackupNamespace};
+
+#[derive(Copy, Clone, Eq, Hash, PartialEq, PartialOrd, Ord)]
+/// Backup snapshot index key
+struct SKey(u64);
+
+#[derive(Copy, Clone, Eq, Hash, PartialEq, PartialOrd, Ord)]
+/// Backup group index key
+struct GKey(u64);
+
+#[derive(Copy, Clone, Eq, Hash, PartialEq, PartialOrd, Ord)]
+/// Backup namespace index key
+struct NKey(u64);
+
+#[derive(Copy, Clone, Eq, Hash, PartialEq, PartialOrd, Ord)]
+/// Backup snapshot timestamp
+struct BackupTime(i64);
+
+impl From<i64> for BackupTime {
+    fn from(time: i64) -> Self {
+        Self(time)
+    }
+}
+
+impl From<BackupTime> for i64 {
+    fn from(time: BackupTime) -> i64 {
+        time.0
+    }
+}
+
+#[derive(Default)]
+/// Index to keep track and quickly reference snapshots, associated with the respective group and
+/// namespace indexes.
+struct SnapshotIndex {
+    index: HashMap<SKey, (NKey, GKey, BackupTime)>,
+}
+
+impl SnapshotIndex {
+    /// Index given snapshot and associate to group and namespace by their respective index keys,
+    /// if not already present.
+    ///
+    /// Returns the associated index key.
+    fn insert(&mut self, snapshot_time: BackupTime, nkey: NKey, gkey: GKey) -> SKey {
+        let hasher = self.index.hasher();
+        let key = SKey(hasher.hash_one((nkey, gkey, snapshot_time)));
+        self.index.entry(key).or_insert((nkey, gkey, snapshot_time));
+        key
+    }
+
+    /// Lookup backup snapshot timestamp by key in index, returning also associated namespace and
+    /// group index keys.
+    fn lookup(&self, key: &SKey) -> Option<&(NKey, GKey, BackupTime)> {
+        self.index.get(key)
+    }
+}
+
+#[derive(Default)]
+/// Index to keep track and quickly reference backup groups.
+struct GroupIndex {
+    index: HashMap<GKey, BackupGroup>,
+}
+
+impl GroupIndex {
+    /// Index given backup group if not already present.
+    ///
+    /// Returns the associated index key.
+    fn insert(&mut self, group: BackupGroup) -> GKey {
+        let hasher = self.index.hasher();
+        let key = GKey(hasher.hash_one(&group));
+        self.index.entry(key).or_insert(group);
+        key
+    }
+
+    /// Lookup backup group by key in index
+    fn lookup(&self, key: &GKey) -> Option<&BackupGroup> {
+        self.index.get(key)
+    }
+}
+
+#[derive(Default)]
+/// Index to keep track and quickly reference backup groups.
+struct NamespaceIndex {
+    index: HashMap<NKey, BackupNamespace>,
+}
+
+impl NamespaceIndex {
+    /// Index given backup namespace if not already present.
+    ///
+    /// Returns the associated index key.
+    fn insert(&mut self, namespace: BackupNamespace) -> NKey {
+        let hasher = self.index.hasher();
+        let key = NKey(hasher.hash_one(&namespace));
+        self.index.entry(key).or_insert(namespace);
+        key
+    }
+
+    /// Lookup backup namespace by key in index
+    fn lookup(&self, key: &NKey) -> Option<&BackupNamespace> {
+        self.index.get(key)
+    }
+}
-- 
2.47.3