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

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
Selbstgebaute Bitmap-Indizes (Judy FTW!)
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

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 (HTTP based? telnet-like?)
- Multithreaded, non-forking
- in C

Exkurs: Fork

Datentypen

Primitive Datentypen

datapoint_id	64 bit int
dataset_id	32 bit int
annotation_id	32 bit int
user/group_id	32 bit int
double	64 bit binary FP
scaled_int	1×10^-8 .. 99 999 999×10⁷
text_string	BER-Length + UTF-8
byte_string	BER-Length + bytes
time_t	32 bit
period	time_t (incl.) + time_t (excl)
...	...

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 BER-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.

TODO

And it is finished
It only has to be written
Offen

Protokoll
einige Datentypen
Indizes
- mmappable?
- können riesige Zwischenergebnisse verhindert werden?

Fragen

?