[PATCH proxmox proxmox-backup 0/3] datastore: gc: prefetch chunk metadata before phase 1

[Enrico Plantulli <plantulli@gmail.com>]

Hi,

garbage collection phase 1 resolves each chunk from its digest and calls
utimensat() on it directly, so it never iterates the chunk directories.
On a cold store that means every chunk costs an independent, serialized
metadata read, and those reads are issued in digest order - which is
uncorrelated with the on-disk layout of the inodes by construction,
since the digest picks the directory while the inode number follows
creation order.

How uncorrelated: on datastore A below, the 1059 chunks in a single
.chunks/ subdirectory map to 1059 *distinct* 16 KiB metadnode blocks,
zero shared, with a median gap of 77966 between consecutive object ids.

Most of the numbers below come from two datastores, please keep them
apart:

  Datastore A: 72M chunks, 159 TiB. This is the one that motivates the
    patch: phase 1 has been running at 39.2 chunks/s, which extrapolates
    to more than 21 days for phase 1 alone; full GC cycles on this store
    have taken between 21 and 66 days. No number below is a before/after
    for this patch on A.
  Datastore B: 65536 chunk directories, of which the 32768 sampled below
    hold 5231473 chunks - about half the store. All readdir/lstat
    numbers below are from B.

Measured on ZFS on rotational disks (7x raidz1 of 4 HDDs, ZFS
2.4.3-pve1, PBS 4.2.5, cold cache):

  readdir over those 32768 directories:  270.9 s,  869726 physical reads
  lstat() over the same 5231473 entries:  80.1 s,       0 physical reads

That is 0.166 physical reads per chunk brought in. A pass over all 65536
directories costs about twice the readdir figure; the pass pays an
openat+getdents even for empty directories, so its fixed cost is always
on 65536 directories.

Physical reads are the sum of the completed-read counters in
/proc/diskstats over the 28 pool members, so one 16 KiB logical metadata
read shows up as more than one device read: 869726 physical reads
against 634549 ARC misses, 1.37 per miss. Of those misses 600605 were
prefetch and 33944 demand (94.7% prefetch); the demand figure is within
4% of the 32768 ZAP headers getdents has to read anyway. The readdir
pass was run twice from a cold ARC and the two physical read counts
agreed to within 0.01%. lstat() is used as a stand-in for the read side
of the utimensat() that phase 1 does; it does not perform the atime
write. zfs_readdir() calls dmu_prefetch_dnode() for the entries it
returns, which is where the win comes from - getdents itself needs only
the directory entry, not the inode.

The same effect showed up on a third store: after a readdir-only pass
over 6979381 chunks, an lstat() over all of them cost zero physical
reads.

Patch 1 (proxmox) adds a gc-chunk-metadata-prefetch tuning option.
Patch 2 (proxmox-backup) implements the pass, wires it up and documents
it. Patch 3 (proxmox-backup) adds the GUI field.

Patches 2 and 3 depend on patch 1, so proxmox-backup needs a
pbs-api-types release and a dependency bump before it builds. I did not
touch debian/changelog or Cargo.toml.

Testing status: the series is compile-tested (cargo build, clippy, fmt,
test of the touched crates) against current master of both
repositories, using the pbs-api-types path override already present in
Cargo.toml, and I have since run it end-to-end once on datastore B in
production, with binaries rebuilt from the 4.2.5-1 tag plus this
series: the prefetch walked 10462700 entries in 27m40s (about half of
them already cached from an earlier experiment; a fully cold pass
extrapolates to roughly 55m), phase 1 then completed in 11m59s against
a 2h14m baseline measured on the same store four days earlier - about
13700 chunks/s warm against 440-563 chunks/s cold - and the ZFS
dirty-data throttle never engaged (dmu_tx_dirty_delay stayed at 0).
The full collection, including a phase 2 that swept 9.85M chunks
through the nightly backup window, finished in 6h21m with TASK OK and
removed 436 GiB. I have not tested the S3 code path, and datastore A
has not run with the option yet.

Design notes and open questions, on which I would appreciate guidance:

* The win is conditional on the prefetched metadata surviving in the
  cache until phase 1 consumes it. On ZFS that is roughly 512 bytes of
  dnode per chunk: about 2.5 GiB for the 5.2M chunks sampled from
  datastore B (twice that for the full store) and about 34 GiB for
  datastore A. On a store whose dnodes do not fit in the ARC the pass
  does not pay off. And even where they fit, whether the tail of the
  prefetch survives until a phase 1 that runs for hours reaches it -
  against the index files phase 1 itself reads, the dnodes it dirties
  and concurrent backup traffic - is an open question on a store of A's
  size. If it does not, the better design would be prefetch windows
  interleaved with marking, which this simple one-pass version does not
  attempt. Treat the datastore A figures as motivation, not as a
  measured result of this patch.

* The warm figures bound the read side only. Phase 1 also dirties every
  chunk's dnode through utimensat(), and in digest order two touches
  that share a 16 KiB metadnode block are millions of operations apart,
  so copy-on-write rewrites the block once per touch instead of once
  per block: on datastore A that is ~72M block rewrites, on the order
  of 1 TiB of metadnode churn plus a multiple of that in dirtied
  indirect blocks. This is the same volume phase 1 writes today, only
  compressed into less wall time - a faster phase 1 even coalesces the
  indirect block updates better. But it does cap the marking rate well
  below what the lstat() figure alone would suggest: with the default
  4 GiB zfs_dirty_data_max the ZFS write throttle starts to shape the
  rate in the low thousands of utimensat() per second. So the end
  state I expect on datastore A is phase 1 bound by metadata
  write-back at a few thousand chunks per second - two orders of
  magnitude above the 39.2 chunks/s it does today, but not the tens of
  thousands the warm read numbers alone might suggest. On datastore B
  the end-to-end run stayed below any throttling (~13700 chunks/s with
  dmu_tx_dirty_delay at 0), so the cap was not reached there; for A
  this remains an estimate, not a measurement.

* Opt-in was the conservative choice. Note that tying it to chunk-order
  would not be conservative at all: chunk-order defaults to `inode`, so
  that would effectively enable the pass everywhere. If you want it on
  by default, I would rather make the option default to true than key it
  off chunk-order.

* The pass is not free, but it is also not a whole extra pass: GC phase
  2 already walks the same directories with the same iterator, so the
  prefetch can warm phase 2 as well - though after an hours-long phase 1
  that rewrites the dnodes it touches, how much of that warmth is left
  for phase 2 is equally open.

* The pass is best effort: a failure is logged and ignored, except for
  abort and shutdown requests, which are re-checked in the error path so
  that cancelling the task still stops the collection.

* It reuses get_chunk_store_iterator(), the same iterator phase 2 uses,
  so there is no second implementation of the chunk directory walk. The
  per-entry hex filtering is redundant for this use, but reusing the
  iterator seemed better than duplicating the walk.

* The pass is sequential, one directory at a time, so it keeps the queue
  depth of the pool low - the same limitation that makes phase 1 slow in
  the first place. Parallelising it over ranges of the 65536
  subdirectories would likely help further on wide pools, but it would
  need a second walk implementation instead of reusing
  get_chunk_store_iterator(), so I left it out of this first version.
  Happy to add it if you would take it.

* This is complementary to the LRU cache added in [0] for #5331: that
  commit removes redundant atime updates, this one makes the remaining
  ones cheap. It does not change what phase 1 marks, only what it has to
  wait for.

* A larger version of the same idea would be to have phase 1 itself walk
  in inode order, the way chunk-order=inode already does for verify.
  That is a much more invasive change and I did not attempt it; the
  readdir pass gets most of the benefit for a fraction of the risk.

[0] https://git.proxmox.com/?p=proxmox-backup.git;a=commit;h=03143eee0a59cf319be0052e139f7e20e124d572

Diffstat over the whole series:

proxmox:

 pbs-api-types/src/datastore.rs | 10 ++++++++++
 1 file changed, 10 insertions(+)

proxmox-backup:

 docs/storage.rst                 | 12 ++++++++++++
 pbs-datastore/src/chunk_store.rs | 38 ++++++++++++++++++++++++++++++++++++++
 pbs-datastore/src/datastore.rs   | 23 +++++++++++++++++++++++
 www/Utils.js                     |  6 ++++++
 www/datastore/OptionView.js      | 16 ++++++++++++++++
 5 files changed, 95 insertions(+)

Thanks,
Enrico Plantulli