BBoxDB – A Distributed Key-Bounding-Box-Value Store

Nidzwetzki, Jan, Kristof

doi:10.18445/20220620-140043-0

published

BBoxDB – A Distributed Key-Bounding-Box-Value Store

English
German

The need for processing multi-dimensional data at scale is growing strongly. Nowadays, GPS receivers are integrated into many devices, and location-based applications that process such data are ubiquitous. However, the support for multi-dimensional data carves out a niche existence in distributed databases. In most of these systems, multi-dimensional data cannot be processed efficiently. Data are distributed across a cluster of nodes based on a one-dimensional key (e.g., a hash function is applied on the key to determine the node that is responsible for the data). The key and the resulting data distribution are not related to the location of the data in space. Common operations on multi-dimensional data, such as range queries (e.g., Which road is located in a given area?) or spatial joins (e.g., Which road leads through a forest?) cannot be executed efficiently by these systems. The query rectangle of the range query cannot be used to determine the tuples that belong to the query result directly. Therefore, a full data scan has to be performed on all nodes, which is an expensive and slow operation. In addition, for the execution of a spatial join, many tuples need to be shuffled and transferred between the nodes, which is also expensive and slow. This thesis covers the design and implementation of two distributed systems that are optimized for the handling of multi-dimensional big data. Distributed SECONDO is a hybrid system that combines the extensible database system SECONDO with the key-value store Apache Cassandra. SECONDO is used for query processing and Cassandra for data storage. The resulting system is a distributed and highly available version of SECONDO. Already in SECONDO implemented algorithms and data models can be used in a distributed and parallel manner on a cluster of nodes; large datasets can be handled without changing the implementation of these operators or data models. Distributed SECONDO was used to study challenges in the distributed storage and processing of multi-dimensional big data. The insights gained led to the development of BBoxDB. BBoxDB is a novel distributed NoSQL database implemented from scratch. The software provides a highly available key-bounding-box-value store. In contrast to regular key-value stores, the values are stored together with a bounding box that describes the location of the value in the n-dimensional space. Range queries and spatial joins can be efficiently executed. Even if data of any dimension are supported, BBoxDB focuses on the handling of lower-dimensional data (e.g., spatial data). BBoxDB partitions (splits and merges) the n-dimensional space dynamically based on the stored data. The software supports point and non-point data, which are spread in a cluster of nodes according to the partitioning. BBoxDB is a generic data store; the stored values are opaque arrays of bytes. Therefore, queries are primarily executed on the bounding boxes of the data. Query results can be refined by user-defined filters, which include the knowledge to interpret the bytes of the stored values. With the extension BBoxDB Streams, the processing of multi-dimensional data streams is also supported.

Es gibt einen stetig wachsenden Bedarf, große Mengen an mehrdimensionalen Daten zu verarbeiten. GPS-Empfänger sind heutzutage in vielen Geräten integriert und ortsbezogene Anwendungen, welche solche Daten verarbeiten, sind allgegenwärtig. Die Unterstützung für multidimensionale Daten fristet jedoch ein Nischendasein in verteilten Datenbanken. Mit den meisten dieser Systeme können mehrdimensionale Daten nicht effizient verarbeitet werden. Die Daten werden auf der Grundlage eines eindimensionalen Schlüssels auf einen Cluster von Knoten verteilt (z.B. durch Anwendung einer Hash-Funktion auf den Schlüssel, um den für die Daten zuständigen Knoten zu ermitteln). Der Schlüssel und die sich daraus ergebende Verteilung der Daten stehen in keinem Zusammenhang mit der Position der Daten im Raum. Gängige Operationen auf mehrdimensionalen Daten wie Bereichsabfragen (z.B. Welche Straße befindet sich in einem bestimmten Gebiet?' oder Spatial Joins (z.B. Welche Straße führt durch einen Wald?}) können von diesen Systemen nicht effizient ausgeführt werden. Das Abfragerechteck der Bereichsabfrage kann nicht verwendet werden, um die relevanten Tupel direkt aufzufinden. Daher muss ein vollständiger Datenscan auf allen Knoten durchgeführt werden, was ein teurer und langsamer Vorgang ist. Zudem müssen für die Berechnung des Spatial Joins viele Tupel zwischen den Knoten umverteilt und übertragen werden, was ebenfalls teuer und langsam ist. In dieser Dissertation wird der Entwurf und die Implementierung von zwei Systemen behandelt, welche für die Verarbeitung von multidimensionalen Daten optimiert sind. Distributed SECONDO ist ein Hybridsystem, das das erweiterbare Datenbanksystem SECONDO mit dem Key-Value Store Apache Cassandra kombiniert. SECONDO wird für die Abfrageverarbeitung eingesetzt und Cassandra für die Datenspeicherung. Das resultierende System ist eine verteilte und hochverfügbare Version von SECONDO. Bereits in SECONDO implementierte Algorithmen und Datenmodelle können verteilt und parallel auf einem Cluster von Systemen verwendet werden. Große Datenmengen können ohne Änderung der Implementierung dieser Operatoren oder Datenmodelle verarbeitet werden. Distributed SECONDO wurde verwendet, um die verteilte Speicherung und Verarbeitung von großen mehrdimensionalen Datenmengen zu untersuchen. Die gewonnen Erkenntnisse führten zu der Entwicklung von BBoxDB. BBoxDB ist eine verteilte NoSQL-Datenbank, welche von Grund auf neu entwickelt wurde. Die Software bietet einen hochverfügbaren Key-Bounding-Box-Value-Store. Im Gegensatz zu herkömmlichen Key-Value-Stores werden die Werte zusammen mit einer Bounding Box gespeichert, welche die Lage des Wertes in einem n-dimensionalen Raum beschreibt. Bereichsabfragen und Spatial Joins können effizient ausgeführt werden. Auch wenn Daten beliebiger Dimension von BBoxDB unterstützt werden, liegt der Schwerpunkt auf der Verarbeitung von niedrigdimensionalen Daten (z.B. Geodaten). BBoxDB partitioniert (teilt und verschmilzt) den $n-dimensionalen Raum dynamisch auf Grundlage der gespeicherten Daten. Die Software unterstützt Punkt- und Nicht-Punkt-Daten, welche entsprechend den Partitionen in einem Cluster verteilt werden. BBoxDB ist ein generisches System, die gespeicherten Werte sind opake Bytearrays für die Software. Abfragen werden daher primär auf den Bounding Boxen der Daten ausgeführt. Die Abfrageergebnisse können durch benutzerdefinierte Filter verfeinert werden, welche das Wissen zur Interpretation der gespeicherten Bytes beinhalten. Mit der Erweiterung BBoxDB Streams wird zudem die Verarbeitung von mehrdimensionalen Datenströmen unterstützt.