diff options
Diffstat (limited to 'pdf/doc.tex')
| -rw-r--r-- | pdf/doc.tex | 492 |
1 files changed, 332 insertions, 160 deletions
diff --git a/pdf/doc.tex b/pdf/doc.tex index 968fb91..a475bdf 100644 --- a/pdf/doc.tex +++ b/pdf/doc.tex @@ -119,14 +119,14 @@ Notre rôle sera de proposer un \emph{système de fichiers} adapté aux spécifi \section{Systèmes de fichiers} -Le but principal d'un \emph{système de fichiers} est de permettre d'organiser des données sur un support de stockage. +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 cohérent de données. +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}. -Les fichiers peuvent être disposés au sein d'une arborescence de \emph{dossiers}, +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 que l'on doit donc stocker en plus des données. -Les systèmes de fichiers récents stockent en général bien plus de métadonnées que simplement les noms des fichiers et des dossiers. +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. @@ -136,12 +136,12 @@ 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 disque-durs et des \ac{ssd}, +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. -Pour des supports plus spécifiques, il est assez fréquent que les systèmes de fichiers soient conçus exclusivement pour eux. +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. @@ -149,7 +149,7 @@ Ces systèmes seront parfaitement adaptés à leur support et pourront donc pous 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 pour la suite. +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}), @@ -158,10 +158,10 @@ soit en lecture et écriture (\ac{rw}) pour la grande majorité des autres systà \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 pris sur le support -et c'est ce cas d'usage que \squashfs tente d'optimiser. -Mais elle peut aussi servir à accélérer les opérations de lecture et d'écriture lorsqu'on est limité par la bande passante. -Les systèmes plus généralistes, comme \btrfs, utilisent la compression surtout dans ce but +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 ? @@ -248,14 +248,14 @@ plus performante en densité de stockage. 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. +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 potentiellement de profiter des mécanismes du vivant, -tels que la réparation automatique de l’\ac{adn} pour corriger les erreurs +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 lui ajoute des contraintes supplémentaires. +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. @@ -265,7 +265,7 @@ 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 un maximum pour limiter la casse dans l'éventualité où un codon START aurait malencontreusement été ajouté. +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}. @@ -281,7 +281,7 @@ le même nucléotide pour éviter les erreurs de séquençage. \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 : +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 : @@ -293,8 +293,8 @@ Les valeurs choisies garantissent quelle que soit la séquence de bits que : \item Des codons STOP seront insérés régulièrement. \end{itemize} -Cet encodage nous permet donc de nous abstraire totalement des problématiques biologiques sous-jacentes lorsqu'on encode des données -et nous laisse ainsi la possibilité de stocker des valeurs complètement arbitraires. +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} @@ -338,7 +338,7 @@ bien qu'il ne serait pas étonnant que des techniques plus performantes fassent 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 prix. +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. 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, @@ -359,10 +359,13 @@ Nous avons choisi de ne pas nous projeter trop loin dans le temps et avons donc L'objectif principal du système d'archivage de fichiers proposé est de réduire la quantité de données écrites, tout en minimisant la quantité de données à lire pour récupérer les données. Toutes les contraintes citées précédemment nous ont incité % TODO: j'aime bof ce mot -à nous orienter plus vers un système de sauvegardes 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. -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. +à 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''. +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. Ce n'est effectivement pas la peine d'écrire un fichier s'il va être supprimé ou renommé quelques secondes plus tard. Afin de minimiser la quantité de données écrites par version, celles-ci sont réalisées de manière incrémentale. @@ -371,9 +374,9 @@ Ce stockage incrémental est obtenu grâce à une utilisation conjointe de la dà De plus, 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 générale} +\chapter{Présentation de DNA-Backup} -DNA-Backup ressemble donc plus à un système de sauvegardes qu'à un système de fichiers. +DNA-Backup, notre proposition, ressemble donc 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. @@ -381,10 +384,12 @@ et on applique un \emph{pipeline} de compression sur les données de chaque vers 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 déduplication, suivi d'une étape d'encodage delta et enfin d'un dernier étage de compression. +Il est composé d'un étage de déduplication, suivi d'une étape d'encodage delta +et enfin d'un dernier étage de compression. Ces trois techniques sont basées sur la découverte 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. +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 compression et l'encodage delta sont tous les deux appliqués sur des blocs d'une même taille fixe appelés \emph{chunks}. @@ -427,29 +432,45 @@ Une des manières de procéder est d'utiliser une fonction de hachage sur une fe 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. +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}, +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. +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. +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é de l'index en mémoire. -De cette manière nous sommes certains de ne rater 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 en sera augmenté, il restera très faible par rapport au temps de synthèse. +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. @@ -458,11 +479,11 @@ C'est pour cela que nous avons finalement décidé de conserver sur un support d la capacité du DNA-Drive étant pour le moment bien inférieure à ce qui existe sur d'autres supports. -\section{Répartition des données} +\section{Fonctionnement général} -Le système part donc du principe qu'on dispose sur un support de stockage classique d'une copie des données stockées en \ac{adn} appelé le \emph{repo} (Figure~\ref{fig:big-picture}). -Contrairement au DNA-Drive qui est optimisé principalement pour les écritures et moins pour les lectures, -le repo doit permettre de rapidement accéder aux données d'un chunk. +Le système part donc 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 @@ -475,85 +496,158 @@ le repo doit permettre de rapidement accéder aux données d'un chunk. \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}; +\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{Schéma global. Le repo est une zone intermédiaire entre le dossier source à sauvegarder et le DNA-Drive} +\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|. -Avant l'application du pipeline, les données des fichiers d'une version sont au préalable concaténées en un segment virtuel continu. -De cette manière, si la taille d'un fichier n'est pas aligné sur la taille d'un chunk, -les données du fichier suivant y seront ajoutées, au lieu d'avoir à le combler avec des bits de bourrage. -Les métadonnées ne sont pas ajoutées dans ce segment. -Elles sont stockées dans une autre zone, ce qui permet -Leur petite taille en rapport aux données - -La Figure~\ref{fig:repo-dir-tree} montre la structure du \emph{repo}. - -\begin{figure} -% \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{Organisation du \emph{repo}} -\label{fig:repo-dir-tree} -\end{figure} - -Pour un repo d'une taille totale de 401 Mio : - -\begin{table}[ht] +\begin{figure*}[ht] \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\% \\ -\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 \ac{adn}, car ils peuvent être - reconstruits à partir des données des \emph{chunks}. -\item - L'ensemble des données écrites en \ac{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} +\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 de code source, + il s'agit donc d'un grand nombre de fichiers texte de petite taille, fortement déduplicables et compressibles. + } + \label{tab:repo-data-distribution} +\end{subtable} + +\caption{Organisation du \emph{repo}.} +\label{fig:repo-organisation} +\end{figure*} -On imagine le \emph{DNA-Drive} comme un segment de \emph{pools} (Figure~\ref{fig:data-layout}) +\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 à ce fichier 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} + +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~\textellipsis). +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. \begin{figure}[ht] \centering @@ -584,12 +678,123 @@ On imagine le \emph{DNA-Drive} comme un segment de \emph{pools} (Figure~\ref{fig \end{tikzpicture} -\caption{Disposition des données} +\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. -\chapter{Fonctionnement détaillé} +Pour chaque version, il faut conserver la taille que chacun des 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. + +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~\textellipsis + +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. + +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 du 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{Restaurer depuis le DNA-Drive} + +\subsubsection{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 \ac{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. + + + +\chapter{Détails d'implémentation} + +% \section{Détails à propos du repo} + +% Le fichier *files* correspond au métadonnées de l'arborescence du système de fichier. +% C'est là que sont stockés les métadonnées des fichiers (comme par exemple 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 fameux *disque virtuel* + +% Conctrètement c'est simplement une liste de structures File : + +% \begin{lstlisting}[language=Go] +% type File struct { +% Path string +% Size int64 +% Link string +% } +% \end{lstlisting} + + +% Le fichier *recipe* est celui qui permet de reconstruire le *disque virtuel*. Concrètement on peut le voir comme une liste de *chunks*. +% Sachant que j'ai cette structure d'identifiant pour un chunk: + + +% \begin{lstlisting}[language=Go] +% type ChunkId struct { +% Version int +% Index uint64 +% } +% \end{lstlisting} + +% Et 3 types de chunks différents : + + +% \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} + +% /Le PartialChunk s'appelle pour le moment TempChunk dans mon code mais il faut que je change ça./ + +% Donc la *recipe* contient bien les les patchs ( delta d'un chunk par rapport à un autre) des DeltaChunks comme dit plus haut, mais aussi potentiellement des chunks d'une taille inférieure à 8Kio (typiquement le tout dernier chunk du disque virtuel, mais il peut y en avoir d'autres). + +% Il ne faut pas oublier que ces 2 informations sont stockées sous la forme de différences par rapport à la version précédents (ajouts et suppression de fichers et ajouts ou suppression de chunks). \section{Algorithme du commit} @@ -667,34 +872,7 @@ On imagine le \emph{DNA-Drive} comme un segment de \emph{pools} (Figure~\ref{fig correspondants dans le répertoire \emph{destination}. \end{enumerate} -\section{\texorpdfstring{Restaurer sans le -\emph{repo}}{Restaurer sans le repo}} - -\subsection{\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}. -\subsection{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. - -\subsection{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 \ac{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. \chapter{Évaluation de performances} @@ -854,9 +1032,7 @@ Lecture de la zone correspondant à la dernière version \\ % TODO: use real data \begin{table*}[ht] \centering -\begin{tabularx}{\textwidth}{RRRRRRRR} -\textbf{Repo 4k} & -\textbf{Repo 8k} & +\begin{tabularx}{\textwidth}{@{}RRRRRR} \textbf{DNA 4k} & \textbf{DNA 8k} & \textbf{Git diffs} & @@ -864,7 +1040,7 @@ Lecture de la zone correspondant à la dernière version \\ \textbf{Tar.gz} & \textbf{Taille réelle} \\ \hline -\input{assets/summary.daily.5.tex} +\input{assets/summary.daily.17.tex} \end{tabularx} \caption{Commits journaliers} \label{tab:commits-daily} @@ -873,9 +1049,7 @@ Lecture de la zone correspondant à la dernière version \\ % TODO: use real data \begin{table*}[ht] -\begin{tabularx}{\textwidth}{RRRRRRRR} -\textbf{Repo 4k} & -\textbf{Repo 8k} & +\begin{tabularx}{\textwidth}{@{}RRRRRR} \textbf{DNA 4k} & \textbf{DNA 8k} & \textbf{Git diffs} & @@ -883,7 +1057,7 @@ Lecture de la zone correspondant à la dernière version \\ \textbf{Tar.gz} & \textbf{Taille réelle} \\ \hline -\input{assets/summary.daily.5.tex} +\input{assets/summary.weekly.17.tex} \end{tabularx} \caption{Commits hebdomadaires} \label{tab:commits-weekly} @@ -892,9 +1066,7 @@ Lecture de la zone correspondant à la dernière version \\ % TODO: use real data \begin{table*}[ht] -\begin{tabularx}{\textwidth}{RRRRRRRR} -\textbf{Repo 4k} & -\textbf{Repo 8k} & +\begin{tabularx}{\textwidth}{@{}RRRRRR} \textbf{DNA 4k} & \textbf{DNA 8k} & \textbf{Git diffs} & @@ -902,7 +1074,7 @@ Lecture de la zone correspondant à la dernière version \\ \textbf{Tar.gz} & \textbf{Taille réelle} \\ \hline -\input{assets/summary.daily.5.tex} +\input{assets/summary.daily.17.tex} \end{tabularx} \caption{Commits Mensuels} \label{tab:commits-monthly} |