Multiversion Indexing in Database Systems
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu |
Master's thesis
Authors
Date
2021-10-19
Department
Major/Subject
Signal, Speech and Language Processing
Mcode
ELEC3031
Degree programme
CCIS - Master’s Programme in Computer, Communication and Information Sciences (TS2013)
Language
en
Pages
55+2
Series
Abstract
Modern database managements systems need to answer long queries while processing incoming updates at the same time. Furthermore, analytic queries often need to read previous versions of the same data item. A multiversion database solves these problems by creating a new read-only snapshot of the database every time the data is updated. This way read queries can work on isolated snapshots without blocking new updates. However, when the saved history becomes long, performance issues arise. One option to solve these issues is to use a multiversion index for retrieving data efficiently from an old version. This thesis implements software for a recent multiversion index data structure called transaction-time versioned B-tree (TVB-tree). The TVB-tree is based on an earlier data structure, multiversion B-tree (MVB-tree). The MVB-tree creates a new version after every action. The TVB-tree extends the MVB-tree and enables transactions to contain multiple actions. Although insert and delete actions in the TVB-tree are performed similar to the MVB-tree, the status of the modifications is uncommitted until the associated transaction commits. To implement isolation, each transaction should see a committed snapshot of the database, as it was in the beginning of the transaction, regardless of uncommitted changes made by other transactions. To enable this, the TVB-tree maintains access to the previously committed values of the entries and takes care of the visibility of the deleted and uncommitted entries in the tree. The TVB-tree is implemented in two different ways: one maintaining the deleted and uncommitted entries in an auxiliary tree and one marking the deleted and uncommitted entries in the main database tree. Additionally, a version chain-based multiversion data structure is implemented for comparison. The data structure implementations are compared with each other in experimental tests. The experiments used workloads that tested read performance to old versions, read performance when a large percentage of data entries has been deleted, and overall transactional processing extension overhead compared to plain MVB-tree. The results of the experimental tests show that the TVB-tree performs well in situations where database keys are being deleted, compared to a version chain-based approach. The performance of the TVB-tree is independent of the version to be read, whereas the performance of the version chain-based implementation degrades with the age of the version. When reading the current version, the performance of the TVB-tree increases when keys are being deleted progressively and the size of the current version shrinks. This is a significant improvement upon the version chain-based methods, in which the complexity increases as the number of actions grows be they insertions, updates, or deletions.Modernit tietokantajärjestelmät vastaavat pitkiin kyselyihin ja samalla prosessoivat tietokantaan tulevia uusia muutoksia. Lisäksi analyyttiset kyselyt lukevat usein tietueiden vanhoja versioita. Moniversiotietokannassa nämä haasteet on ratkaistu luomalla uusia vain luku -tyyppisiä tilannevedoksia aina, kun tietueita päivitetään. Lukukyselyt voivat näin ollen työskennellä eristetyssä tilannevedoksessa siten, että uusia päivityksiä ei estetä. Mutta kun tallennettu historia kasvaa, alenee myös järjestelmän suorituskyky. Eräs vaihtoehto tämän ongelman ratkaisuksi on moniversiohakemisto, jossa vanhojen versioiden hakeminen on tehokasta. Tässä opinnäytetyössä tehdään ohjelmisto, jossa toteutetaan hiljattain keksitty tietorakenne: transaktioiden sitoutumisaikoina versioitu B-puu (engl. transaction-time versioned B-tree), eli TVB-puu. TVB-puu perustuu aikaisemmin julkaistuun tietorakenteeseen nimeltä multiversion B-tree, eli MVB-puu. MVB-puussa uusi versio syntyy jokaisen operaation jälkeen. TVB-puu laajentaa MVB-puuta siten, että useamman operaation pituiset transaktiot ovat mahdollisia. Vaikka lisäys- ja poisto-operaatiot TVB-puussa suoritetaan samalla tavalla kuin MVB-puussa, muutokset ovat sitoutumattomia, kunnes operaatiot tehnyt transaktio sitoutuu. Eristyvyyden toteuttamiseksi jokainen transaktio näkee tietokannan sitoutuneen tilan sellaisena kuin se oli transaktion alkaessa, huolimatta mahdollisista sitoutumattomista muutoksista tietokannassa. Jotta tämä olisi mahdollista, TVB-puu pitää kirjaa tietueiden edellisestä sitoutuneesta arvosta, ja pitää huolen, että poistetut mutta sitoutumattomat tietueet näkyvät versioissa. TVB-puu toteutetaan tässä työssä kahdella eri tavalla: toisessa poistetut mutta sitoutumattomat tietueet tallennetaan aputietorakenteeseen, ja toisessa poistetut mutta sitoutumattomat tietueet merkitään erikseen varsinaiseen TVB-puuhun. Näiden lisäksi toteutetaan versiolistoihin perustuva moniversiotietorakenne vertailua varten. Tietorakenteiden toteutuksia verrataan keskenään kokeilla. Kokeissa käytetään työkuormia, jotka testaavat vanhojen versioiden lukemisen tehokkuutta, poistojen merkittävän määrän vaikutusta lukemisen tehokkuuteen ja transaktioiden hallinnan lisäämisen vaikutusta tehokkuuteen verrattuna pelkkään MVB-puuhun. Kokeiden tulokset osoittavat, että TVB-puu suoriutuu hyvin tilanteissa, joissa tietokannan avaimia poistetaan verrattuna versiolistaan perustuvaan ratkaisuun. TVB-puun suorituskyky ei riipu luettavasta versiosta, kun taas versiolistatoteutuksen suorituskyky laskee version iän mukaan. Kun luetaan nykyversiota, TVB-puun suorituskyky kasvaa, kun avaimia poistetaan progressiivisesti ja nykyversion koko pienenee. Tämä on huomattava parannus verrattuna versiolistoihin perustuvaan menetelmään, jossa kompleksisuus kasvaa operaatioiden lukumäärän mukaan, olivat ne sitten lisäyksiä, päivityksiä tai poistoja.Description
Supervisor
Pollari-Malmi, KerttuThesis advisor
Soisalon-Soininen, EljasEl-Mahgary, Sami
Keywords
database, multiversion, index, transaction processing