Extending a data management system with multiversion indexing, branching, and snapshots

Loading...
Thumbnail Image

URL

Journal Title

Journal ISSN

Volume Title

Perustieteiden korkeakoulu | Master's thesis

Date

2024-06-17

Department

Major/Subject

Machine Learning, Data Science and Artificial Intelligence

Mcode

SCI3044

Degree programme

Master’s Programme in Computer, Communication and Information Sciences

Language

en

Pages

72 + 1

Series

Abstract

Software developers have long been accustomed to using version control in their projects for managing files, but similar solutions for databases are not as well established. This thesis extends a pre-existing proprietary data management system, called Lumo, with snapshots and branches for version control purposes. Additionally, a suitable multiversion index structure is needed to index data in each snapshot (version), and certain key performance criteria are recognized for the structure to adhere to. The criteria demand efficient loading, releasing and cloning of snapshots, as well as efficient access to any data in any snapshot. Furthermore, the amount of shared data between snapshots should be maximized to reduce memory consumption. In this thesis the pre-existing Hash Array Mapped Trie (HAMT) is identified to be a suitable base data structure for the multiversion index. The Multiversion Hash Array Mapped Trie (MHAMT) is introduced as an extension to the HAMT, specifically implemented for multiversion use within Lumo. The MHAMT allows nodes to be shared between several tries, and also adds support for non-unique keys and hash collisions. The MHAMT is shown to satisfy the key performance criteria well. The MHAMT implementation is validated by testing it using real-world data, resulting in a Lumo data model consisting of 769 snapshots, each with their own MHAMT index. The memory consumption of the MHAMTs are analyzed, and it is shown that the MHAMTs consume around 90% less memory compared to the theoretical case where nodes cannot be shared between tries. The trie structures are examined as well, which shows the MHAMTs contain more nodes than necessary. The reason for the unbalanced tries is thought to be the hashing algorithm used by Lumo not being optimized for the test data. The MHAMT implementation introduced in this thesis can still be enhanced. Path compression could be applied to the tries by removing unnecessary one-child nodes, and full nodes could have their bitmaps removed completely. The proposed solution of managing duplicate keys could be improved further, and adding multiversion indexing support for ordered data will also be a priority in future Lumo development.

Mjukvaruutvecklare har sedan länge varit vana med versionskontroll inom sina projekt för att hantera filer, men liknande lösningar för databaser är inte lika väletablerade. Detta diplomarbete kompletterar ett redan existerande proprietärt datahanteringssystem, kallat Lumo, med ögonblicksbilder och förgreningar för versionskontrollsändamål. Dessutom behövs en lämplig multiversionsindexstruktur för att indexera datan i varje ögonblicksbild (version), och några nyckelprestandakriterier identifieras som strukturen bör följa. Kriterierna kräver effektiv laddning, frigivning och kloning av ögonblicksbilder, samt effektiv åtkomst till alla data i alla ögonblicksbilder. Därtill bör mängden delad data mellan ögonblicksbilder maximeras för att reducera minnesförbrukningen. I detta diplomarbete identifieras den existerande datastrukturen Hash Array Mapped Trie (HAMT) som en lämplig basstruktur för multiversionsindexet. Datastrukturen Multiversion Hash Array Mapped Trie (MHAMT) introduceras, som är en utvidgad HAMT specifikt implementerad för multiversionsanvändning inom Lumo. MHAMT tillåter att noder delas mellan flera träd, och lägger även till stöd för icke-unika nyckelvärden och hashkollisioner. MHAMT visar sig tillfredsställa nyckelprestandakriterierna. MHAMT-implementationen valideras genom att testa den med hjälp av verklig data, vilket resulterar i en Lumo-datamodell bestående av 769 ögonblicksbilder, som vardera har sitt egna MHAMT-index. Minnesförbrukningen för MHAMT-träden analyseras och det visas att förbrukningen är cirka 90% mindre jämfört med det teoretiska fallet där noder inte kan delas mellan träden. Trädstrukturerna undersöks också, vilket visar att träden innehåller fler noder än nödvändigt. Anledningen till de obalanserade MHAMT-träden antas vara att hashalgoritmen som används av Lumo inte är optimerad för testdatan. MHAMT-implementationen som introduceras i detta diplomarbete kan fortfarande förbättras. Vägkomprimering kan tillämpas på MHAMT-träden genom att avlägsna onödiga enbarnsnoder, och kompletta noder kan få sina bitmapobjekt helt borttagna. Även den föreslagna lösningen för att hantera nyckeldubbletter kan förbättras ytterligare, och att inkorporera stöd för multiversionsindexering för sorterad data kommer också att vara en prioritet inom den framtida Lumo-utvecklingen.

Description

Supervisor

Pollari-Malsmi, Kerttu

Thesis advisor

Rantanen, Teemu
Nyberg, Kim

Keywords

database, multiversion, index, branch, snapshot, MHAMT

Other note

Citation