Die Risiken von UUID-Primärschlüsseln in SQLite

 (andersmurphy.com)
1 Punkte von GN⁺ 4 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • Die Implementierung von Primärschlüsseln in SQLite führt bei normalen rowid-Tabellen und WITHOUT ROWID-Tabellen zu einer unterschiedlichen physischen Speicherreihenfolge; wird eine zufällige UUID4 als Clustered Index verwendet, entstehen Kosten durch B-Tree-Neubalancierung und zusätzliches Paging
  • Die Integer-rowid-Baseline liegt bei Einfügungen in Schritten von 1 Million Zeilen grob bei 1 Million Einfügungen pro Sekunde, während UUID4 WITHOUT ROWID 14- bis 16-mal längere Einfügezeiten verzeichnete
  • Die ungeordnete Eigenschaft von UUID4 führt dazu, dass Zeilen zufällig in den B-Tree eingefügt werden; im Profiling wurde mehr Zeit für Baum-Balancierung sowie Lese- und Schreibvorgänge aufgewendet
  • UUID7 WITHOUT ROWID verringerte als zeitlich geordnete UUID die Sortierungsprobleme von UUID4 und zeigte dadurch deutlich vernünftigere Einfügezeiten, blieb aber wegen des 16-Byte-BLOB-Schlüssels weiterhin langsamer als ein 8-Byte-Integer-Schlüssel
  • UUID4 WITH ROWID profitiert zwar von der Sequenzialität des versteckten rowid, leidet aber weiterhin unter Write Amplification durch zwei Indizes sowie unter den Kosten zufälliger Index-Einfügungen und ist daher langsamer als UUID7 WITHOUT ROWID

Was ist ein Clustered Index?

  • Ein Clustered Index ist der Index, der die physische Speicherreihenfolge der Tabellenzeilen bestimmt
  • Da Zeilen physisch nur auf eine Weise sortiert werden können, kann es pro Tabelle nur einen Clustered Index geben
  • Der Clustered Index ist die Tabelle selbst; nicht-clustered Indizes speichern nur die indizierten Spalten und einen Zeiger auf die Position der eigentlichen Zeilendaten

Rowid

  • Jede normale SQLite-Tabelle besitzt einen impliziten 64-Bit-Integer-Primärschlüssel namens rowid
  • Die Tabellendaten werden in einer B-Tree-Struktur gespeichert, die für jede Zeile einen Eintrag enthält und den rowid-Wert als Schlüssel verwendet
  • rowid ist faktisch der Clustered Index von SQLite, und die physische Speicherreihenfolge der Zeilen folgt der rowid-Reihenfolge
Anzeige

WITHOUT ROWID

  • SQLite unterstützt WITHOUT ROWID-Tabellen, in denen kein implizites rowid vorhanden ist
  • In WITHOUT ROWID-Tabellen übernimmt der deklarierte Primärschlüssel die Rolle des Clustered Index
  • SQLite-rowid-Tabellen sind als B*-Tree implementiert, bei dem der gesamte Inhalt in den Blättern gespeichert wird; WITHOUT ROWID-Tabellen verwenden dagegen einen normalen B-Tree, der Inhalte sowohl in Blättern als auch in inneren Knoten speichert

Baseline: Integer-Primärschlüssel mit rowid

  • Als Baseline wurde die Einfügezeit in Schritten von 1 Million Zeilen in einer normalen rowid-Tabelle mit der Struktur id INTEGER PRIMARY KEY, data BLOB gemessen
  • In der Ergebnistabelle reicht die Gesamtzahl der Zeilen von 10 Millionen bis 100 Millionen, die gemessene Zeit von 692 ms bis 838 ms
  • Die Baseline-Leistung liegt grob bei etwa 1 Million Einfügungen pro Sekunde

UUID4 WITHOUT ROWID

  • Der UUID4-Test fügte in eine WITHOUT ROWID-Tabelle mit der Struktur id BLOB PRIMARY KEY, data BLOB den Wert random-uuid4-bytes als Primärschlüssel ein
  • In der Ergebnistabelle beträgt die gemessene Zeit bei 10 Millionen Zeilen 2649 ms und bei 100 Millionen Zeilen 12586 ms
  • Die Einfügeleistung ist damit 14- bis 16-mal langsamer als die Integer-rowid-Baseline

Profiling

  • Der normalisierte Diffgraph vergleicht Profiling-Snapshots von INTEGER und UUID4 und zeigt die Unterschiede in einer Flamegraph-Struktur
  • In der normalisierten Ansicht wird die Gesamtzahl der Samples beider Profile angeglichen, damit sich relative Unterschiede prozentual erkennen lassen
  • Blaue Frames zeigen Funktionen, bei denen die Zeit im zweiten Profil UUID4 gegenüber INTEGER gesunken ist; rote Frames zeigen Funktionen, bei denen sie unter UUID4 gestiegen ist
  • Die Farbintensität steht für die Veränderung der Sample-Zahl des jeweiligen Frames selbst, also für die relative Veränderung der Self Time Delta
  • Im Diffgraph wird mehr Zeit für Baum-Balancierung sowie Lese- und Schreibvorgänge aufgewendet
  • Wegen der ungeordneten Eigenschaft von UUID4 werden Schlüssel in zufälliger Reihenfolge sortiert, wodurch SQLite den B-Tree fortlaufend neu balancieren muss
Anzeige

UUID7 WITHOUT ROWID

  • UUID7 ist eine zeitlich geordnete UUID und kann die Sortierungsprobleme von UUID4 beseitigen
  • Der UUID7-Test wurde ebenfalls auf einer WITHOUT ROWID-Tabelle mit der Struktur id BLOB PRIMARY KEY, data BLOB ausgeführt
  • In der Ergebnistabelle beträgt die gemessene Zeit bei 10 Millionen Zeilen 1372 ms und bei 100 Millionen Zeilen 1258 ms
  • UUID7 WITHOUT ROWID kommt damit auf deutlich vernünftigere Werte als UUID4 WITHOUT ROWID, ist aber gegenüber der Baseline weiterhin langsamer
  • Der Unterschied liegt auch darin, dass ein UUID-BLOB-Primärschlüssel 16 Byte groß ist, ein Integer-Primärschlüssel dagegen 8 Byte

UUID4 WITH ROWID

  • Der Test UUID4 WITH ROWID verwendet eine Tabelle id BLOB PRIMARY KEY, data BLOB ohne WITHOUT ROWID
  • In dieser Konfiguration ist das versteckte rowid der Clustered Index; sein Vorteil ist die Sequenzialität
  • Der Nachteil ist, dass dadurch zwei Indizes für die Tabelle entstehen, was zu Write Amplification führt
  • In der Ergebnistabelle beträgt die gemessene Zeit bei 10 Millionen Zeilen 2003 ms und bei 100 Millionen Zeilen 7119 ms
  • UUID4 WITH ROWID ist nicht so performant wie UUID7 WITHOUT ROWID; auch ohne als Clustered Index zu dienen, muss der Index wegen zufälliger Einfügungen fortlaufend neu aufgebaut werden

Fazit

  • UUID-Primärschlüssel in SQLite sind eine Designentscheidung, bei der sich die Einfügeleistung je nach Clustered Index und Sortierbarkeit des Schlüssels stark unterscheiden kann
  • Das Problem zufälliger UUIDs ist nicht auf SQLite beschränkt, sondern betrifft auch andere Datenbanken mit Clustered Index
  • Der vollständige Benchmark-Code ist im GitHub-Repository veröffentlicht

Verwandte Beiträge

1 Kommentare

 
GN⁺ 4 시간 전
Lobste.rs-Kommentare

  • Gut. Es wäre auch interessant, Zahlen dafür zu sehen, was passiert, wenn in einer rowid-Tabelle Integer-Schlüssel nicht monoton ansteigen, sondern zufällig sind
    Ein wichtiger Punkt, der im Artikel fehlt, ist, dass der Primärindex von rowid-Tabellen ein B+-Baum ist, während without rowid-Tabellen einen B-Baum verwenden
    Deshalb ist Letzteres im Allgemeinen nicht ideal, sobald die durchschnittliche Datensatzgröße einen bestimmten Schwellenwert überschreitet. Der Grund ist, dass die internen Knoten des Index den gesamten Datensatz speichern, und soweit ich mich erinnere, nennt das SQLite-Handbuch als Faustregel 1/20 der Seitengröße

  • Es wurde so viel Aufwand in die Messung der UUID-Performance gesteckt, aber natürliche Schlüssel wurden nicht berücksichtigt
    Ob Integer, UUID oder etwas anderes: Surrogatschlüssel erhöhen die Komplexität, fügen keine Information hinzu und verdecken Normalisierungsfehler
    Der Autor nennt als Grund für UUIDs „Duplikate vermeiden“, aber das ist kein Grund. Jede Zeile in jeder Tabelle jeder Datenbank sollte mindestens einen Schlüssel haben, also eine Menge von Spalten, die diese Zeile eindeutig identifiziert
    Eine Datenbank ohne einen solchen Schlüssel enthält doppelte Informationen und ist anfällig für logische Inkonsistenzen. Eine Datenbank, die einen solchen Schlüssel bereits hat, braucht keinen Surrogatschlüssel. Wenn ein natürlicher Schlüssel bereits existiert und durchgesetzt wird, dann muss die Behauptung „aus Performancegründen nötig“ belegt werden, denn sie bedeutet zusätzliche Kosten und unnötige Komplexität

    • Vielleicht fehlt mir die Vorstellungskraft, aber wenn man mit Daten aus der realen Welt arbeitet, ist es meist schwer, einen echten natürlichen Schlüssel zu finden
      Werte, die auf den ersten Blick eindeutig wirken, sind oft nicht so eindeutig wie erwartet, oder Werte, die unveränderlich erscheinen, müssen am Ende doch geändert werden
      Mit Surrogatschlüsseln kann ich dagegen die Identität innerhalb meines Systems definieren, ohne davon abhängig zu sein, wie jemand anderes Eindeutigkeit definiert hat oder meist eben nicht definiert hat
      Es gibt Ausnahmen. Wenn ich das gesamte Modell selbst definiere und die Daten nicht aus der sogenannten realen Welt stammen, dann ergeben natürliche Schlüssel mehr Sinn. Aber beim Entwurf eines Schemas für reale Daten, die wahrscheinlich nie vollständig normalisiert waren, sind Surrogatschlüssel oft nützlich
    • Monoton steigende Integer-Surrogatschlüssel haben ziemlich unmittelbaren praktischen Nutzen
      Jede Zeile lässt sich als Integer referenzieren, was den Zugriff stark vereinfacht, und sie sind für Menschen leicht zu merken und in Abfragen zu verwenden
      Wenn sie monoton ansteigen, enthalten sie an sich auch Information. Das ist zwar redundante Information, aber es stimmt
      Auch die Zugriffsgeschwindigkeit ist optimiert. Für Indizierung mit B-Bäumen, Bitmaps usw. ist das nahezu der Idealfall
      Ich glaube, dass Leute UUIDs meist aus Verwirrung verwenden. Üblicherweise lautet die Logik, dass man Schlüssel verschleiern und unvorhersehbar machen will, aber warum man meint, dieses Ziel nicht mit einem separaten Bezeichner, sondern gleich mit dem Primärschlüssel erzwingen zu müssen, habe ich aufgegeben zu verstehen
    • Der Ausdruck „Duplikate vermeiden“ kommt im Blogpost nicht vor. Tatsächlich sagt der Artikel überhaupt nicht, warum UUIDs verwendet werden

  • UUID Version 7 hat vorne einen 48-Bit-Zeitstempel und ist deshalb nicht auf diese Weise zufällig verteilt. Dadurch sollten auch übermäßiges Paging und Rebalancing reduziert werden

    • Stimmt. Im Artikel geht es um UUID7

  • Verwenden Leute UUIDs wirklich als Primärschlüssel? Wenn man UUIDs braucht, was ist dann der Vorteil davon, sie so zu verwenden statt als Sekundärschlüssel?

    • Wegen Skalierung. Wenn man eindeutige IDs mit hoher Geschwindigkeit auf vielen Rechnern und in mehreren Rechenzentren weltweit verteilt erzeugen muss, etwa bei S3-Uploads, will man keine Sperre auf einen einzelnen aufsteigenden Integer legen. Solche Sperren sind für weltweite Synchronisation zu langsam
      GUIDs und UUIDs lösen dieses Problem strukturell
      v1 und v6 kodieren Maschinen-ID und Zeitstempel und sind damit fast wie automatisch inkrementierende Integer mit einem Namensraum pro Maschine
      Viel Verwirrung entsteht dadurch, dass viele annehmen, UUIDs seien zufällig. Das trifft nur auf v4 zu, und die Wahl von v4 hat leider Kosten
      Häufig braucht man ein gewisses Maß an Determinismus, etwa mit v3, v5 oder v7, um Daten aufzubereiten oder Garantien bei Performance und Kollisionen zu bekommen
    • Selbst wenn man zufällige UUIDs oder gleichverteilte Zufallswerte als Sekundärschlüssel verwendet, werden Inserts trotzdem langsamer. Auch wenn es kein Clustered Index ist, gibt es in dem B-Baum dieses Index weiterhin zufällige Inserts