Seminar
Service Aspects in ad-hoc and
P2P networks
Database functionality
in
P2P-networks
von
Thorsten Weiberg
Überblick
•
•
•
•
•
•
•
•
•
Motivation und Einleitung
DHT-Systeme
Query Vorgänge in P2P Netzen(PIER)
Mögliche allgemeine Architektur
und Architektur von PIER
Operatoren bei Suchanfragen (Bsp.: Join)
Performance von PIER
Robustheit von PIER
Zusammenfassung und Ausblick
2
1. Einleitung und Motivation
• Peer-to-Peer(P2P) v.a. bekannt durch Filesharing
Programme
• Verteilte Datenbanken sind bisher in ihrer Verteilung
beschränkt.
• Traditionelle Datenbanken werden bisher zentral
verwaltet.
• Versuch Prinzip von P2P auf Datenbanken anzusetzen
(Bsp.: PIER)
3
Einleitung und Motivation(2)
Näherung von der Datenbankseite durch Lockerung der
Designprinzipien:
1.
2.
3.
4.
Konsistenz
Anpassende Skalierung
Natürliche Umgebung von Daten
Standardisierte Schemas über eine populäre Software
4
2. DHT-Systeme
Aufbau:
• Eine(!) Hashtable, deren Daten sich auf allen Knoten
verteilt befinden.
• Jeder Knoten kann Daten speichern.
• Jedes Datum hat einen eindeutigen Schlüssel.
• Herzstück: „overlay“-Routing
Ein DHT-System ist skalierbar und braucht für einen
Lookup O(log n) Hops bei n Knoten.
Nur exaktes Matching!
Bsp. für ein DHT-System: CAN
5
3. Query Vorgänge in P2P(Bsp.: PIER)
• Query Engine:
- weit verbreitet, praktisch nutzbar
- API der dazu verwendet DHT dünn, portabel und
allgemein
• PIER (P2P Information Exchange and Retrieval) ist eine
Query Engine, die Anzahl der teilnehmenden Knoten
vergrößert, ohne dass die Skalierbarkeit darunter leidet.
6
4. Eine allgemeine Architektur
• Drei-Schichten Modell:
QP-Schicht
DHT-Schicht
P2P
Netzwerk
Data Storage Schicht
7
5. Architektur von PIER
8
6. Operatoren bei Suchanfragen
•
•
Operatoren für Selektion, Projektion, Join, Grouping,
Aggregation und Sortieren
Zur Vereinfachung wird nur das JOIN betrachtet:
1. Symmertric hash join
2. Fetch Matches
3. Symmetric semi join
4. Bloom Filter
9
6.1 Symmetric Hash Join
• Join (Equi-Join) über Relationen S und R
• Nutzt DHT-Struktur zum Routen und Speichern von
Tupeln
• Rehashing von R und S
• jeder Knoten lokalen scan in seinem Namesspace NR
und NS ein, um alle R und S Tupel zu lokalisieren.
• jedes Tupel, das alle lokalen Selektionsprädikate erfüllt,
wird in den eindeutigen Namespace NQ kopiert.
• Die Werte für die Join-Attribute werden konkateniert und
bilden so die resourceID der Kopie.
10
6.1 Symmetric Hash Join(2)
• Das Prüfen der Hashtable ist eine lokale Operation in
NQ, die parallel beim Bilden geschieht.
• Jeder Knoten registriert sich in der DHT, um ein newData
Callback zu bekommen.
• Wenn nun ein Tupel eingefügt wird, dann wird in NQ
geprüft, ob sich eine Übereinstimmung mit der anderen
Tabelle ergibt.
• Übereinstimmungen werden an das Prüftupel
angehängt, um Ergebnistupel zu generieren.
• Sie werden dann in zur nächsten Station der Anfrage
(ein anderer DHT Namespace) oder falls sie schon
Ergebnistupel sind, zum Ausgangspunkt der Anfrage
geschickt.
11
6.2 Fetch Matches
•
•
•
•
Variation eines traditionellen Join-Algorithmus
Eine Tabelle ist schon gehashed(hier S)!
auf NR ein lscan durchgeführt
Für jedes Tupel von R wird nun in S auf
Übereinstimmungen durchsucht.
• Bei Übereinstimmung wird nun wie beim symmetric hash
join verfahren.
12
6.3 Symmetrisches Semi Join
• beide Tabellen (R und S) neu gehashed
• Braucht dafür große Bandbreite
• Deshalb: Projektion von R und S auf ihre resourceID und
Join Schlüssel
• Auf diese Projektion wird ein normales symmetrisches
Join ausgeführt.
13
6.4 Bloom Join
• Generieren von Bloom Filtern für alle Knoten für jedes S
und R Fragment
• Diese Filter werden in einer temporären DHT mit den
Namespaces für jede Tabelle gespeichert.
• Filter werden nun alle „verodert“
• Multicast zu allen Knoten, die die entgegensetzte Tabelle
speichern
• Ein Knoten scannt nun sein korrespondierendes
Fragment und rehashed nur Tupel, die mit den Bloom
Filter übereinstimmen.
14
7. Performance von PIER
• Traditionellen Datenbanken Skalierbarkeit in der
Netzwerkgröße gemessen
• Beim Internet: Anzahl der Knoten und
Netzwerkcharakteristik
• Erhöhung #Knoten Erhöhung der Ressourcen
 Latenz steigt
• Flaschenhälse: Latenz und Bandbreite
15
7.1 unendliche Bandbreite
• Unendliche Bandbreite (Messergebnisse bis zum
Erhalt des letzten Tupel), Vergleich der JoinAlgorithmen:
Symmetrischer
Hash
Fetch Matches
Sym. Semi-Join
Bloom Filter
3,73 s
3,78 s
4,47 s
6,85 s
• durchschnittliche Latenz von 0,57 s
• Latenz zwischen zwei Knoten beträgt 0,1 s
• ein Multicast braucht hier etwa 3 s
n = 1024 Knoten
16
7.2 begrenzte Bandbreite
Sinkt die Selektivität von den Prädikaten unter 40% dann ist die
Kapazität der Berechnungsknoten der Flaschenhals. Steigt sie
über 40%, dann ist die „inbound“ Kapazität auf der Anfrageseite
der Flaschenhals.
17
8. Robustheit
• Bemerken von Knotenausfällen mit Hilfe von
Lebenszeichen“
• Bemerken eines Knotenausfalls dauert gewisse Zeit
• Knoten müssen also refreshed werden
• Je höher die Refreshrate desto schneller wird ein Ausfall
bemerkt,
• doch desto höher ist die Netzlast.
18
Zusammenfassung/Ausblick
•
•
•
•
PIER schlägt den richtigen Weg ein
Allerdings noch nicht für‘s Internet geeignet,
aber schon eher für verteilte Datenbanken.
Aufteilung der Schichten lassen möglichst allgemeine DHTs
zu
• Selektion: alle Tupel von R durchsucht (DHT-Schicht), Query
Processor von PIER nicht die Möglichkeit diese Tupel von S
zu filtern. Rationalisierungsbedarf für die Zukunft
• Es können keine Selektionen von nicht-DHT Attributen in der
DHT gespeichert werden.
• Anwendungsgebiete: z.B. Netzwerkmonitorapplikationen und
weit verteilte Systeme (Datenbanken)
19

Database functionality in peer–to