Re: Btrfs autodefrag wrote 5TB in one day to a 0.5TB SSD without a measurable benefit

[Zygo Blaxell <ce3g8jdj@umail.furryterror.org>]

On Tue, Mar 15, 2022 at 11:20:09PM +0100, Jan Ziak wrote:
> On Tue, Mar 15, 2022 at 10:06 PM Zygo Blaxell
> <ce3g8jdj@umail.furryterror.org> wrote:
> > This is what makes
> > nodatacow and prealloc slow--on every write, they have to check whether
> > the blocks being written are shared or not, and that check is expensive
> > because it's a linear search of every reference for overlapping block
> > ranges, and it can't exit the search early until it has proven there
> > are no shared references.  Contrast with datacow, which allocates a new
> > unshared extent that it knows it can write to, and only has to check
> > overwritten extents when they are completely overwritten (and only has
> > to check for the existence of one reference, not enumerate them all).
> 
> Some questions:
> 
> - Linear nodatacow search: Do you mean that write(fd1, buf1, 4096) to
> a larger nodatacow file is slower compared to write(fd2, buf2, 4096)
> to a smaller nodatacow file?

Size doesn't matter, the number and position of references do.  It's true
that large extents tend to end up with higher average reference counts
than small extents, but that's only spurious correlation--the "large
extent" and "many references" cases are independent.  An 8K nodatacow
extent, where the first 4K block has exactly one reference and the second
4K has 32767 references, requires a 32768 times more CPU work to write
than a 128M extent with a single reference.

In sane cases, there's only one reference to a nodatacow/prealloc extent,
because multiple references will turn off nodatacow and multiple writes
will turn off prealloc, defeating both features.  When there's only one
reference, the linear search for overlapping blocks ends quickly.

In insane cases (after hole punching, snapshots, reflinks, or writes
to prealloc files) there exist multiple references to the extent,
each covering distinct byte ranges of the extent.  The btrfs trees
only index references from leaf metadata pages to the entire extent,
so to calculate the number of times an individual block is referenced,
we have to iterate over every existing reference to see if it happens to
overlap the blocks of interest.  That's O(N) in the number of references
(roughly--e.g. we don't need to examine different snapshots sharing a
metadata page, because every snapshot sharing a metadata page references
the same bytes in the data extent, but I don't know if btrfs implements
that optimization).

We can't simply read the reference count on the extent for various
reasons.  One is that we don't know what the true reference count is
without walking all parent tree nodes toward the root to see if there's
a snapshot.  The extent is referenced by one metadata page, so its
reference count is 1, but the metadata page is shared by multiple tree
roots, so the true reference count is higher.  Another is that a hole
punched into the middle of an extent causes two references from the same
file, where each reference covers a distinct set of blocks.  None of
the individual blocks are shared, but the extent's reference count is 2.

> - Linear nodatacow search: Does the search happen only with uncached
> metadata, or also with metadata cached in RAM?

All metadata is cached in RAM prior to searching.  I think I missed
where you were going with this question.

> - Extent tree v2 + nodatacow: V2 also features the linear search (like
> v1) or has the search been redesigned to be logarithmic?

I haven't seen the implementation, but the design implies a linear
search over the adjacent range of extent physical addresses that is up
to 2 * max_extent_len wide.  It could be made faster with a clever data
structure, which is implied in the project description, but I haven't
seen details.

There are simple ways to make nodatacow fast, but btrfs doesn't implement
them.  e.g. nodatacow could be a subvol property, where reflink and
snapshot is prohibited over the entire subvol when nodatacow is enabled.
That would eliminate the need to ever search extent references on
write--nodatacow writes could safely assume everything in the subvol is
never shared--and it would match the expectations of people who prefer
that nodatacow takes precedence over all incompatible btrfs features.

> -Jan