Near Real-Time Indexing and Querying of Spatiotemporal Data in Distributed Key-Value Stores

Abstract

"Internet of Things" (IoT) er under stadig utvikling, og kompleksiteten og volumet på generert data øker i takt med at fler IoT enheter kobles til. Enheter som sensorer, biler, smarttelefoner og droner kan alle generere store mengder spatiotemporell data som spesifiserer enhetens plassering på et gitt tidspunkt. Innsamlingen og utnyttelsen av spatiotemporell data på stor skala muliggjør mange nye tjenester, men krever også kontinuerlige forbedringer i metodene for lagring, indeksering, prosessering og spørringer på denne dataen etter hvert som tjenester etterspør strengere servicenivå-garantier. Horisontalt skalerbare NoSQL systemer har blitt introdusert for å håndtere det store datavolumet, men da disse hovedsaklig er utviklet for endimensjonell data i form av nøkkel-verdi-par er indeksering av multidimensjonell data et ikke triviellt problem. Romfyllende kurver kan brukes for å linearisere spatiotemporell data, og muliggjør bruken av endimensjonale NoSQL databaser for indeksering og utføring av spørringer på spatiotemporell data. Det er ikke klart hvor godt en NoSQL database i samband med romfyllende kurver støtter nær sanntid indeksering og spørringer, og denne oppgaven forsøker å svare på dette ved å studere eksisterende metoder og karakteristikker ved NoSQL databaser.

En studie av to eksisterende systemer, GeoMesa og GeoWave, er blitt gjennomført, og metodene som er brukt i disse systemene er blitt kartlagt for å belyse hvordan indeksering og spørringer på spatiotemporell data i NoSQL databaser gjøres i praksis. For å forsøke å svare på hvor godt slike metoder fungerer i nær sanntid scenarier er det blitt foreslått en rekke krav en NoSQL database må imøtekomme for å kunne sies å støtte indeksering og spørringer i nær sanntid. ScyllaDB, en NoSQL database er blitt evaluert opp mot disse kravene, og et sett med eksperimenter er foreslått som kan gi en bedre indikasjon på hvor godt nær sanntid bruksområdet støttes.

Resultatene fra evalueringen av NoSQL databaser og spesifikt ScyllaDB opp mot kravene som ble stillt viser at ikke alle kravene ble oppfyllt av ScyllaDB. Mer spesifikt ble blant annet ikke kravene til forsinkelsestid møtt, og det viste seg usannsynlig at områdespørringer vil kunne utføres innenfor korte tidsrom. For at et NoSQL basert på LSM-trær skal støtte nær sanntid indekseringer og spørringer bør framtidig arbeid være i retning av å forbedre områdespørringer.

The Internet of Things (IoT) is continuously evolving and expanding, and the complexity and volume of the data generated by IoT devices is increasing as a result. IoT devices such as various sensors, cars, smartphones and aerial drones are all equipped to generate large amounts of spatiotemporal data specifying their geographical location at a given point in time. The mass collection and utilization of spatiotemporal data enable a whole set of new services to be deployed, as well as requiring continual improvements in the methods for storing, indexing, processing and querying the data as services demand ever more strict service level agreements. NoSQL systems that are horizontally scalable have been introduced in order to cope with the large volume of data, however, as these are typically one-dimensional data stores, indexing multidimensional data is not a trivial task. Space-filling curves enable the linearization of spatiotemporal data and may allow for the usage of NoSQL systems to support the indexing and querying of spatiotemporal data. It is not clear how well a NoSQL database would support near real-time indexing and querying of spatiotemporal data using space-filling curves and the thesis aims to examine existing methods as well as the characteristics of NoSQL stores in order to answer this.

An examination of methods used in two prevalent systems, GeoMesa and GeoWave, has been performed in order to study how space-filling curves may be used in conjunction with NoSQL stores to index and query spatiotemporal data. Furthermore, to examine how well distributed key-value stores support near real-time indexing and querying of spatiotemporal data a set of requirements has been proposed to provide a framework for evaluation. ScyllaDB, a NoSQL store, has been evaluated with regards to the established requirements, and finally an experimental setup for evaluating the performance of different space-filling curve and key-value store combinations has been proposed.

We found that both GeoMesa and GeoWave provide complete extensible facilities for indexing and querying spatiotemporal data in NoSQL stores. Furthermore, regarding the viability of near real-time scenarios with ScyllaDB it was found that it likely does not meet all the requirements, specifically with regards to latency and range queries. Further work is needed to improve latency guarantees and range query performance before key-value stores based on the LSM-tree can be considered viable.