premier ajout du contenu en LaTeX

2 files changed, 423 insertions, 5 deletions

diff --git a/Makefile b/Makefile
index a4d4373..b6ad941 100644
--- a/Makefile
+++ b/Makefile
@@ -18,7 +18,7 @@
 BIN := dna-backup
 SRC := $(shell find . -not \( -path './exp' -prune \) -type f -name '*.go')
 V   := $(if $(CI),-v)
-SUBDIRS := exp
+SUBDIRS := exp pdf
 
 # Default installation paths
 PREFIX ?= /usr/local
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