QVD-Dateien - was ist drin, Teil 3

Im ersten Artikel über die Struktur der QVD-Datei habe ich die allgemeine Struktur beschrieben und mich eingehend mit Metadaten befasst, und im zweiten Artikel über die Speicherung von Spalten (Zeichen). In diesem Artikel werde ich das Format zum Speichern von Informationen über Zeichenfolgen beschreiben, Pläne und Erfolge zusammenfassen und darüber sprechen.

Denken Sie also daran, dass die QVD-Datei der relationalen Tabelle entspricht. In der QVD-Datei wird die Tabelle in zwei indirekt verbundenen Teilen gespeichert:

Zeichentabellen (mein Begriff) enthalten eindeutige Werte für jede Spalte in der Quelltabelle. Ich habe im zweiten Artikel darüber gesprochen.

Die Zeilentabelle enthält die Zeilen der Quelltabelle, jede Zeile speichert die Indizes der Spalten- (Feld-) Werte der Zeile in der entsprechenden Symboltabelle. Es geht darum, dass dieser Artikel sein wird.

Am Beispiel unserer Platte (denken Sie daran - aus dem ersten Teil)

SET NULLINTERPRET =<sym>; tab1: LOAD * INLINE [ ID, NAME 123.12,"Pete" 124,12/31/2018 -2,"Vasya" 1,"John" <sym>,"None" ]; 

In der Zeilentabelle unserer QVD-Datei entspricht diese Bezeichnung 5 Zeilen - immer eine exakte Übereinstimmung: Wie viele Zeilen befinden sich in der Tabelle, wie viele Zeilen befinden sich in der Zeilentabelle der QVD-Datei.

Eine Zeile in der Zeilentabelle besteht aus nicht negativen Ganzzahlen. Jede dieser Zahlen ist ein Index für die entsprechende Symboltabelle. Auf der logischen Ebene ist alles einfach, es bleibt, die Nuancen zu klären und ein Beispiel zu geben (zerlegen - wie unser Typenschild in QVD dargestellt ist).

Zeilentabellenformat

Die Zeilentabelle besteht aus K * N Bytes, wobei

• K - die Anzahl der Zeilen in der Quelltabelle (der Wert des Metadaten-Tags "NoOfRecords")
• N - Bytelänge der Zeile der Symboltabelle (der Wert des Metadaten-Tags "RecordByteSize")

Die Zeilentabelle beginnt mit dem Versatz "Offset" (Metadaten-Tag) relativ zum Anfang des binären Teils der Datei.

Informationen zur Zeilentabelle (Länge, Zeilengröße, Versatz) werden im allgemeinen Teil der Metadaten gespeichert.

Zeilenformat der Zeilentabelle

Alle Zeilen der Zeilentabelle haben das gleiche Format und sind eine Verkettung von "vorzeichenlosen Zahlen". Die Länge der Zahl reicht minimal aus, um ein bestimmtes Feld darzustellen: Die Länge hängt von der Anzahl der eindeutigen Werte eines bestimmten Feldes ab.

Für Felder mit einem Wert (wie ich bereits geschrieben habe) ist diese Länge Null (dieser Wert ist in jeder Zeile der Quelltabelle gleich und wird in der entsprechenden Symboltabelle gespeichert).

Bei Feldern mit zwei Werten ist diese Länge gleich eins (die möglichen Indexwerte in der Symboltabelle sind 0 und 1) usw.

Da die Gesamtlänge der Zeile der Zeilentabelle ein Vielfaches des Bytes sein sollte, wird die Länge des "letzten Zeichens" an der Bytegrenze ausgerichtet (siehe unten, wenn wir unsere Platte analysieren).

Informationen über das Format jedes Feldes werden in dem Metadatenabschnitt gespeichert, der diesem Feld gewidmet ist (wir werden weiter unten näher darauf eingehen). Die Länge der Bitdarstellung des Feldes wird im Tag "BitWidth" gespeichert.

Speichern von NULL-Werten

Wie speichere ich fehlende Werte? Wenn ich das Thema Warum nicht diskutiere, werde ich folgendermaßen antworten: Nach meinem Verständnis entspricht die folgende Kombination NULL-Werten

• Tag "Bias" des entsprechenden Feldes nimmt den Wert "-2" an (insgesamt bin ich auf zwei mögliche Werte dieses Tags gestoßen - "0" und "-2")
• Der Feldindex für die Zeile, in der dieses Feld NULL ist, ist 0

Dementsprechend werden alle anderen Indizes in der Spalte mit NULL-Werten um 2 erhöht - wir werden in unserem Beispiel etwas niedriger sehen.

Die Reihenfolge der Felder in der Zeile

Die Reihenfolge der Felder in der Zeile der Zeilentabelle entspricht dem Bitversatz des Felds, der im Tag "BitOffset" des Metadatenabschnitts gespeichert ist, der sich auf dieses Feld bezieht.

Lassen Sie uns unser Beispiel analysieren (siehe Metadaten im ersten Teil dieser Reihe).

ID-Feld

• Bitoffset 0 - das Feld ist das "ganz rechts"
• Bitlänge 3 - Das Feld belegt 3 Bits in einer Zeile einer Zeilentabelle
• Die Abweichung ist "-2" - das Feld hat NULL-Werte, alle Indizes werden um 2 erhöht

Feld "NAME"

• Bitversatz 3 - Das Feld befindet sich um 3 Bits links vom ID-Feld
• Bitlänge 5 - Das Feld belegt 5 Bits in der Zeile der Zeilentabelle (ausgerichtet an der Bytegrenze).
• Bias ist "0" - das Feld hat keine NULL-Werte, alle Indizes sind "ehrlich"

Präsentation unseres Typenschildes.

Schauen wir uns die echten "Nullen und Einsen" an - ich werde Fragmente der QVD-Datei als binäre Darstellung "im hexadezimalen Format" (so kompakt) geben.

Erstens der gesamte binäre Teil (der in Pink hervorgehobene Teil, die Metadaten werden abgeschnitten - es tut vielen weh ...)

Kompakt genug, stimme zu. Schauen wir uns das genauer an - direkt nach den Metadaten gibt es Symboltabellen (Metadaten in dieser Datei endeten übrigens mit einem Zeilenvorschub und einem Null-Byte - technisch gesehen geschieht dies, Null-Bytes, nachdem die Metadaten übersprungen werden müssen ...).

Die erste Symboltabelle ist in der folgenden Abbildung hervorgehoben.

Wir sehen:

Der erste eindeutige Wert des ID-Felds ist

• Typ "6" (das erste zugewiesene Byte) ist eine Gleitkommazahl mit einer Zeichenfolge (siehe den zweiten Artikel)
• Nach dem ersten Byte sind 8 der nächsten Bytes eine binär dargestellte Gleitkommazahl
• Nach ihnen folgt die Zeichenfolgendarstellung - sehr praktisch (Sie müssen sich nicht erinnern - was war die Zahl) und endet mit einem Null-Byte

Die verbleibenden drei eindeutigen Werte sind vom Typ 5 (eine Ganzzahl mit einer Zeichenfolge) - die Werte sind "124", "-2" und "1" (entlang der Linien leicht zu erkennen).

In der folgenden Abbildung habe ich die zweite Symboltabelle hervorgehoben (für das Feld "NAME").

Der erste eindeutige Wert des Felds "NAME" ist Typ "4" (das erste zugewiesene Byte) - eine Zeichenfolge, die mit Null endet.

Die anderen vier eindeutigen Werte sind auch die Zeichenfolgen "31.12.2008", "Vaysa", "John" und "Keine".

Jetzt - die Zeilentabelle (in der folgenden Abbildung hervorgehoben)

Wie erwartet - 5 Bytes (5 Zeilen mal 1 Byte).

Die erste Zeile (entspricht Zeile 123.12, "Pete" unserer Platte)

Der Zeichenfolgenwert ist Byte "02" (binär 000000010).

Trennen Sie es (denken Sie an die obige Beschreibung)

• rechts 3 Bits (binär 010, unserer Meinung nach ist es 2) - dies ist ein Index in die Symboltabelle des Feldes "ID"
• wir haben das Feld "ID" enthält NULL, so dass der Index um 2 erhöht wird, d.h. Der resultierende Index ist 0, was dem Zeichen "123.12" entspricht.
• Die nächsten 5 Bits (binär und dezimal 0) sind der Index in der Symboltabelle des Felds "NAME". Sie enthalten kein NULL. Daher ist dies der Index "Pete" in der Symboltabelle.

Zweite Zeile (124.12 / 31/2018) in der Zeilentabelle

Wert - Byte "0B" (binär 00001011)

• rechte 3 Bits (binär 011, unserer Meinung nach 3) - dies ist der Index in der Symboltabelle des Feldes "ID"
• wir haben das Feld "ID" enthält NULL, so dass der Index um 2 erhöht wird, d.h. Der resultierende Index ist 1, was dem Symbol "124" entspricht.
• Die nächsten 5 Bits (binär und dezimal 1) sind der Index in der Symboltabelle des Felds "NAME". Sie enthalten kein NULL. Dies ist also der Index "31.12.2008" in der Symboltabelle.

Nun und so weiter, werfen wir einen kurzen Blick auf die letzte Zeile - dort hatten wir es, "None" (dh NULL und die Zeichenfolge "None"):

Der Wert ist Byte "20" (binär 0010000)

• rechts 3 Bits (binär und dezimal 0) - dies ist der Index in der Symboltabelle des Feldes "ID"
• wir haben das Feld "ID" enthält NULL, so dass der Index um 2 erhöht wird, d.h. Der endgültige Index ist -2, was dem NULL-Wert entspricht.
• Die nächsten 5 Bits (binär 100, dezimal 4) sind der Index in der Symboltabelle des Felds "NAME". Sie enthalten kein NULL. Dies ist also der Index "None" in der Symboltabelle.

WICHTIG Ich kann kein Beispiel finden, das dies bestätigt, aber ich bin auf Dateien gestoßen, die einen endgültigen Index von -1 für NULL-Werte enthielten. Daher betrachte ich in meinen Programmen alle Felder, deren endgültiger Index negativ ist, als NULL.

Längere Zeilen in einer Zeilentabelle

Am Ende der Analyse des QVD-Formats werde ich kurz auf wichtige Nuancen eingehen - lange Zeilen in den Zeilentabellen speichern Felder in der Reihenfolge von rechts nach links, wobei das Feld mit dem Null-Bit-Offset ganz rechts ist (wie oben beschrieben). ABER die Bytereihenfolge ist umgekehrt, d.h. Das erste Byte ist das am weitesten rechts stehende (und enthält das "rechte" Feld - ein Feld mit Null-Bit-Offset), das letzte Byte ist das erste (dh enthält das am meisten "linke" Feld - ein Feld mit maximalem Bit-Offset).

Ein Beispiel sollte gegeben, aber nicht mit Details überladen werden. Schauen wir uns eine solche Bezeichnung an (ich zitiere ein Fragment - um lange Zeilen in der Zeilentabelle zu erhalten, müssen Sie die Anzahl der eindeutigen Werte erhöhen).

 tab2: LOAD * INLINE [ ID, VAL, NAME, PHONE, SINGLE 1, 100001, "Pete1", "1234567890", "single value" 2, 200002, "Pete2", "2234567890", "single value" ... ]; 

Kurzinformationen zu den Feldern (Auspressen von Metadaten):

• ID: Breite 8 Bit, Bitversatz - 0, Bias - 0
• VAL: Breite 5 Bit, Bitversatz - 8, Bias - 0
• NAME: Breite 6 Bit, Bitversatz - 18, Bias - 0
• TELEFON: Breite 5 Bit, Bitversatz - 13, Bias - 0
• SINGLE: Breite 0 Bits (hat einen Wert)

Die Zeilentabelle besteht aus Zeichenfolgen mit einer Länge von jeweils 3 Bytes. In der Zeile der Zeilentabelle werden die Daten zu den Feldern wie folgt logisch zerlegt:

• erste 6 Bits - Feld "NAME"
• nächste 5 Bits - Feld "PHONE"
• dann 5 Bits - Feld "VAL"
• letzte 8 Bits - ID-Feld

Die logische Sequenz wird in umgekehrter Reihenfolge in physikalische Bytes umgewandelt, d.h.

• Das Feld "ID" belegt vollständig das erste Byte (das in der logischen Reihenfolge das letzte ist).
• Das Feld "VAL" belegt die unteren 5 Bits des zweiten Bytes
• Das Feld "PHONE" belegt die oberen 3 Bits des zweiten Bytes und die unteren 2 Bits des dritten Bytes
• Das Feld "NAME" belegt die oberen 6 Bits des dritten Bytes

Schauen wir uns Beispiele an. Hier ist, wie die erste Zeile der Zeilentabelle aussieht (rosa hervorgehoben).

Feldwerte

• ID - binär 00000000, dezimal 0
• VAL - binär 00010, dezimal 2, subtrahiere 2 von der Vorspannung - erhalte 0
• TELEFON - binär 00010, dezimal 2, 2 von Bias subtrahieren - 0 erhalten
• NAME - binär 000000, dezimal 0

Das heißt, die erste Zeile enthält die ersten Zeichen aus den entsprechenden Zeichentabellen.

Im Allgemeinen ist es praktisch, mit dem Parsen ab der ersten Zeile zu beginnen - normalerweise enthält es Nullen als Index (die QVD-Datei wird so erstellt, dass die Werte aus der ersten Zeile zuerst in die Zeichentabelle gelangen).

Schauen wir uns die zweite zu behebende Zeile an

Feldwerte

• ID - binär 00000001, dezimal 1
• VAL - binär 00011, dezimal 3, 2 von Bias subtrahieren - 1 erhalten
• TELEFON - binär 00011, dezimal 3, subtrahieren 2 von Bias - erhalten 1
• NAME - binär 000001, dezimal 1

Das heißt, die zweite Zeile enthält die zweiten Zeichen aus den entsprechenden Zeichentabellen.

Effiziente Formatanalyse

Ich werde ein wenig Erfahrung teilen - wie ich QVD technisch "lese".

Die erste Version wurde in Python geschrieben (ich werde sie veredeln und auf Github setzen).

Die Hauptprobleme wurden schnell klar:

• Symboltabellen können nur "in einer Reihe" gelesen werden (es ist unmöglich, die Symbolnummer N zu lesen, ohne alle vorherigen Zeichen zu lesen).
• echte Dateien passen nicht in den RAM
• der langsamsten Operationen (außer beim Arbeiten mit Dateien) - Bitoperationen (Entpacken einer Zeile einer Zeichenfolgentabelle)
• Die Leistung sinkt stark bei "breiten" QVD-Dateien (wenn viele Spalten vorhanden sind).

Einige dieser Probleme können durch Ändern der Sprache gelöst werden (z. B. von Python auf C). Teil erforderte einige zusätzliche Maßnahmen.

Die derzeitige recht schnelle Implementierung sieht folgendermaßen aus: Die allgemeine Logik ist in Python implementiert, und die kritischsten Vorgänge werden in separaten C-Programmen ausgeführt, die parallel ausgeführt werden.

Kurz

• Symboltabellen werden in Dateien geschrieben, zusätzlich werden Indizes für Textfelder erstellt, wodurch die Symbolnummer N gelesen werden kann
• Arbeiten Sie mit QVD und Dateien mit Symboltabellen, die durch Speicherzuordnungsdateien implementiert sind (also schneller).
• Zunächst werden parallel (mit einer Begrenzung der Anzahl der Prozessoren) Dateien mit Symboltabellen (und Indizes) erstellt.
• dann werden parallel (mit einer ähnlichen Einschränkung) die Zeilen der Zeilentabelle gelesen und CSV-Dateien erstellt (in HDFS)
• Der letzte Schritt besteht darin, diese Dateien in eine ORC-Tabelle zu konvertieren (mit Hive-Tools).
• In C wurde die Erstellung von Dateien mit Symboltabellen und die Erstellung einer CSV-Datei für eine Reihe von Zeilen implementiert

Ich möchte keine Leistungsangaben machen - sie erfordern eine Bindung an die Hardware. Auf qualitativer Ebene stellt sich heraus, dass die QVD-Datei mit etwa der Geschwindigkeit des Kopierens von Daten über das Netzwerk in die ORC-Tabelle kopiert wird. Mit anderen Worten, Daten aus QVD zu entnehmen ist ziemlich realistisch (auf Haushaltsebene).

Ich habe auch die Logik zum Erstellen von QVD-Dateien implementiert - sie funktioniert unter Python recht schnell (anscheinend habe ich noch keine großen Volumes erreicht - es besteht keine Notwendigkeit. Ich werde dorthin gelangen - ich werde sie auf die gleiche Weise wie die "Lese" -Version umschreiben).

Zukunftspläne

Was weiter:

• Ich habe vor, die Python-Version des Codes in Github zu erstellen (mit dieser Version können Sie die QVD-Datei "erkunden" - Metadaten anzeigen, Zeichen und Zeichenfolgen lesen und schreiben. Die Version ist so einfach und offensichtlich langsam wie möglich - ohne Dateien für Zeichentabellen, mit sequentiellem Lesen und Standardbibliotheken zum Arbeiten Bits usw.)
• Ich denke darüber nach, etwas für Pandas zu tun (wie read_qvd ()), es schränkt ein, dass es auf Python langsam sein wird, sowie die Tatsache, dass offensichtlich nicht jeder QVD in den Speicher "passt"
• Ich denke darüber nach, die QVD-Datei zu einer Datenquelle für Spark zu machen - es sollte kein Problem geben, "nicht in den Speicher zu gelangen" (und die Sprache dort - Scala - ist näher an der Hardware).

Anstelle eines Nachwortes

Lange Zeit habe ich mich mit QVD-Dateien beschäftigt und es schien, als sei "dort alles kompliziert". Es stellte sich heraus, dass es schwierig, aber nicht sehr, ein guter Anstoß war Github, den ich im ersten Teil erwähnte (eine Art Katalysator). Dann war es eine Frage der Technologie. Ich und alle bemerken (noch eine Bestätigung) - alles kann in der Programmierung gemacht werden, die Frage ist Zeit und Motivation.

Ich hoffe, ich bin nicht sehr müde von den Details, ich bin bereit, Fragen zu beantworten (in den Kommentaren oder auf andere Weise). Wenn es eine Fortsetzung gibt - werde ich schreiben.