KE 4

1. Namen

   • eine Reihe von Bits/ Zeichen fuer Referenz auf eine Entität

   • Orts-unabhängig

   • besser für Menschen zu lesen

   • Bsp. Entiäten:

     • Hosts

     • Printer

     • Disketten

     • Webseiten

     • Newsgroups

   
   

2. Bezeichner

   • Art von Name

   • identifiziert Entität eindeutig

   • Eigenschaften:

     1. max 1 Entität als Referenz

     2. jede Entität hat max 1 Bezeichner

     3. Bezeichner referiert immer dieselbe Enität

        • wird nie wiederverwendet

   • leichter zu prüfen, ob zwei Prozesse auf die gleiche Entität zugreifen

1. Adressen

   = Access point

   • auf Entitäten kann man Sachen ausführen

     • dafür braucht man access point

     • z.B. Telefon einer Person - Nummer ist die Adresse

   • muss leicht zu ändern sein/ wird häufig gewechselt

     • z.B. Host läuft auf anderer Maschine

   • besonderer Art von Name

   • besser für Maschinen zu nutzen

   • IPv4 - 4 Byte

   • IPv6 - 6 Byte

= Abbildung eines Namens auf eine Adresse

• erlaubt Zugriff auf benannte Ressource

• enger Zusammenhang zwischen Auflösung und Routing

• Datei hat Namen für Benutzer

  • hard links sind mehrere Namen fuer dieselbe Datei

  • OS kennt inode einer Datei

    • enthält Infos wie z.B. Blockadressen

    • inode-Nummer ist eigentliche Adresse fuer Zugriff

• Namensystem braucht:

  • syntaktische Informationen

    • hilft gültige/ ungültige Namen zu erkennen

1. flache Namenssysteme

   • keine Hierarchie

   • flach = random bit strings

     • keine Infos darüber, wie man Entität ortet

       
       

2. strukturierte Namen

   • z.B. DNS

   • auch Dateibenennungen (file naming)

   • besser fuer Menschen zu lesen

   • erlauben Hierarchie

= Organisation von Namen

• Blatt steht fuer benannte Entität

  • enthält z.B. Adresse

  • normalerweise Dateien

  • kann auch Ressourcen sein, wie Drucker, Prozesse usw.

• innerer Knoten

  • .= directory node

  • ausgehende Kanten haben Namen

  • hat directory table = Tabelle mit Kanten

    • jede Kante ein Paar aus node identifier und edge label

• root (node)

  • keine eingehenden Kanten

  • mehrere möglich, meist nur einer

• path name

  • Pfad von der Wurzel zum Knoten

  • entsteht aus den Labeln an den Kanten

• absolute path name

  • wenn erster Knoten Wurzel ist

• relative path name

  • erster Knoten nicht die Wurzel

• z.B. graph as directed acyclic graph

  • mehr als eine eingehende Kante erlaubt

  • aber keine Kreise

• global name = immer für die selbe Entität

  • egal, wo im System name verwendet wird

• local name = interpretation hängt vom Kontext ab

  • anders: relativer name, dessen Ordner (implizit) bekannt ist

= anderer Name fuer selbe Entität

2 Arten bei naming graphs

1. mehrere absolute Pfade erlauben

2. Entität als Blatt speichern

   • keine Adresse gespeichert

   • sondern absoluter Pfad

   • ist wie symbolic links in Unix

= anderer Name space

• eigener root, kann root von dort speichern

= directory node in foreign name space

• während der Auflösung wird mounting point aufgesucht

• und Auflösung macht von dort aus weiter

• network file server

• um Dateien remote aufzurufen

• NFS URL erlaubt die Arbeit damit

  • gibt Datei

  • ohne was am Ende kann es Directory sein

  • server durch DNS aufgelöst

  • außerdem gibt es Protokoll an: "nfs: //"

    • weltweite Übereinkunft, was nfs bedeutet

• NS1 mit NS2 verbinden

• Kommunikation über Server

benötigte Informationen:

1. name of an access protocol

2. name of the server

3. name of the mounting point in NS2

• in Unix nicht nötig:

  • Server und Protokoll unnötig

  • Mounting point ist root of NS2

• eine Möglichkeit:

  • Infos in URL packen

hierarchisch organisierte name space distribution

Ebenen:

1. global layer

   • Knoten der obersten Ebene

   • root und directory nodes close to root (dessen Kinder)

   • stabil - directory tables ändern sich kaum

   • z.B. Organisationen oder Gruppen von Organisationen

   • müssen highly available sein

     • sonst fallen große Teile des name space weg

   • performance durchwachsen

     • caching möglich bei client, weil Tabellen sich kaum ändern

     • deswegen müssen sie nicht schnell antworten

     • müssen aber viele Anfragen bearbeiten können

   • Replikate sinnvoll

2. administrational layer

   • Knoten innerhalb einer Organisation

   • relativ stabil, aber häufiger als bei global

   • availability hauptsächlich wichtig für Organisation

   • performance - ähnlich wie bei global

     • caching möglich

     • sollten aber schnell antworten

     • updates schnell verarbeiten

   • starke Maschinen verwenden

3. managerial layer

   • ändern sich häufig

   • z.B. hosts im lokalen Netzwerk

   • Knoten fuer geteilte Dateien, benutzerdefinierte Ordner

   • auch von Endnutzern verwaltet

   • availabiltiy weniger anspruchsvoll

   • einzelne Maschine reicht

   • performanz ist wichtig

     • caching ist wenig hilfreich

• zones

  • nicht überlappende Teile

  • teilen name space auf

  • hat eigenen name server

• Internet Domain Name System

• übersetzt Namen in IP-Adressen

• weder Namen noch IP-Adresse sind eindeutig

• auch nach 30 Jahren noch sehr brauchbar

DNS Name Space

• hierarchisch organisiert als Root Tree

• Namen

  • label is case-insensitive string of alphanumeric characters

  • max 63 Zeichen fuer Label

  • max 255 Zeichen fuer ganzen Pfad

  • von rechts nach links gelesen

  • label durch . getrennt

  • root als "." - wird meist weggelassen

• Knoten haben genau eine eingehende Kante

  • außer root

  • also label der Kante ist auch label des Knotens

• domain = subtree

• domain name = pfad-Name zur Wurzel

  • kann relativ oder absolut sein

• resource records

  • .= Inhalt eines Knoten

  • Verschiedene Arten

    • 5_21_resource_records_dns

• Knoten repräsentiert verschiedene Entitäten gleichzeitig

  • e.g. vu.nl

    • ist domain

    • und zone

= hauptsächlicher Name eines hosts

• unterschiedlich von aliases

• alias wird implementiert durch Knoten mit gespeicherter CNAME record

  • die enthält canonical name

  • der Knoten ist also wie ein symbolischer Link

Koordination

= Verwalten von Interaktion und Abhängigkeiten zwischen Aktivitäten

2 Phänomene

1. Prozess-synchronisation

   • ein Prozess wartet auf einen anderen

2. Datensynchronisation

   • Datensets sind gleich

• in zentralisierten Systemen ist Zeit klar: man fragt das eine OS

• z.B Rekompilieren abhängig vom Zeitstempel der dateien input.c und input.o

physische Uhren

• Zeiten mit Quarzen

  • quartz oscilliert 60 mal die Sekunde (unter richtigen Bedingungen)

  • counter

    • wird runtergezählt bei jeder Oszillierung

  • holding register

    • laedt counter wieder auf, wenn er bei 0 angekommen ist

    • zugleich kommt interrupt

  • clock tick

    • name der Interrupts

  • clock skew

    • in unterschiedlichen Rechnern laufen die Quarze anders

    • .= Unterschied der Verschiebungen

    • Folge: Zeit abhängig von Maschine

UTC

• Universal Coordinated Time

• Basis fuer globale Zeit

• von Satelliten und einigen Radiostationen verkündet

2 Arten von Synchronisation (zwei Ziele)

1. interne Synchronisation

   = Präzision

   = Abweichung zwischen Uhren von Maschinen in verteiltem System

2. externe Synchronisation

   = Akkuratheit

   = Abweichung zu externer Zeit (z.B. UTC)

zwei Uhren die innerhal pi akkurat sind, sind innerhalb 2pi präzise

• von Präzision kann man aber nicht auf Akkuratheit schließen

= der Unterschied in Zeiteinheiten von einer perfekten Referenzuhr

• bei typischer Quarzuhr: 10^-6 Sekunden pro Sekunde = 31.5 Sekunden pro Jahr

maximum clock drift rate

= Spezifikation einer Hardware-Uhr

• BIld 6_1_1_drift rate

  • \rho ist die maximum clock drift rate

  • F(t) ist die tatsächliche Oszillationsfrequenz

  • F ist die ideale (konstante) Frequenz

  • die Gleichung gibt die Spezifikation

• Interrupts koppeln Software-clock zu Hardware-clock

1. NTP

2. Berkeley-Algorithmus

• in Berkeley-Unix

• Zeit-server ist aktiv

  • sonst sind die Zeit-Server i.d.R. passiv

  • fragt jede Maschine, welche Zeit sie hat

  • berechnet Mittelwert und teilt den Maschinen die nötigen Anpassungen mit

    • eigene Zeit auch im Mittelwert enthalten

• brauchbar in Systemen, in denen keine Maschine UTC receiver hat

• es reicht, wenn sich Prozesse darauf einigen können, in welcher Reihenfolge etwas geschehen ist

• wann etwas abgelaufen ist

= logische Uhr ohne absolute Zeit

• Interagieren Prozesse nicht, brauchen sie auch kein Synchronisation

• zaehlen Ereignisse

• Falls a -> b, dann C(a) < C(b)

• Umkehrung gilt nicht

  • das gilt erst bei Vektoruhr

happens-before = eine Beziehung

• a -> b

  • a geschah vor b

• 2 Situationen:

  • a) a und b sind Ereignisse im gleichen Prozess

    • a geschah vor b

    • a -> b ist wahr

  • b) a ist Ereignis des Nachrichtenversands von einem Prozess, b ist Ereignis des Nachrichtenempfangs eines anderen Prozesses

    • a -> b ist wahr

• transitive Beziehung

• concurrent events

  • x in einem Prozess, y in einem anderen Prozess

  • beide Prozesse interagieren nicht miteinander

  • weder x -> y noch y -> x ist wahr

  • kann nichts über ihre happens-before-Beziehung gesagt werden

Algorithmus

• Bild 6_8_Lamport

• jede Nachricht zwischen Prozessen trägt Zeit des Sendens

  • kommt sie an und die Uhr des Empfängers ist vor der versendeten Zeit, passt er seine Uhr an

  • eins mehr als gesendete Zeit

• Anpassung der Zeit und Zeitstempel in der middelware layer

• Anpassung der (Event-)Zaehler C_i bei jedem Client

  • 1. vor Ereignisausführung wird der Zaehler um eins hoch gezählt:

    • C_i <- C_i +1

  • 2. sendet Prozess P_i Nachricht m zu Pj

    • fügt Zeitstempel ts(m) hinzu gleich wie C_i

  • 3. bei Nachrichtenerhalt passt P_j seinen eigenen Zaehler an:

    • C_j <- max { C_j, ts(m) }

    • dann gibt es Nachricht weiter an Anwendung

• um gleiche Zeiten aufzulösen:

  • versendete Zeitstempel sind Tupel mit Index des Client

  • e.g. <40, i>

  • wenn i < j, dann (40, i) < (40, j)

• -> distrubierte Implementierung einer globalen Uhr

  • .= logische Uhr

• Bsp. Datenbank in verschiedenen Orten repliziert

  • Anfrage kommt immer zu nahegelegensten Kopie

  • Veränderungen müssen bei jeder Kopie gemacht werden

  • zur "gleichen" Zeit:

    • 100 Euro zu Konto von Kunden A hinzufügen

    • 1% Zinsen zum Konto von Kunde A hinzufügen

    • -> je nachdem, was zuerst gemacht wird 1$ Unterschied

• Lösung: total-ordered multikast

  • .= jede Nachricht wird an jeden Empfänger in gleicher Ordnung geliefert

  • Nachrichten werden immer mit Zeit des Senders versandt

  • Sender bekommt auch seine eigene Zeit

  • Nachrichten kommen in eine Queue

  • außerdem wird Erhalt bestätigt

  • Prozess kann Nachricht nur an Anwendung schicken, wenn es an erster Stelle steht und bestätigt wurde (von anderen Prozessen)

  • jeder Prozess hat die gleiche Kopie der Queue -> alle Nachrichten überall gleich verarbeitet

  • ( Anerkennung ist nicht unbedingt nötig, Empfänger muss nur irgendwie reagieren, z.B. eigene Nachricht senden)

• andere Name:

  • " state machine replication "

• C(a) < C(b)

  • bedeutet nicht, dass a vor b passiert ist

• Vektoruhren erfassen Kausalität

  • Lamport-Uhren sagen nichts über Kausalität, nur über zeitliche Abfolge von Ereignissen

  • erfassen causal histories

• a -> b genau dann, wenn VC(a) < VC(b)

  • also wenn VC(a) < VC(b), dann auch a -> b

• verschicken kausale Geschichtsverläufe

• beim eigenen Prozess ist klar

• ansonsten je nach Ankunft wie oben

• Ereigenis p vor Ereignis q, wenn

  • H(p) Teilmenge von H(q)

  • proper subset

  • reicht auch zu schauen, ob p in H(q)

• Problem: Repräsentation ist nicht effizient

• Vektoruhren:

  1. jth Eintrag ist Anzahl Ereignisse bei Prozess j

     • anders: VC_j[j] ist lokale logische Uhr von P_j

     • jedes lokale Ereignis zaehlen

  2. ist VC_j[i] = k, dann weiß P_j dass k Ereignisse bei Prozess P_i geschehen sind

     • kennt also die lokale logische Zeit von C_i

     • Vektoren mit allen Nachrichten mitschicken

• Schritte:

  1. vor jedem Ereignis die lokale Vektoruhr hochzählen

  • VC_i[i] <- VC_i[i] + 1

  2. schickt P_i eine Nachricht m an P_j

  • den Zeitstempel von m ts(m) zu VC_i setzen

  • das Schicken von m wird mitgezählt

  3. erhält P_j die Nachricht m von P_i

  • eigenen Vektor anpassen

  • VC_j[k] <- max { VC_j[k], ts(m)[k] }

  • für jedes k

    • .= die kausalen Geschichtsverläufe vereinen

  • dann den Nachrichtenempfang festhalten

• Nachrichten sorgen dafür, dass man auch über andere Prozesse, die nicht beteiligt waren, auf dem laufenden Gehalten wird

• zeitliche Abfolge ist egal, wenn Kausalität keine Rolle spielt

2 Arten

1. token-based solutions

   
   

2. permission-based approach

   • Prozess, der Ressource will, wartet auf Erlaubnis von anderen Prozessen

   • in der Folge werden Wege der Erlaubnis erklärt

   • 4 Arten:

     • Ein-Prozess-System simulieren

     • Verteilter Algorithmus

     • Token-Ring-Algorithmus

     • Dezentralisierter Algorithmus

• benutzen token = spezielle Nachricht

• gibt nur eins

• wer es hat, darf Ressource verwenden

• wenn fertig, wird token zum nächsten Prozess gegeben

• braucht er die Ressource nicht, gibt er ihn weiter

  
  

2 Eigenschaften:

• a) vermeiden Verhungern

  • -> jeder Prozess bekommt die Resoure mal

• b) deadlocks vermieden

  • -> wenn Prozesse aufeinander warten

  • macht sie einfach

• c) Verlust ist nur schwer zu beheben

  • wenn z.B. ein Prozess mit dem Token abstürtzt

  • muss man sicherstellen, dass der neu erstellte Token auch der einzige ist

• es gibt einen Prozess zur Koordination

• Anfragen für Ressource gehen zum Koordinator

• ist Ressource belegt, kommt Anfrager in Warteschlange

Eigenschaften:

• einfach

• braucht nur 3 Nachrichten

  • request

  • grant

  • release

• Koordinator ist Schwachstelle

  • single point of failure

  • Performance bottleneck

• baut auf Lamports Uhr auf

• braucht totale Ordnung der Ereignisse im System

Vorgehen:

1. Anfrage = Nachricht mit

   • Name der Ressource

   • Prozessnummer

   • gegenwärtige (logische) Zeit

   • geht an alle Prozesse

     • inkl. sich selbst

2. Nachricht empfangen

   • 3 Möglichkeiten:

     • 1. Empfänger ist nicht in Ressource und will sie auch nicht

       • -> schickt ok zurück

     • 2. Empfänger nutzt Ressource

       • antwortet nicht

       • stellt Anfrage in Warteschlange

     • 3. Empfänger wartet auch auf Ressource

       • vergleicht Zeit mit Zeit der eigenen Anfrage

       • nächste Anfrage gewinnt

       • andere näher? -> schickt ok

       • eigene näher? -> schickt gar nichts

3. alle Nachrichten empfangen

   • beginnt arbeit

   • danach schickt er "ok" zu allen wartenden Nachrichten in seiner Warteschlange

   • löscht dann die Anfragen aus Warteschlange

Eigenschaften:

• kein deadlock

• kein starvation

• braucht 2 * ( N - 1) Nachrichten

• es gibt N points of failure

  • weil fehlende Antwort eines (gecrashten) Prozeses als verweigerte Erlaubnis interpretiert wird

  • Verbesserung:

    • bei Anfragen immer Antwort schicken

    • entweder Zustimmung oder Verweigerung

    • dann noch mal versuchen und irgendwann annehmen, dass der andere Prozess tot ist

• man muss festhalten, welche Prozesse in der Gruppe sind

  • entweder multicast communication primitive

  • oder jeder Prozess muss selbst Tabelle verwalten

  • -> geht am Besten mit kleiner Gruppe von Prozessen

    • die nie Mitgliedschaft ändern

• alle Prozesse sind immer an allen Entscheidungen beteiligt

  • verlangt viel Aufmerksamkeit

  • Verbesserung:

    • Mehrheit der Prozesse reicht für Zugriff auf Ressource

• deterministisch

• Software baut overlay-Network in Form eines logischen Rings

  • jede Prozess bekommt Position im Ring

  • und kennt seinen Nachfolger

• am Anfang bekommt Prozess P0 den Token

• Token geht im Kries in point-to-point messages

• bekommt P Token, schaut er, ob er Ressource braucht

• nach Benutzen muss er ihn weitergeben, selbst wenn Ressource wieder braucht

• braucht kein P den Token, zirkuliert er einfach nur

Eigenschaften:

• keine starvation

• Token können verloren gehen und müssen dann neu erstellt werden

  • schwierig, Zeitpunkt zu bestimmen

  • Token könnte ewig im Kreis brauchen

• tote Prozesse können entfernt werden

  • wenn sie bei Erhalt des Token die Annahme bestätigen müssen

  • tun sie es nicht, weiß ihr Vorgänger, dass der Nachfolger tot ist

  • braucht trotzdem, dass jeder P die gegenwärtige Ringkonfiguration verwaltet

• Voting algorithm

• jede Ressource wird N mal repliziert, jede Replik hat eigenen Koordinator

• Zugriff nur nach Mehrheitswahl

  • m > N/2 Koordinatoren

  • Ablehnung wird Anfrager mitgeteilt

• Koordinator setzt sich willkürlich zurück (z.B. wenn er abstürtzt)

  • dann vergisst er, wenn er Zugriff erlaubt hat

  • kann man mit geeignet geringer Wahrscheinlichkeit eines Absturzes vernachlässigen

• bekommt Prozess keine Zustimmung, wiederholt er nach gewisser Zeit die Anfrage

Problem:

• wollen zu viele Prozesse Zugriff, bekommt keiner die Mehrheit

• Ressource liegt nutzlos rum

wie wird der Koordinator gewählt

• Koordinator = Name für spezielle Prozesse

• alle Prozesse haben einzigartigen Bezeichner

• alle Algorithmen suchen Prozess mit höchstem Bezeichner, um ihn zum Koordinator zu machen

• jeder Prozess kennt die Bezeichner der anderen Prozesse

• unbekannt:

  • welche Prozesse gerade laufen

• Ziel:

  • bei einer Wahl einigen sich alle Prozesse auf den gleichen Koordinator

4 Arten:

• Bully Algorithmus

• Ring Algorithmus

• Wahl in wireless

• Election large-scale Systems

• biggest guy in town wins

• geg.:

  • N Prozesse

  • id(P_k) = k

• sobald Koordinator nicht mehr auf Anfrage antwortet, startet die Wahl

• Schritte für die von P_k abgehaltene Wahl:

  • 1. P_k sendet ELECTION-Nachricht an alle Prozesse mit höherem Bezeichner k

  • 2. antwortet keiner, wird P_k Koordinator

  • 3. antwortet einer (der Höheren) übernimmt er die Arbeit

    • P_k braucht nichts mehr zu machen

• erhält P eine ELECTION Nachricht

  • sendet er Ok zurück

    • Sender weiß, dass P läuft

  • startet selbst eine Wahl

  • irgendwann haben alle aufgegeben, außer Prozess N-1 (startet bei 0)

  • letzter Prozess schickt er COORDINATOR Nachricht

• kommt ein Prozess wieder (nachdem er tot war) startet er Wahl

• nutzt (logischen) Ring

• jeder Prozess kennt seinen Nachfolger

• Prozess P_k startet Wahl

  • (wenn er merkt, dass Koordinator nicht mehr arbeitet)

  • schickt ELECTION Nachricht mit eigenem Identifier zu seinem Nachfolger

    • läuft Nachfolger nicht, macht er weiter bis zum ersten laufenden Prozess

  • jeder Prozess packt eigenen Bezeichner mit in die Nachricht dazu

    • macht sich selbst zum Kandidat

• irgendwann kommt Nachricht zu P zurück

  • P erkennt es, weil eigener Bezeichner mit drin ist

  • ändert Nachricht zu Koordinator

  • schickt sie nochmal rum, um alle über Koordinator zu informieren

    • ist der mit der höchsten Id

• zwei simultane Nachrichten stören nicht

• wie ein Graph

• jeder Knoten kann als Leader Wahl starten

• schickt ELECTION Nachricht zu unmittelbaren Nachbarn

• die schicken die Nachricht zu Nachbarn, außer zum Parent

• erhält Node ELECTION Nachricht von nicht-Parent-Node, bestätigt sie Erhalt

• Blätter antworten sofort zu Parent, die anderen Knoten erst nach Antwort

• bester Knoten wird als Koordinator gewählt

• bei mehreren Wahlen, nimmt Knoten nur an einer teil

  • die mit höchster Id

• fuer die Wahl mehrerer Koordinatoren

• z.B. super-peers in peer-to-peer networks

• Anforderungen:

  • 1. normale Knoten haben low-latency access to super peers

  • 2. super peers sollten gleich im Netzwerk verteilt sein

  • 3. Anteil der super peers steht fest im Gesamtnetzwerk

  • 4. jeder super peer sollte fest maximale Anzahl an Knoten bedienen

• meist passt es, weil overlay networks strukturiert sind

  • oder willkürlich unstrukturiert

• jeder Knoten bekommt willkürlich erzeugen m-bit Bezeichner

  • die ersten k (links außen) Bits für super peers reservieren