Skip to Main content Skip to Navigation
Reports

Load-Aware Shedding in Stream Processing Systems

Nicoló Rivetti 1, 2 Emmanuelle Anceaume 3 Yann Busnel 4 Leonardo Querzoni 2 Bruno Sericola 4
3 CIDRE - Confidentialité, Intégrité, Disponibilité et Répartition
CentraleSupélec, Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES, Inria Rennes – Bretagne Atlantique
Abstract : Load shedding is a technique employed by stream processing systems to handle unpredictable spikes in the input load whenever available computing resources are not adequately provisioned. A load shedder drops tuples to keep the input load below a critical threshold and thus avoid unbounded queuing and system trashing. In this paper we propose Load-Aware Shedding (LAS), a novel load shedding solution that, unlike previous works, does not rely neither on a pre-defined cost model nor on any assumption on the tuple execution duration. Leveraging sketches, LAS efficiently builds and maintains at runtime a cost model to estimate the execution duration of each tuple with small error bounds. This estimation enables a proactive load shedding of the input stream at any operator that aims at limiting queuing latencies while dropping as few tuples as possible. We provide a theoretical analysis proving that LAS is an (ε, δ)-approximation of the optimal online load shedder. Furthermore, through an extensive practical evaluation based on simulations and a prototype, we evaluate its impact on stream processing applications, which validate the robustness and accuracy of LAS.
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01311970
Contributor : Nicolò Rivetti <>
Submitted on : Wednesday, May 4, 2016 - 6:05:03 PM
Last modification on : Friday, July 10, 2020 - 4:23:45 PM
Long-term archiving on: : Tuesday, November 15, 2016 - 8:29:20 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01311970, version 1

Citation

Nicoló Rivetti, Emmanuelle Anceaume, Yann Busnel, Leonardo Querzoni, Bruno Sericola. Load-Aware Shedding in Stream Processing Systems. [Research Report] LINA-University of Nantes; Sapienza Università di Roma (Italie); Irisa; Inria Rennes. 2016. ⟨hal-01311970⟩

Share

Metrics

Record views

2600

Files downloads

403