Lehrplan Lektion 27 von 148 · Nutze KI zum Verstehen
Nutze KI zum Verstehen

KI aus Zwilling: der Hash Ring

Warum das wichtig ist Das verpackte Log in Fixation on yourself hatte eine Idee im Kern. Hier ist es wieder, in einem System, das du wirklich bauen könntest, mit dem Tutor aus.

Der Tutor ist für dieses Problem ausgeschaltet. Arbeite es selbst heraus.

A Cache-Cluster verteilt Keys über Server mit Consistent Hashing. Jeder Server besitzt einige Positionen auf einem Ring aus ganzen Zahlen von 0 bis etwa zwei Milliarden. Ein Key wird zu einer Zahl gehasht und gehört zur ersten Node-Position bei oder nach dieser Zahl, wobei der Ring umrundet wird: nach der größten Position springt er zur kleinsten.

Die Knotenpositionen sind sortiert in einer gemeinsamen Tabelle gespeichert, aber die Tabelle ist ein Circular Buffer: sie beginnt dort, wo der letzte Schreiber aufgehört hat. Jeder Lesezugriff auf die Tabelle ist ein Netzwerk-Round-Trip, also werden die Lesevorgänge gezählt.

Die Daten

from creative.budget import Tape
ring = Tape([700, 900, 100, 300])   # sorted positions 100, 300, 700, 900, stored from 700
hashes = [250, 950]
# owners(ring, hashes) -> [300, 100]
Du bist dran

Schreibe owners(ring, hashes). ring ist eine Tape von unterschiedlichen Knotenpositionen, die sortiert sind, aber rotiert sein können (gespeichert von einem beliebigen Startpunkt, möglicherweise 0). Sie enthält mindestens einen Knoten. Für jeden Hash h gib die kleinste Position >= h zurück; wenn es keine gibt, gib die kleinste Position von allen zurück. Budget: mit 100.000 Knoten und 200 Hashes darfst du höchstens 20.000 Werte lesen. len(ring) ist kostenlos.

KI aus: kein Tutor, keine Hinweise oder gelöste Lösung für diese Aufgabe. Nur dein eigenes Denken.

Ein Problem in dieser Lektion entdeckt? Melde es · Frage zu dieser Lektion

Diese Übung öffnet bald

Beende die vorherige Lektion, damit diese freigeschaltet wird. Der ganze Kurs ist kostenlos, kein Konto erforderlich, und du kannst diese Lektion jetzt direkt lesen.