Data Placement and Replica Selection for Improving Co-location in Distributed Environments

Increasing need for large-scale data analytics in a number of ap-plication domains has led to a dramatic rise in the number of dis-tributed data management systems, both parallel relational databases, and systems that support alternative frameworks like MapReduce. There is thus an increasing contention on scarce data center re-sources like network bandwidth (especially cross-rack bandwidth); further, the energy requirements for powering the computing equip-ment are also growing dramatically. As we show empirically, in-creasing the execution parallelism by spreading out data across a large number of machines may achieve the intended goal of de-creasing query latencies, but in most cases, may increase the total resource and energy consumption significantly. For many analyt-ical workloads, however, minimizing query latencies is often not critical; in such scenarios, we argue that we should instead focus on minimizing the average query span, i.e., the average number of machines that are involved in processing of a query, through co-location of data items that are frequently accessed together. In this work, we exploit the fact that most distributed environments need to use replication for fault tolerance, and we devise workload-driven replica selection and placement algorithms that attempt to mini-mize the average query span. We model a historical query work-load trace as a hypergraph over a set of data items (which could be relation partitions, or file chunks), and formulate and analyze the problem of replica placement by drawing connections to several well-studied graph theoretic concepts. We use these connections to develop a series of algorithms to decide which data items to repli-cate, and where to place the replicas. We show effectiveness of our proposed approach by building a trace-driven simulation frame-work and by presenting results on a collection of synthetic and real workloads. Our experiments show that careful data placement and replication can dramatically reduce the average query spans result-ing in significant reductions in the resource consumption. 1