[Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Hier könnt ihr euch selbst, eure Homepage, euren Entwicklerstammtisch, Termine oder eure Projekte vorstellen.
Forumsregeln
Bitte Präfixe benutzen. Das Präfix "[Projekt]" bewirkt die Aufnahme von Bildern aus den Beiträgen des Themenerstellers in den Showroom. Alle Bilder aus dem Thema Showroom erscheinen ebenfalls im Showroom auf der Frontpage. Es werden nur Bilder berücksichtigt, die entweder mit dem attachement- oder dem img-BBCode im Beitrag angezeigt werden.

Die Bildersammelfunktion muss manuell ausgeführt werden, die URL dazu und weitere Details zum Showroom sind hier zu finden.

This forum is primarily intended for German-language video game developers. Please don't post promotional information targeted at end users.
Antworten
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

[Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

Hey Leute,

ich stelle heute mal ein etwas ungewöhnliches Projekt vor: eine In-Memory-Datenbank (oder erst mal: Storage Engine) mit String- und Integer-Kompression, die später mal ein vollwertiger Nachbau eienr nicht näher benannten In-Memory-Datenbank eines ERP-Herstellers werden soll.

Kurz zum Abriss: Die DB ist besonders gut für analytische Queries geeignet, da man in einer spaltenbasierten Datenbank viel schneller so etwas wie Summen zusammenrechnen kann.

Dazu blogge ich auch auf launix.de. Der erste Blogbeitrag ist hier zu bestaunen:

https://launix.de/launix/on-designing-a ... in-golang/
https://launix.de/launix/how-to-balance ... workflows/

Bild
Zuletzt geändert von antisteo am 20.01.2023, 20:17, insgesamt 2-mal geändert.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: [Projekt] cpdb (OpenSource HANA-Nachbau)

Beitrag von NytroX »

Generell sehr interessant.
Bedarf an einer guten Storage-Lösung besteht auf jeden Fall in der Welt.

Spaltenbasierte Datenbanken sind gar nicht mal so gut; es ist quasi das ECS der Datenbanken :-)
Kann Vorteilhaft sein, wenn es deinem Usecase entspricht, aber man kommt sehr schnell an die Grenzen (z.B. wenn du große Tabellen filtern willst).

Spannend wären auf jeden Fall die TradeOffs, die du machen willst.
(d.h. sind die Daten bei einem Crash/Neustart weg, oder gibt es ein Backing-Store, und wie kommen die Daten performant da hin, usw. :-)

Mach am besten relativ früh Performance-Tests und vergleiche sie mit bestehenden DBs (z.B. einfach MariaDB, wenn >6GB Daten drin sind).

Hast du Erfahrung mit DB-Entwicklung?
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource)

Beitrag von antisteo »

Hallo NytroX,

ich habe selbst in den Forschungsteams rund um die Datenbank-Forschung gearbeitet und deshalb auch Erfahrung in der DB-Entwicklung.

Große Tabellen filtern geht bei Columnar Storages sogar ziemlich gut, da du im Filter-State nur die Spalten laden musst, nach denen auch gefiltert wird.

Allein die Kompressionsmöglichkeiten (Hey! Die Datenbank nimmt nur 50% des Platzes gegenüber der InnoDB ein. Damit bist du allein schon beim Full Scan um Größenordnungen schneller fertig, weil du weniger Speicherseiten einlesen musst)
Zuletzt geändert von antisteo am 20.01.2023, 20:19, insgesamt 2-mal geändert.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource)

Beitrag von antisteo »

Zweiter Blogbeitrag - diesmal über die Wahl von Scheme als Programmiersprache für die Query Plans in unserer In-Memory-Engine

https://launix.de/launix/designing-a-pr ... lgorithms/
Zuletzt geändert von antisteo am 20.01.2023, 20:18, insgesamt 1-mal geändert.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource)

Beitrag von antisteo »

Ein kleiner Beitrag, wie die DB eigentlich OLAP und OLTP-Workloads in einer einzigen Engine performant unterbringt:

https://launix.de/launix/how-to-balance ... workflows/
Zuletzt geändert von antisteo am 20.01.2023, 20:18, insgesamt 1-mal geändert.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource)

Beitrag von antisteo »

Und jetzt ein kleiner Benchmark hinterher:

https://launix.de/launix/how-in-memory- ... rformance/
Zuletzt geändert von antisteo am 20.01.2023, 20:19, insgesamt 1-mal geändert.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource)

Beitrag von antisteo »

Im nächsten Beitrag gehts um den Aufbau von Indizes:

https://launix.de/launix/memory-efficie ... -storages/

Insgesamt habe ich eine Query-Zeit von 50µs zum Finden eines Strings in einer 10K-Einträge-Liste geschafft
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

In diesem Beitrag habe ich noch mal 40% des RAM-Verbrauchs eingespart, indem ich NULL-Werte mit weniger als 1 bit komprimiere:

https://launix.de/launix/on-compressing ... -storages/
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] memcp (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

So, der SQL Parser ist Tail Recursive und nach etwas Eingewöhnung ziemlich straigt-forward zu schreiben. Inzwischen kann ich die ersten SQL Queries nach scheme übersetzen und somit per (eval) auswerten:

https://launix.de/launix/memcp-first-sq ... -executed/
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

Sequenzkompression brint einfach mal so 99% RAM-Ersparnis

https://launix.de/launix/sequence-compr ... tal-of-13/
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

Man kann 1 Bit in weniger Platz als 1 Bit abspeichern.

https://launix.de/launix/storing-a-bit- ... n-one-bit/

Einen ähnlichen Algorithmus nutzt auch ZIP/Deflate. Ich habe ihn mal aufgeschlüsselt inkl. Code-Beispielen. In einem 64-bit-Chunk bekomme ich ca. 200 Bits untergebracht gegeben eine unbalancierte Wahrscheinlichkeitsverteilung.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2348
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von Jonathan »

Der Algorithmus sieht ganz interessant aus (ich kannte ihn glaube ich noch nicht und habe ihn jetzt auch eher überflogen), aber die Überschrift finde ich ein wenig, naja, albern. Zunächst einmal speicherst du ja nicht 1 Bit mit weniger als 1 Bit. Du speicherst eine große Anzahl an Bits in einer kleineren Anzahl an Bits. Und warum das irgendwie erstaunlich sein sollte erschließt sich mir überhaupt nicht, das ist halt die Definition von "Kompression" und das hat nun wirklich jeder schon mal gehört. In gewisser Weise wäre "Yet another compression algorithm" die bessere Überschrift gewesen. Das "Yet another" deshalb, weil im Artikel ja weder erwähnt wird, für was für Daten sich das besonders gut eignet, noch der Algorithmus mit irgendwelchen anderen verglichen wird.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
Krishty
Establishment
Beiträge: 8227
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von Krishty »

Nutzt ZIP/Deflate nicht Huffmann Trees, während deins näher an Arithmetic Coding ist?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

Krishty hat geschrieben: 16.03.2023, 15:21 Nutzt ZIP/Deflate nicht Huffmann Trees, während deins näher an Arithmetic Coding ist?
Du hast recht. Die Kompressionsrate von Arithmetic Coding kommt ja sogar noch näher ans Optimum heran als der Huffman Tree, der nur dann effizient ist, wenn die Wahrscheinlichkeit exakt einer 0,5-er-Potenz entspricht.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

Es ist raus - Das Projekt steht jetzt auf Github und ab Montag gehen wir damit auf die Hannover-Messe



https://github.com/launix-de/memcp
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] memcp (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

Die erste Anwendung existiert auf der Basis von MemCP:



Die Github Page ist jetzt auch gefinisht:

https://github.com/launix-de/memcp
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
antisteo
Establishment
Beiträge: 852
Registriert: 15.10.2010, 09:26
Wohnort: Dresdem

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von antisteo »

Die MemCP hat's in die Weihnachtsvorlesung der Hochschule geschafft

http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
NytroX
Establishment
Beiträge: 358
Registriert: 03.10.2003, 12:47

Re: [Projekt] cpdb (OpenSource In-Memory Spaltenbasierte Datenbank)

Beitrag von NytroX »

Das traurige ist, finde ich, dass man immer denkt, dass sich die großen Datenbanken um sowas wie Komprimierung und Speichereffizienz Gedanken machen. Ich meine, was ist denn die Aufgabe einer Datenbank? Daten effizient zu speichern!
Und dann stellt man fest, dass alle klassischen Datenbanken einfach kacke sind.
Indizes sind vollständig im RAM oder gar nicht, es gibt keine ausgefeilten Algorithmen was wo wie gespeichert wird und warum, und Komprimierung funktioniert vorne und hinten nicht gescheit und macht alles nur langsamer.
Ganz zu schweigen davon, dass man immer den doppelten Platz der größten Tabelle (oder Tablespace) braucht, weil man sonst nicht defragmentieren/vacuumieren (oder wie sie es auch immer nennen) kann. Das kann quasi jedes Dateisystem besser.
Und wehe man will das aus unerfindlichen Gründen benötigte manuelle Housekeeping auf der Live-Datenbank machen, dann geht alles den Bach runter.
Und daran hat sich in den letzten 50 Jahren nichts geändert.
Antworten