DragonFly-2.3.0.405.g1775b6 master sys/conf files sys/vfs/hammer Makefile hammer.h hammer_btree.c hammer_cursor.c hammer_ioctl.c hammer_rebalance.c hammer_reblock.c

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxxxxx>]

commit 1775b6a0acbf9ffea2442141c3d913793fe39738
Author: Matthew Dillon <dillon@apollo.backplane.com>
Date:   Sun Mar 15 15:28:38 2009 -0700

    HAMMER VFS - Add a B-Tree rebalancing feature.
    
    This is the initial commit of B-Tree rebalancing support for HAMMER.
    The rebalancer may be run using the 'hammer rebalance' utility directive.
    
    The leafs in a HAMMER B-Tree all reside at the same depth.  Insertions and
    deletions only collapse the B-Tree when a leaf node becomes empty and then
    only if any necessary recursion (possibly reaching the root node) succeeds.
    No balancing occurs during normal operation and B-Tree nodes can wind up
    with wildly different element counts which bloats the tree and makes
    searches less efficient.
    
    The rebalancer effectively does a depth-first traversal of the B-Tree,
    visiting leaf nodes first and parent nodes as a trailing function on the
    way back up the tree.  For any given internal node the sum total of
    elements contained in its children is divided by the number of children.
    The effective number of children is reduced as is practical to obtain a 75%
    fill level.  The elements are then packed into the children and any
    wholely empty children left over are deleted.  The rebalancer does not
    create new B-Tree nodes.
    
    Element packing is fairly complex, requiring tracked cursors, on-media
    parent pointers, mirror TIDs, and boundary elements to be updated.  The
    rebalancer must hold a large number of B-Tree nodes exclusively locked
    while running.

Summary of changes:
 sys/conf/files                    |    1 +
 sys/vfs/hammer/Makefile           |    3 +-
 sys/vfs/hammer/hammer.h           |   36 ++-
 sys/vfs/hammer/hammer_btree.c     |  123 +++++++--
 sys/vfs/hammer/hammer_cursor.c    |   56 ++++
 sys/vfs/hammer/hammer_ioctl.c     |    6 +
 sys/vfs/hammer/hammer_rebalance.c |  526 +++++++++++++++++++++++++++++++++++++
 sys/vfs/hammer/hammer_reblock.c   |   12 +-
 8 files changed, 731 insertions(+), 32 deletions(-)
 create mode 100644 sys/vfs/hammer/hammer_rebalance.c

http://gitweb.dragonflybsd.org/dragonfly.git/commitdiff/1775b6a0acbf9ffea2442141c3d913793fe39738


-- 
DragonFly BSD source repository