Evaluating established B⁺-tree access methods in a parallel processing environment

Abstract

For å kunne fortsette å oppnå stadig større ytelse og gjennomstrømning, benytter datamaskiner i dag et økende antall prosesseringsenheter. Den moderne maskinvarearkitekturen krever horisontal skalerbarhet av applikasjoner og systemer som ønsker å operere mest mulig effektivt. Det å kunne skalere horisontalt innbefatter også evnen til å operere samtidig, og parallelt. Databasehåndteringssystemer (DBMSer) er komplekse systemer med en rik historie, samt en konstant søken etter forbedring på de områdene som muliggjør mest mulig effektiv håndtering av data, og behandling av forespørsler. Med det formålet å forbedre responstiden på den vanlige DBMS oppgaven som går ut på å få tak i poster som tilfredsstiller visse søkebetingelser, opprettes og benyttes supplerende behjelpelige tilgangsstrukturer kalt indekser. B/B⁺-treet er en ofte brukt databaseindeksstruktur. Denne strukturen ble først introdusert i 1970, en tid da de fleste datamaskiner bare hadde en enkelt prosesseringsenhet. Det finnes mange forsøk på å tilpasse og modifisere B/B⁺-treet slik at samspillet blir best mulig i møte med den moderne maskinvarearkitekturen, f.eks. [1]-[5]. Disse forsøkene er varierte både i tilnærming og teknikker benyttet.

Denne masteroppgaven gjør sitt eget forsøk på å parallellisere de allerede etablerte tilgangsmetodene til B⁺-treet. Implementasjonen av det parallelle B⁺-treet som presenteres opprettholdes i minnet, benytter “thread pool” designmønsteret, og støtter batchprosessering av operasjoner gruppert etter type, så vel som enkeltoperasjoner. Dessuten kan Bloom-filtre valgfritt benyttes og essensielle variabler, som den øvre grensen av en nodes antall barn, antall tråder, og antall vanlige B⁺-tree, konfigureres.

Resultatene som ble oppnådd på bakgrunn av å sammenligne ytelsen til den parallelle implementasjonen av B⁺-treet, og grunnlinjen etablert av det vanlige B⁺-treet som kun benytter en enkelt tråd, viser at beslutningen om å velge å utnytte tilgjengelig parallell prosesseringskapabilitet, bare vil være verdt det dersom graden av parallellitet er tilstrekkelig, og kostnaden indusert av oppgaveoppretting og håndtering blir ubetydelig sammenlignet med oppgaveutførelsestiden. Dette motiverer bruken av parallell batchprosessering og bruk av nytte-kostnadsanalyse for å beslutte når parallell utførelse skal foretas.

In order to keep achieving higher performance and throughput, computers nowadays trend towards employing an increasing number of processing units. The modern hardware architecture demands horizontal scalability by applications and systems wanting to operate most efficiently. Within the ability to scale horizontally lies the ability to operate concurrently, and in parallel. Database management systems (DBMSs) are complex systems with a rich history, always seeking to improve in ways that allows most efficient management of data, and handling of requests. For the purposes of speeding up the very common DBMS task of retrieving records in response to certain search conditions, additional auxiliary access structures, called indexes, are created and made use of. The B/B⁺-tree is a commonly used database index structure, with origins dating all the way back to 1970, a time when most computers only had a single processing unit. There are many attempts at making this structure better fit for the modern hardware architecture, e.g. [1]-[5]. These attempts are varied in approaches and techniques applied.

This master’s thesis makes its own attempt at parallelizing the already established access methods of the B⁺-tree. The parallel B⁺-tree implementation is sustained in-memory, makes use of a thread pool design pattern, and supports batch processing of operations grouped by type, as well as so-called single key operations. Futhermore, Bloom filters can optionally be enabled and essential variables, such as order, the number of threads, and the number of base B⁺-trees, can be configured.

The results obtained when comparing the parallel B⁺-tree implementation against a single threaded B⁺-tree basline, show that opting to leverage parallel processing capabilities will only ever be worthwhile, if the degree of parallelism is sufficient, and the cost induced by task creation and managment becomes negligible compared to task execution time. This motivates the use of parallel batch processing, and application of cost-benefit analysis to determine when to execute in parallel.