InnoDB and the Bw-tree An analysis and comparison of an unlikely friendship in today's times

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