An on-line replication strategy to increase availability in Data Grids

Abstract

Data is typically replicated in a Data Grid to improve the job response time and data availability. Strategies for data replication in a Data Grid have previously been proposed, but they typically assume unlimited storage for replicas. In this paper, we address the system-wide data availability problem assuming limited replica storage. We describe two new metrics to evaluate the reliability of the system, and propose an on-line optimizer algorithm that can Minimize the Data Missing Rate (MinDmr) in order to maximize the data availability. Based on MinDmr, we develop four optimizers associated with four different file access prediction functions. Simulation results utilizing the OptorSim show our MinDmr strategies achieve better performance overall than other strategies in terms of the goal of data availability using the two new metrics.

Introduction

The popularity of data-intensive scientific applications, in which millions of files are generated from scientific experiments and thousands of users world-wide access this data, has resulted in the emergence of Grid computing. In a Grid system, the resources of many computers, spanning geographic locations and organizations, are utilized to solve large-scale problems. These geographically distributed systems with loosely coupled jobs can require the management of an extremely large number of data sets. A Grid computing system for processing and managing this very large amount of distributed data is a Data Grid. Examples of Data Grids are the Biomedical Informatics Research Network (BIRN) [22], the Large Hadron Collider (LHC) [23] at the particle physics center CERN, the DataGrid project (EDG) [21] funded by the European Union, now known as the Enabling Grids for E-SciencE project (EGEE) [5], the International Virtual Observatory Alliance (IVOA) Grid community Research Group [24] and physics Data Grids [6], [12]. Data Grids require users to share both data and resources, and the management of such a large volume of data sets has posed a challenging problem in how to make the data more approachable and available to the users.

A common solution to improve availability and file access time in a Data Grid is to replicate the data. When data is replicated, copies of data files are created at many different sites in the Data Grid [3]. Deciding on where and when to make the data copies in the distributed nodes is a problem common to all data replication schemes for Data Grids. Earlier research on data replication [2], [4], [8], [11], [14], [16] focused on decreasing the data access latency and the network bandwidth assumption. As bandwidth and computing capacity have become relatively cheaper, the data access latency can drop dramatically, and how to improve the data availability and system reliability becomes the new focus.

The dynamic behavior of a Grid user, in combination with the large volume of datasets, makes it difficult to make decisions concerning data replication to meet the system availability goal [15]. In a Data Grid system, there are hundreds of clients across the globe who will submit their job requests, each of which will access multiple files to do some type of analysis. In data-intensive applications, when a job accesses a massive-size file, the unavailability of that file can cause the whole job to hang and the potential delay of the job can be unbounded. In large-scale data-intensive systems, hundreds of nodes will be involved and any node failure or network outage can cause potential file unavailability. As a result, there has been an increase in research focusing on how to maximize the file availability. Data replication strategies to improve the data availability have been proposed in [13], [15], but have assumed unlimited storage for replicas.

In this paper, we address the system-wide data availability problem assuming limited replica storage. We present two new data availability metrics, the System File Missing Rate and the System Bytes Missing Rate. (We are not aware of any other research at this time that utilizes any system data availability metrics.) We then model the problem in terms of an optimal solution in a static system. More importantly, for on-line processing of file replication, we propose a novel heuristic algorithm that maximizes the data availability by Minimizing the Data Missing Rate (MinDmr) for limited storage resources without sacrificing the data access latency. Based on MinDmr, we present four optimizers that are associated with four different prediction functions. Our test results on the popular OptorSim [9] show that our four MinDmr replica schemes perform better overall than the Binomial economical replica scheme, Zipf economical replica scheme [2], [4], LFU and LRU for the two metrics.

The rest of the paper is organized as follows. We describe related work in Grid systems in Section 2. Section 3 presents the two measures (the System File Missing Rate and the System Bytes Missing Rate), and discusses the system model. We present our analytical model and the dynamic replica algorithm in Section 4. In Section 5, we describe our simulation results based on the OptorSim, a simulator designed by the European Data Grid Project [5]. In the final section, we conclude our paper and describe future work.