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