HYPERSONIC A Hybrid Parallelization Approach for Scalable Complex Event Processing.pdf

Bigbig

165

15页

1次

2022-07-12

免费下载

HYPERSONIC: A Hybrid Parallelization Approach for Scalable

Complex Event Processing

Maor Yankovitch

Technion, Israel Institute of

Technology

Haifa, Israel

yankovitch@cs.technion.ac.il

Ilya Kolchinsky

Technion, Israel Institute of

Technology

Haifa, Israel

ikolchin@cs.technion.ac.il

Assaf Schuster

Technion, Israel Institute of

Technology

Haifa, Israel

assaf@cs.technion.ac.il

ABSTRACT

The ability to promptly and eciently detect arbitrarily complex

patterns in massive real-time data streams is a crucial requirement

in many modern applications. The ever-growing scale of these

applications and the sophistication of the patterns involved makes it

imperative to employ advanced solutions that can optimize pattern

detection. One of the most prominent and well-established ways

to achieve the above goal is to apply complex event processing

(CEP) in a parallel manner, using a multi-core machine and/or a

distributed environment. However, the inherent tightly coupled

nature of CEP severely limits the scalability of the parallelization

methods currently available.

In this paper, we introduce a novel parallelization mechanism for

ecient complex event processing over data streams. This mech-

anism is based on a hybrid two-tier model combining multiple

layers of parallelism. By employing a ne-grained load balancing

model, this multi-layered approach leads to a substantial increase

in event detection throughput, while at the same time reducing the

latency and the memory consumption. An extensive experimental

evaluation on multiple real-life datasets shows that our approach

consistently outperforms state-of-the-art CEP parallelization meth-

ods by a factor of two to three orders of magnitude.

CCS CONCEPTS

• Information systems

→

Stream management; Query opti-

mization; • Computing methodologies

→

Parallel algorithms;

Distributed algorithms.

KEYWORDS

Complex Event Processing, Parallel Query Processing, Distributed

Query Processing, Query Optimization

ACM Reference Format:

Maor Yankovitch, Ilya Kolchinsky, and Assaf Schuster. 2022. HYPERSONIC:

A Hybrid Parallelization Approach for Scalable Complex Event Processing.

In Proceedings of the 2022 International Conference on Management of Data

(SIGMOD ’22), June 12–17, 2022, Philadelphia, PA, USA. ACM, New York, NY,

USA, 17 pages. https://doi.org/10.1145/3514221.3517829

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for components of this work owned by others than ACM

must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,

to post on servers or to redistribute to lists, requires prior specic permission and/or a

fee. Request permissions from permissions@acm.org.

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

ACM ISBN 978-1-4503-9249-5/22/06.. .$15.00

https://doi.org/10.1145/3514221.3517829

1 INTRODUCTION

Complex event processing (CEP) is a leading technology for robust

and high-performance real-time detection of arbitrarily complex

patterns in massive data streams [

]. It is widely employed

in many areas where the data is continuously generated in a stream-

ing manner and needs to be promptly and eciently analyzed on-

the-y. Online nance [

], credit card fraud detection [

], sensor

networks [

], healthcare industry [

], and IoT applications [

]

are among the many examples.

CEP engines treat the data items that make up the input streams

as primitive events arriving from event sources. As new primitive

events are observed, they are assembled into higher-level complex

events that match the user-dened patterns. Detecting complex

events is performed by collecting primitive events and incremen-

tally combining them into partial matches. As more events are added

to a partial match, a full pattern match is eventually formed and

reported. The loose order of constructing and extending partial

matches is dened by a graph-based structure, typically an automa-

ton or a tree, composed of a set of states. Each state represents

some intermediate stage of pattern detection. Figure 1 (and 1(b) in

particular) illustrates this principle.

As discussed by multiple authors [

], the processing time,

latency, and resource consumption of the CEP execution grows ex-

ponentially with the length of the pattern being detected. The main

factor contributing to this growth is the need to explicitly examine a

large number of sets of events to determine whether they comprise

valid pattern matches, which leads to a crucial performance bottle-

neck. The situation is exacerbated by the tight real-time constraints

imposed on these systems, as well as by a common requirement to

simultaneously process multiple patterns and streams. Therefore,

advanced optimization techniques are essential for achieving an

acceptable quality of service.

Parallelizing CEP evaluation ows is one of the most prominent

avenues for improving the performance of event processing appli-

cations. Various techniques for allocating the workload of a CEP

system to multiple execution units and managing their parallel

execution have been proposed, addressing multi-core and fully dis-

tributed scenarios. These solutions can be roughly divided into two

separate categories: data-parallel and state-parallel methods.

Data-parallel approaches [

] operate by splitting the

input data stream into dierent partitions according to predened

criteria and routing each partition to a dedicated execution unit;

this unit may be a thread, a process, or a separate machine. Each

unit then applies the same pattern matching process on the data it

receives, and the resulting pattern matches are merged and jointly

returned to the end users. Figure 1(a) presents an example of a

Session 15: Streaming and Sensor Networks 2

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1093

(a) Data parallelism (b) State parallelism (c) Hybrid parallelism

Figure 1: Parallelism classes: (a) input is split into partitions and handled separately by each execution unit; (b) each building block is

represented by a dedicated execution unit that receives a substream of events and performs a well-dened sequential task; (c) a two-layer

approach combining both data parallelism and state parallelism.

parallel CEP system architecture implemented according to this

paradigm. While this scheme was proven highly ecient in many

cases, its inherent limitation lies in the diculty of designing a

good partitioning scheme. Since any subset of data items can repre-

sent a pattern match, at least a fraction of the sub-streams must be

duplicated to multiple units to avoid missing results and to guaran-

tee detection correctness. It is also exceptionally hard to achieve

ne-grained load balancing in presence of data skew.

The second category of CEP parallelization methods is known

as state-parallel [

]. This approach assigns a dedicated exe-

cution unit to each building block of the pattern detection model,

making it exclusively responsible for some functional part of the

sequential pattern matching algorithm. The units are arranged ac-

cording to a predened topology and the intermediate results of the

pattern match construction process are passed between them. An

example is shown in Figure 1(b). This parallelization scheme avoids

the data stream duplication problem that plagues data-parallel meth-

ods. However, it imposes a hard limit on the degree of parallelism as

the number of execution units is bounded by the number of states.

In this paper, we propose HYPERSONIC: a HYbrid ParallElization

appRoach for Scalable cOmpLex eveNt processIng appliCations.

HYPERSONIC implements a new paradigm for parallelizing CEP

applications, which we refer to as a hybrid-parallel approach. In a

hybrid-parallel system, the execution units are organized in two

layers, and the workload distribution proceeds in two stages. First,

a state-parallel procedure allocates a set of execution units to each

state according to its expected load. Second, a data-parallel routine is

applied within each state to share the work performed by this state

between the individual units. This process is repeated continuously

during the system run. In this way, the system can dynamically

adapt to the ever-changing data arrival rates, system properties,

and resource availability. Figure 1(c) illustrates this scheme.

By providing two distinct layers of parallelism, our approach

combines the strengths of data-parallel and state-parallel solutions

while overcoming their limitations. Unlike that of a pure state-

parallel system, the degree of parallelism in HYPERSONIC is un-

bounded. In addition, no duplicate data transmission is required:

the outer parallelization layer mimics the evaluation ow of the

state-parallel approach and only passes the data once between ad-

jacent states, while the inner parallelization layer avoids the need

for an explicit partitioning scheme by utilizing shared memory

between execution units. This latter communication mechanism

is designed in a way allowing an extension to a fully distributed

share-nothing environment. The two-tier dynamic load balancing

scheme of HYPERSONIC ensures ecient allocation of execution

units to states and of the input data to execution units based on

up-to-date data characteristics and system load.

Rather than merely constituting a load balancing scheme, HY-

PERSONIC is an end-to-end system for ecient and scalable parallel

execution of complex event processing workloads. Any method for

CEP parallelization faces a multitude of CEP-specic challenges

stemming from the inherent tightly coupled nature of the problem.

These challenges include avoiding data duplication, enabling data

sharing between the execution units, and supporting highly com-

plex operators. As we elaborate later on, our solution successfully

tackles these challenges.

The contributions of this paper can be summarized as follows:

•

A novel hybrid-parallel approach for eciently distributing

CEP workloads between multiple execution units.

•

A two-level load balancing scheme based on the above sys-

tem architecture, and a thorough analysis of its performance.

•

Practical extensions to the basic hybrid-parallel method al-

lowing us to further improve the performance and the re-

source utilization of pattern detection.

•

An extensive experimental evaluation of our method, demon-

strating its superiority over state-of-the-art CEP paralleliza-

tion mechanisms as well as a superlinear speedup over the

sequential baseline.

The remainder of this paper is organized as follows. Section 2

presents the necessary background and formally denes the tar-

geted problem. The core design of HYPERSONIC is described in

Section 3 with important extensions covered in Section 4. We re-

port the results of our experimental study in Section 5. Section 6

discusses the related work and Section 7 concludes the paper.

Session 15: Streaming and Sensor Networks 2

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

1094

of 15

免费下载

sigmod2022 paper

关注

评论