From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <Lubomir.Apostolov@directique.com>
Received: from firstgate.proxmox.com (firstgate.proxmox.com [212.224.123.68])
 (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)
 key-exchange X25519 server-signature RSA-PSS (2048 bits))
 (No client certificate requested)
 by lists.proxmox.com (Postfix) with ESMTPS id 068726AE35
 for <pbs-devel@lists.proxmox.com>; Wed,  9 Dec 2020 17:27:28 +0100 (CET)
Received: from firstgate.proxmox.com (localhost [127.0.0.1])
 by firstgate.proxmox.com (Proxmox) with ESMTP id E896C13A64
 for <pbs-devel@lists.proxmox.com>; Wed,  9 Dec 2020 17:26:57 +0100 (CET)
Received: from mail.directique.com (mail.directique.com [176.31.91.54])
 (using TLSv1 with cipher AES256-SHA (256/256 bits))
 (No client certificate requested)
 by firstgate.proxmox.com (Proxmox) with ESMTPS id D44B913A58
 for <pbs-devel@lists.proxmox.com>; Wed,  9 Dec 2020 17:26:55 +0100 (CET)
Received: from SCOM4.directique.net ([::1]) by SCOM4.directique.net ([::1])
 with mapi id 14.03.0487.000; Wed, 9 Dec 2020 17:23:46 +0100
From: Lubomir Apostolov <Lubomir.Apostolov@directique.com>
To: Proxmox Backup Server development discussion <pbs-devel@lists.proxmox.com>
Thread-Topic: [pbs-devel] [PATCH proxmox-backup] docs: explain some
 technical details about datastores/chunks
Thread-Index: AQHWzj+qXSxQS5+MkEKI9cwLvuZDLKnu7UEg
Date: Wed, 9 Dec 2020 16:23:25 +0000
Message-ID: <718D0AF11703FA4C85B0535448A05610038195BAB5@SCOM4.directique.net>
References: <20201209152553.8752-1-d.csapak@proxmox.com>
In-Reply-To: <20201209152553.8752-1-d.csapak@proxmox.com>
Accept-Language: fr-FR, en-US
Content-Language: fr-FR
X-MS-Has-Attach: 
X-MS-TNEF-Correlator: 
x-originating-ip: [90.46.0.213]
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-SPAM-LEVEL: Spam detection results:  0
 KAM_DMARC_STATUS 0.01 Test Rule for DKIM or SPF Failure with Strict Alignment
 SPF_HELO_NONE           0.001 SPF: HELO does not publish an SPF Record
 SPF_PASS               -0.001 SPF: sender matches SPF record
 URIBL_BLOCKED 0.001 ADMINISTRATOR NOTICE: The query to URIBL was blocked. See
 http://wiki.apache.org/spamassassin/DnsBlocklists#dnsbl-block for more
 information. [proxmox.com]
Subject: Re: [pbs-devel] [PATCH proxmox-backup] docs: explain some technical
 details about datastores/chunks
X-BeenThere: pbs-devel@lists.proxmox.com
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Proxmox Backup Server development discussion
 <pbs-devel.lists.proxmox.com>
List-Unsubscribe: <https://lists.proxmox.com/cgi-bin/mailman/options/pbs-devel>, 
 <mailto:pbs-devel-request@lists.proxmox.com?subject=unsubscribe>
List-Archive: <http://lists.proxmox.com/pipermail/pbs-devel/>
List-Post: <mailto:pbs-devel@lists.proxmox.com>
List-Help: <mailto:pbs-devel-request@lists.proxmox.com?subject=help>
List-Subscribe: <https://lists.proxmox.com/cgi-bin/mailman/listinfo/pbs-devel>, 
 <mailto:pbs-devel-request@lists.proxmox.com?subject=subscribe>
X-List-Received-Date: Wed, 09 Dec 2020 16:27:28 -0000

Hi,

After reading https://bugzilla.proxmox.com/show_bug.cgi?id=3D3138 and your =
mail, I'd like to discuss the following statement :
"we have to read all files again in every backup" for both cases - file and=
 image based backup.

The image-backup seems simpler - fixed-size chunks.=20
PBS should be able to link a snapshot with it's backup, and backup only dif=
ferencies with parent snapshot as for example zfs send/recv works.
Every backup knows the chunk order and chunk size, so it can map every chun=
k to the original image extents.
The snapshot differences gives extents, which PBS can map to overlapped chu=
nks, and send only those chunks, while referencing unchanged chunks from pr=
evious backup chunks list.

The variable-size chunks based on files needs another mapping between chunk=
s and filenames.=20
The rolling hash over the data may be linked a list containing the filename=
s inside, and then the snapshot diff containing files can flag the chunks t=
o be saved.

So where's the catch ?

Best regards,
Lubomir Apostolov

-----Message d'origine-----
De=A0: pbs-devel [mailto:pbs-devel-bounces@lists.proxmox.com] De la part de=
 Dominik Csapak
Envoy=E9=A0: mercredi 9 d=E9cembre 2020 16:26
=C0=A0: pbs-devel@lists.proxmox.com
Objet=A0: [pbs-devel] [PATCH proxmox-backup] docs: explain some technical d=
etails about datastores/chunks

adds explanations for:
* what datastores are
* their relation with snapshots/chunks
* basic information about chunk directory structures
* fixed-/dynamically-sized chunks
* special handling of encrypted chunks
* hash collision probability
* limitation of file-based backups

Signed-off-by: Dominik Csapak <d.csapak@proxmox.com>
---
 docs/index.rst              |   1 +
 docs/technical-overview.rst | 152 ++++++++++++++++++++++++++++++++++++
 docs/terminology.rst        |   3 +
 3 files changed, 156 insertions(+)
 create mode 100644 docs/technical-overview.rst

diff --git a/docs/index.rst b/docs/index.rst
index fffcb4fd..f3e6bf0c 100644
--- a/docs/index.rst
+++ b/docs/index.rst
@@ -33,6 +33,7 @@ in the section entitled "GNU Free Documentation License".
    pve-integration.rst
    pxar-tool.rst
    sysadmin.rst
+   technical-overview.rst
    faq.rst
=20
 .. raw:: latex
diff --git a/docs/technical-overview.rst b/docs/technical-overview.rst
new file mode 100644
index 00000000..20f937bd
--- /dev/null
+++ b/docs/technical-overview.rst
@@ -0,0 +1,152 @@
+Technical Overview
+=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
+
+.. _technical_overview:
+
+Datastores
+----------
+
+A Datastore is the logical place where :ref:`Backup Snapshots <backup_snap=
shot>`
+and their chunks are stored. Snapshots consist of a manifest, blobs,
+dynamic- and fixed-indexes (see :ref:`terminology`), and are stored in the=
 following directory structure:
+
+ <datastore-root>/<type>/<id>/<time>/
+
+The indexes contained in a snapshot reference chunks on which the deduplic=
ation
+of datastores is based.
+
+Chunks
+------
+
+A chunk is some (sometimes encrypted) data with a CRC-32 checksum at
+the end and a type marker at the beginning. It is identified by a
+SHA-256 checksum of its content.
+
+To generate such chunks, backup data is split either into fixed-size or
+dynamically-sized chunks. The same content will be hashed to the same
+checksum.
+
+The chunks of a datastore are found in
+
+ <datastore-root>/.chunks/
+
+This chunk directory is further subdivided by the first four byte of the
+chunks checksum, so the chunk with the checksum
+
+ a342e8151cbf439ce65f3df696b54c67a114982cc0aa751f2852c2f7acc19a8b
+
+lives in
+
+ <datastore-root>/.chunks/a342/
+
+This is done to reduce the number of files per directory, as having
+many files per directory can be bad for file system performance.
+
+These chunk directories('0000'-'ffff') will be preallocated when the datas=
tore is
+created.
+
+Fixed-sized Chunks
+^^^^^^^^^^^^^^^^^^
+
+For block based backups (like VMs), fixed-sized chunks are used. The conte=
nt
+(disk image), is split into chunks of the same length (typically 4 MiB).
+
+This works very well for VM images, since the file system on the guest,
+most often tries to allocate files in contiguous pieces, so new files get
+new blocks, and changing existing files changes only their own blocks.
+
+As an optimization, VMs in `Proxmox VE`_ can make use of 'dirty bitmaps',
+which can track the changed blocks of an image. Since these bitmap
+are also a representation of the image split into chunks, we have
+a direct relation between dirty blocks of the image and chunks we have
+to upload, so only touched chunks of the disk have to be uploaded for a ba=
ckup.
+
+Dynamically-sized Chunks
+^^^^^^^^^^^^^^^^^^^^^^^^
+
+If does not want to backup block-based systems but file-based systems,
+using fixed-sized chunks is not a good idea, since every time a file
+would change in size, the remaining data gets shifted around and this
+would result in many chunks changing, reducing the effect of deduplication=
.
+
+To improve this, `Proxmox Backup`_ Server uses dynamically-sized chunks
+instead. Instead of splitting an image into fixed sizes, it generates
+a consistent file archive and uses a rolling hash over the data
+to calculate chunk boundaries. We use a variant of Buzhash which
+is a cyclic polynomial algorithm.
+
+It works by continuously calculating a hashsum while iterating over the
+data, and on certain conditions it triggers a hash boundary.
+
+Assuming that there is not a change in every file of the to system to
+be backed up, eventually the algorithm triggers the boundary on the
+same data as a previous backup, resulting in a chunk that can be reused.
+
+Encrypted Chunks
+^^^^^^^^^^^^^^^^
+
+A special case are encrypted chunks. Both fixed- and dynamically-sized
+chunks can be encrypted, and their handling is slightly different
+from normal chunks.
+
+The hash of encrypted chunks are calculated not with the actual (encrypted=
)
+chunk content, but with the plaintext content concatenated with
+the encryption key. This way, two chunks of the same data encrypted with
+different keys generate two different checksums and no collisions occur fo=
r
+multiple encryption keys.
+
+This is done to speed up the client part of the backup, since it only need=
s
+to encrypt chunks that are actually getting uploaded and chunks that exist
+already in the previous backup, do not need to be encrypted and uploaded.
+
+Caveats and Limitations
+-----------------------
+
+Notes on hash collisions
+^^^^^^^^^^^^^^^^^^^^^^^^
+Every hash has a chance to produce collisions, meaning two (or more) input=
s
+generating the same hashsum. For SHA-256, this chance is negligible.
+To calculate such a collision, one can use the ideas of the 'birthday prob=
lem'
+from probability theory. For big numbers, this is actually not feasible to
+calculate with normal computers, but there is a good approximation:
+
+.. math::
+
+ p(n, d) =3D 1 - e^{-n^2/(2d)}
+
+Where `n` is the number of tries, and `d` is the number of possibilities.
+So for example, if we assume a large datastore of 1 PiB, and an average ch=
unk
+size of 4 MiB, we have :math:`n =3D 268435456` tries, and :math:`d =3D 2^{=
256}`
+possibilities.  Using the above formula we get that the probability of a
+collision in that scenario is:
+
+.. math::
+
+ 3.1115 * 10^{-61}
+
+For context, in a lottery game of 6 of 45, the chance to correctly guess a=
ll
+6 numbers is only :math:`1.2277 * 10^{-7}`.
+
+So it is extremely unlikely that such a collision would occur by accident
+in a normal datastore.
+
+Additionally, SHA-256 is prone to length extension attacks, but since
+there is an upper limit for how big the chunk sizes are, this is not
+problem, since a potential attacker cannot arbitrarily add the content.
+
+
+File-based Backup
+^^^^^^^^^^^^^^^^^
+
+Since there is no relation between files and dynamically-sized chunks,
+we have to read all files again in every backup. Otherwise it would not be
+possible to generate a format where the original chunks can be reused.
+
+Verification of encrypted chunks
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+For encrypted chunks, only the checksum of the original (plaintext) data
+is available, making it impossible for the server (without the encryption =
key),
+to verify its content against it. Instead only the CRC-32 checksum gets ch=
ecked.
+
+
diff --git a/docs/terminology.rst b/docs/terminology.rst
index 89ec7646..3eff9780 100644
--- a/docs/terminology.rst
+++ b/docs/terminology.rst
@@ -1,3 +1,5 @@
+.. _terminology:
+
 Terminology
 =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
=20
@@ -99,6 +101,7 @@ Backup Group
 The tuple ``<type>/<ID>`` is called a backup group. Such a group
 may contain one or more backup snapshots.
=20
+.. _backup_snapshot:
=20
 Backup Snapshot
 ---------------
--=20
2.20.1



_______________________________________________
pbs-devel mailing list
pbs-devel@lists.proxmox.com
https://lists.proxmox.com/cgi-bin/mailman/listinfo/pbs-devel