DragonFly users List (threaded) for 2008-01
HAMMER update - 1/11/2008
HAMMER is progressing very well with only 3-4 big-ticket items left
* On-the-fly Recovery (<--- current WIP)
* Refactoring of the spike code
* Retention policy scan
Everything else is now working and reasonably stable. Of the remaining
items only the spike coding has any real algorithmic complexity. Recovery
and balancing just require brute force and the physical record deletion
the retention policy scan needs to do is already coded and working (just
not the scan itself).
I'm really happy with the progress I'm making on HAMMER.
I'm going to talk about the spike and balancing code for a moment. What
is a spike? Basically, when a cluster (a 64MB block of of the disk) fills
up a 'spike' needs to be driven into that cluster's B-Tree in order to
expand it into a new cluster. The spike basically forwards a portion of
the B-Tree's key space to a new cluster.
At the moment the spike takes the B-Tree cursor at a leaf after a failed
insertion (due to running out of space) and copies that whole leaf to a
new cluster, then replaces the reference in the internal node pointing
to that leaf with a pointer to the new cluster (the 'spike').
This is extremely inefficient because the key space covered by the spike
is usually fairly minimal, so the newly spiked cluster might not fill up
before another spike is needed.
Refactoring the spike code means doing a better job selecting the amount
of key space the spike can represent.
The balancing code is responsible for slowly cleaning up any
inefficiencies that build up in the filesystem. As its name
implies, the idea is to 'balance' the overall B-Tree representing
the filesystem. We want to slowly move physical data records
from higher level clusters to lower level clusters, eventually
winding up with a situation where the higher level clusters contain
only spikes and lower level clusters are mostly full.
The idea is for the spike code to use heuristics to try to select
an optimal key range to copy into the new spike to try to avoid
unnecessary copying later on, and if it doesn't make good choices
the balancing code will come along and finish the job.
Keep in mind that HAMMER is designed to handle very large filesystems...
in particular, filesystems that are big enough that you don't actually
fill them up under normal operation, or at least do not quickly fill
them up and then quickly clean them out. The balancing code is expected
to need upwards of a day (or longer) to slowly iron out storage
inefficiencies. If a situation comes up where faster action is needed,
then faster action can be taken. I intend to take advantage of the fact
that most filesystems (and, really, any large filesystem), takes quite
a while to actually become full.