research-article

Replica placement for high availability in distributed stream processing systems

Authors:

Thomas Repantis,

Vana KalogerakiAuthors Info & Claims

DEBS '08: Proceedings of the second international conference on Distributed event-based systems

Pages 181 - 192

https://doi.org/10.1145/1385989.1386012

Published: 01 July 2008 Publication History

Abstract

A significant number of emerging on-line data analysis applications require the processing of data streams, large amounts of data that get updated continuously, to generate outputs of interest or to identify meaningful events. Example domains include network traffic management, stock price monitoring, customized e-commerce websites, and analysis of sensor data. In this paper we look at the problem of high availability in such a distributed stream processing system. By taking into account the particular characteristics of stream processing applications we first identify design principles for a replica placement algorithm for high availability. We incorporate these principles in a decentralized replica placement protocol that aims to maximize availability, while respecting resource constraints, and making performance-aware placement decisions. We have integrated our replica placement protocol in Synergy, our distributed stream processing middleware. Our experimental comparison over PlanetLab with the current state of the art corroborates our claims that our techniques maximize availability while sustaining good performance.

References

[1]

D. Abadi et al. The design of the Borealis stream processing engine. In Proceedings of 2nd Biennial Conference on Innovative Data Systems Research, CIDR, Asilomar, CA, USA, January 2005.]]

[2]

A. Adya et al. FARSITE: Federated, available, and reliable storage for an incompletely trusted environment. In Proceedings of 5th Symposium on Operating Systems Design and Implementation, OSDI, Boston, December 2002.]]

Digital Library

[3]

Y. Ahmad and U. Çetintemel. Network-aware query processing for stream-based applications. In Proceedings of 30th International Conference on Very Large Data Bases, VLDB, Toronto, Canada, August 2004.]]

Digital Library

[4]

A. Aiyer, L. Alvisi, A. Clement, M. Dahlin, J. Martin, and C. Porth. BAR fault tolerance for cooperative services. In Proceedings of 20th Symposium on Operating Systems Principles, SOSP, Brighton, UK, October 2005.]]

Digital Library

[5]

M. Balazinska, H. Balakrishnan, S. Madden, and M. Stonebraker. Fault-tolerance in the Borealis distributed stream processing system. In Proceedings of ACM SIGMOD, Baltimore, MD, USA, June 2005.]]

Digital Library

[6]

A. Bartoli, R. Jimenez-Peris, B. Kemme, C. Pautasso, S. Patarin, S. Wheater, and S. Woodman. The ADAPT framework for adaptable and composable web services. IEEE Distributed Systems On Line, September 2005.]]

[7]

A. Bavier et al. Operating systems support for planetary-scale network services. In Proceedings of 1st Symposium on Networked Systems Design and Implementation, NSDI, San Francisco, USA, March 2004.]]

Digital Library

[8]

K. Birman. The process group approach to reliable distributed computing. Communications of the ACM, 36(12):37--53, December 1993.]]

Digital Library

[9]

N. Budhlraja, K. Marzullo, F. B. Schneider, and S. Toueg. Primary-Backup protocols: Lower bounds and optimal implementations. In Cornell University Technical Report TR-92-1265, January 1992.]]

[10]

Z. Cai, V. Kumar, B. Cooper, G. Eisenhauer, K. Schwan, and R. Strom. Utility-driven proactive management of availability in enterprise-scale information flows. In Proceedings of 7th Middleware, Melbourne, November 2006.]]

Digital Library

[11]

P. Felber, B. Garbinato, and R. Guerraoui. The design of a CORBA group communication service. In Proceedings of 15th Symposium on Reliable Distributed Systems, SRDS, Ontario, Canada, October 1996.]]

Digital Library

[12]

P. Felber and P. Narasimhan. Experiences, approaches and challenges in building fault-tolerant CORBA systems. IEEE Transactions on Computers, 54(5):497--511, May 2004.]]

Digital Library

[13]

S. Frølund and R. Guerraoui. e-Transactions: End-to-end reliability for three-tier architectures. IEEE Transactions on Software Engineering, 28(4):378--395, April 2002.]]

Digital Library

[14]

A. Gokhale, B. Natarajan, D. C. Schmidt, and J. Cross. Towards real-time fault-tolerant CORBA middleware. Cluster Computing, 7(4):331--346, October 2004.]]

Digital Library

[15]

J. Hwang, M. Balazinska, A. Rasin, U. Çetintemel, M. Stonebraker, and S. Zdonik. High-availability algorithms for distributed stream processing. In Proceedings of 21st International Conference on Data Engineering, ICDE, Tokyo, Japan, April 2005.]]

Digital Library

[16]

J. Hwang, Y. Xing, U. Çetintemel, and S. Zdonik. A cooperative, self-configuring high-availability solution for stream processing. In Proceedings of 23rd International Conference on Data Engineering, ICDE, Istanbul, Turkey, April 2007.]]

[17]

A. Kermarrec and C. Morin. Smooth and efficient integration of high-availability in a parallel single level store system. In Proceedings of Euro-Par, August 2001.]]

Digital Library

[18]

S. Krishnamurthy, W. Sanders, and M. Cukier. An adaptive quality of service aware middleware for replicated services. IEEE Transactions on Parallel and Distributed Systems, 14(11):1112--1125, November 2003.]]

Digital Library

[19]

P. Melliar-Smith and L. Moser. Surviving network partitioning. IEEE Computer, 31(3):62--68, March 1998.]]

Digital Library

[20]

M. G. Merideth, A. Iyengar, T. A. Mikalsen, S. Tai, I. Rouvellou, and P. Narasimhan. Thema: Byzantine-fault-tolerant middleware for web-service applications. In Proceedings of 24th Symposium on Reliable Distributed Systems, SRDS, Orlando, FL, October 2005.]]

Digital Library

[21]

Object Management Group. Fault tolerant CORBA. OMG Technical Committee Document formal / 02-06-59, Chapter 23, CORBA/IIOP 3.0.3, 2004.]]

[22]

M. Patino-Martinez, R. Jimenez-Peris, B. Kemme, and G. Alonso. Consistent database replication at the middleware level. ACM Transactions on Computers, 23(4):1--49, 2005.]]

Digital Library

[23]

P. Pietzuch, J. Ledlie, J. Shneidman, M. Roussopoulos, M. Welsh, and M. Seltzer. Network-aware operator placement for stream-processing systems. In Proceedings of 22nd International Conference on Data Engineering, ICDE, Atlanta, GA, USA, April 2006.]]

Digital Library

[24]

C. Plattner, G. Alonso, and M. T. Özsu. DBFarm: A scalable cluster for multiple databases. In Proceedings of 7th Middleware, Melbourne, Australia, November 2006.]]

Digital Library

[25]

Y. Ren, D. Bakken, T. Courtney, M. Cukier, D. Karr, P. Rubel, C. Sabnis, W. Sanders, R. Schantz, and M. Seri. AQuA: An adaptive architecture that provides dependable distributed objects. IEEE Transactions on Computers, 52(1):31--50, January 2003.]]

Digital Library

[26]

T. Repantis, X. Gu, and V. Kalogeraki. Synergy: Sharing-aware component composition for distributed stream processing systems. In Proceedings of 7th Middleware, Melbourne, Australia, November 2006.]]

Digital Library

[27]

T. Repantis and V. Kalogeraki. Alleviating hot-spots in peer-to-peer stream processing environments. In Proceedings of 5th International Workshop on Databases, Information Systems and Peer-to-Peer Computing, DBISP2P, Vienna, Austria, September 2007.]]

[28]

T. Repantis and V. Kalogeraki. Hot-spot prediction and alleviation in distributed stream processing applications. In Proceedings of 38th International Conference on Dependable Systems and Networks, DSN, Anchorage, AK, USA, June 2008.]]

[29]

A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proceedings of 1st Middleware, Heidelberg, Germany, November 2001.]]

Digital Library

[30]

F. Schintke and A. Reinefeld. Modeling replica availability in large data grids. Grid Computing, 1(2):219--227, June 2003.]]

[31]

F. Schneider. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys, 22(4):299--319, December 1990.]]

Digital Library

[32]

M. Shah, J. Hellerstein, and E. Brewer. Highly available, fault-tolerant, parallel dataflows. In Proceedings of ACM SIGMOD, Paris, France, June 2004.]]

Digital Library

[33]

K. C. W. So and E. G. Sirer. Latency and bandwidth-minimizing failure detectors. In Proceedings of 2nd EuroSys Conference, Lisboa, Portugal, March 2007.]]

Digital Library

[34]

M. Wiesmann, F. Pedone, A. Schiper, B. Kemme, and G. Alonso. Understanding replication in databases and distributed systems. In Proceedings of 20th IEEE International Conference on Distributed Computing Systems, ICDCS, Taipei, Taiwan, April 2000.]]

Digital Library

[35]

B. Wong, A. Slivkins, and E. Sirer. Meridian: A lightweight network location service without virtual coordinates. In Proceedings of ACM SIGCOMM, Philadelphia, PA, USA, August 2005.]]

Digital Library

[36]

H. Wu and B. Kemme. Fault-tolerance for stateful application servers in the presence of advanced transaction patterns. In Proceedings of 24th Symposium on Reliable Distributed Systems, SRDS, Orlando, FL, October 2005.]]

Digital Library

[37]

K.-L. Wu et al. Challenges and experience in prototyping a multi-modal stream analytic and monitoring application on system s. In Proceedings of 33rd International Conference on Very Large Data Bases, VLDB, Vienna, September 2007.]]

Digital Library

[38]

H. Yu and P. Gibbons. Optimal inter-object correlation when replicating for availability. In Proceedings of 26th Symposium on Principles of Distributed Computing, PODC, Portland, OR, USA, August 2007.]]

Digital Library

[39]

H. Yu, P. Gibbons, and S. Nath. Availability of multi-object operations. In Proceedings of 3rd Symposium on Networked Systems Design and Implementation, NSDI, San Jose, CA, USA, May 2006.]]

Digital Library

Cited By

Ding WZhao ZHan Y(2016)An Adaptive Replica Mechanism for Real-Time Stream Processing2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld)10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld.2016.0081(449-455)Online publication date: Jul-2016
https://doi.org/10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld.2016.0081
Ding WZhao ZHan Y(2016)A Framework to Improve the Availability of Stream Computing2016 IEEE International Conference on Web Services (ICWS)10.1109/ICWS.2016.82(594-601)Online publication date: Jun-2016
https://doi.org/10.1109/ICWS.2016.82
Heinze TZia MKrahn RJerzak ZFetzer CEliassen FVitenberg R(2015)An adaptive replication scheme for elastic data stream processing systemsProceedings of the 9th ACM International Conference on Distributed Event-Based Systems10.1145/2675743.2771831(150-161)Online publication date: 24-Jun-2015
https://dl.acm.org/doi/10.1145/2675743.2771831
Show More Cited By

Index Terms

Replica placement for high availability in distributed stream processing systems
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Providing High Availability for Distributed Stream Processing Application with Replica Placement
NBIS '12: Proceedings of the 2012 15th International Conference on Network-Based Information Systems

With the popularity of cloud computing, high volume data needs to be processed in real-time. Therefore, many distributed stream processing systems have risen to deal with this requirement. One kind of distributed stream processing applications contains ...
Placement of replicated tasks for distributed stream processing systems
DEBS '10: Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems

We propose an algorithm for placing tasks of data flows for streaming systems onto servers within a message-oriented middleware where certain tasks can be replicated. Our work is centered on the idea that certain transformations are stateless and can ...
A New Replica Creation and Placement Algorithm for Data Grid Environment
DSDE '10: Proceedings of the 2010 International Conference on Data Storage and Data Engineering

Grid computing is emerging as a key enabling infrastructure for a wide range of disciplines in Science and Engineering. Data grids provide distributed resources for dealing with large scale applications that generate huge volume of data sets. Data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

DEBS '08: Proceedings of the second international conference on Distributed event-based systems

July 2008

377 pages

ISBN:9781605580906

DOI:10.1145/1385989

General Chair:
Roberto Baldoni
Sapienza Universitá di Roma, Italy

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

IEEE
USENIX Assoc: USENIX Assoc
IFIP: International Federation for Information Processing

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DEBS '08

Sponsor:

USENIX Assoc
IFIP

DEBS '08: Distributed Event-based Systems Conference

July 1 - 4, 2008

Rome, Italy

Acceptance Rates

Overall Acceptance Rate 145 of 583 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
823
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ding WZhao ZHan Y(2016)An Adaptive Replica Mechanism for Real-Time Stream Processing2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld)10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld.2016.0081(449-455)Online publication date: Jul-2016
https://doi.org/10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld.2016.0081
Ding WZhao ZHan Y(2016)A Framework to Improve the Availability of Stream Computing2016 IEEE International Conference on Web Services (ICWS)10.1109/ICWS.2016.82(594-601)Online publication date: Jun-2016
https://doi.org/10.1109/ICWS.2016.82
Heinze TZia MKrahn RJerzak ZFetzer CEliassen FVitenberg R(2015)An adaptive replication scheme for elastic data stream processing systemsProceedings of the 9th ACM International Conference on Distributed Event-Based Systems10.1145/2675743.2771831(150-161)Online publication date: 24-Jun-2015
https://dl.acm.org/doi/10.1145/2675743.2771831
Ding WHan YWang JZhao Z(2014)Feature-based high-availability mechanism for quantile tasks in real-time data stream processingSoftware—Practice & Experience10.1002/spe.224444:7(855-871)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1002/spe.2244
He RLuan ZHuang YCheng ZQian DGuan G(2012)Providing High Availability for Distributed Stream Processing Application with Replica PlacementProceedings of the 2012 15th International Conference on Network-Based Information Systems10.1109/NBiS.2012.103(685-690)Online publication date: 26-Sep-2012
https://dl.acm.org/doi/10.1109/NBiS.2012.103
Ding WHan YZhao ZWang J(2012)Stream-oriented Availability Services for Endpoint-to-endpoint Data TransmissionProceedings of the 2012 International Conference on Cloud and Service Computing10.1109/CSC.2012.40(212-218)Online publication date: 22-Nov-2012
https://dl.acm.org/doi/10.1109/CSC.2012.40
Lakshmanan GLi YStrom RPietzuch PBacon JSventek JCetintemel U(2010)Placement of replicated tasks for distributed stream processing systemsProceedings of the Fourth ACM International Conference on Distributed Event-Based Systems10.1145/1827418.1827450(128-139)Online publication date: 12-Jul-2010
https://dl.acm.org/doi/10.1145/1827418.1827450
Aritsugi MNagano K(2010)Recovery processing for high availability stream processing systems in local area networksTENCON 2010 - 2010 IEEE Region 10 Conference10.1109/TENCON.2010.5686443(1036-1041)Online publication date: Nov-2010
https://doi.org/10.1109/TENCON.2010.5686443
Fuyuan Xiao Nagano KItokawa TKitasuka TAritsugi M(2010)A self-recovery technique for highly-available stream processing over local area networksTENCON 2010 - 2010 IEEE Region 10 Conference10.1109/TENCON.2010.5685904(2406-2411)Online publication date: Nov-2010
https://doi.org/10.1109/TENCON.2010.5685904
Repantis TGu XKalogeraki V(2009)QoS-Aware Shared Component Composition for Distributed Stream Processing SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2008.16520:7(968-982)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1109/TPDS.2008.165

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents