Two kinds of atomic commit

Matthew Dillon dillon at
Mon Jul 28 10:04:34 PDT 2008

:1) The Update a Clone Method
:2) The Update in Place Method

    Hmm.  Those seem fairly complex.  How would you deal with incidental
    operations on the B-Tree such as doing a split?  A single insert
    could wind up requiring a split of every internal node on the way
    down to the leaf.  I guess you could clone the blocks, but there are
    a ton of parent and child linkages that have to be changed when you
    split a node.  It sounds pretty expensive.

    Maybe implementing UNDOs for incidental B-Tree operations is the ticket.
    Incidental meaning those operations (such as splits) which lead up to
    an insertion or deletion but do not actually perform the insertion
    or deletion.   On crash recovery you would undo partially completed
    B-Tree operations and then REDO the related logical operations.

    Having to allocate new blocks for B-Tree deletions could create a big
    issue when the filesystem becomes full or near-full.

					Matthew Dillon 
					<dillon at>

More information about the Kernel mailing list