Load-Aware Shedding in Stream Processing Systems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2016

Load-Aware Shedding in Stream Processing Systems

Résumé

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.
Fichier principal
Vignette du fichier
main.pdf (766.8 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01311970 , version 1 (04-05-2016)

Identifiants

  • HAL Id : hal-01311970 , version 1

Citer

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⟩
745 Consultations
234 Téléchargements

Partager

Gmail Facebook X LinkedIn More