Definition - Consistent Hashing (Sharding)

• Generalisierungen:
  • Hash-based Sharding
• Involvierte Definitionen:
  • Hash-based Sharding
  • Sharding
  • Natürliche Zahlen
• Veranstaltung: DEDS
• Referenz: @storl2024 (KE6, NoSQL: Datenmodelle und Techniken; Teil 2.3)

⠀

Definition: Consistent Hashing (Sharding)

Als Consistent Hashing bezeichnen wir eine Technik zur dynamischen Verteilung von Daten auf mehrere Shards auf Basis einer Hash-Funktion.

• Hierbei werden die Daten zunächst mittels einer Hash-Funktion auf einen natürlichen Zahlenbereich abgebildet.

• Anschließend wird jedem Shard eine Teilmenge dieses Zahlenbereiches zugewiesen.

• Wir stellen uns die Shards nun als geschlossenen Ring vor, hier am Beispiel von Modulo 4000:
  

• Wird ein Shard hinzugefügt, so teilen wir den Wertebereich eines oder beider angrenzenden Shards anteilig auf den neuen Shard auf:
  

• Wird ein Shard entfernt, so teilen wir seinen Wertebereich auf einen oder beide angrenzenden Shards auf:
  

Ob nun der nächste, der vorige oder beide angrenzenden Shards für die Verteilung der Daten genutzt werden ist abhängig vom jeweiligen Algorithmus.