Daten nach Schlüssel auf Rechner verteilen
Partitionierung, auch Sharding genannt, teilt einen großen Datenbestand nach dem Schlüssel auf mehrere Rechner auf. Jeder Rechner hält nur einen Teil, und jeder Schlüssel liegt auf genau einem Rechner.
Ein Onlineshop mit 20 Millionen Kundendaten passt auf keinen einzelnen Rechner. Man braucht eine Regel, die zu jedem Kunden sagt, wo seine Daten liegen.
Am Ende dieser Lektion
Notiz
Ich kann Daten anhand ihres Schlüssels auf mehrere Rechner verteilen.
Schlüsselwörter
| Begriff | Was er bedeutet | Beispiel |
|---|---|---|
| Partition | ein Teil der Daten, der auf einem Rechner liegt (Shard) | |
| Hashfunktion | macht aus einem Schlüssel eine Zahl | |
| Rest | was bei einer Division übrig bleibt (Modulo) | 7 % 3 ergibt 1 |
| Ring | Positionen, die man im Kreis anordnet | |
| Consistent Hashing | Verteilung mit einem Ring, bei der wenige Schlüssel wandern | |
| Hotspot | ein Rechner, der viel mehr Last trägt als die anderen |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Ein Hash und ein Rest wählen den Rechner
Eine Hashfunktion macht aus einem Schlüssel eine Zahl. Bei drei Rechnern teilen Sie diese Zahl durch 3: Der Rest (0, 1 oder 2) ist die Nummer des Rechners.
Eine echte Hashfunktion verteilt die Schlüssel gleichmäßig. Wir nehmen hier als Spielzeug die Länge des Schlüssels. Sie ist nur zum Üben gedacht und für echte Systeme ungeeignet, denn viele Schlüssel sind gleich lang.
Einen kleinen Client namens v bauen
v() ( printf '%s\r\n' "$*" | nc -w 1 valkey 6379 )Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Die Länge des Schlüssels zählen
printf 'kunde:lea' | wc -cHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Den Rest bei drei Rechnern ausrechnen
expr 9 % 3Hier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Den Datensatz auf Rechner 0 ablegen
v SET schale0:kunde:lea LeipzigHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Ihn dort wieder lesen
v GET schale0:kunde:leaHier angezeigt, nicht ausgeführt. Erstellen Sie ein kostenloses Konto, um „Ausführen“ zu drücken und ihn im Terminal Ihres eigenen Labs einzugeben.
Einen Schlüssel einem Rechner zuordnen
# Ein Spielzeug-Hash: die Summe der Buchstabencodes. Der Rest bei 3 Rechnern wählt den Rechner.
schluessel = "kunde:lea"
summe = 0
for zeichen in schluessel:
summe = summe + ord(zeichen)
print("Summe:", summe)
print("Rechner:", summe % 3)
# Ersetzen Sie lea durch max und starten Sie erneut.
Beim Dazukommen eines Rechners wandern fast alle Schlüssel
Kommt ein vierter Rechner dazu, teilen Sie durch 4 statt durch 3. Für die meisten Schlüssel ändert sich dann der Rest, also der Rechner.
Die Daten müssten fast alle umziehen. Bei einem großen System kostet das Zeit und Netz, genau dann, wenn es ohnehin voll ist.
Zwölf Schlüssel bei 3 und 4 Rechnern
| Schlüssel | 0 bis 2 | 3 bis 5 | 6 bis 8 | 9 bis 11 |
|---|---|---|---|---|
| Rechner bei 3 | 0, 1, 2 | 0, 1, 2 | 0, 1, 2 | 0, 1, 2 |
| Rechner bei 4 | 0, 1, 2 | 3, 0, 1 | 2, 3, 0 | 1, 2, 3 |
| Bleibt am selben Ort | 3 von 3 | 0 von 3 | 0 von 3 | 0 von 3 |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Wie viele Schlüssel wandern
# Wie viele von 12 Schlüsseln wechseln den Rechner, wenn ein vierter dazukommt?
gewandert = 0
for nummer in range(12):
if nummer % 3 != nummer % 4:
gewandert = gewandert + 1
print("Gewandert:", gewandert, "von 12")
# Rechnen Sie mit 20 statt 12 Schlüsseln.
Ein Ring lässt nur wenige Schlüssel wandern
Beim Consistent Hashing liegen Schlüssel und Rechner auf einem Ring mit den Positionen 0 bis 99. Ein Schlüssel gehört dem ersten Rechner, den man von seiner Position im Uhrzeigersinn erreicht. Am Ende des Rings geht es bei 0 weiter.
Kommt ein Rechner dazu, übernimmt er nur die Schlüssel zwischen sich und seinem Vorgänger. Alle anderen bleiben.
Beispiel: ein Ring mit drei Rechnern
| Position des Schlüssels | Nächster Rechner im Uhrzeigersinn | Grund |
|---|---|---|
| 35 | B | B bei 50 ist die erste Position ab 35 |
| 50 | B | Eine gleiche Position zählt |
| 90 | A | Nach 80 kommt der Ringanfang, dort liegt A bei 20 |
| Rechner D bei 65 kommt dazu | D übernimmt 51 bis 65 von C | Alle anderen Schlüssel bleiben |
Die Zellen, die Lernende ausfüllen, bleiben in dieser Vorschau leer.
Den nächsten Rechner auf dem Ring suchen
# Ein Ring mit den Positionen 0 bis 99. Ein Schlüssel geht zum nächsten Rechner im Uhrzeigersinn.
ring = {"A": 20, "B": 50, "C": 80}
position = 35
ziel = ""
kleinste = 100
for name in ring:
if ring[name] >= position and ring[name] < kleinste:
ziel = name
kleinste = ring[name]
print("Position", position, "geht zu", ziel)
# Setzen Sie position auf 35, 50 und dann 90. Bei 90 passiert etwas Neues.
Ein häufiger Fehler
Warnung
Viele denken, bei einem Ring müsse nie etwas umziehen. Das stimmt nicht: Der neue Rechner übernimmt Schlüssel von seinem Nachbarn. Es sind nur viel weniger als beim Rest, nämlich ein Teil des Rings statt fast aller Schlüssel.