path: root/pdf/doc.tex

\documentclass[a4paper]{report}

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

% Bibliography
\usepackage[numbers]{natbib}    % more bibliography options
\usepackage[nottoc]{tocbibind}  % add link to table of contents
\bibliographystyle{plainnat}    % more detailled plain bibliography

% 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
\usepackage{lmodern}        % Latin modern font recommended by Vincent
\DeclareUnicodeCharacter{202F}{\thinspace}

% Define some colors
\usepackage{xcolor}
\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
}

% Graphics
\usepackage{graphicx}        % images and figures
\usepackage{subcaption}      % subcaption and subtables
\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}
\usepackage{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

% Localised number print (thousands, decimals, etc.)
\usepackage{numprint}

% Directory tree
\usepackage{dirtree}

% Acronyms
\usepackage[printonlyused,footnote]{acronym}

% Hyperlinks
\usepackage{xurl}                % allow word break for url wrapping
\usepackage[
  hidelinks,                     % invisible links
  pagebackref=true               % linkback to citations from bibliography
]{hyperref}                      % create clickable links
\usepackage{doi}                 % add links to doi urls

% Backrefs in the bibliography for french
\renewcommand{\backrefalt}[4]{
\ifcase #1 {}
  \or \emph{Cité page #2}
  \else \emph{Cité pages #2}
\fi
}
% Backref separators for french
\renewcommand{\backreftwosep}{ et~}
\renewcommand{\backreflastsep}{, et~}

% Style
\setlength{\parskip}{.3em} % space between paragraphs

% Custom commands
\usepackage{xspace} % automatically add a space after the command if needed
\newcommand{\etal}{\emph{et al.}\@\xspace}

\newcommand{\fonts}[2][m]{{\fontseries{#1}\selectfont #2}} % select a font series for the given text
\newcommand{\textb}{\fonts[b]}

\newcommand{\btrfs}{BTRFS~\cite{rodeh2013btrfs}\@\xspace}
\newcommand{\erofs}{EROFS~\cite{gao2019erofs}\@\xspace}
\newcommand{\hptfs}{HPTFS~\cite{zhang2006hptfs}\@\xspace}
\newcommand{\ltfs}{LTFS~\cite{pease2010linear}\@\xspace}
\newcommand{\squashfs}{SquashFS~\cite{lougher2009squashfs}\@\xspace}
\newcommand{\udf}{UDF~\cite{optical2003universal}\@\xspace}

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

\title{Système de fichiers pour le stockage d’informations numériques sur ADN}

\date{Octobre 2021}

\author{Nicolas Peugnet}

\begin{document}

\pagenumbering{Roman}
\begin{titlepage}
\maketitle
\end{titlepage}

\pagenumbering{arabic}
\tableofcontents

\chapter{Introduction}

Ce stage a été réalisé dans le cadre du projet DNA-Drive,
un système développé par l'équipe de Stéphane Lemaire (\ac{lcqb})
visant à stocker des données numériques arbitraires via des molécules d'\ac{adn}.
Notre rôle sera de proposer un \emph{système de fichiers} adapté aux spécificités de ce nouveau médium de stockage.

\section{Systèmes de fichiers}

Le but d'un \emph{système de fichiers} est d'organiser des données sur un support de stockage.
En son absence, les différentes données d'un support seraient toutes écrites d'un seul tenant
et il ne serait pas possible de savoir où commence et où s'arrête un morceau de données cohérent.
Le système de fichiers offre donc la possibilité de répartir les données dans des segments nommés : les \emph{fichiers}.
Ces fichiers peuvent être disposés au sein d'une arborescence de \emph{dossiers},
ce qui permet de les organiser de manière logique.
Les informations de cette arborescence sont des métadonnées qui doivent donc être stockées en plus des données.
En règle générale, les systèmes de fichiers récents stockent bien plus de métadonnées que simplement les noms des fichiers et des dossiers.
Parmi celles-ci, on peut citer par exemple les dates de création et de modification,
ou bien encore les permissions lorsqu'il s'agit d'un système POSIX.

Grâce à cette structure d'arborescence de fichiers commune à tous les systèmes,
on obtient une compatibilité de l'un à l'autre,
ce qui offre à la couche supérieure une abstraction des supports de stockages.

Pour stocker ou lire des données, un système de fichiers doit communiquer avec le matériel.
Lorsqu'il s'agit d'un support de stockage classique respectant le \ac{lba},
comme c'est le cas des disques durs et des \ac{ssd},
le système de fichiers n'a pas besoin de connaitre le fonctionnement détaillé du périphérique.
Il lui suffit de demander de lire ou écrire les données du bloc $n$
et c'est le contrôleur du périphérique lui-même qui se charge de retrouver l'emplacement physique de ce bloc logique.

Dans le cas de supports plus spécifiques, il est assez fréquent que les systèmes de fichiers soient conçus exclusivement pour ceux-ci.
C'est par exemple le cas pour les bandes magnétiques avec \hptfs et \ltfs ou les disques optiques avec \udf.
Ces systèmes seront parfaitement adaptés à leur support et pourront donc pousser plus loin certaines optimisations.

\subsection{Fonctionnalités et caractéristiques}

En plus de son rôle d'abstraction des supports de stockage,
un système de fichier peut proposer un grand nombre de fonctionnalités et de caractéristiques intéressantes.
Nous n'introduirons ici que celles qui nous seront utiles à la compréhension de la suite de ce document.

\paragraph{Type d'accès}
Un système de fichiers peut être accessible soit en lecture uniquement (\ac{ro}),
comme c'est le cas d'une bonne partie des systèmes compressés (\squashfs, \erofs,~etc.),
soit en lecture et écriture (\ac{rw}) pour la grande majorité des autres systèmes.

\paragraph{Compression}
La compression peut avoir plusieurs intérêts pour un système de fichiers.
Elle peut bien-sûr permettre de réduire l'espace occupé par les données sur le support
et c'est ce cas d'utilisation que \squashfs tente d'optimiser.
Mais elle peut aussi servir à accélérer les opérations de lecture et d'écriture lorsque la bande passante est un facteur limitant.
Des systèmes plus généralistes, comme \btrfs, utilisent la compression à cette fin
et d'autres systèmes de fichiers, comme \erofs, sont même entièrement basés sur ce principe.

% TODO: quelles autres propriétés ?

\section{Stocker des données sur ADN}

L'information génétique des organismes vivants a pour support l'\ac{adn} (Acide DésoxyriboNucléique), et l'ensemble du matériel génétique d'un organisme constitue son génome.
L'\ac{adn} est codé sous la forme d'une suite de molécules organiques que sont les \emph{nucléotides}.
Il existe quatre nucléotides différents, représentés par quatre lettres : \textbf{A} pour Adénine, \textbf{T} pour Thymine, \textbf{G} pour Guanine, et \textbf{C} pour Cytosine.
Les nucléotides s'associent deux à deux pour former un double brin d'\ac{adn}.
Ainsi, l'Adénine est appariée à la Thymine et la Guanine à la Cytosine.
Chaque brin d'\ac{adn} est alors complémentaire de l'autre.

Il est donc possible d'établir un parallèle entre l'information génétique, codée par les 4 nucléotides formant l'\ac{adn}, en base~4, et la donnée informatique, codée par une suite de bits en base~2.
Utiliser l'\ac{adn} comme support de stockage numérique
pourrait avoir plusieurs intérêts.
La densité d'information est assez importante
($10^{19}$~bit/cm$^3$ contre $10^{16}$ pour une mémoire flash)
et la durée de vie de la molécule peut atteindre plusieurs centaines d'années,
contre une cinquantaine d'années maximum pour les bandes magnétiques,
le support le plus pérenne actuellement.

Plusieurs démonstrations de faisabilité du stockage sur l’\ac{adn} ont déjà été réalisées ces dernières années.
Les travaux publiés pour l’instant se basent essentiellement sur l’utilisation d’\emph{oligonucléotides}, qui sont des courts segments d’\ac{adn} contenant quelques dizaines de nucléotides.

\subsection{Encodages}

Les premières démonstrations significatives sur l’utilisation de ces oligonucléotides pour stocker des données remontent à seulement 2012 avec George Church~\cite{church2012next} qui réussit à stocker 658~ko sur \numprint{54898} oligonucléotides.
Dans ses travaux, Church souhaite pouvoir contrôler le taux de GC et limiter les répétitions d’un même nucléotide.
Le taux de GC est la proportion de nucléotides G et C dans une séquence donnée. 
Les appariements GC sont formées par trois liaisons hydrogène tandis que les appariements AT n'en ont que deux, les rendant moins stables.
Un taux de GC élevé assure ainsi une meilleure stabilité, mais un taux trop élevé peut provoquer une autolyse (autodestruction) plus facilement.
Il est donc préférable d’avoir un taux de GC équilibré.
En ce qui concerne les longues répétitions d’un même nucléotide, elles produisent des erreurs lors du séquençage.
Pour toutes ces raisons, Church va utiliser un encodage en base~2 : $A=C=0$ et $T=G=1$ pour avoir plus de flexibilité (Table~\ref{tab:church-encoding}).

\begin{table}[ht]
\centering
\setlength{\tabcolsep}{.8em}
\renewcommand\arraystretch{1.5}

\begin{subtable}[t]{.45\textwidth}
  \centering
  \begin{tabular}{|c|c|c|c|}
  \hline
  \multirow{2}{*}{\textbf{Bit}} & \textbf{0} & A & C \\
  \cline{2-4}
  & \textbf{1} & T & G \\
  \hline
  \end{tabular}
  \caption{Encodage Church~\cite{church2012next}}
  \label{tab:church-encoding}
\end{subtable}
\hfill
\begin{subtable}[t]{.54\textwidth}
  \centering
  \begin{tabular}{|c|c|c|c|}
  \cline{3-4}
  \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{\textbf{Position}} \\
  \cline{3-4}
  \multicolumn{2}{c|}{} & \textbf{Paire} & \textbf{Impaire} \\
  \hline
  \multirow{2}{*}{\textbf{Bit}} & \textbf{0} & A & C \\
  \cline{2-4}
  & \textbf{1} & T & G \\
  \hline
  \end{tabular}
  \caption{Encodage BIODATA}
  \label{tab:biodata-encoding}
\end{subtable}

\caption{Différents encodages pour \ac{adn}}
\label{tab:dna-encodings}
\end{table}

Suite à ces travaux, un certain nombre de nouvelles publications
vont apporter des améliorations intéressantes aux techniques existantes,
avec par exemple l'encodage de Goldman~\cite{goldman2013towards}
qui propose l'utilisation d'une base~3 (Figure~\ref{fig:goldman-encoding}),
plus performante en densité de stockage.

\begin{figure}[ht]
\centering
\includegraphics[width=.6\textwidth]{goldman-encoding}
\caption{Encodage de Goldman~\cite{goldman2013towards}}
\label{fig:goldman-encoding}
\end{figure}


\subsection{Spécificités du DNA-Drive}

\subsubsection{Spécificités biologiques}

La spécificité principale de DNA-Drive par rapport à ses concurrents
est d'utiliser la molécule d'\ac{adn} sous sa forme de double hélice,
plutôt que sous la forme d'un simple brin.

Cette forme a plusieurs avantages : 
premièrement, la molécule est plus stable sous cette forme,
ce qui limite sa dégradation et permet donc d'augmenter sa durée de vie.
Deuxièmement, il s'agit de la forme utilisée par l'ensemble des organismes vivants
de notre planète\footnote{En considérant que les virus ne sont pas vivants},
ce qui nous permet donc de potentiellement profiter des mécanismes du vivant,
tels que la réparation automatique de l’\ac{adn} pour corriger les erreurs,
ou la division cellulaire qui va permettre une copie peu coûteuse et très rapide de grandes quantités de données.

Cependant, faire en sorte qu'une molécule d'\ac{adn} soit compatible avec un être vivant ajoute des contraintes supplémentaires.
En particulier, en plus de garantir un taux de GC équilibré,
notre encodeur doit à tout prix éviter que les séquences de données, une fois encodées en ADN,
ne soient interprétés par l'hôte comme des séquences codantes de son génome.

Dans l'ADN d'un être vivant, ces parties codantes sont délimités par
deux courtes séquences de nucléotides placées au début et à la fin de la zone à interpréter.
Il s'agit des codons START et STOP.
Le codon START indique le début d'une séquence à interpréter,
c'est donc celui qu'il faut à tout prix éviter d'obtenir une fois les données encodées.
Le codon STOP, au contraire, définit la fin d'une telle séquence,
il est donc intéressant d'en insérer autant que possible pour limiter les effets néfastes
dans l'éventualité où un codon START aurait malencontreusement été ajouté.

En ce qui concerne la lecture des données, on utilise un séquenceur génétique portatif à
nanopore tels que celui utilisé par l’équipe de H. Yadzi~\cite{yazdi2017portable} et présenté sur la Figure~\ref{fig:oxford-nanopore-minion}.
Les séquenceurs en général ont un problème avec la lecture des homopolymères, c’est-à-dire des
séquences de répétitions d’un même nucléotide. On interdit donc les séquences de plus de trois fois
le même nucléotide pour éviter les erreurs de séquençage.

\begin{figure}[ht]
\centering
\includegraphics[width=.6\textwidth]{oxford-nanopore-minion}
\caption{Lecteur Oxford Nanopore MinION}
\label{fig:oxford-nanopore-minion}
\end{figure}

BIODATA, l'encodage mis au point par Clémence Blachon (\ac{lcqb}) pour le DNA-Drive
est justement chargé de faire respecter ces propriétés par les données encodées.
Il est inspiré de celui de Church, auquel des contraintes supplémentaires viennent s'appliquer :
Pour chaque bit, on fixe la valeur du nucléotide en fonction de sa valeur et de la parité de sa position (Table~\ref{tab:biodata-encoding}).
De cette manière l'encodage est totalement contraint et le résultat est déterministe.
Les valeurs choisies garantissent quelle que soit la séquence de bits que :

\begin{itemize}
  \item Le taux de GC restera équilibré.
  \item Un nucléotide ne sera jamais répété plusieurs fois à la suite.
  \item Aucun codon START ne sera inséré.
  \item Des codons STOP seront insérés régulièrement.
\end{itemize}

Cet encodage permet donc, lorsqu'on encode des données, de s'abstraire totalement des problématiques biologiques sous-jacentes
et laisse ainsi la possibilité de stocker des valeurs arbitraires.

\subsubsection{Spécificités techniques}

L'organisation physique des données du DNA-Drive est assez particulière
et doit être prise en compte afin d'optimiser les lectures et les écritures.

\paragraph{Track} Une \emph{track} est un segment de données, actuellement de 1024~octets.
C'est la plus petite unité de stockage du système.
Toutes les écritures devront donc être alignées sur la taille d'une track.
Elles sont obtenues grâce à un assemblage MoClo~\cite{werner2012fast} sur 3 niveaux
et sont refermées en un cercle pour former des \emph{plasmides}.
Cette forme particulière de la molécule d'\ac{adn} comporte plusieurs avantages.
Elle est tout d'abord plus pérenne grâce à sa structure circulaire,
car c'est principalement par ses extrémités que la molécule se dégrade.
Mais les plasmides profitent en plus de leur propre mécanisme d'auto-réplication autonome.
Cependant, cette forme ne permet pas de les mettre bout-à-bout,
il n'y a donc pas d'ordre naturel entre les tracks.
C'est pour cette raison que chaque track contient un \emph{barcode} qui permet de les identifier et donc de les réordonner.

\paragraph{Barcode} Le \emph{barcode} est un entier de 4~octets présent au tout début d'une track et permettant de l'identifier.

\paragraph{Pool} Un \emph{pool} est une minicapsule contenant plusieurs tracks.
Actuellement, un pool peut contenir \numprint{10000} tracks et les lectures sont réalisées par pool entier.
Il est possible de lire plusieurs pools en même temps
et même de fusionner des pools si les barcodes des tracks qu'ils contiennent ne se chevauchent pas.

\paragraph{Array} Un \emph{array} est une plaque de 96~pools ($8\times12$) qui est traditionnellement utilisée en biologie.
La taille maximum disponible pour des données d’un array est donc de \numprint{979.2}~Mo ($96\times\numprint{10000}\times\numprint{1020}$~octets).
On peut multiplier les arrays afin d'obtenir une plus grande capacité de stockage.

Les chiffres donnés ici sur l’organisation du disque de \numprint{1024} octets par track
et \numprint{10000} tracks par pool sont limités respectivement par la complexité de l'assemblage MoClo
et la précision limitée des techniques de séquençage actuelles.
La capacité disponible est donc amenée à évoluer dans le futur avec l'arrivée de technologies plus performantes.

% TODO: peut-être un schéma si j'ai le temps

\section{Problématique}

Il existe donc plusieurs techniques et encodages permettant
de stocker des informations arbitraires sur la molécule d'\ac{adn},
mais, malgré les avantages de densité et de durabilité de cette molécule,
toutes ont en commun quelques inconvénients majeurs.
Ces inconvénients proviennent pour la plupart des limites actuelles
des technologies de synthèse et de séquençage.
Une expérience d'un système automatisé de transmission de données par \ac{adn} datant de 2019~\cite{takahashi2019demonstration}
nous donne un ordre de grandeur des durées de lecture et d'écriture,
bien qu'il ne serait pas étonnant que des techniques plus performantes fassent leur apparition dans un futur proche :
La latence d'une opération d'écriture suivie d'une lecture d'une séquence de 12~octets est de 21~h,
dont \numprint{20.4}~h pour l'écriture (\numprint{8.4}~h de synthèse à 305~s par base et 12~h de stabilisation)
et les 36~min restantes pour la lecture (30~min de préparation et 6~min de séquençage et décodage).
Les lectures ne sont donc déjà pas très rapides,
mais le point le plus limitant provient très largement des écritures
qui sont exceptionnellement lentes, sans même parler de leur coût.
% TODO: revoir cette phrase

Une autre inconvénient du DNA-Drive et de l'ensemble des initiatives
de stockage de données sur \ac{adn} est l'impossibilité de supprimer
ou de modifier des données une fois écrites.
Ce point est particulièrement bloquant pour un système de fichiers \ac{rw} classique,
qui se base sur ces deux propriétés pour mettre à jour les fichiers et leurs métadonnées
ainsi que pour récupérer de l'espace lorsque des fichiers sont supprimés.

Cette problématique se retrouve sur d'autres systèmes de stockages,
comme les bandes magnétiques ou les disques optiques.
Elle est résolue par leur système de fichiers respectif,
\ltfs pour les bandes magnétiques et \udf pour les CD 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 \ltfs ou de la Virtual Allocation Table dans le cas de \udf.

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.


\section{Réponse}

La proposition qui suit s'inscrit dans le cadre d'une réponse à court terme au problème posé.
Nous avons choisi de ne pas nous projeter trop loin dans le temps
et avons donc basé l'ensemble de la réflexion sur les capacités actuelles
des technologies de synthèse et de séquençage \ac{adn}.

L'objectif principal du système d'archivage de fichiers proposé
est de \emph{réduire la quantité de données écrites} et donc synthétisées.
Cependant, il est tout de même important de minimiser la quantité de données
à lire pour restaurer les fichiers.

Toutes les contraintes citées précédemment nous ont incité
à nous orienter vers un système de sauvegardes plutôt que vers un véritable système de fichiers.
En effet, les vitesses et coûts d'écriture et de lecture ne permettent, pour le moment,
absolument pas d'en faire un système de fichiers accessible ``à chaud''.
Ce n'est par exemple pas la peine d'écrire un fichier
s'il va être supprimé ou renommé quelques secondes plus tard.
Les cas d'usage envisagés seront donc ceux de sauvegardes sur différentes plages de temps :
journalières, hebdomadaires ou mensuelles.
De cette manière, l'ensemble des opérations réalisés sur les fichiers pendant cette plage de temps
seront factorisées dans un seul bloc de modification : la nouvelle version.


Afin de minimiser la quantité de données écrites par version, celles-ci sont réalisées de manière incrémentale.
Chaque nouvelle version est donc en quelque sorte une différence par rapport aux précédentes.
Ce stockage incrémental est obtenu grâce à une utilisation conjointe de la déduplication et de l'encodage delta.
Ainsi, comme aucune donnée ne peut être supprimée,
nous en profitons pour réaliser un système versionné,
qui nous laisse la possibilité d'accéder aux précédentes sauvegardes.


\chapter{Présentation de DNA-Backup}

DNA-Backup, notre proposition, ressemble plus à un système de sauvegardes qu'à un système de fichiers.
Chaque nouvelle version vient s'ajouter à la précédente, car il est impossible de supprimer ou de modifier des données
et on applique un \emph{pipeline} de compression sur les données de chaque version afin d'en minimiser la taille.

\section{Pipeline de compression}

Le pipeline est inspiré de celui de Philip Shilane \etal
dans leur travail sur la réplication de sauvegardes à travers un lien de faible bande passante~\cite{shilane2012wan}.
Il est composé d'un étage de \emph{déduplication}, suivi d'un étage d'\emph{encodage delta}
et enfin d'un dernier étage de \emph{compression}.
Ces trois techniques sont basées sur l'identification de similitudes entre différentes zones du flux de données.
La déduplication permet de ne pas réécrire plusieurs fois le même bloc de données si ce bloc existe déjà.
L'encodage delta permet de ne pas avoir à réécrire entièrement un bloc similaire à un bloc existant,
en n'en écrivant que la différence.
La compression est également basée sur ces deux principes, mais elle est appliquée à une plus petite échelle.
Dans DNA-backup, la déduplication et l'encodage delta sont tous les deux appliqués sur des blocs d'une même taille fixe appelés \emph{chunks}.

Afin d'appliquer de manière efficace les étapes de déduplication et d'encodage delta de notre pipeline,
il nous faut être capable de rapidement retrouver des chunk identiques ou similaires.
Nous utilisons pour cela deux fonctions de hachage qui fournissent des signatures aux propriétés particulières.
L'une de ces signatures, appelée ici \emph{fingerprint} permet d'identifier des chunks identiques à dédupliquer,
l'autre, appelée ici \emph{sketch} permet de trouver des chunks fortement similaires,
lesquels feraient de bons candidats à l'encodage delta.
De cette manière, pour appliquer le pipeline sur une nouvelle version,
il nous suffit d'avoir ces deux informations en mémoire pour chaque chunk déjà écrit.
Seule l'étape d'encodage delta nous forcera à aller chercher le contenu réel d'un chunk similaire,
lorsqu'il aura été trouvé à l'aide de son sketch.

\subsection{Fingerprint}

La \emph{fingerprint} permet d'identifier un bloc de manière unique en fonction de son contenu.
C'est ainsi que l'on peut savoir si deux chunks sont identiques et devraient donc être dédupliqués.
Pour cette application, n'importe quelle fonction de hachage uniformément répartie pourrait convenir.
Il faut simplement calibrer la taille de la signature en fonction du nombre de chunks que le support peut contenir afin d'éviter les collisions.

Dans notre cas précis, nous avons tout de même besoin d'une fonction capable d'être d'appliquée sur une fenêtre glissante, appelée \emph{rolling hash}.
En effet, lorsqu'une nouvelle version est traitée par le pipeline,
il faut appliquer la fonction de hachage sur tous les chunks possibles, octet par octet, des données de cette version.
Une fonction optimisée pour ce type de traitement apportera donc un gain de performances non négligeable.

Nous avons choisi pour cet usage l'empreinte de Rabin~\cite{rabin1981fingerprinting},
car c'est une fonction de hachage sur fenêtre glissante efficiente et populaire
et parce qu'elle sera également utilisée pour calculer le \emph{sketch} des chunks.

\subsection{Sketch}

Le \emph{sketch} est ce qu'on appelle un \emph{hash de ressemblance}.
Il correspond en fait à une fonction de hachage dont la répartition n'est pas du tout uniforme,
mais au contraire, fait correspondre la même signature à des données différentes si elles sont similaires.

De manière intuitive, les sketches de similitude fonctionnent en identifiant des portions d'un chunk
qui ne changeraient probablement pas si de faibles variations sont introduites ;
on appelle ces portions des ``features''.
Une des manières de procéder est d'utiliser une fonction de hachage sur une fenêtre glissante de petite taille
(e.g. 32~octets) et de choisir la valeur maximale obtenue en tant que feature.
En utilisant différentes fonctions de hash on peut ainsi obtenir plusieurs features.

La méthode exacte utilisée est celle décrite par Philip Shilane \etal~\cite{shilane2012wan}.
Elle s'appuie sur l'empreinte de Rabin~\cite{rabin1981fingerprinting}
que l'on décline en différentes fonctions de hachage pour obtenir plusieurs features.
Les features ainsi obtenues sont ensuite regroupées pour former un plus petit nombre de ``super-features''.
La valeur d'une super-feature correspond au hash des features sous-jacentes,
donc si deux chunks ont une super-feature en commun,
alors toutes les features correspondantes sont également identiques.
Regrouper les features de cette manière aide à réduire les faux-positifs
et augmente le taux de similarité lorsqu'une correspondance est trouvée.

Augmenter le nombre de features par super-feature augmente la qualité des correspondances,
mais diminue aussi leur nombre.
Augmenter les nombre de super-feature par sketch augmente le nombre de correspondances,
mais nécessite plus d'espace mémoire.
Nous utilisons pour le moment les valeurs choisies par Philip Shilane \etal
au cours de leurs expérimentations~\cite{shilane2012wan},
soit 3 super-features par sketch et 4 features par super-features.
Ces valeurs pourraient être ajustées une fois que de plus amples expériences
sur des jeux de données plus variés auront été réalisés.

\subsection{Index des signatures}
Pour connaitre de manière efficace l'existence d'une fingerprint
ou d'un sketch dans les données existantes du DNA-Drive, nous avons besoin de stocker leur valeur.
En effet, autrement il faudrait les recalculer depuis les données, ce qui serait coûteux.
Ces valeurs sont donc stockées dans deux index.
L'un faisant l'association entre des fingerprints et leur chunk,
l'autre entre des super-features et leurs chunks.
Philip Shilane \etal travaillaient sur de très gros jeux de données
et ne pouvaient pas se permettre de garder l'ensemble de ces index en mémoire,
ils ont donc opté pour n'en garder qu'une partie à l'aide d'un cache~\cite{shilane2012wan}.
Dans notre cas, la quantité de données est suffisamment faible pour qu'on puisse se permettre
de garder la totalité des index en mémoire.
De cette manière nous sommes certains de ne manquer aucune correspondance,
ce qui maximise la qualité de déduplication et l'encodage Delta.

Dans l'hypothèse où l'espace de stockage du DNA-Drive deviendrait beaucoup plus grand,
il restera toujours la possibilité de ne garder qu'un cache en mémoire
et d'utiliser un filtre de Bloom~\cite{bloom1970space} devant le reste de l'index
qui serait stocké sur disque.
En effet, même si le temps de recherche dans l'index s'en trouvera augmenté,
il restera très faible par rapport au temps de synthèse.

Cependant, les index de signatures seuls ne sont pas suffisants pour appliquer le pipeline.
Nous avons également besoin du contenu des chunks lors de l'encodage delta.
Or, les temps de lecture rédhibitoires du DNA-Drive nous empêchent de lire à la demande
le contenu d'un chunk lorsque l'on en a besoin.
C'est pour cela que nous avons finalement décidé de conserver sur un support de stockage classique
une copie des informations stockées sur le DNA-Drive ;
la capacité du DNA-Drive étant pour le moment bien inférieure à ce qui existe sur d'autres supports.


\section{Fonctionnement général}

Le système part du principe qu'on dispose, sur un support de stockage classique,
d'une copie des données stockées en \ac{adn} appelée le \emph{repo} (Figure~\ref{fig:big-picture}).
Sa raison d'être est d'accélérer la création et la restauration d'une version
en fournissant un accès rapide aux données que contient le DNA-Drive.

\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.3) -- (5,2.3) node[midway,above] {Commit};
\draw[Arrow] (7.5,2.3) -- (10,2.3) node[midway,above] {Export};
\draw[Arrow] (5,1.7) -- (3,1.7) node[midway,below] {Restore};
\draw[Arrow] (10,1.7) -- (7.5,1.7) node[midway,below] {Import};

\end{tikzpicture}

\caption{Le repo est une zone intermédiaire entre le dossier source à sauvegarder et le DNA-Drive.}
\label{fig:big-picture}
\end{figure*}

\subsection{Principe de base}

Pour créer une nouvelle version ou en restaurer une existante, DNA-Backup n'utilise donc que le repo.
Il est ensuite possible d'exporter les données du repo vers le DNA-Drive,
ou bien de reconstruire le repo en important les données du DNA-Drive,
par exemple dans le cas d'une défaillance ou bien d'une duplication.

DNA-Backup stocke les données d'une version d'une manière assez particulière.
Chaque version est en fait un \emph{disque virtuel} contenant les données des fichiers mis bout-à-bout.
Ce disque virtuel ne contient aucune métadonnée, seulement le contenu des fichiers
et c'est sur lui qu'on applique le pipeline de compression.
Il n'est donc pas stocké sous la forme d'un segment continu, mais en tant qu'un ensemble de chunks.
La liste des chunks qui le compose fait partie des métadonnées que DNA-Backup doit enregistrer.
C'est à partir de cette liste et du contenu des chunks que l'on peut recréer le disque virtuel.
Mais le disque virtuel à lui seul ne suffit pas à restaurer une version.
En effet, il ne contient aucune métadonnée,
il est donc impossible de savoir à quel fichier correspond une donnée.
DNA-Backup doit donc également sauvegarder pour chaque version une liste de noms de fichiers,
permettant de retrouver dans son disque virtuel où commence et où s'arrête chaque fichier.

Pour restaurer une version, il faut donc dans un premier temps
reconstruire en mémoire le disque virtuel à partir de sa liste de chunks,
puis le découper en fichiers à partir de la liste des noms de fichiers.


\subsection{Contenu du repo}

Le repo est donc une zone intermédiaire qui devra contenir l'ensemble des données écrites sur le DNA-Drive.
Mais contrairement à ce dernier, il est stocké sur un support classique.
Il n'est donc pas nécessaire de l'optimiser autant en terme d'espace de stockage.
D'autant plus qu'il faut que les données soient facilement accessibles
pour augmenter l'efficacité des algorithmes du commit et du restore.
Toutefois, afin de simplifier les imports et les exports avec le DNA-Drive,
la plupart des données sont stockées de manière quasiment identique.
Il ne faut pas non-plus que l'espace qu'il occupe soit trop important,
la totalité de ses fichiers sont donc compressés.

Le repo tire parti du système de fichier sur lequel il est stocké.
Il organise ses données dans différents fichiers,
chacun rangé dans le dossier de la version à laquelle il appartient.
La Figure~\ref{fig:repo-dir-tree} montre un exemple d'arborescence de repo comportant deux versions.
Un dossier de version est nommé par son numéro et contient trois fichiers de métadonnées :
\verb|files|, \verb|hashes|, et \verb|recipe|, ainsi qu'un dossier \verb|chunks|.

\begin{figure*}[ht]
\centering

\begin{subfigure}[c]{.34\textwidth}
  % \centering % centering ne fonctionne pas du tout avec le dirtree
  \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{Exemple d'arborescence d'un repo comportant deux versions.}
  \label{fig:repo-dir-tree}
\end{subfigure}
\hfill
\begin{subtable}[c]{.55\textwidth}
  \centering
  \begin{tabular}{l r 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\% \\
  \end{tabular}
  \caption{
    Répartition des données d'un repo comportant une seule version pour une taille totale de 401 Mio.
    Ce repo a été obtenu à partir d'un dossier contenant un certain nombre de projets web,
    il s'agit donc d'un contenu assez hétéroclite, comportant notamment des images et autres fichiers déjà compressés.
  }
  \label{tab:repo-data-distribution}
\end{subtable}

\caption{Organisation du \emph{repo}.}
\label{fig:repo-organisation}
\end{figure*}

\paragraph{Chunks}
Le dossier \verb|chunks| contient l'ensemble des chunks ajoutés dans cette version.
Chaque chunk est stocké dans un fichier séparé et compressé indépendamment des autres.
De cette manière, il est très facile d'accéder au contenu d'un chunk précis.

\paragraph{Files}
Le fichier \verb|files| contient la liste des fichiers ainsi que leur taille.
C'est grâce à lui qu'on est capable de retrouver
à quel fichier appartient une donnée du disque virtuel d'une version.
Il ne contient en réalité que la différence apportée à cette liste dans cette version
par rapport à la précédente.
Pour reconstruire la véritable liste de fichiers,
il faut donc relire l'ensemble des fichiers \verb|files|
et appliquer les différences les unes à la suite des autres.
De plus, le contenu de ce fichier est finalement compressé avant d'être écrit sur le disque,
afin d'encore économiser de l'espace.

\paragraph{Recipe}
C'est dans le fichier \verb|recipe| que le repo stocke la liste des chunks
permettant de reconstruire le disque virtuel d'une version.
Exactement comme pour le fichier \verb|files|, il est enregistré de manière incrémentale,
en différence par rapport à la version précédente.
Le même processus de reconstruction d'y applique donc.

\paragraph{Hashes}
Pour ne pas avoir à recalculer les signatures (fingerprints et sketches) de tous les chunks du repo lors d'un commit,
on stocke ses valeurs dans un fichier \verb|hashes| séparé.
Celui-ci ne sera pas synthétisé en \ac{adn},
car les données qu'il contient peuvent être recalculées à partir du contenu des chunks.


\subsection{L'export vers le DNA-Drive}
\label{sec:dna-export}

Au lieu de voir le DNA-Drive comme une grille,
on l'imagine comme une liste de \emph{pools} à une seule dimension (Figure~\ref{fig:data-layout}).
De cette manière on peut répartir l'espace de stockage
entre les deux principaux segments de données de DNA-Backup :
les chunks et les métadonnées (recipe + files).
Comme on peut le remarquer sur la Figure~\ref{tab:repo-data-distribution},
les métadonnées ont une taille bien inférieure à celle de l'ensemble des chunks,
en particulier lorsque les fichiers sont grands.
Cependant, il n'est pas possible de savoir à l'avance exactement
quelle proportion sera utilisée par les métadonnées,
car leur taille peut varier en fonction d'un certain nombre de paramètres
(type de fichiers sauvegardés, fréquence de sauvegarde, quantité et taille des fichiers,~etc.).
Pour garantir une utilisation maximale de l'espace disponible,
on fait démarrer ces deux segments chacun à une extrémité du DNA-Drive
et on les laisse grandir l'un vers l'autre,
à la manière de la \emph{pile} et du \emph{tas} d'un processus.

Contrairement à la manière dont ils sont stockés dans le repo,
lors de l'export, les chunks ne sont pas compressés indépendamment,
mais tous ensembles, par version.
De cette manière on réduit encore l'espace occupé par les chunks,
car l'algorithme de compression n'a pas à réécrire plusieurs fois son ``header''
et peut réutiliser les motifs de répétition trouvés dans un chunk
à travers l'ensemble des chunks d'une version.
Cette technique a pour inconvénient d'avoir besoin de décompresser (et donc lire)
la totalité des chunks d'une version même si on ne veut en lire qu'un seul.


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

Le tout premier pool du DNA-Dire (numéro 0) est réservé aux \emph{header} des versions
et aux métadonnées globales du repo.

Pour chaque version, il faut conserver la taille de ses trois segments
(\verb|chunks|, \verb|recipe| et \verb|files|).
De la même manière qu'il serait impossible de savoir
à quel fichier appartient une donnée sans la liste de fichiers,
il serait impossible sans ces informations, de savoir
à quelle version et à quel segment de données appartient une track.
Le header d'une version ne comptant que trois valeurs numériques, il ne remplira jamais une track.
Pour éviter de gâcher l'espace restant des tracks de version,
DNA-Backup le remplit avec le contenu des segments de métadonnées (\verb|recipe| + \verb|files|)
jusqu'à ce qu'il soit plein ou que toutes les métadonnées aient été écrites.
S'il reste encore des métadonnées, elles sont écrites à l'endroit prévu initialement.

En ce qui concerne les métadonnées du repo,
un \emph{superblock} serait ajouté dans la toute première track du premier pool.
Celui-ci contiendrait les valeurs des paramètres de DNA-Backup,
à savoir principalement la taille des chunks, mais aussi les paramètres de la fonction de sketch,
l'algorithme utilisé pour la compression utilisé, celui pour les deltas,~etc.

L'export est actuellement réalisé dans un dossier, dans lequel 96~fichiers
représentant chacun un pool sont créés et remplis avec les données du repo.
Les écritures sont alignées sur la taille d'une track, laquelle est configurable.
Le repo n'a pas réellement de connaissances de ces valeurs en dehors de l'export.
DNA-Backup est donc en grande partie indépendant du DNA-Drive
et pourrait être utilisé avec d'autres supports de stockages,
ou même en utilisant uniquement le repo,
à la manière d'un logiciel de sauvegardes incrémentales classique.


\subsection{Importer depuis le DNA-Drive}

Les fonctions d'import n'ont pour le moment pas été implémentées.
Ce qui suit décrit donc l'ensemble des fonctionnalités qui pourraient être implémentées
à partir du format d'export décrit dans la section~\ref{sec:dna-export}.

\subsubsection{Reconstruction complète du repo}

En lisant la totalité du DNA-Drive, il est possible de reconstruire entièrement le repo.
Une fois ce dernier reconstruit, n'importe quelle version peut être restaurée très rapidement.
Afin de reconstruire le repo, il faut dans un premier temps lire le pool de version.
Celui-ci contient en effet le superblock ainsi que les headers des versions,
nécessaires à l'initialisation du repo et au découpage du reste des données en segments cohérents.
Une fois ce pool séquencé et décodé, il est possible de savoir
le nombre de pools qu'il faut maintenant lire pour récupérer les chunks
et les métadonnées de chaque version.

Pour réduire le temps total de lecture, il serait également possible,
en même temps que de lire le pool de version,
de séquencer en parallèle les premiers pools de chunks et de métadonnées.
Ainsi, même si on ne peut pas immédiatement donner du sens aux données de ces pools,
il sera possible de les décoder dès que les headers des versions seront restaurés.

Cette opération est longue, mais n'est à réaliser que lorsque l'on veut restaurer la totalité du repo,
par exemple après une défaillance ou lors d'une duplication.
Si le but n'est que de récupérer la dernière version,
il n'est pas nécessaire de reconstruire le repo en entier.

\subsubsection{Restauration de la dernière version}

Il est possible de ne restaurer qu'une version,
sans avoir à lire la totalité des données présentes sur le DNA-Drive.
L'opération commence de la même manière que pour la reconstruction complète du repo,
il nous faut donc tout d'abord lire le pool de version ainsi que ceux des métadonnées.
Comme le montre la Figure~\ref{tab:repo-data-distribution},
la taille des métadonnées est très faible par rapport à celle des chunks.
Nous n'avons pas eu l'opportunité de réaliser suffisamment de tests
afin d'évaluer le pourcentage maximum utilisé par les métadonnées,
mais aux cours de nos tests sur des données fortement déduplicables et compressibles,
les métadonnées ont atteint jusqu'à 15\% du volume total de données.
Nous estimons qu'elles ne devraient pas dépasser 20\% de la totalité des données écrites.

Une fois les pools de métadonnées séquencés,
il est possible de reconstruire les véritables valeurs
de la recipe et de la liste des fichiers,
en appliquant les différences de chaque version les unes à la suite des autres.
Avec ces informations, la liste des chunks permettant
de reconstruire le disque virtuel de cette version est maintenant connue.
L'étape suivante consiste donc à déterminer quels sont les pools de chunks qu'il va falloir lire.

C'est malheureusement ici qu'on paie le prix de la compression réalisée lors de l'export.
En effet, comme les chunks sont tous compressés en même temps,
il n'est pas possible de sélectionner seulement les tracks composant un chunk lors d'une lecture.
Il faut nécessairement lire la totalité du segment de chunks de cette version
pour pouvoir le décompresser, et en extraire le chunk voulu.
On obtient donc une forte amplification des lectures,
car il faudra lire une quantité de données beaucoup plus grande que celles qui composent réellement la version.

Nous ne pouvons pas réellement quantifier cette amplification des lectures pour le moment.
Il faudrait pour cela réaliser des simulations du coût de restauration d'une version.
Cela-dit, si la lecture est finalement un cas d'utilisation qui devient plus important,
il reste toujours la possibilité, à la manière du repo,
de compresser les chunks indépendamment lors de l'export vers le DNA-Drive,
au détriment de l'espace utilisé.

\subsubsection{Restauration d'un seul fichier}

De manière assez similaire à la restauration d'une version complète,
bien que la seule lecture des métadonnées nous permette d'obtenir les arborescences de chaque version,
ainsi que de déterminer les chunks qu'il est nécessaire de lire
afin de restaurer le contenu d'un fichier unique,
la technique de compression utilisée lors de l'export diminue l'intérêt de ce cas d'utilisation.
Les lectures seront une fois encore amplifiées, car tous les chunks d'une même version devront être lus.

Toutefois, il est possible que les chunks du fichier en question fassent tous partie d'une petite et même version.
Dans ce cas l'amplification de lecture restera contenue
et potentiellement bien moindre que si on avait eu à restaurer la totalité de la version.


\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
(L'Annexe~\ref{sec:documentation} donne quelques informations supplémentaires pour aider à la compilation et l'utilisation du programme).
Ce langage a été choisi, car :
\begin{itemize}
  \item Il propose un bon compromis entre performance et temps de développement.
  \item Il est très facilement compilable pour un grand nombre de systèmes d'exploitation et d'architectures.
  \item Le programme résultant n'est dépendant d'aucun runtime, ce qui permet de produire des logiciels ``cross-platform''.
  \item Par curiosité et envie de découvrir et d'apprendre ce langage.
\end{itemize}

\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|~\cite{pike2011gob},
a été utilisé à maintes reprises, du fait de sa simplicité de mise en œuvre
et de sa relativement bonne efficacité en terme d'espace.
Malheureusement, il n'est pas particulièrement interopérable car,
malgré que la totalité de ses spécifications soient disponibles,
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, le choix n'a pas tellement d'importance,
car l'algorithme peut être facilement remplacé par un autre, plus performant.
L'utilisation actuelle de \emph{Zlib}~\cite{rfc1950} basé sur DEFLATE~\cite{rfc1951} reste malgré tout 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 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,
jusqu'à ce qu'ils décident d'en créer un parfaitement adapté à leur besoin~\cite{chromium2012courgette}.
Cependant, \verb|bsdiff| est optimisé pour des 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}

\subsubsection{Files}
Pour rappel, le fichier \verb|files| correspond aux métadonnées
de l'arborescence du système de fichier.
C'est là que sont stockés les données à propos des fichiers, comme leur nom et leur taille
et c'est grâce à ce segment de données qu'on peut retrouver la position d'un fichier
dans le disque virtuel.
DNA-Backup stocke le contenu de ce fichier comme une liste de structures \verb|File|
(Figure~\ref{fig:type-file-struct}), encodée avec \verb|gob|~\cite{pike2011gob}.

Cette structure possède également un champ \verb|Link|.
Celui-ci permet de supporter la fonction de liens symboliques des systèmes de fichiers POSIX.
DNA-Backup conserve ainsi la valeur des liens
et ne duplique pas le contenu des fichiers ou des dossiers.
Si le lien est absolu, il sera correctement reformé lors de la restauration
et les liens relatifs le restent une fois restaurés.
Les autres métadonnées des fichiers
comme les permissions et les dates de création ou de modification
ne sont pas enregistrées.

\subsubsection{Recipe}
Le fichier \verb|recipe| est celui qui permet de reconstruire le disque virtuel.
Go nous autorise à créer des listes de structures hétérogènes grâce aux interfaces,
il s'agit donc concrètement d'une simple liste de structures de chunks (Figure~\ref{fig:type-chunks-struct}).
Une fois encore, encodée à l'aide de \verb|gob|~\cite{pike2011gob}.
Un chunk est référencé par son ID, dont la structure est visible Figure~\ref{fig:type-chunkid-struct}.

\begin{figure}[ht]
\centering
\begin{subfigure}[t]{.45\textwidth}
\begin{lstlisting}[language=Go]
type File struct {
    Path string
    Size int
    Link string
}
\end{lstlisting}
\caption{Structure File}
\label{fig:type-file-struct}
\hfill
\begin{lstlisting}[language=Go]
type ChunkId struct {
    Version int
    Index   int
}
\end{lstlisting}
\caption{Structure ChunkId}
\label{fig:type-chunkid-struct}
\end{subfigure}
\hfil
\begin{subfigure}[t]{.45\textwidth}
\begin{lstlisting}[language=Go]
type StoredChunk struct {
    Id      ChunkId
}

type DeltaChunk struct {
    Source  ChunkId
    Patch   []byte
    Size    int
}

type PartialChunk struct {
    Value []byte
}
\end{lstlisting}
\caption{Structures des différents types de chunks\protect\footnotemark}
\label{fig:type-chunks-struct}
\end{subfigure}
\caption{Structures de données du repo}
\label{fig:repo-type-struct}
\end{figure}
\footnotetext{\lstinline{PartialChunk} s'appelle en réalité \lstinline{TempChunk} dans le code, pour le moment}

Comme on peut le voir, les \verb|DeltaChunks| contiennent un champ \verb|Patch|.
Il s'agit de la différence de ce chunk par rapport à celui référencé par le champ \verb|Source|.
C'est donc la \verb|recipe| qui contient les deltas,
mais aussi potentiellement des données d'une taille inférieure à la taille d'un chunk,
par exemple le tout dernier chunk du disque virtuel.

Le même algorithme d'encodage delta que celui utilisé pour les chunks,
\verb|fdelta|~\cite{hipp2006fdelta},
permet de sauvegarder les informations de ces deux fichiers de manière incrémentale.
Il est appliqué sur le résultat de l'encodage par \verb|gob|~\cite{pike2011gob}
et sa sortie est compressée avant d'être stockée.

\section{Algorithme du commit}

\begin{enumerate}
\item
  Chargement des métadonnées du repo afin de reconstruire en
  mémoire l'état de la dernière version :

  \begin{itemize}
  \item
    Reconstruction de la recipe à partir des deltas de chaque
    version.
  \item
    Reconstruction du listage des fichiers à partir des deltas de chaque
    version (fichier \verb|files|).
  \item
    Reconstruction en mémoire des index de \emph{fingerprints} et
    de \emph{sketches} à partir des fichiers \verb|hashes| de chaque
    version.
  \end{itemize}
\item
  Listage des fichiers de la source.
\item
  Concaténation de l'ensemble des fichiers de la source en un disque
  virtuel continu.
\item
  Lecture de ce disque virtuel. Tant qu'il reste des données dans le disque virtuel :
  
  \begin{itemize}
  \item
    Application de l'empreinte de Rabin~\cite{rabin1981fingerprinting}
    sur les données du disque virtuel, avec une fenêtre glissante de la taille d'un chunk,
    afin de chercher des correspondances de \emph{fingerprint} avec l'index.
  \item
    Lorsqu'une fingerprint est trouvée, le chunk correspondant est alors
    stocké de manière dé-dupliquée, sous la forme d'un \verb|StoredChunk|
    (Figure~\ref{fig:type-chunks-struct})
    contenant l'identifiant du chunk trouvé dans l'index.
  \item
    Si aucune correspondance n'est trouvé après avoir analysé
    l'équivalent de 3 chunks de données,
    alors le \emph{sketch} du premier chunk est calculé et cherché dans l'index
    pour tenter de le stocker en encodage delta, sous la forme d'un \verb|DeltaChunk|
    (Figure~\ref{fig:type-chunks-struct}).
  \item
    S'il n'est pas trouvé, il est alors stocké en tant que nouveau \verb|StoredChunk|
    et sa \emph{fingerprint} et son \emph{sketch} sont ajoutés aux index.
  \item
    Si une correspondance (de fingerprint ou de sketch) arrive entre le deuxième
    et le troisième chunk, alors, si possible, le reste du deuxième chunk est
    fusionné avec le premier pour tenter de l'encoder en tant qu'un seul \verb|DeltaChunk|.
  \end{itemize}
\item
  Calcul des différences entre la nouvelle version et la précédente pour
  les métadonnées (files et recipe) et stockage des deltas ainsi obtenus.
\end{enumerate}

\section{Algorithme du restore}

\begin{enumerate}
\item
  Chargement des métadonnées du repo afin de reconstruire en
  mémoire l'état de la dernière version :

  \begin{itemize}
  \item
    Reconstruction de la 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 recipe, reconstruire le disque virtuel.
\item
  Découper ce disque virtuel en fonction du listage des fichiers
  et réécrire les données dans les fichiers correspondants dans le répertoire destination.
\end{enumerate}


\chapter{Évaluation de performances}

Nous comparons DNA-Backup à des systèmes existants
afin de quantifier son potentiel intérêt.
Les évaluations réalisées au cours de ce stage reste toutefois limitées.
Seul l'espace occupé est pris en compte dans ce comparatif.
De plus amples expériences pourraient aider à évaluer ce système,
notamment en termes de coût des lectures.

\section{Bases de comparaison}

Quatre autres systèmes de stockage versionnés ont été choisis comme bases de comparaison
(la Table~\ref{tab:recap-table} offre une vision d'ensemble
pour comparer les différentes fonctionnalités de ces systèmes) :
\begin{itemize}
\item \textbf{Git diffs}
\item \textbf{Git objects}
\item \textbf{Tar.gz}
\item \textbf{Taille réelle}
\end{itemize}

\subsection{Git diffs}
\label{sec: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 les restaurer, il faut
appliquer séquentiellement l'ensemble des deltas jusqu'à obtenir l'état
de la version voulue.

Le delta ainsi obtenu est ensuite compressé à l'aide de Gzip pour en diminuer la taille.
Cette compression est assez efficace, car elle est réalisée d'une seule passe sur toute la version.
La commande utilisée pour produire ces versions est la suivante :

\begin{lstlisting}[language=sh]
git diff --minimal --binary --unified=0 -l0 | gzip
\end{lstlisting}

L'option \verb|--minimal| permet de faire en sorte que Git passe plus de temps
à essayer de trouver le plus petit ensemble de différences.
L'option \verb|--binary| est là pour forcer Git
à calculer des différences pour les fichiers binaires.
Avec \verb|--unified=0| on peut produire des diffs
qui ne contiennent aucune contextualisation
et \verb|-l0| désactive la limite du nombre de fichiers
à prendre en compte pour la détection de renommage.
Nous nous assurons avec toutes ces options de produire les deltas les plus petits possibles.
Pour garantir que ces différences sont viables,
elles sont, au cours de l'expérience, réappliquées au moins une fois
et le résultat est comparé avec le dossier source.

\subsection{Git objects}

Il s'agit de la manière dont Git
sauvegarde les données des fichiers d'un dépôt~\cite{straub2013git}. 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.

Cette base de comparaison simule un système de fichiers qui ne serait
pas autorisé à modifier des données sur le support tout en gardant la
possibilité de les mettre à jour.

\subsection{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.

\subsection{Taille réelle}

Cette base de comparaison n'est en réalité pas un système viable. Elle
correspond à la taille réelle qu'occupe 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.

\begin{table*}[ht]
\renewcommand\arraystretch{1.5}
\small

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

&
\textb{DNA-Backup} &
\textb{Git diffs} &
\textb{Git objects} &
\textb{Tar.gz} &
\textb{Taille réelle} \\
\hline

\multirow{2}{=}{\textb{Dé\-du\-pli\-ca\-tion}} &
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}{=}{\textb{Encodage delta}} &
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

\textb{Com\-pres\-sion} &
Niveau version &
Niveau version &
Niveau fichier &
Niveau version &
N/A \\
\hline

\textb{Res\-tau\-ra\-tion 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{Récapitulatif des systèmes de stockages versionnés comparés.}
\label{tab:recap-table}
\end{table*}

\section{Quantité d'octets par version}


Pour évaluer les performances du système DNA-Backup,
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.

Un inconvénient de ce jeu de données, en plus de son unicité,
est de n'être composé quasiment exclusivement que de fichiers texte.
Ce type de fichier est très fortement compressible,
ce qui augmente l'importance de l'étape de compression.
Ce n'est pas spécialement cette étape qui sépare DNA-Backup
des autres systèmes auxquels nous nous comparons.
L'utilisation commune de Zlib~\cite{rfc1950} par toutes les solutions testés
permet heureusement de ne pas trop avantager un système par rapport aux autres.

\subsection{Protocole expérimental}
\label{sec:protocole-experimental}

Le protocole se base sur des dépôts Git comme base de données
de dossiers dont le contenu évolue au cours du temps.
Le dépôt sélectionné est dans un premier temps cloné avec son dossier \verb|.git| externalisé.
Dans notre cas, il s'agit de celui du noyau Linux.
Nous pouvons ensuite extraire une liste de commits en ordre chronologique.
Laquelle est finalement filtrée à l'aide de \verb|sort|
pour n'en garder au maximum qu'un seul par jour.
La commande utilisée est la suivante :

\begin{lstlisting}[language=sh]
git log --reverse --date-order --first-parent --pretty=tformat:"%H	%as" | sort --unique --key=2
\end{lstlisting}

L'utilisation de l'option \verb|--first-parent| est importante,
car elle permet de ne suivre qu'une seule branche de l'historique
et ainsi éviter le va-et-vient d'une branche à une autre entre deux commits.
Pour les expérimentations simulant des commits hebdomadaires et mensuels,
cette liste est filtrée à nouveau pour n'en garder respectivement
qu'une ligne sur sept et une ligne sur 30.

Chaque expérimentation va ensuite faire évoluer l'état du dossier du dépôt
de celui d'un commit de cette liste au suivant.
Tout en exécutant à chaque fois entre deux, les différents systèmes à comparer.
Aucune autre valeur que l'espace de stockage n'est mesuré.
Ce dernier est comptabilisé à l'aide de la commande \verb|du|
et de son option \verb|--apparent-size|, car on ne veut surtout pas prendre en compte l'``overhead''
du système de fichier par-dessus lequel les tests sont réalisés.

Tous les scripts permettant d'obtenir les résultats suivants sont disponibles
et les expérimentations sont reproductibles.
L'Annexe~\ref{sec:experimentations} apporte une aide minimale sur l'utilisation de ces scripts.

\subsection{Résultats}

\subsubsection{Méthode de compression des chunks}

Dans un premier temps, nous comparons les performances de DNA-Backup
entre l'espace utilisé par le repo et celui utilisé par l'export (Table~\ref{tab:commits-daily-repo}).
Le but ici était principalement de quantifier la perte d'espace
due à la compression indépendante des chunks.
Le fichier \verb|hashes| n'est donc pas comptabilisé dans cette expérience.

\begin{table*}[ht]
\small
\centering
\begin{subtable}[t]{.65\textwidth}
  \centering
  \begin{tabular}{rrrr}
  \textb{Repo 4k} &
  \textb{Repo 8k} &
  \textb{DNA 4k} &
  \textb{DNA 8k} \\
  \hline
  \input{assets/summary.daily.17.repo.tex}
  \end{tabular}
  \caption{
    Comparaison entre la taille du repo (mis à part le fichier hashes)
    et l'espace pris par l'export DNA-Drive, avec des chunks de 4 et 8~ko.
  }
  \label{tab:commits-daily-repo}
\end{subtable}
\hfill
\begin{subtable}[t]{.3\textwidth}
  \centering
  \begin{tabular}{r}
  \textb{Borg} \\
  \hline
  \input{assets/summary.daily.17.borg.tex}
  \end{tabular}
  \caption{Logiciel de sauvegardes dédupliqués \emph{Borg}~\cite{waldmann2017borg}, avec le chiffrement désactivé.}
  \label{tab:commits-daily-borg}
\end{subtable}
\caption{Commits journaliers.}
\label{tab:commits-daily-misc}
\end{table*}

La comparaison n'est pas tout à fait équitable,
car lors de l'export, les segments des versions sont alignées à la taille d'une track,
ici \numprint{1020}~octets.
Les exports ont donc un handicap, car des bits de bourrage sont potentiellement ajoutés.
Cependant, on remarque tout de même une très nette réduction d'espace
lorsque les chunks sont compressés par version plutôt qu'indépendamment.

Nous pouvons également remarquer que lorsque les chunks sont compressés tous ensemble,
il devient plus intéressant d'en réduire la taille.
En effet, plus les chunks sont petits, plus l'on perd d'efficacité
avec les algorithmes de compression lorsqu'ils sont compressés indépendamment.

Dans la suite des expériences, nous ne comptabiliserons pas l'espace occupé par le repo,
mais uniquement celui occupé par les exports.


\subsubsection{Comparaison avec Borg}

\emph{Borg Backup}~\cite{waldmann2017borg} est un système de sauvegardes dédupliqué populaire
au fonctionnement assez similaire à celui de DNA-Backup en ce qui concerne la déduplication.
Cependant, il n'implémente pas d'encodage delta.
Nous ne l'avons pas mentionné dans le tableau comparatif
parce qu'il a été ajouté au banc de test un peu trop tardivement.
La Table~\ref{tab:commits-daily-borg} montre le résultat d'une exécution sur des commits journaliers.
Nous nous attendions à un meilleur résultat,
venant d'un système de sauvegarde incrémental dédié à cet usage.
L'espace qu'il occupe est même supérieur aux \textbf{Git objects} (Table~\ref{tab:commits-daily}).
Cet écart provient peut-être de métadonnées que Borg pourrait ajouter,
telles que des sommes de contrôle ou bien des index.
Dans la suite des expérimentations, Borg ne sera pas ajouté au banc de tests.

Nous ne nous sommes pas trop attardés sur les options que Borg propose.
Il se peut que certaines permettent de réduire la taille des sauvegardes.
Nous nous sommes contentés de désactiver l'option de chiffrement du dépôt,
cette dernière ne pouvant que l'augmenter.



\begin{table*}[ht]
\small
\centering
\begin{tabularx}{\textwidth}{@{}RRRRRR}
\textb{DNA 4k} &
\textb{DNA 8k} &
\textb{Git diffs} &
\textb{Git objects} &
\textb{Tar.gz} &
\textb{Taille réelle} \\
\hline
\input{assets/summary.daily.17.tex}
\end{tabularx}
\caption{Commits journaliers.}
\label{tab:commits-daily}
\end{table*}

\subsubsection{Commits journaliers}

La Table~\ref{tab:commits-daily} montre les résultats de l'expérience
lorsqu'on crée un commit chaque jour.
Le jeu de données de test étant un gros projet,
les modifications réalisées en une journée sont déjà assez conséquentes.
La colonne \textbf{Git diffs} offre une bonne approximation
de la quantité de données qui ont été modifiées à chaque version.

Dans notre comparatif, l'espace occupé par les diffs Git est considéré comme optimal.
En effet, la différence obtenue avec l'aide de Git
et des options spécifiées Section~\ref{sec:git-diffs},
correspond presque au set de changement minimum nécessaire à décrire cette version.
Cependant, les versions ainsi obtenues ne profitent pas totalement des informations déjà écrites.
Car elles ne sont produites qu'en différence par rapport à la version précédente
et pas par rapport à toutes les versions précédentes.
Avant d'utiliser l'option \verb|--first-parent| décrite Section~\ref{sec:protocole-experimental},
il est arrivé que DNA-Backup soit meilleur que les diffs Git.
Effectivement, comme les différences alternaient d'une branche à l'autre,
elles contenaient en grande partie des modifications annulant les précédentes, et ainsi de suite.
Tandis que DNA-backup pouvait profiter de la déduplication pour économiser des écritures.

Nous avons décidé de ne pas inclure ces résultats dans le présent rapport,
car le cas d'usage nous paraissait trop éloigné de la réalité.
Mais il pourrait tout de même être intéressant de pousser cette expérience plus loin dans le temps
pour voir si, à terme, la déduplication et l'encodage delta permettent de surpasser les diffs Git
en rentabilisant au maximum les données déjà présentes sur le support.


\begin{table*}[ht]
\small
\centering
\begin{tabularx}{\textwidth}{@{}RRRRRR}
\textb{DNA 4k} &
\textb{DNA 8k} &
\textb{Git diffs} &
\textb{Git objects} &
\textb{Tar.gz} &
\textb{Taille réelle} \\
\hline
\input{assets/summary.weekly.17.tex}
\end{tabularx}
\caption{Commits hebdomadaires.}
\label{tab:commits-weekly}
\end{table*}

\begin{table*}[ht]
\small
\centering
\begin{tabularx}{\textwidth}{@{}RRRRRR}
\textb{DNA 4k} &
\textb{DNA 8k} &
\textb{Git diffs} &
\textb{Git objects} &
\textb{Tar.gz} &
\textb{Taille réelle} \\
\hline
\input{assets/summary.monthly.17.tex}
\end{tabularx}
\caption{Commits Mensuels.}
\label{tab:commits-monthly}
\end{table*}

\subsubsection{Commits hebdomadaires et mensuels}

Les résultats hebdomadaires (Figure~\ref{tab:commits-weekly}) et mensuels (Figure~\ref{tab:commits-monthly})
ne font que confirmer ce qui a été observé précédemment.
L'écart se creuse avec les diffs Git, mais DNA-Backup reste un bon compromis.
Car il ne faut pas oublier que pour restaurer la dernière version des diffs Git,
il est absolument nécessaire de relire la totalité des données qui ont été stockées.
De plus, Git est particulièrement bon dans ce cas précis
parce qu'il s'agit de fichiers textes,
pour lesquels il est explicitement optimisé.
Sur des données plus hétérogènes, il est possible que DNA-Backup se montre meilleur.

Pour rendre toutes ces comparaisons plus équitables,
il aurait été possible d'aligner chacune des versions
des autres systèmes à la taille d'une track,
afin que DNA-Backup ne soit pas le seul à avoir ce handicap.

Finalement, on remarque surtout le manque cruel d'un plus grand nombre d'expérimentations,
que ce soit au niveau des jeux de données, des paramètres de DNA-Backup ou des propriétés à tester.
En l'état, il est difficile de tirer une conclusion claire, en raison du manque d'éléments de réponse.


\chapter*{Conclusion}
\addcontentsline{toc}{chapter}{Conclusion}

L'\ac{adn} en tant que support de stockage des données présente des avantages de durabilité et de densité,
mais souffre également d'inconvénients majeurs.
Il est impossible de supprimer ou même de modifier des données existantes
et les débits de lecture et d'écriture sont plusieurs ordres de grandeurs
plus faibles que ceux des autres supports d'archivage actuels.

Pour répondre à cette problématique, le système de fichier que nous avons imaginé
s'efforce de réduire au maximum la quantité de données écrites,
tout en essayant de limiter l'amplification des lectures.
Pour cela, on applique sur les données un pipeline de compression basé sur la déduplication et l'encodage delta
et on limite les métadonnées des fichiers au strict minimum.
Ces dernières étant stockées à part afin de pouvoir rapidement y accéder
et de manière incrémentale pour en réduire la taille.

Comme aucune donnée ne peut être supprimée,
le système est versionné pour offrir un accès aux états précédents.
Et pour profiter autant que possible des données existantes,
le pipeline de compression se base non seulement sur les données de la nouvelle version,
mais aussi celles des versions déjà écrites.
Cependant, encoder la différence par rapport à un chunk existant
nécessite d'avoir accès à ses données.
Pour cette raison, nous décidons de conserver une copie des données du DNA-Drive
sur un support de stockage classique.
Ainsi il est possible d'accéder rapidement aux données,
tout en profitant de la durabilité de l'\ac{adn}.
On ne voit donc plus vraiment le DNA-Drive comme un support de stockage,
mais plus comme un système de sauvegardes incrémentales à long terme.
Il devient alors intéressant pour conserver une copie de données cruciales sur un support stable,
qui permettra de les restaurer après une défaillance.

L'évaluation des performances d'une version expérimentale de DNA-Backup
a permis de montrer son potentiel.
Mais il reste encore beaucoup de travail afin d'obtenir des résultats convaincants.
Plus d'expérimentations pourraient être menées, rien qu'avec la version actuelle du programme.
Par exemple en faisant varier plus de paramètres ou en testant avec différents jeux de données.
En ce qui concerne l'implémentation actuelle il manque encore un certain nombre de fonctionnalités.
Les plus importantes étant bien-sûr les différents imports depuis le DNA-Drive.
Mais le superblock n'a pas non plus été implémenté
et les données qu'il contient n'ont pas encore été précisément définies.
De manière générale, l'ensemble des structures de données stockées
sur le DNA-Drive doivent être redéfinies et normalisées,
afin d'être en mesure de publier une spécification
que d'autres logiciels pourraient implémenter.

Plusieurs pistes d'amélioration ont été envisagées.
Notamment l'utilisation d'``extents'' dans la recipe,
comme le font les systèmes de fichiers récents, afin d'en réduire la taille.
Ou bien encore le remplacement des algorithmes d'encodage,
de différence et de compression par des versions plus performantes.
Il serait aussi possible de s'inspirer encore un peu de Git,
en tentant de détecter les renommages de fichiers,
et d'ainsi simplement modifier leur nom dans la liste des fichiers
et réduire encore la taille des versions.
Cette fonctionnalité nécessiterait probablement
de stocker des données supplémentaires dans le repo,
mais le compromis semble très largement gagnant,
car il s'agira de données qu'il ne sera pas nécessaire de copier en \ac{adn}.
Plus globalement, il reste évidemment des optimisations à apporter au code actuel,
que ce soit en termes de temps d'exécution ou d'utilisation CPU.



% Bibliography
\bibliography{doc.bib}

% Annexes
\appendix

% Acronyms
\include{assets/acronyms.tex}

\chapter{Documentation technique}

\section{Documentation du programme}
\label{sec:documentation}

Le code source de l'implémentation de DNA-Backup réalisée pendant ce stage
est disponible sur GitHub à l'adresse suivante :
\url{https://github.com/n-peugnet/dna-backup}.
Ce programme est un logiciel libre ;
vous pouvez le redistribuer ou le modifier suivant les termes de la GNU General Public License
telle que publiée par la Free Software Foundation\footnote{\url{https://www.gnu.org/licenses/gpl-3.0.fr.html}} ;
soit la version 3 de la licence, soit (à votre gré) toute version ultérieure.

\subsection{Compilation}

Le code doit compiler convenablement sur Linux, MacOS et Windows
et les tests doivent passer sans problème sur ces trois plateformes.
Pour nous en assurer, des tests sont lancés par les serveurs
d'intégration de GitHub\footnote{\url{https://github.com/n-peugnet/dna-backup/actions/workflows/build.yml}}.

\subsubsection{Pré-requis}

\begin{itemize}
  \item Go >= 1.16
\end{itemize}

\subsubsection{Instructions}

\begin{lstlisting}[language=sh]
# Build
make build

# Test
make test

# Run
./dna-backup commit <source-dir> <repository>
\end{lstlisting}

\subsection{Usage}

DNA-Backup est un programme s'utilisant en \ac{cli}.
Trois commandes sont disponibles :

\begin{itemize}
  \item \verb|commit| : pour ajouter une nouvelle version au \emph{repo}.
  \item \verb|restore| : afin de restaurer la dernière version depuis le \emph{repo}
  \item \verb|export| : pour générer un export à partir des données du \emph{repo}
\end{itemize}

\section{Scripts des expérimentations}
\label{sec:experimentations}

Le dossier \verb|exp| contient les scripts permettant de reproduire les expériences.
Les scripts ne sont prévus pour fonctionner que sur Linux, avec Bash et GNUMake.

\subsection{Aide}


\begin{lstlisting}[language=sh]
# run experiences
make [SKIP_COMMITS=<count>] [SKIP_CHECK=<count>] [MAX_VERSION=<count>] [RANGE=<range>]

# clean results
make mostlyclean

# clean all
make clean
\end{lstlisting}

\verb|<range>| peut prendre l'une des valeurs suivantes :

\begin{itemize}
  \item \verb|daily|
  \item \verb|weekly|
  \item \verb|monthly|
\end{itemize}

Il est aussi possible de sélectionner les tests qui seront exécutés
et apparaitrons dans les résultats en modifiant leur dossier.
Par exemple, la commande suivante lancera l'expérience, en y ajoutant Borg et en retirant les diffs Git :

\begin{lstlisting}[language=Make]
make DIFFS= BORG=borg
\end{lstlisting}

\subsubsection{Valeurs par défaut des options}

\begin{lstlisting}[language=Make]
SKIP_COMMITS = 0
SKIP_CHECK   = 4
MAX_VERSION  = 5
RANGE        = daily
\end{lstlisting}

\subsubsection{Valeurs par défaut des dossiers}

\begin{lstlisting}[language=Make]
NOPACK = nopack
BORG   =
TARGZ  = targz
REAL   = real
DIFFS  = diffs
\end{lstlisting}


\end{document}