diff options
Diffstat (limited to 'pdf/doc.tex')
| -rw-r--r-- | pdf/doc.tex | 75 |
1 files changed, 37 insertions, 38 deletions
diff --git a/pdf/doc.tex b/pdf/doc.tex index 5ceba47..7878993 100644 --- a/pdf/doc.tex +++ b/pdf/doc.tex @@ -904,7 +904,7 @@ DNA-Backup stocke le contenu de ce fichier comme une liste de structures \verb|F 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}. +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] @@ -966,80 +966,79 @@ par exemple le tout dernier chunk du disque virtuel. \begin{enumerate} \item - Chargement des métadonnées du \emph{repo} afin de reconstruire en + 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 \emph{recipe} à partir des deltas de chaque + Reconstruction de la recipe à partir des deltas de chaque version. \item Reconstruction du listage des fichiers à partir des deltas de chaque - version (fichier \emph{files}). + version (fichier \verb|files|). \item - Reconstruction en mémoire des \emph{maps} de \emph{fingerprints} et - de \emph{sketches} à partir des fichiers \emph{hashes} de chaque + 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 \emph{source}. + Listage des fichiers de la 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} + 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'une 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 - 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). + 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 - 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). + 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 - 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} + 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 (\emph{files} et \emph{recipe}) et stockage des deltas - ainsi obtenus. + 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 \emph{repo} afin de reconstruire en + 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 \emph{recipe} à partir des deltas de chaque - version. + Reconstruction de la recipe à partir des deltas de chaque version. \item - Reconstruction du listage des fichiers à partir des deltas de chaque - version. + 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}). + À partir de la recipe, reconstruire le disque virtuel. \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}. + 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} Le dossier \verb|exp| contient les scripts permettant de reproduire |