Of Episodes, Phases and Forks

[Daniel Phillips]

On Thursday 23 October 2008 21:37, Matthew Dillon wrote:
> :the parents of member blocks.  Each promise is a triple:
> :
> :   { body extent, parent address, offset }
> 
>     There may be an issue when making multiple updates to related meta-data.
>     For example, if inserting an element in a B-Tree the extent of the
>     modification to the block may cover most of the block even though the
>     actual operation is just an insertion.
> 
>     You might have to make the promises more sophisticated to be able to
>     record such modifications without generating large amounts of data
>     in the promise tuple.

Clearly there is plenty of scope to get this wrong.  The "offset" above
is specific to the type of metadata item being altered.  In the case of
a data btree leaf (dleaf) it is the difference between the base logical
address encoded in the dleaf and the logical offset of the extent being
inserted.  On reconstruction, the insertion is performed by the same
mechanism that inserted the extent into the cached dleaf in normal
operation, hopefully with the same result.

The rule I didn't state is that all these promises have to be applied
in order at reconstruction time, so that when all promises in the log
are applied, up to the end of the last complete phase, the result will
be exactly the metadata block that was in cache when that phase was
committed to disk.  And there will be a checksum crosscheck going on at
least initially when this code is shakey.

I also didn't describe how splits are handled, because I am not sure
yet whether it is best to try to encode them via some logical scheme,
or log the resulting blocks verbatim, or force a rollup at that point.
A little messy.

Indeed, this sounds a rather long chain of reasoning, but if a computer
can't produce the same result twice in a row by following the same
sequence of actions, we have bigger problems that just fullfilling Tux3
metadata promises.

By the way, I wish I'd thought of a better term for this than promise,
but that one seems to be catching on.  It is certainly shorter than
"logical update logged in a commit block".

>     Side note:  HAMMER uses an unsophisticated method when generating its
>     UNDO, but because the UNDO works in reverse of your promise, multiple
>     modifications to the same meta-data within a single phase (using your
>     terminology) only needs the initial UNDO and can throw away the
>     generation of followup UNDOs for each modification covering the same
>     meta-data space.

Unsophsticated methods are good :-)

Thanks much for the commentary so far,

Daniel