Optimizing data aggregation for cluster-based internet services
Lingkun Chu, Hong Tang, Tao Yang et al. · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · 2003
Large-scale cluster-based Internet services often host partitioned datasets to provide incremental scalability. The aggregation of results produced from multiple partitions is a fundamental building block for the delivery of these services. This paper presents the design and implementation of a programming primitive -- Data Aggregation Call (DAC) -- to exploit partition parallelism for cluster-based Internet services. A DAC request specifies a local processing operator and a global reduction operator, and it aggregates the local processing results from participating nodes through the global reduction operator. Applications may allow a DAC request to return partial aggregation results as a tradeoff between quality and availability. Our architecture design aims at improving interactive responses with sustained throughput for typical cluster environments where platform heterogeneity and software/hardware failures are common. At the cluster level, our load-adaptive reduction tree construction algorithm balances processing and aggregation load across servers while exploiting partition parallelism. Inside each node, we employ an event-driven thread pool design that prevents slow nodes from adversely affecting system throughput under highly concurrent workload. We further devise a staged timeout scheme that eagerly prunes slow or unresponsive servers from the reduction tree to meet soft deadlines. We have used the DAC primitive to implement several applications: a search engine document retriever, a parallel protein sequence matcher, and an online parallel facial recognizer. Our experimental and simulation results validate the effectiveness of the proposed optimization techniques for reducing response time, improving throughput, and gracefully handling server unresponsiveness. We also demonstrate the ease-of use of the DAC primitive and the scalability of our architecture design.
Cited by 23 works. doi:10.1145/781498.781517
Authors
References
- Basic Local Alignment Search Tool
- Eigenfaces for Recognition
- TAG
- A high-performance, portable implementation of the MPI message passing interface standard
- Cluster-based scalable network services
- MPI: The Complete Reference
- SEDA
- Locality-aware request distribution in cluster-based network servers
- Flash: an efficient and portable web server
- Locality-aware request distribution in cluster-based network servers