A Framework of Hypergraph-Based Data Placement Among Geo-Distributed Datacenters

摘要

Data-intensive applications need to address the problem of properly placing the set of data items in geo-distributed storage nodes. Traditional techniques use the hashing method to achieve the load balance among nodes such as those used in Hadoop and Cassandra, but are not efficient for the requests reading multiple data items in one transaction, especially when the source locations of requests are also distributed. Some recent papers proposed the managed data placement schemes for online social networks, but have a limited scope of applications due to their focuses. We propose a general hypergraph-based data placement framework, which considers both the performance metrics related to the co-location of associated data and those related to the exact location of fulfilling each requested data item. In the framework, we present the methods to convert the optimization objectives into hypergraph models and employ a hypergraph partitioning to efficiently partition the set of data items and place them in distributed nodes. Further, we extend the scheme into replica placement where we need to find multiple locations to place the replicas of the same data item. Through extensive experiments based on trace-based datasets, we evaluate the performance of the proposed framework and demonstrate its effectiveness.