Sauvegarde et dissémination dans MoSAIC
Ludovic Courtès
LAAS-CNRS
Sauvegarde des données : résumé
Soumission à MobiHoc : plan de l'article -- Contraintes sur les mécanismes de stockage -- Solutions proposées issues de l'état de l'art -- Solutions proposées : fragmentation & indexation -- Évaluation des solutions : cas de test -- Évaluation des solutions : conclusion -- 

1 / 15 -- Soumission à MobiHoc : plan de l'article


2 / 15 -- Contraintes sur les mécanismes de stockage


3 / 15 -- Solutions proposées issues de l'état de l'art
Détection d'erreurs
  • fonctions de hachage cryptographiques (SHA*, Whirlpool, etc.)
Compression
  • stockage à instance unique
  • découpage fonction du contenu
  • compression sans perte "classique"
  • voire compression à perte spécifique (images, sons, etc.)
An illustration
4 / 15 -- Solutions proposées : fragmentation & indexation
Fragmentation
  • fragmentation
  • indexation de blocs individuels
  • indexation de séquences de blocs ⇒ méta-données

An illustration


5 / 15 -- Évaluation des solutions : cas de test
  1. Fichiers en "écriture seule"
    • ensemble de fichiers PostScript
    • peu voire pas de ressemblance entre eux
    • format "verbeux", non compact
  2. Versions successives de fichiers textes
    • ensemble de fichiers sources C
    • beaucoup de ressemblances
    • format non compact
  3. Un fichier texte
    • boîte aux lettres (format mbox)
    • format non compact


6 / 15 -- Évaluation des solutions : conclusion
Critères d'évaluation
  • taux de compression
  • débit lors du traitement ≈ consommation CPU
Résultats
  • compression "classique" (type gzip) indispensable
  • stockage à instance unique bénéfique et "gratuit"
  • découpage fonction du contenu (algo. de Manber) limité

Codes d'effacement
Codes d'effacement : définitions -- Codes d'effacement : exemples -- Impact sur la disponibilité et le coût de stockage -- Codes d'effacement et disponibilité -- 

7 / 15 -- Codes d'effacement : définitions
Définition
  • message de b blocs → b × S blocs
  • m blocs suffisent pour recouvrir le message, b < m < (S × b)
  • S ∈ℜ : "amplification" (ou stretch factor, overhead)
  • défaillances tolérées : (S × b) - m
Codes optimaux (Maximum Distance Separable)
  • quand m = b ⇒ défaillances tolérées : (S × b) - b
  • notation : code (n,k) ⇔ S = (n / k) et n - k défaillances tolérées
An illustration
8 / 15 -- Codes d'effacement : exemples
Exemples
  • code (3,1) : 2 défaillances tolérées, S = 3
  • code (5,3) : 2 défaillances tolérées, S = 1.67

An illustration


9 / 15 -- Impact sur la disponibilité et le coût de stockage
Disponibilité d'une donnée D
  • Hypothèse : S × b fragments, chacun stocké chez un contributeur différent
  • μ : probabilité qu'un contributeur soit disponible en un instant quelconque
  • An illustration
Problèmes
  • impact de μ sur la disponibilité des données ?
  • impact du nombre de blocs b ?
  • impact du facteur de réplication S ?


10 / 15 -- Codes d'effacement et disponibilité
Conclusions
[Lin et al. 2004]
  • Si (S × μ) > 1, alors choisir b "grand"
  • Si (S × μ) ≤ 1, alors choisir b = 1
Problématiques
  • évaluation dynamique de μ
  • impact de la fragmentation et de la dissémination des fragments sur la disponibilité des données
An illustration

Nouvelles pistes de recherche
Évaluation des protocoles choisis -- Évaluation : une fois les données distribuées -- Évaluation : l'algorithme de dissémination -- Résultats escomptés -- 

11 / 15 -- Évaluation des protocoles choisis
Impact de l'algorithme de dissémination
  • politiques possibles ?
  • impact sur la disponibilité ?
  • impact sur le coût en ressources ? (avec stockage ≈ énergie)
Méthodologie
  • évaluation analytique
  • à partir d'un automate représentant les scénarios de dissémination


12 / 15 -- Évaluation : une fois les données distribuées
Hypothèses
  • réplication simple, N copies distribuées
  • λ : taux de défaillance d'un contributeur
  • β : taux de connexion à Internet d'un contributeur

An illustration


13 / 15 -- Évaluation : l'algorithme de dissémination
Et avant les N copies ?
An illustration
14 / 15 -- Résultats escomptés
Paramètres
  • temps moyen entre deux rencontres
  • temps moyen entre deux connexions Internet
  • temps moyen entre deux défaillances de contributeurs
Résultats
  • probabilité de réussite/échec
  • temps moyen pour arriver à l'état OK
  • et si on utilise des codes d'effacement ?


15 / 15 -- Fin

Questions ?

This HTML page was produced by Skribilo.
Last update: Wed Oct 25 15:11:09+0200 2006