Consistent Hashing löste ein echtes Problem verteilter Systeme: Beim Hinzufügen oder Entfernen von Buckets soll nicht jeder Schlüssel neu zugeordnet werden. Der übliche Ring im Karger-Stil brachte jedoch betrieblichen Ballast mit sich: virtuelle Knoten, Speicherbedarf und Ungleichmäßigkeiten, die man wegoptimieren musste.
Der Jump Consistent Hash von Lamping und Veach stellte eine engere Frage: Wenn Buckets fortlaufend nummeriert sind, lässt sich das Ziel eines Schlüssels dann berechnen, ohne überhaupt einen Ring zu speichern? Ihre Antwort passte in etwa fünf Codezeilen.
Das arXiv-Paper gibt an, dass die Methode keinen Speicher benötigt, schneller als der Algorithmus von Karger et al. ist und sowohl den Schlüsselraum als auch die Arbeitslast gleichmäßiger aufteilt, wenn sich die Anzahl der Buckets ändert. Ihr Kompromiss ist ausdrücklich: Fortlaufende Bucket-Nummern machen sie besser für Speicher geeignet als für beliebige Mitgliedschaften in Web-Caches.
Direkt zum letzten Bucket-Wechsel springen
Die Beschränkung auf fortlaufende Bucket-IDs machte einen Mitgliedschaftsring überflüssig.
Minimales Neu-Zuordnen ergibt sich aus dem Sprungprozess: Ein Schlüssel bewegt sich nur, wenn der hinzugefügte Bucket ihn gewinnt.
Keine Lookup-Tabelle bedeutet keinen Speicherbedarf, der neu aufgebaut oder verteilt werden muss.
Die Einschränkung ist ehrlich und nützlich: Der Trick eignet sich besser für Speicher-Shards als für flüchtige Cache-Flotten.
Wenn eine Datenstruktur hauptsächlich dazu dient, ein Wahrscheinlichkeitsgesetz zu bewahren, lässt sich das Gesetz manchmal direkt sampeln, und die Struktur kann verschwinden.
Jump consistent hash wurde zu einer kompakten Option für Sharded Storage, Datenbanken und Bibliotheken, die eine stabile Platzierung mit sehr geringem Implementierungsaufwand benötigen. Seine Eleganz liegt in der Einschränkung: Gibt man beliebige Bucket-Namen auf, verschwindet der ganze Ring.
DEN BELEGEN FOLGEN
Die Quellen
- A Fast, Minimal Memory, Consistent Hash Algorithm arXiv · arxiv.org ·