7ff9bbe63807bbb38713592ec0759f630b28bfda
[dragonfly.git] / sys / vfs / hammer2 / DESIGN
1
2                             HAMMER2 DESIGN DOCUMENT
3
4                                 Matthew Dillon
5                                  08-Feb-2012
6                              dillon@backplane.com
7
8 * These features have been speced in the media structures.
9
10 * Implementation work has begun.
11
12 * A working filesystem with some features implemented is expected by July 2012.
13
14 * A fully functional filesystem with most (but not all) features is expected
15   by the end of 2012.
16
17 * All elements of the filesystem have been designed except for the freemap
18   (which isn't needed for initial work).  8MB per 2GB of filesystem
19   storage has been reserved for the freemap.  The design of the freemap
20   is expected to be completely speced by mid-year.
21
22 * This is my only project this year.  I'm not going to be doing any major
23   kernel bug hunting this year.
24
25                                 Feature List
26
27 * Multiple roots (allowing snapshots to be mounted).  This is implemented
28   via the super-root concept.  When mounting a HAMMER2 filesystem you specify
29   a device path and a directory name in the super-root.
30
31 * HAMMER1 had PFS's.  HAMMER2 does not.  Instead, in HAMMER2 any directory
32   in the tree can be configured as a PFS, causing all elements recursively
33   underneath that directory to become a part of that PFS.
34
35 * Writable snapshots.  Any subdirectory tree can be snapshotted.  Snapshots
36   show up in the super-root.  It is possible to snapshot a subdirectory
37   and then later snapshot a parent of that subdirectory... really there are
38   no limitations here.
39
40 * Directory sub-hierarchy based quotas and space and inode usage tracking.
41   Any directory sub-tree, whether at a mount point or not, tracks aggregate
42   inode use and data space use.  This is stored in the directory inode all
43   the way up the chain.
44
45 * Incremental queueless mirroring / mirroring-streams.  Because HAMMER2 is
46   block-oriented and copy-on-write each blockref tracks both direct
47   modifications to the referenced data via (modify_tid) and indirect
48   modifications to the referenced data or any sub-tree via (mirror_tid).
49   This makes it possible to do an incremental scan of meta-data that covers
50   only changes made since the mirror_tid recorded in a prior-run.
51
52   This feature is also intended to be used to locate recently allocated
53   blocks and thus be able to fixup the freemap after a crash.
54
55   HAMMER2 mirroring works a bit differently than HAMMER1 mirroring in
56   that HAMMER2 does not keep track of 'deleted' records.  Instead any
57   recursion by the mirroring code which finds that (modify_tid) has
58   been updated must also send the direct block table or indirect block
59   table state it winds up recursing through so the target can check
60   similar key ranges and locate elements to be deleted.  This can be
61   avoided if the mirroring stream is mostly caught up in that very recent
62   deletions will be cached in memory and can be queried, allowing shorter
63   record deletions to be passed in the stream instead.
64
65 * Will support multiple compression algorithms configured on subdirectory
66   tree basis and on a file basis.  Up to 64K block compression will be used.
67   Only compression ratios near powers of 2 that are at least 2:1 (e.g. 2:1,
68   4:1, 8:1, etc) will work in this scheme because physical block allocations
69   in HAMMER2 are always power-of-2.
70
71   Compression algorithm #0 will mean no compression and no zero-checking.
72   Compression algorithm #1 will mean zero-checking but no other compression.
73   Real compression will be supported starting with algorithm 2.
74
75 * Zero detection on write (writing all-zeros), which requires the data
76   buffer to be scanned, will be supported as compression algorithm #1.
77   This allows the writing of 0's to create holes and will be the default
78   compression algorithm for HAMMER2.
79
80 * Copies support for redundancy.  The media blockref structure would
81   have become too bloated but I found a clean way to do copies using the
82   blockset structure (which is a set of 8 fully associative blockref's).
83
84   The design is such that the filesystem should be able to function at
85   full speed even if disks are pulled or inserted, as long as at least one
86   good copy is present.  A background task will be needed to resynchronize
87   missing copies (or remove excessive copies in the case where the copies
88   value is reduced on a live filesystem).
89
90 * Intended to be clusterable, with a multi-master protocol under design
91   but not expected to be fully operational until mid-2013.  The media
92   format for HAMMER1 was less condusive to logical clustering than I had
93   hoped so I was never able to get that aspect of my personal goals
94   working with HAMMER1.  HAMMER2 effectively solves the issues that cropped
95   up with HAMMER1 (mainly that HAMMER1's B-Tree did not reflect the logical
96   file/directory hierarchy, making cache coherency very difficult).
97
98 * Hardlinks will be supported.  All other standard features will be supported
99   too of course.  Hardlinks in this sort of filesystem require significant
100   work.
101
102 * The media blockref structure is now large enough to support up to a 192-bit
103   check value, which would typically be a cryptographic hash of some sort.
104   Multiple check value algorithms will be supported with the default being
105   a simple 32-bit iSCSI CRC.
106
107 * Fully verified deduplication will be supported and automatic (and
108   necessary in many respects).
109
110 * Non-verified de-duplication will be supported as a configurable option on
111   a file or subdirectory tree.  Non-verified deduplication would use the
112   largest available check code (192 bits) and not bother to verify data
113   matches during the dedup pass, which is necessary on extremely large
114   filesystems with a great deal of deduplicable data (as otherwise a large
115   chunk of the media would have to be read to implement the dedup).
116
117   This feature is intended only for those files where occassional corruption
118   is ok, such as in a large data store of farmed web content.
119
120                                 GENERAL DESIGN
121
122 HAMMER2 generally implements a copy-on-write block design for the filesystem,
123 which is very different from HAMMER1's B-Tree design.  Because the design
124 is copy-on-write it can be trivially snapshotted simply by referencing an
125 existing block, and because the media structures logically match a standard
126 filesystem directory/file hierarchy snapshots and other similar operations
127 can be trivially performed on an entire subdirectory tree at any level in
128 the filesystem.
129
130 The copy-on-write nature of the filesystem implies that any modification
131 whatsoever will have to eventually synchronize new disk blocks all the way
132 to the super-root of the filesystem and the volume header itself.  This forms
133 the basis for crash recovery.  All disk writes are to new blocks except for
134 the volume header, thus allowing all writes to run concurrently except for
135 the volume header update at the end.
136
137 Clearly this method requires intermediate modifications to the chain to be
138 cached so multiple modifications can be aggregated prior to being
139 synchronized.  One advantage, however, is that the cache can be flushed at
140 any time WITHOUT having to allocate yet another new block when further
141 modifications are made as long as the volume header has not yet been flushed.
142 This means that buffer cache overhead is very well bounded and can handle
143 filesystem operations of any complexity even on boxes with very small amounts
144 of physical memory.
145
146 I intend to implement a shortcut to make fsync()'s run fast, and that is to
147 allow deep updates to blockrefs to shortcut to auxillary space in the
148 volume header to satisfy the fsync requirement.  The related blockref is
149 then recorded when the filesystem is mounted after a crash and the update
150 chain is reconstituted when a matching blockref is encountered again during
151 normal operation of the filesystem.
152
153 Basically this means that no real work needs to be done at mount-time
154 even after a crash.
155
156 Directories are hashed, and another major design element is that directory
157 entries ARE INODES.  They are one and the same.  In addition to directory
158 entries being inodes the data for very small files (512 bytes or smaller)
159 can be directly embedded in the inode (overloaded onto the same space that
160 the direct blockref array uses).  This should result in very high
161 performance.
162
163 Inode numbers are not spatially referenced, which complicates NFS servers
164 but doesn't complicate anything else.  The inode number is stored in the
165 inode itself, an absolutely necessary feature in order to support the
166 hugely flexible snapshots that we want to have in HAMMER2.
167
168                                   HARDLINKS
169
170 Hardlinks are a particularly sticky problem for HAMMER2 due to the lack of
171 a spatial reference to the inode number.  We do not want to have to have
172 an index of inode numbers for any basic HAMMER2 feature if we can help it.
173
174 Hardlinks are handled by placing the inode for a multiply-hardlinked file
175 in the closest common parent directory.  If "a/x" and "a/y" are hardlinked
176 the inode for the hardlinked file will be placed in directory "a", e.g.
177 "a/3239944", but it will be invisible and will be in an out-of-band namespace.
178 The directory entries "a/x" and "a/y" will be given the same inode number
179 but in fact just be placemarks that cause HAMMER2 to recurse upwards through
180 the directory tree to find the invisible inode number.
181
182 Because directories are hashed and a different namespace (hash key range)
183 is used for hardlinked inodes, standard directory scans are able to trivially
184 skip this invisible namespace and inode-specific lookups can restrict their
185 lookup to within this space.
186
187 The nature of snapshotting makes handling link-count 2->1 and 1->2 cases
188 trivial.  Basically the inode media structure is copied as needed to break-up
189 or re-form the standard directory entry/inode.  There are no backpointers in
190 HAMMER2 and no reference counts on the blocks (see FREEMAP NOTES below), so
191 it is an utterly trivial operation.
192
193                                 FREEMAP NOTES
194
195 In order to implement fast snapshots (and writable snapshots for that
196 matter), HAMMER2 does NOT ref-count allocations.  The freemap which
197 is still under design just won't do that.  All the freemap does is
198 keep track of 100% free blocks.
199
200 This not only trivializes all the snapshot features it also trivializes
201 hardlink handling and solves the problem of keeping the freemap sychronized
202 in the event of a crash.  Now all we have to do after a crash is make
203 sure blocks allocated before the freemap was flushed are properly
204 marked as allocated in the allocmap.  This is a trivial exercise using the
205 same algorithm the mirror streaming code uses (which is very similar to
206 HAMMER1)... an incremental meta-data scan that covers only the blocks that
207 might have been allocated between the last allocation map sync and now.
208
209 Thus the freemap does not have to be synchronized during a fsync().
210
211 The complexity is in figuring out what can be freed... that is, when one
212 can mark blocks in the freemap as being free.  HAMMER2 implements this as
213 a background task which essentially must scan available meta-data to
214 determine which blocks are not being referenced.
215
216 Part of the ongoing design work is finding ways to reduce the scope of this
217 meta-data scan so the entire filesystem's meta-data does not need to be
218 scanned (though in tests with HAMMER1, even full meta-data scans have
219 turned out to be fairly low cost).  In other words, its an area that we
220 can continue to improve on as the filesystem matures.  Not only that, but
221 we can completely change the freemap algorithms without creating
222 incompatibilities (at worse simply having to require that a R+W mount do
223 a full meta-data scan when upgrading or downgrading the freemap algorithm).
224
225                                   CLUSTERING
226
227 Clustering, as always, is the most difficult bit but we have some advantages
228 with HAMMER2 that we did not have with HAMMER1.  First, HAMMER2's media
229 structures generally follow the kernel's filesystem hiearchy.  Second,
230 HAMMER2's writable snapshots make it possible to implement several forms
231 of multi-master clustering.
232
233 The general mechanics for most of the multi-master clustering implementations
234 will be as follows:
235
236     (a) Use the copies mechanism to specify all elements of the cluster,
237         both local and remote (networked).
238
239     (b) The core synchronization state operates just as it does for copies,
240         simply requiring a fully-flushed ack from the remote in order to
241         mark the blocks as having been fully synchronized.
242
243         The mirror_tid may be used to locate these blocks, allowing the
244         synchronization state to be updated on the fly at a much later
245         time without requiring the state to be maintained in-memory.
246         (also for crash recovery resynchronization purposes).
247
248     (c) Data/meta-data can be retrieved from those copies which are marked
249         as being synchronized, with priority given to the local storage
250         relative to any given physical machine.
251
252         This means that e.g. even in a master-slave orientation the slave
253         may be able to satisfy a request from a program when the slave
254         happens to be the local storage.
255
256     (d) Transaction id synchronization between all elements of the cluster,
257         typically through masking (assigning a cluster number using the low
258         3 bits of the transaction id).
259
260     (e) General access (synchronized or otherwise) may require cache
261         coherency mechanisms to run over the network.
262
263         Implementing cache coherency is a major complexity issue.
264
265     (f) General access (synchronized or otherwise) may require quorum
266         agreement, using the synchronization flags in the blockrefs
267         to determine whether agreement has been reached.
268
269         Implementing quorum voting is a major complexity issue.
270
271 There are lots of ways to implement multi-master environments using the
272 above core features but the implementation is going to be fairly complex
273 even with HAMMER2's feature set.
274
275 Keep in mind that modifications propagate all the way to the super-root
276 and volume header, so in any clustered arrangement the use of (modify_tid)
277 and (mirror_tid) is critical in determining the synchronization state of
278 portion(s) of the filesystem.
279
280 Specifically, since any modification propagates to the root the (mirror_tid)
281 in higher level directories is going to be in a constant state of flux.  This
282 state of flux DOES NOT invalidate the cache state for these higher levels
283 of directories.  Instead, the (modify_tid) is used on a node-by-node basis
284 to determine cache state at any given level, and (mirror_tid) is used to
285 determine whether any recursively underlying state is desynchronized.
286
287 * Simple semi-synchronized multi-master environment.
288
289     In this environment all nodes are considered masters and modifications
290     can be made on any of them, and then propagate to the others
291     asynchronously via HAMMER2 mirror streams.  One difference here is
292     that kernel can activate these userland-managed streams automatically
293     when the copies configuration is used to specify the cluster.
294
295     The only type of conflict which isn't readily resolvable by comparing
296     the (modify_tid) is when file data is updated.  In this case user
297     intervention might be required but, theoretically, it should be
298     possible to automate most merges using a multi-way patch and, if not,
299     choosing one and creating backup copies if the others to allow the
300     user or sysop to resolve the conflict later.
301
302 * Simple fully synchronized fail-over environment.
303
304     In this environment there is one designated master and the remaining
305     nodes are slaves.  If the master fails all remaining nodes agree on a
306     new master, possibly with the requirement that a quorum be achieved
307     (if you don't want to allow the cluster to split).
308
309     If network splits are allowed the each sub-cluster operates in this
310     mode but recombining the clusters reverts to the first algorithm.
311     If not allowed whomever no longer has a quorum will be forced to stall.
312
313     In this environment the current designated master is responsible for
314     managing locks for modifying operations.  The designated master will
315     proactively tell the other nodes to mark the blocks related to the
316     modifying operation as no longer being synchronized while any local
317     data at the node that acquired the lock (master or slave) remains
318     marked as being synchronized.
319
320     The node that succesfully gets the lock then issues the modifying
321     operation to both its local copy and to the master, marking the
322     master as being desynchronized until the master acknowledges receipt.
323
324     In this environment any node can access data from local storage if
325     the designated master copy is marked synchronized AND its (modify_tid)
326     matches the slave copy's (modify_tid).
327
328     However, if a slave disconnects from the master then reconnects the
329     slave will have lost the master's desynchronization stream and must
330     mark its root blockref for the master copy HAMMER2_BREF_DESYNCHLD as
331     well as clear the SYNC1/SYNC2 bits.  Setting DESYNCCHLD forces on-demand
332     recursive reverification that the master and slave are (or are not) in
333     sync in order to reestablish on the slave the synchronization state of
334     the master.
335
336     That might be a bit confusing but the whole point here is to allow
337     read accesses to the filesystem to be satisfied by any node in a
338     multi-master cluster, not just by the current designated master.
339
340 * Fully cache coherent and synchronized multi-master environment.
341
342     In this environment a quorum is required to perform any modifying
343     action.  All nodes are masters (there is no 'designated' master)
344     and all nodes connect to all other nodes in a cross-bar.
345
346     The quorum is specified by copies setup in the root volume configuration.
347     A quorum of nodes in the cluster must agree on the copies configuration.
348     If they do not the cluster cannot proceed to mount.  Any other nodes
349     not in the quorum which are in the cluster which disagree with the
350     configuration will inherit the copies configuration from the quorum.
351
352     Any modifying action will initiate a lock request locally to all nodes
353     in the cluster.  The modifying action is allowed to proceed the instant
354     a quorum of nodes respond in the affirmative (even if some have not
355     yet responded or are down).  The modifying action is considered complete
356     once the two-phase commit protocol succeeds.  The modifying action
357     typically creates and commits a temporary snapshot on at least a quorum
358     of masters as phase-1 and then ties the snapshot back into the main
359     mount as phase-2.
360
361     These locks are cache-coherency locks and may be passively maintained
362     in order to aggregate multiple operations under the same lock and thus
363     under the same transaction from the point of view of the rest of the
364     quorum.
365
366     A lock request which interferes with a passively maintained lock will
367     force the two-phase commit protocol to complete and then transfer
368     ownership to the requesting entity, thus avoiding having to deal with
369     deadlock protocols at this point in the state machine.
370
371     Since any node can initiate concurrent lock requests to many other nodes
372     it is possible to deadlock.  When two nodes initiate conflicting lock
373     requests to the cluster the one achieving the quorum basically wins and
374     the other is forced to retry (go back one paragraph).  In this situation
375     no deadlock will occur.
376
377     If three are more nodes initiate conflicting lock requests to the
378     cluster a deadlock can occur whereby none of the nodes achieve a quorum.
379     In this case every node will know which of the other nodes was granted
380     the lock(s).  Deadlock resolution then proceeds simultaniously on the
381     three nodes (since they have the same information), whereby the lock
382     holders on the losing end of the algorithm transfer their locks to one
383     of the other nodes.  The lock state and knowledge of the lock state is
384     updated in real time on all nodes until a quorum is achieved.
385
386 * Fully cache coherent and synchronized multi-master environment with
387   passive read locking.
388
389     This is a more complex form of clustering than the previous form.
390     Take the previous form and add the ability to passively hold SHARED
391     locks in addition to the EXCLUSIVE locks the previous form is able
392     to hold.
393
394     The advantage of being able to passively hold a shared lock on a sub-tree
395     (locks can be held on single nodes or entire sub-trees) is that it is
396     then possible for all nodes to validate a node (modify_tid) or entire
397     sub-tree (mirror_tid) with a very short network transaction and then
398     satisfy a large number of requests from local storage.
399
400 * Fully cache coherent and synchronized multi-master environment with
401   passive read locking and slave-only nodes.
402
403     This is the MOST complex form of clustering we intend to support.
404     In a multi-master environment requiring a quorum of masters to operate
405     we implement all of the above plus ALSO allow additional nodes to be
406     added to the cluster as slave-only nodes.
407
408     The difference between a slave-only node and setting up a manual
409     mirror-stream from the cluster to a read-only snapshot on another
410     HAMMER2 filesystem is that the slave-only node will be fully
411     cache coherent with either the cluster proper (if connected to a quorum
412     of masters), or to one or more other nodes in the cluster (if not
413     connected to a quorum of masters), EVEN if the slave itself is not
414     completely caught up.
415
416     So if the slave-only cluster node is connected to the rest of the cluster
417     over a slow connection you basically get a combination of local disk
418     speeds for any data that is locally in sync and network-limited speeds
419     for any data that is not locally in sync.
420
421     slave-only cluster nodes run a standard mirror-stream in the background
422     to pull in the data as quickly as possible.
423
424     This is in constrast to a manual mirror-stream to a read-only
425     snapshot (basically a simple slave), which has no ability to bypass
426     the local storage to handle out-of-date requests (in fact has no ability
427     to detect that the local storage is out-of-date anyway).