Seminar zur Nebenläufigkeit in verteilten Systemen Kodierungsverfahren vorgestellt von Jens Brauckmann

Seminar zur Nebenläufigkeit in verteilten Systemen

Kodierungsverfahren vorgestellt von Jens Brauckmann



-Vorgeschlagen von Gagan Agrawal und Pankaj Jalote

„Coding-Based Replication Schemes for Distributed Systems“ IEEE Transaction on Paralleland Distributed Systems, März 1995

-zusätzlich zur Synchronisation der Zugriffe auf replizierte Datenbestände auch Reduktion des Speicherplatzbedarfs

-Kein Verzicht auf Verfügbarkeitsvorteile

-Erhöhte Datensicherheit

- nicht wie bei „Zeugen“ durch weglassen einer Dateikopie sondern durch verteilte Speicherung von Dateistücken

Kodierungsverfahren



Grundidee:

N Stücke

NM

Möglichkeiten diejenigen M Rechner zu wählen von denen Rekonstruiert werden soll

|d| m

|d| m

|d| m

|d| m

|d| m

Größe

Größe

Größe

Größe

Größe

d

Datei

d

Datei

M Stücken

N > M

(Redundanz)

Rechner 1

Rechner 2

Rechner 3

Rechner 4

Rechner 5



Codierung von M. O. Rabin aus seinem Artikel „Efficient dispersal of information for security, load balancing and fault-tolerance“ von 1987.

Eine Datei F mit den Zeichen F= b1 …. bx wird in N Vektoren der Länge M unterteilt. Diese Vektoren werden als Matrix (n, m) geschrieben und mit einer Linear unabhängigen Transformationsmatrix (m,n) multipliziert (z.B.Vandermonde Matrix) . c11 … c1n

cn1 … cnn

b1 … bm

bm+1 …b2m

a11 ... a1n

am1 ... amn

x =

Die Ergebnismatrix C besteht aus N Vectoren die als Dateistücke auf verschiedenen Computern abgelegt werden können.

Für die Rekonstruktion werden lediglich M dieser N Vectoren benötigt: Zunächst werden die Vectoren entsprechend ihrem auftreten in der Matrix C sortiert. Anschließend wird die Transformationsmatrix entsprechen der vorhandenen Dateistücke gekürzt und invertiert.

Multipliziert man nun die invertierte Transformationsmatrix mit der Matrix C‘ erhält man die Ursprungsmatrix (die letztlich nur ein Abbild der Datei ist).

B = C‘ x A‘



d = DateiM = Anzahl der benötigten Stücke für RekonstruktionN = Anzahl der Stück in die unterteilt worden istBedingung: N > MDateigrösse: |d|/M

Replikationsgrad: n

Bedingung: (n N)

n-N = Anzahl der Replikationsstücke

Anstelle von n vollen Dateikopien reduziert sich der Speicherbedarf um einen Faktor M.Höhere Verfügbarkeit aber verkomplizierter leicht den SynchronisationsalgorithmusAnalog zum Votierungsverfahren hat jedes Dateistück eine Versionsnummer, Stimmgewicht und es gibt ein Lese- / Schreib- Quorum mit den Werten für gewichtetes Voten.



Quorumbegriff:

minimal hinreichendes Quorum:• gegenseitiger Ausschluss konkurrierender Zugriffe

• sicherstellen das aktuelle Versionsnummer identifiziert werden kann

QULmh = max ( M, QUL)

QUsmh = max ( k, QUs)

mit k M

k= Anzahl der Dateistücke auf denen eine Operation ausgeführt werden muss

maximal notwendiges Quorum:• Worstcase um sicher zu stellen das M paarweise verschiedene

aktuelle Dateistücke vorliegen

QULmn = n – k + M

QUsmn = max ( QUs , n – N + k)

M = Anzahl der benötigten Stücke für Rekonstruktionn = ReplikationsgradQUL = Grenzwert für LesenoperationQUS = Grenzwert für Schreibzugriff



Beispiel:

N = 10 M = 3 n = 12

QUL = 4 QUS = 9

mit QUL + QUS 12

Jeder Teilnehmer hat ein Stimmgewicht von 1

k = 10 Dateistücke für FortschreibungEs ergibt sich:

QULmh = 4 QUL

mn = 5

QUsmh = 10 QUs

mn = 12

QULmh = max ( M, QUL)

QUsmh = max ( k, QUs)

QULmn = n – k + M

QUsmn = max ( QUs , n – N + k)

(7)

(4) (8)

(9) (9)

k kann nicht beliebig abgesenkt werden



Dynamische Neuordnung:

Bei Write-Operation mit mindestens x Dateifragmenten bei denen weniger als m verschiedene, aber insgesamt mehr als k Dateifragmente vorhanden sind, werden die Dateifragmente neu „verteilt“.

Die x Dateifragemente werden mit den m nötigen Teilen überschrieben .

Damit ändert sich die benötigte Anzahl von Dateistücken um eine Schreiboperation durchführen zu können und somit auch die maximal benötigten Quoren-Grenzen.

QULmn = n – k + M ändert sich zu

QULmn = n –QUS

mh + M [QUsmh = max ( k, QUs) ]

Und QUsmn = max ( QUs , n – N + k) ändert sich zu

QUsmn = max (QUS

mh , QUsmn)



Verfügbarkeit:

p = Wahrscheinlichkeit mit der Dateifragment erreichbar ist

Warscheinlichkeit für eine Quorum-erreichung



Benötigter Speicherplatz pro System ( Fehlerwarscheinlichkeit p = 0.90 )



Speicherplatz und Fehlerwarscheinlichkeit ( Verfügbarkeit bei 0.999 )



Bandbreite für write-Operationen und Verfügbarkeit (p = 0.90 )



Bandbreite für Read-Operationen und Verfügbarkeit ( p = 0.90 )



Verfügbarkeit:

Kodierungsverfahren mit udate sites cardinality



Zusammenfassung:

• Höhere Sicherheit durch Fragmentierung und Codierungsverfahren nach Rabin

• Steigende oder sinkende Anzahl von Teilnehmern läst sich einfach durch Anpassung des Replikationsgrades und damit der Quorum-Grenzen anpassen

• Benötigter Speicherplatz ist stark reduziert (besser als bei „Zeugen“ und reiner Fragmentierung)

• Nachteil: erhöhte Bandbreite bei Read-Operationen

Documents

Seminar zur Nebenläufigkeit in verteilten Systemen Kodierungsverfahren vorgestellt von Jens Brauckmann