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
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique , CentraleSupélec
4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
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.
Type de document :
Rapport
[Research Report] LINA-University of Nantes; Sapienza Università di Roma (Italie); Irisa; Inria Rennes. 2016
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01311970
Contributeur : Nicolò Rivetti <>
Soumis le : mercredi 4 mai 2016 - 18:05:03
Dernière modification le : vendredi 12 octobre 2018 - 15:10:02
Document(s) archivé(s) le : mardi 15 novembre 2016 - 20:29:20

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

1935

Téléchargements de fichiers

167