Balancing leaves when walking from top to down (was Btrfs:...)

[Edward Shishkin <edward@redhat.com>]

Chris Mason wrote:
> On Fri, Jun 18, 2010 at 09:29:40PM +0200, Edward Shishkin wrote:
>   
>> 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.
>>>       
>> Hello Jamie.
>>
>>     
>>> 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
>> records don't
>> 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
>> choose some
>> *sane* strategy (for example the paper of Ohad Rodeh) and strictly
>> adhere this in
>> future.
>>     
>
> Again, other than the inline file data, what exactly do you believe
> needs to change?

1. getting rid of inline extents;
2. new formats for directory and xattr items to not look like a train,
   which is able to occupy the whole leaf;
3. make sure we do pro-active balancing like it is described in the paper.

Sorry, I don't see other ways for now..

>   Top down balancing vs balancing on insertion doesn't
> impact our ability to maintain full leaves.  The current code is clearly
> choosing not to merge two leaves that it should have merged, which is
> just a plain old bug.
>   

How are you going to balance leaves when walking from top to down?
Suppose 1) and 2) above are not satisfied and having arrived to the leaf
level we see a number of items of variable length. What will we do to
keep leaves full?

Could you please provide a sketch of the algorithm?

Thanks!

-- 
Edward O. Shishkin
Principal Software Engineer
Red Hat Czech