Evaluating the potential and possibilities of combining LSM-trees and secondary indexes

Abstract

De siste årene har databaseindeks-konseptet Log-Structured Merge-tree (LSM-tree) fått fotfeste som en stadig mer utbredt løsning. LSM-tree er relativt optimalisert for skrive-intensive arbeidsoppgaver, ettersom at konseptet utelater struktur og modifikasjon av data på samme disklokasjon, til fordel for et sekvensielt mønster for diskaksess. Flere populære, distribuerte NoSQL-databaser benytter lagringsmetoder basert på LSM-tree i persistens-laget deres. Et utvalg av disse databasene tilbyr sekundærindeksering med forbehold.

Også i tilfeller hvor en database stort sett betjener skrive-intensive oppgaver, kan behov for spørringer med krav til attributter forekomme. Å søke gjennom en database uten støtte fra en indeks kan gå fryktelig sakte, og ikke minst være veldig ressurskrevende.

Denne oppgaven kan betraktes som et sammenlignende studie, hvor LSM-tree blir sammenlignet med B-tree, med sekundærindeksering i fokus. Begge databaseindeks-konseptene er representert ved et utvalg databaser. Ulike sekundærindeksering-teknikker for LSM-tree blir også sammenlignet med hverandre, og hvordan de påvirker andre databaseoperasjoner - ettersom at den basale kompleksiteten til en database øker ved at en legger til en ny indeks. En forstudie ble gjennomført for å få overblikk over konsepter og databasenes indre, og deretter ble databasene ytelsestestet for å få innsikt i hvordan de yter i praksis.

De undersøkte databasene er i hovedsak basert på LSM-tree eller variasjoner av B-tree. For sekundærindeksering benytter de dominerende databasene enkle, separate indekser til å finne primærnøkler til relevante, lagrede objekter. Primærnøklene blir deretter brukt til å hente de relevante objektene gjennom primærindeks. En variasjon av en separat indeks, duplikatindeks, er også representert i ytelsestestingen. En nyere og litt ulik tilnærming, innebygd indeks, er undersøkt i kartleggingen, men ikke representert i ytelsestestingen.

Ytelsestestingen ble gjennomført med et datasett langt mindre enn testmaskinens minne. Resultatmessig var databasene ganske jevne, også på tvers av skillet mellom databaser basert på LSM-tree og B-tree. Cassandra, som representant for LSM-tree, og MongoDB, som representant for B-tree, scoret begge over gjennomsnittet for de fleste lese- og skrive-testene. Mens Cassandra var overlegen på skrive-operasjoner, var MongoDB ganske suveren på lese-operasjoner. Cassandra viser at LSM-tree kan gjøre det bra for både lese-intensive og skrive-intensive arbeidsmengder. Valget mellom Cassandra og MongoDB er til sist et spørsmål om mengdeforholdet mellom lese-operasjoner og skrive-operasjoner, og muligens kompleksiteten til lese-operasjonene.

I denne studien fremkommer det en tendens til små ytelsesforskjeller mellom B-tree og LSM-tree, for de fleste databasene. For store datamengder, som de utvalgte databasene opprinnelig er designet for, kunne resultatene blitt betydelig annerledes. Et datasett som ikke utfordrer minnekapasiteten, vil nok ikke på en adekvat måte belyse en av de store styrkene til et LSM-tree - dets sekvensielle mønster for diskaksess.

The database index concept Log-Structured Merge-tree (LSM-tree), has in recent years settled as a popular solution. The LSM-tree is relatively optimized for write-intensive workloads as it leaves out structure and in-place modifications in favor of a sequential disk access pattern. Multiple popular, distributed, NoSQL databases utilize storage engines based on the LSM-tree at their storage level, whereby a selection only provide secondary indexing with reservations.

Though a workload is write-intensive, queries conditioning attributes apart from primary key may occur. Searching through a database without the support of an index, is usually immensely slow, and the computational complexity is correspondingly poor.

This thesis can be considered as a comparative study, where the LSM-tree is compared to the B-tree, with secondary indexing in focus. Both index concepts are represented through a selection of databases. Different secondary indexing techniques for LSM-trees are also compared to each other, and how they affect the simpler operations of the LSM-tree - as the basal complexity of the databases increase. A survey was first conducted to get an overview of the state of affairs, and then a benchmark was conducted to measure actual performance of the databases.

The databases examined are mainly based on either the LSM-tree or variations of the B-tree. For secondary indexing, the most dominating databases all utilize simple, separate indexes to retrieve the primary keys of actual records and later fetch the entire records through the primary index. A variation of the separate index, the covered index, is also present in the benchmark. A novel approach, embedded index, is examined in the survey, but not represented in the benchmark.

The benchmark was conducted with an in-memory size dataset. The databases appeared to be quite even, even across the line between LSM-tree and B-tree. Cassandra, representing the LSM-tree, and MongoDB, representing the B-tree, both score above average for most read and write operations. While Cassandra is superior at write operations, MongoDB excels at read operations. Cassandra shows that the LSM-tree can do well for both read-intensive and write-intensive workloads. The choice between Cassandra and MongoDB is still a question of ratio between read and write operations, and possibly the complexity of the read operations.

For in-memory workloads, there is a tendency of evenness between LSM-tree and B-tree, for most databases. For big amounts of data, in which the selection of databases were originally designed for, the results could be significantly different. An in-memory dataset does not adequately enlighten one of the major strengths of the LSM-tree - its sequential disk access pattern.