Re: [pbs-devel] [PATCH v3 proxmox-backup 43/58] client: pxar: implement store to insert chunks on caching

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

Quoting Christian Ebner (2024-03-28 13:36:52)
> In preparation for the look-ahead caching used to temprarily store
> entries before encoding them in the pxar archive, being able to
> decide wether to re-use or re-encode regular file entries.
> 
> Allows to insert and store reused chunks in the archiver,
> deduplicating chunks upon insert when possible.
> 
> Signed-off-by: Christian Ebner <c.ebner@proxmox.com>
> ---
> changes since version 2:
> - Strongly adapted and refactored: keep track also of paddings
>   introduced by reusing the chunks, making a suggestion whether to
>   re-use, re-encode or check next entry based on threshold
> - completely removed code which allowed to calculate offsets based on
>   chunks found in the middle, they must either be a continuation of the
>   end or be added after, otherwise offsets are not monotonically
>   increasing, which is required for sequential restore
> 
>  pbs-client/src/pxar/create.rs | 126 +++++++++++++++++++++++++++++++++-
>  1 file changed, 125 insertions(+), 1 deletion(-)
> 
> diff --git a/pbs-client/src/pxar/create.rs b/pbs-client/src/pxar/create.rs
> index 335e3556f..95a91a59b 100644
> --- a/pbs-client/src/pxar/create.rs
> +++ b/pbs-client/src/pxar/create.rs
> @@ -20,7 +20,7 @@ use pathpatterns::{MatchEntry, MatchFlag, MatchList, MatchType, PatternFlag};
>  use pbs_datastore::index::IndexFile;
>  use proxmox_sys::error::SysError;
>  use pxar::accessor::aio::Accessor;
> -use pxar::encoder::{LinkOffset, SeqWrite};
> +use pxar::encoder::{LinkOffset, PayloadOffset, SeqWrite};
>  use pxar::Metadata;
>  
>  use proxmox_io::vec;
> @@ -36,6 +36,128 @@ use crate::pxar::metadata::errno_is_unsupported;
>  use crate::pxar::tools::assert_single_path_component;
>  use crate::pxar::Flags;
>  
> +const CHUNK_PADDING_THRESHOLD: f64 = 0.1;
> +
> +#[derive(Default)]
> +struct ReusedChunks {
> +    start_boundary: PayloadOffset,
> +    total: PayloadOffset,
> +    padding: u64,
> +    chunks: Vec<(u64, ReusableDynamicEntry)>,
> +    must_flush_first: bool,
> +    suggestion: Suggested,
> +}
> +
> +#[derive(Copy, Clone, Default)]
> +enum Suggested {
> +    #[default]
> +    CheckNext,
> +    Reuse,
> +    Reencode,
> +}

this is a bit of a misnomer - it's not a suggestion, it's what is going to
happen ;) maybe `action` or even `result` or something similar might be a
better fit? or something going into the direction of "decision"?

> +
> +impl ReusedChunks {
> +    fn new() -> Self {
> +        Self::default()
> +    }

this is not needed, can just use default()

> +
> +    fn start_boundary(&self) -> PayloadOffset {
> +        self.start_boundary
> +    }

is this needed? access is only local anyway, and we don't have a similar helper
for self.chunks ;)

> +
> +    fn is_empty(&self) -> bool {
> +        self.chunks.is_empty()
> +    }
> +
> +    fn suggested(&self) -> Suggested {
> +        self.suggestion

same question here..

> +    }
> +
> +    fn insert(
> +        &mut self,
> +        indices: Vec<ReusableDynamicEntry>,
> +        boundary: PayloadOffset,
> +        start_padding: u64,
> +        end_padding: u64,
> +    ) -> PayloadOffset {

another fn that definitely would benefit from some comments describing the
thought processes behind the logic :)

> +        if self.is_empty() {
> +            self.start_boundary = boundary;
> +        }

okay, so this is actually just set

> +
> +        if let Some(offset) = self.last_digest_matched(&indices) {
> +            if let Some((padding, last)) = self.chunks.last_mut() {

we already know a last chunk must exist (else last_digest_matched wouldn't have
returned). that means last_digest_matched could just return the last chunk?

> +                // Existing chunk, update padding based on pre-existing one
> +                // Start padding is expected to be larger than previous padding

should we validate this expectation? or is it already validated somewhere else?
and also, isn't start_padding by definition always smaller than last.size()?

> +                *padding += start_padding - last.size();
> +                self.padding += start_padding - last.size();

(see below) here we correct the per-chunk padding, but only for a partial chunk that is continued..

if I understand this part correctly, here we basically want to adapt from a
potential end_padding of the last chunk, if it was:

A|A|A|P|P|P|P

and we now have

P|P|P|P|P|B|B

we want to end up with just 2 'P's in the middle? isn't start_padding - size
the count of the payload? so what we actually want is

*padding -= (last.size() - start_padding)

? IMHO that makes the intention much more readable, especially if you factor out

let payload_size = last.size() - start_padding;
*padding -= payload_size;
self.padding -= payload_size;

if we want to be extra careful, we could even add the three checks/assertions here:
- start_padding must be smaller than the chunk size
- both chunk and total padding must be bigger than the payload size

> +            }
> +
> +            for chunk in indices.into_iter().skip(1) {
> +                self.total = self.total.add(chunk.size());
> +                self.chunks.push((0, chunk));

here we push the second and later chunks with 0 padding

> +            }
> +
> +            if let Some((padding, _last)) = self.chunks.last_mut() {
> +                *padding += end_padding;
> +                self.padding += end_padding;

and here we account for the end_padding of the last chunk, which might actually
be the same as the first chunk, but that works out..

> +            }
> +
> +            let padding_ratio = self.padding as f64 / self.total.raw() as f64;
> +            if self.chunks.len() > 1 && padding_ratio < CHUNK_PADDING_THRESHOLD {
> +                self.suggestion = Suggested::Reuse;
> +            }

see below

> +
> +            self.start_boundary.add(offset + start_padding)
> +        } else {
> +            let offset = self.total.raw();
> +
> +            if let Some(first) = indices.first() {
> +                self.total = self.total.add(first.size());
> +                self.chunks.push((start_padding, first.clone()));
> +                // New chunk, all start padding counts
> +                self.padding += start_padding;
> +            }
> +
> +            for chunk in indices.into_iter().skip(1) {
> +                self.total = self.total.add(chunk.size());
> +                self.chunks.push((chunk.size(), chunk));

so here we count the full chunk size as padding (for the per-chunk stats), but
don't count it for the total padding? I think this should be 0 just like above?

this and the handling of the first chunk could actually be combined:

for (idx, chunk) in indices.into_iter().enumerate() {
	self.total = self.total.add(chunk.size());
	let chunk_padding = if idx == 0 { self.padding += start_padding; start_padding } else { 0 };
	self.chunks.push((chunk_padding, chunk));
}

or we could make start_padding mut, and do

self.padding += start_padding;
for chunk in indices.into_iter() {
	self.total = self.total.add(chunk.size());
	self.chunks.push((start_padding, chunk));
	start_padding = 0; // only first chunk counts
}

> +            }
> +
> +            if let Some((padding, _last)) = self.chunks.last_mut() {
> +                *padding += end_padding;
> +                self.padding += end_padding;
> +            }
> +
> +            if self.chunks.len() > 2 {

so if we insert more than two chunks without a continuation, all of them are
accounted for as full of padding but they are still re-used if start and end
padding are below the threshold ;)

> +                let padding_ratio = self.padding as f64 / self.total.raw() as f64;
> +                if padding_ratio < CHUNK_PADDING_THRESHOLD {
> +                    self.suggestion = Suggested::Reuse;
> +                } else {
> +                    self.suggestion = Suggested::Reencode;
> +                }

we could just return the suggestion instead of storing it - it's only ever needed right after `insert` anyway?

this calculation above seems to not handle some corner cases though.

 if I have the following sequence

|P|A|A|A|A|A|B|P|P|P|P|P|
|    C1     |    C2     |

where P represent padding parts, A and B are file contents of two files, and C1
and C2 are two chunks. let's say both A and B are re-usable files. first A is
resolved via the index and inserted, but since it's the first chunk, there is
no "suggestion" yet (CheckNext). now B is resolved and inserted - it doesn't
continue a partial previous chunk, so we take the else branch. but now the
(total) padding ratio is skewed because of B, even though A on its own would
have been perfectly fine to be re-used.. (let's say we then insert another
chunk different to C1 and C2, depending on the exact ratios that one might lead
to the whole sequence being re-used or not, even though C2 should not be
re-used, C1 should, and the hypothetical C3 might or might not!)

basically, as soon as we have a break in the chunk sequence (file A followed by
file B, with no chunk overlap) we can treat each part on its own?

> +            }
> +
> +            self.start_boundary.add(offset + start_padding)
> +        }
> +    }
> +
> +    fn last_digest_matched(&self, indices: &[ReusableDynamicEntry]) -> Option<u64> {
> +        let digest = if let Some(first) = indices.first() {
> +            first.digest()
> +        } else {
> +            return None;
> +        };
> +
> +        if let Some(last) = self.chunks.last() {
> +            if last.1.digest() == digest {
> +                return Some(self.total.raw() - last.1.size());
> +            }
> +        }
> +
> +        None
> +    }
> +}
> +
>  /// Pxar options for creating a pxar archive/stream
>  #[derive(Default, Clone)]
>  pub struct PxarCreateOptions {
> @@ -147,6 +269,7 @@ struct Archiver {
>      hardlinks: HashMap<HardLinkInfo, (PathBuf, LinkOffset)>,
>      file_copy_buffer: Vec<u8>,
>      skip_e2big_xattr: bool,
> +    reused_chunks: ReusedChunks,
>      forced_boundaries: Option<Arc<Mutex<VecDeque<InjectChunks>>>>,
>  }
>  
> @@ -239,6 +362,7 @@ where
>          hardlinks: HashMap::new(),
>          file_copy_buffer: vec::undefined(4 * 1024 * 1024),
>          skip_e2big_xattr: options.skip_e2big_xattr,
> +        reused_chunks: ReusedChunks::new(),
>          forced_boundaries,
>      };
>  
> -- 
> 2.39.2
> 
> 
> 
> _______________________________________________
> pbs-devel mailing list
> pbs-devel@lists.proxmox.com
> https://lists.proxmox.com/cgi-bin/mailman/listinfo/pbs-devel
> 
>