diff options
author | n-peugnet <n.peugnet@free.fr> | 2021-11-11 00:40:04 +0100 |
---|---|---|
committer | n-peugnet <n.peugnet@free.fr> | 2021-11-11 00:43:06 +0100 |
commit | 02ac5aa70b8ffd203093c4e33690012234b2a037 (patch) | |
tree | ea104b2a2373a8c854fb93dd6b27d39dbafffbde /pdf | |
parent | 5eab2ecb4525b0bc7a1f69be10e2ee329ad6789d (diff) | |
download | dna-backup-02ac5aa70b8ffd203093c4e33690012234b2a037.tar.gz dna-backup-02ac5aa70b8ffd203093c4e33690012234b2a037.zip |
encodage delta + un max de refs
Diffstat (limited to 'pdf')
-rw-r--r-- | pdf/doc.bib | 52 | ||||
-rw-r--r-- | pdf/doc.tex | 28 |
2 files changed, 75 insertions, 5 deletions
diff --git a/pdf/doc.bib b/pdf/doc.bib index bd07b54..b1799f3 100644 --- a/pdf/doc.bib +++ b/pdf/doc.bib @@ -81,6 +81,42 @@ publisher={Center for Research in Computing Technology, Harvard University} } +@misc{rfc1950, + series={Request for Comments}, + number=1950, + howpublished={RFC 1950}, + publisher={RFC Editor}, + doi={10.17487/RFC1950}, + url={https://rfc-editor.org/rfc/rfc1950.txt}, + author={L. Peter Deutsch and Jean-loup Gailly}, + title={{ZLIB Compressed Data Format Specification version 3.3}}, + pagetotal=11, + year=1996, + month=may +} + +@misc{rfc1951, + series={Request for Comments}, + number=1951, + howpublished={RFC 1951}, + publisher={RFC Editor}, + doi={10.17487/RFC1951}, + url={https://rfc-editor.org/rfc/rfc1951.txt}, + author={L. Peter Deutsch}, + title={{DEFLATE Compressed Data Format Specification version 1.3}}, + pagetotal=17, + year=1996, + month=may + } + +@misc{percival2003naive, + title={Na{\i}ve differences of executable code}, + author={Percival, Colin}, + howpublished={\url{http://www.daemonology.net/papers/bsdiff.pdf}}, + year={2003}, + publisher={Citeseer} +} + @inproceedings{zhang2006hptfs, title={Hptfs: A high performance tape file system}, author={Zhang, Xianbo and Du, David and Hughes, Jim and Kavuri, Ravi and StorageTek, Sun}, @@ -97,6 +133,22 @@ note={[Online; accessed: 2021-11-04]} } +@misc{hipp2006fdelta, + title={Fossil Delta Format}, + author={D. Richard Hipp}, + howpublished={\url{https://fossil-scm.org/home/doc/trunk/www/delta_format.wiki}}, + year={2006}, + note={[Online; accessed: 2021-11-10]} +} + +@misc{chromium2012courgette, + title={Software Updates: Courgette}, + author={The Chromium Projects}, + howpublished={\url{https://www.chromium.org/developers/design-documents/software-updates-courgette}}, + year={2012}, + note={[Online; accessed: 2021-11-10]} +} + @inproceedings{pease2010linear, title={The linear tape file system}, author={Pease, David and Amir, Arnon and Real, Lucas Villa and Biskeborn, Brian and Richmond, Michael and Abe, Atsushi}, diff --git a/pdf/doc.tex b/pdf/doc.tex index c5e6eb7..a153a76 100644 --- a/pdf/doc.tex +++ b/pdf/doc.tex @@ -838,9 +838,14 @@ Dans ce cas l'amplification de lecture restera contenue et bien moindre que si on avait eu à restaurer la totalité de la version. -\chapter{Détails d'implémentation} +\chapter{Détails techniques} + +\section{Spécificités d'implémentation} L'implémentation de DNA-Backup présentée ici a été réalisée sous la forme d'un programme en \ac{cli} codé en Go. + +\subsection{Choix techniques} + Un certain nombre de choix techniques ont été dictées par le temps limité et la disponibilité de librairies efficaces. Notamment, l'encodeur par défaut du langage Go : \verb|gob|, a été utilisé à maintes reprises, du fait de sa simplicité de mise en œuvre @@ -852,12 +857,25 @@ il n'existe que très peu d'implémentations dans d'autres langages. De la même manière, les algorithmes de compression et d'encodage delta utilisés dans DNA-Backup n'ont pour le moment pas été choisis en fonction de leur efficacité, mais plutôt pour des raisons de facilité. -En ce qui concerne la compression, l'utilisation de \emph{Zlib} reste intéressante, +En ce qui concerne la compression, l'utilisation de \emph{Zlib}~\cite{rfc1950} basé sur DEFLATE~\cite{rfc1951} reste intéressante, car il s'agit de l'algorithme utilisé par les autres systèmes auxquels nous allons nous comparer par la suite. -Ainsi les résultats ne seront pas biaisés par l'utilisation d'un algorithme plus efficace. - -% \section{Détails à propos du repo} +Ainsi les résultats ne seront pas biaisés par l'utilisation d'un algorithme plus performant que les autres. + +Deux algorithmes ont été testés pour l'encodage delta. +Tout d'abord \verb|bsdiff|~\cite{percival2003naive} qui est la référence actuelle +quand il s'agit de produire des différences binaires d'une taille minimale. +C'était par exemple l'algorithme utilisé par le projet Chromium pour distribuer ses mises-à-jour, +avant qu'ils ne décident d'en créer un parfaitement adapté à leur besoin~\cite{chromium2012courgette}. +Cependant, \verb|bsdiff| est trop spécifique aux données binaires exécutables, +ce qui en fait un algorithme trop peu généraliste. +De plus, son fonctionnement inclut une passe de compression sur la différence qu'il crée, +laquelle est redondante avec celle que nous appliquons nous-même sur les données que nous stockons. +Nous choisissons finalement d'utiliser \verb|fdelta| le format de différence utilisé par le gestionnaire de version Fossil~\cite{hipp2006fdelta}. +Celui-ci étant plus généraliste et produisant des différences d'une taille suffisamment réduite, +tout en étant explicitement prévu pour être ensuite compressé avec l'algorithme de notre choix. + +\subsection{Structures de données du repo} % Le fichier *files* correspond au métadonnées de l'arborescence du système de fichier. % C'est là que sont stockés les métadonnées des fichiers (comme par exemple leur nom et leur taille) |