path: root/pdf/doc.tex

\documentclass[a4paper,twocolumn]{article}

% Set page dimentions
\usepackage[margin=22mm]{geometry}

% Packages for french documents
\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
\DeclareUnicodeCharacter{202F}{\thinspace}

% Define some colors
\usepackage{color}
\definecolor{string}{RGB}{100, 200, 0}
\definecolor{comment}{RGB}{150, 150, 150}
\definecolor{identifier}{RGB}{100, 100, 200}

% Source code style
\usepackage{listings}
\lstset{
	basicstyle=\footnotesize\ttfamily, % sets font style for the code
	frame=single,                 % adds a frame around the code
	showstringspaces=false,       % underline spaces within strings
	tabsize=4,                    % sets default tabsize to 2 spaces
	breaklines=true,              % sets automatic line breaking
	breakatwhitespace=true,       % sets if automatic breaks should only happen at whitespace
	keywordstyle=\color{magenta}, % sets color for keywords
	stringstyle=\color{string},   % sets color for strings
	commentstyle=\color{comment}, % sets color for comments
	emphstyle=\color{identifier}, % sets color for comments
}

% Hyperlinks
\usepackage[hyphens]{url}
\usepackage[hidelinks]{hyperref}

% Bibliography
\usepackage[nottoc]{tocbibind}  % add link to table of contents

% Graphics
\usepackage{graphicx}        % images and figures
\graphicspath{ {assets} }    % path containing images
\usepackage{tikz}            % to generate graphics
\usetikzlibrary{arrows.meta} % setup arrows
\usetikzlibrary{chains,decorations.pathreplacing} % tiks chains
\tikzstyle{Arrow}=[-{Stealth[scale=1.5]}]

% Complex tables
\usepackage{multirow,tabularx}
% Custom column types
\usepackage{array}
\newcolumntype{L}{>{\raggedright\arraybackslash}X} % Left-aligned auto-span columns
\newcolumntype{R}{>{\raggedleft\arraybackslash}X} % Right-aligned auto-span columns

% Directory tree
\usepackage{dirtree}

%--------------------------------------- Content ---------------------------------------%

\title{DNA-Backup}

\date{Octobre 2021}

\author{Nicolas Peugnet}

\begin{document}

\maketitle

\tableofcontents

\section{Introduction}

\subsection{Situation}

Il existe un certain nombre de techniques permettant de stocker des données arbitraires via des molécules d'ADN.
Différents encodages et techniques de conservation sont utilisés, mais elles ont en commun quelques spécificités :

\begin{enumerate}
  \item Elles ne permettent pas de supprimer des données une fois écrites.
  \item Les lectures sont lentes et coûteuses.
  \item Les écritures le sont encore plus.
\end{enumerate}

\subsection{Problématique}

Une des fonctionnalités que le système devait supporter était la possibilité de mettre à jour des fichiers déjà écrits.
Or le médium de stockage utilisé ne permet ni de supprimer des données écrites, ni même de les modifier.
Cette problématique se retrouve sur d'autres médiums de stockages, comme par exemple les bandes magnétiques ou les disques optiques.
Elle est résolue par leur système de fichiers respectif, LTFS \cite{pease2010linear} pour les bandes magnétiques et UDF \cite{optical2003universal} pour les CDs et DVD non-RW.
Dans les deux cas le système est basé sur la réécriture complète des blocs modifiés des fichiers ainsi que de l'index dans le cas de LFTS ou de la Virtual Allocation Table dans le cas d'UDF.

% ajouter un § par rapport aux coùt des écritures

La difficulté principale était donc de réussir à implémenter cette fonctionnalité sur un médium de stockage qui n'a pas la capacité de modifier les données existantes, tout en limitant les écritures au strict nécessaire.


\subsection{Réponse}



La solution proposée se base sur une technique de  \cite{shilane2012wan}.

\section{Présentation générale}


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} (Figure \ref{fig:big-picture}).
\begin{figure*}[ht]
\centering

\begin{tikzpicture}

\draw (0,0) node[anchor=south west] {Ordinateur} rectangle (8, 3.5) ;

\draw (.5,1) rectangle (3,3) node[midway] {Source};
\draw (5,1) rectangle (7.5,3) node[midway] {Repo};
\draw (10,1) rectangle (12.5,3) node[midway] {DNA-Drive};

\draw[Arrow] (3,2) -- (5,2) node[midway,below] {Commit};
\draw[Arrow] (7.5,2) -- (10,2) node[midway,below] {Synthèse};

\end{tikzpicture}

\caption{Schéma global}
\label{fig:big-picture}
\end{figure*}

La Figure \ref{fig:repo-dir-tree} montre la structure du \emph{repo}. 

\begin{figure}
\dirtree{%
.1 repo/. 
.2 00000/. 
.3 chunks/. 
.4 000000000000000. 
.4 000000000000001. 
.4 000000000000002. 
.4 000000000000003. 
.3 files. 
.3 hashes. 
.3 recipe. 
.2 00001/. 
.3 chunks/. 
.4 000000000000000. 
.4 000000000000001. 
.3 files. 
.3 hashes. 
.3 recipe. 
}
\caption{Organisation du \emph{repo}}
\label{fig:repo-dir-tree}
\end{figure}

Pour un repo d'une taille totale de 401 Mio :

\begin{table}
\begin{tabular}{l l r}
\verb|repo/00000/recipe| &   5076011 &   1.2\% \\
\verb|repo/00000/files| &      24664 &   0.1\% \\
\verb|repo/00000/hashes| &   3923672 &   0.9\% \\
\verb|repo/00000/chunks| & 412263137 &  97.8\% \\
\verb|repo/00000| &        421287604 & 100.0\% \\
\end{tabular}
\caption{Répartition des données d'une première version}
\label{fig:repo-data-distribution}
\end{table}

\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} (Figure \ref{fig:data-layout})

\begin{figure}[ht]
\centering

\begin{tikzpicture}[
  start chain = going right,
  node distance = 0,
  Box/.style={draw, minimum width=2em, minimum height=2em, outer sep=0, on chain},
  Brace/.style={decorate,decoration={brace, amplitude=1em, raise=.5em, mirror}}
]
\node[Box] (p0) {$0$};
\node[Box] (p1) {$1$};
\node[Box] (p2) {$2$};
\node[Box] (p3) {$3$};
\node[Box] (p4) {$4$};
\node[Box,minimum width=6em] (ellipsis) {$\cdots$};
\node[Box] (p93) {$93$};
\node[Box] (p94) {$94$};
\node[Box] (p95) {$95$};

\draw[Arrow] (p4.east) to +(2em,0);
\draw[Arrow] (p93.west) to +(-2em,0);

\node (ver) at (0,-3.2em) {version};
\draw[->] (p0.south) to (ver);
\draw[Brace] (p1.south west) to node[black,midway,below=1.5em] {chunks} (p4.south east);
\draw[Brace] (p93.south west) to node[black,midway,below=1.5em,align=center] {metadata\\(recipe+files)} (p95.south east);

\end{tikzpicture}

\caption{Disposition des données}
\label{fig:data-layout}
\end{figure}

\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{Tar.gz}
\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{Tar.gz}

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}

\begin{table*}[ht]

\begin{tabularx}{\textwidth}{L|L|L|L|L|L}

\textbf{Feature} &
\textbf{DNA-Backup} &
\textbf{Git diffs} &
\textbf{Git objects} &
\textbf{Tar.gz} &
\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}

\caption{Tableau récapitulatif}
\label{tab:recap-table}
\end{table*}

\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}


\begin{table*}[ht]
\centering
\begin{tabularx}{\textwidth}{RRRRRRRR}
\textbf{Repo 4k} &
\textbf{Repo 8k} &
\textbf{DNA 4k} &
\textbf{DNA 8k} &
\textbf{Git diffs} &
\textbf{Git repo} &
\textbf{Tar.gz} &
\textbf{Real size} \\
\hline
\input{assets/summary.daily.5.tex}
\end{tabularx}
\caption{Commits journaliers}
\label{tab:commits-daily}
\end{table*}


\begin{table*}[ht]
\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}
\caption{Commits hebdomadaires}
\label{tab:commits-weekly}
\end{table*}


\begin{table*}[ht]
\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}
\caption{Commits Mensuels}
\label{tab:commits-monthly}
\end{table*}


% Bibliography
\bibliographystyle{plain}
\bibliography{doc.bib}

\end{document}