Einfuehrung in Distributed Hash Tables

Filip Martinovský Philipp Wagner

FB Informatik FB Informatik
FH Zittau/Görlitz FH Zittau/Görlitz
safimart@[Link] siphwagn@[Link]

Abstract strong consistency Hierbei haben alle Klienten des Systems

Distributed Hash Tables (DHT) stellen eine einfache die gleiche Sicht auf die Daten, welche durch Two-
Möglichkeit dar, hochverfügbare und verteilte Systeme zu Phase-Commit Algorithmen auch bei Dateiänderungen
konstruieren. Seit den viel beachteten initialen Veröffentlichungen gewährleistet werden kann. Das beste Beispiel für
zu konsistenten Hashverfahren [KLL+ 97] und einer Arbeit zu strong consistency ist vermutlich das in Relationa-
verteilten Hashtabellen [SMK+ 01] hat auch die Industrie den Wert len Datenbanksystemen verwendete ACID (Atomicity
der Technologie erkannt und beispielsweise in Amazons Dynamo Consistency Availability Durability). Berichte aus der
[HJK+ 07] umgesetzt. Industrie und Forschung legen jedoch nahe, daß
Dieser Beleg ist eine Einführung in die Theorie der verteilten ACID in verteilten Umgebungen in einer schlechten
Hashtabellen. Die Umsetzung von Chord [SMK+ 01], einem Proto- Verfügbarkeit resultiert. [HJK+ 07] [FGC+ 97]
koll für verteilte Hashtabellen, erfolgt in Erlang1 . weak consistency/eventual consistency Bei schwacher
Konsistenz kann es passieren, daß nicht alle Benutzer
1 Motivation des Systems die gleiche Sicht auf die Daten haben. Ein
Unbestritten sind viele Unternehmen in der heutigen Zeit exis- lesender Klient sieht also nicht zwangsläufig die letzten
tentiell abhängig von ihrem Datenbestand. Diese Daten müssen zu Schreibzugriffe.
jedem Zeitpunkt verfügbar und für korrekte Ergebnisse möglichst
konsistent sein. Schwache Konsistenz lässt sich am besten an einem
Neben Verfügbarkeit und Konsistenz ist darüber hinaus die La- Beispiel erklären: Angenommen man hat ein System
tenzzeit eine wichtige Komponente in Geschäftsmodellen. Googles mit N Nodes, davon sind W Nodes bei jedem Schreib-
VP Marissa Mayer erklärte beispielsweise, daß eine Steigerung der zugriff und R Nodes bei jedem lesenden Zugriff be-
Latenz um eine halbe Sekunde einen Einbruch des Suchvolumens teiligt. Starke Konsistenz lässt sich nur erreichen wenn
von 20% bedeutet. Bei Amazon ist die Steigerung der Ladezeit von R +W > N ist, was bedeutet dass sich die Menge R und
100 ms für einen Rückgang der Verkäufe um 1% verantwortlich. W überschneiden. Der lesende Zugriff hat jederzeit die
[KL07] Möglichkeit die letzte schreibende Änderung im Sys-
In der Entwicklung verteilter Systeme ist es notwendig Archi- tem zu entdecken.3
tekturmuster offenzulegen, so daß das Verhalten hinsichtlich Kon- Ein RDBMS mit synchroner Replikation ist beispiels-
sistenz, Verfügbarkeit und Latenzverhalten modelliert und unter- weise: N = 2,W = 2, R = 1, stark konsistent.
sucht werden kann.
Ein System tritt in Eventuelle Konsistenz über, wenn
Distributed Hash Tables sind eine Basis für dezentrale, verteilte R + W < N ist. Das bedeutet, die Mengen R und
Systeme. Sie finden breite Anwendung in Peer-to-Peer Technolo- W müssen sich nicht mehr überschneiden. Lesen-
gien, wie beispielsweise BitTorrent oder auch in anderen verteil- de Zugriffe müssen zwangläufig nicht mehr garan-
ten Speicherlösungen: das Backend von Amazon, Amazon Dynamo tiert die letzten Schreibzugriffe im System sehen, es
[HJK+ 07], basiert auf einem verteilten Hashverfahren. kann Inkonsistent sein und ist eventuell noch konsis-
1.1 Brewer’s CAP Theorem tent. Die Änderungen an Datensätzen werden durch
Bei der Konsktruktion von verteilten Systemen gibt es be- Gossip Protokolle durch die beteiligten Instanzen
schränkende Eigenschaften. In einer Keynote Speech postulierte propagiert.[HJK+ 07] [GBL+ 03]
Eric A. Brewer die Vermutung, daß unter den 3 Eigenschaften (Ab- Ein RDBMS mit asynchroner Replikation, beispiels-
bildung 1): (Starke) Konsistenz, Verfügbarkeit und Partition Tole- weise N = 2,W = 1, R = 1 ist nicht konsistent.
rance bei einem verteilten System nur 2 gleichzeitig erfüllbar sind.
[Bre00] Die Vermutung erhielt den Namen CAP, gemäß ihrer Ei- Availability gibt eine Aussage darüber ob das System die
genschaften: Fähigkeit besitzt trotz des Ausfalls von Nodes vollständig zu
operieren.
Consistency stellt die Frage ob ein System nach einer Operation in
einem konsistenten Zustand übertritt. In verteilten Datenbank- Partition Tolerance bezieht sich auf die Fähigkeit eines Systems
systemen muss dabei zwischen strong und weak consistency im Falle einer Partitionierung des Netzwerks zu arbeiten. Par-
2 unterschieden werden.
3 Beispiel von: [Link]
1 [Link]
post/282603471/eventual-consistency-for-techies
2 starker und schwacher Konsistenz übernommen.
 CAP Theorem werkfehlern.
Warum das Google File System keine Distributed Hash Tables
verwendet, wird in [HGL03] erläutert. Das Google File System hat
Consistency
durch die zentrale Verwaltung und den Master Node sehr genau-
es Wissen über seine Nodes und kann so, ohne unnötige und das
Netzwerk belastende Anfragen zu stellen, sehr spezielle Annahmen
für Berechnungsschritte4 machen um beispielsweise die Lokalität
Availability
von Maschinen auszunutzen: “[...] it makes placement decisions,
creates new chunks and hence replicas, and coordinates various
system-wide activities to keep chunks fully replicated, to balance
load across all the chunkservers, and to reclaim unused storage.“.

Partition Tolerance
2 Theorie
2.1 Hashing
Hash-Funktionen (aus dem Englischen “to hash“ = zerhacken),
im Deutschen auch als Streuwertfunktionen bekannt, stellen eine
Abbildung von einer größeren Quellmenge in einen kleineren Ziel-
raum (auch Schlüsselraum genannt) dar. Sie sind in vielen Berei-
Abb. 1: CAP Theorem chen der Informatik relevant, denn oft ist es eine Notwendigkeit
Daten in kurzer Zeit in bestehende Verzeichnisse einzufügen oder
auszulesen. Beispiele sind:

titionen können sich beispielsweise durch getrennte Kommu- • Assoziative Arrays

nikationsleitungen ausdrücken. Gilbert und Lynch definierten • Hashindexe in Datenbanken
Partition Tolerance [GL02] als:
• Symboltabellen von Compilern
No set of failures less than total network failure is Darüber hinaus eignen sich kryptographische Hash-Funktionen
allowed to cause the system to respond incorrect- ausserordentlich dafür, die Integrität von Daten zu sichern (Listing
ly. 1) und sind prädestiniert für Aufgaben wie Datenverschlüsselung
Das CAP Theorem ist real und in der Welt der verteilten Sys- (One-Way-Hash) oder Prüfsummenberechnung.
teme muss eventuelle Konsistenz zwangsläufig hingenommen wer- Eine ausführliche Einführung in Hashfunktionen kann an dieser
den. Denn angenommen die Anzahl an Nodes ist N > 1000 und Stelle nicht gegeben werden und die Thematik kann einer reichhal-
R = 1, so ist es (besonders unter konkurrierendem lesendem/schrei- tigen Literatur entnommen werden, wie dem hervorragenden “Art
benden Zugriff) äußerst unreal und ineffizient eine synchrone Re- of Computer Programming, Volume 3: Sorting and Searching “
plikation mit W = N zu setzen um eine starke Konsistenz der Daten [Knu98] oder “Numerical recipes: the art of scientific computing“
zu gewährleisten. [wil07], .
Opfert man jeweils eine der 3 Eigenschaften, ergeben sich die
Listing 1: md5 und sha1
Fälle:
philipp@banana :˜/ svn /dht - svn$ md5sum dht . tex
Consistency + Availability bei geclusterten Datenbanklösungen, 19 a658e2233d444a1d78943bb8c765c2 dht . tex
klassischen RDBMS. philipp@banana :˜/ svn /dht - svn$ sha1sum dht . tex
41 db64329bf8944ecb91725fabc1cfd198a12ba9 dht . tex
• Two-Phase Commit
Heutzutage wird angenommen, daß kryptographische Hash-
Consistency + Partition-Tolerance bei verteilten Datenbanken. funktionen, wie Message Digest 5 (MD5) und Secure Hash Algo-
• Systemweite Blockierung möglich rithm 1 (SHA1), Daten möglichst gleichverteilen und gute Hash-
funktionen sind.
• Pessimistische Locking-Strategie Gute Hashfunktionen haben als Kriterien:
Partition-Tolerance + Availability bei DNS und Web-Caches. • Datenreduktion
• Optimistische Update Strategie • Zufälligkeit
• Auflösen von Konflikten • Eindeutigkeit
• Effizienz
1.2 Anwendungsbeispiele Sichere Hashfunktionen sind darüber hinaus:
Google BigTable ist Consistency + Availability. Google legt den
Fokus auf starke Konsistenz und hohe Verfügbarkeit, denn • Kollisionsfrei Hashwerte sollten eine geringe Wahrschein-
eine Replikation der Daten erfolgt nicht auf Ebene der lichkeit für Kollisionen aufweisen und möglichst eine Gleich-
Datenbank sondern wird vom GFS (Google File System) verteilung der Zielmenge.
übernommen. • Unumkehrbar
Amazons Dynamo ist Availability + Partition Tolerance und 2.2 Consistent Hashing
erfüllt die Merkmale der Verfügbarkeit und der Toleranz ge- Nicht jeder Inhalt im Internet wird gleichermassen angefordert.
genüber Ausfällen. Dynamo verwendet modifizierte Distribu- Durch populäre Downloads, oder oft angeforderte Inhalte, ist es
ted Hash Tables, die Gegenstand dieses Belegs sind und er-
reicht so Hochverfügbarkeit und Toleranz gegenüber Netz- 4 MapReduce
 Hashfunctions Die Ressourcen werden in den Schlüsselraum gehashed,
f(x) = x mod 4
durch Anwendung kryptographischer Hashfunktionen wie MD5

4
g(x) = x mod 5
(RFC13219 ) oder SHA-1, da diese möglichst kollsionsfrei sind und
so die Wahrscheinlichkeit von doppelten Einträgen minimiert wird.
0
3

Resource B
Buckets

2
1
0

0 2 4 6 8 10 Resource A
Data

Abschliessend werden die Nodes in den Schlüsselraum des glei-

Abb. 2: Hash-Funktion: Zuordnung Daten zu Schlüssel. chen Ringes gehashed. Es ist notwedig ein eindeutiges Merkmal zu
hashen, beispielsweise die IP Adresse des Servers.
0
notwendig Last zu verteilen und Caches einzurichten, so daß Inhal-
te aus dem Hauptspeicher geladen werden.5 Ein intuitiver Ansatz IP1-1
Resource B

die Last zu verteilen, wäre es URL6 Adressen durch eine einfache IP2-2
Hashfunktion auf die Server zu abzubilden.
Audioscrobbler verwendete für seine Clients beispielsweise fol-
genden Hash7 :
IP2-1

server = serverlist[hash( key ) modulo serverlist .length];

Resource A IP3-1

Das Problem daran ist: sobald ein Server hinzukommt oder

ausfällt werden (im schlimmsten Fall alle) URL Adressen einem
anderen Server zugewiesen. Der Inhalt im Cache wird hinfällig, Der verantwortliche Node für eine Resource ist nun jener Node,
siehe Abbildung 2, und Datenbank und Festplatte müssen belastet welcher im Uhrzeigersinn ausgehend von der Resource als Erster
werden um alle Inhalte wieder in den Cache zu laden. getroffen wird. Ist dieser Server ausgefallen, so wird zum nächsten
Server im Ring gegangen. Somit müssen im Falle eines Ausfalls
Konsistentes Hashing löst das Problem dieser wechselnden
nicht die Caches für alle Server geladen werden, sondern nur die
Sichten. Vorgeschlagen wurde es von einer Forschergruppe am
Resourcen für die der Node nun verantwortlich ist.
Massachusetts Institute of Technology und in der Publikation
“Consistent Hashing and Random Trees: Distributed Caching Pro- 3 Chord
tocols for Relieving Hot Spots on the World Wide Web“ [KLL+ 97] Chord [SMK+ 01] ist ein Protokoll zur Implementierung eines
auf ein theoretisches Fundament gestellt. verteilten Lookup Service und die konsequente Umsetzung von
Die Idee von konsistentem Hashing lässt sich so beschreiben, konsistentem Hashing. Dabei ist adressiert das Modell folgende
daß sowohl für den Node8 als auch für die Resource Hashfunktio- Probleme:
nen existieren: • Lastverteilung: Durch die Gleichverteilung der (meist
• Node: hNode : {1, . . . , n} → {0, . . . , 2m − 1} kryptographischen) Hashfunktion wird eine Lastverteilung
gewährleistet. Die Teilnehmer sind so im Idealfall für eine
• Key: hResource : {1, . . . , k} → {0, . . . , 2m − 1}
gleiche Anzahl an Ressourcen im Ring zuständig.
Bei konsistentem Hashing stellt man sich den Schlüsselraum am
besten als Ring vor: • Dezentralisierung: Es werden bei Chord keine zentralen Ser-
0
ver benötigt. Der Ring ist ein lose Kopplung gleichberechtig-
ter Instanzen.
• Skalierbarkeit: In der Komplexitätsanalyse wird ersichtlich,
daß eine Suche im Chord-Protokoll in O (log n) liegt und somit
auch Netze mit vielen Teilnehmern möglich sind.
• Verfügbarkeit: Chord reorganisiert das Netz, wenn Nodes
hinzukommen oder den Ring spontan verlassen. Eine peri-
odisch ausgeführte Stabilisierungsoperation ist dafür verant-
wortlich, daß Änderungen im Ring von den Knoten propagiert
werden.
• Flexible Namensgebung: durch die Hashfunktion ist der
5 Siehe memcache. Schlüsselraum flach. Die Hashfunktionen macht keine An-
6 Uniform Resource Locator nahme über die Namensgebung der Schlüssel und die jeweili-
7 [Link] ge Applikation kann dies selbst bestimmen.
8 Server, Teilnehmer 9 [Link]
 N45 N45
a) b) Index k + 2i-1 modulo 2m Knoten
N4 N4
Knoten k = 11
N36 N36
1 12 23
N7 N7
4 19 23
5 27 30
N28 N11 N28 N11 6 43 45
K4? K4?
Knoten k = 45
N23 N23 1 46 60
4 53 60
Abb. 3: Lookup 5 61 4
6 13 23
N60 K2 Knoten k = 60
N4
1 61 4
... ... ...
N45
N11
Tab. 1: Fingertable für Knoten k=11, k=45, k=60
K2?

N23 a) b)
p p

N30
n n

Abb. 4: Suche nach Schlüssel 2 in einem Ring der Größte 26 . s s

3.1 Lookup c) d)
3.1.1 Lookup ohne Finger-Informationen p p
Hat ein Knoten keine zusätzlichen Routinginformationen, kennt
er nur seinen Vorgänger und Nachfolger. Eine Suche nach einem
Schlüssel würde eine sequentielle Suche werden, wie in Abbildung n n
3 beschrieben. Die Komplexität würde ein Aufwand von O (n) be-
s s
deuten, und dies ist in großen Netzen nicht hinnehmbar.
3.1.2 Lookup mit Finger-Informationen
Um das System also zum Skalieren zu bringen, muss das Ziel Abb. 5: Einfügen eines Knotens
entweder eine konstante Suchzeit O (1) oder ein logarithmischer
Aufwand O (log n) sein. Eine konstante Suchzeit kann erreicht wer-
den, indem jeder Node den gesamten Ring kennt und Anfragen erfolgt.
direkt an den verantwortlichen Node weitergeleitet werden. Dies
bedeutet jedoch einen hohen Verwaltungsaufwand und stellt eine 4. Datenaustausch zwischen Node 4 und Node 11.
Speicherplatzanforderung für den Client dar. Chord ist deshalb für Es sei an dieser Stelle auf den Beweis verzichtet, daß die Such-
eine Suche in logarithmischer Zeit vorgesehen. Es werden nur m zeit in Chord in wirklich in O (log n) liegt. Denn die Beweisidee
Einträge in der Routingtabelle, auch Fingertabelle genannt, benötigt in [SMK+ 01] ist offensichtlich: durch Abbildung 4 und den Rou-
und m ist die Bitlänge der Hashfunktion. tinginformationen in Listing 1 ist einzusehen, daß sich mit jedem
Der i-te Eintrag in der Fingertable ist der Knoten, der den 2i−1 - Schritt der Suchraum mit hoher Wahrscheinlichkeit halbiert. Die
ten Eintrag im Ring verwaltet. Es ist ersichtlich, daß der erste Ein- Suche nach einem Wert wird letztendlich zu einer binären Suche
trag der Tabelle k + 20 der Nachfolger des Knotens k ist. Das Ziel mit bekanntermaßen logarithmischen Aufwand.
der Fingertable ist mit jedem Suchschritt den Suchraum innerhalb
des Rings zu halbieren. 3.2 Operationen
Der Lookup wird an einem konkreten Beispiel beschrieben: in 3.2.1 Einfügen eines Knotens
Abbildung 4 wird in einem Ring der Größe 26 bei Knoten 11 nach Soll ein neuer Knoten n hizugefügt werden so muss diesem be-
dem Schlüssel 2 gesucht, die Fingertables der Knoten sind mit Lis- reits ein Knoten x aus dem Ring bekannt sein. Ausgehend von x
ting 1 gegeben. kann der zu n zugehörige Nachfolger s im Ring gesucht werden,
Die Suche läuft folgendermassen: gemäß der thematisierten Lookup Strategie.10 , in Abbildung 5a dar-
1. Node 11 wählt Node 45 aus seiner Fingertable, denn dieser ist gestellt.
der größte Node der Fingertable der vor Key 2 liegt. n setzt seinen Nachfolger-Zeiger auf s und informiert ihn über
die Änderung. Ist n der Vorgänger von s im Ring (d.h. seine ID
2. Node 45 wählt Node 60 aus seiner Fingertable, denn Node 60 ist größer als die des urspünglichen Vorgängers p) setzt s seinen
ist der Node mit dem höchsten Hashwert vor Key 2. Vorgänger-Zeiger auf n, siehe Abbildung 5b.
3. Node 60 hat als Nachfolger Node 4. Da Node 4 schon einen
höheren Hashwert als 2 hat, ist Node 4 für Key 2 verant- 10 Die Position ist dabei abhängig von der gewählten Ve-
wortlich und eine Benachrichtigung des suchenden Knotens schlüsselung aus MAC-Adresse, IP-Adresse. . . und Hash-Funktion
 a) b) c) 3. Fingertable aktualisieren
Nach den ersten beiden Stabilisierungsschritten kann davon
ausgegangen werden, daß der Nachfolger des Knotens exis-
tiert und eine Anfrage gestartet werden kann. Um die Finger-
table für den Node n aufzubauen, ist es notwendig die Nodes
zu finden die für den n + 2i−1 -ten Schlüssel zuständig sind,
Abb. 6: Löschen eines Knotens i ∈ {1, . . . , m}.
4 Implementierung
Eine Umsetzung von Chord erfolgte in der Programmierspra-
Bei der periodischen Ausführung der Stabilisierungsfunktion che Erlang13 . Die Softwareauswahl wurde für Erlang entschieden,
wird p feststellen, dass n der Vorgänger von s ist und aktualisiert denn mit dieser Sprache lassen sich prototypische Implementierun-
dementsprechend seinen Nachfolger-Zeiger auf n (Abbildung 5c) gen verteilter Systeme effizient durchführen. Eine sehr gute und hu-
und informiert seinen neuen Nachfolger, welcher seinen Vorgänger- morvolle Einführung ist für den interessierten Leser mit dem freien
Zeiger auf p setzen wird. Damit ist der Ring wieder in einem stabi- Buch [TH10] gegeben. Die folgende Einführung wurde mit Erlaub-
len Zustand (Abbildung 5d) übergetreten und alle Routinginforma- nis der Autoren aus [MWH10] übernommen.
tionen sind konsistent.
4.1 Erlang
3.2.2 Löschen eines Knotens Erlang ist eine funktionale Programmiersprache die von Erics-
Für das Löschen eines Knotens ist es nicht unbedingt erforde- sons Computer Science Laboratory in den späten 1980er Jahren
lich eine Funktion zur Verfügung zu stellen, da sich der Ring beim entwickelt wurde. Die Sprache, ähnlich wie Java von einer VM
Löschen eines Knotens periodisch stabilisiert. Es ist jedoch aus interpretiert, bringt ein Framework (OTP14 ) für die Entwicklung
Sicht der Datensicherung und der Performanz wünschenswert, denn von parallelen, verteilten und fehlertoleranten Systemen mit. 1998
verlässt ein Knoten freiwillig den Ring11 kann er die Stabilisierung wurde die Sprache und die VM von Ericsson als Open Source zur
autonom durchführen und deutlich beschleunigen. Verfügung gestellt. Die Charakteristika von Erlang sind:
Die erforderte Funktionalität ist einfach: der Node der den
Ring verlassen möchte aktualisiert die Zeiger seines Vorgängers • Funktionen höherer Ordnung
und Nachfolgers so, daß beide aufeinander zeigen, Abbildung 6b. • Prozesse und Message-Passing
Gleichzeitig wechselt der Node in einen Zustand in dem Lookups
• leichte Skalierbarkeit
gleich an den Nachfolger weitergeleitet werden. Dadurch werden
die Ergebnisse der gerade laufenden Stabilisierungsfunktionen so • Soft Real-Time Fähigkeit
manipuliert, dass sich der Ring nach dem Löschen des Knotens in
einem stabilen Zustand befindet (Abbildung 6c). Variablen
In Erlang beginnt ein Name einer Variable immer mit einem
3.2.3 Stabilisierungsphase Großbuchstaben. Werte werden mit Hilfe des Zuweisungsoperators
Da die Topologie dezentral ist gibt es keine zentrale Instanz die = an Variablen gebunden. Es ist zu beachten, dass in Erlang single
die Konsistenz der Routinginformationen gewährleistet. Jeder Teil- assignment gilt, das heisst eine Variable kann nur einmal an einen
nehmer im Ring ist also dafür verantwortlich seine Routinginfor- Wert gebunden werden:
mationen auf dem neuesten Stand zu halten.
Knoten können dem Ring jederzeit verlassen oder beitreten, 1> Q = 4683.
die Routinginformationen der einzelnen Knoten würden somit 4683
ungültig. Die für die Distributed Hash Table grundlegende Lookup 2> A = 30484.
Operation wäre nicht mehr möglich. 30484
Die in [SMK+ 01] als Stabilisierung bezeichnete Aktualisierung 3> Q = A.
der Routinginformationen wird bei jedem Knoten im Ring peri- ** exception error: no match of right
odisch ausgeführt. Die Stabilisierung erfolgt in 3 Schritten: hand side value 30484

1. Nachfolger prüfen Atoms

Jeder Node x prüft, ob er noch der Vorgänger seines Nachfol- Atoms sind durch Namen fest definierte IDs. Die Idee kommt
gers s ist. Ist dies nicht der Fall, ist ein neuer Node n zwischen aus der Programmiersprache Prolog. Atomare Datentypen müssen
beiden aufgetaucht und x setzt seinen Nachfolger-Zeiger auf in Erlang immer mit einen Kleinbuchstaben beginnen oder werden
n, gleichzeitig wird der Vorgänger-Zeiger von n auf x gesetzt. in quotes geschrieben:
2. Vorgänger prüfen > atom1.
Eine Prüfung der Vorgänger-Zeiger ist notwendig um über atom1
den Ausfall eines Nodes notifiziert zu werden. Ist der > ’Atom2’.
Vorgänger-Zeiger nicht existent, so setzt er den Vorgänger- ’Atom2’
Zeiger auf sich selbst. 12 > test@[Link].
’test@[Link]’
Sollte ein Knoten in der nächsten Stabilisierungsphase bemer-
ken, daß sein Nachfolger ausgefallen ist, so wird der nächste Boolescher Datentyp
aktive Knoten in der Fingertable als neuer Nachfolger gesetzt In Erlang existiert kein expliziter Datentyp für Wahrheitswerte.
und die Zeiger aktualisiert. Wahrheitswerte werden durch die Atome true und false darge-
stellt.
11 Also nicht durch einen Systemabsturz o.ä..
12 Bemerkung: In der Fachliteratur wird der Zeiger auf NULL ge- 13 [Link]

setzt, es hat aber keine Auswirkungen ihn auf sich selbst zu setzen. 14 Open Telecommunication Platform
Zahlen Message
Integer A B
Erlang bietet die Möglichkeit Integer mit verschiedenen Basen
zu verwenden. Diese sind im Format BASIS#WERT einzugeben: Prozess A Prozess B (NewFun)
> NewFun ! ping. receive
> -10. PONG! ping ->
-10 ping io:format("PONG!~n")
> 2#101010101010110. end.

21846
> 16#CAFEBABE.
3405691582 Abb. 7: Message Passing in Erlang

Float
Gleitkommazahlen werden gemäß dem 64-bit Format des
IEEE754-1985 Standards abgespeichert (11 bit Exponent, 52 bit
Funktionen
Mantisse): Funktionen können in Erlang ausschliesslich in Modulen defi-
niert werden und können erst nachdem sie kompiliert wurden gela-
> 1.2E10 - 1.2E-10. den werden. Die meisten rekursiven Funktionen nutzen das Pattern-
1.2e10 Matching:
> 1.231.
1.231 mymap(Fun,[]) ->
[];
Tupel mymap(Fun,[Hd|Tl]) ->
Tupel dienen zur Speicherung einer festen Anzahl von Elemen- [Fun(Hd) | mymap(Fun,Tl)].
ten die meist in Beziehung zueinander stehen. Ein Tupel kann un-
terschiedliche Datentypen enthalten und wird durch geschweifte Dieses kurze Programm definiert die map Funktion. Als Funk-
Klammern gekennzeichnet: tion höherer Ordnung ruft map die Funktion Fun (eine anonyme
Funktion) mit jedem Element in der Liste auf und liefert anschlie-
> { ’Map’, 16#BABE }. ßend eine Ergebnisliste gleicher Kardinalität.
{ ’Map’, 47806 }
> tuple_size({ ’Map’, 16#BABE }). Nebenläufigkeit in Erlang
2 Die große Stärke von Erlang ist die Unterstützung von Ne-
Um die Arbeit mit Tuplen zu vereinfachen gibt es in Erlang die benläufigkeit. Jede Funktion kann mittels der Funktion spawn auf-
Funktionen element, tuple size und setelement. gerufen werden und als ein neuer Prozess in der Erlang VM fun-
gieren. Die Erlang VM verwaltet die Prozesse unabhängig vom Be-
Listen triebssystem und verteilt selbstständig die Erlang VM Threads auf
Listen werden wie Tupel für das Abspeichern von Daten ge- Betriebssystem-Prozesse.15 Die Erlangprozesse sind sehr leichtge-
nutzt. Im Unterschied zu Tupeln haben Listen eine variable Anzahl wichtig, da sie innerhalb der Erlang VM lediglich Funktionen sind
an Elementen. Listen werden durch eckige Klammern [] gekenn- und so der Overhead durch Kontextwechsel und Process Control
zeichnet. Blocks entfällt. Der Rückgabewert von spawn ist die Pid16 des neu
> [ ’Map’, 16#BABE ]. erstellten Prozesses.
[ ’Map’, 47806 ]
> length([ ’Map’, 16#BABE ]).
Message Passing
2 Weil ein Aufruf der Funktion spawn asynchroner Natur ist wird
> [ test1 | [ test2 | [] ] ]. ein realisiert Erlang die Kommunikationen zwischen den Prozessen
[ test1, test2 ] mit Hilfe des Message Passing. Nachrichten, Erlang Ausdrücke,
werden an Prozesse mit dem ! Operator gesendet. Die Nachricht
Pattern Matching wird in der Mailbox des empfangenden Prozesses gespeichert und
Erlang nutzt bei der Bindung von Variablen Pattern-Matching mittels Pattern-Matching innerhalb der receive Klausel ausgele-
und ermöglicht es so Werte aus komplexen Datenstrukturen zu ex- sen.
trahieren:
> NewFun = spawn(fun()-> receive
> {person, Name, en} = {person, ’Thomas’, de}. > ping -> io:format("PONG!˜n")
** exception error: no match of > end end ).
right hand side value {person,’Thomas’,de} <0.48.0>
> {person, Name, de} = {person, ’Thomas’, de}. > NewFun ! ping.
{person,’Thomas’,de} PONG!
> Name. ping
’Thomas’
In diesem Beispiel wird ein Prozess erstellt, der innerhalb sei-
Es gibt auch spezielle Operatoren für das Pattern-Matching bei ner receive Klausel auf die Nachricht ping wartet und bei Erfolg
Listen: die Nachricht PONG! herausgibt und beendet. Dies ist dargestellt in
> [Hd | Tl] = [test1, test2, test3]. Abbildung 7.
> Hd.
test1 15 [Link]
erl> Tl. html
[test2, test3] 16 Process identifier in der Erlang VM.
4.2 Chord Listing 3: Stabilisierung
4.2.1 Aufbau updater ( NodePid ) ->
Das System wurde in 3 Schichten aufgeteilt: NodeId = node_id ( NodePid ) ,
{_ , _NextId , NextPid} = node_sc ( NodePid ) ,
Basis Schicht enthält Distanz- und Hashing-Funktionen die als case node_pr ( NextPid ) of
Grundbausteine für den Chord-Algorithmus notwendig sind. { _ , NodeId , NodePid } -> ReqNode = NextPid ;
{ _ , _NewId , NewPid } -> ReqNode = NewPid ;
Chord Schicht ist der Kern der Implementierung. Diese Schicht {error, timeout } -> ReqNode = NodePid
setzt die Funktionen für Node-Join, Lookup und Stabilisie- end,
rungsfunktion um, sowie Hilfsfunktionen für die Kommuni- try finger_table ( NodeId , NodePid , ReqNode ) of
kation zwischen Nodes. FingerTable ->
NewFingerTable = [ {0, NodeId + 1, ReqNode} |
Daten Schicht implementiert, aufbauend auf den unteren Schich- FingerTable],
NodePid ! # msg{id = set_finger , from =self() , data =
ten, die Funktionen für das Abspeichern der Daten und deren NewFingerTable}
Lookup. Intern ist eine einfache Backup-Strategie umgesetzt catch
indem ein Schlüssel zweifach redundant an einen Node und error: badarith ->
dessen Nachfolger verteilt wird, damit Daten nach Absturz FingerTable = [ {I , idistance ( NodeId , math : pow (2 , I
)) , ReqNode } || I <- lists : seq (1 , 3, 1)],
eines Nodes dem Ring erhalten bleiben. NewFingerTable = [ {0, NodeId + 1, ReqNode} |
Die Nodes in dem Chord-Ring werden als Erlang-Prozesse im- FingerTable],
plementiert. Um die Absturzgefahr dieser Prozesse zu minimieren, NodePid ! # msg{id = set_finger , from =self() , data =
NewFingerTable};
kommunizieren diese mittels Funktionen in getrenten Prozessen. _:_ ->
4.2.2 Stabilisierung NewFingerTable = [ {I , idistance ( NodeId , math : pow
Die Stabilisierungsfunktion ist eine der wichtigsten Funktionen (2 , I)) , NodePid } || I <- lists : seq (0 , 3, 1)]
,
für den Chord-Ring. Ohne Stabilisierung wäre nach Absturz eines NodePid ! # msg{id = set_finger , from =self() , data =
Nodes kein lookup mehr möglich und noch wichtiger: es könnte gar NewFingerTable}
kein Chord-Ring aufgebaut werden. end,
Die Stabilisierungsfunktion wird periodisch aufgerufen und ruft SucNodePid = element(3 , node_sc ( NodePid )) ,
SucNodePid ! # msg{id = set_pre , from =self() , data ={NodeId
die Funktion node_updater auf, diese erledigt die eigentliche Ar- , NodePid}},
beit der Stabilisierungsfunktion: ok.
• Neue Nodes in den Ring aufnehmen
Die wichtigste Routine bei konsistenten Hashverfahren ist die
• Nodes ohne Rückmeldung aus den Routingtabellen zu entfer- Bestimmung des für einen Schlüsselbereich zuständigen Node.
nen
Beim Erstellen eines Nodes wird gleichzeitig ein Stabilisierung- Listing 4: Bestimmung des für Schlüssel zuständigen Node
prozess gestartet und mit dem Prozess des jeweiligen Nodes ver- findNode ( HashKey , NodePid ) ->
linkt. Tritt in einem der beiden Prozesse ein Fehler auf, werden bei- NodeId = node_id ( NodePid ) ,
de Prozesse beendet. { _ , PrevId , _PrevPid} = node_pr ( NodePid ) ,
Found = distance ( HashKey , NodeId ) =< distance ( HashKey ,
PrevId ) ,
Listing 2: Periodische Stabilisierung case Found of
node_updater ( NodePid ) -> true -> NodePid ;
receive false ->
after {_Pos , _NextId , NextPid } = node_fs ( HashKey ,
5000 -> NodePid ) ,
updater ( NodePid ) , findNode ( HashKey , NextPid )
node_updater ( NodePid ) end.
end.
4.2.3 Node Join
Mit den Funktionen node_id, node_sc und node_pr kann man Um dem Chord-Ring beizutreten muss dem neuen Node bereits
die Informationen über den Node, den Nachfolger-Node oder den ein Teilnehmer des Ringes bekannt sein. Die Methode join in Lis-
Vorgänger des Nodes abrufen. Der Rückgabewert dieser Funktio- ting 5 bekommt also die Adresse des neuen Nodes: ChordNodePid.
nen ist ein 3-Tupel {Num, Id, Pid}: Anschliessend wird der Hashwert NewNodeId des Nodes aus seiner
Num ist die Enfernung des Nodes vom aktuellem Node (interne Pid NewNodePid bestimmt und die Adresse NextNodePid des Nachfol-
Information) gers im Ring gesucht.
Nachdem diese Informationen bekannt sind, kann die Fingerta-
Id der Hashwert, bestimmt die Position des Nodes in dem Chord-
ble des Knotens neu aufgebaut werden. Gemäß der in Abbildung
Ring
4 gezeigten Strategie wird die bekannte Pid des Nachfolgers ange-
Pid die Pid des Nodes unter Erlang also die Addresse des Nodes fragt und die für NewNodeId+2i verantwortlichen Knoten gesucht.
Die updater Methode überprüft zuerst den Nachfolger des No- Mit NewNodePid !#msg{id=set_finger, from=self(), data=
des, durch Anwendung der Funktion node_sc( NodePid ). An- NewFingerTable} wird die Fingertable des beitretenden Nodes
schliessend wird der Vorgänger (node_pr) des Nodes mit NextPid gesetzt. Abschliessend wird der Vorgängerzeiger auf den, mit
überprüft. Sind die Routinginformationen noch konsistent, d.h. die node_pr( NextNodePid ) gefundenen, Vorgängerknoten gesetzt (der
Zeiger-Informationen sind aktuell, wird die Fingertable auf Basis Vorgänger des neuen Knotens ist, wie in der Theorie erwähnt,
des Nachfolgers gebaut. Ist jedoch ein neuer Node hinzugekom- der Vorgänger des Nachfolgers) und der Vorgängerzeiger des
men, wird die Fingertable auf Basis des neuen Nodes aufgebaut. Nachfolgers gesetzt.
Greift die letzte Regel ist ein Fehler bei der Kommunikation aufge-
treten und der Node NextPid wird aus der Fingertable entfernt und Listing 5: Beitritt eines Nodes
ein neuer Nachfolger ermittelt. join ( NewNodePid , ChordNodePid ) ->
 NewNodeId = node_id ( NewNodePid ) ,
NextNodePid = findNode ( NewNodeId , ChordNodePid ) , Node < Citronella >
NodeID :8 af
FingerTable = [ {X+1 , idistance ( NewNodeId , math : pow (2 ,X NodePID : <0.42.0 >
)) , findNode ( idistance ( NewNodeId , math : pow (2 ,X)) ,
NextNodePid )} || X <- lists : seq (0 ,3 ,1)], Node <Dattel >
NewFingerTable = [{0, NewNodeId + 1, NextNodePid} | NodeID : eb5
FingerTable], NodePID : <0.43.0 >

{_ , PreId , PrePid} = node_pr ( NextNodePid ) , Die NodeID ist ein MD5 Hash (128bit Länge) und stellt die Po-
NewNodePid ! # msg{id = set_finger , from =self() , data = sition im Chord-Ring dar. Für das Beispiel werden nur die ersten 3
NewFingerTable}, Zeichen verwendet, da diese für dieses Beispiel eindeutig sind und
NewNodePid ! # msg{id = set_pre , from =self() , data ={PreId , es nachvollziehbarer machen.
PrePid}},
NextNodePid ! # msg{id = set_pre , from =self() , data ={ 4.4.2 Beitritt der Nodes
NewNodeId , NewNodePid}}, Jeder Node kann die Basis für einen Chord-Ring sein. Im fol-
ok. genden möchte Ananas dem Chord-Ring beitreten, der bisher ledig-
lich aus Banana besteht. Anschliessend treten weitere Nodes dem
4.3 Store Ring bei und erweitern diesen.
Im Chord-Ring werden (Schlüssel,Wert)-Paare gespeichert und
der Befehl zum Speichern kann an die Adresse eines beliebigen, be- join_node ( Ananas , Banana ) ,
join_node ( Citronella , Banana ) ,
kannten Node NodePid gestellt werden. Dieser bestimmt den für den join_node ( Dattel , Citronella ) ,
Schlüssel Key verantwortlichen Node StoreId und dessen Nachfolger
SucceId. Bevor die Stabilisierungsroutinen zur Aktualisierung der Rou-
Anschliessend wird der Befehl zum Speichern des tinginformationen ausgeführt wurden stellt sich der Ring dar als:
(Schlüssel,Wert)-Paar an die Adressen StorePid, SuccePid der
beiden Nodes gesandt oder bei keiner Verbindung nach 2 Sekunden JoinNode
mit einem Fehler quittiert. NodeID :3 e2 ( Ananas )
SuccessorId : e6f ( Banana )
node_store (Key , Value , NodePid ) ->
{ _ , StoreId , StorePid } = find_node (Key , NodePid ) , JoinNode
{ _ , SucceId , SuccePid } = node_successor ( StorePid ) , NodeID :8 af ( Citronella )
SuccessorId : e6f ( Banana )
io : format (" Store Key :˜32.16.0 b\t NodeId :˜32.16.0 b\n" ,[
Key , StoreId]) , JoinNode NodeID : eb5 ( Dattel )
SuccessorId : e6f ( Banana )
StorePid ! # msg{id = store_key , from =self() , data ={Key ,
Value}}, Nachdem die Stabilisierung abgeschlossen ist, stellt ist der Ring
receive dar als:
# msg{id = store_key , from = StorePid , data =ok} -> ok
after
NodeID : eb5 ( Dattel )
2000 -> error
Successor :3 e2 ( Ananas )
end,
NodeID :3 e2 ( Ananas )
io : format (" BackupId :˜32.16.0 b\n" ,[SucceId]) ,
SuccessorID :8 af ( Citronella )
SuccePid ! # msg{id = store_key , from =self() , data ={Key ,
NodeID :8 af ( Citronella )
Value}},
SuccessorId : e6f ( Banana )
receive
# msg{id = store_key , from = SuccePid , data =ok} -> ok
NodeID : e6f ( Banana )
after
SuccessorId : eb5 ( Dattel )
2000 -> {error, timeout}
end.
( Dattel -> Ananas -> Citronella -> Banana -> Dattel )

4.4 Beispiel 4.4.3 put

4.4.1 Erstellen der Nodes Nachdem der Ring in einen stabilen Zustand übergetreten ist,
Zuerst werden die Nodes Ananas, Banana, Citronella und Dat- können (Schlüssel, Wert) Paare im Chord-Ring abgelegt werden.
tel erstellt: Der put Befehl node_store zum Speichern des Paares nimmt als Ein-
Ananas = node_create (" Ananas ") , gabe: Schlüssel, Wert und Node. Der Befehl zum speichern kann an
Banana = node_create (" Banana ") , einen beliebigen Node gesendet werden, welcher die Daten weiter-
Citronella = node_create (" Citronella ") , verteilt.
Dattel = node_create (" Dattel ") ,
Key1 = hash(" lipsum ") ,
Es werden im Beispiel die Namen der Nodes gehashed, damit Key2 = hash(" nes ") ,
für das Beispiel deutlich wird auf welche Nodes die Ressourcen node_store ( Key1 , " Lorem ipsum dolor sit amet " , Ananas ) ,
verteilt werden. node_store ( Key2 , " NES controller to USB gamepad " , Banana )
,
Node <Ananas >
NodeID : 3 e2 Chord ist für dynamische Systeme konzipiert, in dem ein Teil-
NodePID : <0.40.0 > nehmer zu jeder Zeit dem Ring beitreten oder den Ring verlas-
Node <Banana >
sen kann. Das bedeutet, daß Daten redundant im Ring verteilt sein
NodeID : e6f müssen, im Beispielprogramm werden die Daten beim verantwort-
NodePID : <0.41.0 > lichen Node und Nachfolger abgelegt.
 [GL02] G ILBERT, Seth ; LYNCH, Nancy: Brewer’s Conjecture
Store Key :804
NodeId :8 af ( Citronella )
and the Feasibility of Consistent Available Partition-
BackupId : e6f ( Banana ) Tolerant Web Services. In: In ACM SIGACT News,
2002, S. 2002
Store Key :1 d7
NodeId :3 e2 ( Ananas ) [HGL03] H OWARD, Sanjay G. ; G OBIOFF, Howard ; L EUNG,
BackupId :8 af ( Citronella ) Shun tak: The Google File System. 2003
[HJK+ 07] H ASTORUN, Deniz ; JAMPANI, Madan ; K AKULAPA -
4.4.4 get TI , Gunavardhan ; P ILCHIN , Alex ; S IVASUBRAMA -
Anfragen für einen Schlüssel können an einem beliebigen No- NIAN , Swaminathan ; VOSSHALL, Peter ; VOGELS ,
de gestellt werden und die Daten werden im Ring mit der bereits Werner: Dynamo: amazon’s highly available key-value
beschriebenen Lookup Strategie gesucht. store. In: In Proc. SOSP, 2007, S. 205–220
print_lookup ( Key1 , Citronella ) , [KL07] KOHAVI, Ron ; L ONGBOTHAM, Roger: Online Ex-
print_lookup ( Key2 , Citronella ) , periments: Lessons Learned. In: IEEE Computer 40
(2007)
Es antworten die Nodes, die sich für den Schlüssel verantwort-
lich zeigen: [KLL+ 97] K ARGER, David ; L EHMAN, Eric ; L EIGHTON, Tom
; L EVINE, Mathhew ; L EWIN, Daniel ; PANIGRAHY,
Node < Citronella > NodePid : <0.42.0 > KeyId :804 Rina: Consistent Hashing and Random Trees: Distri-
Value : Lorem ipsum dolor sit amet buted Caching Protocols for Relieving Hot Spots on
Node <Ananas > NodePid : <0.40.0 > KeyId :1 d7 the World Wide Web. In: In ACM Symposium on Theo-
Value : NES controller to USB gamepad ry of Computing, 1997, S. 654–663
[Knu98] K NUTH, Donald E.: Art of Computer Program-
4.4.5 Node Leave ming, Volume 3: Sorting and Searching (2nd Editi-
Verlässt ein Node den Ring, im folgenden wird ein Erlang Pro- on). 2. Addison-Wesley Professional, 1998 http:
zess hart terminiert17 , zeigt sich der Backup Node verantwortlich //[Link]/isbn/0201896850. – ISBN
für Anfragen. Ein Node tritt aus dem Ring aus: 0201896850
erlang :exit( Ananas , brutal_kill ) [MWH10] M ARTINOVSK Ý, Filip ; WAGNER, Philipp ; H EINZE,
Stefan: Konzept und Implementierung eines MapRedu-
und ein erneuter Lookup: ce Framework in Erlang. 2010. – FH Zittau-Goerlitz,
Beleg
print_lookup ( Key1 , Dattel ) ,
print_lookup ( Key2 , Dattel ) , [SMK+ 01] S TOICA, Ion ; M ORRIS, Robert ; K ARGER, David ;
K AASHOEK, M. F. ; BALAKRISHNAN, Hari: Chord:
zeigt, daß sich nun Citronella für die Schlüssel verantwortlich A Scalable Peer-to-Peer Lookup Service for Internet
zeigt: Applications, 2001
Node < Citronella > NodePid : <0.42.0 > KeyId :804 [TH10] T ROTTIER -H EBERT, Frederic: Learn You So-
Value : Lorem ipsum dolor sit amet me Erlang: For Great Good. [Link]
[Link]. Version: 2010. – Freies
Node < Citronella > NodePid : <0.42.0 > KeyId :1 d7
Value : NES controller to USB gamepad
Onlinebuch. Lizenziert unter CreativeCommons 3.
[wil07] Numerical Recipes 3rd Edition: The Art of Scientific
5 Fazit Computing. 3. Cambridge University Press, 2007. –
ISBN 0521880688
Es erfolgte eine Einführung in Distributed Hash Tables und das
in [SMK+ 01] vorgestellte Protokoll Chord wurde hinsichtlich sei-
ner Komplexität untersucht und in Erlang implementiert.
A Literatur
[Bre00] B REWER, Eric A.: Towards Robust Distribu-
ted Systems. [Link]/˜brewer/
cs262b-2004/[Link], 2000. – Keynote
Speech at ACM Symposium on the Principles of Dis-
tributed Computing
[FGC+ 97] F OX, Armando ; G RIBBLE, Steven D. ; C HAWATHE,
Yatin ; B REWER, Eric A. ; G AUTHIER, Paul: Cluster-
Based Scalable Network Services, 1997, S. 78–91
[GBL+ 03] G UPTA, Indranil ; B IRMAN, Ken ; L INGA, Prakash ;
D EMERS, Al ; R ENESSE, Robbert van: Kelips: Buil-
ding an efficient and stable P2P DHT through incre-
ased memory and background overhead. In: Procee-
dings of the 2nd International Workshop on Peer-to-
Peer Systems (IPTPS ’03, 2003
17 Es tut auch nicht weh.