- Ausgehend von einem einfachen Bash-Key-Value-Store wird schrittweise gezeigt, warum echte Datenbanken Durability, Atomicity, Isolation und Performance als eigene Designprobleme behandeln müssen
fsync/fdatasync,flockund WAL sind grundlegende Werkzeuge, um Daten bei Ausfällen und Nebenläufigkeit zu schützen, doch je höher das Garantieniveau, desto größer die Performance-Kosten- Storage Engines verwenden Strukturen wie B-tree und LSM tree, um Disk-I/O und Suchkosten zu reduzieren; jeweils mit Wartungsaufwand wie Vacuum bzw. Compaction
- Verteilte Datenbanken gewinnen Verfügbarkeit und horizontale Skalierung, nehmen dafür aber Komplexität verteilter Systeme wie CAP-Theorem, Netzwerkpartitionen, Abstimmung der Konsistenz und Konfliktlösung in Kauf
- Bei der Auswahl oder Implementierung einer Datenbank müssen ACID-Garantien, Isolation Levels, Speicherstruktur, Replikationsmethode und Konsistenzanforderungen an den Workload angepasst werden
Die grundlegenden Datenbankprobleme, die bashdb sichtbar macht
bashdbist ein einfacher Key-Value-Store, der aus zwei Bash-Funktionen bestehtdb_sethängt Daten im Formatkey,valuean eine Datei andb_getkombiniertgrep,sedundtail, um den letzten Wert zu lesen
- Für Lernzwecke ist das simpel, doch schon diese Implementierung zeigt die Probleme, die Produktionsdatenbanken lösen müssen
- Durability: Wenn die Maschine nach einem erfolgreichen
db_setabstürzt, können Daten verloren gehen, die noch nicht auf die Festplatte geflusht wurden - Atomicity: Wenn es während eines Schreibvorgangs zu einem Absturz kommt, können Daten nur teilweise geschrieben und dadurch beschädigt werden
- Isolation: Wenn Lesen und Schreiben gleichzeitig auf denselben Eintrag zugreifen, kann der Leser nur einen Teil der Daten sehen
- Performance:
db_getdurchsucht die gesamte Datei zeilenweise und ist daherO(n)
- Durability: Wenn die Maschine nach einem erfolgreichen
ACID und Versuche, bashdb zu verbessern
- ACID ist ein Akronym für Eigenschaften, die viele Datenbanken garantieren wollen
- Atomicity: Wenn während eines Schreibvorgangs ein Fehler auftritt, wird die gesamte Transaktion abgebrochen oder zurückgerollt, sodass kein Zustand mit teilweisem Schreiben zurückbleibt
- Consistency: Ungültige Transaktionen dürfen die Datenbank nicht beschädigen
- Isolation: Bei gleichzeitigem Zugriff auf dieselben Daten darf es keine Race Conditions geben
- Durability: Erfolgreiche Schreibvorgänge müssen auch nach Ereignissen wie einem Stromausfall erhalten bleiben
- Nicht jede Datenbanktransaktion muss zwingend ACID garantieren; in manchen Anwendungsfällen können Garantien zugunsten der Performance abgeschwächt werden
-
Durability und
fsync- Der Systemaufruf
writeschreibt einen Buffer in eine Datei, bedeutet aber nicht, dass er sofort auf nichtflüchtigen Speicher geschrieben wird - Der Kernel kann Buffer als Dirty Pages im Page Cache speichern und später auf die Festplatte flushen
- Auch Festplattengeräte oder RAID-Systeme können einen eigenen Write Cache haben
fsyncundfdatasyncsind Systemaufrufe, um Dirty Pages auf dauerhaften Speicher zu flushenfdatasyncflusht den anwriteübergebenen Raw Bufferfsyncflusht neben den Daten auch Dateimetadaten wiemtime- Wenn man nach
db_setsync -d databaseanhängt, lässt sich die Durability mit einem Verhalten nahe anfdatasyncerhöhen; üblicherweise ist sync jedoch langsamer als das Schreiben selbst und verschlechtert die Performance - Ein erfolgreicher
fsync()bedeutet: „Alle writes seit dem letzten fsync haben die Festplatte erreicht“, nicht nur „die writes seit dem zuletzt erfolgreichen fsync“ - PostgreSQL war 2018 von diesem Problem betroffen und änderte sein Verhalten so, dass bei einem fsync-Fehler statt eines erneuten Versuchs ein Panic ausgelöst wird
- Dieser Vorfall ist als fsyncgate bekannt; als zugehöriges Material wird das Paper zu fsync failures verlinkt
- Bei MongoDB werden Schreibvorgänge standardmäßig alle 100 ms synchronisiert und sind daher nicht zu 100 % durable
- Der Systemaufruf
-
Isolation und
flock- Die einfachste Methode zur Isolation mehrerer Prozesse in
bashdbbesteht darin, die Speicherdatei vor dem Lesen oder Schreiben zu sperren flockunter Linux sperrt Dateien; mit dem Flag-swird ein Shared Lock verwendet, sodass mehrere Reader gleichzeitig lesen können- Das verbesserte
bashdbnutzt einen Exclusive Lock für Schreibvorgänge und einen Shared Lock für Lesevorgänge - Der Nachteil ist, dass bei jedem Schreibvorgang die gesamte Datenbank gesperrt wird
- Atomicity lässt sich allein mit Bash nur schwer einfach garantieren; denkbar wäre der Einsatz von
mv -Toderrename, wird hier aber nicht vollständig umgesetzt bashdblöst weiterhin nicht das Problem derO(n)-Abfragen
- Die einfachste Methode zur Isolation mehrerer Prozesse in
Rolle und Engpässe von Storage Engines
- Eine Storage Engine bietet eine Abstraktion zum Lesen und Schreiben von Daten in persistentem Speicher; die Hauptziele sind hoher Durchsatz und niedrige Latenz
- Die größte Einschränkung ergibt sich aus den Geschwindigkeitsunterschieden der Speichermedien selbst
- In einer Beispiel-Latenztabelle wird ein L1-Cache-Zugriff mit etwa
0.5ns, ein 4-KB-Random-Read von einer SSD mit150,000nsund ein Disk Seek mit10,000,000nsangegeben - Wenn man einen L1-Cache-Zugriff als Herzschlag von etwa 0,5 Sekunden betrachtet, entspricht ein sequenzieller 1-MB-Read von einer SSD etwa 12 Tagen und ein sequenzieller 1-MB-Read von einer Festplatte etwa 8 Monaten
- In einer Beispiel-Latenztabelle wird ein L1-Cache-Zugriff mit etwa
- Deshalb entwickelt sich das Design von Storage Engines in Richtung einer möglichst starken Reduzierung von Disk-I/O und Disk Seeks
- Typische Designelemente einer Storage Engine sind:
- die grundlegende Datenstruktur, mit der Einträge auf der Festplatte gespeichert werden
- ACID-Transaktionen
- Caches, um Disk Reads zu reduzieren
- API-Schichten wie SQL, Document oder Graph
- Datenstrukturen von Storage Engines lassen sich grob in veränderbare und unveränderliche Strukturen einteilen
- Veränderbare Strukturen können Daten, die in eine Datei geschrieben wurden, später überschreiben
- Unveränderliche Strukturen lesen Daten, die in eine Datei geschrieben wurden, nur wieder aus
Veränderbarer B-tree
- Damit die Performance auch bei wachsender Datenmenge gut bleibt, müssen Einträge nicht wie bei
bashdbüber lineare Suche, sondern höchstens in logarithmischer Zeit gefunden werden können - Ein BST erlaubt
O(log n)-Abfragen, doch wenn die Knoten auf der Festplatte weit voneinander entfernt liegen, können bei der Suche viele Disk Seeks entstehen - Ein B-tree ist eine Verallgemeinerung eines BST, bei der ein Knoten mehr als zwei Kinder haben kann, und nutzt spatial locality
- Von der Festplatte wird in der Regel eine 4-KB- oder 8-KB-Page gelesen; darin werden mehrere Knoten sequenziell im Arbeitsspeicher und CPU-Cache verglichen
- Da Zugriffe auf Arbeitsspeicher und CPU-Cache um mehrere Größenordnungen schneller sind als Festplattenzugriffe, ist es wichtig, möglichst viele der von der Festplatte gelesenen Bytes zu nutzen
- Sequenzieller Speicherzugriff kann dank SIMD, Instruction Pipelining und Prefetching sehr leistungsfähig sein
- Ein B+ tree speichert Werte nur in Leaf Nodes und in den übrigen Knoten nur Keys, sodass auf einer einzelnen Disk Page mehr Keys verglichen werden können
-
Speicherbereinigung und Vacuum
- Ein B-tree muss zur Speicheroptimierung freien Platz zurückgewinnen, der durch Datenfragmentierung entstanden ist
- Beim Update auf einen größeren Wert könnten die Daten des nächsten Knotens überschrieben werden, daher wird der Eintrag an eine andere Stelle verschoben und auf der ursprünglichen Page entsteht ein Loch
- Beim Update auf einen kleineren Wert bleibt am Ende ein Loch übrig
- Beim Löschen entsteht an der Stelle des gelöschten Werts ein Loch
- Diese Speicherbereinigung und das Neuschreiben von Pages können Vacuum, Compaction, Page Defragmentation, Maintenance usw. genannt werden
- Sie werden üblicherweise im Hintergrund ausgeführt, um Latenzspitzen bei Nutzeranfragen zu vermeiden
- PostgreSQL kann einen Auto-Vacuum-Daemon konfigurieren
- B-tree wird häufig als zugrunde liegende Datenstruktur für Indizes verwendet, etwa beim Standardindex von PostgreSQL; DynamoDB wurde einmal scherzhaft als „distributed B-tree“ bezeichnet
Unveränderlicher LSM-Tree
- Der LSM-Tree ist eine Append-only-Datenstruktur, die aus der Beobachtung heraus entstanden ist, dass Disk-Seeks teuer sind
- Wenn Daten nur am Ende einer Datei angehängt werden, muss sich der Festplattenkopf seltener weit zur nächsten Schreibposition bewegen; das ist vorteilhaft für Workloads mit vielen Schreibzugriffen
- Der
Log Structured Merge tree, kurz LSM tree, wird in modernen Datenbank-Storage-Engines wie RocksDB, Cassandra und ScyllaDB verwendet - Die Grundfunktionsweise ist wie folgt
- Schreibvorgänge werden in einer sortierbaren Datenstruktur im Speicher gepuffert
- Beispiele sind
AVL tree,Red Black treeundSkip List - Wenn eine bestimmte Größe erreicht ist, wird in eine sortierte Datei geflusht: eine
Sorted String Table, also SSTable
- Eine SSTable speichert sortierte Daten, sodass sich durch Binary Search und Sparse Index die Disk-I/O reduzieren lässt
- Für Dauerhaftigkeit werden in den Speicher geschriebene Operationen in einem Write-Ahead Log, kurz WAL, protokolliert
- Beim Programmstart wird das WAL gelesen, um den Zustand vor dem Beenden oder Crash wiederherzustellen
- Auch Löschungen werden wie normale Schreibvorgänge angehängt; statt eines Werts wird ein Tombstone gespeichert
- Tombstones werden im Zuge der Compaction entfernt
-
Lesen und Compaction im LSM-Tree
- Beim Lesen in einem LSM-Tree wird zuerst die Datenstruktur im Speicher durchsucht; falls der Eintrag dort nicht vorhanden ist, werden die SSTables auf der Festplatte von den neuesten zu den ältesten Dateien durchsucht
- Je mehr geschrieben wird, desto mehr SSTables müssen geprüft werden
- Auch wenn jede Datei sortiert ist, kann das Durchsuchen vieler kleiner Dateien langsamer sein als das Durchsuchen einer einzigen großen Datei
- Die Vergleichsformel lautet
log(num_files * table_size) < num_files * log(table_size) - Compaction ist ein Hintergrundprozess, der mehrere kleine SSTables zu einer großen SSTable zusammenführt und Tombstones entfernt
- RocksDB implementiert Leveled Compaction
- Neu geflushte SSTables befinden sich auf Level 0
- Wenn sich in einem Level die konfigurierte Anzahl von Dateien angesammelt hat, wird nach der Compaction die neue Datei in das nächste Level hochgestuft
- Beim Entfernen von Tombstones ist Vorsicht geboten
- Es kann zum Problem der Data Resurrection kommen, bei dem gelöschte Einträge bei der Compaction mit älteren Dateien wieder auftauchen
- RocksDB behält Tombstones bis zur Compaction bei, die sie in das letzte Level hochstuft
- Ein praktisches Beispiel in Rust ist im LSM-Tree-Code von dbeel verlinkt
-
Bloom-Filter
- Ein Bloom-Filter ist eine probabilistische Mengen-Datenstruktur, mit der sich effizient feststellen lässt, dass ein Element nicht in einer Menge enthalten ist
- Es gibt zwei mögliche Ergebnisse einer Abfrage
false: Das Element ist definitiv nicht in der Mengetrue: Das Element könnte in der Menge sein
- Ein Bloom-Filter bildet die Ergebnisse mehrerer Hash-Funktionen auf Bit-Positionen einer Bitmap ab und setzt sie auf 1
- Die Platzkomplexität wird im Unterschied zu
O(n)eines normalen Sets mitO(log n)angegeben - Durch mehr Bitmap-Speicher und eine höhere Anzahl von Hash-Funktionen lässt sich die „Wahrscheinlichkeit, sicher ausschließen zu können“ anpassen; dafür gibt es auch einen Rechner
- Ein LSM-Tree speichert für jede SSTable einen Bloom-Filter, sodass die Suche in SSTables übersprungen werden kann, wenn feststeht, dass ein bestimmter Key dort nicht vorhanden ist
WAL und Transaktionsgarantien
- Ein WAL ist ein Verfahren, bei dem alle Transaktionsoperationen in einer speziellen Datei protokolliert werden, um plötzliche Crashes zu überstehen
- Wenn der Datenbankprozess startet, liest er die WAL-Datei und rekonstruiert den Datenzustand
- Transaktionen ohne Commit-Log werden übersprungen, wodurch Atomarität erreicht wird
- Wenn die Daten einer Schreibanfrage im WAL protokolliert und geflusht werden, bevor dem Benutzer geantwortet wird, können sie beim Start garantiert gelesen werden; dadurch wird Dauerhaftigkeit erreicht
- Ein WAL lässt sich als eine Form von Event Sourcing für Transaktionsereignisse betrachten
Isolationsstufen und Nebenläufigkeitskontrolle
- Die Verfahren zur Erreichung von Isolation lassen sich grob in drei Kategorien einteilen
- Pessimistischer Lock: Verhindert den Zugriff auf Daten, die gerade geschrieben werden
- Optimistischer Lock: Ändert eine Kopie der Daten und committet nur dann, wenn sich das Original während der Transaktion nicht geändert hat; andernfalls wird ein Retry durchgeführt
- MVCC: Überschreibt Daten nicht, sondern erzeugt eine neue Version, sodass jeder Benutzer einen Snapshot eines bestimmten Zeitpunkts sieht
- Nicht jede Anwendung benötigt vollständige Isolation, also Serializable Isolation
- ANSI/ISO SQL 92 klassifiziert die Ergebnisse, die entstehen können, wenn eine andere Transaktion während einer Transaktion dieselben Daten verändert, in drei Kategorien
- Dirty Read: Liest Updates einer anderen Transaktion, die noch nicht committet wurden
- Non-repeatable Read: Zwischen zwei Lesevorgängen derselben Row committet eine andere Transaktion, sodass sich der Wert ändert
- Phantom Read: Zwischen zwei Lesevorgängen derselben Menge von Rows mit derselben Bedingung werden Rows hinzugefügt oder entfernt
- Die Isolationsstufen nach ANSI/SQL 92 lauten in absteigender Stärke wie folgt
- Serializable: Liest nur committete Daten und vermeidet Phantom Reads, einschließlich bereichsbasierter Schreibvorgänge über mehrere Rows
- Repeatable Reads: Phantom Reads sind erlaubt
- Read Committed: Non-repeatable Reads sind erlaubt
- Read Uncommitted: Dirty Reads sind erlaubt
- Höhere Isolationsstufen gehen in der Regel mit Performance-Einbußen einher
- Die Isolationsstufen nach ANSI/SQL 92 werden dafür kritisiert, nicht vollständig zu sein
- Viele MVCC-Implementierungen bieten keine Serializable Isolation, sondern Snapshot Isolation
- Als schneller Serializable-MVCC-Algorithmus wird HyPer empfohlen
Warum verteilte Systeme nötig sind und CAP
- Verteilte Systeme bringen viel Komplexität mit sich und sollten vermieden werden, wenn eine nicht verteilte Lösung ausreicht
- Es gibt zwei typische Gründe, Daten auf mehrere Maschinen zu verteilen
- Verfügbarkeit (Availability): Auch wenn die Datenbankmaschine crasht oder die Verbindung zum Benutzer abbricht, können Anfragen an eine andere Maschine gesendet werden
- Horizontale Skalierung (Horizontal Scaling): Statt per Vertical Scaling auf eine größere Einzelmaschine zu skalieren, verhalten sich mehrere über ein Netzwerk verbundene Maschinen wie eine einzige
- Verteilte Systeme führen betriebliche Komplexität und das Problem von Netzwerkpartitionen ein
- Das CAP-Theorem besagt, dass ein System nur zwei der folgenden drei Eigenschaften garantieren kann
- Consistency: Lesevorgänge erhalten den neuesten Schreibvorgang
- Availability: Alle Anfragen sind unabhängig von Ausfällen erfolgreich
- Partition Tolerance: Das System arbeitet weiter, auch wenn Nachrichten zwischen Nodes verloren gehen oder verzögert werden
- Eine Datenbank auf einer einzelnen Maschine hat keine Netzwerkpartitionen und ist konsistent, verstößt aber bei einem Maschinenausfall gegen Availability, weil neue Anfragen fehlschlagen
- Wenn zwei Maschinen getrennte CPUs, Speicher und Festplatten haben und per Kabel verbunden sind, ergeben sich im Fehlerfall unterschiedliche Optionen
- Werden Anfragen abgebrochen, wird Availability geopfert und Consistency gewahrt
- Werden Anfragen nur auf der noch funktionierenden Maschine weiterverarbeitet, wird Consistency geopfert und Availability gewahrt
- Systeme, die Consistency opfern und später ausgleichen, werden eventually consistent genannt
- Netzwerkpartitionen erschweren auch effiziente
JOINs, weil über den Cluster verteilte Daten zusammengeführt werden müssen; die NoSQL-Welt empfiehlt zur Abmilderung Denormalization
Replikation und das Beispiel Amazon Dynamo
- Das ursprüngliche Dynamo-Paper von Amazon wird als Beispiel dafür vorgestellt, dass im Warenkorb von amazon.com availability wichtiger war als consistency
- Wenn Nutzer im Warenkorb denselben Artikel zweimal sehen, können sie einen davon löschen
- Die Einschätzung war, dass dies besser ist als eine Situation, in der der Kauf selbst unmöglich ist
- Um availability zu erreichen, reicht es nicht aus, dass mehrere Nodes die Daten untereinander aufteilen; von jedem Eintrag muss mindestens eine Kopie vorhanden sein
- Ein Node, der eine Kopie eines Eintrags speichert, ist eine replica, der Kopiervorgang heißt replication
- Erhöht man die Anzahl der replicas, steigt die availability, es werden aber mehr Ressourcen zum Speichern der Kopien benötigt
- Datenkopien können auch nicht als Ganzes gespeichert, sondern per erasure coding aufgeteilt und über mehrere Nodes verteilt werden; die entsprechenden Latenzeigenschaften werden im Artikel zu erasure coding behandelt
Consistent Hashing und Datenplatzierung
- Wenn es mehrere Nodes gibt, braucht man ein Load-Balancing- oder Datenpartitionierungsverfahren, das festlegt, welcher Node eine Speicheranfrage verarbeitet
- Ein einfaches Verfahren ist, den primary key zu hashen und anschließend modulo der Anzahl der Nodes zu rechnen
- Wenn ein Node hinzugefügt oder entfernt wird, ändert sich
len(nodes), sodass derselbe key auf einen anderen Node zeigt - In diesem Fall müssen fast alle Einträge migriert werden, was teuer ist
- Wenn ein Node hinzugefügt oder entfernt wird, ändert sich
- Consistent Hashing platziert Nodes nicht in einem Array, sondern auf einem Ring und reduziert so die Zahl der Einträge, die beim Hinzufügen oder Entfernen von Nodes verschoben werden müssen
- Es wird in Datenbanken wie Dynamo und Cassandra verwendet
- Beim Consistent Hashing wird der Hash des Node-Namens auf dem Ring platziert; Eigentümer wird der Node, der nach dem Hash des Anfrage-keys auf dem Ring angetroffen wird
- Die Auswahl von replicas kann erfolgen, indem man gegen den Uhrzeigersinn über den Ring läuft und die Kopien auf den nächsten Nodes speichert
- Fällt der Eigentümer-Node aus, verarbeitet ein replica-Node die Anfrage und erhält so die availability
- Dieses Verfahren wird Leaderless Replication genannt und in Dynamo-artigen Datenbanken wie Cassandra verwendet
- Die Anzahl der keys, die beim Hinzufügen eines Nodes verschoben werden müssen, beträgt im Durchschnitt
num_keys / num_nodes - Ein virtual node platziert einen physischen Node mehrfach auf dem Ring und verringert so die Wahrscheinlichkeit, dass einzelne Nodes deutlich mehr Einträge besitzen
- Ein Beispiel ist, dem Node-Namen einen Index als Suffix anzuhängen, etwa
"half-0"oder"half-1"
- Ein Beispiel ist, dem Node-Namen einen Index als Suffix anzuhängen, etwa
- Ein anderes Verfahren zur Auswahl von leader node und replica node ist leader election, wird hier aber nicht behandelt
Leaderless Replication und Konsistenzabstimmung
- Eine leaderless-Konfiguration opfert consistency zugunsten hoher availability
- Wenn der Eigentümer-Node bei einer write-Anfrage down ist, wird auf eine replica geschrieben; nachdem der Eigentümer-Node wieder hochgefahren ist, kann eine read-Anfrage veraltete Daten lesen
- Wenn für eine bestimmte Anfrage consistency nötig ist, sendet man die read-Anfrage parallel an mehrere replicas und den Eigentümer-Node, und der Client wählt die neuesten Daten aus
- write-Anfragen werden üblicherweise parallel an alle replicas gesendet, wobei nur auf acknowledgements von einigen Nodes gewartet wird
- Um consistency auf Anfrageebene abzustimmen, prüft man
R + W > N/2 + 1N: Anzahl der Nodes mit einer DatenkopieW: Anzahl der Nodes, die für einen erfolgreichen write ein acknowledgement liefern müssenR: Anzahl der Nodes, die für einen erfolgreichen read antworten müssen
- Eine Anfrage an die Mehrheit der Nodes, bei der
WoderRgleichN/2 + 1ist, wird quorum genannt -
Konfliktauflösung
- Der Prozess, den neuesten write auszuwählen, ist Conflict Resolution
- Ein bloßer Vergleich von timestamps ist in verteilten Systemen schwer verlässlich zu machen
- Jede Maschine hat ihre eigene hardware clock, und clocks sind nicht perfekt genau, sodass drift entsteht
- NTP bezieht die Zeit aus einer genaueren Zeitquelle, aber da die Anfrage selbst über das Netzwerk läuft, lässt sich die Zeit bis zur Antwort nicht exakt bestimmen
- Cassandra verwendet timestamps; die zugehörige Dokumentation ist unter Cassandra data versioning verlinkt
- Google Spanner hat consistency-Garantien auf clock-Basis durch spezielle hochpräzise Zeithardware und eine API erreicht, die den Unsicherheitsbereich von timestamps offenlegt; das zugehörige Paper ist das Spanner paper
- Systeme wie Dynamo reduzieren einen Teil der Konflikte mit Version Vectors
- Jeder Eintragsversion wird ein
(node, counter)-Paar zugeordnet, um kausale Beziehungen zwischen Versionen zu ermitteln - So lassen sich eindeutig neuere Versionen finden und einige ältere Werte entfernen
- Als weiterführendes Material sind Dotted Version Vectors verlinkt
- Wie bei Riak KV kann man auch alle konfliktbehafteten Werte an die Anwendung zurückgeben und sie auf Basis ihres Wissens über die Daten auflösen lassen
- Verschiedene Techniken zur Reduzierung von Konflikten in eventually consistent Systemen werden meist unter dem Begriff Anti Entropy zusammengefasst
Anti-Entropy-Techniken
-
Read Repair
- Nachdem der Client aus den read-Ergebnissen mehrerer Nodes den neuesten Wert ausgewählt hat, sendet er diesen Wert erneut an die Nodes, die ihn noch nicht gespeichert haben, und repariert sie so
-
Hinted Handoff
- Wenn eine write-Anfrage den Ziel-Node nicht erreicht, wird sie als hint auf einem anderen Node gespeichert
- Sobald der Ziel-Node wieder available ist, wird der gespeicherte hint übergeben
- Bei quorum writes wird dieses Verfahren auch
Sloppy Quorumgenannt und erhöht die availability von quorum-Anfragen weiter
-
Merkle Trees
- Da read repair nur abgefragte Daten korrigiert, können viele Daten lange inkonsistent bleiben
- Den gesamten Unterschied durch Synchronisierung zwischen Nodes zu finden, ist bei großen Datenmengen mit
O(n)teuer - Ein Merkle tree ist eine hierarchische Struktur, bei der Hashes von Datenbereichen in den Blättern gespeichert werden und Elternknoten einen Hash speichern, der die Hashes ihrer Kinder kombiniert
- Sind die Root-Hashes gleich, sind die Daten zweier Nodes gleich; unterscheiden sie sich, vergleicht man rekursiv die darunterliegenden Hashes, um inkonsistente Daten zu finden, und kann die Synchronisierung so auf
O(log n)beschleunigen
-
Gossip Dissemination
- Ein Verfahren, um Events einfach und zuverlässig im gesamten Cluster zu verbreiten
- Ein Node sendet eine Nachricht an eine konfigurierte Anzahl zufälliger Nodes, also den fanout, und empfangende Nodes senden sie wiederum an
Nzufällige Nodes - Wenn dieselbe gossip-Nachricht die konfigurierte Anzahl von Malen gesehen wurde, wird sie nicht weiter broadcastet
- Verlinkt ist ein simulator, mit dem man die Datenkonvergenz nachvollziehen kann
- gossip-Nachrichten werden üblicherweise per UDP übertragen
Bereiche für eine vertiefte Behandlung
- Datenbanken umfassen neben den hier behandelten Inhalten viele weitere Themen
- Bei der Auswahl oder Implementierung einer Datenbank sollte man gemeinsam betrachten, wie Storage Engine, ACID, Isolation Levels, verteilte Replikation und Verfahren zur Konfliktauflösung zu den tatsächlichen Anforderungen passen
1 Kommentare
Hacker-News-Kommentare
Die Methode
compacthat einen Bug: Tombstones sollten nur beim Kompaktieren der letzten, also der größten Ebene, übersprungen werden, und nicht zwischen allen Ebenen entfernt werden.Andernfalls verschwinden Tombstones aus höheren Ebenen während der Kompaktierung, sodass Einträge aus niedrigeren Ebenen wieder sichtbar werden.
In LSM-basierten Datenbanken ist es eines der Merkmale, dass Lösch-/Tombstone-Records lange bestehen bleiben; einige Datenbanken wie RocksDB enthalten Optimierungen, um das zu vermeiden.
Die Funktionen für Range Deletes kenne ich, aber zu Deletes einzelner Keys habe ich kaum etwas gelesen.
Viele lernen Datenbanken, während sie SQL lernen; ich empfehle aber, sie über einen solchen Kurs und über das Verständnis von B-Bäumen zu lernen.
Die Vor- und Nachteile von RDBMS versteht man größtenteils, wenn man B-Bäume und deren Auswirkungen auf Key-Inserts, Lookups und Sortierung kennt.
Viele versuchen, Datenbanken durch zusätzliche Indizes schneller zu machen, aber letztlich legt man damit nur einen weiteren Baum auf einen Baum und verdeckt das eigentliche Problem.
Manche Probleme passen gut zu B-Bäumen, viele aber nicht.
SQL ist lediglich eine Query-Schnittstelle zu einem entfernten B-Baum-System.
B-Bäume sind nicht die einzige Indexing-Strategie, und es ist auch allgemein bekannt, dass Indizes ein Mittel sind, um Lese-Performance auf Kosten der Schreib-Performance zu erhöhen.
Denn Datenbanken verarbeiten in der Regel sehr viel mehr Reads als Writes.
Mich würde interessieren, welches Problem genau durch „einen weiteren Baum auf einen Baum legen“ verdeckt wird und wie man es lösen will, ohne Indizes anzufassen.
Für Tabellen ab einer gewissen Größe sind Indizes praktisch unverzichtbar.
Man sollte Dinge wie B-Bäume und Hash-Indizes, die I/O-Schicht und Prozessmodelle lernen.
Heutzutage lohnt es sich auch, allgemeine Strategien spaltenorientierter Datenbanken zu lernen: späte Tuple-Materialisierung, Lazy Execution, lineare Scans und binäre Suche, Instruction Pipelining und Ähnliches.
Wenn man damit vertraut ist, erkennt man in der Praxis auch, wann kein DBMS nötig ist, sondern einfache Flat Files oder eine eingebettete Datenbank wie RocksDB ausreichen.
Natürlich kann es auch Covering Indexes geben.
Zur Empfehlung „Vermeide verteilte Systeme, wenn eine nicht verteilte Lösung ausreicht“ würde ich das Gegenteil sagen.
Jedes nicht triviale Produktionssystem ist ein verteiltes System.
Wenn die Datenbank zumindest ein Replica Set ist, ist es bereits ein verteiltes System; verteilte Systeme nicht zu lernen bedeutet also, ein Risiko einzugehen.
https://jepsen.io/ und https://raft.github.io/ sind einen Blick wert.
Das heißt aber nicht, dass es in Ordnung ist, sie überall einzuführen; dadurch steigt die Komplexität unnötig stark.
So formuliert widerlegt das nicht den Rat, unnötige Komplexität zu vermeiden. Der Kern ist nicht, ob etwas technisch verteilt ist, sondern ob es wirklich nötig ist.
Verteilte Systeme zu lernen ist etwas anderes, als sie einzusetzen.
Wichtig ist, ob man nach dem Lernen noch die Zurückhaltung aufbringt, sie nur dort anzuwenden, wo sie passen.
Heutzutage wird oft viel Aufwand betrieben, einfache, gut funktionierende Systeme auf ein stärker verteiltes Modell zu migrieren, als ob das nahezu kostenlos wäre.
Betrachtet man jedoch das zu lösende Problem und die Größenordnung, war in vielen Fällen offensichtlich eine einzelne Postgres-Instanz mit einem Monolithen ausreichend.
So verstehe ich den Rat im Original.
Zumindest muss es nicht zwangsläufig so sein.
Ich würde weiterhin empfehlen, eine einfache Lösung zu wählen.
Systeme schaffen es oft schon bei „trivialen und einfachen Speichern“ nicht, persistenten Zustand korrekt zu speichern, zu sichern und wiederherzustellen.
Den Zustand eines verteilten Speichers in einem Disaster-Recovery-Szenario wiederherstellen zu wollen, ist noch schwieriger.
Man kann zuerst eine funktionierende Backup-Lösung haben und danach eine verteilte Lösung einführen.
Auch eine Master-Konfiguration mit Read-only-Replicas ist nicht das, was die meisten Leute mit „verteilt“ meinen, weil die Writes nicht verteilt sind.
In der Praxis bedeutet verteilt meist, dass Daten geshardet werden, und das ist etwas, das man unbedingt vermeiden möchte, wenn es nicht wirklich nötig ist.
Ich fand es interessant zu lesen, weil es die vielen Konzepte, die beim Bau einer Datenbank relevant sind, gut überblickt.
Es reicht von SIMD, um auf einer einzelnen Maschine Performance herauszuholen, bis hin zu Konsensalgorithmen.
Wenn es schon um Datenbanken, Zuverlässigkeit und verteilte Systeme geht, lohnt es sich auch, formale Methoden zu lesen, die sich auf solche Situationen und interne Datenbankimplementierungen anwenden lassen.
Es gibt ein interessantes Paper des S3-Teams, das mit TLA+ modelliert wurde.
[0] Use of Formal Methods at Amazon Web Services
https://lamport.azurewebsites.net/tla/formal-methods-amazon....
[1] How Amazon Web Services uses formal methods
https://www.amazon.science/publications/how-amazon-web-servi...
Bei Konsistenz gibt es Datenbankkonsistenz und Anwendungskonsistenz.
Beispielsweise kann man auf Ebene einer einzelnen Tabelle Atomicity, Isolation und Durability erreichen, aber bei Writes über mehrere Tabellen hinweg scheitern.
Sobald man beginnt, Transaktionen zu behandeln, die mehrere Tabellen gleichzeitig aktualisieren, wird Konsistenz wichtig.
Entweder müssen alle Tabellen gleichzeitig aktualisiert werden, oder keine.
Das Design mit einer Dokument-API wie MongoDB, leaderloser Replikation wie Cassandra und einer Thread-per-Core-Architektur wie ScyllaDB ist sehr cool.
Außerdem ist alles in Rust geschrieben.
Die Phase, in der „die Bücher die Neugier geweckt haben und man selbst eine kleine Datenbank gebaut hat“, durchlaufen wohl viele Entwickler irgendwann einmal.
Ich würde nicht versuchen, sie davon abzuhalten. Wenn man es selbst ausprobiert, lernt man wirklich viel darüber, was nicht funktioniert.
Wenn man sich die Zeit nehmen kann, ist das eine äußerst wertvolle Lektion.
Dass ich selbst einmal eine Datenbank gebaut habe, hat meinen Respekt vor bestehenden Lösungen am stärksten wachsen lassen.
Bytes schnell auf die Festplatte zu schreiben und von dort zu lesen, ist nicht der schwierige Teil.
Wirklich schwierig ist es, über Jahre hinweg zuverlässig zu funktionieren und dabei Anwendungsfälle zu unterstützen, an die man nie gedacht hätte.
Welche Effizienz ließe sich gewinnen, wenn man ein domänenspezifisches DBMS unter der Annahme entwirft, dass Anwendungsfälle außerhalb der Domäne verboten sind und ignoriert werden können?
Zum Beispiel verwenden wir heute auch für Datensätze, die im Grunde append-only sind, Allzweckdatenbanken.
Wie wäre eine Datenbank, in der es überhaupt kein Konzept für Aktualisierung oder Löschung bestehender Zeilen gibt, sondern nur Einfügen und das Löschen ganzer Tabellen/Datensätze?
Müsste eine solche Datenbank keine MVCC-Transaktionen implementieren? Könnte jede Tabelle selbst das Write-Ahead-Log sein und man so ein separates Write-Ahead-Log vermeiden? Könnte man effizienter speichern? Könnte man Indexierung mit Atomarität auf Chunk-Ebene statt auf Ebene der gesamten Tabelle bauen und so Locks reduzieren?
Lässt sich die Atomarität der Bash-Version nicht „einfach“ erreichen, indem man die Datei in eine temporäre Datei kopiert, sie dort ändert und dann
sync; mv; syncverwendet?grep-Filter auch Duplikate vermeiden.Beim Kopieren könnte man nebenbei auch Sortierung garantieren, aber nur mit „bash“ und den Standard-Utilities scheint das nicht besonders sinnvoll zu sein.
Für solche Zwecke gibt es DJBs CDB, also cdbget, cdbmake usw.:
https://cr.yp.to/cdb.html
Hervorragender Artikel.
Das Buch Database Internals sieht gut aus; gibt es weitere ähnliche Bücher, die tief in die interne Implementierung eintauchen?
https://www.youtube.com/c/cmudatabasegroup
Sowohl Einführungs- als auch fortgeschrittene Kurse sind online, dazu gibt es Vorträge und Lehrveranstaltungen zu Produkten aus der Industrie.
Sehr nützlich.
Als Material mit stärker theoretisch-informatischer Perspektive auf höherer Ebene und weniger Fokus auf physischer Implementierung ist das „Alice“-Buch, also „Foundations of Databases“, ausgezeichnet.
Es ist sehr dicht und mathematisch, behandelt aber relationale Algebra, Datalog und die Übersetzung von Datalog in relationale Algebra.
Die gedruckte Ausgabe ist inzwischen schwer zu bekommen, und das gebraucht gekaufte Exemplar kam mit kaputter Bindung und herausfallenden Seiten an, aber das ganze Buch ist online verfügbar: http://webdam.inria.fr/Alice/
https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
Allerdings ist Database Internals moderner.
Mir gefällt, dass der Artikel „Datenbanken“ nicht mystifiziert, sondern mit einer trivialen Implementierung als Bash-Einzeiler beginnt.
Ein hervorragender Einstieg.