Move my data to the cloud: an online cost-minimizing approach

Abstract

Cloud computing has rapidly emerged as a new computation paradigm, providing agile and scalable resource access in a utility-like fashion. Processing of massive amounts of data has been a primary usage of the clouds in practice. While many efforts have been devoted to designing the computation models (e.g., MapReduce), one important issue has been largely neglected in this respect: how do we efficiently move the data, practically generated from different geographical locations over time, into a cloud for effective processing? The usual approach of shipping data using hard disks lacks flexibility and security. As the first dedicated effort, this paper tackles this massive, dynamic data migration issue. Targeting a cloud encompassing disparate data centers of different resource charges, we model the cost-minimizing data migration problem, and propose efficient offline and online algorithms, which optimize the routes of data into the cloud and the choice of the data center to aggregate the data for processing, at any give time. Three online algorithms are proposed to practically guide data migration over time. With no need of any future information on the data generation pattern, an online lazy migration (OLM) algorithm achieves a competitive ratio as low as 2:55 under typical system settings, and a work function algorithm (WFA) has a linear 2K-1 (K is the number of data centers) competitive ratio. The rest one randomized fixed horizon control algorithm (RFHC) achieves 1+ 1/(l+1 ) κ/λ competitive ratio in theory with a lookahead window of l into the future, where κ and λ are protocol parameters. We conduct extensive experiments to evaluate our online algorithms, using real-world meteorological data generation traces, under realistic cloud settings. Comparisons among online and offline algorithms show a close-to-offline-optimum performance and demonstrate the effectiveness of our online algorithms in practice.