DragonFly commits List (threaded) for 2008-07
cvs commit: src/sys/vfs/hammer hammer.h hammer_btree.c hammer_cursor.h hammer_disk.h hammer_inode.c hammer_ioctl.h hammer_mirror.c hammer_object.c hammer_subs.c hammer_vnops.c
dillon 2008/07/09 21:44:33 PDT
DragonFly src repository
sys/vfs/hammer hammer.h hammer_btree.c hammer_cursor.h
HAMMER 60J/Many: Mirroring
Finish implementing the core mirroring algorithm. The last bit was to add
support for no-history deletions on the master. The same support also covers
masters which have pruned records away prior to the mirroring operation.
As with the work done previously, the algorithm is 100% queue-less and
has no age limitations. You could wait a month, and then do a mirroring
update from master to slave, and the algorithm will efficiently handle it.
The basic issue that this commit tackles is what to do when records are
physically deleted from the master. When this occurs the mirror master
cannot provide a list of records to delete to its slaves.
The solution is to use the mirror TID propagation to physically identify
swaths of the B-Tree in which a deletion MAY have taken place. The
mirroring code uses this information to generate PASS and SKIP mrecords.
A PASS identifies a record (sans its data payload) that remains within
the identified swath and should already exist on the target. The
mirroring target does a simultanious iteration of the same swath on the
target B-Tree and deletes records not identified by the master.
A SKIP is the heart of the algorithm's efficiency. The same mirror TID
stored in the B-Tree can also identify large swaths of the B-Tree for which
*NO* deletions have taken place (which will be most of the B-Tree). One
SKIP Record can identify an arbitrarily large swath. The target uses
the SKIP record to skip that swath on the target. No scan takes place.
SKIP records can be generated from any internal node of the B-Tree and cover
that node's entire sub-tree.
This also provides us with the feature where the retention policy can be
completely different between a master and a mirror, or between mirrors.
When the slave identifies a record that must be deleted through the above
algorithm it only needs to mark it as historically deleted, it does not
have to physically delete the record.
Revision Changes Path
1.109 +2 -1 src/sys/vfs/hammer/hammer.h
1.68 +91 -12 src/sys/vfs/hammer/hammer_btree.c
1.25 +18 -1 src/sys/vfs/hammer/hammer_cursor.h
1.49 +12 -1 src/sys/vfs/hammer/hammer_disk.h
1.97 +7 -0 src/sys/vfs/hammer/hammer_inode.c
1.19 +53 -10 src/sys/vfs/hammer/hammer_ioctl.h
1.10 +499 -122 src/sys/vfs/hammer/hammer_mirror.c
1.85 +3 -2 src/sys/vfs/hammer/hammer_object.c
1.33 +1 -1 src/sys/vfs/hammer/hammer_subs.c
1.85 +13 -18 src/sys/vfs/hammer/hammer_vnops.c