format.txt

   1                        Backup Format Description
   2                   for an LFS-Inspired Backup Solution
   3
   4 NOTE: This format specification is not yet complete.  Right now the code
   5 provides the best documentation of the format.
   6
   7 This document simply describes the snapshot format.  It is described
   8 from the point of view of a decompressor which wishes to restore the
   9 files from a snapshot.  It does not specify the exact behavior required
  10 of the backup program writing the snapshot.
  11
  12 This document does not explain the rationale behind the format; for
  13 that, see design.txt.
  14
  15
  16 DATA CHECKSUMS
  17 ==============
  18
  19 In several places in the LBS format, a cryptographic checksum may be
  20 used to allow data integrity to be verified.  At the moment, only the
  21 SHA-1 checksum is supported, but it is expected that other algorithms
  22 will be supported in the future.
  23
  24 When a checksum is called for, the checksum is always stored in a text
  25 format.  The general format used is
  26     <algorithm>=<hexdigits>
  27
  28 <algorithm> identifies the checksum algorithm used, and allows new
  29 algorithms to be added later.  At the moment, the only permissible value
  30 is "sha1", indicating a SHA-1 checksum.
  31
  32 <hexdigits> is a sequence of hexadecimal digits which encode the
  33 checksum value.  For sha1, <hexdigits> should be precisely 40 digits
  34 long.
  35
  36 A sample checksum string is
  37     sha1=67049e7931ad7db37b5c794d6ad146c82e5f3187
  38
  39
  40 SEGMENTS & OBJECTS: STORAGE AND NAMING
  41 ======================================
  42
  43 An LBS snapshot consists, at its base, of a collection of /objects/:
  44 binary blobs of data, much like a file.  Higher layers interpret the
  45 contents of objects in various ways, but the lowest layer is simply
  46 concerned with storing and naming these objects.
  47
  48 An object is a sequence of bytes (octets) of arbitrary length.  An
  49 object may contain as few as zero bytes (though such objects are not
  50 very useful).  Object sizes are potentially unbounded, but it is
  51 recommended that the maximum size of objects produced be on the order of
  52 megabytes.  Files of essentially unlimited size can be stored in an LBS
  53 snapshot using objects of modest size, so this should not cause any real
  54 restrictions.
  55
  56 For storage purposes, objects are grouped together into /segments/.
  57 Segments use the TAR format; each object within a segment is stored as a
  58 separate file.  Segments are named using UUIDs (Universally Unique
  59 Identifiers), which are 128-bit numbers.  The textual form of a UUID is
  60 a sequence of lowercase hexadecimal digits with hyphens inserted at
  61 fixed points; an example UUID is
  62     a704eeae-97f2-4f30-91a4-d4473956366b
  63 This segment could be stored in the filesystem as a file
  64     a704eeae-97f2-4f30-91a4-d4473956366b.tar
  65 The UUID used to name a segment is assigned when the segment is created.
  66
  67 Filters can be layered on top of the segment storage to provide
  68 compression, encryption, or other features.  For example, the example
  69 segment above might be stored as
  70     a704eeae-97f2-4f30-91a4-d4473956366b.tar.bz2
  71 or
  72     a704eeae-97f2-4f30-91a4-d4473956366b.tar.gpg
  73 if the file data had been filtered through bzip2 or gpg, respectively,
  74 before storage.  Filtering of segment data is outside the scope of this
  75 format specification, however; it is assumed that if filtering is used,
  76 when decompressing the unfiltered data can be recovered (yielding data
  77 in the TAR format).
  78
  79 Objects within a segment are numbered sequentially.  This sequence
  80 number is then formatted as an 8-digit (zero-padded) hexadecimal
  81 (lowercase) value.  The fully qualified name of an object consists of
  82 the segment name, followed by a slash ("/"), followed by the object
  83 sequence number.  So, for example
  84     a704eeae-97f2-4f30-91a4-d4473956366b/000001ad
  85 names an object.
  86
  87 Within the segment TAR file, the filename used for each object is its
  88 fully-qualified name.  Thus, when extracted using the standard tar
  89 utility, a segment will produce a directory with the same name as the
  90 segment itself, and that directory will contain a set of
  91 sequentially-numbered files each storing the contents of a single
  92 object.
  93
  94 NOTE: When naming an object, the segment portion consists of the UUID
  95 only.  Any extensions appended to the segment when storing it as a file
  96 in the filesystem (for example, .tar.bz2) are _not_ part of the name of
  97 the object.
  98
  99 There are two additional components which may appear in an object name;
 100 both are optional.
 101
 102 First, a checksum may be added to the object name to express an
 103 integrity constraint: the referred-to data must match the checksum
 104 given.  A checksum is enclosed in parentheses and appended to the object
 105 name:
 106     a704eeae-97f2-4f30-91a4-d4473956366b/000001ad(sha1=67049e7931ad7db37b5c794d6ad146c82e5f3187)
 107
 108 Secondly, an object may be /sliced/: a subset of the bytes actually
 109 stored in the object may be selected to be returned.  The slice syntax
 110 is
 111     [<start>+<length>]
 112 where <start> is the first byte to return (as a decimal offset) and
 113 <length> specifies the number of bytes to return (again in decimal).  It
 114 is invalid to select using the slice syntax a range of bytes that does
 115 not fall within the original object.  The slice specification should be
 116 appended to an object name, for example:
 117     a704eeae-97f2-4f30-91a4-d4473956366b/000001ad[264+1000]
 118 selects only bytes 264..1263 from the original object.
 119
 120 Both a checksum and a slice can be used.  In this case, the checksum is
 121 given first, followed by the slice.  The checksum is computed over the
 122 original object contents, before slicing.
 123
 124
 125 FILE METADATA LISTING
 126 =====================
 127
 128 A snapshot stores two distinct types of data into the object store
 129 described above: data and metadata.  Data for a file may be stored as a
 130 single object, or the data may be broken apart into blocks which are
 131 stored as separate objects.  The file /metadata/ log (which may be
 132 spread across multiple objects) specifies the names of the files in a
 133 snapshot, metadata about them such as ownership and timestamps, and
 134 gives the list of objects that contain the data for the file.
 135
 136 The metadata log consists of a set of stanzas, each of which are
 137 formatted somewhat like RFC 822 (email) headers.  An example is:
 138
 139     name: etc/fstab
 140     checksum: sha1=11bd6ec140e4ec3110a91e1dd0f02b63b701421f
 141     data: 2f46bce9-4554-4a60-a4a2-543637bd3989/000001f7
 142     group: 0 (root)
 143     mode: 0644
 144     mtime: 1177977313
 145     size: 867
 146     type: -
 147     user: 0 (root)
 148
 149 The meanings of all the fields are described later.  A blank line
 150 separates stanzas with information about different files.  In addition
 151 to regular stanzas, the metadata listing may contain a line containing
 152 an object reference prefixed with "@".  Such a line indicates that the
 153 contents of the referenced object should be fetched and parsed as a
 154 metadata listing at this point, prior to continuing to parse the current
 155 object.
 156
 157 Several common encodings are used for various fields.  The encoding used
 158 for each field is specified in the field listing that follows.
 159     encoded string: An arbitrary string (octet sequence), with bytes
 160         optionally escaped by replacing a byte with %xx, where "xx" is a
 161         hexadecimal representation of the byte replaced.  For example,
 162         space can be replaced with "%20".  This is the same escaping
 163         mechanism as used in URLs.
 164     integer: An integer, which may be written in decimal, octal, or
 165         hexadecimal.  Strings starting with 0 are interpreted as octal,
 166         and those starting with 0x are intepreted as hexadecimal.
 167
 168 Common fields (required in all stanzas):
 169     name [encoded string]: Full path of the file archived.
 170     user [special]: The user ID of the file, as an integer, optionally
 171         followed by a space and the corresponding username, as an
 172         escaped string enclosed in parentheses.
 173     group [special]: The group ID which owns the file.  Encoding is the
 174         same as for the user field: an integer, with an optional name in
 175         parentheses following.
 176     mode [integer]: Unix mode bits for the file.
 177     type [special]: A single character which indicates the type of file.
 178         The type indicators are meant to be consistent with the
 179         characters used to indicate file type in a directory listing:
 180             -   regular file
 181             b   block device
 182             c   character device
 183             d   directory
 184             l   symlink
 185             p   pipe
 186             s   socket
 187     mtime [integer]: Modification time of the file.
 188
 189 Optional common fields:
 190     links [integer]: Number of hard links to this file, generally only
 191         reported if greater than 1.
 192     inode [string]: String specifying the inode number of this file when
 193         it was dumped.  If "links" is greater than 1, then searching for
 194         other files that have an identical "inode" value can be used to
 195         determine which files should be hard-linked together when
 196         restoring.  The inode field should be treated as an opaque
 197         string and compared for equality as such; an implementation may
 198         choose whatever representation is convenient.  The format
 199         produced by the standard tool is <major>/<minor>/<inode> (where
 200         <major> and <minor> specify the device of the containing
 201         filesystem and <inode> is the inode number of the file).
 202
 203 Special fields used for regular files:
 204     checksum [string]: Checksum of the file contents.
 205     size [integer]: Size of the file, in bytes.
 206     data [reference list]: Whitespace-separated list of object
 207         references.  The referenced data, when concatenated in the
 208         listed order, will reconstruct the file data.  Any reference
 209         that begins with a "@" character is an indirect reference--the
 210         given object includes a whitespace-separated list of object
 211         references which should be parsed in the same manner as the data
 212         field.
 213
 214
 215 SNAPSHOT DESCRIPTOR
 216 ===================
 217
 218 The snapshot descriptor is a small file which describes a single
 219 snapshot.  It is one of the few files which is not stored as an object
 220 in the segment store.  It is stored as a separate file, in plain text,
 221 but in the same directory as segments are stored.
 222
 223 The name of snapshot descriptor file is
 224     snapshot-<scheme>-<timestamp>.lbs
 225 <scheme> is a descriptive text which can be used to distinguish several
 226 logically distinct sets of snapshots (such as snapshots for two
 227 different directory trees) that are being stored in the same location.
 228 <timestamp> gives the date and time the snapshot was taken; the format
 229 is %Y%m%dT%H%M%S (20070806T092239 means 2007-08-06 09:22:39).
 230
 231 The contents of the descriptor are a set of RFC 822-style headers (much
 232 like the metadata listing).  The fields which are defined are:
 233     Format: The string "LBS Snapshot v0.2" which identifies this file as
 234         an LBS backup descriptor.  The version number (v0.2) might
 235         change if there are changes to the format.  It is expected that
 236         at some point, once the format is stabilized, the version
 237         identifier will be changed to v1.0.
 238     Producer: A informative string which identifies the program that
 239         produced the backup.
 240     Date: The date the snapshot was produced.  This matches the
 241         timestamp encoded in the filename, but is written out in full.
 242         A timezone is given.  For example: "2007-08-06 09:22:39 -0700".
 243     Scheme: The <scheme> field from the descriptor filename.
 244     Segments: A whitespace-seprated list of segment names.  Any segment
 245         which is referenced by this snapshot must be included in the
 246         list, since this list can be used in garbage-collecting old
 247         segments, determining which segments need to be downloaded to
 248         completely reconstruct a snapshot, etc.
 249     Root: A single object reference which points to the metadata
 250         listing for the snapshot.
 251     Checksums: A checksum file may be produced (with the same name as
 252         the snapshot descriptor file, but with extension .sha1sums
 253         instead of .lbs) containing SHA-1 checksums of all segments.
 254         This field contains a checksum of that file.