High-Availability Algorithms for Distributed Stream Processing
Published 19 April 2005
Jeong-Hyon Hwang, Magdalena Bałazińska, Alexander Rasin, Uğur Çetintemel, Mike Stonebraker, Stanley B. Zdonik
Citations263
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The design and algorithmic challenges associated with the proposed recovery techniques are discussed and how each can provide different guarantees with proper combinations of redundant processing, checkpointing, and remote logging are described.
Abstract
Stream-processing systems are designed to support an emerging class of applications that require sophisticated and timely processing of high-volume data streams, often originating in distributed environments. Unlike traditional data-processing applications that require precise recovery for correctness, many stream-processing applications can tolerate and benefit from weaker recovery guarantees. In this paper, we study various recovery guarantees and pertinent recovery techniques that can meet the correctness and performance requirements of stream-processing applications. We discuss the design and algorithmic challenges associated with the proposed recovery techniques and describe how each can provide different guarantees with proper combinations of redundant processing, checkpointing, and remote logging. Using analysis and simulations, we quantify the cost of our recovery guarantees and examine the performance and applicability of the recovery techniques. We also analyze how the knowledge of query network properties can help decrease the cost of high availability.
Keywords
Computer Science
Models and issues in data stream systems
2,517 Citations2002Brian Babcock, Shivnath Babu +3 more
The need for and research issues arising from a new model of data processing, where data does not take the form of persistent relations, but rather arrives in multiple, continuous, rapid, time-varying data streams are motivated.
ACM Computing SurveysA survey of rollback-recovery protocols in message-passing systems
1,795 Citations2002E. N. Mootaz Elnozahy, Lorenzo Alvisi +2 more
This survey covers rollback-recovery techniques that do not require special language constructs and distinguishes between checkpoint-based and log-based protocols, which rely solely on checkpointing for system state restoration.
The VLDB JournalAurora: a new model and architecture for data stream management
1,493 Citations2003Daniel J. Abadi, Don Carney +7 more
The basic processing model and architecture of Aurora, a new system to manage data streams for monitoring applications, are described and a stream-oriented set of operators are described.
The VLDB JournalThe CQL continuous query language: semantic foundations and query execution
1,187 Citations2005Arvind Arasu, Shivnath Babu +1 more
This paper presents the structure of CQL's query execution plans as well as details of the most important components: operators, interoperator queues, synopses, and sharing of components among multiple operators and queries.
Conference on Innovative Data Systems ResearchTelegraphCQ: Continuous Dataflow Processing for an Uncertain World.
966 Citations2003Sirish Chandrasekaran, Owen Cooper +9 more
The next generation Telegraph system, called TelegraphCQ, is focused on meeting the challenges that arise in handling large streams of continuous queries over high-volume, highly-variable data streams and leverages the PostgreSQL open source code base.
Elsevier eBooksMonitoring Streams — A New Class of Data Management Applications
838 Citations2002Don Carney, Uğur Çetintemel +7 more
This paper presents Aurora, a new DBMS that is currently under construction at Brandeis University, Brown University, and M.I.T. and describes the basic system architecture, a stream-oriented set of operators, optimization tactics, and support for real-time operation.
Models and issues in data stream systems
746 Citations2002Brian Babcock, Shivnath Babu +3 more
Why Do Computers Stop and What Can Be Done About It?
671 Citations2024Jim Gray
Fjording the stream: an architecture for queries over streaming sensor data
500 Citations2003Samuel Madden, Michael J. Franklin
This work presents the Fjords architecture for managing multiple queries over many sensors, and shows how it can be used to limit sensor resource demands while maintaining high query throughput.
Scalable Distributed Stream Processing
482 Citations2003Mitch Cherniack, Hari Balakrishnan +4 more
The architectural challenges facing the design of large-scale distributed stream processing systems are described, and novel approaches for addressing load management, high availability, and federated operation issues are discussed.
Query Processing, Approximation, and Resource Management in a Data Stream Management System.
410 Citations2003Rajeev Motwani, Jennifer Widom +8 more
Flux: an adaptive partitioning operator for continuous query systems
317 Citations2004Mehul A. Shah, Joseph M. Hellerstein +2 more
A dataflow operator called flux is introduced that encapsulates adaptive state partitioning and dataflow routing that can be used for CQ operators under shifting processing and memory loads and can provide several factors improvement in throughput and orders of magnitude improvement in average latency over the static case.
High-Availability Algorithms for Distributed Stream Processing
263 Citations2005Jeong-Hyon Hwang, Magdalena Bałazińska +4 more
The design and algorithmic challenges associated with the proposed recovery techniques are discussed and how each can provide different guarantees with proper combinations of redundant processing, checkpointing, and remote logging are described.
Highly available, fault-tolerant, parallel dataflows
205 Citations2004Mehul A. Shah, Joseph M. Hellerstein +1 more
A technique that masks failures in a cluster to provide high availability and fault-tolerance for long-running, parallelized dataflows that can use these dataflows to implement a variety of continuous query applications that require high-throughput, 24x7 operation.
The CQL Continuous Query Language : Semantic Foundations and Query Execution
102 Citations2003Arvind Arasu
ACM SIGMOD RecordEfficient resumption of interrupted warehouse loads
59 Citations2000Wilburt Labio, Janet L. Wiener +2 more
Lecture notes in computer scienceProviding high availability in very large workflow management systems
59 Citations1996M. Kamath, Gustavo Alonso +2 more
This paper addresses the problem of providing high availability in workflow management systems by proposing a backup technique which ensures that execution of a process instance can be resumed at any point in time in the event of a failure.
Efficient resumption of interrupted warehouse loads
38 Citations2000Wilburt Labio, Janet L. Wiener +2 more
This work develops a resumption algorithm called DR that imposes no overhead and relies only on the high-level properties of the transformations of the data and shows that DR can lead to a ten-fold reduction in resumption time by performing experiments using commercial software.
IBM Corp. eBooksIbm websphere v5.0 performance, scalability, and high availability websphere handbook series
5 Citations2003Birgit Roehm, Narayanan Alavandar +9 more
This book provides step-by-step instructions for implementing a sample multiple-machine environment and uses this environment to illustrate most of IBM WebSphere Application Server Network Deployment V5.0 workload management and scalability features.