| dc.description.abstract | I 2013 publiserte et team hos Microsoft Research en artikkel om en ny type B-tre, som kalles Bw-tree, er laget for moderne maskinvaresystemer og visste seg til å være langt bedre enn alle andre moderne datastrukturer som ble testet. Men i 2018 hadde en annen gruppe av forskere brukt 2013-papirets beskrivelse av treet for å lage sin egen i-minne versjon, kalt OpenBw-tree. Resultatene var sterkt forskjellig fra hva Microsoft hevdet i 2013.
På grunn av den sterke variasjonen i resultatene hadde Oracle interesse i å teste Bw-treet mot sin egen database. Utgangspunktet for denne oppgaven var å dele OpenBw-treet i en klient og server side. Hovedproblemet var at det var en selvstendig i-minne datastruktur. På grunn av det ble MySQLs lagringsmotor, InnoDB, direkte skrevet til og testet via sin Memcached-plugin. Planen var å kutte lagringsmotorens kostnad så mye som mulig for å forbedre sammenligenbarhet av begge datastrukturene. Men siden OpenBw-treet mangler transaksjonsstøtte, som potensielt har et stort innvirkning på ytelsen, er skaleringsegenskapene til trærne viktigere enn kjøretidene.
Utførte tester ble basert på innsetting, lesing, oppdatering, samt lesing + oppdatering av arbeidsbelastninger på opptil 100 millioner operasjoner ved bruk av tilfeldige og monotone nøkkelfordeler. I tillegg ble InnoDBs B+-tree og OpenBw-tree testet med henholdsvis 64 og 96 samtidige klient-serverforbindelser. Resultatene viser at OpenBw-treet skaleres lineært i alle test tilfeller. Den har også omtrent samme ytelsestider for alle arbeidsbelastningstyper. B+-treet, derimot, skalerer ikke så bra, og har mest problemer med innsetting og oppdatering. Som et resultat av dette varierer ytelsestidene mye mellom arbeidsbelastningstyper og -størrelser og mengden tilkoblinger som brukes.
Denne oppgaven gir en detaljert beskrivelse av Bw-treets kjerneelementer og mekanismer som ble bygd på både forskningspapirets teorideler og OpenBw-treets kode. Selv om Bw-treet gjorde så bra, bør det huskes at kjerne elementer til lagringsmotoren, for eksempel transaksjonsstøtte, logging og vedvarenhet, mangler. Implementasjon av disse vil sikkert redusere ytelsen, men skaleringspotensialet er ganske ekte. Det er tvilsomt hva Oracle ville få ut av ved å implementere et Bw-tree i InnoDB. Tross alt ble indeksen bygget med moderne maskinvare som gjør bruk av CaS-operasjoner i stedet for låser. Dette innebærer at det enten må gjøres betydelige endringer i InnoDB eller det vil være behov for en helt ny lagringsmotor i stedet. | |
| dc.description.abstract | In 2013, a team at Microsoft Research published a paper regarding a new type of B-tree, the Bw-tree, made for modern hardware systems that were supposedly far superior to all other modern data structures tested. However, in 2018, another group of researchers had used the 2013 paper's description of the tree to create their own in-memory version, called the OpenBw-tree. The results differed strongly from what Microsoft was claiming in 2013.
Due to the strong variation in results, Oracle had an interest in testing the Bw-tree against their own database. The starting point for this thesis was to split the OpenBw-tree into a client and server side. The main issue, however, was it being a standalone in-memory data structure. As a result, MySQL's storage engine, InnoDB, was directly written to and tested via its Memcached plugin. The plan was to cut the storage engine's cost as much as possible to improve the comparability of both data structures. However, as the OpenBw-tree lacks transaction support, having a potentially large impact on performance, scaling properties of the trees are more important than execution times.
The tests conducted were based on insert-, read-, update- as well as read + update workloads of up to 100 million operations using random-, and monotone-key distributions. Additionally, InnoDB's B+-tree and the OpenBw-tree were tested with up to 64 and 96 concurrent client-server connections respectively. The results show that the OpenBw-tree scales linearly in all test cases. It also has roughly the same performance times for all workload types. The B+-tree, on the other hand, does not scale as good, having most problems with insert and update operations. As a result, the performance times do differ heavily among the workload types and sizes and amount of connections used.
This thesis provides a detailed description of the Bw-tree's core elements and mechanisms which was built upon both research papers' theory parts as well as the OpenBw-tree's code. Even though the Bw-tree performed so well, it should be kept in mind that core storage engine elements, such as transaction support, logging, and persistence, are missing. Implementing these would certainly reduce its performance, however, the scaling potential is quite real. In the end, it is questionable what Oracle would gain by implementing a Bw-tree into InnoDB. After all, the index was built with modern hardware in mind, using CaS operations rather than latches. This either means that substantial changes would have to be made to InnoDB or an entirely new storage engine would be needed instead. | |
