LH*rsP2P: une nouvelle Structure de Données Distribuée et

Scalable pour un environnement pair à pair

Présenté par H.YAKOUBEN

Dirigé par le Pr. W. LITWIN

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 214/09/2006

PLAN

Objectifs du stage État de l’art LH*P2P et LH*rsP2P Architecture fonctionnelle de LH*rsP2P Domaine d’application Conclusion et perspectives

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 314/09/2006

Conception d’une nouvelle SDDS pour un environnement pair à pair

Une SDDS à haute disponibilité Elle réduit le nombre de renvoi à un seul au

maximum d’une requête à clé Conception et implémentation d’une nouvelle

architecture fonctionnelle à base de LH*rs.

Objectifs

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 414/09/2006

Clients

Croissance par des éclatements

serveur

Structure de Données Distribuées et Scalables (SDDS) principes

pair

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 514/09/2006

Structure de Données Distribuées et Scalables (SDDS), principes

Clients

Image A

juste

ment

Mess

age

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 614/09/2006

Classification des SDDS

LH*sa

SDDS(1993)

Structure de Données

Classique

Arbre

m-d arbre1-d arbre

RP*, BATON

k-RP*DRT, DRT*, VBI-Tree

LH*,LH*LH

DDH, EH*, CHORD

Hachage

Haute Disponibilité

1-dimensionnel d-dimensionnel

IH*

LH*rs LH*s

s-disponibilité Sécurité

LH*m LH*g

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 714/09/2006

Le ‘Churn’ LH*rs

Structure de Données Distribuées et Scalables (SDDS)

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 814/09/2006

Architecture fonctionnelle de LH*rs

Structure de Données Distribuées et Scalables (SDDS)

Client nClient 2Client 1

ApplicationApplicationApplication

Serveurs de paritésServeurs de données

Réseau

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 914/09/2006

Hachage linaire distribué et scalable Pair à PairLH*P2P et LH*rsP2P

Pair LH*rs

Client LH*rs

ServeurLH*rs

Pair LH*rs

j

i’n’

Partie client

Partie serveur

Pair LH*P2P

Pair LH*rsP2P

Client LH*rs

ServeurLH*rs

Pair candidat

Pair candidat

Pair LH*rsP2P

Conception d’un pair

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1014/09/2006

Hachage linaire distribué et scalable Pair à PairLH*P2P et LH*rsP2P

Éclatement d’un pairi’ = j  ; /* Image du niveau i du fichier

n ‘ = m +1 ; /* Image du pointeur n d’éclatement

if n’ = 2i’ then i’ = j + 1 ;  n’ = 0 ; /* Correction si le pointeur doit revenir à zéro */

Algorithme

Adressage

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1114/09/2006

Hachage linaire distribué et scalable Pair à PairLH*P2P et LH*rsP2P

Avant l’éclatement

Pair Coordinateur (PC)

P0

j=2

i’=1n’=1

P2P1i=1n=1

j=1

i’=1n’=0

j=2

i’=1n’=1

Après éclatement

j=2

i’=2n’=0

PC

P0

j=2

i’=1n’=1

P2P1i=2n=0

j=2

i’=2n’=0

j=2

i’=1n’=1

P3

i’= j =1;n’= m+1= 1+1;

If n’=21 then n’=0; i’= i’+1Donc

(i’, n’)= (2,0)

Exemple

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1214/09/2006

Hachage linaire distribué et scalable Pair à PairLH*P2P et LH*rsP2P

Calcul d’une adresse du côté client (du pair)

a’ hi’(C ) ; /* a’ est l’adresse du pair destiné à recevoir la clé C*/

if a’ < n’ then a hi’+1(C ) ; Algorithme

Calcul d’une adresse, du côté serveur du paira’ hj(C ) ; if a’ a then /* en cas d’erreur d’adressage*/a” hj-1(C ) ; /* a” l’adresse destinée à recevoir la clé C */if a”> a and a”<a’ then a’ a”;

Algorithme

Adressage

Ajustement de l’image du pair

i’ j-1, n’ a+1 ; /* a est l’adresse du bon pair*/if n’> 2i’ then n’0 ; i’ i’+1 ;

Algorithme

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1314/09/2006

Insertion d’un nouveau noeud

Hachage linaire distribué et scalable Pair à PairLH*P2P et LH*rsP2P

PC

i=2n=2

P0

j=3

i’=2n’=1

Pairs

P2

j=2

i’=1n’=1

P5

j=3

i’=2n’=2

Pair candidat

i’=0n’=0

P6

j=3

i’=2n’=3

i=2

n=3

i’=2n’=3

j=3

Pupille

i’=2n’=1

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1414/09/2006

Hachage linaire distribué et scalable Pair à PairLH*P2P et LH*rsP2P

PC

i=3n=2

P0

j=4

i’=3n’=1

Pairs

P4

j=3

i’=2n’=2

P9

j=4

i’=3n’=2

P1

j=4

i’=3n’=2

9

9

IAM

Exemple de recherche

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1514/09/2006

Architecture fonctionnelle du système‘LH*rsP2P’

Éclatement d’une case LH*rsP2P

Pair/Serveur n Pupille 1 Pupille k Pair/Serveur n+2^i

{hachage des clés et adresse IP de ces pupilles} Articles + les adresses IP des pupilles

MiseAJourTuteur

ensembles des pupilles qui seront sous le tutorat du nouveau noeud

{Mise à jour de son image si c'est un pair}

la mise a jour des pupilles qui restentAccusé Ack

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1614/09/2006

Traitement du ‘Churn‘

Architecture fonctionnelle du systèmeLH*rsP2P

Pair/ Client Pair/Serveur k -1 Pair/ serveur k Pair /Serveur K+1 Case de parité 1

recherche d' un article

pas de reponse

recherche d' un article

renvoi de la requête

{ traitement de la requêtede recherche d' article}

Article rechercher + IAM

Pair/Serveur m Case de parité 2

Case de paritéCase de données

reconstruction de la case k

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1714/09/2006

Attribution d’un tuteur aux nouveaux sites

Architecture fonctionnelle du systèmeLH*rsP2P

1 2 3 ð Numéro logique des tuteurs

...

(NuméroEntité, AdresseIP)

T2

Déclaration de candidature

PairCandidat(IDMessage, AdresseIP) Éclatement de la case d’un pair

MiseAJourTuteur(IDMessage, NF_j, NuméroLogique, AdresseIPTuteur,NumeroEntité)

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1814/09/2006

Domaine d’application de LH*rsP2P : le projet eGov

eGov vise l’intégration des services publics Il permet de développer une plate-forme intégrée

visant la réalisation d’un guichet administratif qui soit : Ouvert Évolutif Extensible

eGov offre un vocabulaire « GovML » standard pour la description des services publics.

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 1914/09/2006

Exemple d’un document GovML [KT5] <?xml version=‘’1.0’’ encoding=‘’ UTF-8’’?>

<govml:GovML xmlns:govml=‘’http://egov-projet.org/GovMLScheme/ ‘’xmlns:xsi=‘’http://www.w3.org/2001/XMLSchema-instance’’xsi:schemaLocation=‘’http://egov-projetct.org/GovMLSchema/ file:///C:/temp/GovMLSchema.xsd>

<description xsi:type=‘’govml:SpecificLifeEventDescription’’><identifier>ABC1234H</identifier><language>EN </language><title>Description of the life event’’getting maried’’ </title><description> Getting married</description> <attention> This life event conccenes only adults </attention><faq-list> <item>

<question>Is there a possiblity toà get married online? </question><answer>Yes. Visiste the national governmental portal </answer>

</item> </faq-list><related-services> <item>

<title>Issuing a birth certificate </title><uri>http://www.egovproject.org\birth#</uri>

< /item></related-services><law>Law withe nhimber FRC-234</law>

</description></govml:GovML>

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 2014/09/2006

WAP/GSM

user

Internet

user

Portal

one-stop

e-government

GovML GovML

GovML

Local authority

Public

Local services

repository

Local authority

Public

Local services

repository

National authority

Public

National services

repositoryComment gérer

les ‘Virtual Repository’

Architecture générale de eGov

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 2114/09/2006

Application de LH*rsP2P

Wrapper Wrapper

Virtual Repository

réseau

SD-SQL Server LH*rsP2P

sd_select ‘* from.. Search key ‘ABC1234H’

pour les documents

‘GovML’ peu volumineux et

souvent utilisés

pour les documents ‘GovML’

volumineux et rarement utilisés

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 2214/09/2006

Conclusion et perspectives LH*rsP2P réduit le nombres de renvois de deux à un

seul. Résultat impossible à améliorer LH*rsP2P offre la disponibilité en cas de panne d’un site LH*rsP2P palie au ‘Churn’

Étude expérimentale de LH*rsP2P sur la base de la généralisation du prototype LH*rs

Application aux documents réels de GovML Étude de variantes de LH*rsP2P.

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 2314/09/2006

Références [G01] Glassey O , EPFL. Isps.ch newsletter n)11.10/2001

[LNS96] Litwin, W., Neimat, M.-A. & Schneider, D. LH*: A Scalable Distributed Data Structure. ACM-TODS, Dec. 1996.

[LNS93a] Litwin, W., Neimat, M.-A. & Schneider, D. Linear Hashing for Distributed Files. ACM-SIGMOD International Conference on Management of Data, 1993.

[LNS93b] Litwin, W., Neimat, M-A. & Schneider, D. LH*: A Scalable Distributed Data Structure. Submitted for journal publ. Nov. 1993.

[LMS05] Litwin W, Moussa R, Schwarz T: LH*RS – A Highly-Available Scalable Distributed Data Structure. ACM-TODS, Sept. 2005.

[LRS02] Litwin, W. & Sahri, S. Implementing SD-SQL Server: a Scalable Distributed Database System. Intl. Workshop on Distributed Data and Structures, WDAS 2004, Lausanne, Carleton Scientific (publ.).

[LSS06a] Litwin, W., Sahri, S. & Schwarz, Th. Scalable Command Processing in SD-SQL Server: a Scalable Distributed Database System. 7th Intl. Workshop on Distributed Data and Structures (WDAS-7) Santa Clara, CA, 2006.

[KT5] Gregory Kavadias and Efthimios Tambouris GovML: A Markup Language for Describing Public Services and Life Events . Archetypon S.A., 236 Sygrou Av., Athens, 176-72, Greece {gkavadias, tambouris}@archetypon.gr

[LMS6] Litwin ,W, Mokadem R, Sahri S. Virtual Repository for eGov Life Event Documents. CERIA 2006

LH*rsP2P: une nouvelle SDDS pour un environnement pair à pair 2414/09/2006

j=i+1 j=i+1

j=i

2i n+2in0