Exploiting the synergy between scheduling and load shedding to facilitate differentiated levels of service for continuous queries

Type PhD Dissertation Defense
Start Date April 8, 2016 02:00 PM
End Date April 8, 2016 04:00 PM
Location 6106 Sennott Square
Organizer Name
Speaker Name Thao Pham
Speaker Affiliation University of Pittsburgh Ph.D. Candidate
Abstract Data Stream Management Systems (DSMSs) offer the most effective solution for processing
data streams by efficiently executing continuous queries (CQs) over the incoming data. CQs
inherently have different levels of criticality and hence different levels of expected quality of
service (QoS) and quality of data (QoD). Adhering to such expected QoS/QoD metrics is
even more important in cases of multi-tenant data stream management services. In this dis-
sertation, we propose DILoS, a framework that, through priority-based scheduling and load
shedding, supports differentiated QoS and QoD for multiple classes of CQs. Unlike existing
works that consider scheduling and load shedding separately, DILoS is a novel unified frame-
work that exploits the synergy between scheduling and load shedding. For the realization of
DILoS, we propose ALoMa and SEamLeSS, two general, adaptive load managers. Our load managers perform better than the state-of-the-art alternatives in three dimensions: (1) they automatically tune the headroom factor, (2) they honor the delay target, and (3) they are applicable to complex query networks with shared operators.

We implemented DILoS, ALoMa and SEamLeSS in our real DSMS prototype system (AQSIOS) and evaluate their performance for a variety of real and synthetic workloads. Our experimental
evaluation of ALoMa and SEamLeSS verified their advantages over the state-of-the-art approaches. Our experimental evaluation of the DILoS framework showed that it (a) allows the scheduler and load shedder to consistently honor CQs’ priorities, (b) significantly increases system capaciity utilization by exploiting batch processing, and (c) enables operator sharing among query classes of different priorities while avoiding priority inversion, i.e., a lower-priority class never blocks a higher-priority one.

As a preliminary step toward our future work on a large-scale resource management using
DILoS, we also implemented UniMiCo, a protocol to migrate continuous queries without
interupting the execution of the queries. Our experiments showed that UniMiCo produced
correct outputs and did not introduce any hiccup in the response time of the queries.
Committee Panos K. Chrysanthis, Professor, University of Pittsburgh
Alexandros Labrinidis, Associate Professor, University of Pittsburgh
Adam Lee, Associate Professor, University of Pittsburgh
Christos Faloutsos, Professor, Carnegie Mellon University