Dynamic Bloom Filters in Cassandra DB

Abstract

Denne masteroppgaven undersøker en mye brukt distribuert database, Cassandra. Cassandra ble først utviklet av Facebook, men administreres nå av Apache-stiftelsen, og er tilgjengelig som åpen kildekode. NoSQL-databasen brukes av kjente selskaper som Apple, Netflix, eBay og GitHub. Cassandra er populært fordi det tilbyr konkurransedyktige egenskaper som høy tilgjengelighet, enkelt oppsett og vedlikehold, fleksibel datastruktur og god skalerbarhet på grunn av sin master-less arkitektur og peer-to-peer replikering.

Cassandra bruker flere metoder for å øke tilfeldig leseytelse, inkludert Bloom-filtre, cacher og komprimeringer. Et Bloom-filter er en interessant probabilistisk datastruktur som brukes i Cassandra for å øke effektiviteten til en lesesøk. Når man forespørr data, kan Bloom-filterene brukes til å raskt oppdage om dataene sannsynligvis eksisterer eller om de helt sikkert ikke gjør det. Bloom filtrene in Cassandra ble utforsket i dybden i fordypningsprosjektet\cite{specialisationproject}, og resultatene som ble funnet har blitt brukt som inspirasjon til formålet med denne masteroppgaven.

Bloom-filtrene i Cassandra er konfigurerbare og størrelsen på filteret påvirker presisjonen filteret har, noe som betyr at mer presise Bloom-filtre bruker mer plass. Vår hypotese er at ved å dynamisk sette størrelsene på Bloom-filtrene i Cassandra, kan vi forbedre leseytelsen for data som er aksessert mye til en lavere plasskostnad. I denne oppgaven undersøker vi en måte å dynamisk justere Bloom-filtre basert på lesehyppigheten til spesifikke data.

Det dynamiske Bloom-filteret ble implementert ved å endre Bloom-filterets logikk i kassandras kildekode. Bloom-filterstørrelsen endres basert på populariteten, her lesehyppigheten, til dataene.

This master thesis explores one commonly used distributed database, Cassandra. Cassandra was initially developed by Facebook, but it is now managed by the Apache foundation and is distributed as open-source. The NoSQL database is used by well-known companies like Apple, Netflix, eBay, and GitHub. Cassandra is popular because it offers competitive properties as high availability, easy setup and maintenance, flexible wide-column data structure, and good scalability because of its master-less architecture and peer-to-peer replication.

Cassandra applies several methodologies to elevate random read performance, including Bloom filters, caches, and compactions. A Bloom filter is an interesting probabilistic data structure used in Cassandra to increase the efficiency of a read query. When querying data Bloom filters can be used to quickly discover whether the data likely exists or whether it for certain does not. Bloom filters in Cassandra were explored in depth in the specialization project preceding this thesis, and the results have been used as inspiration to the purpose of this master thesis.

Bloom filters in Cassandra are configurable and the size of the filter affects the precision of it, meaning more precise Bloom filters use more space. The hypothesis is that by dynamically tuning the sizes of the Bloom filters in Cassandra, we can precisely improve read performance for frequently accessed data at a lower space cost. In this thesis, we explore a way of dynamically tuning Bloom filters based on the read frequency of specified data.

A proof of concept of a dynamically tuning Bloom filter is presented in this thesis. It is implemented by altering the logic within Cassandra's source code, exploiting the read rate, or hotness, of the accessed data.