docs/technical-overview.rst

   1 .. _tech_design_overview:
   2
   3 Technical Overview
   4 ==================
   5
   6 Datastores
   7 ----------
   8
   9 A Datastore is the logical place where :ref:`Backup Snapshots
  10 <term_backup_snapshot>` and their chunks are stored. Snapshots consist of a
  11 manifest, blobs, and dynamic- and fixed-indexes (see :ref:`terms`), and are
  12 stored in the following directory structure:
  13
  14  <datastore-root>/<type>/<id>/<time>/
  15
  16 The deduplication of datastores is based on reusing chunks, which are
  17 referenced by the indexes in a backup snapshot. This means that multiple
  18 indexes can reference the same chunks, reducing the amount of space needed to
  19 contain the data (even across backup snapshots).
  20
  21 Snapshots
  22 ---------
  23
  24 A Snapshot is the collection of manifest, blobs and indexes that represent
  25 a backup. When a client creates a snapshot, it can upload blobs (single files
  26 which are not chunked, e.g. the client log), or one or more indexes
  27 (fixed or dynamic).
  28
  29 When uploading an index, the client first has to read the source data, chunk it
  30 and send the data as chunks with their identifying checksum to the server.
  31
  32 If there is a previous Snapshot in the backup group, the client can first
  33 download the chunk list of the previous Snapshot. If it detects a chunk that
  34 already exists on the server, it can send only the checksum instead of data
  35 and checksum. This way the actual upload of Snapshots is incremental while
  36 each Snapshot references all chunks and is thus a full backup.
  37
  38 After uploading all data, the client has to signal to the server that the
  39 backup is finished. If that is not done before the connection closes, the
  40 server will remove the unfinished snapshot.
  41
  42 Chunks
  43 ------
  44
  45 A chunk is some (possibly encrypted) data with a CRC-32 checksum at the end and
  46 a type marker at the beginning. It is identified by the SHA-256 checksum of its
  47 content.
  48
  49 To generate such chunks, backup data is split either into fixed-size or
  50 dynamically sized chunks. The same content will be hashed to the same checksum.
  51
  52 The chunks of a datastore are found in
  53
  54  <datastore-root>/.chunks/
  55
  56 This chunk directory is further subdivided by the first four bytes of the
  57 chunk's checksum, so a chunk with the checksum
  58
  59  a342e8151cbf439ce65f3df696b54c67a114982cc0aa751f2852c2f7acc19a8b
  60
  61 lives in
  62
  63  <datastore-root>/.chunks/a342/
  64
  65 This is done to reduce the number of files per directory, as having many files
  66 per directory can be bad for file system performance.
  67
  68 These chunk directories ('0000'-'ffff') will be preallocated when a datastore
  69 is created.
  70
  71 Fixed-Sized Chunks
  72 ^^^^^^^^^^^^^^^^^^
  73
  74 For block based backups (like VMs), fixed-sized chunks are used. The content
  75 (disk image), is split into chunks of the same length (typically 4 MiB).
  76
  77 This works very well for VM images, since the file system on the guest most
  78 often tries to allocate files in contiguous pieces, so new files get new
  79 blocks, and changing existing files changes only their own blocks.
  80
  81 As an optimization, VMs in `Proxmox VE`_ can make use of 'dirty bitmaps', which
  82 can track the changed blocks of an image. Since these bitmaps are also a
  83 representation of the image split into chunks, there is a direct relation
  84 between the dirty blocks of the image and chunks which need to be uploaded.
  85 Thus, only modified chunks of the disk need to be uploaded to a backup.
  86
  87 Since the image is always split into chunks of the same size, unchanged blocks
  88 will result in identical checksums for those chunks, so such chunks do not need
  89 to be backed up again. This way storage snapshots are not needed to find the
  90 changed blocks.
  91
  92 For consistency, `Proxmox VE`_ uses a QEMU internal snapshot mechanism, that
  93 does not rely on storage snapshots either.
  94
  95 Dynamically Sized Chunks
  96 ^^^^^^^^^^^^^^^^^^^^^^^^
  97
  98 When working with file-based systems rather than block-based systems,
  99 using fixed-sized chunks is not a good idea, since every time a file
 100 would change in size, the remaining data would be shifted around,
 101 resulting in many chunks changing and the amount of deduplication being reduced.
 102
 103 To improve this, `Proxmox Backup`_ Server uses dynamically sized chunks
 104 instead. Instead of splitting an image into fixed sizes, it first generates a
 105 consistent file archive (:ref:`pxar <pxar-format>`) and uses a rolling hash
 106 over this on-the-fly generated archive to calculate chunk boundaries.
 107
 108 We use a variant of Buzhash which is a cyclic polynomial algorithm. It works
 109 by continuously calculating a checksum while iterating over the data, and on
 110 certain conditions, it triggers a hash boundary.
 111
 112 Assuming that most files on the system that is to be backed up have not
 113 changed, eventually the algorithm triggers the boundary on the same data as a
 114 previous backup, resulting in chunks that can be reused.
 115
 116 Encrypted Chunks
 117 ^^^^^^^^^^^^^^^^
 118
 119 Encrypted chunks are a special case. Both fixed- and dynamically sized chunks
 120 can be encrypted, and they are handled in a slightly different manner than
 121 normal chunks.
 122
 123 The hashes of encrypted chunks are calculated not with the actual (encrypted)
 124 chunk content, but with the plain-text content, concatenated with the encryption
 125 key. This way, two chunks with the same data but encrypted with different keys
 126 generate two different checksums and no collisions occur for multiple
 127 encryption keys.
 128
 129 This is done to speed up the client part of the backup, since it only needs to
 130 encrypt chunks that are actually getting uploaded. Chunks that exist already in
 131 the previous backup, do not need to be encrypted and uploaded.
 132
 133 Caveats and Limitations
 134 -----------------------
 135
 136 Notes on Hash Collisions
 137 ^^^^^^^^^^^^^^^^^^^^^^^^
 138
 139 Every hashing algorithm has a chance to produce collisions, meaning two (or
 140 more) inputs generate the same checksum. For SHA-256, this chance is
 141 negligible. To calculate the chances of such a collision, one can use the ideas
 142 of the 'birthday problem' from probability theory. For big numbers, this is
 143 actually unfeasible to calculate with regular computers, but there is a good
 144 approximation:
 145
 146 .. math::
 147
 148  p(n, d) = 1 - e^{-n^2/(2d)}
 149
 150 Where `n` is the number of tries, and `d` is the number of possibilities.
 151 For a concrete example, lets assume a large datastore of 1 PiB and an average
 152 chunk size of 4 MiB. That means :math:`n = 268435456` tries, and :math:`d =
 153 2^{256}` possibilities. Inserting those values in the formula from earlier you
 154 will see that the probability of a collision in that scenario is:
 155
 156 .. math::
 157
 158  3.1115 * 10^{-61}
 159
 160 For context, in a lottery game of guessing 6 numbers out of 45, the chance to
 161 correctly guess all 6 numbers is only :math:`1.2277 * 10^{-7}`. This means the
 162 chance of a collision is about the same as winning 13 such lottery games *in a
 163 row*.
 164
 165 In conclusion, it is extremely unlikely that such a collision would occur by
 166 accident in a normal datastore.
 167
 168 Additionally, SHA-256 is prone to length extension attacks, but since there is
 169 an upper limit for how big the chunks are, this is not a problem, because a
 170 potential attacker cannot arbitrarily add content to the data beyond that
 171 limit.
 172
 173 File-Based Backup
 174 ^^^^^^^^^^^^^^^^^
 175
 176 Since dynamically sized chunks (for file-based backups) are created on a custom
 177 archive format (pxar) and not over the files directly, there is no relation
 178 between the files and chunks. This means that the Proxmox Backup Client has to
 179 read all files again for every backup, otherwise it would not be possible to
 180 generate a consistent, independent pxar archive where the original chunks can be
 181 reused. Note that in spite of this, only new or changed chunks will be uploaded.
 182
 183 Verification of Encrypted Chunks
 184 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 185
 186 For encrypted chunks, only the checksum of the original (plaintext) data is
 187 available, making it impossible for the server (without the encryption key) to
 188 verify its content against it. Instead only the CRC-32 checksum gets checked.
 189
 190 Troubleshooting
 191 ---------------
 192
 193 Index files(*.fidx*, *.didx*) contain information about how to rebuild a file.
 194 More precisely, they contain an ordered list of references to the chunks that
 195 the original file was split into. If there is something wrong with a snapshot,
 196 it might be useful to find out which chunks are referenced in it, and check
 197 whether they are present and intact. The ``proxmox-backup-debug`` command-line
 198 tool can be used to inspect such files and recover their contents. For example,
 199 to get a list of the referenced chunks of a *.fidx* index:
 200
 201 .. code-block:: console
 202
 203     # proxmox-backup-debug inspect file drive-scsi0.img.fidx
 204
 205 The same command can be used to inspect *.blob* files. Without the ``--decode``
 206 parameter, just the size and the encryption type, if any, are printed. If
 207 ``--decode`` is set, the blob file is decoded into the specified file ('-' will
 208 decode it directly to stdout).
 209
 210 The following example would print the decoded contents of
 211 `qemu-server.conf.blob`. If the file you're trying to inspect is encrypted, a
 212 path to the key file must be provided using ``--keyfile``.
 213
 214 .. code-block:: console
 215
 216     # proxmox-backup-debug inspect file qemu-server.conf.blob --decode -
 217
 218 You can also check in which index files a specific chunk file is referenced
 219 with:
 220
 221 .. code-block:: console
 222
 223     # proxmox-backup-debug inspect chunk b531d3ffc9bd7c65748a61198c060678326a431db7eded874c327b7986e595e0 --reference-filter /path/in/a/datastore/directory
 224
 225 Here ``--reference-filter`` specifies where index files should be searched. This
 226 can be an arbitrary path. If, for some reason, the filename of the chunk was
 227 changed, you can explicitly specify the digest using ``--digest``. By default, the
 228 chunk filename is used as the digest to look for. If no ``--reference-filter``
 229 is specified, it will only print the CRC and encryption status of the chunk. You
 230 can also decode chunks, by setting the ``--decode`` flag. If the chunk is
 231 encrypted, a ``--keyfile`` must be provided, in order to decode it.
 232
 233 Restore without a Running Proxmox Backup Server
 234 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 235
 236 It's possible to restore specific files from a snapshot, without a running
 237 `Proxmox Backup`_ Server instance, using the ``recover`` subcommand, provided
 238 you have access to the intact index and chunk files. Note that you also need the
 239 corresponding key file if the backup was encrypted.
 240
 241 .. code-block:: console
 242
 243     # proxmox-backup-debug recover index drive-scsi0.img.fidx /path/to/.chunks
 244
 245 In the above example, the `/path/to/.chunks` argument is the path to the
 246 directory that contains the chunks, and `drive-scsi0.img.fidx` is the index file
 247 of the file you'd like to restore. Both paths can be absolute or relative. With
 248 ``--skip-crc``, it's possible to disable the CRC checks of the chunks. This
 249 will speed up the process slightly and allow for trying to restore (partially)
 250 corrupt chunks. It's recommended to always try without the skip-CRC option
 251 first.
 252