of 55/55
1 IH* – Hachage Multidimensionnel Distribué et Scalable BOUKHELEF Djelloul Étudiant en PhD, Institut National d’Informatique (INI), Alger. Algérie E-mail: [email protected] Directeur de thèse : Pr D-E. ZEGOUR

1 IH* – Hachage Multidimensionnel Distribu é et Scalable BOUKHELEF Djelloul É tudiant en PhD, Institut National d Informatique (INI), Alger. Algérie E-mail:

  • View
    109

  • Download
    2

Embed Size (px)

Text of 1 IH* – Hachage Multidimensionnel Distribu é et Scalable BOUKHELEF Djelloul É tudiant en PhD,...

  • Page 1
  • 1 IH* Hachage Multidimensionnel Distribu et Scalable BOUKHELEF Djelloul tudiant en PhD, Institut National d Informatique (INI), Alger. Algrie E-mail: [email protected] Directeur de thse : Pr D-E. ZEGOUR
  • Page 2
  • 2 Partie I: Structures de donn es Distribu s et Scalables
  • Page 3
  • 3 Serveurs Clients Rpertoire d'accs Structures de donn es classiques Schmas de distribution classiques : Partitionnement par intervalle, Partitionnement par hachage, Round-Robin, Mcanisme de calcul d'adresse unique et centralis un point d'accumulation Limite sur les performances d'accs Vulnrabilit aux pannes Scalabilit et Disponibilit Duplication du calcul d'adresse MAJ synchrones des clients: Impossible pour un grand nombre de clients distribus et autonomes
  • Page 4
  • 4 SDDS Structures de Donn es Distribu es et Scalables Conues spcifiquement pour les multiordinateurs Une collection d'ordinateurs, Stations de travail, faiblement coupls ( partage de rien, shared nothing) interconnects par un rseau informatique (MAN, LAN, WAN) Une nouvelle classe de structures de donnes pour des bases de donnes modernes Dune grande taille (GO TO) Avec des donnes complexes: spatiales, gographiques, Image, Son, Scalables Grandissent rapidement en gardant les mmes performances Haute disponiblilit et disponibilit incrmentale (scalable availability)
  • Page 5
  • 5 SDDS Axiomes g n raux (1) Les donnes sont identifies par des cls (d1), OID pour les objets Les donnes sont stockes sur des serveurs et sont accdes par des clients autonomes Il n'y a pas de rpertoire central d'accs Image locale par client Mcanisme de vrification et de redirection des requtes Mcanisme de mise jour distribu des images des clients Les MAJ de la structure d'une SDDS ne sont pas envoyes aux clients de manire synchrone
  • Page 6
  • 6 SDDS Axiomes g n raux (2) Un client peut faire des erreurs d'adressage suite une image inadquate de la structure de SDDS Chaque serveur vrifie l'adresse de la requte et l'achemine vers un autre serveur si une erreur est dtecte Le serveur adquat 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 mme erreur
  • Page 7
  • 7 SDDS Axiomes g n raux (3) i = 0 n = 0 01 0 1234 Level = 2 Next = 1 Correction dimage Level = 2 Requte h 0 (k) = 1 Rponse Redirection i = 2 n = 0 Ajustement de limage locale
  • Page 8
  • 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'accs d'une SDDS Nombre de messages sur le rseau (indpendante des paramtres du rseau) Nombre de messages par opration Vitesse de convergence de limage dun nouveau client
  • Page 9
  • 9 SDDS Contraintes (2) Scalabilit Prendre en charge nimporte quelle quantit de donnes pas de limite thorique de la taille, pas de rorganisation totale de la structure Maintenir les performances quand le volume de donnes stockes varie: temps d accs constants Distribution Une grande quantit de donnes Traitement parallle et distribu Non vulnrabilit aux pannes Disponibilit Assurer la continuit du fonctionnement 24 heures sur 7 jours
  • Page 10
  • 10 SDDS Typologie ArbreHachage Disponibilit LH* m, LH* g Disponibilit LH* m, LH* g Scuris LH* s Scuris LH* s Classiques SDDS 1- d -Arbre DRT, DRT*, RP* 1- d -Arbre DRT, DRT*, RP* k - d -Arbre Distributed B + k -RP* k - d -Arbre Distributed B + k -RP* d -dimensionnel IH* d -dimensionnel IH* 1-dimensionnel LH*, LH* LH DDH, EH* 1-dimensionnel LH*, LH* LH DDH, EH* k -disponibilit LH* RS, LH* SA k -disponibilit LH* RS, LH* SA Structure de Donnes
  • Page 11
  • 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
  • Page 12
  • 12 Partie II: Structures de donn es multidimensionnelles
  • Page 13
  • 13 Donn es multidimensionnelles Espace de cl s K : K = D 0D 1...D d-1 Fichier F : F = (r 1,r 2,..., r N ) Enregistrement r : r = (k 0, k 1,..., k d-1, a 0, a 1,..., a m ) K ; k j D j pour 0 j d D1D1 D0D0 Records K
  • Page 14
  • 14 M thodes d acc s multidimensionnelles Propri t s
  • Page 15
  • 15 IH Hachage par Interpolation Propos par W.A. Burkhard en 1983 Extension du Hachage Lin aire (LH) de Litwin Principe : cl k = k 0, k 1,..., k d-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 requtes intervalle : (partial match query & range query).
  • Page 16
  • 16 Partie III: IH* - Adaptation du Hachage par interpolation aux environnements distribu s
  • Page 17
  • 17 IH* Hachage par Interpolation Distribu et Scalable Structure de donn e base du Hachage (Lin aire) Adaptation du IH aux environnements distribu s selon 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 Linaire Multidimensionnel (IH) Hachage Linaire Multidimensionnel (IH) Hachage Linaire Distribu et Scalable (LH*) Hachage Linaire Distribu et Scalable (LH*) Hachage Linaire (LH)
  • Page 18
  • 18 IH* Structure d un fichier Serveurs (j) Stockage de donn es Evaluation des requtes 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 Coordinateur i, n Coordinateur i, n Client 1 i, n Client 1 i, n Client n i, n Client n i, n Rseaux dinterconnexion jjj Serveurs
  • Page 19
  • 19 IH* volution du Fichier 0 i = 0, n = 0 0
  • Page 20
  • 20 IH* volution du Fichier i = 1, n = 0 0 1 0 1
  • Page 21
  • 21 IH* volution du Fichier i = 1, n = 1 0 1 2 0 1 2
  • Page 22
  • 22 IH* volution du Fichier i = 2, n = 0 0 123 0 2 1 3
  • Page 23
  • 23 clatement d un serveur Algorithme SplitServer (n) 1- cr er la case (n+2 j ): niveau j = j+1 2- clater la case (n) en utilisant h j+1 3- mettre jour j j+1 4- confier l clatement au site coordinateur Fin
  • Page 24
  • 24 IH* Eclatement clatement non contrl chaque collision clatement contrl Taux de chargement est sup rieur / inf rieur au facteur de chargement du fichier 01 2 3 4567 8910 Splitted ServersNewly created Servers 0 1 2 3 4 5 67 8 9 10 Next server to split (n) Splitted ServersNewly created Servers Uniform data distributionNon-uniform data distribution
  • Page 25
  • 25 IH* - clatement contrl 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 67 8 9 10 Splitted ServersNewly created Servers Non-uniform data distribution
  • Page 26
  • 26 Adressage (1) i = 0 n = 0 01 0 1234 Level = 2 Next = 1 IAM Level = 2 Requte h 0 (k) = 1 Rponse Redirection i = 2 n = 0 Ajustement de limage locale
  • Page 27
  • 27 Adressage (2) i = 2 n = 0 0 123 Level = 2 Next = 3 IAM Level = 3 Requte h 2 (k) = 2 Rponse Redirection i = 2 n = 2 Ajustement de limage locale 0123 456
  • Page 28
  • 28 Requte intervalles 1 0 Image du client i = 1, n = 0 1 Image exacte Level = 2, Next = 3 140 62 5 3 5 3
  • Page 29
  • 29 Requte intervalles
  • Page 30
  • 30 Envoi par Diffusion Principes i =.. n =.. Client Mcanisme denvoi multicast Requte par intervalle sur F 1 Multiordinateur F1F1 012345 F2F2 0123 Serveurs libres
  • Page 31
  • 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 implment Trop de messages sur le rseaux Problmes du dterminisme denvoi et de rception dans le cas des
  • Page 32
  • 32 Envoi cibl (solution LH*) i = 1 n = 0 Client Multiordinateur Level = 2 Next = 3 F1F1 0123465 01 Requte intervalle sur F 1
  • Page 33
  • 33 Envoi cibl Critiques D terministe Parcours de tous les serveur mme pour un petit nombre d enregistrements Pas d ordre dans LH
  • Page 34
  • 34 Envoi s lectif (solution IH*) i = 1 n = 0 Client Multiordinateur Level = 2 Next = 3 F1F1 0123465 01 Requte intervalle sur F 1
  • Page 35
  • 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-requte correspondante;
  • Page 36
  • 36 Envoi s lectif Serveur D couper la requte re ue en des sous des sous-requtes plus fines D terminer l ensemble des serveur fils et envoyer chaque serveur la sous-requte correspondante Si port e du serveur port e de la sous-requte alors Ex cuter la requte correspondante Retourner(r ponse + adresse + niveau)
  • Page 37
  • 37 Envoi par d composition r cursive
  • Page 38
  • 38 D composition r cursive Client Algorithm Generate_Target_Servers Begin Compute the set S of target servers: S={s 0, s 1,..., s m } {0, 1,..., n +2i -1} Decompose the range of Q into relevant sub- queries: P ={ q 0, q 1,..., q m } for each server s i from S do Send (q i, j) towards server (s i ): j i +1 if (s in) and j i otherwise end for End
  • Page 40
  • 40 D composition r cursive Exemple
  • Page 41
  • 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 requte Retourner l application les r ponses re ues Signaler au Coordinateur les serveurs n ayant pas r pondu Lancer la proc dure de recouvrement
  • Page 42
  • 42 Architecture Serveur / Coordinateur
  • Page 43
  • 43 Architecture Client
  • Page 44
  • 44 Architecture Serveur de noms
  • Page 45
  • 45 Module de contrle de flux Worker Thread Window Thread Sender Threads Timer Thread Ack / Error Thread Worker Thread Receiver Thread Answers FIFO Ack / Error FIFO Requests FIFONon Ack FIFO Full Win. Pos. Window Empty Win. Pos. Push Pop Input Socket Output Sockets
  • Page 46
  • 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, ) Requtes / Rponses par lot (bulk operations)
  • Page 47
  • 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
  • Page 48
  • 48 Impl mentation Client
  • Page 49
  • 49 Impl mentation Serveur
  • Page 50
  • 50 Impl mentation Manager / Agent
  • Page 51
  • 51 Partie IV: Conclusion & perspectives
  • Page 52
  • 52 Travaux en cours Compl ter le prototype IH*, mesurer ses performances R tr cissement du fichier Structure de la case (IH* IH ), contrle d clatement Terminaison des requtes intervalle et r ception de repenses G n raliser le contrleur de flux, Event-driven : IOCP Am lioration du sch ma IH classique Requtes 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 Requte non orthogonales & Recherche au voisinage
  • Page 53
  • 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
  • Page 54
  • 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
  • Page 55
  • 55 Merci de votre attention BOUKHELEF Djelloul [email protected]