From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from firstgate.proxmox.com (firstgate.proxmox.com [IPv6:2a01:7e0:0:424::9]) by lore.proxmox.com (Postfix) with ESMTPS id 65C6D1FF146 for ; Mon, 19 Jan 2026 14:27:16 +0100 (CET) Received: from firstgate.proxmox.com (localhost [127.0.0.1]) by firstgate.proxmox.com (Proxmox) with ESMTP id 8E5401EC61; Mon, 19 Jan 2026 14:27:24 +0100 (CET) From: Christian Ebner To: pbs-devel@lists.proxmox.com Date: Mon, 19 Jan 2026 14:27:05 +0100 Message-ID: <20260119132707.686523-3-c.ebner@proxmox.com> X-Mailer: git-send-email 2.47.3 In-Reply-To: <20260119132707.686523-1-c.ebner@proxmox.com> References: <20260119132707.686523-1-c.ebner@proxmox.com> MIME-Version: 1.0 X-Bm-Milter-Handled: 55990f41-d878-4baa-be0a-ee34c49e34d2 X-Bm-Transport-Timestamp: 1768829187266 X-SPAM-LEVEL: Spam detection results: 0 AWL 0.048 Adjusted score from AWL reputation of From: address BAYES_00 -1.9 Bayes spam probability is 0 to 1% DMARC_MISSING 0.1 Missing DMARC policy KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment SPF_HELO_NONE 0.001 SPF: HELO does not publish an SPF Record SPF_PASS -0.001 SPF: sender matches SPF record Subject: [pbs-devel] [PATCH proxmox-backup 2/4] datastore: add namespace/group/snapshot indices for reverse lookups X-BeenThere: pbs-devel@lists.proxmox.com X-Mailman-Version: 2.1.29 Precedence: list List-Id: Proxmox Backup Server development discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Reply-To: Proxmox Backup Server development discussion Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Errors-To: pbs-devel-bounces@lists.proxmox.com Sender: "pbs-devel" 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 --- 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 for BackupTime { + fn from(time: i64) -> Self { + Self(time) + } +} + +impl From 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, +} + +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, +} + +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, +} + +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 _______________________________________________ pbs-devel mailing list pbs-devel@lists.proxmox.com https://lists.proxmox.com/cgi-bin/mailman/listinfo/pbs-devel