1

IH* – Hachage Multidimensionnel Distribué et Scalable

BOUKHELEF DjelloulÉtudiant en PhD, Institut National d’Informatique (INI), Alger. Algérie

E-mail: boukhelef_dj@yahoo.fr

Directeur de thèse : Pr D-E. ZEGOUR

2

Partie I:

Structures de données Distribués et Scalables

3

Serveurs

Clients

Répertoired'accès

Structures de données classiques

Schémas de distribution classiques : Partitionnement par intervalle, Partitionnement par hachage, Round-Robin , …

Mécanisme de calcul d'adresse unique et centralisé un point d'accumulation Limite sur les performances d'accès Vulnérabilité aux pannes Scalabilité et Disponibilité

Duplication du calcul d'adresse MAJ synchrones des clients:

Impossible pour un grand nombre de clients distribués et autonomes

4

SDDS – Structures de Données Distribuées et Scalables

Conçues spécifiquement pour les multiordinateurs

Une collection d'ordinateurs, Stations de travail, faiblement couplés (à partage de rien, shared nothing) interconnectés par un réseau informatique (MAN, LAN, WAN)

Une nouvelle classe de structures de données pour des bases de données modernes

D’une grande taille (GO – TO) Avec des données complexes: spatiales, géographiques, Image, Son, …

Scalables Grandissent rapidement en gardant les mêmes performances

Haute disponiblilité et disponibilité incrémentale (scalable availability)

5

SDDS – Axiomes généraux (1)

Les données sont identifiées par des clés (d1), OID pour les objets

Les données sont stockées sur des serveurs et sont accédées par des clients autonomes

Il n'y a pas de répertoire central d'accès Image locale par client Mécanisme de vérification et de redirection des requêtes Mécanisme de mise à jour distribué des images des clients

Les MAJ de la structure d'une SDDS ne sont pas envoyées aux clients de manière synchrone

6

SDDS – Axiomes généraux (2)

Un client peut faire des erreurs d'adressage suite à une image inadéquate de la structure de SDDS

Chaque serveur vérifie l'adresse de la requête et l'achemine vers un autre serveur si une erreur est détectée

Le serveur adéquat envoie un message correctif (Image Adjustment Message, IAM) au client ayant commis l'erreur d'adressage

Le client ajuste son image local pour ne plus faire, au moins, la même erreur

7

SDDS – Axiomes généraux (3)

i’ = 0n’ = 0

0 1

0 1 2 3 4

Level = 2Next = 1

Correction d’image Level = 2

Requête h0(k) = 1

Réponse

Redirectioni’ = 2n’ = 0

Ajustement de l’image

locale

8

SDDS – Contraintes (1)

Si une SDDS n'évolue plus, alors les IAM font converger toute image d'un client vers l'image actuelle du fichier

L'ensemble des renvois à la suite d'une erreur d'adressage ne se fait qu'en quelques messages

Performance d'accès d'une SDDS Nombre de messages sur le réseau (indépendante des

paramètres du réseau) Nombre de messages par opération Vitesse de convergence de l’image d’un nouveau client

9

SDDS – Contraintes (2)

Scalabilité Prendre en charge n’importe quelle quantité de données

pas de limite théorique de la taille, pas de réorganisation totale de la structure

Maintenir les performances quand le volume de données stockées varie: temps d ’accès constants

Distribution Une grande quantité de données Traitement parallèle et distribué Non vulnérabilité aux pannes

Disponibilité Assurer la continuité du fonctionnement 24 heures sur 7

jours

10

SDDS – Typologie

Arbre Hachage

DisponibilitéLH*m, LH*g

DisponibilitéLH*m, LH*g

SécuriséLH*s

SécuriséLH*s

ClassiquesClassiquesSDDSSDDS

1-d-ArbreDRT, DRT*,

RP*

1-d-ArbreDRT, DRT*,

RP*

k-d-ArbreDistributed B+

k-RP*

k-d-ArbreDistributed B+

k-RP*

d-dimensionnel

IH*d-dimensionnel

IH*

1-dimensionnelLH*, LH*LH

DDH, EH*

1-dimensionnelLH*, LH*LH

DDH, EH*

k-disponibilitéLH*RS, LH*SA

k-disponibilitéLH*RS, LH*SA

Structure de DonnéesStructure de Données

11

SDDS – Travaux en cours à l’INI

IH* Scalable and Distributed Interpolation-Based Hashing

D. Boukhelef

CTH* Scalable and Distributed Compact-Trie-Hashing

D-E. Zegour

TH* Scalable and Distributed Trie-Hashing

M. Aridj

12

Partie II:

Structures de données multidimensionnelles

13

Données multidimensionnelles

Espace de clés K : K = D0D1...Dd-1

Fichier F : F = (r1,r2, ... , rN)

Enregistrement r : r = (k0, k1, ... , kd-1, a0, a1, ... , am) K ;

kj Dj pour 0 j d

D1

D0

Records

K

14

Méthodes d’accès multidimensionnelles

Propriétés

00R 1

0R 11R

20R

22R 2

3R

21R

All

jRK

ji RR

15

IH – Hachage par Interpolation

Proposé par W.A. Burkhard en 1983 Extension du Hachage Linéaire (LH) de Litwin

Principe : clé k = k0, k1, ... , kd-1

Interpolation (shuffle function) Former la signature de k (record signature) Appliquer le LH classique pour décider où se trouve la clé k

Implémentation des requêtes à intervalle : (partial match query & range query).

16

Partie III:

IH* - Adaptation du Hachage par interpolation aux environnements distribués

17

IH* – Hachage par Interpolation Distribué et Scalable

Structure de donnée àbase du Hachage (Linéaire)

Adaptation du IH aux environnements distribuésselon le modèle SDDS

Introduction de l’ordre et l’aspect multidimensionnel à la SDDS LH*

Hachage par Interpolation

Distribué et Scalable (IH*)

Hachage par Interpolation

Distribué et Scalable (IH*)

Hachage Linéaire

Multidimensionnel (IH)

Hachage Linéaire

Multidimensionnel (IH)

Hachage Linéaire

Distribué et Scalable (LH*)

Hachage Linéaire

Distribué et Scalable (LH*)

Hachage Linéaire (LH)Hachage Linéaire (LH)

18

IH* – Structure d’un fichier

Serveurs (j) Stockage de données Evaluation des requêtes des clients

Clients autonomes (i’ , n’) Accès aux données Intermédiaire entre application

et système SDDS

Site Coordinateur (i , n) Maintient les paramètres du fichier Gestion d’éclatement Allocation de sites

Coordinateuri , n

Coordinateuri , n

Client1

i’ , n’

Client1

i’ , n’

Clientn

i’ , n’

Clientn

i’ , n’

Réseaux d’interconnexion

j j j

Serveurs

19

IH* – Évolution du Fichier

0

00R

i = 0 , n = 0i = 0 , n = 0

0

20

IH* – Évolution du Fichier

i = 1 , n = 0i = 1 , n = 0

0 1

11R

10R

0 1

21

IH* – Évolution du Fichier

i = 1 , n = 1i = 1 , n = 1

0

1222R

20R

11R

0 1 2

22

IH* – Évolution du Fichier

i = 2 , n = 0i = 2 , n = 0

0 1 2 3

0

2

1

323R

22R

20R

21R

23

Éclatement d’un serveur

Algorithme SplitServer (n)

1- créer la case (n+2j): niveau j’= j+1

2- éclater la case (n) en utilisant hj+1

3- mettre à jour j j+1

4- confier l’éclatement au site coordinateur

Fin

24

IH* – Eclatement

Éclatement non contrôlé À chaque collision

Éclatement contrôlé Taux de chargement est supérieur / inférieur au

facteur de chargement du fichier

0 1 2

3 4 5 6 7

8 9 10

Splitted Servers Newly created Servers

0

1

2

3

4

5

6 7

8

910

Next server to split (n)

Splitted Servers Newly created Servers

Uniform data distribution Non-uniform data distribution

25

IH* - Éclatement contrôlé

1ère solution : Loi de distribution de données

2ème solution : Négociation entre Coordinateur et Server (n) Garder l’historique des messages de collision

Next server to split (n)

0

1

2

3

4

5

6 7

8

910

Splitted Servers Newly created Servers

Non-uniform data distribution

26

Adressage (1)

i’ = 0n’ = 0

0 1

0 1 2 3 4

Level = 2Next = 1

IAM Level = 2

Requête h0(k) = 1

Réponse

Redirectioni’ = 2n’ = 0

Ajustement de l’image

locale

27

Adressage (2)

i’ = 2n’ = 0

0 1 2 3

Level = 2Next = 3

IAM Level = 3

Requête h2(k) = 2

Réponse

Redirection i’ = 2n’ = 2

Ajustement de l’image

locale

0 1 2 3

4 5 6

28

Requête à intervalles

10

Image du clienti’ = 1 , n’ = 0

1

Image exacteLevel = 2, Next = 3

140

62

5

3

5

3

29

Requête à intervalles

)( )( )( ), , ,()( 1-1-1-1110001-10 dddd uklukluklkkkku,l R

30

Envoi par Diffusion – Principes

i’ = ..n’ = ..

Client

Mécanisme d’envoi

multicast

Requête par intervalle sur

F1

Multiordinateur

F1 0 1 2 3 4 5

F2 0 1 2 3

Serveurs libres

31

Envoi par Diffusion – Critiques

Simple: un envoi pour tous le monde

Multicast n’est pas toujours disponibles sur tous les réseaux

Peut ne pas être efficacement implémenté

Trop de messages sur le réseaux

Problèmes du déterminisme d’envoi et de réception dans le cas des

32

Envoi ciblé (solution LH*)

i’ = 1n’ = 0

Client

Multiordinateur

Level = 2 Next = 3

F1 0 1 2 3 4 65

0 1

Requête à intervalle sur

F1

33

Envoi ciblé – Critiques

Déterministe

Parcours de tous les serveur même pour un petit nombre d’enregistrements

Pas d’ordre dans LH

34

Envoi sélectif (solution IH*)

i’ = 1n’ = 0

Client

Multiordinateur

Level = 2 Next = 3

F1 0 1 2 3 4 65

0 1

Requête à intervalle sur F1

35

Envoi sélectif – Client

Déterminer l’ensemble A des serveurs couvrant la région de Q (Algo Range Query du IH) : A {0, 1, ..., n’+2i’}

Déterminer pour chaque serveur de A la région correspondante en utilisant (n’est pas forni par IH)

Envoyer à chaque serveur de A la sous-requête correspondante;

36

Envoi sélectif – Serveur

Découper la requête reçue en des sous des sous-requêtes plus fines

Déterminer l’ensemble des serveur fils et envoyer à chaque serveur la sous-requête correspondante

Si portée du serveur portée de la sous-requête alors

Exécuter la requête correspondante Retourner(réponse + adresse + niveau)

37

Envoi par décomposition récursive

38

Décomposition récursive – Client

Algorithm Generate_Target_ServersBegin

Compute the set S of target servers: S={s0, s1, ... , sm} {0, 1, ... , n’+2i’-1}

Decompose the range of Q into relevant sub-queries: P ={ q0, q1, ... , qm}

for each server si from S do

Send (qi, j) towards server (si): j i’+1 if (sin) and j i’ otherwiseend for

End

39

Décomposition récursive – Serveur

Algorithm Query_Propagation (Q, j)Begin

Compute the set S of children servers: S={sk, sk+1, ... , sk+m} {a+2j+1, ... , a+2j’’}

where k is the level of sk at the moment of its creation by server (a): j <k j’Decompose the range of Q into relevant sub-queries: P ={ qk, qk+1, ... , qk+m}for each server sk from S do

Send (qk, k) towards server (sk)end for

End

40

Décomposition récursive – Exemple

41

Tests de terminaison

Probabiliste Expiration du timeout

Déterministe Tous les serveurs ont bien répondu

Hybride : Déterministe avec timeout

Déterminer les serveurs manquant Leur retransmettre les messages de requête Retourner à l’application les réponses reçues Signaler au Coordinateur les serveurs n’ayant pas répondu Lancer la procédure de recouvrement

42

Architecture – Serveur / Coordinateur

43

Architecture – Client

44

Architecture – Serveur de noms

45

Module de contrôle de flux

Worker Thread

Window Thread

Sender Threads

Timer Thread

Ack / Error Thread

Worker Thread

Receiver ThreadAnswers FIFO

Ack / Error FIFO

Requests FIFO Non Ack FIFO

Full Win. Pos.

Window

Empty Win. Pos.

PushPop

Input Socket

Output Sockets

46

Implémentations

Environnement Windows (XP, 2000)

Windows - Visual C++ (V6) Protocole plus complet Test et validation des résultats

Java et XML Interopérabilité (Langage, SQL Xquery, …) Portabilité (Windows, Linux, …) Requêtes / Réponses par lot (bulk operations)

47

Visual C++ (V6)

Programmation 100% objet

Interface graphique

MFC & API Windows

TCP, UDP I/O Completion Port, Asynchronous I/O Multithreading

…

Environnement de développement

48

Implémentation – Client

49

Implémentation – Serveur

50

Implémentation – Manager / Agent

51

Partie IV:

Conclusion & perspectives

52

Travaux en cours

Compléter le prototype IH*, mesurer ses performances Rétrécissement du fichier Structure de la case (IH*IH), contrôle d’éclatement Terminaison des requêtes à intervalle et réception de repenses Généraliser le contrôleur de flux, Event-driven : IOCP

Amélioration du schéma IH classique Requêtes à intervalle récursives Détermination de la portée d’une région quelque soit le niveau

actuelle du fichier.

Nouveau schéma de hachage linéaire multidimensionnel Gray code, distance de Hamming Préservation de la localité spatiale (proximity preserving) Meilleur déclustering des données Requête non orthogonales & Recherche au voisinage

53

Travaux futurs

Sécurité & Haute disponibilité récupération sur panne: serveur, coordinateur Sans-coordinateur, coordination distribués

Sauvegarde & restauration : Signature, …

Qualité , Performances : Architectures (Even-driven), communication, … Serveur de noms distribué, Interopérabilité (XML)

Adaptation du IH* au P2P Fully decentrilzed (data & index), fault tolerent SDDS

54

Problèmes ouverts

Plate-forme unifiée pour le test et la validation des systèmes SDDS

SDDS avec coordination et accès complètement décentralisés

Placement des serveurs et équilibrage de charge (données et travail)

Gestion des caches dans les systèmes SDDS

…

55

Merci de votre attention

BOUKHELEF Djelloul

boukhelef_dj@yahoo.fr