Evaluering av ytelsen til aksessmetoder for main memory databaser

Abstract

Den publiserte forskningen om samtidige aksessmetoder for main memory databaser gir ingen entydige svar på hvilke aksessmetoder som yter best. Hovedårsaken til dette er usikkerhet knyttet til tidsforbruket til de nødvendige synkroniseringsmekanismene for samtidighetskontroll. Nyere ytelsesmålinger viser at tidsforbruket knyttet til synkroniseringsmekanismene kan være lavere enn først antatt. Vi har i denne rapporten simulert flere samtidighetsalgoritmer for aksessmetodene B-trær og T-trær. Simuleringene er foretatt under ulike realistiske omgivelser med varierende prosessorantall. Resultatene viser at algoritmene for T-trær, som setter èn lås i treet, yter bedre enn eller like godt som algoritmene for B-trær under alle omgivelser. Det eneste unntaket er når det anvendes mange prosessorer og en stor andel av operasjonene gjør innsettinger. I slike omgivelser yter B-trær best. Det er også utført simuleringer hvor tidsforbruket knyttet til synkroniseringsprimitivene er variert. Resultatene viser at ved lavt tidsforbruk er det effektivitet med tanke på prosessorbruk som har mest å si for ytelsen, mens ved høyt tidsforbruk er det antall låser som avgjør ytelsen. Ved tilstrekkelig mange samtidige operasjoner i aksessmetodene oppstår det, i alle de simulerte algoritmene, en flaskehals som skyldes en delt ressurs ved inngangen til aksessmetoden. Denne flaskehalsen fører til at det ikke oppnås høyere gjennomstrømning av operasjoner ved bruk av flere prosessorer. Det presenteres løsninger på dette problemet som er anvendbare på alle algoritmene. Simuleringer av algoritmer som anvender løsningene viser at man kan oppnå tilnærmet lineær skalering av ytelsen opp til minst $32$ prosessorer for alle algoritmene.