Re: [pbs-devel] [PATCH v2 proxmox-backup 3/4] garbage collection: allow to keep track of already touched chunks

["Fabian Grünbichler" <f.gruenbichler@proxmox.com>]

On March 10, 2025 12:16 pm, Christian Ebner wrote:
> Implements the `TouchedChunks` struct and methods to keep track of
> already touched chunks during garbage collection phase 1, to avoid
> multiple computational and I/O intensive atime updates via a syscall.
> 
> By inserting a digest, the chunk will be considered as touched and
> can be ignored for subsequent encounters. To limit memory usage, the
> structure allows to reset the chunk status, flagging them as seen
> previous to the reset. A subsequent insert will then flag it as seen
> after the reset. Chunks not seen after a reset, will be cleared from
> the structure by the next reset call, eliminating them from memory.
> 
> This allows to reset the tracking stat after each processes image
> index file, to mimic the incremental backup behaviour of known chunks
> and limit memory footprint.
> 
> Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
> ---
> changes since version 1:
> - no changes
> 
>  pbs-datastore/src/datastore.rs | 29 +++++++++++++++++++++++++++++
>  1 file changed, 29 insertions(+)
> 
> diff --git a/pbs-datastore/src/datastore.rs b/pbs-datastore/src/datastore.rs
> index 72bc9f77f..fdbb33a98 100644
> --- a/pbs-datastore/src/datastore.rs
> +++ b/pbs-datastore/src/datastore.rs
> @@ -1585,3 +1585,32 @@ impl DataStore {
>          Ok(())
>      }
>  }
> +
> +struct TouchedChunks {
> +    list: HashMap<[u8; 32], bool>,
> +}
> +
> +impl TouchedChunks {
> +    fn new() -> Self {
> +        Self {
> +            list: HashMap::new(),
> +        }
> +    }
> +
> +    // Clear untouched chunks and reset the touched marker for others.
> +    fn reset(&mut self) {
> +        let mut new_list = HashMap::new();
> +        for (digest, touched) in self.list.drain() {
> +            if touched {
> +                new_list.insert(digest, false);
> +            }
> +        }
> +        self.list = new_list;

this could avoid the memory allocation (and for bigger
indices/snapshots, probably multiple reallocations via the inserts) by
switching to `retain` (which gets a `&mut V` and can thus flip the value
of touched while filtering in a single pass).

despite the performance warning about it visiting empty buckets as well,
this seems to be (slightly) faster for my test datastore (would be
interesting if your test cases agree?) when benchmarking with a warmed
up cache.

I used the following on-top of your series (the shrink_to is to reduce
memory usage in case of outliers after they've been processed):

```
diff --git a/pbs-datastore/src/datastore.rs b/pbs-datastore/src/datastore.rs
index a80343d9b..d3c3f831f 100644
--- a/pbs-datastore/src/datastore.rs
+++ b/pbs-datastore/src/datastore.rs
@@ -1650,13 +1650,12 @@ impl TouchedChunks {
 
     // Clear untouched chunks and reset the touched marker for others.
     fn reset(&mut self) {
-        let mut new_list = HashMap::new();
-        for (digest, touched) in self.list.drain() {
-            if touched {
-                new_list.insert(digest, false);
-            }
-        }
-        self.list = new_list;
+        self.list.retain(|_digest, touched| {
+            *touched = !*touched;
+            !*touched
+        });
+        let max_capacity = self.list.len().saturating_add(self.list.len() / 3);
+        self.list.shrink_to(max_capacity);
     }
 
     // Insert the digest in the list of touched chunks.
```

if the above is slower for your test inputs, then at least initializing
the second HashMap with some initial capacity (the len of the previous
list?) is probably sensible..

alternatively, we could also explore (maybe as a follow-up to
immediately realize the performance gains we already know we get from
the current aproach?) some sort of LRU-based approach?

that might give us the option of:
- dropping the reset call/fn while still having bounded (even
  configurable?) memory overhead
- extend skipping touches across a broader range of snapshots/indices
  for additional performance gains (if the capacity is high enough)

> +    }
> +
> +    // Insert the digest in the list of touched chunks.
> +    // Returns true if the chunk was already present, false otherwise.
> +    fn insert(&mut self, digest: [u8; 32]) -> bool {
> +        self.list.insert(digest, true).is_some()
> +    }
> +}
> -- 
> 2.39.5
> 
> 
> 
> _______________________________________________
> pbs-devel mailing list
> pbs-devel@lists.proxmox.com
> https://lists.proxmox.com/cgi-bin/mailman/listinfo/pbs-devel
> 
> 
> 


_______________________________________________
pbs-devel mailing list
pbs-devel@lists.proxmox.com
https://lists.proxmox.com/cgi-bin/mailman/listinfo/pbs-devel