Verteilung globaler Anfragen auf heterogene Stromverarbeitungssysteme

Deployment of Global Queries in Distributed and Heterogeneous Stream-Processing Systems

  • Datenstromsysteme haben sich in den letzten Jahren als interessante Alternative zu Datenbanken für die kontinuierliche Anfrageverarbeitung etabliert. In vielen Szenarien fallen die zu verarbeitenden Datenströme verteilt an. Zur Reduzierung des Verarbeitungs- und Kommunikationsaufwandes drängt sich eine verteilte Datenstromverarbeitung nahezu auf, die eine Filterung oder Verdichtung der Daten bereits in Nähe der Datenquelle durchführt. Mit diesem Problem haben sich zahlreiche wissenschaftliche Projekte in den letzten Jahren auseinandergesetzt. Häufig gehen mit der verteilten Datenstromverarbeitung heterogene Systeme einher. Insbesondere so genannte Wireless Sensor Networks (WSNs) haben sich aDatenstromsysteme haben sich in den letzten Jahren als interessante Alternative zu Datenbanken für die kontinuierliche Anfrageverarbeitung etabliert. In vielen Szenarien fallen die zu verarbeitenden Datenströme verteilt an. Zur Reduzierung des Verarbeitungs- und Kommunikationsaufwandes drängt sich eine verteilte Datenstromverarbeitung nahezu auf, die eine Filterung oder Verdichtung der Daten bereits in Nähe der Datenquelle durchführt. Mit diesem Problem haben sich zahlreiche wissenschaftliche Projekte in den letzten Jahren auseinandergesetzt. Häufig gehen mit der verteilten Datenstromverarbeitung heterogene Systeme einher. Insbesondere so genannte Wireless Sensor Networks (WSNs) haben sich als interessante Datenquelle angeboten, da sie eine neuartige programmierbare Datenquelle mit speziellen Herausforderungen darstellen, die in die Datenstromverarbeitung eingebunden werden kann. In der Kette der stromverarbeitenden Systeme werden die einzelnen Verarbeitungsschritte meist manuell festgelegt, so dass diese Heterogenität weitgehend ignoriert werden kann. Diese manuelle Vorgehensweise kann als Bottom-Up-Ansatz charakterisiert werden. In dieser Arbeit wird angenommen, dass aus Sicht potenzieller Anwender eine Verteilung globaler Anfragen automatisch erfolgen sollte. Die Integration der verteilten und heterogenen Systeme soll dabei in einem Top-Down-Ansatz automatisch ablaufen. Daher wird zunächst eine Möglichkeit vorgestellt, um globale Anfragen plattform- und verteilungsunabhängig zu definieren. Das Szenario wird dabei zusammen mit den Metadaten unabhängig von der abstrakten Anfrage modelliert. Die Verteilung der Anfrage soll nach Kostenaspekten optimieren und muss dabei die Fähigkeiten der einzelnen stromverarbeitenden Systeme berücksichtigen. Zu diesem Zweck werden Kostenmodelle vorgestellt und Verteilungsalgorithmen evaluiert. Nach der Zerlegung der globalen Anfrage werden die Teilanfragen in eine plattformspezifische Darstellung gebracht. Dies wird für graphbasierte und SQL-basierte Anfragedefinitionen umgesetzt und auch die Generierung von C-Code für WSN-Knoten wird unterstützt. Erleichtert wird die Integration durch die Einführung eines abstrakten Tupelformats sowie eines Modellgraphen, der die Schemaableitung, die Ratenschätzung und weitere für die Verteilung relevante Informationen aufbereitet. Alle notwendigen Verfahren sind in einem Prototyp integriert, der abstrakte Anfragen geeignet zerlegt und dabei verteilte und heterogene Datenstromsysteme einbindet.show moreshow less
  • Distributed in-network stream processing is more efficient than sending all data to a central processing unit. In the past few years Stream-Processing Systems (SPSs) have established themselves as an interesting alternative to database systems for continuous query processing. There are many scenarios having widely distributed data streams as data sources. Distributed stream processing is an obvious solution for reducing computation and communication effort. It facilitates early filtering and aggregation in the vicinity of the data sources. There have been many publications dealing with stream processing and distributed stream processing in particular. These distributed systems are often heteDistributed in-network stream processing is more efficient than sending all data to a central processing unit. In the past few years Stream-Processing Systems (SPSs) have established themselves as an interesting alternative to database systems for continuous query processing. There are many scenarios having widely distributed data streams as data sources. Distributed stream processing is an obvious solution for reducing computation and communication effort. It facilitates early filtering and aggregation in the vicinity of the data sources. There have been many publications dealing with stream processing and distributed stream processing in particular. These distributed systems are often heterogeneous. Especially Wireless Sensor Networks (WSNs) have been used as a challenging data source. They are novel programmable and can participate in stream processing. Many projects have only focused on the technical impact of heterogeneity as they configure each single step of data processing manually. We characterize this as a bottom-up approach. In this work, we assume that users want to define global queries not considering both distribution and heterogeneity of distributed SPSs, i.e. queries should be distributed and deployed automatically. A top-down approach has to integrate distributed and heterogeneous SPSs automatically. This work offers a possibility for defining global queries that are independent of platform and topology constraints. The domain of the distributed query is part of the metadata and can be defined separately from the abstract query. Query distribution should be cost-optimal and has to consider constraints due to topology and capabilities of the distributed SPSs. We provide cost models and evaluate distribution algorithms for this purpose. Partitioning a global query leads to partial queries that are still abstract. A query mapper creates platform-specific queries. The query mapper can create graph-based and SQL-based queries. Further, we support the generation of modules for WSN nodes. An intermediate tuple format facilitates the technical integration of heterogeneous SPSs having different representations of data-stream elements. We use a model graph as representation of the global query for schema deduction, rate estimation and the derivation of other data that is relevant for the distribution process. A prototype integrates all relevant processes and algorithms. After the query-distribution step, it deploys mapped partial queries to different SPSs and connects the relevant data streams.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Michael Daum
URN:urn:nbn:de:bvb:29-opus-27659
Advisor:Klaus Meyer-Wegener
Document Type:Doctoral Thesis
Language:German
Date of Publication (online):2011/09/07
Publishing Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)
Granting Institution:Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU), Technische Fakultät
Date of final exam:2011/07/26
Release Date:2011/09/07
Tag:Datenstromverarbeitung; Integration von Stromverarbeitungssystemen; Wireless Sensor Networks
Integration; Stream-Processing; Wiresless Sensor Networks
SWD-Keyword:Abfrageverarbeitung; Codegenerierung; Datenstrom; Ganzzahlige lineare Optimierung; Heterogeni; MDA <Vorgehensmodell>; Metaheuristik; Middleware
Institutes:Technische Fakultät -ohne weitere Spezifikation-
Dewey Decimal Classification:004 Datenverarbeitung; Informatik

$Rev: 12793 $