LWN: Comments on "Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs) "

Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)

Blaisorblade — Wed, 10 Nov 2010 07:48:22 +0000

A trivial insertion sort also takes linear time (and performs no permutation) on already-sorted data; moreover, . Donald Knuth already pointed out how bad bubble sort is, and other researchers recommended that bubble sort should not even be taught. See:
http://en.wikipedia.org/wiki/Bubble_sort#In_practice

Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)

Wol — Thu, 01 Jul 2010 14:24:18 +0000

"In computer science I recall sort algorithms that are almost always fast, but in the worse cases horribly slow."

Or are usually slow but can be incredibly fast :-) Hence the need to know your data!

The sort you are thinking of is the quick sort - under most circumstances it's the fastest.

The one I'm thinking of is the bubble sort :-) The watermark-optimised version, run over a already-sorted input set, is provably the fastest sort possible! And this is also the quick-sort worst case!

I'm a regular user of the bubble sort and variants, but oftentimes I know my datasets are approximately sorted before I start.

Cheers,
Wol

Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)

cwillu — Mon, 28 Jun 2010 06:09:30 +0000

Honestly, I'm suspicious that Edward is just trolling. The actual test points he's brought up have been addressed, and are unrelated to the major claims he's making with regards to the actual design. Requests for clarification on those claims have yet to be answered beyond simple restatements of the claims.

Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)

vonbrand — Thu, 24 Jun 2010 21:02:45 +0000

I understand the above numbers aren't some "worst case behaviour", but (simple but near real-life) test cases.

Btrfs: broken file system design (was Unbound(?) internal fragmentation in Btrfs)

NRArnot — Thu, 24 Jun 2010 12:21:56 +0000

In computer science I recall sort algorithms that are almost always fast, but in the worse cases horribly slow. One is recommended to randomise the sequence of one's input data before using one of these, thereby destroying pre-existing mal-order. However, there is no proof that one can't randomise one's data into a pessimal order - indeed, a trivial proof that one can. It just becomes thermodynamically unlikely as the number of items increases (and for the case of small N, then even pesimally slow is tolerably fast). In this case one can calculate the probabilities.

There are a large number of algorithms which do not have provable bounds, or which have extremely undesirable provable bounds, but which work fine in practice. If btrfs is one of these, do we need to worry if it has theoretical weaknesses? Perhaps, if it is possible to run an attack on a filesystem that fragments it into uselessness even after deletion of the files created by the attacker. Certainly, if it is possible that real-world usage may accidentally arrive in this unfortunate state. Not at all, if such an attack is only theoretically possible, but not realizable in the real world by a party lacking access to the filesystem's internal structures (or more accurately, realisable in the real world only with a thermodynamically small probability for a realistically large filesystem)

Which is it? It may be that even this question is not amenable to theory, and will have to be resolved by real-world testing.