doc/design.txt

   1 This document aims to describe the goals and constraints of the Cumulus
   2 design.
   3
   4 ========================================================================
   5
   6 OVERALL GOALS: Efficient creation and storage of multiple backup
   7 snapshots of a filesystem tree.  Logically, each snapshot is
   8 self-contained and stores the state of all files at a single point in
   9 time.  However, it should be possible for snapshots to share the same
  10 underlying storage, so that data duplicated in many snapshots need not
  11 be stored multiple times.  It should be possible to delete old
  12 snapshots, and recover (most of) the storage associated with them.  It
  13 must be possible to delete old backups in any order; for example, it
  14 must be possible to delete intermediate backups before long-term
  15 backups.  It should be possible to recover the files in a snapshot
  16 without transferring significantly more data than that stored in the
  17 files to be recovered.
  18
  19 CONSTRAINTS: The system should not rely upon a smart server at the
  20 remote end where backups are stored.  It should be possible to create
  21 new backups using a single primitive: StoreFile, which stores a string
  22 of bytes at the backup server using a specified filename.  Thus, backups
  23 can be run over any file transfer protocol, without requiring special
  24 software be installed on the storage server.
  25
  26 ========================================================================
  27
  28 DESIGN APPROACHES
  29
  30 STORING INCREMENTAL BACKUPS
  31
  32 One simple approach is to simply store a copy of every file one the
  33 remote end, and construct a listing which tells where each file in the
  34 source ends up on the remote server.  For subsequent backups, if a file
  35 is unchanged, the listing can simply point to the location of the file
  36 from the previous backup.  Deleting backups is simple: delete the
  37 listing file for a particular snapshot, then garbage collect all files
  38 which are no longer referenced.
  39
  40 This approach does not as efficiently handle partial changes to large
  41 files.  If a file is changed at all, it needs to be transferred in its
  42 entirety.  One approach is to represent intra-file changes by storing
  43 patches.  The original file is kept, and a smaller file is transferred
  44 that stores the differences between the original and the new.  Some care
  45 is needed, however.  A series of small changes could accumulate over
  46 many snapshots.  If each snapshot refers to the original file, much data
  47 will be duplicated between the patches in different snapshots.  If each
  48 patch can refer to previous patches as well, a long chain of patches can
  49 build up, which complicates removing old backups to reclaim storage.
  50
  51 An alternative approach is to break files apart into smaller units
  52 (blocks) and to represent files in a snapshot as the concatenation of
  53 (possibly many) blocks.  Small change to files can be represented by
  54 replacing a few of the blocks, but referring to most blocks used in the
  55 old file directly.  Some care is needed with this approach as
  56 well--there is additional overhead needed to specify even the original
  57 file, since the entire list of blocks must be specified.  If the block
  58 size is too small, this can lead to a large overhead, but if the block
  59 size is too large, then sharing of file data may not be achieved.  In
  60 this scheme, data blocks do not depend on other data blocks, so chains
  61 of dependencies do not arise as in the incremental patching scheme.
  62 Each snapshot is independent, and so can easily be removed.
  63
  64 One minor modification to this scheme is to permit the list of blocks to
  65 specify that only a portion of a block should be used to reconstruct a
  66 file; if, say, only the end of a block is changed, then the new backup
  67 can refer to most of the old block, and use a new block for the small
  68 changed part.  Doing so does allow the possibility that a block might be
  69 kept around even though a portion of it is being used, leading to wasted
  70 space.
  71
  72
  73 DATA STORAGE
  74
  75 The simplest data storage format would place each file, patch, or block
  76 in a separate file on the storage server.  Doing so maximizes the
  77 ability to reclaim storage when deleting old snapshots, and minimizes
  78 the amount of extra data that must be transferred to recover a snapshot.
  79 Any other format which combines data from multiple files/patches/blocks
  80 together risks having needed data grouped with unwanted data.
  81
  82 However, there are reasons to consider grouping, since there is overhead
  83 associated with storing many small files.  In any transfer protocol
  84 which is not pipelined, transferring many small files may be slower than
  85 transferring the same quantity of data in larger files.  Small files may
  86 also lead to more wasted storage space due to internal fragmentation.
  87 Grouping files together gives the chance for better compression, taking
  88 advantage of inter-file similarity.
  89
  90 Grouping is even more important if the snapshot format breaks files
  91 apart into blocks for storage, since the number of blocks could be far
  92 larger than the number of files being backed up.
  93
  94 ========================================================================
  95
  96 SELECTED DESIGN
  97
  98 At a high level, the selected design stores snapshots by breaking files
  99 into blocks for storage, and does not use patches.  These data blocks,
 100 along with the metadata fragments (collectively, the blocks and metadata
 101 are referred to as objects) are grouped together for storage purposes
 102 (each storage group is called a segment).
 103
 104 TAR is chosen as the format for grouping objects together into segments
 105 rather than inventing a new format.  Doing so makes it easy to
 106 manipulate the segments using other tools, if needed.
 107
 108 Data blocks for files are stored as-is.  Metadata is stored in a text
 109 format, to make it more transparent.  (This should make debugging
 110 easier, and the hope is that this will make understanding the format
 111 simpler.)