2013/02/18 by K. Ashwin Kumar, Kumar, K. Ashwin, Amol Deshpande +3 · 1 citation
Computer Science · #Analytics #Caching and Content Delivery #Cloud Computing and Resource Management #Computer science #Data mining #Database design #Databases (cs.DB) #Distributed #Distributed computing #Distributed systems and fault tolerance #Exploit #FOS: Computer and information sciences #Information retrieval #Materialized view #Online aggregation #Parallel #Query optimization #Replica #Replication (statistics) #Sargable #Search engine #View #Web search query #Workload #and Cluster Computing (cs.DC) #cs.DB #cs.DC
paper · pdf · doi:10.48550/arxiv.1302.4168
published in arXiv (Cornell University) (Cornell University) · 12 pages, 22 figures
arxiv created 2013/02/18 · openalex publication_date 2013/02/18 · arxiv updated 2013/02/19 · openalex created_date 2022/10/06 · openalex updated_date 2026/07/28
Increasing need for large-scale data analytics in a number of application\ndomains has led to a dramatic rise in the number of distributed data management\nsystems, both parallel relational databases, and systems that support\nalternative frameworks like MapReduce. There is thus an increasing contention\non scarce data center resources like network bandwidth; further, the energy\nrequirements for powering the computing equipment are also growing\ndramatically. As we show empirically, increasing the execution parallelism by\nspreading out data across a large number of machines may achieve the intended\ngoal of decreasing query latencies, but in most cases, may increase the total\nresource and energy consumption significantly. For many analytical workloads,\nhowever, minimizing query latencies is often not critical; in such scenarios,\nwe argue that we should instead focus on minimizing the average query span,\ni.e., the average number of machines that are involved in processing of a\nquery, through colocation of data items that are frequently accessed together.\nIn this work, we exploit the fact that most distributed environments need to\nuse replication for fault tolerance, and we devise workload-driven replica\nselection and placement algorithms that attempt to minimize the average query\nspan. We model a historical query workload trace as a hypergraph over a set of\ndata items, and formulate and analyze the problem of replica placement by\ndrawing connections to several well-studied graph theoretic concepts. We\ndevelop a series of algorithms to decide which data items to replicate, and\nwhere to place the replicas. We show effectiveness of our proposed approach by\npresenting results on a collection of synthetic and real workloads. Our\nexperiments show that careful data placement and replication can dramatically\nreduce the average query spans resulting in significant reductions in the\nresource consumption.\n