Replica placement for high availability in distributed stream processing systems

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: Atul Adya , William J. Bolosky , Miguel Castro , Gerald Cermak , Ronnie Chaiken , John R. Douceur , Jon Howell , Jacob R. Lorch , Marvin Theimer , Roger P. Wattenhofer, Farsite: federated, available, and reliable storage for an incompletely trusted environment, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060291]
• 3: Yanif Ahmad , Uğur Çetintemel, Network-aware query processing for stream-based applications, Proceedings of the Thirtieth international conference on Very large data bases, p.456-467, August 31-September 03, 2004, Toronto, Canada
• 4: Amitanand S. Aiyer , Lorenzo Alvisi , Allen Clement , Mike Dahlin , Jean-Philippe Martin , Carl Porth, BAR fault tolerance for cooperative services, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 5: Magdalena Balazinska , Hari Balakrishnan , Samuel Madden , Michael Stonebraker, Fault-tolerance in the Borealis distributed stream processing system, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066160]
• 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: Andy Bavier , Mic Bowman , Brent Chun , David Culler , Scott Karlin , Steve Muir , Larry Peterson , Timothy Roscoe , Tammo Spalink , Mike Wawrzoniak, Operating system support for planetary-scale network services, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.19-19, March 29-31, 2004, San Francisco, California
• 8: Kenneth P. Birman, The process group approach to reliable distributed computing, Communications of the ACM, v.36 n.12, p.37-53, Dec. 1993 [doi>10.1145/163298.163303]
• 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.
• 11: P. Felber , B. Garbinato , R. Guerraoui, The design of a CORBA group communication service, Proceedings of the 15th Symposium on Reliable Distributed Systems (SRDS '96), p.150, October 23-25, 1996
• 12: Pascal Felber , Priya Narasimhan, Experiences, Strategies, and Challenges in Building Fault-Tolerant CORBA Systems, IEEE Transactions on Computers, v.53 n.5, p.497-511, May 2004 [doi>10.1109/TC.2004.1275293]
• 13: Svend Frølund , Rachid Guerraoui, e-Transactions: End-to-End Reliability for Three-Tier Architectures, IEEE Transactions on Software Engineering, v.28 n.4, p.378-395, April 2002 [doi>10.1109/TSE.2002.995430]
• 14: Aniruddha S. Gokhale , Balachandran Natarajan , Douglas C. Schmidt , Joseph K. Cross, Towards Real-Time Fault-Tolerant CORBA Middleware, Cluster Computing, v.7 n.4, p.331-346, October 2004 [doi>10.1023/B:CLUS.0000039493.73008.13]
• 15: Jeong-Hyon Hwang , Magdalena Balazinska , Alexander Rasin , Ugur Cetintemel , Michael Stonebraker , Stan Zdonik, High-Availability Algorithms for Distributed Stream Processing, Proceedings of the 21st International Conference on Data Engineering, p.779-790, April 05-08, 2005 [doi>10.1109/ICDE.2005.72]
• 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: Anne-Marie Kermarrec , Christine Morin, Smooth and Efficient Integration of High-Availability in a Parallel Single Level Store System, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.752-763, August 28-31, 2001
• 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.
• 19: Peter Michael Melliar-Smith , Louise Elizabeth Moser, Surviving Network Partitioning, Computer, v.31 n.3, p.62-68, March 1998 [doi>10.1109/2.660191]
• 20: Michael G. Merideth , Arun Iyengar , Thomas Mikalsen , Stefan Tai , Isabelle Rouvellou , Priya Narasimhan, Thema: Byzantine-Fault-Tolerant Middleware forWeb-Service Applications, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.131-142, October 26-28, 2005 [doi>10.1109/RELDIS.2005.28]
• 21: Object Management Group. Fault tolerant CORBA. OMG Technical Committee Document formal / 02-06-59, Chapter 23, CORBA/IIOP 3.0.3, 2004.
• 22: Marta Patiño-Martinez , Ricardo Jiménez-Peris , Bettina Kemme , Gustavo Alonso, MIDDLE-R: Consistent database replication at the middleware level, ACM Transactions on Computer Systems (TOCS), v.23 n.4, p.375-423, November 2005 [doi>10.1145/1113574.1113576]
• 23: Peter Pietzuch , Jonathan Ledlie , Jeffrey Shneidman , Mema Roussopoulos , Matt Welsh , Margo Seltzer, Network-Aware Operator Placement for Stream-Processing Systems, Proceedings of the 22nd International Conference on Data Engineering, p.49, April 03-07, 2006 [doi>10.1109/ICDE.2006.105]
• 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.
• 25: Yansong (Jennifer) Ren , David E. Bakken , Tod Courtney , Michel Cukier , David A. Karr , Paul Rubel , Chetan Sabnis , William H. Sanders , Richard E. Schantz , Mouna Seri, AQuA: An Adaptive Architecture that Provides Dependable Distributed Objects, IEEE Transactions on Computers, v.52 n.1, p.31-50, January 2003 [doi>10.1109/TC.2003.1159752]
• 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.
• 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: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 30: F. Schintke and A. Reinefeld. Modeling replica availability in large data grids. Grid Computing, 1(2):219--227, June 2003.
• 31: Fred B. Schneider, Implementing fault-tolerant services using the state machine approach: a tutorial, ACM Computing Surveys (CSUR), v.22 n.4, p.299-319, Dec. 1990 [doi>10.1145/98163.98167]
• 32: Mehul A. Shah , Joseph M. Hellerstein , Eric Brewer, Highly available, fault-tolerant, parallel dataflows, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007662]
• 33: Kelvin C. W. So , Emin Gün Sirer, Latency and bandwidth-minimizing failure detectors, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 34: M. Wiesmann , F. Pedone , A. Schiper , B. Kemme , G. Alonso, Understanding Replication in Databases and Distributed Systems, Proceedings of the The 20th International Conference on Distributed Computing Systems ( ICDCS 2000), p.464, April 10-13, 2000
• 35: Bernard Wong , Aleksandrs Slivkins , Emin Gün Sirer, Meridian: a lightweight network location service without virtual coordinates, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 36: Huaigu Wu , Bettina Kemme, Fault-tolerance for Stateful Application Servers in the Presence of Advanced Transactions Patterns, Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, p.95-108, October 26-28, 2005 [doi>10.1109/RELDIS.2005.18]
• 37: Kun-Lung Wu , Kirsten W. Hildrum , Wei Fan , Philip S. Yu , Charu C. Aggarwal , David A. George , Buǧra Gedik , Eric Bouillet , Xiaohui Gu , Gang Luo , Haixun Wang, Challenges and experience in prototyping a multi-modal stream analytic and monitoring application on System S, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 38: Haifeng Yu , Phillip B. Gibbons, Optimal inter-object correlation when replicating for availability, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281137]
• 39: Haifeng Yu , Phillip B. Gibbons , Suman Nath, Availability of multi-object operations, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.16-16, May 08-10, 2006, San Jose, CA

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Design, Experimentation, Reliability

Keywords:
distributed stream processing, high availability, replica placement