From: Edward Shishkin <email@example.com>
To: Jamie Lokier <firstname.lastname@example.org>
Cc: Edward Shishkin <email@example.com>,
Mat <firstname.lastname@example.org>, LKML <email@example.com>,
Chris Mason <firstname.lastname@example.org>,
Ric Wheeler <email@example.com>,
Andrew Morton <firstname.lastname@example.org>,
Linus Torvalds <email@example.com>,
The development of BTRFS <firstname.lastname@example.org>
Subject: Re: Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)
Date: Fri, 18 Jun 2010 21:29:40 +0200 [thread overview]
Message-ID: <4C1BC924.email@example.com> (raw)
Jamie Lokier wrote:
> Edward Shishkin wrote:
>> If you decide to base your file system on some algorithms then please
>> use the original ones from proper academic papers. DO NOT modify the
>> algorithms in solitude: this is very fragile thing! All such
>> modifications must be reviewed by specialists in the theory of
>> algorithms. Such review can be done in various scientific magazines of
>> proper level.
>> Personally I don't see any way to improve the situation with Btrfs
>> except full redesigning the last one. If you want to base your file
>> system on the paper of Ohad Rodeh, then please, use *exactly* the
>> Bayer's B-trees that he refers to. That said, make sure that all
>> records you put to the tree has equal length and all non-root nodes of
>> your tree are at least half filled.
> First, thanks Edward for identifying a specific problem with the
> current btrfs implementation.
> I've studied modified B-trees quite a lot and know enough to be sure
> that they are quite robust when you modify them in all sorts of ways.
Which property is robust?
> Moreover, you are incorrect to say there's an intrinsic algorithmic
> problem with variable-length records. It is not true; if Knuth said
> so, Knuth was mistaken.
I didn't say about intrinsic algorithmic problems :)
I just repeat (after Knuth et al) that B-trees with variable-length
have any sane boundary for internal fragmentation. The common idea is
that if we
don't want Btrfs to be in infinite development stage, then we should
*sane* strategy (for example the paper of Ohad Rodeh) and strictly
adhere this in
> This is easily shown by modelling variable-length records (key ->
> string) as a range of fixed length records ([key,index] -> byte) and
> apply the standard B-tree algorithms to that, which guarantees
> algorithm properties such as space utilisation and time; then you can
> substitute a "compressed" representation of contiguous index runs,
> which amounts to nothing more than just storing the strings (split
> where the algorithm says to do so) and endpoint indexes , and because
> this compression does not expand (in any way that matters), classic
> algorithmic properties are still guaranteed.
> Variable-length keys are a different business. Those are trickier,
> but as far as I know, btrfs doesn't use them.
>> As to current Btrfs code: *NOT ACK*!!! I don't think we need such
>> "file systems".
> Btrfs provides many useful features that other filesystems don't. We
> definitely need it, or something like it. You have identified a bug.
> It's not a corruption bug, but it's definitely a bug, and probably
> affects performance as well as space utilisation.
> It is not deep design bug; it is just a result of the packing and
> balancing heuristics.
Frankly, I would like to believe to such end, taking into account amount
contributions to the Btrfs project. At least to make sure I didn't do
> If you are still interested, please apply your knowledge of B-tree
> algorithms to understanding why btrfs fails to balance the tree
> sufficiently well,
Because of top-down balancing. It doesn't like "clever" things like
and "merging". Currently top-down works properly only with stupid classic
> and then propose a fix.
I'll try to help, but I am rather pessimistic here: working out
something, which doesn't like timelines..
> Note that it's not necessarily a problem to have a few nodes with low
> utilisation. Deliberate violation of the classic balancing heuristic
> is often useful for performance.[*]
Ok, let's violate this, but not in the detriment of utilisation:
Internal fragmentation is a horror for file systems, the enemy #1
(which is completely defeated in the last century BTW).
> The problem you've found is only a
> real problem when there are _too many_ nodes with low utilisation.
IMHO this is a problem, as we can not estimate number of such nodes.
Do you have any sane upper boundary for this number? I don't know such one.
Maybe I have missed something?
> [*] For example when filling a tree by inserting contiguously
> ascending keys, the classic "split into two when full" heuristic gives
> the worst possible results (50% lost space), and deliberately
> underfilling the most actively updated nodes, which is not permitted
> at all by the classic algorithm, gives denser packing in the end
> (almost zero lost space).
At the end of what? I hope you don't speak about on-line defragmentation?
Can you point me to the paper (if any)?
> It's also faster. The trick is to make
> sure there's just the right number of underfilled nodes...
> -- Jamie
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to firstname.lastname@example.org
> More majordomo info at http://vger.kernel.org/majordomo-info.html
Edward O. Shishkin
Principal Software Engineer
Red Hat Czech
next prev parent reply other threads:[~2010-06-18 19:29 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-06-03 14:58 Unbound(?) internal fragmentation in Btrfs Edward Shishkin
[not found] ` <AANLkTilKw2onQkdNlZjg7WVnPu2dsNpDSvoxrO_FA2z_@mail.gmail.com>
2010-06-18 8:03 ` Christian Stroetmann
2010-06-18 13:32 ` Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs) Edward Shishkin
2010-06-18 13:45 ` Daniel J Blueman
2010-06-18 16:50 ` Edward Shishkin
2010-06-23 23:40 ` Jamie Lokier
2010-06-24 3:43 ` Daniel Taylor
2010-06-24 4:51 ` Mike Fedyk
2010-06-24 22:06 ` Daniel Taylor
2010-06-25 9:15 ` Btrfs: broken file system design Andi Kleen
2010-06-25 18:58 ` Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs) Ric Wheeler
2010-06-26 5:18 ` Michael Tokarev
2010-06-26 11:55 ` Ric Wheeler
[not found] ` <57784.2001:5c0:82dc::email@example.com>
2010-06-26 13:47 ` Ric Wheeler
2010-06-24 9:50 ` David Woodhouse
2010-06-18 18:15 ` Christian Stroetmann
2010-06-18 13:47 ` Chris Mason
2010-06-18 15:05 ` Edward Shishkin
[not found] ` <4C1B8B4A.firstname.lastname@example.org>
2010-06-18 15:10 ` Chris Mason
2010-06-18 16:22 ` Edward Shishkin
[not found] ` <4C1B9D4F.email@example.com>
2010-06-18 18:10 ` Chris Mason
2010-06-18 15:21 ` Christian Stroetmann
2010-06-18 15:22 ` Chris Mason
2010-06-18 15:56 ` Jamie Lokier
2010-06-18 19:25 ` Christian Stroetmann
2010-06-18 19:29 ` Edward Shishkin [this message]
2010-06-18 19:35 ` Chris Mason
2010-06-18 22:04 ` Balancing leaves when walking from top to down (was Btrfs:...) Edward Shishkin
[not found] ` <4C1BED56.firstname.lastname@example.org>
2010-06-18 22:16 ` Ric Wheeler
2010-06-19 0:03 ` Edward Shishkin
2010-06-21 13:15 ` Chris Mason
[not found] ` <20100621180013.GD17979@think>
2010-06-22 14:12 ` Edward Shishkin
2010-06-22 14:20 ` Chris Mason
2010-06-23 13:46 ` Edward Shishkin
[not found] ` <4C221049.email@example.com>
2010-06-23 23:37 ` Jamie Lokier
2010-06-24 13:06 ` Chris Mason
2010-06-30 20:05 ` Edward Shishkin
[not found] ` <4C2BA381.firstname.lastname@example.org>
2010-06-30 21:12 ` Chris Mason
2010-07-09 4:16 ` Chris Samuel
2010-07-09 20:30 ` Chris Mason
2010-06-23 23:57 ` Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs) Jamie Lokier
You may reply publicly 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:
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).