diff options
Diffstat (limited to 'pdf/doc.tex')
| -rw-r--r-- | pdf/doc.tex | 107 |
1 files changed, 74 insertions, 33 deletions
diff --git a/pdf/doc.tex b/pdf/doc.tex index 105823a..26e3253 100644 --- a/pdf/doc.tex +++ b/pdf/doc.tex @@ -53,7 +53,7 @@ \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...) +% Localised number print (thousands, decimals, etc.) \usepackage{numprint} % Directory tree @@ -118,7 +118,9 @@ \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}. +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} @@ -157,7 +159,7 @@ Nous n'introduirons ici que celles qui nous seront utiles à la compréhension d \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~\textellipsis), +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} @@ -234,8 +236,10 @@ Pour toutes ces raisons, Church va utiliser un encodage en base~2 : $A=C=0$ et $ \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}), +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] @@ -250,11 +254,15 @@ plus performante en densité de stockage. \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. +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}, +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. @@ -264,12 +272,14 @@ 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. +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é. +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}. @@ -284,7 +294,8 @@ le même nucléotide pour éviter les erreurs de séquençage. \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. +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. @@ -302,7 +313,8 @@ 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. +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. @@ -328,39 +340,57 @@ et même de fusionner des pools si les barcodes des tracks qu'ils contiennent ne 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. +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. \section{Problématique} -Il existe donc plusieurs techniques et encodages permettant de stocker des informations arbitraires sur la molécule d'\ac{adn}, +Il existe donc plusieurs techniques et encodages permettant +de stocker des informations arbitraires sur la molécule d'\ac{adn}, mais 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. +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. +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. +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. +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. +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. +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}. +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 réduire la quantité de données écrites, tout en minimisant la quantité de données à lire pour récupérer les données. +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 vers un système de sauvegardes plutôt que vers un véritable système de fichiers. @@ -370,12 +400,15 @@ Les cas d'usage envisagés seront donc ceux de sauvegardes sur différentes plag 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. +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. 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. -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. +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 de DNA-Backup} @@ -420,7 +453,9 @@ 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. +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} @@ -472,20 +507,24 @@ 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. +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 ; +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 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}). +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. @@ -647,7 +686,7 @@ 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). +(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, @@ -700,7 +739,7 @@ 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 +l'algorithme utilisé pour la compression utilisé, celui pour les deltas,~etc. 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, @@ -1053,6 +1092,7 @@ Lecture de la zone correspondant à la dernière version \\ \begin{table*}[ht] +\centering \begin{tabularx}{\textwidth}{@{}RRRRRR} \textb{DNA 4k} & \textb{DNA 8k} & @@ -1069,6 +1109,7 @@ Lecture de la zone correspondant à la dernière version \\ \begin{table*}[ht] +\centering \begin{tabularx}{\textwidth}{@{}RRRRRR} \textb{DNA 4k} & \textb{DNA 8k} & |