1 $DragonFly: src/sys/vfs/hammer/Attic/hammer.txt,v 1.2 2007/10/12 17:17:20 dillon Exp $
5 (I) General Storage Abstraction
7 HAMMER uses a basic 16K filesystem buffer for all I/O. Buffers are
8 collected into clusters, cluster are collected into super-clusters,
9 and super-clusters are collected into volumes. A single HAMMER filesystem
10 may span multiple volumes.
12 HAMMER maintains small hinted radix trees called A-Lists in several
13 places for storage management in each layer. A major feature of the
14 A-list is the ability to stack with another A-list and pass hinting
15 information between the two to create an integrated storage management
18 Volumes are typically specified as disk partitions, with one volume
19 designated as the root volume containing the root cluster. The root
20 cluster does not need to be contained in volume 0 nor does it have to
21 be located at any particular offset.
23 Data can be migrated on a cluster-by-cluster or volume-by-volume basis
24 and any given volume may be expanded or contracted while the filesystem
25 is live. Whole volumes can be added and (with appropriate data
28 HAMMER's storage management limits it to 32768 volumes. Each volume
29 contains up to 16384 super-clusters and each super-cluster may contain
30 up to 32768 clusters. A cluster may contain up to 4096 16K filesystem
31 buffers (64MB). Volumes less then 2TB do away with the super-cluster
32 layer. HAMMER can manage individual volumes up to 32768TB each. The
33 total size of a HAMMER filesystem is, well, a lot, about 2^70 bytes of
36 HAMMER breaks all of its information down into objects and records.
37 Records have a creation and deletion transaction id which allows HAMMER
38 to maintain a historical store. Information is only physically deleted
39 based on the data retention policy. Those portions of the data retention
40 policy affecting near-term modifications may be acted upon by the live
41 filesystem but all historical vacuuming is handled by a helper process.
43 All information in a HAMMER filesystem is CRCd to detect corruption.
45 (II) Filesystem Object Topology
47 The objects and records making up a HAMMER filesystem is organized into
48 a single, unified B-Tree. Each cluster maintains a B-Tree of the
49 records contained in that cluster and a unified B-Tree is constructed by
50 linking clusters together. HAMMER issues PUSH and PULL operations
51 internally to open up space for new records and to balance the global
52 B-Tree. These operations may have the side effect of allocating
53 new clusters or freeing clusters which become unused.
55 B-Tree operations tend to be limited to a single cluster. That is,
56 the B-Tree insertion and deletion algorithm is not extended to the
57 whole unified tree. If insufficient space exists in a cluster HAMMER
58 will allocate a new cluster, PUSH a portion of the existing
59 cluster's record store to the new cluster, and link the existing
60 cluster's B-Tree to the new one.
62 Because B-Tree operations tend to be restricted and because HAMMER tries
63 to avoid balancing clusters in the critical path, HAMMER employs a
64 background process to keep the topology as a whole in balance. One
65 side effect of this is that HAMMER is fairly loose when it comes to
66 inserting new clusters into the topology.
68 HAMMER objects revolve around the concept of an object identifier.
69 The obj_id is a 64 bit quantity which uniquely identifies a filesystem
70 object for the entire life of the filesystem. This uniqueness allows
71 backups and mirrors to retain varying amounts of filesystem history by
72 removing any possibility of conflict through identifier reuse. HAMMER
73 typically iterates object identifiers sequentially and expects to never
74 run out. At a creation rate of 100,000 objects per second it would
75 take HAMMER around 6 million years to run out of identifier space.
76 The characteristics of the HAMMER obj_id also allow HAMMER to operate
77 in a multi-master clustered environment.
79 A filesystem object is made up of records. Each record references a
80 variable-length store of related data, a 64 bit key, and a creation
81 and deletion transaction id which is indexed along with the key.
83 HAMMER utilizes a 64 bit key to index all records. Regular files use
84 the base data offset of the record as the key while directories use a
85 namekey hash as the key and store one directory entry per record. For
86 all intents and purposes a directory can store an unlimited number of
89 HAMMER is also capable of associating any number of out-of-band
90 attributes with a filesystem object using a separate key space. This
91 key space may be used for extended attributes, ACLs, and anything else
94 (III) Access to historical information
96 A HAMMER filesystem can be mounted with an as-of date to access a
97 snapshot of the system. Snapshots do not have to be explicitly taken
98 but are instead based on the retention policy you specify for any
99 given HAMMER filesystem. It is also possible to access individual files
100 or directories (and their contents) using an as-of extension on the
103 HAMMER uses the transaction ids stored in records to present a snapshot
104 view of the filesystem as-of any time in the past, with a granularity
105 based on the retention policy chosen by the system administrator.
106 feature also effectively implements file versioning.
108 (IV) Mirrors and Backups
110 HAMMER is organized in a way that allows an information stream to be
111 generated for mirroring and backup purposes. This stream includes all
112 historical information available in the source. No queueing is required
113 so there is no limit to the number of mirrors or backups you can have
114 and no limit to how long any given mirror or backup can be taken offline.
115 Resynchronization of the stream is not considered to be an expensive
118 Mirrors and backups are maintained logically, not physically, and may
119 have their own, independant retention polcies. For example, your live
120 filesystem could have a fairly rough retention policy, even none at all,
121 then be streamed to an on-site backup and from there to an off-site
122 backup, each with different retention policies.
124 (V) Transactions and Recovery
126 HAMMER implement an instant-mount capability and will recover information
127 on a cluster-by-cluster basis as it is being accessed.
129 HAMMER numbers each record it lays down and stores a synchronization
130 point in the cluster header. Clusters are synchronously marked 'open'
131 when undergoing modification. If HAMMER encounters a cluster which is
132 unexpectedly marked open it will perform a recovery operation on the
133 cluster and throw away any records beyond the synchronization point.
135 HAMMER supports a userland transactional facility. Userland can query
136 the current (filesystem wide) transaction id, issue numerous operations
137 and on recovery can tell HAMMER to revert all records with a greater
138 transaction id for any particular set of files. Multiple userland
139 applications can use this feature simultaniously as long as the files
140 they are accessing do not overlap. It is also possible for userland
141 to set up an ordering dependancy and maintain completely asynchronous
142 operation while still being able to guarentee recovery to a fairly
143 recent transaction id.
147 HAMMER uses 64 bit keys internally and makes key-based files directly
148 available to userland. Key-based files are not regular files and do not
149 operate using a normal data offset space.
151 You cannot copy a database file using a regular file copier. The
152 file type will not be S_IFREG but instead will be S_IFDB. The file
153 must be opened with O_DATABASE. Reads which normally seek the file
154 forward will instead iterate through the records and lseek/qseek can
155 be used to acquire or set the key prior to the read/write operation.