aboutsummaryrefslogtreecommitdiff
path: root/pdf
diff options
context:
space:
mode:
authorn-peugnet <n.peugnet@free.fr>2021-10-22 15:17:14 +0200
committern-peugnet <n.peugnet@free.fr>2021-10-22 15:24:23 +0200
commit67079bf2007e62ce6a8527fe5298b61d0dd9bc75 (patch)
tree516e3604b3099c33e99ab19c66e56a3016fdc8e9 /pdf
parent2906807f4341eef0e23f91356675595c89715490 (diff)
downloaddna-backup-67079bf2007e62ce6a8527fe5298b61d0dd9bc75.tar.gz
dna-backup-67079bf2007e62ce6a8527fe5298b61d0dd9bc75.zip
premier ajout du contenu en LaTeX
Diffstat (limited to 'pdf')
-rw-r--r--pdf/doc.tex426
1 files changed, 422 insertions, 4 deletions
diff --git a/pdf/doc.tex b/pdf/doc.tex
index 33d691c..303cc2a 100644
--- a/pdf/doc.tex
+++ b/pdf/doc.tex
@@ -1,12 +1,12 @@
-\documentclass[a4paper,twocolumn,french]{article}
+\documentclass[a4paper]{article}
% Set page dimentions
\usepackage[margin=22mm]{geometry}
% Packages for french documents
-\usepackage[french]{babel}
-\usepackage[utf8]{inputenc}
-\usepackage[T1]{fontenc}
+\usepackage[french]{babel} % latex rules for french words
+\usepackage[utf8]{inputenc} % UTF-8 encoding for special chars
+\usepackage[T1]{fontenc} % T1 font for smooth render of special chars
% Define some colors
\usepackage{color}
@@ -37,6 +37,14 @@
\usepackage{graphicx}
\graphicspath{ {img} }
+% Complex tables
+\usepackage{multirow,tabularx}
+% Ragged right auto-span columns
+\usepackage{array}
+\newcolumntype{R}{>{\raggedright\arraybackslash}X}
+
+%--------------------------------------- Content ---------------------------------------%
+
\title{DNA-Backup}
\date{Octobre 2021}
@@ -49,6 +57,416 @@
\tableofcontents
+\section{Introduction}
+
+Le système part du principe qu'on a une copie des données stockées en
+ADN sur un support de stockage classique : le \emph{repo}.
+
+\begin{verbatim}
+ +----------------------------------+
+ | +---------+ +---------+ | +-----------+
+ | | | | | | | |
+ | | Source |--------->| Repo |----------->| DNA-Drive |
+ | | | COMMIT | | | SYNTHESE | |
+ | +---------+ +---------+ | +-----------+
+ | |
+ | Ordinateur |
+ +----------------------------------+
+\end{verbatim}
+
+La structure du \emph{repo} est la suivante :
+
+\begin{verbatim}
+repo/
++-- 00000/
+| +-- chunks/
+| | +-- 000000000000000
+| | +-- 000000000000001
+| | +-- 000000000000002
+| | +-- 000000000000003
+| +-- files
+| +-- hashes
+| +-- recipe
++-- 00001/
+ +-- chunks/
+ | +-- 000000000000000
+ | +-- 000000000000001
+ +-- files
+ +-- hashes
+ +-- recipe
+\end{verbatim}
+
+Pour un repo d'une taille totale de 401 Mio :
+
+\begin{verbatim}
+/tmp/test-1/00000/recipe 5076011 (1.20%)
+/tmp/test-1/00000/files 24664 (0.06%)
+/tmp/test-1/00000/hashes 3923672 (0.93%)
+/tmp/test-1/00000/chunks 412263137 (97.8%)
+/tmp/test-1/00000 421287604 ( 100%)
+\end{verbatim}
+
+\begin{itemize}
+\item
+ On considère que le \emph{repo} est toujours présent lors d'une
+ écriture (\emph{commit}).
+\item
+ Le \emph{repo} peut être reconstruit à partir des données présentes
+ dans le \emph{DNA-Drive}.
+\item
+ Les \emph{hashes} ne sont pas écrits en ADN, car ils peuvent être
+ reconstruits à partir des données des \emph{chunks}.
+\item
+ L'ensemble des données écrites en ADN sont compressées, pour le moment
+ via \emph{ZLib}.
+\item
+ Les métadonnées sont stockées de manière incrémentale, chaque version
+ stocke donc ses métadonnées sous la forme de delta par rapport à la
+ version précédente.
+\end{itemize}
+
+On imagine le \emph{DNA-Drive} comme un segment de \emph{pools} :
+
+\begin{verbatim}
+ +---+---+---+---+---+---------+---+---+---+
+ | 0 | 1 | 2 | 3 | 4 |--> <--| 93| 94| 95|
+ +---+---+---+---+---+---------+---+---+---+
+|versions| chunks | | metadata |
+ (recipe+files)
+\end{verbatim}
+
+\subsection{Algorithme du commit}
+
+\begin{enumerate}
+\item
+ Chargement des métadonnées du \emph{repo} afin de reconstruire en
+ mémoire l'état de la dernière version :
+
+ \begin{itemize}
+ \item
+ Reconstruction de la \emph{recipe} à partir des deltas de chaque
+ version.
+ \item
+ Reconstruction du listage des fichiers à partir des deltas de chaque
+ version (fichier \emph{files}).
+ \item
+ Reconstruction en mémoire des \emph{maps} de \emph{fingerprints} et
+ de \emph{sketches} à partir des fichiers \emph{hashes} de chaque
+ version.
+ \end{itemize}
+\item
+ Listage des fichiers de la \emph{source}.
+\item
+ Concaténation de l'ensemble des fichiers de la source en un disque
+ virtuel continu.
+\item
+ Lecture du \emph{stream} de ce disque virtuel et découpage en
+ \emph{chunk} (de 8 Kio actuellement).
+\item
+ Pour chaque \emph{chunk} du \emph{stream}~:
+
+ \begin{enumerate}
+ \item
+ Calculer sa \emph{fingerprint} (hash classique), si elle est
+ présente dans la \emph{map} : le stocker de manière dé-dupliquée
+ (sous la forme d'identifiant faisant référence au \emph{chunk}
+ trouvé dans la map).
+ \item
+ Sinon, calculer son \emph{sketch} (hash de ressemblance), s'il est
+ présent dans la \emph{map}, le stocker sous la forme de delta
+ (calcul de sa différence par rapport au \emph{chunk} trouvé dans la
+ map).
+ \item
+ Sinon, le stocker sous la forme de nouveau bloc (ajout de sa
+ \emph{fingerprint} et de son \emph{sketch} dans les \emph{maps} et
+ stockage du contenu complet dans un nouveau \emph{chunk}).
+ \end{enumerate}
+\item
+ Calcul des différences entre la nouvelle version et la précédente pour
+ les métadonnées (\emph{files} et \emph{recipe}) et stockage des deltas
+ ainsi obtenus.
+\end{enumerate}
+
+\subsection{Algorithme du restore}
+
+\begin{enumerate}
+\item
+ Chargement des métadonnées du \emph{repo} afin de reconstruire en
+ mémoire l'état de la dernière version :
+
+ \begin{itemize}
+ \item
+ Reconstruction de la \emph{recipe} à partir des deltas de chaque
+ version.
+ \item
+ Reconstruction du listage des fichiers à partir des deltas de chaque
+ version.
+ \end{itemize}
+\item
+ À partir de la \emph{recipe}, reconstruire le disque virtuel (sous la
+ forme d'un \emph{stream}).
+\item
+ Découper ce \emph{stream} en fonction du listage des fichiers
+ (\emph{files}) et réécrire les données dans les fichiers
+ correspondants dans le répertoire \emph{destination}.
+\end{enumerate}
+
+\subsection{\texorpdfstring{Restaurer sans le
+\emph{repo}}{Restaurer sans le repo}}
+
+\subsubsection{\texorpdfstring{Reconstruction complète du
+\emph{repo}}{Reconstruction complète du repo}}
+
+Il est possible de reconstruire le \emph{repo} en entier en lisant la
+totalité du \emph{DNA-Drive}.
+
+\subsubsection{Restauration de la dernière
+version}
+
+Il est possible de ne restaurer que la dernière version en lisant dans
+un premier temps le \emph{pool} de versions et les quelques \emph{pools}
+de métadonnées (environ 2\% de la totalité des données écrites), puis en
+lisant tous les \emph{pools} contenant des \emph{chunks} référencés par
+la \emph{recipe} de cette version.
+
+\subsubsection{Restauration d'un seul
+fichier}
+
+Il pourrait être possible (pas pour le moment) de ne restaurer qu'un
+seul fichier d'une version en ayant moins de données à lire que pour
+restaurer la version complète.
+
+Pour cela, il faudrait en plus stocker en ADN un mapping \emph{chunk}
+décompressé → \emph{pool} contenant ce \emph{chunk} et ainsi n'avoir à
+lire que les \emph{pools} contenant des \emph{chunks} de ce fichier.
+
+\section{Évaluation de performances}
+
+Le dossier \verb|exp| contient les scripts permettant de reproduire
+les expériences. Les scripts ne sont prévus pour fonctionner que sur
+Linux.
+
+On utilise le dépôt Git du noyau Linux comme base de donnée de test. Il
+s'agit en effet d'une bonne simulation de modification de dossiers, car
+l'historique contient toutes les modifications qui ont été apportées
+petit à petit à l'ensemble des fichiers.
+
+\subsection{Bases de comparaison}
+
+Pour évaluer les performances du système DNA-Backup, quatre autres
+systèmes de stockage versionnés ont été choisis comme base de
+comparaison :
+
+\begin{itemize}
+\item
+ \textbf{Git diffs}
+\item
+ \textbf{Git objects}
+\item
+ \textbf{Targz}
+\item
+ \textbf{Taille réelle}
+\end{itemize}
+
+\subsubsection{Git diffs}
+
+Ce système utilise le delta généré par la commande \verb|git diff|
+pour sauvegarder une nouvelle version. Les données à stocker consistent
+donc en une somme de deltas. Pour restaurer les données, il faut
+appliquer séquentiellement l'ensemble des deltas jusqu'à obtenir l'état
+de la version voulue.
+
+\subsubsection{Git objects}
+
+Ce système nous permet de simuler un système de fichier qui ne serait
+pas autorisé à modifier des données sur le support tout en gardant la
+possibilité de modifier les données. Il s'agit de la manière dont Git
+sauvegarde les données des fichiers d'un dépôt. Le contenu de chaque
+fichier et de chaque dossier est hashé afin d'en obtenir une signature.
+Il est ensuite compressé et stocké sous la forme d'\emph{object}
+immuable, référencé par la signature obtenue. Si un fichier est modifié,
+il produira une signature différente et sera donc stocké sous la forme
+d'un nouvel \emph{object}. Par contre, si deux fichiers ont un contenu
+strictement identique, ils produiront alors la même signature et seront
+donc automatiquement dé-dupliqués. Les dossiers sont également stockés
+en tant qu'\emph{objects}, mais les fichiers qu'ils contiennent sont
+référencés non pas par leur nom, mais par leur signature. La
+modification d'un fichier entrainera donc l'ajout de nouveaux
+\emph{objects} pour l'ensemble des dossiers de la branche contenant ce
+fichier. C'est de cette manière que Git est capable de créer un système
+de fichiers modifiable à partir d'objets immuables.
+
+\subsubsection{Targz}
+
+Une technique d'archivage assez classique à laquelle il peut être
+intéressant de nous comparer est de stocker chaque version en tant
+qu'une nouvelle archive Tar elle-même compressée à l'aide de Gzip. Cette
+technique produit des archives d'une taille très réduite, car la
+compression est appliquée à l'ensemble des fichiers d'un seul coup,
+contrairement à une compression fichier par fichier.
+
+Elle a cependant l'inconvénient de ne pas faire de dé-duplication ni
+d'encodage delta, et ne tire donc pas du tout parti des données déjà
+écrites sur le support.
+
+\subsubsection{Taille réelle}
+
+Cette base de comparaison n'est en réalité pas un système viable. Elle
+correspond à la taille que prend en réalité le dossier \emph{source} au
+moment de la sauvegarde. C'est un indicateur qui permet de se rendre
+compte du poids que prendrait la sauvegarde de multiples versions sans
+aucune déduplication ou compression.
+
+\subsubsection{Tableau récapitulatif}
+
+\noindent
+\begin{tabularx}{\textwidth}{R|R|R|R|R|R}
+
+\textbf{Feature} &
+\textbf{DNA-Backup} &
+\textbf{Git diffs} &
+\textbf{Git objects} &
+\textbf{Targz} &
+\textbf{Taille réelle} \\
+\hline
+
+\multirow{2}{*}{Déduplication} &
+Niveau chunk &
+\multirow{2}{*}{N/A} &
+Niveau fichier &
+\multirow{2}{*}{N/A} &
+\multirow{2}{*}{N/A} \\ \cline{2-2} \cline{4-4}
+& Transversal aux versions & & Transversal aux versions & \\
+\hline
+
+\multirow{2}{*}{Delta-encoding} &
+Niveau chunk &
+Niveau version &
+\multirow{2}{*}{N/A} &
+\multirow{2}{*}{N/A} &
+\multirow{2}{*}{N/A} \\ \cline{2-3}
+& Transversal aux versions & Par rapport à la précédente & & \\
+\hline
+
+Compression &
+Niveau chunk &
+Niveau version &
+Niveau fichier &
+Niveau version &
+N/A \\
+\hline
+
+Restauration de la dernière version &
+Lecture des métadonnées puis des chunks de cette version (répartis dans différents pools) &
+Lecture de la totalité du DNA-Drive &
+Lecture récursive des différents objets composant la version (répartis dans différents pools) &
+Lecture de la zone correspondant à la dernière version &
+Lecture de la zone correspondant à la dernière version \\
+
+\end{tabularx}
+
+\subsection{Nombre d'octets par version}
+
+\subsubsection{Légende}
+
+\begin{itemize}
+\item
+ \verb|4k_export| : le système DNA-Backup avec des blocs de 4 Kio.
+\item
+ \verb|8k_export| : le système DNA-Backup avec des blocs de 8 Kio.
+\item
+ \verb|diffs| : une somme de diffs Git minimales Gzippées.
+\item
+ \verb|nopack| : le dossier `objects de Git, contenant l'ensemble des
+ données des fichiers et dossiers d'un dépôt.
+\item
+ \verb|targz| : une somme d'archives Tar Gzippées.
+\item
+ \verb|real| : le poids réel de chaque version et donc l'espace
+ nécessaire à stocker l'ensemble des versions de manière
+ non-dé-dupliquées.
+\end{itemize}
+
+\subsubsection{Résultats}
+
+Commits journaliers~:
+
+\begin{verbatim}
+=============================== SUMMARY ===============================
+ 4k_export 8k_export diffs nopack targz real
+ 46,080,540 46,021,380 47,011,621 63,237,214 47,582,036 201,476,675
+ 8,160 13,260 2,625 88,673 47,580,422 201,472,392
+ 6,453,540 8,091,660 3,270,798 26,668,802 48,699,094 206,006,230
+ 205,020 108,120 496 24,839 48,699,144 206,006,227
+ 214,200 121,380 1,475 318,053 48,699,266 206,006,571
+ 255,000 162,180 3,271,631 107,651 47,592,358 201,472,618
+ 393,720 358,020 99,337 2,758,951 47,579,804 201,420,809
+ 67,320 78,540 127,793 561,940 47,578,309 201,415,269
+ 155,040 75,480 19,221 10,035 47,590,552 201,467,847
+ 286,620 205,020 250,581 1,203,018 47,719,274 202,032,972
+ 39,780 38,760 19,555 550,478 47,721,098 202,042,129
+ 159,120 80,580 203 45,564 47,721,112 202,042,114
+ 182,580 115,260 12,419 284,765 47,725,696 202,057,720
+ 13,260 14,280 5,823 76,010 47,731,040 202,065,875
+ 23,460 28,560 13,370 528,743 47,738,360 202,078,613
+ 27,540 33,660 10,837 374,955 47,735,904 202,078,276
+ 68,340 81,600 69,707 498,918 47,771,130 202,216,013
+================================ TOTAL ================================
+ 54,633,240 55,627,740 54,187,492 97,338,609 813,464,599 3,443,358,350
+\end{verbatim}
+
+Commits hebdomadaires :
+
+\begin{verbatim}
+=============================== SUMMARY ===============================
+ 4k_export 8k_export diffs nopack targz real
+ 46,086,660 46,003,020 47,003,541 63,221,563 47,569,933 201,420,809
+ 701,760 820,080 395,080 6,358,050 47,723,749 202,065,875
+ 6,293,400 7,983,540 2,994,599 25,581,925 48,700,415 206,003,757
+ 206,040 109,140 407 50,815 48,700,637 206,003,795
+ 225,420 142,800 8,679 401,381 48,698,820 206,005,265
+ 1,299,480 1,707,480 579,422 6,943,222 48,733,791 206,098,060
+ 952,680 1,248,480 360,710 4,799,958 48,840,759 206,648,359
+ 1,425,960 1,831,920 738,359 4,983,831 48,892,096 206,834,840
+ 1,770,720 2,091,000 1,389,502 7,767,439 49,297,747 209,328,856
+ 479,400 727,260 146,129 2,899,286 49,331,055 209,479,362
+ 168,300 235,620 47,436 1,385,568 49,333,845 209,503,564
+ 134,640 236,640 37,183 1,808,603 49,338,373 209,509,777
+ 90,780 122,400 23,924 1,555,868 49,336,559 209,515,352
+ 3,088,560 3,953,520 1,404,256 11,037,484 49,933,159 211,878,380
+ 4,987,800 6,165,900 2,326,692 17,577,030 50,214,110 212,941,025
+ 993,480 1,378,020 304,617 6,594,520 50,293,382 213,254,405
+ 684,420 900,660 258,512 4,016,395 50,398,489 213,650,745
+================================ TOTAL ================================
+ 69,589,500 75,657,480 58,019,048 166,982,938 835,336,919 3,540,142,226
+\end{verbatim}
+
+Commits mensuels :
+
+\begin{verbatim}
+=============================== SUMMARY ===============================
+ 4k_export 8k_export diffs nopack targz real
+ 47,297,400 47,244,360 48,249,466 64,900,653 48,828,605 206,662,692
+ 1,822,740 1,938,000 1,495,969 7,407,714 48,900,735 206,964,143
+ 1,525,920 1,808,460 797,390 9,856,043 49,326,511 209,515,646
+ 8,047,800 9,840,960 4,142,700 28,400,251 50,394,403 213,653,996
+ 10,730,400 13,230,420 5,489,832 34,132,686 51,315,648 217,862,957
+ 5,786,460 6,936,000 2,262,584 19,233,445 51,941,615 220,756,834
+ 7,816,260 10,320,360 2,999,817 28,983,950 52,574,107 223,306,219
+ 1,210,740 1,643,220 299,628 8,343,393 52,587,994 223,373,786
+ 11,002,740 13,589,460 4,759,088 34,259,652 53,210,823 226,113,059
+ 1,819,680 2,399,040 679,794 10,029,012 53,165,063 225,781,616
+ 622,200 858,840 138,547 4,375,159 53,183,197 225,870,650
+ 12,874,440 16,493,400 5,142,691 45,544,733 53,842,821 228,546,001
+ 1,169,940 1,591,200 247,526 8,491,133 53,876,401 228,653,615
+ 5,631,420 6,589,200 2,333,317 18,119,613 54,605,555 232,014,492
+ 9,988,860 12,876,480 3,989,065 37,945,661 55,206,806 234,571,285
+ 10,659,000 13,416,060 3,800,775 37,509,079 56,059,067 238,170,923
+ 8,796,480 11,079,240 3,030,148 32,387,325 56,716,443 241,420,002
+================================ TOTAL ================================
+146,802,480 171,854,700 89,858,337 429,919,502 895,735,794 3,803,237,916
+\end{verbatim}
+
% \begin{figure}[h]
% \centering