lkml.org 
[lkml]   [2010]   [Jun]   [18]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectBalancing leaves when walking from top to down (was Btrfs:...)
    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



    \
     
     \ /
      Last update: 2010-06-19 00:07    [W:0.046 / U:30.784 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site