Linux-BTRFS Archive on lore.kernel.org
 help / color / Atom feed
From: Zygo Blaxell <ce3g8jdj@umail.furryterror.org>
To: Chris Murphy <lists@colorremedies.com>
Cc: "Austin S. Hemmelgarn" <ahferroin7@gmail.com>,
	General Zed <general-zed@zedlx.com>,
	Btrfs BTRFS <linux-btrfs@vger.kernel.org>
Subject: Re: Feature requests: online backup - defrag - change RAID level
Date: Sat, 14 Sep 2019 19:39:12 -0400
Message-ID: <20190914233912.GA24379@hungrycats.org> (raw)
In-Reply-To: <CAJCQCtQ9729my4i2hdqwyTD-PVhsQk8cRaTg9vbDT4Yn2s7SAA@mail.gmail.com>

On Sat, Sep 14, 2019 at 12:29:09PM -0600, Chris Murphy wrote:
> On Fri, Sep 13, 2019 at 5:04 AM Austin S. Hemmelgarn
> <ahferroin7@gmail.com> wrote:
> >
> > Do you have a source for this claim of a 128MB max extent size?  Because
> > everything I've seen indicates the max extent size is a full data chunk
> > (so 1GB for the common case, potentially up to about 5GB for really big
> > filesystems)
> 
> Yeah a block group can be a kind of "super extent". I think the
> EXTENT_DATA maxes out at 128M but they are often contiguous, for
> example
> 
>     item 308 key (5741459 EXTENT_DATA 0) itemoff 39032 itemsize 53
>         generation 241638 type 1 (regular)
>         extent data disk byte 193851400192 nr 134217728
>         extent data offset 0 nr 134217728 ram 134217728
>         extent compression 0 (none)
>     item 309 key (5741459 EXTENT_DATA 134217728) itemoff 38979 itemsize 53
>         generation 241638 type 1 (regular)
>         extent data disk byte 193985617920 nr 134217728
>         extent data offset 0 nr 134217728 ram 134217728
>         extent compression 0 (none)
>     item 310 key (5741459 EXTENT_DATA 268435456) itemoff 38926 itemsize 53
>         generation 241638 type 1 (regular)
>         extent data disk byte 194119835648 nr 134217728
>         extent data offset 0 nr 134217728 ram 134217728
>         extent compression 0 (none)
> 
> Where FIEMAP has a different view (via filefrag -v)
> 
>  ext:     logical_offset:        physical_offset: length:   expected: flags:
>    0:        0..  131071:   47327002..  47458073: 131072:
>    1:   131072..  294911:   47518701..  47682540: 163840:   47458074:
>    2:   294912..  360447:   50279681..  50345216:  65536:   47682541:
>    3:   360448..  499871:   50377984..  50517407: 139424:   50345217: last,eof
> Fedora-Workstation-Live-x86_64-31_Beta-1.1.iso: 4 extents found
> 
> Those extents are all bigger than 128M. But they're each made up of
> contiguous EXTENT_DATA items.
> 
> Also, the EXTENT_DATA size goes to a 128K max for any compressed
> files, so you get an explosive number of EXTENT_DATA items on
> compressed file systems, and thus metadata to rewrite.

The compressed extents tend to be physically contiguous as well, so
quantitatively they aren't much of a problem.  There's more space used in
metadata, but that is compensated by less space in data.  In the subvol
trees, logically contiguous extents are always logically contiguous by
key order, so they are packed densely in subvol metadata pages.

In extent, csum, and free space trees, when there is physical
contiguity--or just proximity--the extent's items are packed into the
same metadata pages, keeping their costs down.  That's true of all
small extents, not just compressed ones.  Note that contiguity isn't
necessary for metadata space efficiency--the extents just have to be
close together, they don't need to be seamless, or in order (at least
not for this reason).

Writes that are separated in _time_ are a different problem, and
potentially much worse than the compression case.  If you have a file that
consists of lots of extents that were written with significant allocations
to other files between them, that file becomes a metadata monster that
can create massive commit latencies when it is deleted or modified.
If you unpack tarballs or build sources or rsync backup trees or really
any two or more writing tasks at the same time on a big btrfs filesystem,
you can run into cases where the metadata:data ratio goes above 1.0 during
updates _and_ the metadata is randomly distributed physically.  Commits
after a big delete run for hours.

> I wonder if instead of a rewrite of defragmenting, if there could be
> improvements to the allocator to write bigger extents. I guess the
> problem really comes from file appends? Smarter often means slower but
> perhaps it could be a variation on autodefrag?

Physically dispersed files can be fixed by defrag, but directory trees
are a little different.  The current defrag doesn't look at the physical
distances between files, only the extents within a single file, so it
doesn't help when you have a big fragmented directory tree of many small
not-fragmented files.  IOW defrag helps with 'rm -f' performance but not
'rm -rf' performance.

Other filesystems have allocator heuristics that reserve space near
growing files, or try to pre-divide the free space to spread out
files belonging to different directories or created by two processes.
This is an attempt to fix the problem before it occurs, and sometimes
it works; however, the heuristics have to match the reality or it just
makes things worse, and extra complexity breeds bugs, e.g. the fix
recently for a bug which tried to give every thread its own block group
for allocation--i.e. 20 threads writing 4K each could ENOSPC if there
was less than 20GB of unallocated space.

I think the best approach may be to attack the problem quantitatively
with an autodefrag agent:  keep the write path fast and simple, but
detect areas where problems are occurring--i.e. where the ratio of extent
metadata locality to physical locality is low--and clean them up with
some minimal data relocation.  Note that's somewhat different from what
the current kernel autodefrag does.

In absolute terms autodefrag is worse--ideally we'd just put the data
in the right place from the start, not write it in the wrong place
then spend more iops fixing it later--but not all iops have equal cost.
In some cases there is an opportunity to trade cheap iops at one time
for expensive iops at a different time, and a userspace agent can invest
more time, memory, and code complexity on that trade than the kernel.

Some back-of-the-envelope math says we don't need to do very much
post-processing work to deal with the very worst cases:  keep extent
sizes over a few hundred KB, and keep small files not more than about
5-10 metadata items away from their logical neighbors, and we avoid the
worst-case 12.0 metadata-to-data ratios during updates.  Compared to
those, other inefficiencies are trivial.

> 
> -- 
> Chris Murphy
> 

  reply index

Thread overview: 111+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-09-09  2:55 zedlryqc
2019-09-09  3:51 ` Qu Wenruo
2019-09-09 11:25   ` zedlryqc
2019-09-09 12:18     ` Qu Wenruo
2019-09-09 12:28       ` Qu Wenruo
2019-09-09 17:11         ` webmaster
2019-09-10 17:39           ` Andrei Borzenkov
2019-09-10 22:41             ` webmaster
2019-09-09 15:29       ` Graham Cobb
2019-09-09 17:24         ` Remi Gauvin
2019-09-09 19:26         ` webmaster
2019-09-10 19:22           ` Austin S. Hemmelgarn
2019-09-10 23:32             ` webmaster
2019-09-11 12:02               ` Austin S. Hemmelgarn
2019-09-11 16:26                 ` Zygo Blaxell
2019-09-11 17:20                 ` webmaster
2019-09-11 18:19                   ` Austin S. Hemmelgarn
2019-09-11 20:01                     ` webmaster
2019-09-11 21:42                       ` Zygo Blaxell
2019-09-13  1:33                         ` General Zed
2019-09-11 21:37                     ` webmaster
2019-09-12 11:31                       ` Austin S. Hemmelgarn
2019-09-12 19:18                         ` webmaster
2019-09-12 19:44                           ` Chris Murphy
2019-09-12 21:34                             ` General Zed
2019-09-12 22:28                               ` Chris Murphy
2019-09-12 22:57                                 ` General Zed
2019-09-12 23:54                                   ` Zygo Blaxell
2019-09-13  0:26                                     ` General Zed
2019-09-13  3:12                                       ` Zygo Blaxell
2019-09-13  5:05                                         ` General Zed
2019-09-14  0:56                                           ` Zygo Blaxell
2019-09-14  1:50                                             ` General Zed
2019-09-14  4:42                                               ` Zygo Blaxell
2019-09-14  4:53                                                 ` Zygo Blaxell
2019-09-15 17:54                                                 ` General Zed
2019-09-16 22:51                                                   ` Zygo Blaxell
2019-09-17  1:03                                                     ` General Zed
2019-09-17  1:34                                                       ` General Zed
2019-09-17  1:44                                                       ` Chris Murphy
2019-09-17  4:55                                                         ` Zygo Blaxell
2019-09-17  4:19                                                       ` Zygo Blaxell
2019-09-17  3:10                                                     ` General Zed
2019-09-17  4:05                                                       ` General Zed
2019-09-14  1:56                                             ` General Zed
2019-09-13  5:22                                         ` General Zed
2019-09-13  6:16                                         ` General Zed
2019-09-13  6:58                                         ` General Zed
2019-09-13  9:25                                           ` General Zed
2019-09-13 17:02                                             ` General Zed
2019-09-14  0:59                                             ` Zygo Blaxell
2019-09-14  1:28                                               ` General Zed
2019-09-14  4:28                                                 ` Zygo Blaxell
2019-09-15 18:05                                                   ` General Zed
2019-09-16 23:05                                                     ` Zygo Blaxell
2019-09-13  7:51                                         ` General Zed
2019-09-13 11:04                                     ` Austin S. Hemmelgarn
2019-09-13 20:43                                       ` Zygo Blaxell
2019-09-14  0:20                                         ` General Zed
2019-09-14 18:29                                       ` Chris Murphy
2019-09-14 23:39                                         ` Zygo Blaxell [this message]
2019-09-13 11:09                                   ` Austin S. Hemmelgarn
2019-09-13 17:20                                     ` General Zed
2019-09-13 18:20                                       ` General Zed
2019-09-12 19:54                           ` Austin S. Hemmelgarn
2019-09-12 22:21                             ` General Zed
2019-09-13 11:53                               ` Austin S. Hemmelgarn
2019-09-13 16:54                                 ` General Zed
2019-09-13 18:29                                   ` Austin S. Hemmelgarn
2019-09-13 19:40                                     ` General Zed
2019-09-14 15:10                                       ` Jukka Larja
2019-09-12 22:47                             ` General Zed
2019-09-11 21:37                   ` Zygo Blaxell
2019-09-11 23:21                     ` webmaster
2019-09-12  0:10                       ` Remi Gauvin
2019-09-12  3:05                         ` webmaster
2019-09-12  3:30                           ` Remi Gauvin
2019-09-12  3:33                             ` Remi Gauvin
2019-09-12  5:19                       ` Zygo Blaxell
2019-09-12 21:23                         ` General Zed
2019-09-14  4:12                           ` Zygo Blaxell
2019-09-16 11:42                             ` General Zed
2019-09-17  0:49                               ` Zygo Blaxell
2019-09-17  2:30                                 ` General Zed
2019-09-17  5:30                                   ` Zygo Blaxell
2019-09-17 10:07                                     ` General Zed
2019-09-17 23:40                                       ` Zygo Blaxell
2019-09-18  4:37                                         ` General Zed
2019-09-18 18:00                                           ` Zygo Blaxell
2019-09-10 23:58             ` webmaster
2019-09-09 23:24         ` Qu Wenruo
2019-09-09 23:25         ` webmaster
2019-09-09 16:38       ` webmaster
2019-09-09 23:44         ` Qu Wenruo
2019-09-10  0:00           ` Chris Murphy
2019-09-10  0:51             ` Qu Wenruo
2019-09-10  0:06           ` webmaster
2019-09-10  0:48             ` Qu Wenruo
2019-09-10  1:24               ` webmaster
2019-09-10  1:48                 ` Qu Wenruo
2019-09-10  3:32                   ` webmaster
2019-09-10 14:14                     ` Nikolay Borisov
2019-09-10 22:35                       ` webmaster
2019-09-11  6:40                         ` Nikolay Borisov
2019-09-10 22:48                     ` webmaster
2019-09-10 23:14                   ` webmaster
2019-09-11  0:26               ` webmaster
2019-09-11  0:36                 ` webmaster
2019-09-11  1:00                 ` webmaster
2019-09-10 11:12     ` Austin S. Hemmelgarn
2019-09-09  3:12 webmaster

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190914233912.GA24379@hungrycats.org \
    --to=ce3g8jdj@umail.furryterror.org \
    --cc=ahferroin7@gmail.com \
    --cc=general-zed@zedlx.com \
    --cc=linux-btrfs@vger.kernel.org \
    --cc=lists@colorremedies.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-BTRFS Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-btrfs/0 linux-btrfs/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-btrfs linux-btrfs/ https://lore.kernel.org/linux-btrfs \
		linux-btrfs@vger.kernel.org linux-btrfs@archiver.kernel.org
	public-inbox-index linux-btrfs

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-btrfs


AGPL code for this site: git clone https://public-inbox.org/ public-inbox