[PATCH proxmox{,-backup} v2 00/14] fix #5799: gather datastore usage statistics on per-entity level

[PATCH proxmox{,-backup} v2 00/14] fix #5799: gather datastore usage statistics on per-entity level

[Christian Ebner]

Issue #5799 requested to gather and cache information about raw
storage size of uniquely referenced chunks and deduplication factor
for backup groups, with the intent to provide better introspection
for storage optimization by allowing to pruning specific backup
groups/snapshot based on this additional information.

This patches implement the accumulation of such statistics during
garbage collection, by tracking chunk to namespace/group/snapshot
association in memory efficient lookup structures by storing compact
vectors but providing also fast lookups via a hashtable where
required.

During phase 1, snapshots referencing chunk digests are stored
together with their association to namespace, group and snapshot
hierarchy. During phase 2 raw chunk size is collected while iterating
over chunk files.

Finally, the statistics are gathered by accumulating the counts of
each chunk digest for each of the namespace/group/snapshot, taking
advantage of the fast lookup map.

Since this feature requires additional memory during garbage
collection it is provided as opt-in feature, which can be enabled
per-datastore via the `extended-usage-statistics` in the datastore
config.

Additionally, the gathered statistics are stored on the datastore
and can be retrieved via CLI or inspected in a new `Statistics`
tab.

Memory usage was evaluated using the following procedure:
Differences in RSS for a garbage collection run with and without
the statistics gathering was performed.
Max memory usage during garbage collection was measured by taking the
maximum obtained from
`watch -n 1 "ps -p $(pidof proxmox-backup-proxy) -o rss | tail -n 1 | tee -a ps-rss.out"`
and subtracted by the initial RSS values after service restart.
This was performed on 2 independent datastores with different contents
and GC LRU cache disabled by setting to 0:

| Delta RSS (MiB) | index files | chunk count | deduplication factor |
----------------------------------------------------------------------
|          85.890 |         179 |      778005 |                 3.37 |
|          71.378 |         157 |      555392 |                 4.99 |
----------------------------------------------------------------------

Changes since RFC:
This is basically a complete rewrite in order to optimize memory usage
during chunk gathering while keeping lookups fast. Therefore, IndexMap
and IndexSet have been implemented, storing the chunk info and their
association to the respective hierarchical datastore entity in a
compact vector while keeping fast lookup capability via hashes.

Link to the bugtracker issue:
https://bugzilla.proxmox.com/show_bug.cgi?id=5799


proxmox:

Christian Ebner (4):
  pbs-api-types: avoid reimplementation of is_false helper
  pbs-api-types: add types for fine-grained datastore usage statistics
  pbs-api-types: add schema for datastore usage statistics listing
  pbs-api-types: add flag to control usage statistics collection

 pbs-api-types/src/datastore.rs | 116 +++++++++++++++++++++++++++++++++
 pbs-api-types/src/jobs.rs      |   6 +-
 pbs-api-types/src/lib.rs       |   5 ++
 pbs-api-types/src/user.rs      |   6 +-
 4 files changed, 123 insertions(+), 10 deletions(-)


proxmox-backup:

Christian Ebner (10):
  chunk store: restrict chunk sweep helper method to module parent
  datastore: implement index map for compact chunk usage tracking
  datastore: implement chunk map for collecting chunk usage statistics
  datastore: cleanup persisted statistics during datastore destruction
  fix #5799: GC: track chunk digests and accumulate statistics
  api: config: allow modification of extended-usage-statistics flag
  ui: expose extended usage statistics flag in datastore options
  api: admin: add endpoint to fetch fine-grained datastore usage stats
  bin: manager: allow listing of extended usage statistics via cli
  ui: implement statistics tab for datastore panel

 Cargo.toml                                  |   1 +
 pbs-datastore/Cargo.toml                    |   1 +
 pbs-datastore/src/chunk_map.rs              | 315 ++++++++++++++
 pbs-datastore/src/chunk_store.rs            |  11 +-
 pbs-datastore/src/datastore.rs              |  84 +++-
 pbs-datastore/src/index_map.rs              | 101 +++++
 pbs-datastore/src/lib.rs                    |   2 +
 src/api2/admin/datastore.rs                 |  35 +-
 src/api2/config/datastore.rs                |   9 +
 src/bin/proxmox_backup_manager/datastore.rs |  47 ++
 www/Makefile                                |   1 +
 www/datastore/OptionView.js                 |  19 +
 www/datastore/Panel.js                      |   8 +
 www/datastore/Statistics.js                 | 452 ++++++++++++++++++++
 14 files changed, 1077 insertions(+), 9 deletions(-)
 create mode 100644 pbs-datastore/src/chunk_map.rs
 create mode 100644 pbs-datastore/src/index_map.rs
 create mode 100644 www/datastore/Statistics.js


Summary over all repositories:
  18 files changed, 1200 insertions(+), 19 deletions(-)

-- 
Generated by murpp 0.11.0

[PATCH proxmox v2 01/14] pbs-api-types: avoid reimplementation of is_false helper

[Christian Ebner]

Already implemented twice, move to a common crate wide implementation
so the same can be reused also for future locations requiring serde
deserialization to be skipped.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-api-types/src/jobs.rs | 6 +-----
 pbs-api-types/src/lib.rs  | 5 +++++
 pbs-api-types/src/user.rs | 6 +-----
 3 files changed, 7 insertions(+), 10 deletions(-)

diff --git a/pbs-api-types/src/jobs.rs b/pbs-api-types/src/jobs.rs
index 9a5d2b77..e93a1ce4 100644
--- a/pbs-api-types/src/jobs.rs
+++ b/pbs-api-types/src/jobs.rs
@@ -919,7 +919,7 @@ pub struct PruneJobConfig {
     pub store: String,
 
     /// Disable this job.
-    #[serde(default, skip_serializing_if = "is_false")]
+    #[serde(default, skip_serializing_if = "crate::is_false")]
     #[updater(serde(skip_serializing_if = "Option::is_none"))]
     pub disable: bool,
 
@@ -938,10 +938,6 @@ impl PruneJobConfig {
     }
 }
 
-fn is_false(b: &bool) -> bool {
-    !b
-}
-
 #[api(
     properties: {
         config: {
diff --git a/pbs-api-types/src/lib.rs b/pbs-api-types/src/lib.rs
index 21ef733d..1555f3f8 100644
--- a/pbs-api-types/src/lib.rs
+++ b/pbs-api-types/src/lib.rs
@@ -486,3 +486,8 @@ impl Default for PbsRealmConfig {
         }
     }
 }
+
+// Helper to skip serialization of boolean flags
+pub(crate) fn is_false(b: &bool) -> bool {
+    !b
+}
diff --git a/pbs-api-types/src/user.rs b/pbs-api-types/src/user.rs
index a5368916..3f864ffb 100644
--- a/pbs-api-types/src/user.rs
+++ b/pbs-api-types/src/user.rs
@@ -109,16 +109,12 @@ pub struct UserWithTokens {
     pub email: Option<String>,
     #[serde(skip_serializing_if = "Vec::is_empty", default)]
     pub tokens: Vec<ApiToken>,
-    #[serde(skip_serializing_if = "bool_is_false", default)]
+    #[serde(skip_serializing_if = "crate::is_false", default)]
     pub totp_locked: bool,
     #[serde(skip_serializing_if = "Option::is_none")]
     pub tfa_locked_until: Option<i64>,
 }
 
-fn bool_is_false(b: &bool) -> bool {
-    !b
-}
-
 #[api(
     properties: {
         tokenid: {
-- 
2.47.3

[PATCH proxmox v2 02/14] pbs-api-types: add types for fine-grained datastore usage statistics

[Christian Ebner]

Defines the api types for chunk data usage statistics to be used on
datastore, namespace, group and snapshot hierarchy levels, as well
as the list type to fetch these per-level usage statistics via the
api.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-api-types/src/datastore.rs | 97 ++++++++++++++++++++++++++++++++++
 1 file changed, 97 insertions(+)

diff --git a/pbs-api-types/src/datastore.rs b/pbs-api-types/src/datastore.rs
index 93ccaf07..05baa1b3 100644
--- a/pbs-api-types/src/datastore.rs
+++ b/pbs-api-types/src/datastore.rs
@@ -1582,6 +1582,103 @@ pub struct NamespaceListItem {
     pub comment: Option<String>,
 }
 
+#[api(
+    properties: {
+        "raw-size": {
+            type: Integer,
+        },
+        "logical-size": {
+            type: Integer,
+        },
+        "unique-raw-size": {
+            type: Integer,
+        },
+        "reference-count": {
+            type: Integer,
+        },
+        "unique-count": {
+            type: Integer,
+        },
+        "dedup-count": {
+            type: Integer,
+        },
+    }
+)]
+#[derive(Default, Serialize, Deserialize, Clone, PartialEq)]
+#[serde(rename_all = "kebab-case")]
+/// Usage statistics for datastores, namespaces, groups and snapshots.
+pub struct StoreUsageStatistics {
+    /// On disk size of all referenced chunks
+    pub raw_size: u64,
+    /// Logical size of all referenced chunks
+    pub logical_size: u64,
+    /// On disk size of all unique chunks
+    pub unique_raw_size: u64,
+    /// Count of all chunks being referenced
+    pub reference_count: u64,
+    /// Count of unique chunks being referenced
+    pub unique_count: u64,
+    /// Count of chunks with multiple references
+    pub dedup_count: u64,
+}
+
+impl StoreUsageStatistics {
+    /// Account for storage usage by chunk
+    pub fn add(&mut self, raw: u64, logical: u64, unique: bool) {
+        self.raw_size += raw;
+        self.logical_size += logical;
+        self.reference_count += 1;
+        if unique {
+            self.unique_count += 1;
+            self.unique_raw_size += raw;
+        } else {
+            self.dedup_count += 1;
+        }
+    }
+}
+
+#[api(
+    properties: {
+        "ns": {
+            type: BackupNamespace,
+            optional: true,
+        },
+        "backup-type": {
+            type: BackupType,
+            optional: true,
+        },
+        "backup-id": {
+            schema: BACKUP_ID_SCHEMA,
+            optional: true,
+        },
+        "backup-time": {
+            schema: BACKUP_TIME_SCHEMA,
+            optional: true,
+        },
+        "stats": {
+            type: StoreUsageStatistics
+        },
+    },
+)]
+#[derive(Serialize, Deserialize, Clone, PartialEq)]
+#[serde(rename_all = "kebab-case")]
+/// Basic information about a backup group.
+pub struct StatisticsListItem {
+    #[serde(skip_serializing_if = "Option::is_none")]
+    pub ns: Option<BackupNamespace>,
+    #[serde(skip_serializing_if = "Option::is_none")]
+    #[serde(rename = "backup-type")]
+    pub ty: Option<BackupType>,
+    #[serde(skip_serializing_if = "Option::is_none")]
+    #[serde(rename = "backup-id")]
+    pub id: Option<String>,
+    #[serde(rename = "backup-time")]
+    #[serde(skip_serializing_if = "Option::is_none")]
+    pub time: Option<i64>,
+    #[serde(flatten)]
+    pub stats: StoreUsageStatistics,
+}
+
 #[api(
     properties: {
         "backup": { type: BackupDir },
-- 
2.47.3

[PATCH proxmox v2 03/14] pbs-api-types: add schema for datastore usage statistics listing

[Christian Ebner]

Define the schema required for formatting and listing of the output
as table or json via CLI command.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-api-types/src/datastore.rs | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/pbs-api-types/src/datastore.rs b/pbs-api-types/src/datastore.rs
index 05baa1b3..f7a2dab4 100644
--- a/pbs-api-types/src/datastore.rs
+++ b/pbs-api-types/src/datastore.rs
@@ -1969,6 +1969,15 @@ impl DataStoreStatusListItem {
     }
 }
 
+pub const ADMIN_DATASTORE_LIST_STATISTICS_RETURN_TYPE: ReturnType = ReturnType {
+    optional: false,
+    schema: &ArraySchema::new(
+        "Returns the list of fine-grained datastore usage statistics.",
+        &StatisticsListItem::API_SCHEMA,
+    )
+    .schema(),
+};
+
 pub const ADMIN_DATASTORE_LIST_SNAPSHOTS_RETURN_TYPE: ReturnType = ReturnType {
     optional: false,
     schema: &ArraySchema::new(
-- 
2.47.3

[PATCH proxmox v2 04/14] pbs-api-types: add flag to control usage statistics collection

[Christian Ebner]

Adds a flag to the datastore config in order to control when enabling
fine-grained hierarchy level usage statistics for namespaces, groups
and levels during garbage collection.

Defaults to false due to the additional memory requirements for
bookkeeping during garbage collection.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-api-types/src/datastore.rs | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/pbs-api-types/src/datastore.rs b/pbs-api-types/src/datastore.rs
index f7a2dab4..e4ae33ab 100644
--- a/pbs-api-types/src/datastore.rs
+++ b/pbs-api-types/src/datastore.rs
@@ -509,6 +509,11 @@ pub const COUNTER_RESET_SCHEDULE_SCHEMA: Schema =
             optional: true,
             schema: COUNTER_RESET_SCHEDULE_SCHEMA,
         },
+        "extended-usage-statistics": {
+            description: "Collect more fine grained usage statistics during garbage collection",
+            optional: true,
+            type: Boolean,
+        },
     }
 )]
 #[derive(Serialize, Deserialize, Updater, Clone, PartialEq)]
@@ -577,6 +582,10 @@ pub struct DataStoreConfig {
     /// Notification threshold related counter reset schedule
     #[serde(skip_serializing_if = "Option::is_none")]
     pub counter_reset_schedule: Option<String>,
+
+    #[serde(default, skip_serializing_if = "crate::is_false")]
+    #[updater(serde(skip_serializing_if = "Option::is_none"))]
+    pub extended_usage_statistics: bool,
 }
 
 #[api]
@@ -619,6 +628,7 @@ impl DataStoreConfig {
             backend: None,
             notification_thresholds: None,
             counter_reset_schedule: None,
+            extended_usage_statistics: Default::default(),
         }
     }
 
-- 
2.47.3

[PATCH proxmox-backup v2 05/14] chunk store: restrict chunk sweep helper method to module parent

[Christian Ebner]

This method is only used by garbage collection and must not be called
from outside the pbs-datastore crate.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-datastore/src/chunk_store.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/pbs-datastore/src/chunk_store.rs b/pbs-datastore/src/chunk_store.rs
index 6d2ffdbde..ec657092e 100644
--- a/pbs-datastore/src/chunk_store.rs
+++ b/pbs-datastore/src/chunk_store.rs
@@ -434,7 +434,7 @@ impl ChunkStore {
         &self.mutex
     }
 
-    pub fn sweep_unused_chunks(
+    pub(super) fn sweep_unused_chunks(
         &self,
         oldest_writer: i64,
         min_atime: i64,
-- 
2.47.3

[PATCH proxmox-backup v2 06/14] datastore: implement index map for compact chunk usage tracking

[Christian Ebner]

In order to collect usage information on per-namespace/group/snapshot
level, a compact mapping from the chunks to the individual entities
referencing them needs to be established during phase 1 of garbage
collection in order to allow for reverse lookup and accounting during
phase 2, when the actual chunk raw size information is processed.
This needs to be done while keeping the memory footprint small.

IndexSet and IndexMap are therefore implemented, which store the value
or (key, value) in a compact vector, with fast item access by index,
while keeping a hashtable for fast lookup via key/value. Hash
collisions are taken into account by item comparison. The usable
index is kept generic to allow for different type checked index
implementations.

This follows along the implementation of hashed_index create,
implementing and exposing required functionality only.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 Cargo.toml                     |   1 +
 pbs-datastore/Cargo.toml       |   1 +
 pbs-datastore/src/index_map.rs | 101 +++++++++++++++++++++++++++++++++
 pbs-datastore/src/lib.rs       |   1 +
 4 files changed, 104 insertions(+)
 create mode 100644 pbs-datastore/src/index_map.rs

diff --git a/Cargo.toml b/Cargo.toml
index 6d82326c0..7d838f110 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -136,6 +136,7 @@ foreign-types = "0.3"
 futures = "0.3"
 h2 = { version = "0.4", features = [ "stream" ] }
 handlebars = "3.0"
+hashbrown = "0.14"
 hex = "0.4.3"
 hickory-resolver = { version = "0.24.1", default-features = false, features = [ "system-config", "tokio-runtime" ] }
 http-body-util = "0.1"
diff --git a/pbs-datastore/Cargo.toml b/pbs-datastore/Cargo.toml
index b51438dc6..c18e5b6b0 100644
--- a/pbs-datastore/Cargo.toml
+++ b/pbs-datastore/Cargo.toml
@@ -12,6 +12,7 @@ const_format.workspace = true
 crc32fast.workspace = true
 endian_trait.workspace = true
 futures.workspace = true
+hashbrown.workspace = true
 hex = { workspace = true, features = [ "serde" ] }
 http-body-util.workspace = true
 hyper.workspace = true
diff --git a/pbs-datastore/src/index_map.rs b/pbs-datastore/src/index_map.rs
new file mode 100644
index 000000000..f8affaf76
--- /dev/null
+++ b/pbs-datastore/src/index_map.rs
@@ -0,0 +1,101 @@
+use std::hash::{BuildHasher, Hash};
+
+use hashbrown::HashTable;
+use hashbrown::hash_map::DefaultHashBuilder;
+
+pub struct IndexSet<E, I = u32, H = DefaultHashBuilder> {
+    // Stores the hash of and entry and its index in the entries.
+    // Hash is not guaranteed to be collision free, so entries must be compared.
+    table: HashTable<I>,
+    entries: Vec<E>,
+    hasher: H,
+}
+
+impl<E, I> IndexSet<E, I> {
+    pub fn new() -> Self {
+        Self {
+            table: HashTable::<I>::new(),
+            entries: Vec::new(),
+            hasher: DefaultHashBuilder::default(),
+        }
+    }
+}
+
+impl<E: Hash + Eq, I: Copy + From<usize> + Into<usize>> IndexSet<E, I> {
+    pub fn insert(&mut self, entry: E) -> I {
+        let hash = self.hasher.hash_one(&entry);
+        if let Some(idx) = self
+            .table
+            .find(hash, |idx| self.entries[I::into(*idx)] == entry)
+        {
+            return *idx;
+        }
+        let idx = I::from(self.entries.len());
+        self.entries.push(entry);
+        self.table.insert_unique(hash, idx, |idx| {
+            self.hasher.hash_one(&self.entries[I::into(*idx)])
+        });
+        idx
+    }
+
+    pub fn lookup(&self, idx: I) -> Option<&E> {
+        self.entries.get(I::into(idx))
+    }
+}
+
+pub struct Entry<K, V> {
+    pub key: K,
+    pub value: V,
+}
+
+pub struct IndexMap<K, V, I = u32, H = DefaultHashBuilder> {
+    // Stores the hash of and entry and its index in the entries.
+    // Hash is not guaranteed to be collision free, so entry keys must be compared.
+    table: HashTable<I>,
+    entries: Vec<Entry<K, V>>,
+    hasher: H,
+}
+
+impl<K, V, I> IndexMap<K, V, I> {
+    pub fn new() -> Self {
+        Self {
+            table: HashTable::new(),
+            entries: Vec::new(),
+            hasher: DefaultHashBuilder::default(),
+        }
+    }
+}
+
+impl<K: Hash + Eq, V, I: Copy + From<usize> + Into<usize>> IndexMap<K, V, I> {
+    pub fn insert(&mut self, entry: Entry<K, V>) -> I {
+        let hash = self.hasher.hash_one(&entry.key);
+        if let Some(idx) = self.get_index_of(hash, &entry.key) {
+            self.entries[I::into(idx)].value = entry.value;
+            return idx;
+        }
+        let idx = I::from(self.entries.len());
+        self.entries.push(entry);
+        self.table.insert_unique(hash, idx, |idx| {
+            self.hasher.hash_one(&self.entries[I::into(*idx)].key)
+        });
+        idx
+    }
+
+    pub fn lookup(&self, idx: I) -> Option<&Entry<K, V>> {
+        self.entries.get(I::into(idx))
+    }
+
+    /// Get mutable reference to entry value with given key
+    pub fn get_mut(&mut self, key: &K) -> Option<&mut Entry<K, V>> {
+        let hash = self.hasher.hash_one(key);
+        self.get_index_of(hash, key)
+            .and_then(|idx| self.entries.get_mut(I::into(idx)))
+    }
+
+    /// Find index for entry by its hash, comparig with key to detect hash collisions
+    fn get_index_of(&self, hash: u64, key: &K) -> Option<I> {
+        self.table
+            .find(hash, |idx| &self.entries[I::into(*idx)].key == key)
+            .copied()
+    }
+}
diff --git a/pbs-datastore/src/lib.rs b/pbs-datastore/src/lib.rs
index d9d7a4cb6..4e1222f9d 100644
--- a/pbs-datastore/src/lib.rs
+++ b/pbs-datastore/src/lib.rs
@@ -191,6 +191,7 @@ pub mod data_blob;
 pub mod data_blob_reader;
 pub mod file_formats;
 pub mod index;
+pub(crate) mod index_map;
 pub mod manifest;
 pub mod move_journal;
 pub mod paperkey;
-- 
2.47.3

[PATCH proxmox-backup v2 07/14] datastore: implement chunk map for collecting chunk usage statistics

[Christian Ebner]

The chunk map uses the previously introduced IndexSet and IndexMap to
keep track of chunk associations to snapshots, their groups and
namespaces during phase 1 of garbage collection and allow for
accounting after determining the raw chunk size for each referenced
chunk during phase 2.

Per entity indexes are defined for additional type checks, the
accumulated hierarchy statistics finally persisted to the datastore.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-datastore/src/chunk_map.rs | 315 +++++++++++++++++++++++++++++++++
 pbs-datastore/src/datastore.rs |  11 +-
 pbs-datastore/src/lib.rs       |   1 +
 3 files changed, 326 insertions(+), 1 deletion(-)
 create mode 100644 pbs-datastore/src/chunk_map.rs

diff --git a/pbs-datastore/src/chunk_map.rs b/pbs-datastore/src/chunk_map.rs
new file mode 100644
index 000000000..adff27628
--- /dev/null
+++ b/pbs-datastore/src/chunk_map.rs
@@ -0,0 +1,315 @@
+use std::collections::HashMap;
+use std::hash::Hash;
+
+use anyhow::{Context, Error};
+
+use pbs_api_types::{
+    BackupDir, BackupGroup, BackupNamespace, StatisticsListItem, StoreUsageStatistics,
+};
+
+use crate::DataStore;
+use crate::index_map::{Entry, IndexMap, IndexSet};
+
+// Limits index to u64::MAX chunks
+#[derive(Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
+struct ChunkIndex(u64);
+
+impl From<ChunkIndex> for usize {
+    fn from(val: ChunkIndex) -> Self {
+        val.0 as usize
+    }
+}
+
+impl From<usize> for ChunkIndex {
+    fn from(id: usize) -> Self {
+        Self(id as u64)
+    }
+}
+
+#[derive(Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
+struct SnapshotIndex(u32);
+
+impl From<SnapshotIndex> for usize {
+    fn from(val: SnapshotIndex) -> Self {
+        val.0 as usize
+    }
+}
+
+impl From<usize> for SnapshotIndex {
+    fn from(id: usize) -> Self {
+        Self(id as u32)
+    }
+}
+
+#[derive(Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
+struct GroupIndex(u32);
+
+impl From<GroupIndex> for usize {
+    fn from(val: GroupIndex) -> Self {
+        val.0 as usize
+    }
+}
+
+impl From<usize> for GroupIndex {
+    fn from(id: usize) -> Self {
+        Self(id as u32)
+    }
+}
+
+#[derive(Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
+struct NamespaceIndex(u32);
+
+impl From<NamespaceIndex> for usize {
+    fn from(val: NamespaceIndex) -> Self {
+        val.0 as usize
+    }
+}
+
+impl From<usize> for NamespaceIndex {
+    fn from(id: usize) -> Self {
+        Self(id as u32)
+    }
+}
+
+#[derive(Eq, Hash, PartialEq)]
+struct BackupTime(i64);
+
+impl From<i64> for BackupTime {
+    fn from(time: i64) -> Self {
+        Self(time)
+    }
+}
+
+struct ChunkAssociation {
+    chunk_idx: ChunkIndex,
+    snapshot_idx: SnapshotIndex,
+    logical_size: u64,
+}
+
+pub struct ChunkMap<'a> {
+    /// Datastore associated with instance
+    datastore: &'a DataStore,
+    /// Compact list of digest and size
+    chunks: IndexMap<[u8; 32], u64, ChunkIndex>,
+    /// Compact list of namespaces
+    namespaces: IndexSet<BackupNamespace, NamespaceIndex>,
+    /// Compact list of groups
+    groups: IndexSet<(NamespaceIndex, BackupGroup), GroupIndex>,
+    /// Set keeping track of snapshots by index and their relation to group and namespace
+    snapshots: IndexSet<(GroupIndex, BackupTime), SnapshotIndex>,
+    /// Compact list keeping track of chunk <-> snapshot relation
+    associations: Vec<ChunkAssociation>,
+}
+
+impl<'a> ChunkMap<'a> {
+    /// Create new mapping instance for given datastore.
+    pub fn with_datastore(datastore: &'a DataStore) -> Self {
+        Self {
+            datastore,
+            chunks: IndexMap::new(),
+            namespaces: IndexSet::new(),
+            groups: IndexSet::new(),
+            snapshots: IndexSet::new(),
+            associations: Vec::new(),
+        }
+    }
+
+    /// Inserts the logical chunk information for an associated digest,
+    /// without accountig for the raw chunk size.
+    pub fn insert(
+        &mut self,
+        digest: &[u8; 32],
+        namespace: &BackupNamespace,
+        snapshot: &BackupDir,
+        logical_size: u64,
+    ) {
+        let chunk_entry = Entry {
+            key: *digest,
+            value: 0,
+        };
+        let chunk_idx = self.chunks.insert(chunk_entry);
+
+        let namespace_idx = self.namespaces.insert(namespace.clone());
+        let group_idx = self.groups.insert((namespace_idx, snapshot.group.clone()));
+        let snapshot_idx = self
+            .snapshots
+            .insert((group_idx, BackupTime::from(snapshot.time)));
+
+        self.associations.push(ChunkAssociation {
+            chunk_idx,
+            snapshot_idx,
+            logical_size,
+        });
+    }
+
+    /// Set the raw chunk size metadata information for an associated digest.
+    pub fn set_raw_chunk_size(&mut self, digest: &[u8; 32], raw_size: u64) {
+        if let Some(chunk_entry) = self.chunks.get_mut(digest) {
+            chunk_entry.value = raw_size;
+        } else {
+            let chunk_entry = Entry {
+                key: *digest,
+                value: raw_size,
+            };
+            let _idx = self.chunks.insert(chunk_entry);
+        }
+    }
+
+    /// Accumulate collected statistics on per-hierarchy level and store them
+    pub fn accumulate_and_persist(mut self) -> Result<(), Error> {
+        let mut datastore_stats = StoreUsageStatistics::default();
+        let mut namespace_stats: HashMap<NamespaceIndex, StoreUsageStatistics> = HashMap::new();
+        let mut group_stats: HashMap<GroupIndex, StoreUsageStatistics> = HashMap::new();
+        let mut snapshot_stats: HashMap<SnapshotIndex, StoreUsageStatistics> = HashMap::new();
+
+        // Buffer to handle individual chunk associations not only to
+        // snapshot index but also to its hierarchy
+        let mut association_buffer: Vec<(NamespaceIndex, GroupIndex, SnapshotIndex, u64)> =
+            Vec::new();
+
+        // Group associations by identical chunks in order to easily distinguish unique,
+        // duplicate and per-snapshot duplicate chunks.
+        self.associations
+            .sort_unstable_by_key(|association| (association.chunk_idx, association.snapshot_idx));
+        for association in self
+            .associations
+            .chunk_by(|a, b| a.chunk_idx == b.chunk_idx)
+        {
+            // All chunks within the same association are identical, can use first index
+            let chunk_idx = association[0].chunk_idx;
+            let raw_size = self
+                .chunks
+                .lookup(chunk_idx)
+                .map(|entry| entry.value)
+                .unwrap_or(0);
+
+            association_buffer.clear();
+            for record in association {
+                let (group_idx, _) = self
+                    .snapshots
+                    .lookup(record.snapshot_idx)
+                    .context("missing snapshot for index")?;
+                let (namespace_idx, _) = self
+                    .groups
+                    .lookup(*group_idx)
+                    .context("missing namespace for index")?;
+                association_buffer.push((
+                    *namespace_idx,
+                    *group_idx,
+                    record.snapshot_idx,
+                    record.logical_size,
+                ));
+            }
+
+            association_buffer.sort_unstable_by_key(
+                |&(namespace_idx, group_idx, snapshot_idx, _)| {
+                    (namespace_idx, group_idx, snapshot_idx)
+                },
+            );
+            let unique = association_buffer.len() == 1;
+            let mut datastore_sum = 0;
+
+            for namespace_associations in association_buffer.chunk_by(|a, b| a.0 == b.0) {
+                let namespace_idx = namespace_associations[0].0;
+                let mut namespace_sum = 0;
+
+                for group_associations in namespace_associations.chunk_by(|a, b| a.1 == b.1) {
+                    let group_idx = group_associations[0].1;
+                    let mut group_sum = 0;
+
+                    for snapshot_associations in group_associations.chunk_by(|a, b| a.2 == b.2) {
+                        let snapshot_idx = snapshot_associations[0].2;
+                        // Logical size must take into account if the same snapshot references the
+                        // same chunk multiple times, raw size is accounted once only.
+                        let snapshot_sum = snapshot_associations
+                            .iter()
+                            .map(|&(_, _, _, logical_size)| logical_size)
+                            .sum();
+                        group_sum += snapshot_sum;
+                        snapshot_stats.entry(snapshot_idx).or_default().add(
+                            raw_size,
+                            snapshot_sum,
+                            unique,
+                        );
+                    }
+
+                    namespace_sum += group_sum;
+                    group_stats
+                        .entry(group_idx)
+                        .or_default()
+                        .add(raw_size, group_sum, unique);
+                }
+
+                datastore_sum += namespace_sum;
+                namespace_stats.entry(namespace_idx).or_default().add(
+                    raw_size,
+                    namespace_sum,
+                    unique,
+                );
+            }
+
+            datastore_stats.add(raw_size, datastore_sum, unique);
+        }
+
+        let mut output = Vec::new();
+        for (snapshot_idx, stats) in snapshot_stats {
+            let (group_idx, snapshot_time) = self
+                .snapshots
+                .lookup(snapshot_idx)
+                .context("missing snapshot for index")?;
+            let (namespace_idx, group) = self
+                .groups
+                .lookup(*group_idx)
+                .context("missing group for index")?;
+            let namespace = self
+                .namespaces
+                .lookup(*namespace_idx)
+                .context("missing namespace for index")?;
+            output.push(StatisticsListItem {
+                ns: Some(namespace.clone()),
+                ty: Some(group.ty),
+                id: Some(group.id.clone()),
+                time: Some(snapshot_time.0),
+                stats,
+            });
+        }
+
+        for (group_idx, stats) in group_stats {
+            let (namespace_idx, group) = self
+                .groups
+                .lookup(group_idx)
+                .context("missing group for index")?;
+            let namespace = self
+                .namespaces
+                .lookup(*namespace_idx)
+                .context("missing namespace for index")?;
+            output.push(StatisticsListItem {
+                ns: Some(namespace.clone()),
+                ty: Some(group.ty),
+                id: Some(group.id.clone()),
+                time: None,
+                stats,
+            });
+        }
+
+        for (namespace_idx, stats) in namespace_stats {
+            let namespace = self
+                .namespaces
+                .lookup(namespace_idx)
+                .context("missing namespace for index")?;
+            output.push(StatisticsListItem {
+                ns: Some(namespace.clone()),
+                ty: None,
+                id: None,
+                time: None,
+                stats,
+            });
+        }
+
+        self.datastore
+            .write_statistics(&output)
+            .context("failed to write statistics")?;
+
+        Ok(())
+    }
+}
diff --git a/pbs-datastore/src/datastore.rs b/pbs-datastore/src/datastore.rs
index d6dcce77f..420221585 100644
--- a/pbs-datastore/src/datastore.rs
+++ b/pbs-datastore/src/datastore.rs
@@ -34,7 +34,7 @@ use pbs_api_types::{
     ArchiveType, Authid, BackupGroupDeleteStats, BackupNamespace, BackupType, ChunkOrder,
     DataStoreConfig, DatastoreBackendConfig, DatastoreBackendType, GarbageCollectionCacheStats,
     GarbageCollectionStatus, MAX_NAMESPACE_DEPTH, MaintenanceMode, MaintenanceType, Operation,
-    S3Statistics, UPID,
+    S3Statistics, StatisticsListItem, UPID,
 };
 use pbs_config::s3::S3_CFG_TYPE_ID;
 use pbs_config::{BackupLockGuard, ConfigVersionCache};
@@ -90,6 +90,8 @@ const S3_DELETE_BATCH_LIMIT: usize = 100;
 const S3_DELETE_DEFER_LIMIT_SECONDS: Duration = Duration::from_secs(60 * 5);
 // upper bound on concurrent snapshot locks during move operations to avoid exhausting FDs
 const MAX_SNAPSHOT_LOCKS: usize = 512;
+// Filename for the datastore statistics
+const DATASTORE_STATISTICS_FILENAME: &str = "statistics.json";
 
 /// Error from a locked per-group operation. Soft errors (e.g. lock conflicts)
 /// are retryable, hard errors are not.
@@ -3489,6 +3491,13 @@ impl DataStore {
 
         result
     }
+
+    pub(crate) fn write_statistics(&self, list: &[StatisticsListItem]) -> Result<(), Error> {
+        let path = self.base_path().join(DATASTORE_STATISTICS_FILENAME);
+        let contents = serde_json::to_vec(list)?;
+        replace_file(&path, &contents, CreateOptions::new(), true)?;
+        Ok(())
+    }
 }
 
 /// Track S3 object keys to be deleted by garbage collection while holding their file lock.
diff --git a/pbs-datastore/src/lib.rs b/pbs-datastore/src/lib.rs
index 4e1222f9d..8b98735d0 100644
--- a/pbs-datastore/src/lib.rs
+++ b/pbs-datastore/src/lib.rs
@@ -182,6 +182,7 @@ pub mod cached_chunk_reader;
 pub mod catalog;
 pub mod checksum_reader;
 pub mod checksum_writer;
+mod chunk_map;
 pub mod chunk_stat;
 pub mod chunk_store;
 pub mod chunker;
-- 
2.47.3

[PATCH proxmox-backup v2 08/14] datastore: cleanup persisted statistics during datastore destruction

[Christian Ebner]

Handle the statistics json file when removing a datastore with its
contents and assure cleanup does not fail if the file is missing.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-datastore/src/datastore.rs | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/pbs-datastore/src/datastore.rs b/pbs-datastore/src/datastore.rs
index 420221585..941e74437 100644
--- a/pbs-datastore/src/datastore.rs
+++ b/pbs-datastore/src/datastore.rs
@@ -3064,6 +3064,12 @@ impl DataStore {
                         ok = false;
                     }
                 }
+                if let Err(err) = std::fs::remove_file(base.join(DATASTORE_STATISTICS_FILENAME)) {
+                    if err.kind() != io::ErrorKind::NotFound {
+                        warn!("failed to remove file '{DATASTORE_STATISTICS_FILENAME}': {err}");
+                        ok = false;
+                    }
+                }
             }
 
             if let (_backend, Some(s3_client)) =
-- 
2.47.3

[PATCH proxmox-backup v2 09/14] fix #5799: GC: track chunk digests and accumulate statistics

[Christian Ebner]

Keep track of all digests referenced by snapshots index files
encountered during phase 1 of garbage collection in the chunk
map for accounting and fill in raw chunk size information
during phase 2.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-datastore/src/chunk_store.rs |  9 ++++++
 pbs-datastore/src/datastore.rs   | 54 ++++++++++++++++++++++++++++++--
 2 files changed, 60 insertions(+), 3 deletions(-)

diff --git a/pbs-datastore/src/chunk_store.rs b/pbs-datastore/src/chunk_store.rs
index ec657092e..a7dea91ee 100644
--- a/pbs-datastore/src/chunk_store.rs
+++ b/pbs-datastore/src/chunk_store.rs
@@ -19,6 +19,7 @@ use proxmox_sys::process_locker::{
 use proxmox_worker_task::WorkerTaskContext;
 
 use crate::backup_info::DATASTORE_LOCKS_DIR;
+use crate::chunk_map::ChunkMap;
 use crate::data_blob::DataChunkBuilder;
 use crate::file_formats::{
     COMPRESSED_BLOB_MAGIC_1_0, ENCRYPTED_BLOB_MAGIC_1_0, UNCOMPRESSED_BLOB_MAGIC_1_0,
@@ -441,6 +442,7 @@ impl ChunkStore {
         status: &mut GarbageCollectionStatus,
         worker: &dyn WorkerTaskContext,
         cache: Option<&LocalDatastoreLruCache>,
+        mut chunk_map: Option<&mut ChunkMap>,
     ) -> Result<(), Error> {
         // unwrap: only `None` in unit tests
         assert!(self.locker.is_some());
@@ -531,6 +533,13 @@ impl ChunkStore {
                         },
                     )?;
                 }
+
+                if chunk_ext == ChunkExt::None {
+                    if let Some(ref mut chunk_map) = chunk_map {
+                        let digest = <[u8; 32]>::from_hex(filename.to_bytes())?;
+                        chunk_map.set_raw_chunk_size(&digest, stat.st_size as u64);
+                    }
+                }
             }
             drop(lock);
         }
diff --git a/pbs-datastore/src/datastore.rs b/pbs-datastore/src/datastore.rs
index 941e74437..f568ea2b3 100644
--- a/pbs-datastore/src/datastore.rs
+++ b/pbs-datastore/src/datastore.rs
@@ -43,6 +43,7 @@ use proxmox_section_config::SectionConfigData;
 use crate::backup_info::{
     BackupDir, BackupGroup, BackupInfo, OLD_LOCKING, PROTECTED_MARKER_FILENAME,
 };
+use crate::chunk_map::ChunkMap;
 use crate::chunk_store::{ChunkStore, is_bad_chunk_suffix};
 use crate::dynamic_index::{DynamicIndexReader, DynamicIndexWriter};
 use crate::fixed_index::{FixedIndexReader, FixedIndexWriter};
@@ -2117,6 +2118,7 @@ impl DataStore {
         index: Box<dyn IndexFile>,
         file_name: &Path, // only used for error reporting
         chunk_lru_cache: &mut Option<LruCache<[u8; 32], ()>>,
+        mut chunk_map_info: Option<ChunkMapInfo>,
         status: &mut GarbageCollectionStatus,
         worker: &dyn WorkerTaskContext,
         s3_client: Option<Arc<S3Client>>,
@@ -2127,7 +2129,13 @@ impl DataStore {
         for pos in 0..index.index_count() {
             worker.check_abort()?;
             worker.fail_on_shutdown()?;
-            let digest = index.index_digest(pos).unwrap();
+            let chunk_info = index.chunk_info(pos).unwrap();
+            let digest = &chunk_info.digest;
+
+            if let Some(map) = chunk_map_info.as_mut() {
+                map.digests
+                    .insert(digest, map.namespace, map.snapshot, chunk_info.size());
+            }
 
             // Avoid multiple expensive atime updates by utimensat
             if let Some(chunk_lru_cache) = chunk_lru_cache {
@@ -2171,12 +2179,13 @@ impl DataStore {
         Ok(())
     }
 
-    fn mark_used_chunks(
+    fn mark_used_chunks<'a>(
         &self,
         status: &mut GarbageCollectionStatus,
         worker: &dyn WorkerTaskContext,
         cache_capacity: usize,
         s3_client: Option<Arc<S3Client>>,
+        mut chunk_map: Option<&mut ChunkMap<'a>>,
     ) -> Result<(), Error> {
         // Iterate twice over the datastore to fetch index files, even if this comes with an
         // additional runtime cost:
@@ -2206,7 +2215,7 @@ impl DataStore {
             .context("creating namespace iterator failed")?
         {
             let namespace = namespace.context("iterating namespaces failed")?;
-            for group in arc_self.iter_backup_groups(namespace)? {
+            for group in arc_self.iter_backup_groups(namespace.clone())? {
                 let group = group.context("iterating backup groups failed")?;
 
                 // Avoid race between listing/marking of snapshots by GC and pruning the last
@@ -2264,10 +2273,21 @@ impl DataStore {
                                 }
                             };
 
+                            let digest_map = if let Some(digests) = chunk_map.as_mut() {
+                                Some(ChunkMapInfo {
+                                    digests,
+                                    namespace: &namespace,
+                                    snapshot: snapshot.backup_dir.dir(),
+                                })
+                            } else {
+                                None
+                            };
+
                             self.index_mark_used_chunks(
                                 index,
                                 &path,
                                 &mut chunk_lru_cache,
+                                digest_map,
                                 status,
                                 worker,
                                 s3_client.as_ref().cloned(),
@@ -2311,6 +2331,7 @@ impl DataStore {
                 index,
                 &path,
                 &mut chunk_lru_cache,
+                None,
                 status,
                 worker,
                 s3_client.as_ref().cloned(),
@@ -2333,6 +2354,7 @@ impl DataStore {
                 index,
                 path,
                 &mut chunk_lru_cache,
+                None,
                 status,
                 worker,
                 s3_client.as_ref().cloned(),
@@ -2461,6 +2483,13 @@ impl DataStore {
             1024 * 1024
         };
 
+        let mut chunk_map = if gc_store_config.extended_usage_statistics {
+            info!("Enabled extended usage statistics gathering.");
+            Some(ChunkMap::with_datastore(self))
+        } else {
+            None
+        };
+
         info!("Start GC phase1 (mark used chunks)");
 
         self.mark_used_chunks(
@@ -2468,6 +2497,7 @@ impl DataStore {
             worker,
             gc_cache_capacity,
             s3_client.as_ref().cloned(),
+            chunk_map.as_mut(),
         )
         .context("marking used chunks failed")?;
 
@@ -2493,6 +2523,10 @@ impl DataStore {
                             None => continue,
                         };
 
+                    if let Some(map) = chunk_map.as_mut() {
+                        map.set_raw_chunk_size(&digest, content.size);
+                    }
+
                     let timeout = std::time::Duration::from_secs(0);
                     let _chunk_guard = match self.inner.chunk_store.lock_chunk(&digest, timeout) {
                         Ok(guard) => guard,
@@ -2589,6 +2623,7 @@ impl DataStore {
                 &mut tmp_gc_status,
                 worker,
                 self.cache(),
+                None,
             )?;
         } else {
             self.inner.chunk_store.sweep_unused_chunks(
@@ -2597,6 +2632,7 @@ impl DataStore {
                 &mut gc_status,
                 worker,
                 None,
+                chunk_map.as_mut(),
             )?;
         }
 
@@ -2610,6 +2646,12 @@ impl DataStore {
                 );
             }
         }
+
+        if let Some(map) = chunk_map.take() {
+            map.accumulate_and_persist()
+                .context("failed to accumulate and persists usage statistics")?;
+        }
+
         info!(
             "Removed garbage: {}",
             HumanByte::from(gc_status.removed_bytes),
@@ -3577,3 +3619,9 @@ impl S3DeleteList {
         Ok(())
     }
 }
+
+struct ChunkMapInfo<'a, 'b> {
+    digests: &'a mut ChunkMap<'b>,
+    namespace: &'a pbs_api_types::BackupNamespace,
+    snapshot: &'a pbs_api_types::BackupDir,
+}
-- 
2.47.3

[PATCH proxmox-backup v2 10/14] api: config: allow modification of extended-usage-statistics flag

[Christian Ebner]

Allows to update or delete the extended-usage-statistics flag to
control whether garbage collection should gather the per-entity
level usage statistics.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 src/api2/config/datastore.rs | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/src/api2/config/datastore.rs b/src/api2/config/datastore.rs
index e7028480c..ab41b3bde 100644
--- a/src/api2/config/datastore.rs
+++ b/src/api2/config/datastore.rs
@@ -440,6 +440,8 @@ pub enum DeletableProperty {
     NotificationThresholds,
     /// Delete the counter reset schedule.
     CounterResetSchedule,
+    /// Delete the extended-usage-statistics property
+    ExtendedUsageStatistics,
 }
 
 #[api(
@@ -545,6 +547,9 @@ pub fn update_datastore(
                 DeletableProperty::CounterResetSchedule => {
                     data.counter_reset_schedule = None;
                 }
+                DeletableProperty::ExtendedUsageStatistics => {
+                    data.extended_usage_statistics = false;
+                }
             }
         }
     }
@@ -646,6 +651,10 @@ pub fn update_datastore(
         data.counter_reset_schedule = update.counter_reset_schedule;
     }
 
+    if let Some(value) = update.extended_usage_statistics {
+        data.extended_usage_statistics = value;
+    }
+
     config.set_data(&name, "datastore", &data)?;
 
     pbs_config::datastore::save_config(&config)?;
-- 
2.47.3

[PATCH proxmox-backup v2 11/14] ui: expose extended usage statistics flag in datastore options

[Christian Ebner]

Exposes the flag to control extended usage statistics gathering
performed during garbage collection to the datastore options.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 www/datastore/OptionView.js | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/www/datastore/OptionView.js b/www/datastore/OptionView.js
index 42a6104dc..54d8ee194 100644
--- a/www/datastore/OptionView.js
+++ b/www/datastore/OptionView.js
@@ -384,5 +384,24 @@ Ext.define('PBS.Datastore.Options', {
                 xtype: 'pbsThresholdResetScheduleEdit',
             },
         },
+        'extended-usage-statistics': {
+            required: true,
+            header: gettext('Extended Usage Statistics'),
+            defaultValue: false,
+            renderer: Proxmox.Utils.format_boolean,
+            editor: {
+                xtype: 'proxmoxWindowEdit',
+                title: gettext('Extended Usage Statistics'),
+                width: 450,
+                items: {
+                    xtype: 'proxmoxcheckbox',
+                    name: 'extended-usage-statistics',
+                    boxLabel: gettext('Gather extended usage statistics during garbage collection'),
+                    defaultValue: false,
+                    deleteDefaultValue: true,
+                    deleteEmpty: true,
+                },
+            },
+        },
     },
 });
-- 
2.47.3

[PATCH proxmox-backup v2 12/14] api: admin: add endpoint to fetch fine-grained datastore usage stats

[Christian Ebner]

Provides the endpoint to read the per-namespace/group/snapshot usage
statistics as persisted during the last garbage collection run.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 pbs-datastore/src/datastore.rs | 13 ++++++++++++-
 src/api2/admin/datastore.rs    | 35 +++++++++++++++++++++++++++++++---
 2 files changed, 44 insertions(+), 4 deletions(-)

diff --git a/pbs-datastore/src/datastore.rs b/pbs-datastore/src/datastore.rs
index f568ea2b3..a35b3721f 100644
--- a/pbs-datastore/src/datastore.rs
+++ b/pbs-datastore/src/datastore.rs
@@ -24,7 +24,7 @@ use proxmox_s3_client::{
 use proxmox_schema::ApiType;
 
 use proxmox_sys::error::SysError;
-use proxmox_sys::fs::{CreateOptions, file_read_optional_string, replace_file};
+use proxmox_sys::fs::{CreateOptions, file_get_contents, file_read_optional_string, replace_file};
 use proxmox_sys::linux::procfs::MountInfo;
 use proxmox_sys::process_locker::{ProcessLockExclusiveGuard, ProcessLockSharedGuard};
 use proxmox_time::{TimeSpan, epoch_i64};
@@ -3546,6 +3546,17 @@ impl DataStore {
         replace_file(&path, &contents, CreateOptions::new(), true)?;
         Ok(())
     }
+
+    pub fn read_statistics(&self) -> Result<Vec<StatisticsListItem>, Error> {
+        let path = self.base_path().join(DATASTORE_STATISTICS_FILENAME);
+        if !path.exists() {
+            // no statistics generated yet
+            return Ok(Vec::new());
+        }
+        let contents = file_get_contents(&path)?;
+        let list = serde_json::from_slice(&contents)?;
+        Ok(list)
+    }
 }
 
 /// Track S3 object keys to be deleted by garbage collection while holding their file lock.
diff --git a/src/api2/admin/datastore.rs b/src/api2/admin/datastore.rs
index 3367fb2c1..b111af5fa 100644
--- a/src/api2/admin/datastore.rs
+++ b/src/api2/admin/datastore.rs
@@ -44,9 +44,10 @@ use pbs_api_types::{
     IGNORE_VERIFIED_BACKUPS_SCHEMA, JobScheduleStatus, KeepOptions, MAX_NAMESPACE_DEPTH,
     MaintenanceMode, MaintenanceType, NS_MAX_DEPTH_SCHEMA, Operation, PRIV_DATASTORE_AUDIT,
     PRIV_DATASTORE_BACKUP, PRIV_DATASTORE_MODIFY, PRIV_DATASTORE_PRUNE, PRIV_DATASTORE_READ,
-    PRIV_DATASTORE_VERIFY, PRIV_SYS_MODIFY, PruneJobOptions, SnapshotListItem, SyncJobConfig, UPID,
-    UPID_SCHEMA, VERIFICATION_OUTDATED_AFTER_SCHEMA, VERIFY_JOB_READ_THREADS_SCHEMA,
-    VERIFY_JOB_VERIFY_THREADS_SCHEMA, print_ns_and_snapshot, print_store_and_ns,
+    PRIV_DATASTORE_VERIFY, PRIV_SYS_MODIFY, PruneJobOptions, SnapshotListItem, StatisticsListItem,
+    SyncJobConfig, UPID, UPID_SCHEMA, VERIFICATION_OUTDATED_AFTER_SCHEMA,
+    VERIFY_JOB_READ_THREADS_SCHEMA, VERIFY_JOB_VERIFY_THREADS_SCHEMA, print_ns_and_snapshot,
+    print_store_and_ns,
 };
 use pbs_client::pxar::{create_tar, create_zip};
 use pbs_config::CachedUserInfo;
@@ -523,6 +524,30 @@ pub async fn list_snapshots(
     .map_err(|err| format_err!("failed to await blocking task: {err}"))?
 }
 
+#[api(
+    input: {
+        properties: {
+            store: { schema: DATASTORE_SCHEMA },
+        },
+    },
+    access: {
+        permission: &Permission::Privilege(&["datastore", "{store}"], PRIV_DATASTORE_AUDIT, false),
+    },
+    returns: pbs_api_types::ADMIN_DATASTORE_LIST_STATISTICS_RETURN_TYPE,
+)]
+/// List backup usage statistics.
+pub fn list_statistics(
+    store: String,
+    _info: &ApiMethod,
+    _rpcenv: &mut dyn RpcEnvironment,
+) -> Result<Vec<StatisticsListItem>, Error> {
+    let datastore = DataStore::lookup_datastore(lookup_with(&store, Operation::Read))?;
+    let stats = datastore
+        .read_statistics()
+        .map_err(|err| format_err!("failed to read statistics: {err}"))?;
+    Ok(stats)
+}
+
 fn get_group_owner(
     store: &str,
     ns: &BackupNamespace,
@@ -2984,6 +3009,10 @@ const DATASTORE_INFO_SUBDIRS: SubdirMap = &[
             .get(&API_METHOD_LIST_GROUPS)
             .delete(&API_METHOD_DELETE_GROUP),
     ),
+    (
+        "list-statistics",
+        &Router::new().get(&API_METHOD_LIST_STATISTICS),
+    ),
     ("mount", &Router::new().post(&API_METHOD_MOUNT)),
     ("move-group", &Router::new().post(&API_METHOD_MOVE_GROUP)),
     (
-- 
2.47.3

[PATCH proxmox-backup v2 13/14] bin: manager: allow listing of extended usage statistics via cli

[Christian Ebner]

Implements the command to expose the statistics provided by the
list-statistics api endpoint via `proxmox-backup-manager datastore
list-statistics` subcommand.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 src/bin/proxmox_backup_manager/datastore.rs | 47 +++++++++++++++++++++
 1 file changed, 47 insertions(+)

diff --git a/src/bin/proxmox_backup_manager/datastore.rs b/src/bin/proxmox_backup_manager/datastore.rs
index 4c1d9daf5..3063c872e 100644
--- a/src/bin/proxmox_backup_manager/datastore.rs
+++ b/src/bin/proxmox_backup_manager/datastore.rs
@@ -347,9 +347,56 @@ async fn s3_refresh(mut param: Value, rpcenv: &mut dyn RpcEnvironment) -> Result
     Ok(())
 }
 
+#[api(
+    input: {
+        properties: {
+            store: {
+                schema: DATASTORE_SCHEMA,
+            },
+            "output-format": {
+                schema: OUTPUT_FORMAT,
+                optional: true,
+            },
+        }
+    }
+)]
+/// List datastore statistics
+fn list_statistics(param: Value, rpcenv: &mut dyn RpcEnvironment) -> Result<Value, Error> {
+    let output_format = get_output_format(&param);
+
+    let info = &api2::admin::datastore::API_METHOD_LIST_STATISTICS;
+    let mut data = match info.handler {
+        ApiHandler::Sync(handler) => (handler)(param, info, rpcenv)?,
+        _ => unreachable!(),
+    };
+
+    let options = default_table_format_options().column_config(vec![
+        ColumnConfig::new("ns").header("Namespace"),
+        ColumnConfig::new("backup-type").header("Type"),
+        ColumnConfig::new("backup-id").header("ID"),
+        ColumnConfig::new("backup-time").header("Time"),
+        ColumnConfig::new("logical-size").header("Logical Size"),
+        ColumnConfig::new("raw-size").header("Raw Size"),
+        ColumnConfig::new("unique-raw-size").header("Unique Raw Size"),
+        ColumnConfig::new("reference-count").header("Reference Count"),
+        ColumnConfig::new("unique-count").header("Unique Count"),
+        ColumnConfig::new("dedup-count").header("Deduplication Count"),
+    ]);
+
+    format_and_print_result_full(&mut data, &info.returns, &output_format, &options);
+
+    Ok(Value::Null)
+}
+
 pub fn datastore_commands() -> CommandLineInterface {
     let cmd_def = CliCommandMap::new()
         .insert("list", CliCommand::new(&API_METHOD_LIST_DATASTORES))
+        .insert(
+            "list-statistics",
+            CliCommand::new(&API_METHOD_LIST_STATISTICS)
+                .arg_param(&["store"])
+                .completion_cb("store", pbs_config::datastore::complete_datastore_name),
+        )
         .insert(
             "mount",
             CliCommand::new(&API_METHOD_MOUNT_DATASTORE)
-- 
2.47.3

[PATCH proxmox-backup v2 14/14] ui: implement statistics tab for datastore panel

[Christian Ebner]

Allows to inspect the statistics for individual items. Contents are
collected and grouped client side to closely resemble the layout of
the items as presented in contents tab.

Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
---
 www/Makefile                |   1 +
 www/datastore/Panel.js      |   8 +
 www/datastore/Statistics.js | 452 ++++++++++++++++++++++++++++++++++++
 3 files changed, 461 insertions(+)
 create mode 100644 www/datastore/Statistics.js

diff --git a/www/Makefile b/www/Makefile
index 568836455..a4a3acb16 100644
--- a/www/Makefile
+++ b/www/Makefile
@@ -123,6 +123,7 @@ JSSRC=							\
 	datastore/Prune.js				\
 	datastore/Content.js				\
 	datastore/OptionView.js				\
+	datastore/Statistics.js				\
 	datastore/Panel.js				\
 	datastore/DataStoreListSummary.js		\
 	datastore/DataStoreList.js			\
diff --git a/www/datastore/Panel.js b/www/datastore/Panel.js
index 68c1c1318..5972e98c7 100644
--- a/www/datastore/Panel.js
+++ b/www/datastore/Panel.js
@@ -99,6 +99,14 @@ Ext.define('PBS.DataStorePanel', {
                 datastore: '{datastore}',
             },
         },
+        {
+            xtype: 'pbsDataStoreStatistics',
+            itemId: 'statistics',
+            iconCls: 'fa fa-bar-chart',
+            cbind: {
+                datastore: '{datastore}',
+            },
+        },
     ],
 
     initComponent: function () {
diff --git a/www/datastore/Statistics.js b/www/datastore/Statistics.js
new file mode 100644
index 000000000..4f5f6a9cd
--- /dev/null
+++ b/www/datastore/Statistics.js
@@ -0,0 +1,452 @@
+Ext.define('pbs-data-store-statistics', {
+    extend: 'Ext.data.Model',
+    fields: [
+        { name: 'ns', type: 'string', allowNull: true },
+        { name: 'backup-type', type: 'string', allowNull: true },
+        { name: 'backup-id', type: 'string', allowNull: true },
+        {
+            name: 'backup-time',
+            type: 'date',
+            dateFormat: 'timestamp',
+        },
+        { name: 'raw-size', type: 'int' },
+        { name: 'logical-size', type: 'int' },
+        { name: 'unique-raw-size', type: 'int' },
+        { name: 'reference-count', type: 'int' },
+        { name: 'unique-count', type: 'int' },
+        { name: 'dedup-count', type: 'int' },
+        {
+            name: 'ty',
+            type: 'string',
+            calculate: function (data) {
+                if (!data.ns) {
+                    return; // unexpected
+                } else if (!data['backup-type'] || !data['backup-id']) {
+                    if (data['backup-time']) {
+                        return; //unexpected
+                    } else {
+                        return 'ns';
+                    }
+                } else if (data['backup-time']) {
+                    return 'dir';
+                } else {
+                    return 'group';
+                }
+            },
+        },
+        {
+            name: 'dedup-factor',
+            type: 'float',
+            calculate: function (data) {
+                if (data['raw-size'] > 0) {
+                    let logical = Ext.Number.parseFloat(data['logical-size']);
+                    let raw = Ext.Number.parseFloat(data['raw-size']);
+                    return logical / raw;
+                } else {
+                    return 1.0;
+                }
+            },
+        },
+    ],
+});
+
+Ext.define('PBS.DataStoreStatistics', {
+    extend: 'Ext.tree.Panel',
+    alias: 'widget.pbsDataStoreStatistics',
+    mixins: ['Proxmox.Mixin.CBind'],
+
+    rootVisible: false,
+
+    title: gettext('Statistics'),
+
+    controller: {
+        xclass: 'Ext.app.ViewController',
+
+        init: function (view) {
+            if (!view.datastore) {
+                throw 'no datastore specified';
+            }
+
+            this.store = Ext.create('Ext.data.Store', {
+                model: 'pbs-data-store-statistics',
+                groupField: 'backup-group',
+            });
+            this.store.on('load', this.onLoad, this);
+
+            view.getStore().setSorters(['sortWeight', 'text', 'backup-time']);
+        },
+
+        control: {
+            '#': {
+                rowdblclick: 'rowDoubleClicked',
+            },
+        },
+
+        rowDoubleClicked: function (table, rec, el, rowId, ev) {
+            if (rec?.data?.ty === 'ns' && !rec.data.root) {
+                this.nsChange(null, rec.data.ns);
+            }
+        },
+
+        nsChange: function (field, value) {
+            let view = this.getView();
+            view.namespace = value;
+            this.reload();
+        },
+
+        reload: function () {
+            let view = this.getView();
+            if (!view.store || !this.store) {
+                console.warn('cannot reload, no store(s)');
+                return;
+            }
+
+            let url = `/api2/json/admin/datastore/${view.datastore}/list-statistics`;
+            this.store.setProxy({
+                type: 'proxmox',
+                timeout: 60 * 1000,
+                url: url,
+            });
+
+            this.store.load();
+        },
+
+        namespacedItems: function(parentNamespace, records) {
+            let ns = parentNamespace;
+            if (!parentNamespace) {
+                ns = "";
+            }
+            let groups = {};
+            let items = [];
+            let pos = ns.length === 0 ? ns.length : ns.length + 1;
+
+            for (const item of records) {
+                let data = item.data;
+                if (!data.ns.startsWith(ns)) {
+                    continue;
+                }
+                let slice = data.ns.substring(pos).split('/');
+                if (slice.length !== 1) {
+                    continue; // namespace level mismatch
+                }
+
+                if (!data['backup-type'] || !data['backup-id']) {
+                    if (!data['backup-time']) {
+                        if (data.ns === ns) {
+                            continue;
+                        }
+                        data.text = slice[0];
+                        data.iconCls = 'fa fa-object-group';
+                        data.expanded = true;
+                        data.expandable = false;
+                        data.sortWeight = 10;
+                        data.leaf = true;
+                        items.push(data);
+                    }
+                    continue;
+                }
+
+                let key = data['backup-type'] + '/' + data['backup-id'];
+
+                if (data['backup-time']) {
+                    data.text = key + '/' + PBS.Utils.render_datetime_utc(data['backup-time']);
+                    data.cls = 'no-leaf-icons';
+                    data.leaf = true;
+                    data.matchesFilter = true;
+                    data.expanded = false;
+                    if (!groups[key]) {
+                        groups[key] = { children: [] };
+                    }
+                    if (!groups[key].children) {
+                        groups[key].children = [];
+                    }
+                    groups[key].children.push(data);
+                } else {
+                    let cls = PBS.Utils.get_type_icon_cls(data['backup-type']);
+                    if (cls === '') {
+                        continue;
+                    }
+
+                    data.text = key;
+                    data.leaf = false;
+                    data.iconCls = 'fa ' + cls;
+                    data.expanded = false;
+                    data.sortWeight = 0;
+
+                    if (!groups[key]) {
+                        groups[key] = data;
+                        groups[key].children = [];
+                    } else {
+                        data.children = groups[key].children;
+                        groups[key] = data;
+                    }
+                }
+            }
+
+            for (const [_name, group] of Object.entries(groups)) {
+                items.push(group);
+            }
+
+            return items;
+        },
+
+        onLoad: async function (store, records, success, operation) {
+            let me = this;
+            let view = this.getView();
+
+            let children = me.namespacedItems(view.namespace, records);
+
+            let isRootNS = !view.namespace || view.namespace === '';
+            let rootText = isRootNS
+                ? gettext('Root Namespace')
+                : Ext.String.format(gettext("Namespace '{0}'"), view.namespace);
+
+            let topNodes = [];
+            if (!isRootNS) {
+                let parentNS = view.namespace.split('/').slice(0, -1).join('/');
+                topNodes.push({
+                    text: `.. (${parentNS === '' ? gettext('Root') : parentNS})`,
+                    iconCls: 'fa fa-level-up',
+                    ty: 'ns',
+                    ns: parentNS,
+                    sortWeight: -10,
+                    leaf: true,
+                });
+            }
+            topNodes.push({
+                text: rootText,
+                iconCls: 'fa fa-' + (isRootNS ? 'database' : 'object-group'),
+                expanded: true,
+                expandable: false,
+                sortWeight: -5,
+                root: true, // fake root
+                isRootNS,
+                ty: 'ns',
+                children: children,
+            });
+
+            view.setRootNode({
+                expanded: true,
+                children: topNodes,
+            });
+
+            if (view.getStore().getFilters().length > 0) {
+                let searchBox = me.lookup('searchbox');
+                let searchvalue = searchBox.getValue();
+                me.search(searchBox, searchvalue);
+            }
+        },
+
+        openNamespace: function (tv, rI, Ci, item, e, rec) {
+            let me = this;
+            if (rec.data.ty === 'ns') {
+                me.nsChange(null, rec.data.ns);
+                return;
+            }
+        },
+
+        filter: function (item, value) {
+            const needle = value.toLowerCase();
+            return item.data.text.toLowerCase().includes(needle);
+        },
+
+        search: function (tf, value) {
+            let me = this;
+            let view = me.getView();
+            let store = view.getStore();
+            if (!value && value !== 0) {
+                store.clearFilter();
+                // only collapse the children below our toplevel namespace "root"
+                store.getRoot().lastChild.collapseChildren(true);
+                // expand just the namespace "root", otherwise the navigation breaks,
+                // as the children are not accessible anymore
+                store.getRoot().lastChild.expand();
+                tf.triggers.clear.setVisible(false);
+                return;
+            }
+            tf.triggers.clear.setVisible(true);
+            if (value.length < 2) {
+                return;
+            }
+            Proxmox.Utils.setErrorMask(view, true);
+            // we do it a little bit later for the error mask to work
+            setTimeout(function () {
+                store.clearFilter();
+                store.getRoot().collapseChildren(true);
+
+                store.beginUpdate();
+                store.getRoot().cascadeBy({
+                    before: function (item) {
+                        if (me.filter(item, value)) {
+                            item.set('matchesFilter', true);
+                            if (item.parentNode && item.parentNode.id !== 'root') {
+                                item.parentNode.childmatches = true;
+                            }
+                            return false;
+                        }
+                        return true;
+                    },
+                    after: function (item) {
+                        if (me.filter(item, value) || item.id === 'root' || item.childmatches) {
+                            item.set('matchesFilter', true);
+                            if (item.parentNode && item.parentNode.id !== 'root') {
+                                item.parentNode.childmatches = true;
+                            }
+                            if (item.childmatches) {
+                                item.expand();
+                            }
+                        } else {
+                            item.set('matchesFilter', false);
+                        }
+                        delete item.childmatches;
+                    },
+                });
+                store.endUpdate();
+
+                store.filter((item) => !!item.get('matchesFilter'));
+                Proxmox.Utils.setErrorMask(view, false);
+            }, 10);
+        },
+    },
+
+    listeners: {
+        activate: function() {
+            this.getController().reload();
+        },
+    },
+
+    columns: [
+        {
+            xtype: 'treecolumn',
+            header: gettext('Backup Group'),
+            dataIndex: 'text',
+            flex: 1,
+        },
+        {
+            header: gettext('Actions'),
+            xtype: 'actioncolumn',
+            dataIndex: 'text',
+            width: 100,
+            items: [
+                {
+                    handler: 'openNamespace',
+                    tooltip: gettext('Browse Namespace'),
+                    getClass: (v, m, { data }) => {
+                        if (data.ty === 'ns' && !data.root) {
+                            return 'fa fa-folder-open-o';
+                        }
+                        return 'pmx-hidden';
+                    },
+                    isActionDisabled: (v, r, c, i, { data }) => {
+                        return data.ty !== 'ns' || data.root;
+                    },
+                },
+            ],
+        },
+        {
+            xtype: 'datecolumn',
+            header: gettext('Backup Time'),
+            dataIndex: 'backup-time',
+            format: 'Y-m-d H:i:s',
+            sortable: true,
+            width: 150,
+        },
+        {
+            header: gettext('Raw Size'),
+            dataIndex: 'raw-size',
+            renderer: (val) => (!val) ? '' : Proxmox.Utils.format_size(val),
+            sortable: true,
+            align: 'right',
+        },
+        {
+            header: gettext('Logical Size'),
+            dataIndex: 'logical-size',
+            renderer: (val) => (!val) ? '' : Proxmox.Utils.format_size(val),
+            sortable: true,
+            align: 'right',
+        },
+        {
+            header: gettext('Unique Raw Size'),
+            dataIndex: 'unique-raw-size',
+            renderer: (val) => (!val) ? '' : Proxmox.Utils.format_size(val),
+            sortable: true,
+            align: 'right',
+        },
+        {
+            xtype: 'numbercolumn',
+            header: gettext('Reference Count'),
+            dataIndex: 'reference-count',
+            format: '0',
+            sortable: true,
+            width: 150,
+            align: 'right',
+        },
+        {
+            xtype: 'numbercolumn',
+            header: gettext('Unique Count'),
+            dataIndex: 'unique-count',
+            format: '0',
+            sortable: true,
+            width: 150,
+            align: 'right',
+        },
+        {
+            xtype: 'numbercolumn',
+            header: gettext('Deduplication Count'),
+            dataIndex: 'dedup-count',
+            format: '0',
+            sortable: true,
+            width: 150,
+            align: 'right',
+        },
+        {
+            xtype: 'numbercolumn',
+            header: gettext('Deduplication Factor'),
+            dataIndex: 'dedup-factor',
+            format: '0.00',
+            sortable: true,
+            width: 150,
+            align: 'right',
+        },
+    ],
+
+    tbar: [
+        {
+            text: gettext('Reload'),
+            iconCls: 'fa fa-refresh',
+            handler: 'reload',
+        },
+        '-',
+        {
+            xtype: 'tbtext',
+            html: gettext('Shown statistics are not live, but generated by last garbage collection'),
+        },
+        '->',
+        {
+            xtype: 'tbtext',
+            html: gettext('Search'),
+        },
+        {
+            xtype: 'textfield',
+            reference: 'searchbox',
+            emptyText: gettext('item name or date'),
+            triggers: {
+                clear: {
+                    cls: 'pmx-clear-trigger',
+                    weight: -1,
+                    hidden: true,
+                    handler: function () {
+                        this.triggers.clear.setVisible(false);
+                        this.setValue('');
+                    },
+                },
+            },
+            listeners: {
+                change: {
+                    fn: 'search',
+                    buffer: 500,
+                },
+            },
+        },
+    ],
+});
-- 
2.47.3