Post on 05-Apr-2015
transcript
PlanetenWachHundNetzPlanetenWachHundNetz
Instrumenting Infrastructure for
PlanetLab
Instrumenting Infrastructure for
PlanetLab
OutlineOutline
◊ Motivation◊ Hindernisse◊ Bekannte Ansätze◊ Unsere Lösung◊ Evaluation◊ Zusammenfassung
◊ Motivation◊ Hindernisse◊ Bekannte Ansätze◊ Unsere Lösung◊ Evaluation◊ Zusammenfassung
MotivationMotivation
◊ Context: Verteilte Anwendung• P2P (File-sharing), SETI ...
◊ Monitoring• Statistics• Log collection
◊ Context: Verteilte Anwendung• P2P (File-sharing), SETI ...
◊ Monitoring• Statistics• Log collection
Probleme und AuswegeProbleme und Auswege
◊ “Central warehousing” nicht scalierbar• “Push”: logs alle 5 min werden an zentralen Server geschickt
• “Pull”: nur auf AnfrageDaten müssen “en-route” reduziert werden• Reduction-tree• Distributed parallel prefix (MapReduce)
◊ “Central warehousing” nicht scalierbar• “Push”: logs alle 5 min werden an zentralen Server geschickt
• “Pull”: nur auf AnfrageDaten müssen “en-route” reduziert werden• Reduction-tree• Distributed parallel prefix (MapReduce)
Andere LösungenAndere Lösungen
◊ Reduction-Trees auf P2P◊ Basieren auf “structured
overlays”1) Finger-table based Tree (FTT)
• Unregelmäßig
2) Key-based Tree (KBT)• Nur ein globaler
Beide nicht locality-aware
◊ Reduction-Trees auf P2P◊ Basieren auf “structured
overlays”1) Finger-table based Tree (FTT)
• Unregelmäßig
2) Key-based Tree (KBT)• Nur ein globaler
Beide nicht locality-aware
Structured Overlay (DHT)Structured Overlay (DHT)◊ Key-based routing (KBR)
• Vergebe lange bit strings (keys/IDs)• Nodes teilen key-space unter sich auf• Garantiere routing zum “Besitzer” in log(n)◊Durch route zu “näherer” node
◊ Distributed Hashtable• Put, Get (Hashtable semantik)• Speichere Bucket beim Besitzer des Hash
◊ Key-based routing (KBR)• Vergebe lange bit strings (keys/IDs)• Nodes teilen key-space unter sich auf• Garantiere routing zum “Besitzer” in log(n)◊Durch route zu “näherer” node
◊ Distributed Hashtable• Put, Get (Hashtable semantik)• Speichere Bucket beim Besitzer des Hash
DHT Beispiel: ChordDHT Beispiel: Chord
◊ 160 bit Ids, representiert in einem Kreis
◊ Fingertables speichern Zeiger
◊ 160 bit Ids, representiert in einem Kreis
◊ Fingertables speichern Zeiger
Chord: LookupChord: Lookup
◊ Benutze fingertable um zur nahsten bekannten node zu springen
◊ Benutze fingertable um zur nahsten bekannten node zu springen
Finger-table based Tree (FTT)Finger-table based Tree (FTT)◊ Vereinigung aller Wege zu einer bestimmten ID• Abhängig von allen Fingertables
◊ Vereinigung aller Wege zu einer bestimmten ID• Abhängig von allen Fingertables
Key-based Tree (KBT)Key-based Tree (KBT)
◊ Tree auf Key-space gemappt• “virt.” interne nodes representieren prefixes
• “phys.” nodes sind Blätter
• Subtree enthält alle, die prefix entsprechen
• Algorithm. entscheidet, wer Vater wird
◊ Tree auf Key-space gemappt• “virt.” interne nodes representieren prefixes
• “phys.” nodes sind Blätter
• Subtree enthält alle, die prefix entsprechen
• Algorithm. entscheidet, wer Vater wird
Unser AnsatzUnser Ansatz
◊ Hybrid zwischen FTT und KBT KBT mit “root” node
o Ein Tree pro queryo Stochastisch balanciert
• Coral für Ortsinformationo Bildet “cluster”
◊ Hybrid zwischen FTT und KBT KBT mit “root” node
o Ein Tree pro queryo Stochastisch balanciert
• Coral für Ortsinformationo Bildet “cluster”
Key-based MapReduce (KMR)Key-based MapReduce (KMR)
◊ Phys. Root node
◊ In jedem level ein bit des root negiert
◊ Phys. Root node
◊ In jedem level ein bit des root negiert
EvaluationEvaluation
◊ PlanetenWachHundNetz (PWHN)• Application-level monitoring software• Service für PlanetLab• Testet KMR und FFT• Benutzt Coral und (Free-) Pastry
• 3 Executables von User :• Eingabe• Reduzieren• Ausgabe
◊ PlanetenWachHundNetz (PWHN)• Application-level monitoring software• Service für PlanetLab• Testet KMR und FFT• Benutzt Coral und (Free-) Pastry
• 3 Executables von User :• Eingabe• Reduzieren• Ausgabe
ZusammenfassungZusammenfassung