Datenpartitionierung und Replikation

Die Datenpartitionierung teilt eine Datenbank zur Skalierbarkeit auf mehrere Knoten auf, während die Replikation Kopien von Daten auf mehreren Knoten für Verfügbarkeit und Leseleistung vorhält; zusammen bestimmen sie, wie eine verteilte Datenbank skaliert und Fehlertoleranz aufweist.

Definition

Partitionierung (Fragmentierung oder Sharding) teilt die Zeilen oder Spalten einer Relation auf mehrere Knoten auf, sodass jeder einen Teil der Daten enthält; Replikation speichert Kopien derselben Daten auf mehreren Knoten; Platzierungs- und Replikationsrichtlinien steuern gemeinsam Skalierbarkeit, Verfügbarkeit und Lastverteilung.

Scope

Dieses Thema behandelt, wie Daten auf Knoten platziert werden: horizontale Partitionierung (Sharding) nach Bereich, Hash oder Liste und vertikale Partitionierung nach Spalten; Partitionierungsstrategien einschließlich konsistenten Hashings; und Replikationsmodelle – synchron versus asynchron, primär-sekundär versus multi-primär – zusammen mit den damit verbundenen Kompromissen zwischen Konsistenz und Verfügbarkeit. Es wird behandelt, wie Partitionierung Parallelität ermöglicht und wie Replikation Fehlertoleranz ermöglicht. Ausgenommen sind die Commit- und Konsensprotokolle, die Replikate in Übereinstimmung halten, welche ein angrenzendes Thema darstellen.

Core questions

• Wie verteilen Bereichs-, Hash- und Listenpartitionierung Zeilen auf Knoten?
• Wann ist vertikale Partitionierung der horizontalen Partitionierung vorzuziehen?
• Wie begrenzt konsistentes Hashing die Datenbewegung, wenn Knoten hinzugefügt oder entfernt werden?
• Welche Kompromisse gibt es zwischen synchroner und asynchroner Replikation?
• Wie unterscheiden sich primär-sekundäre und multi-primäre Replikation in Bezug auf Konsistenz und Verfügbarkeit?

Key concepts

• horizontale Partitionierung (Sharding)
• vertikale Partitionierung
• Bereichs-, Hash- und Listenpartitionierung
• konsistentes Hashing
• synchrone versus asynchrone Replikation
• primär-sekundäre Replikation
• multi-primäre Replikation
• Partitionsschlüssel und Lastverteilung

Key theories

Horizontale und vertikale Partitionierung

Horizontale Partitionierung (Sharding) verteilt die Zeilen einer Tabelle über Knoten mittels eines Partitionsschlüssels, um die Last zu verteilen und parallele Verarbeitung zu ermöglichen, während vertikale Partitionierung eine Tabelle nach Spalten aufteilt; die Partitionierungsfunktion beeinflusst maßgeblich die Lastverteilung und die Abfragelokalität.

Konsistentes Hashing

Konsistentes Hashing bildet Schlüssel und Knoten auf einen Ring ab, sodass das Hinzufügen oder Entfernen eines Knotens nur einen kleinen, begrenzten Anteil von Schlüsseln verschiebt, was es zu einer grundlegenden Technik für die Partitionierung in elastischen verteilten Datenspeichern macht.

Replikationsmodelle und Kompromisse

Synchrone Replikation hält Kopien identisch auf Kosten von Latenz und Verfügbarkeit bei Partitionen, während asynchrone Replikation schneller ist, aber veraltete Daten liefern kann; primär-sekundär zentralisiert Schreibvorgänge, während multi-primär Schreibvorgänge überall erlaubt, auf Kosten der Konfliktlösung.

Clinical relevance

Partitionierung und Replikation sind die Hebel, die Datensysteme skalierbar und verfügbar machen: Sharding ermöglicht es einer einzelnen logischen Datenbank, Arbeitslasten zu bedienen, die keine einzelne Maschine bewältigen könnte, und Replikation hält Dienste über Ausfälle und Regionen hinweg am Laufen und schnell, wodurch diese Techniken für jede große Datenplattform von zentraler Bedeutung sind.

History

Fragmentierung und Replikation wurden in frühen verteilten Datenbanksystemen der späten 1970er und 1980er Jahre untersucht. Konsistentes Hashing, das 1997 von Karger und Kollegen für Web-Caching eingeführt wurde, wurde später von skalierbaren Schlüssel-Wert-Speichern als Partitionierungsschema übernommen, und große Internetdienste popularisierten aggressives Sharding und Replikation für Elastizität und Verfügbarkeit.

Key figures

• M. Tamer Özsu
• Patrick Valduriez
• David Karger

Seminal works

• ozsu2011
• karger1997

Frequently asked questions

Was ist der Unterschied zwischen Partitionierung und Replikation?

Partitionierung teilt die Daten so auf, dass jeder Knoten eine andere Teilmenge enthält, was Speicher und Last zur Skalierbarkeit verteilt. Replikation hält Kopien derselben Daten auf mehreren Knoten für Verfügbarkeit und schnellere Lesevorgänge vor. Die meisten großen Systeme tun beides: Daten werden über Knoten geshardet, und jedes Shard wird mehrfach repliziert.

Warum konsistentes Hashing anstelle von einfacher Hash-Partitionierung verwenden?

Bei der gewöhnlichen modulobasierten Hash-Partitionierung ordnet eine Änderung der Anzahl der Knoten fast jeden Schlüssel neu zu, was eine massive Datenbewegung erzwingt. Konsistentes Hashing ordnet Schlüssel und Knoten auf einem Ring an, sodass das Hinzufügen oder Entfernen eines Knotens nur die Schlüssel in der Nähe dieses Knotens neu zuweist, wodurch das Rebalancing kostengünstig bleibt, wenn der Cluster wächst oder schrumpft.