docs/backupdb.txt

   1 = The Tahoe BackupDB =
   2
   3 == Overview ==
   4 To speed up backup operations, Tahoe maintains a small database known as the
   5 "backupdb". This is used to avoid re-uploading files which have already been
   6 uploaded recently.
   7
   8 This database lives in ~/.tahoe/private/backupdb.sqlite, and is a SQLite
   9 single-file database. It is used by the "tahoe backup" command. In the future,
  10 it will also be used by "tahoe mirror", and by "tahoe cp" when the
  11 --use-backupdb option is included.
  12
  13 The purpose of this database is twofold: to manage the file-to-cap
  14 translation (the "upload" step) and the directory-to-cap translation (the
  15 "mkdir-immutable" step).
  16
  17 The overall goal of optimizing backup is to reduce the work required when the
  18 source disk has not changed (much) since the last backup. In the ideal case,
  19 running "tahoe backup" twice in a row, with no intervening changes to the
  20 disk, will not require any network traffic. Minimal changes to the source
  21 disk should result in minimal traffic.
  22
  23 This database is optional. If it is deleted, the worst effect is that a
  24 subsequent backup operation may use more effort (network bandwidth, CPU
  25 cycles, and disk IO) than it would have without the backupdb.
  26
  27 The database uses sqlite3, which is included as part of the standard python
  28 library with python2.5 and later. For python2.4, Tahoe will try to install the
  29 "pysqlite" package at build-time, but this will succeed only if sqlite3 with
  30 development headers is already installed.  On Debian and Debian derivatives
  31 you can install the "python-pysqlite2" package (which, despite the name,
  32 actually provides sqlite3 rather than sqlite2), but on old distributions such
  33 as Debian etch (4.0 "oldstable") or Ubuntu Edgy (6.10) the "python-pysqlite2"
  34 package won't work, but the "sqlite3-dev" package will.
  35
  36 == Schema ==
  37
  38 The database contains the following tables:
  39
  40 CREATE TABLE version
  41 (
  42  version integer  # contains one row, set to 1
  43 );
  44
  45 CREATE TABLE local_files
  46 (
  47  path  varchar(1024),  PRIMARY KEY -- index, this is os.path.abspath(fn)
  48  size  integer,         -- os.stat(fn)[stat.ST_SIZE]
  49  mtime number,          -- os.stat(fn)[stat.ST_MTIME]
  50  ctime number,          -- os.stat(fn)[stat.ST_CTIME]
  51  fileid integer
  52 );
  53
  54 CREATE TABLE caps
  55 (
  56  fileid integer PRIMARY KEY AUTOINCREMENT,
  57  filecap varchar(256) UNIQUE    -- URI:CHK:...
  58 );
  59
  60 CREATE TABLE last_upload
  61 (
  62  fileid INTEGER PRIMARY KEY,
  63  last_uploaded TIMESTAMP,
  64  last_checked TIMESTAMP
  65 );
  66
  67 CREATE TABLE directories
  68 (
  69  dirhash varchar(256) PRIMARY KEY,
  70  dircap varchar(256),
  71  last_uploaded TIMESTAMP,
  72  last_checked TIMESTAMP
  73 );
  74
  75 == Upload Operation ==
  76
  77 The upload process starts with a pathname (like ~/.emacs) and wants to end up
  78 with a file-cap (like URI:CHK:...).
  79
  80 The first step is to convert the path to an absolute form
  81 (/home/warner/.emacs) and do a lookup in the local_files table. If the path
  82 is not present in this table, the file must be uploaded. The upload process
  83 is:
  84
  85  1. record the file's size, creation time, and modification time
  86  2. upload the file into the grid, obtaining an immutable file read-cap
  87  3. add an entry to the 'caps' table, with the read-cap, to get a fileid
  88  4. add an entry to the 'last_upload' table, with the current time
  89  5. add an entry to the 'local_files' table, with the fileid, the path,
  90     and the local file's size/ctime/mtime
  91
  92 If the path *is* present in 'local_files', the easy-to-compute identifying
  93 information is compared: file size and ctime/mtime. If these differ, the file
  94 must be uploaded. The row is removed from the local_files table, and the
  95 upload process above is followed.
  96
  97 If the path is present but ctime or mtime differs, the file may have changed.
  98 If the size differs, then the file has certainly changed. At this point, a
  99 future version of the "backup" command might hash the file and look for a
 100 match in an as-yet-defined table, in the hopes that the file has simply been
 101 moved from somewhere else on the disk. This enhancement requires changes to
 102 the Tahoe upload API before it can be significantly more efficient than
 103 simply handing the file to Tahoe and relying upon the normal convergence to
 104 notice the similarity.
 105
 106 If ctime, mtime, or size is different, the client will upload the file, as
 107 above.
 108
 109 If these identifiers are the same, the client will assume that the file is
 110 unchanged (unless the --ignore-timestamps option is provided, in which case
 111 the client always re-uploads the file), and it may be allowed to skip the
 112 upload. For safety, however, we require the client periodically perform a
 113 filecheck on these probably-already-uploaded files, and re-upload anything
 114 that doesn't look healthy. The client looks the fileid up in the
 115 'last_checked' table, to see how long it has been since the file was last
 116 checked.
 117
 118 A "random early check" algorithm should be used, in which a check is
 119 performed with a probability that increases with the age of the previous
 120 results. E.g. files that were last checked within a month are not checked,
 121 files that were checked 5 weeks ago are re-checked with 25% probability, 6
 122 weeks with 50%, more than 8 weeks are always checked. This reduces the
 123 "thundering herd" of filechecks-on-everything that would otherwise result
 124 when a backup operation is run one month after the original backup. If a
 125 filecheck reveals the file is not healthy, it is re-uploaded.
 126
 127 If the filecheck shows the file is healthy, or if the filecheck was skipped,
 128 the client gets to skip the upload, and uses the previous filecap (from the
 129 'caps' table) to add to the parent directory.
 130
 131 If a new file is uploaded, a new entry is put in the 'caps' and 'last_upload'
 132 table, and an entry is made in the 'local_files' table to reflect the mapping
 133 from local disk pathname to uploaded filecap. If an old file is re-uploaded,
 134 the 'last_upload' entry is updated with the new timestamps. If an old file is
 135 checked and found healthy, the 'last_upload' entry is updated.
 136
 137 Relying upon timestamps is a compromise between efficiency and safety: a file
 138 which is modified without changing the timestamp or size will be treated as
 139 unmodified, and the "tahoe backup" command will not copy the new contents
 140 into the grid. The --no-timestamps can be used to disable this optimization,
 141 forcing every byte of the file to be hashed and encoded.
 142
 143 == Directory Operations ==
 144
 145 Once the contents of a directory are known (a filecap for each file, and a
 146 dircap for each directory), the backup process must find or create a tahoe
 147 directory node with the same contents. The contents are hashed, and the hash
 148 is queried in the 'directories' table. If found, the last-checked timestamp
 149 is used to perform the same random-early-check algorithm described for files
 150 above, but no new upload is performed. Since "tahoe backup" creates immutable
 151 directories, it is perfectly safe to re-use a directory from a previous
 152 backup.
 153
 154 If not found, the webapi "mkdir-immutable" operation is used to create a new
 155 directory, and an entry is stored in the table.
 156
 157 The comparison operation ignores timestamps and metadata, and pays attention
 158 solely to the file names and contents.
 159
 160 By using a directory-contents hash, the "tahoe backup" command is able to
 161 re-use directories from other places in the backed up data, or from old
 162 backups. This means that renaming a directory and moving a subdirectory to a
 163 new parent both count as "minor changes" and will result in minimal Tahoe
 164 operations and subsequent network traffic (new directories will be created
 165 for the modified directory and all of its ancestors). It also means that you
 166 can perform a backup ("#1"), delete a file or directory, perform a backup
 167 ("#2"), restore it, and then the next backup ("#3") will re-use the
 168 directories from backup #1.
 169
 170 The best case is a null backup, in which nothing has changed. This will
 171 result in minimal network bandwidth: one directory read and two modifies. The
 172 Archives/ directory must be read to locate the latest backup, and must be
 173 modified to add a new snapshot, and the Latest/ directory will be updated to
 174 point to that same snapshot.
 175