Réunion DataGraal 30-31 Janvier 2003 Grenoble Tolérance aux fautes et passage à léchelle Pierre Sens

Réunion DataGraal 30-31 Janvier 2003

Grenoble

Tolérance aux fautes et passage à l’échelle

Pierre Sens

DataGraal – Grenoble 30-31 Janvier 2003

Généralités sur la tolérance aux fautes

But : fournir des garanties de fiabilité en cas de défaillance permettre la continuité de l'exécution lorsque l'un des nœuds ne répond plus

1. Types de fautes

2. Détection de fautes

3. Traitement des fautes : Réplication

4. Exemple : DARX


Types de fautes

Franche (fail-silent, crash)• Arrêt permanent

Omission (recovery)• Transitoire

Temporaire• Trop tôt ou trop tard

Byzantin• malicieux


Problèmatique de la détection

Très dépendant du modèle temporel Réseau synchrone : délai de transmission / traitement

borné et connus• Détection sûre => Fournir une liste de site en panne

Réseau asynchrone : pas de délai• Consensus impossible [Fisher Lynch Paterson 85]

Partiellement synchrone : délais bornés inconnus• Pas de solution exacte

• Détecteurs de fautes non fiables [Chandra Toueg 94] => Fournir une liste de suspects

Large échelle

Détection


Techniques de détection

Applicatif (refus de services) Pinging

Heatbeat

Détecteur sur qp up

p down

p up

p

q

Détecteur sur q

p up

p down

p up

p

q

Détection


Réplication

La réplication : méthode de base pour la sûreté de fonctionnement• délais de recouvrement relativement courts

2 principaux mécanismes (stratégies) de réplication :• Active

ActiveSemi-activeCoordinateur-cohorte

• Passive


Réplication active

S1

S2

S3

C

Adapté au temps réel : erreurs masquées Traite les fautes byzantines Serveurs déterministes

requête réponse

Réplication


Réplication semi-active

S1

S2

S3

C

notification

Recouvrement rapide Fautes franches

requête réponse

Réplication


Réplication passive

S1

S2

S3

C

sauvegarde

Temps de recouvrement important Possibilité de non-déterminisme Fautes franches

requête réponse

Réplication


Comparaison des stratégies de réplication

Actives• Surcoût élevé

Degré de réplication N => multiplication des coûts par N

• Très bon recouvrement

Passive• Surcoût moins élevé

La mise à jour des réplicats s'effectue indépendamment du calcul

• Recouvrement plus hasardeux

Les traitements survenus depuis la dernière sauvegarde sont perdus

=> solutions de recouvrement plus coûteuses

Choix de la stratégieSe fait en fonction des contraintes et des besoins applicatifs

active : fortes contraintes de temps, défaillances fréquentes, …

passive : exécution non-déterministe, beaucoup de communication, …

Réplication


Point de reprise (checkpointing)

Sauvegardes régulières sur supports stables Nombreux algorithmes, 2 approches Points de reprise coordonnés

• Sauvegarde d’un état global cohérentPose de point de reprise coûteuxPas de contrôle de sauvegardeRecouvrement lent

Points de reprise indépendant• Assurer la cohérence => effet domino

• Journalisation de message => reprise confinée, coût des communication


Constats

La plupart des plates-formes sont peu adaptées au large échelleEloignement => Forte latence des protocoles à 3 phaseNombre de sites => Coût en ressources (réseau)Dynamicité => Approche statique (stratégie figée ou guidée par

l'utilisateur)Topologie => Partitionnement

Modèle de faute restreint (crash, recovery)Tendance à élargir vers fautes byzantines (dans P2P)Outils : librairie BFT, pb très coûteux !


Réplication dans systèmes P2P

Réplication complète de données immutables (PAST)

Réplication de données modifiables par peu d’ecrivain (Ivy)

Réplication avec information redondante(type RAID) • OceanStore

• N3FS (Turin)


Comparatif

FarSite (MSR) OceanStore (UCB) Pasta (RUT) Pangaea (HP Labs)

Mutable files yes yes (version numbers) yes yesDuplicate handling SIS (2) ? on a per-block basis (3) ?

Update granularity ? on a per-block basis on a per-block basis (3) ?

File replication factor server-availability driven (3-4 copies) request- and system-load driven user-specified ? on demand replication (100+)

Replicas location within small geographical area within pools primary store node leafset anywhere (pervasive replication)

# [Concurrent] writers ? ? ? ?Writers location anywhere ? ? ?

Mobility handling yes (local cache)yes (local cache + optimistic

concurrency control)?

yes (local cache + optimistic concurrency control)

Consistency protocollazy update (for temporary files and

increased availability)from weak to ACID consistency,

using per-block conflict resolution (1)

close-to-open consistency model, multicast cache invalidation

messages

optmistic concurrency control, epidemic back-ground update

propagation

Specific nodes involved ?responsible party for request

serializationprimary store node, for invalidate

messages subscriptionnone

Tolerance to partitionning local cache + ?local cache + optimistic

concurrency controllocal cache + ?

local cache + optimistic concurrency control

Target configuration 105 severs, 1010 files, 1016 bytes 1010 users, 1014 files ? 103+ trusted servers, 109 files

Largest implementation only analysis and simulation ?conflict resolution and routing facility

already developpedbeing incorporated in Xenoserver

project under development

Notes(1) derived from Bayou system(2) Single Instance Storage (Windows 2000)(3) content-based chunking"?": not explicitly specified


Expérience de passage à l’échelle au LIP6

Projet DARX : Plate-forme pour système multi-agents Equipe OASIS (S. Aknine, JP Briot, Z. Guessoum)

Equipe SRC (M. Bertier, O. Marin, P. Sens)

Agent

Adaptateur

Réplication

Détection de défaillances

Contrôle de réplication

adaptatifObservation

DARX

SMA

Nommage/Localisation


Approche

Rendre la tolérance aux fautes dynamique & personnaliséeQualité de service exprimée par l ’agent

(criticité, nombre et type de fautes acceptés, ...)

+Observation de l ’évolution de l ’environnement

(latence, temps d’accès, taux de fautes, ...)

Adaptation aux contraintes dynamiques de l’environnement Domaines applicatifs visés

• Simulation à large échelle

• Qualité de service dynamique : gestion de crise(exemple : nuage toxique)

• Collecte d’information à large échelle

• Domotique

Stratégie au runtime

DARX



Agent

Adaptateur

Réplication




SMA


DARX

DARX


Organisation des détecteurs de défaillances

But

• S’abstraire des problèmes de synchronisme

• Optimiser le temps de recouvrement Organisation hiérarchique Un module de nommage par site et un module de détection

sous-réseau 1

sous-réseau 3

sous-réseau 2

A G

H

FD

E

C

DARX - Détection

B


Fonctionnement

Diffusion de « heartbeats » Défaillances : Crash / Recovery Composé de 2 couches :

• Détection de base

• Adaptation de la qualité de service à l’application

Adaptable :• Estimations dynamiques

• Intervalle d’émission

Utilisation d’IP-multicast Permet le transport d’information

DARX - Détection


Performances

Adaptation :• Court terme (Marge)• Moyen terme (date)

Détection Darx RTT Chen

Fausses détections 24 54 29

Durée d’erreur (ms) 31,6 25,23 36,61

Temps de détection (ms) 5131,7 5081,79 5672,53

DARX - Détection


Expérimentation à large échelle

Utilisation de dummynet pour simuler la latence réseau

DARX - Détection

Ajout latencePerte

LAN 1

LAN 2

LAN 3


Comparaison Hiérarchique / Plat

DARX - Détection

60 ms

20 ms

80 ms


Réplication

Agent

Adaptateur

Réplication




SMA


DARX

DARX - Réplication


Stratégies de réplication

4 stratégies de réplication:• active

tous les réplicats traitent les requêtes

• passive

seul le réplicat primaire traite les requêtes

• semi-active

comme active, mais un seul réplicat répond

• quorum

réduction du nombre de copies à jour

DARX - Réplication


Dynamicité

A tout moment l’agent peut :• Ajouter/retirer un réplicat

• Changer la stratégie

• Changer les mécanismes internes (Modifier la fréquence de mise à jour des copies ...)

• Stratégies hybrides

DARX - Réplication


Philosophes

Philosophes

Table = 1 agent répliqué activement

Philosophe = agent à 3 états :• Stateless : Philosophe pense

• Localstate : Philosophe demande les couverts

• Globalstate : Philosophe possède les couverts et mange


Performance sur application

Documents

Réunion DataGraal 30-31 Janvier 2003 Grenoble Tolérance aux fautes et passage à léchelle Pierre Sens