Add a few items to the TODO list.
[cumulus.git] / doc / implementation.txt
1            Cumulus: Efficient Filesystem Backup to the Cloud
2                         Implementation Overview
3
4 HIGH-LEVEL OVERVIEW
5 ===================
6
7 There are two different classes of data stored, typically in different
8 directories:
9
10 The SNAPSHOT directory contains the actual backup contents.  It consists
11 of segment data (typically in compressed/encrypted form, one segment per
12 file) as well as various small per-snapshot files such as the snapshot
13 descriptor files (which names each snapshot and tells where to locate
14 the data for it) and checksum files (which list checksums of segments
15 for quick integrity checking).  The snapshot directory may be stored on
16 a remote server.  It is write-only, in the sense that data does not need
17 to be read from the snapshot directory to create a new snapshot, and
18 files in it are immutable once created (they may be deleted if they are
19 no longer needed, but file contents are never changed).
20
21 The LOCAL DATABASE contains indexes used during the backup process.
22 Files here keep track of what information is known to be stored in the
23 snapshot directory, so that new snapshots can appropriate re-use data.
24 The local database, as its name implies, should be stored somewhere
25 local, since random access (read and write) will be required during the
26 backup process.  Unlike the snapshot directory, files here are not
27 immutable.
28
29 Only the data stored in the snapshot directory is required to restore a
30 snapshot.  The local database does not need to be backed up (stored at
31 multiple separate locations, etc.).  The contents of the local database
32 can be rebuilt (at least in theory) from data in the snapshot directory
33 and the local filesystem; it is expected that tools will eventually be
34 provided to do so.
35
36 The format of data in the snapshot directory is described in format.txt.
37 The format of data in the local database is more fluid and may evolve
38 over time.  The current structure of the local database is described in
39 this document.
40
41
42 LOCAL DATABASE FORMAT
43 =====================
44
45 The local database directory currently contains two files:
46 localdb.sqlite and a statcache file.  (Actually, two types of files.  It
47 is possible to create snapshots using different schemes, and have them
48 share the same local database directory.  In this case, there will still
49 be one localdb.sqlite file, but one statcache file for each backup
50 scheme.)
51
52 Each statcache file is a plain text file, with a format similar to the
53 file metadata listing used in the snapshot directory.  The purpose of
54 the statcache file is to speed the backup process by making it possible
55 to determine if a file has changed since the previous snapshot by
56 comparing the results of a stat() system call with the data in the
57 statcache file, and if the file is unchanged, providing the checksum and
58 list of data blocks used to previously store the file.  The statcache
59 file is rewritten each time a snapshot is taken, and can safely be
60 deleted (with the only major side effect being that the first backups
61 after doing so will progress much more slowly).
62
63 localdb.sqlite is an SQLite database file, which is used for indexing
64 objects stored in the snapshot directory and various other purposes.
65 The database schema is contained in the file schema.sql in the Cumulus
66 source.  Among the data tracked by localdb.sqlite:
67
68   - A list of segments stored in the snapshot directory.  This might not
69     include all segments (segments belonging to old snapshots might be
70     removed), but for correctness all segments listed in the local
71     database must exist in the snapshot directory.
72
73   - A block index which tracks objects in the snapshot directory used to
74     store file data.  It is indexed by block checksum, and so can be
75     used while generating a snapshot to determine if a just-read block
76     of data is already stored in the snapshot directory, and if so how
77     to name it.
78
79   - A list of recent snapshots, together with a list of the objects from
80     the block index they reference.
81
82 The localdb SQL database is central to data sharing and segment
83 cleaning.  When creating a new snapshot, information about the new
84 snapshot and the blocks is uses (including any new ones) is written to
85 the database.  Using the database, separate segment cleaning processes
86 can determine how much data in various segments is still live, and
87 determine which segments are best candidates for cleaning.  Cleaning is
88 performed by updating the database to mark objects in the cleaned
89 segments as unavailable for use in future snapshots; when the backup
90 process next runs, any files that would use these expired blocks instead
91 have a copy of the data written to a new segment.