Naming Terminology
Name |
Zeichenkette welche auf eine Entity verweist |
Address |
Name eines Access Points |
Access Point |
Spezieller Typ einer Entity um auf andere Entity zuzugreifen |
Entity |
Alles was betrieben werden kann |
Address und Access Points können ändern, aber weiterhin erreichbar via Name. Entity kann auf mehrere Access Points hören.
Flat Naming
Names sind unstrukturierte Identifiers |
Meistens: |
* identifiziert Entity unique |
* kann Random sein |
Können zwar eine interne Struktur haben, wird jedoch nicht für Name Resolution verwendet.
Broadcasting
+ Selbstverwaltetes Naming system |
+ Einfach zu implementieren |
+ Ortsunabhängig |
- Skaliert nicht (Overhead Kommunikation entspricht Anzahl Entity) |
Recursive Resolution
+ Besseres Caching möglich |
- Hohe Performance Ansprüche an jedem Nameserver |
Structured Naming
Hierarchisch strukturiert, z.B. unterricht.hsr.ch |
Namensauflösung kann auf Layers mit versch. Verantw. und Anf. aufgeteilt werden |
Attribute-Based Naming
Suche nach Entity aufgrund Attribut-Paare |
Distributed Hash Tables
Spezielle Art von Hashing, welches Vergrösserung erlaubt |
Im Schnitt nur Anz.Keys/Anz.Nodes zu verschieben |
Distributed Hash Tables Beispiel
Vergrösserung von 3 auf 4 Nodes, nur 3 Keys verschieben
P2P Networks
Peer |
Participant, Equal, may act as server and/or client |
Decentralized |
Overlay network |
Structures |
Unstructured, Structured, Hybrid |
Torrent Q&A
|
Welche Aufgabe erfüllt ein Peer? Lädt Daten von anderen Peers. stellt fertige Pieces seinem Schwarm zur Verfügung. Auswahl der nächsten Teile verantwortlich. Fertiges Teil sicherstellen indem SHA-1 Hashs überprüfen.
|
|
Weshalb sind Files in Teile aufgeteilt? Von mehreren gleichzeitig laden. Upload schon nach fertigem Teil. Fehler im Teil verwirft nur Teil.
|
|
Auswahl der Teile folgt vier Policies Strict Priority: Ein Teil wird komplett geladen damit möglichst schnell verifiziert und weitergegeben werden kann. Rarest First: Seltene Teile werden bevorzugt um Engpässe zu verhindern. Random First Piece: Damit nicht zuerst ein seltenes Teil angefordert wird, würde sonst Upload verzögern und zu Choking führen. Endgame Mode: Verbleibende Teile mehrmals parallel von div. Peers angefordert um Download schnell abszuschliessen.
|
|
|
Chord: Storing Resources
succ(_) nicht verwechseln mit "_.successor" |
succ(_) ist eine verteilte Funktion |
_.successor ist eine lokale Funktion |
Für alle p gilt: p.successor = succ(p+1) |
Chord: Finger Table
Wenn korrekt, lookup ist O(log N) |
Wenn successor pointers (p.finger[1]) korrekt. lookup ergibt korrektes Resultat |
Aber gleichzeitige joins oder failing nodes korruptieren finger table |
* periodische Stabilisation Prozedur |
* dank Stablisation, Netzwerk konvergiert in konsistenten Zustand |
NTP
δ round-trip time = (Cr-Cs)-(Ss-Sr)
θ offset = Ss-Cr+(δ/2) = ((Ss+Sr)-(Cs+Cr))/2
NTP client passt Uhr an durch verlangsamern oder verschnellern des Intervalls
Logical Clocks: Causuality
Running Example: replicated DB
All nodes must ACK the message of updates to other nodes. Perform update only when all have ACKd. |
All update messages get timestamp of physical clock. Updates in priority queue (based on timestamp) |
Totally ordered multicasting. Use Lamport's Clock as the timestamp |
Use a vector clock to version updates. concurrent updates can be merged. |
Only Solution Abschnitte hier abgebildet.
Distributed Batch Processing
|
|
Lamport's Logical Clock
Jeder Pi erhöht Ci(.) bei jedem Event
Bei Erhalt: Ci(a) = max(Ci(a), Ci(b))+1
Logical Clocks: Summary
Erfasst "->" das consept of casuality immer komplett? Nicht immer: Events auf gleichem Prozess können independent sein; Events auf versch. Prozessen können concurrent sein, aber beiläufig durch Externes
Casuality Beispiele
Does totally ordered multicasting preserve casuality? Yes, Since messages are delivered in the order of their Lamport timestamps, which preserve the happened-before relation.
Resilient Distributed Datasets
Deploying Naming
Spark Context |
Entry point for creating RDDs, Manages connection to the cluster, accesses services like schedulers and block manager |
Cluster Manager |
Service managing resources in the cluster, e.g. spark standalone, mesos, YARN |
Worker Node |
A node that can run coe of a Spark application |
Executor |
A process launched for a certain application, Applications are isolated from each other |
|
