Outline
P-Ring
• Database P2P e stato dell’arte delle
strutture di indice
• Obiettivi dell’architettura P-Ring
• Soluzioni di P-Ring
• Verifiche sperimentali dei risultati
Gruppo 20 – Altini Bonetti Cardone
Database peer - to - peer
P-Ring
Stato dell’arte
Obiettivi
Soluzioni
• Perchè si usano?
– Fault tolerance
– Robustezza
– Scalabilità
(q,r)
Verifiche
• Requisiti
– Query di uguaglianza
– Query di range
Gruppo 20 – Altini Bonetti Cardone
Parametri di performance
P-Ring
Stato dell’arte
1. Load Balancing
– Load imbalance
Obiettivi
|nodoPiuCarico|
Soluzioni
|nodoMenoCarico|
Verifiche
2. Performance di query
(q,r)
(q,r)
Gruppo 20 – Altini Bonetti Cardone
Stato dell’arte
P-Ring
Stato dell’arte
Obiettivi
• Chord
– Basato su hashing
load balanced
– Dati non ordinati
query di range non
supportate
Soluzioni
Verifiche
• BATON*
– Performance di query proporzionali a logdP
– Nessuna garanzia di load balancing
Gruppo 20 – Altini Bonetti Cardone
Hashing di Chord
P-Ring
[0,8)
Massive Attack
Stato dell’arte
Mogwai
[32,40)
[8,15)
Obiettivi
Mono
Soluzioni
Mùm
Verifiche
Munari
[26,32)
[15,26)
Load balancing
Performance di query
Gruppo 20 – Altini Bonetti Cardone
Mantenendo l’ordine?
P-Ring
AB..
Massive Attack
Stato dell’arte
Mogwai
OA..
DA..
Obiettivi
Mono
Soluzioni
Mùm
Verifiche
Munari
MA..
GA..
Load balancing
Performance di query
Gruppo 20 – Altini Bonetti Cardone
Obiettivi di P-Ring
P-Ring
• Supportare query di uguaglianza e di range
Stato dell’arte
Obiettivi
Soluzioni
• Distribuire uniformemente i dati tra i peer
Load balancing
Verifiche
• Garantire routing efficiente dei messaggi
sull’anello
Performance di query
Gruppo 20 – Altini Bonetti Cardone
Data Store
P-Ring
Stato dell’arte
Obiettivi
• Peer divisi in due gruppi:
– Owner peers ( sf ÷ 2sf )
– Helper peers ( scarichi )
sf =  N/P 
Soluzioni
Verifiche
Se viene inserito un elemento in un
peer che ha già 2sf elementi overflow
Se viene cancellato un elemento in un
peer che ha sf elementi underflow
Gruppo 20 – Altini Bonetti Cardone
Data Store - Overflow
P-Ring
Stato dell’arte
P1 [0,8)
Algorithm 1 : p.split()
P5 [32,40)
1: p0 = getHelperPeer();
2: if p0 == null then
3: return;
4: end if
P2 [8,15)
Obiettivi
Soluzioni
Verifiche
P4 [26,32)
P [20,26)
P3 [15,26)
[15,20)
5: //execute the split
6: splitItems = p:own.splitSecondHalf();
7: splitV alue = p:own.lastValue();
8: splitRange = p:range.splitLast(splitV alue);
9: p0::joinRingMsgHandler(p,splitItems,splitRange);
Helper peers
Gruppo 20 – Altini Bonetti Cardone
Data Store - Underflow
Algorithm 3 : p.merge()
P-Ring
Stato dell’arte
1: //send message to successor and wait for result
2: (action; newRange; newItemsList) =
p:ringNode:getSuccessor()::
initiateMergeMsgHandler(p, jp:ownj);
3: p:own.add(newItemsList);
4: p:range.add(newRange);
P1 [0,8)
P5 [32,40)
P2 [8,15)
Obiettivi
Algorithm 4 : (action; newRange; newItemsList)
Soluzioni
Verifiche
P4 [26,32)
[30,32)
P3 [15,26)
[15,30)
p0.initiateMergeMsgHandler(p,numItems)
1: if numItems + jp0:ownj > 2 ¢ sf then
2: //redistribute
3: compute nbItemsT oGive;
4: splitItems = p0:own.splitFirst(nbItemsT oGive);
5: splitV alue = splitItems:lastValue();
6: splitRange = p0:range.splitFirst(splitV alue);
7: return (redistribute,splitRange,splitItems);
8: else
9: //merge and leave the ring
10: splitItems = p0:own;
11: splitRange = p0:range;
12: p0:ringNode:leaveRing();
13: return (merge, splitRange, splitItems);
14: end if
Gruppo 20 – Altini Bonetti Cardone
Risultati
P-Ring
Stato dell’arte
Obiettivi
Soluzioni
Verifiche
• Load imbalance ≤ 2
...siamo proprio sicuri?
Usare gli helper peer per bilanciare
davvero il carico
• Ogni owner è responsabile del suo
range...ma gli elementi sono distribuiti
anche tra gli helper peer
Gruppo 20 – Altini Bonetti Cardone
Overflow
P-Ring
Stato dell’arte
P1 [0,8)
q1 [30,32)
P5 [34,42)
P2 [8,15)
q2 [28,30)
P [32,34)
Obiettivi
P4 [32,34)
Soluzioni
Verifiche
Inserimento su P4
q1 [30,32)
P4 [26,28)
P3 [15,24)
q2 [28,30)
q3 [26,28)
q4 [24,26)
Gruppo 20 – Altini Bonetti Cardone
Usurp
P-Ring
Load balancing ancora non garantito
Stato dell’arte
Esempio:
Obiettivi
Soluzioni
< sf !! < sf!!
< sf!!
Verifiche
sf
Serve un’ulteriore operazione
Gruppo 20 – Altini Bonetti Cardone
Usurp
P-Ring
Algorithm 5 : p.usurp()
Stato dell’arte
P1
Obiettivi
Soluzioni
Verifiche
P2
1: //find least loaded helper peer and its
”master”
2: (q,p0) = getLeastLoadedHelperPeer();
3: if jp.respj ¸ 2p1 + ±jq.respj then
4: p:setHelperPeer(q);
5: redistribute p:own among new set of helpers;
6: redistribute p0:own among new set of
helpers;
7: end if
Load imbalance ≤ 2+ε
Gruppo 20 – Altini Bonetti Cardone
Content Router
P-Ring
Obiettivo: inoltrare efficientemente i messaggi
Stato dell’arte
Problema : dati non uniformi
Obiettivi
(q,r)
Soluzioni
Verifiche
Gruppo 20 – Altini Bonetti Cardone
Problemi di indicizzazione
P-Ring
Stato dell’arte
• Utilizzare tabelle o B+tree? No
– Problema di consistenza
Obiettivi
Soluzioni
Verifiche
• Indicizzare per valore di chiave? No
– Load balancing esplicito non lo
consente (distribuzione non uniforme
dei dati)
• Indicizzare per posizione!
HR
Gruppo 20 – Altini Bonetti Cardone
Hierarchical Ring
P-Ring
Stato dell’arte
•d: ordine dell’anello, intero
positivo > 1
Soluzioni
•Livello 1: primi d successori
del peer
Verifiche
P5
Obiettivi
•Livello 2: peer ogni d hop
•Livello 3: peer ogni d2 hop
•Livello i : peer ogni d(i-1) hop
3
20,P5
2
15,P3 20,P5
1
10,P2 15,P3
P1
5
P2
20
10
18
15
P3
P4
Gruppo 20 – Altini Bonetti Cardone
Content Routing - Esempio
P-Ring
Query di uguaglianza
Valore richiesto 18
Algorithm :
p.routeHandler(lb, up, msg, originator)
find the maximum level l s.t.  j > 0
p.node[l][j].iValue Є (rangeMin(p), lb].
if no such level exists then
Stato dell’arte
send(p.handleMessage(msg),originator);
if rangeMin(succ(p)) Є(rangeMin(p); ub]
then
Obiettivi
send(Route(lb,ub,msg,originator,requestT ype),succ(p))
else
send(RoutingDoneMessage,originator);
end if
else
find maximum k such that
p.node[l][k].iValue Є(rangeMin(p); lb];
send(Route((lb,ub,msg,originator),
p.node[l][k].peer));
end if
Soluzioni
Verifiche
Performance: logdP + m
Gruppo 20 – Altini Bonetti Cardone
Stabilizzazione dell’indice
...e durante inserimenti di peers?
P-Ring Se l’HR non è consistente: caso peggiore scan sequenziale
algoritmo di stabilizzazione
Stato dell’arte
succ()
Obiettivi
p1
Soluzioni
20,p5
Verifiche
15,p3
20,p5
18,p4
5,p1
10,p2
15,p3
15,p3
18,p4
p2
5,p1
• L’algoritmo gira indipendendemente su ogni peer
• È dimostrato che converge
• Performance: logdP + m + 2r(d-1)logdP
Gruppo 20 – Altini Bonetti Cardone
Performance
P-Ring
Stato dell’arte
Obiettivi
• Grafici
(primo, terzo,
Overhead
di traffico
rispettopaio
alla velocità
degli ultimi)
di inserimento degli
elementi
4-5-6 , un
Soluzioni
Verifiche
Supporto alle
query di range
Primo obiettivo raggiunto
Gruppo 20 – Altini Bonetti Cardone
Performance
P-Ring
Stato dell’arte
Obiettivi
Soluzioni
• Grafici (primo, terzo, 4-5-6 , un
paio degli ultimi)
Load imbalance
medio con diverse
distribuzioni di dati
Verifiche
Load
balancing
Secondo obiettivo raggiunto
Gruppo 20 – Altini Bonetti Cardone
Performance
P-Ring
Stato dell’arte
Obiettivi
Soluzioni
• Grafici (primo, terzo, 4-5-6 , un
paio
degli
ultimi)
Costo di ricerca di
un peer al variare
del numero dei
peer
Verifiche
Buone
performance
di query
Terzo obiettivo raggiunto
Gruppo 20 – Altini Bonetti Cardone