}
Computer & Internet► Datenbanken

Warum Hash-Keys als Primärschlüssel keine gute Wahl sind

Gerne wird im Kontext Datawarehouse propagiert, dass als Primärschlüssel ein Hash-Key, also ein durch Anwendung einer kryptografischen Hash-Funktion auf die Geschäftsschlüssel (Business Keys) (z.B. Kundennummer, Vertragsnummer, Rechnungsnummer) erzeugter Surrogate-Key verwendet werden sollte. Dabei wird in der Regel als Hauptvorteil angefügt, dass dadurch eine komplette Parallelisierung der Beladung des Data-Warehouse möglich werden soll: Bei der Verwendung von Sequences zur Generierung von Surrogate-Keys kann, auch bei abgeschalteter Referentieller-Integrität, die Beladung abhängiger Tabellen (Child-Tables) erst dann durchgeführt werden, wenn alle referenzierten Tabellen (Parent- oder Master-Tables) beladen wurden. Dies liegt daran, das die für die Fremdschlüssel erforderlichen Surrogate erst bei der Beladung der referenzierten Tabellen erzeugt werden und im Ladeprozess für die abhängigen Tabellen in den referenzierten Tabellen (oder anderen Lookup-Tabellen) nachgeschlagen werden müssen. Wenn Hash-Keys verwendet werden können abhängige Tabellen - bei abgeschalteter Referentieller-Integrität - zeitgleich mit den referenzierten Tabellen geladen werden. Dies funktioniert, da in beiden Beladungen der Hash-Key unabhängig voneinander aus den Geschäftsschlüsseln berechnet werden kann, was die Abhängigkeit im Ladeprozess auflöst. In der Regel wird dabei empfohlen eine kryptografische Hash-Funktion wie MD5, SHA-1, SHA-256 oder ähnliches zu verwenden. Es wird dabei auch gerne behauptet, dass der Vorteil der Parallelisierung bei der Beladung etwaige Performance-Nachteile, welche durch die Hash-Keys entstehen mehr als aufwiegen. Das Thema möglicher Hash-Kollisionen wird entweder als zu unwahrscheinlich abgetan oder es wird schlicht gesagt das man halt ein Kollisions-Handling benötige, ohne Details zu nennen wie dies aussehen könnte. Ich habe über die Performance-Nachteile beim Datenlesen nachgedacht und das verhalten von Indizes mit Hash-Keys untersucht. Dabei beschränke ich mich im Folgenden jedoch ausschließlich auf die Anwendung von Hash-Keys in relationalen Datenbanksystemen.

Performance-Nachteile eines Hash-Keys

Der Hash hat zwei Aspekte die Hauptsächlich für mögliche Nachteile bei der Performance verantwortlich sind: Er benötigt mehr Speicher und besitzt eine für Indizes ungünstige Verteilung der Werte beim Einfügen neuer Werte

Speicherplatzbedarf

Der Hash benötigt mehr Speicherplatz in allen Strukturen (Tabellen, Indizes, …) in denen er gespeichert ist. Ein MD5 Hash benötigt 128 Bit (16 Byte), ein SHA-256 benötigt wie der Name andeutet 256-Bit (32 Byte). Ein aus einer Sequence erzeugter Integer benötigt in der Regel 4 oder 8 Bytes, wenn man absolut sicher sein kann das nie mehr als ca. 2 Milliarden Keys in der Tabelle erforderlich sind reichen die 4 Bytes, sonst sollten 8 verwendet werden. Der Hash-Key ist also 2- bis 8-mal so groß wie die Sequence-Werte. Viele Datenbaken können jedoch einen Hash-Key als Primärschlüssel nicht in seiner nativen Form speichern, weshalb er in einen Text gewandelt werden muss. Wenn man hierzu eine einfache hexadezimale Kodierung der Bytes verwendet wird jedes Byte zu zwei Buchstaben kodiert, die Größe verdoppelt sich also: 32 Byte für MD5, 64 Byte für SHA-256. Wenn die etwas effizientere Base64-Kodierung verwendet wird, werden jeweils 3 Bytes in 4 Zeichen kodiert, der Platzbedarf steigt um ca. 33%: MD5 benötigt dann 24 Byte und SHA-256 benötigt 44 Byte. Dadurch benötigt ein Hash-Key gegenüber einer numerischen Sequence je nach Hash-Algorithmus und Kodierung den 2- bis 11-Fachen Speicherplatz. Hierbei habe ich evtl. im DBMS auftretenden Over-Head vernachlässigt. Das ein höherer Platzbedarf sowohl beim Lesen und Schreiben einen Laufzeitnachteil verursacht liegt auf der Hand. Bei kleinen Datenmengen und stark Selektiven Abfragen mag dieser noch nicht auftreten, aber bei Millionen von Sätzen - wie sie typischerweise in einem Datawarehouse auftreten - werden diese insbesondere bei den in DWHs oft ausgeführten nicht selektiven Abfragen (z.B. Aggregate Umfangreicher Daten aus einem Data-Mart-Fakt) durchaus bemerkbar: Bei 15 Millionen Zeilen in einer Tabelle wird alleine die Tabelle je nach Hash mehr als 100MB oder gar mehr als 500MB mehr Speicher benötigen. Wenn man den Primary Key Index mit berücksichtig sind es mehr als 200MB bis über 1GB zusätzlicher Speicherplatzbedarf. Hinzu kommt noch der entsprechend erhöhte Platzbedarf in allen Fremdschlüsseln (Foreign-Keys).

Verteilung der Hash-Werte

Der erhöhte Speicherplatzbedarf eines einzelnen Hash-Wertes gegenüber einem Wert aus einer Sequence ist jedoch nur eine Ursache des Performancenachteils eines Hash-Wertes als Primary-Key. Bei Verwendung in indizierten Spalten von relationalen Datenbanksystemen erzeugt die Verteilung der durch den Hash generierten Werte einen zusätzlichen Performancenachteil. Da Primärschlüssel indiziert sind, gilt dieser Nachteil auch bei der Verwendung als Primärschlüssel: Bei kryptografischen Hash-Funktionen ist die Verteilung der Ergebniswerte so gestaltet, dass schon eine sehr kleine Änderung am Input einen völlig anderen Hash-Wert als Ausgabe erzeugt. Dadurch sollen die Werte möglichst gleichmäßig über den Wertebereich verteilte und möglichst unvorhersehbar sein. Diese Eigenschaft ist beim Einfügen in B-Tree-Indizes - wie sie die meisten relationalen Datenbanken verwenden - eher Nachteilig. Ein B-Tree-Index arbeitet am besten wenn die einzufügenden Werte im mathematisch Sinne streng monoton steigend sind, also kontinuierlich wachsen und keine Werte doppelt vorkommen. Streng monoton fallend, also kontinuierlich kleiner werdend ohne doppelte Werte, ist in der Regel genauso gut. Bei einer guten kryptografischen Hash-Funktion werden die Werte jedoch auch bei streng monoton steigendem Input maximal Verteilt über den Wertebereich erzeugt und somit Chaotisch verteilt im Index eingefügt. Dies hat zur Folge, dass es im Index häufig zu sogenannten Page-Splits kommt, bei denen ein neuer Eintrag auf einer bereits vollen Seite des Index angelegt werden muss, weshalb diese in zwei teilweise gefüllte Seiten aufgeteilt wird. Was nicht nur Zeit kostendes Daten kopieren beim Insert erforderlich macht, sondern auch leere Bereiche im Index entstehen lässt. Diese leeren Bereiche müssen beim Lesen mitgelesen werden obwohl sie keine Daten enthalten, dadurch müssen bei Abfragen die den Index nutzen zusätzlich größere Datenmengen verarbeitet werden.

Messungen

Nach diesen theoretischen Betrachtungen nun zu den praktischen Messungen. Zum Messen habe ich 5 Surrogate-Keys im Vergleich gemessen:

  • Numerische-Sequence 4-Byte Integer erzeugt aus einer aufsteigenden Sequence
  • Hash-Key Base64 Der Wert aus der Numerischen-Sequence gehashed und Base64 kodiert. (Länge 24 Zeichen)
  • 24 Zeichen Alpha-Numerische-Folge Eine Alpha-Numerische aufsteigende Folge mit 24 Zeichen länge als Vergleich wie sich ein Key mit gleicher Länge wie der Base64 kodierte Hash verhält.
  • Hash-Key Hex-Kodiert Der Wert aus der Numerischen-Sequence gehashed und Hexadezimal kodiert. (Länge 32 Zeichen)
  • 32 Zeichen Alpha-Numerische-Folge Eine Alpha-Numerische aufsteigende Folge mit 32 Zeichen länge als Vergleich wie sich ein Key mit gleicher Länge wie der Hexadezimal kodierte Hash verhält.

Mit allen fünfen habe ich 1 Million Datensätze in eine Heap-Tabelle geschrieben. Beim Schreiben war auf der Tabelle jeweils ein Index der nur die eine Spalte mit dem nach dem entsprechenden Verfahren erzeugten Surrogat enthielt aktiv. Für diesen Index habe ich nach jedem Datensatz protokolliert wie groß der Index (in 8k Pages) ist und wie viele Zeilen je Page im Index durchschnittlich gespeichert sind. Nach 50.000 Zeilen und nach 350.000 Zeilen wurde der Index neu aufgebaut. Zeilen je Index-Seite Zeilen je Index-Seite Es ist dabei auffällig, das sowohl der Index auf der Numerischen Sequence, als auch die Indizes auf den Alpha-Numerischen-Folgen zügig auf eine gewisse Zahl Zeilen je Page anwachsen und dann fast kontinuierlich auf dieser Zahl bleiben. Die Indizes auf den Hashes hingegen zeigen eine Wellenartige Zeilenzahl je Page. Dieses Wellenmuster ist ein Zeichen für die stattfindenden Page-Splits: Da die Hashes gleichmäßig im Werteraum verteilt sind werden die Index-Seiten gleichmäßig gefüllt (Aufwärtsbewegung der Kurve). Anschließend werden (fast) alle Seiten mit nur wenigen aufeinanderfolgenden Inserts gesplitted (Abwärtsbewegung der Kurve). Nach dem Index-Rebuild sind alle Seiten so voll, dass sie keine Datensätze mehr aufnehmen können, weshalb die nächsten eingefügten Sätze fast alle einen Page-Split auslösen. Dadurch ist in Folge eines Rebuilds nach nur wenig mehr neueingefügten Sätzen als der Index Leaf-Pages besitzt die Situation schlimmer als vor dem Rebuild. Die folgende Darstellung zeigt die Entwicklung der Seitenzahl die die jeweiligen Indizes benötigen: Indexgröße in 8k-Seiten Indexgröße in 8k-Seiten Während Seitenzahl und damit der Speicherbedarf der Indizes auf der numerischen Sequence und den Alpha-Numerischen-Folgen linear steigen, weisen die Indizes auf den Hashes erneut die Wellenform der ungleichmäßigen Seitenallokation auf. Die Alpha-Numerischen-Indizes steigen schneller als die auf der numerischen Sequence, da die Werte eine höhere Datenbreite aufweisen. Die Indizes auf den Hashes benötigen durchschnittlich wesentlich mehr Speicher als die auf gleichbreiten Alpha-Numerischen-Folgen. An den Stellen an denen auf allen Seiten im Index Platz frei ist, welcher für die neuen Sätze genutzt wird, entstehen Plateaus in der Speichernutzung der Indizes auf den Hash-Spalten. Da hier die neuen Sätze in den vorhandenen Seiten landen und diese auffüllen was die Zeilenzahl je Seite steigen lässt (Vgl. voriges Diagram). Bei jeder Veränderung der Anzahl der Pages im Index habe ich zusätzlich ermittelt wie stark der Index fragmentiert ist: Index-Fragmentierung Index-Fragmentierung Wie man sieht, ist die Fragmentierung der Indizes auf den Hash-Keys wesentlich stärker als die der Indizes auf den monoton steigenden Werten. Während die Fragmentierung bei den monoton steigenden Spalten nach einer kurzen Weile unter 1% fällt steigt die der Indizes auf den Hash-Werten schnell auf nahezu 100% an. Auch dies liegt an dem durch die Verteilung der Werte neueingefügter Sätzen entstehenden Page-Splits. Auch hinsichtlich der Fragmentierung hilft ein Index-Rebuild nur sehr kurzfristig. Eine geringe Fragmentierung bedeutet hierbei, dass das Leaf-Level des Index in wenigen großen Fragmenten von sequentiell aufeinanderfolgenden Pages vorliegt. Eine hohe Fragmentierung heißt das es sehr viele Fragmente gibt die nur wenige oder gar nur eine Seite umfassen. Dies ist vor allem bei Index-Range-Scans oder Index-Full-Scans unter Einsatz klassischer Magnetspeicher ein Nachteil: Diese können zwar gut sequentiell lesen brauchen jedoch lange um den Lesekopf auf eine neue Position zu bringen. Bei einer hohen Fragmentierung können jeweils nur wenige zusammenhängende Blöcke gelesen werden, bevor der Kopf zur Position des nächsten Fragments springen muss. Beim Einsatz von modernen Solid-State-Speichern oder eines SANs ist dies weniger relevant, da hier in der Regel die Suchzeiten wesentlich kürzer sind und wahlfreier Zugriff wenn überhaupt nur unbedeutend langsamer ist als sequentieller Zugriff.

Fazit

Kryptografische Hash-Keys können einen spürbaren Performance-Nachteil beim Abfragen von Daten erzeugen, was durchaus die Verwendung einer anderen Alternative zur Generierung von Surrogate-Keys nahelegt.