Eine NoSQL-Datenbank für numerische Daten

Peter J. Holzer
WSR
hjp@wsr.ac.at

Geschichte: 1973

Computer statt „Leintücher“
WIFO und IHS gründen ein gemeinsames Rechenzentrum
ZeitReihenProzessor, später WIFO-ZeitReihenProzessor
Univac 1106 bzw. 1100/80
Proprietäres hierarchisches Datenbanksystem: FSM 8
FORTRAN

Geschichte: 1992

HP-9000 (PA-RISC), HP/UX
Relationales Datenbanksystem: Oracle
(außer UNO-Daten)
immer noch FORTRAN
Frontend VisualData in C++
Web-Frontend in Perl

Jetztzeit: 2011

alles neu
Zeitreihen sind nicht alles
Z.B. Paneldaten
statt kryptischer Labels (PV8IGS, 122"M134"J)
und hierarchischer Kataloge
Multidimensionale Würfel
Flexible Taxonomien (hierarchisch, Tags, Überschneidungen, ...)
Dokumentation der Daten
wartbar für die nächsten 19 Jahre (mindestens)

Ein Schritt zurück: FIW (2007)

Projekt des BMWFJ: Forschungsplattform internationale Wirtschaft
Forschungsinstitute, Unis, Ministerien, Kammern, OeNB, ...
Forschung & Beratung
Konferenzen, Publikationen
und dafür braucht man Daten
die haben wir
aber kein zeitgemäßes Tool
also: Prototyp für WZRP-Nachfolger

Datenmodell - naiv

Value	Reporter	Partner	NACE	Flow	Unit	Beschäftigungsverhältnis	Geschlecht	Source	Period	. . .	. . .	. . .	. . .	. . .	. . .
2391	Wien		21		Personen	Unselbständig	weiblich	HSV	2008M01	. . .	. . .	. . .	. . .	. . .	. . .
2418	Wien		21		Personen	Unselbständig	weiblich	HSV	2008M02	. . .	. . .	. . .	. . .	. . .	. . .
2419	Wien		21		Personen	Unselbständig	weiblich	HSV	2008M03	. . .	. . .	. . .	. . .	. . .	. . .
873538.93	Austria	Germany	21	Export	1000 €			COMEXT	1995	. . .	. . .	. . .	. . .	. . .	. . .
788461.86	Austria	Germany	21	Export	1000 €			COMEXT	1996	. . .	. . .	. . .	. . .	. . .	. . .
745836.8	Austria	Germany	21	Export	1000 €			COMEXT	1997	. . .	. . .	. . .	. . .	. . .	. . .
697264.7	Austria	Germany	21	Import	1000 €			COMEXT	1995	. . .	. . .	. . .	. . .	. . .	. . .
631038.2	Austria	Germany	21	Import	1000 €			COMEXT	1996	. . .	. . .	. . .	. . .	. . .	. . .
670684.75	Austria	Germany	21	Import	1000 €			COMEXT	1997	. . .	. . .	. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .

Datenmodell (Directed Graph)

Datenmodell

Datapoints
Datasets
Annotations

Umsetzung

Relationale Datenbank
Oracle
(eh klar)
Aber DB nur für Storage
und Logik in eigenem Layer

Architektur

Datenmodell

Ja, aber

Eine Tabelle mit 8 Milliarden Rows
macht keinen Spaß
der Kampf gegen den Cost Based Pessimizer auch nicht
Workarounds:
- Denormalisieren: "Fact tables" mit Bitmap Indizes (schnell aber unflexibel, Enterprise Feature)
- Materialized Views
- Selbstgebaute Bitmap-Indizes (Judy FTW!)
Externe Caches:
- Memcached
- Katalog im Filesystem gecachet
nicht so interaktiv wie wir es gerne hätten
und außerdem nicht billig

PostgreSQL

1:1 Portierung von Oracle (fast) trivial
Arrays und GIN Indexes
genau was wir brauchen
(theoretisch)
Performance leider nicht gut
und vor allem unvorhersagbar

NoSQL

HDF5, Cassandra, Redis, Tokyocabinet, CouchDB, ...
es gibt viele
generell für Dokumente gedacht
relativ hoher Overhead pro Record
tw. Skalierungsprobleme
tw. ~~schlechte~~für mich unverständliche Doku

NIH

N I H

Not Invented Here

Anforderungen

Der größte Teil der Daten soll im RAM gehalten werden.
On-Disk-Datenstrukturen sollen möglichst unverändert ins RAM gelesen werden können (kurze Startup-Zeit, Memory-Mapping).
Effiziente Suchmethoden für Datasets und Datenpunkte (generell sollte keine Query länger als ein paar Sekunden dauern).
Queries sollen parallelisierbar sein.
Falls die Daten nicht vollständig ins RAM passen, sollte die Datenbank bei graduell schlechterer Performance trotzdem funktionieren.
On-Disk-Datenstrukturen sollen robust sein.
History
Online-Backup sollte möglich sein.
Die Datenbank sollte auf mehrere Server verteilbar sein (Replikation und/oder Sharding).
Transaktionen sind nicht notwendig.
Foreign Keys und andere Konsistenzchecks sind nicht notwendig
As simple as possible, but not simpler!

Queries

Datenpunkte: Lange boolsche Ausdrücke: ((A1 | A2 | A3) & (B1 | B2) & (C1 | C2 | C3 | C4))
Alle Datasets, in denen eine Menge von Datenpunkten enthalten ist
Suche nach Datasets (Path, Description)
Suche nach Annotations (Fulltext)
Updates

Architektur

Simple Directory/File-Struktur
- Ein Directory pro Datentyp (data, dataset, annotation)
- Simples Mapping Primary Key (Id) → Filename
- Journal-Struktur: Änderungen nur am Ende des Files
- Indizes als Judy-Arrays (vorläufig)
Server-Prozess
- Simples TCP-basiertes Protokoll (ähnlich IMAP)
- Multithreaded, non-forking
- in C

Datentypen

Primitive Datentypen

varuint	base-128 little endian
varsint	base-128 little endian (zigzag encoded)
all ids	varuint
double	64 bit binary FP
scaled_int	1×10^-8 .. 99 999 999×10⁷
text_string	varuint-Length + UTF-8
byte_string	varuint-Length + bytes
time (days)	varsint
period (days)	start (varsint), length (varuint)
time (seconds)	varsint
period (seconds)	start (varsint), length (varuint)
...	...

Data

Filename

⌊ datapoint_id / CHUNK_SIZE ⌋ + ".dp"

Syntax

Data_File       ::= DataPointRecord*

DataPointRecord ::= DataPointMagic Length DataPointId
                    ChangeRecord
                    ValueRecord? CoordRecord*

ChangeRecord    ::= UserId Timestamp

ValueRecord     ::= DOUBLE_VALUE Double
                  | SCALEDINT_VALUE ScaledInt
		  | STRING_VALUE String
		  | TIME_T_VALUE time_t32LE
		  | TIME_T_PERIOD_VALUE time_t32LE time_t32LE

CoordRecord    ::= DATASET_COORD DataSetId
                 | DOUBLE_COORD DataSetId Double
		 | SCALEDINT_COORD DataSetId ScaledInt
		 | STRING_COORD DataSetId String
		 | TIME_T_COORD DataSetId time_t32LE
		 | TIME_T_PERIOD_COORD DataSetId time_t32LE time_t32LE
		 | ANNOTATION_COORD AnnotationId

DataSet

Metadaten

Filename

dataset_id + ".meta"

Syntax

DataSetMetaFile     ::= DataSetChangeRecord*

DataSetChangeRecord ::= DataSetChangeMagic Length ChangeRecord 
                        (
			  NAME String
			  DESCRIPTION LanguageTag String
			  DOWNLINK CoordType CoordRecord
			  UPLINK CoordType CoordRecord
			  ACE AccessControlEntry
			  ANNOTATION AnnotationId
			)*

DataSetChangeMagic  ::= OVERWRITE | ADD | DELETE

Index

Filename: dataset_id + ".jb"
Syntax: Serialisierte Judy-Bitmap, erster Index absolut, alle weiteren relativ. Alle Werte varuint-kodiert.

Annotation

Metadaten

Filename

annotation_id + ".meta"

Syntax

AnnotationMetaFile     ::= AnnotationChangeRecord*

AnnotationChangeRecord ::= AnnotationChangeMagic Length ChangeRecord 
                        (
			  TITLE String |
			  LANGUAGE LanguageTag |
			  MIMETYPE CoordType CoordRecord |
			  URL ByteString |
			  CONTENT ByteString |
			  ACE AccessControlEntry
			)*

AnnotationChangeMagic  ::= OVERWRITE | ADD | DELETE

Content

Filename: SHA-256 Summe (hex) des Inhalts, Im Meta-File als relativer file:-URL gespeichert.
Inhalt: Der Inhalt der Annotation :-). Wird nur für lange Annotations verwendet, kurze können direkt im Meta-File gespeichert werden.

Status

Proof of Concept Code existiert
- Dataset-Info
- (Einfache) Data Queries
- (Einfache) Data Queries mit Dimensionen
Gesamter Datenbestand FIW importiert (ca. 100 GB vs. > 500 GB in Oracle bzw. 800(?) GB in Postgres)
Erste Performance-Tests sind vielversprechend
Offen

Startup langsam.
- Dataset-Metadaten zusammenfassen?
- Indizes parallel einlesen?
- übergeordnete Indizes? (Dimensionen, Hierarchien)
- anderes Indexformat?
Updates!
Annotations
Optimizer

Fragen

?