Highly available, fault-tolerant, parallel dataflows

ABSTRACT

We present a technique that masks failures in a cluster to provide high availability and fault-tolerance for long-running, parallelized dataflows. We can use these dataflows to implement a variety of continuous query (CQ) applications that require high-throughput, 24x7 operation. Examples include network monitoring, phone call processing, click-stream processing, and online financial analysis. Our main contribution is a scheme that carefully integrates traditional query processing techniques for partitioned parallelism with the process-pairs approach for high availability. This delicate integration allows us to tolerate failures of portions of a parallel dataflow without sacrificing result quality. Upon failure, our technique provides quick fail-over, and automatically recovers the lost pieces on the fly. This piecemeal recovery provides minimal disruption to the ongoing dataflow computation and improved reliability as compared to the straight-forward application of the process-pairs technique on a per dataflow basis. Thus, our technique provides the high availability necessary for critical CQ applications. Our techniques are encapsulated in a reusable dataflow operator called Flux, an extension of the Exchange that is used to compose parallel dataflows. Encapsulating the fault-tolerance logic into Flux minimizes modifications to existing operator code and relieves the burden on the operator writer of repeatedly implementing and verifying this critical logic. We present experiments illustrating these features with an implementation of Flux in the TelegraphCQ code base [8].

REFERENCES

• 1: Y. Amir and J. Stanton. The Spread Wide Area Group Communication System. Technical Report CNDS-98-4, Johns Hopkins, 1998.
• 2: Thomas E. Anderson , David E. Culler , David A. Patterson , and the NOW team, A Case for NOW (Networks of Workstations), IEEE Micro, v.15 n.1, p.54-64, February 1995 [doi>10.1109/40.342018]
• 3: J. Baulier, S. Blott, H. Korth, and A. Silberschatz. A Database System for Real-Time Event Aggregation in Telecommunication. 1998.
• 4: Philip A. Bernstein , Meichun Hsu , Bruce Mann, Implementing recoverable requests using queues, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.112-122, May 23-26, 1990, Atlantic City, New Jersey, United States
• 5: Kenneth P. Birman, ISIS: A System for Fault-Tolerant Distributed Computing, Cornell University, Ithaca, NY, 1986
• 6: Kenneth P. Birman , Robert Constable , Mark Hayden , Jason Hickey , Christoph Kreitz , Robbert Van Renesse , Ohad Rodeh , Werner Vogels, The Horus and Ensemble Projects: Accomplishments and Limitations, Cornell University, Ithaca, NY, 1999
• 7: D. Carny et al. Monitoring Streams - A New Class of Data Management Applications. In VLDB, 2002.
• 8: S. Chandrasekaran et al. TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. In CIDR, 2003.
• 9: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 10: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 11: E. Elnozahy, D. Johnson, and Y. Wang. A Survey of Rollback-Recovery Protocols in Message-Passing Systems. Technical Report CMU-CS-96-181, CMU, 1996.
• 12: Seth Gilbert , Nancy Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564601]
• 13: Goetz Graefe, Encapsulation of parallelism in the Volcano query processing system, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.102-111, May 23-26, 1990, Atlantic City, New Jersey, United States
• 14: G. Graefe. Query Evaluation Techniques for Large Databases. In ACM Computing Surveys, 2002.
• 15: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 16: Hui-I Hsiao , David J. DeWitt, Chained Declustering: A New Availability Strategy for Multiprocessor Database Machines, Proceedings of the Sixth International Conference on Data Engineering, p.456-465, February 05-09, 1990
• 17: S. Hvasshovd et al. The ClustRa Telecom Database. In VLDB, 1995.
• 18: J. Hwang et al. A Comparison of Stream-Oriented High-Availability Algorithms. Technical Report CS-03--17, Brown, 2003.
• 19: B. Kemme and G. Alonso. Don't Be Lazy, Be Consistent. In VLDB, 2000.
• 20: Christopher Kruegel , Fredrik Valeur , Giovanni Vigna , Richard Kemmerer, Stateful Intrusion Detection for High-Speed Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.285, May 12-15, 2002
• 21: L. Lamport. The Implementation of Reliable Distributed Multiprocess Systems. Computer Networks, 1978.
• 22: Butler Lampson, The ABCD's of Paxos, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.13, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.383969]
• 23: Roger Barga , David Lomet, Phoenix project: fault-tolerant applications, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565139]
• 24: S. Madden and M. Franklin. Fjording the Stream: An Architecture for Queries over Streaming Sensor Data. In ICDE, 2002.
• 25: Manish Mehta , David J. DeWitt, Managing Intra-operator Parallelism in Parallel Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.382-394, September 11-15, 1995
• 26: R. Motwani et al. Query Processing, Approximation, and Resource Management in a Data Stream Management System. In CIDR, 2003.
• 27: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7]
• 28: Fred B. Schneider, Byzantine generals in action: implementing fail-stop processors, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.145-154, May 1984 [doi>10.1145/190.357399]
• 29: 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]
• 30: M. Shah, J. Hellerstein, S. Chandrasekaran, and M. Franklin. Flux: An Adaptive Partitioning Operator for Continuous Query Systems. In ICDE, 2003.
• 31: T. Urhan and M. Franklin. XJoin: A Reactively-Scheduled Pipelined Join Operator. IEEE Data Engineering Bulletin, June 2000.
• 32: Giovanni Vigna , William Robertson , Vishal Kher , Richard A. Kemmerer, A Stateful Intrusion Detection System for World-Wide Web Servers, Proceedings of the 19th Annual Computer Security Applications Conference, p.34, December 08-12, 2003
• 33: W. Vogels , D. Dumitriu , K. Birman , R. Gamache , M. Massa , R. Short , J. Vert , J. Barrera , J. Gray, The Design and Architecture of the Microsoft Cluster Service - A Practical Approach to High-Availability and Scalability, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.422, June 23-25, 1998