Adaptive popularity-driven replica placement in hierarchical data grids

J Supercomput (2010) 51: 374–392 DOI 10.1007/s11227-009-0371-9

Adaptive popularity-driven replica placement in hierarchical data grids Mohammad Shorfuzzaman · Peter Graham · Rasit Eskicioglu

Published online: 23 December 2009 © Springer Science+Business Media, LLC 2009

Abstract Data grids support access to widely distributed storage for large numbers of users accessing potentially many large files. Efficient access is hindered by the high latency of the Internet. To improve access time, replication at nearby sites may be used. Replication also provides high availability, decreased bandwidth use, enhanced fault tolerance, and improved scalability. Resource availability, network latency, and user requests in a grid environment may vary with time. Any replica placement strategy must be able to adapt to such dynamic behavior. In this paper, we describe a new dynamic replica placement algorithm, Popularity Based Replica Placement (PBRP), for hierarchical data grids which is guided by file “popularity”. Our goal is to place replicas close to clients to reduce data access time while still using network and storage resources efficiently. The effectiveness of PBRP depends on the selection of a threshold value related to file popularity. We also present Adaptive-PBRP (APBRP) that determines this threshold dynamically based on data request arrival rates. We evaluate both algorithms using simulation. Results for a range of data access patterns show that our algorithms can shorten job execution time significantly and reduce bandwidth consumption compared to other dynamic replication methods. Keywords Data grids · Replication · Replica placement · Execution time · Bandwidth · Adaptive

M. Shorfuzzaman () · P. Graham · R. Eskicioglu Department of Computer Science, University of Manitoba, Winnipeg, Manitoba, Canada R3T 2N2 e-mail: [email protected] P. Graham e-mail: [email protected] R. Eskicioglu e-mail: [email protected]

Adaptive popularity-driven replica placement in hierarchical data

375

1 Introduction Many scientific applications in areas including high-energy physics and earth sciences involve remote access to large datasets [1, 2, 6, 15]. The distributed analysis of these datasets and/or their dissemination among researchers located over a wide geographical area require special techniques such as grid computing [8] where a widely distributed scientific community can share resources across administrative and organizational boundaries. A good example of this is the experiments being run at the European Center for Nuclear Research (CERN) using the Large Hadron Collider (LHC) [9]. The CMS [7] and ATLAS [17] experiments using the LHC will collect massive amounts of data (many petabytes per annum) and involve thousands of researchers from around the world. A data grid has been designed [7, 18] to efficiently provide access to, and sharing of, the associated data. A data grid focuses on providing users with infrastructure that enables reliable access to and sharing of data across widely distributed locations. A framework for data grids has been proposed by Foster et al. [8]. Simply providing a local copy of data on each site needing the data is cost prohibitive. Also, storing large amounts of data in a centralized manner is impractical due to the slowness of remote data access. Given the high latency of wide-area networks that underlie many grid systems and the need to access or manage multiple petabytes of data in grid environments, data availability and access optimization are key challenges that must be addressed. One way to speed up access in data grid systems is to replicate data at multiple locations, so a user can access the data from a nearby site [19]. Replication not only reduces access time, but also improves data availability. Creating replicas also promotes the routing of client requests to different replicas thereby distributing the load of a single server across the replica servers. The network load is also distributed across multiple network paths thereby decreasing the probability of congestion related performance degradation. Experience from parallel and distributed systems shows that replication offers fast access, high data availability, low bandwidth consumption, increased fault tolerance, and improved scalability. However, replication algorithms used in such systems cannot always be directly applied to data grids for various reasons including high transfer latencies, hierarchical network structures and special data access patterns that are not common in other systems. To maximize the gains from replication, strategic placement of replicas in the system is critical. The replica placement service is that component of a data grid architecture that decides where in the system a file replica should be placed. The overall file replication problem consists of deciding [13]: (1) which files should be replicated; (2) when and how many replicas should be created; and (3) where the replicas be placed in the system. Replication strategies can be classified as static or dynamic [16]. For static replication, after a replica is created, it is stored in the same place until it is deleted. The drawback of static replication is evident—when client access patterns change, the benefit of replication decreases. Dynamic replication takes into consideration changes in the data grid environment and automatically creates new replicas for frequently referenced files or moves the replicas to other sites as needed to improve performance. We propose a popularity-driven dynamic replica placement algorithm for hierarchically structured data grids that are commonly used by many scientific projects.

376

M. Shorfuzzaman et al.

Fig. 1 Example hierarchical data grid

The effectiveness of this algorithm depends on the careful selection of a threshold value that relates to the popularity of files. We also propose an adaptive version of this algorithm that determines the threshold dynamically using such factors as data request arrival rates and available storage capacities at the replica servers. To evaluate the performance of our algorithms, we use the data grid simulator OptorSim [3]. A simulated hierarchical data grid is used that reflects the characteristics of the Compact Muon Spectrometer (CMS) experiment [7] at CERN. Various simulations are carried out with different file access patterns and replica server capacities. We compare our base algorithm to a number of existing replica placement algorithms and then to our adaptive version. In this paper, we assume a hierarchical (multi-tier) data grid model as is common in current data grid systems [5, 9, 12, 13]. To minimize access time and network load, replicas of the data can be created and spread from the root towards leaf nodes in the hierarchy. In such a system, a request goes up the hierarchy and uses the first replica encountered along the path towards the root. For example, Fig. 1 shows a four-tier hierarchical data grid. Assume a user at node k tries to access a file but does not find it locally. Thus, the request goes to the parent node g, where the data is not available either. Finally, the request reaches node c, and is served by the replica there. The rest of this paper is organized as follows. In Sect. 2, research in replica placement in data grid systems is briefly reviewed. We present our new algorithms in Sect. 3.1. Our simulation methods and performance results are presented in Sects. 4 and 5, respectively. Finally, Sect. 6 concludes the paper and suggests some directions for future work.

2 Related work Ranganathan and Foster [12, 13] present and evaluate six different replication strategies for hierarchical data grids: (1) No Replication: only root node holds files; (2) Best Client: replica is created for the client who accesses the file the most; (3) Cascading: a replica is created somewhere on the path from the root node to the best client; (4) Plain Caching: local copies are stored on initial request; (5) Caching plus Cascading: combines plain caching and cascading; (6) Fast Spread: replicas are stored at

Adaptive popularity-driven replica placement in hierarchical data

377

each node on the path from the root to the best client. Results show that the cascading strategy reduces response time by 30% over plain caching when access patterns reflect both temporal and geographical locality. When access patterns reflect some locality, Fast Spread saves significant bandwidth over other strategies. In their model, the network links are not shared and each replica server can only serve one request at a time. In our approach, the network bandwidth is shared and the replica servers support concurrent data requests. Sang-Min Park et al. [11] propose a dynamic replication strategy, called BHR (Bandwidth Hierarchy-based Replication), to reduce data access time in a data grid. BHR benefits from ‘network-level locality’, by accessing replicas located at sites that have the best current bandwidth to the job’s execution site. The BHR strategy thus exploits the network-level locality that occurs naturally in regional (and other) networks. Two dynamic replication mechanisms were proposed by Tang et al. [16] for multitier data grids: Simple Bottom-Up (SBU) and Aggregate Bottom-Up (ABU). The SBU algorithm replicates any file that exceeds a pre-defined access rate threshold as close as possible to the clients. SBU, however, does not consider historical accesses. To address this, ABU was designed which considers the access histories of files used by sibling nodes and aggregates the access records of similar files so that the frequently accessed files are replicated first. This aggregation is repeated until the root is reached. Clients search for files from a leaf to the root (which replicates the needed files at every node). Access latency can be improved significantly with ABU at the cost of significant storage use. Storage utilization and access latency must be traded off. Different data grid users may have different service requirements. Thus, Quality of Service (QoS) can also be an important factor in data grids. Lin et al. [10] address the problem of replica placement in hierarchical data grids given traffic patterns and locality requirements. They consider several important issues. First, the replicas should be distributed across servers so that the workload on each server is balanced. The optimal number of replicas must also be chosen when the maximum workload capacity for each server is known. Lin et al. also consider the issue of service locality. Each user can specify the minimum acceptable distance to the nearest replica server. Wang et al. [20] also study QoS-aware replica placement and provide a heuristic algorithm to determine the necessary locations of replicas to simultaneously improve system performance and satisfy the quality requirements of the users. Their model is not restricted to hierarchical data grids. Their algorithm starts by finding the cover set [14] of every server. It then identifies and deletes super cover sets in the network. Finally, it inserts replicas into the network iteratively until all servers are satisfied. Experimental results indicate that their algorithm efficiently finds near-optimal solutions but it does not consider the workload capacity of replica servers.

3 Our dynamic replication algorithms We now present our new popularity-driven dynamic replica placement strategy, called Popularity Based Replica Placement (PBRP) and its adaptive counterpart AdaptivePBRP (APBRP).

378

M. Shorfuzzaman et al.

3.1 Popularity Based Replica Placement The primary goal of the PBRP algorithm is to improve access time from the client’s perspective by dynamically creating replicas for “popular” files. At the same time, from the perspective of the whole system, efficient use of bandwidth and storage resources must be considered to ensure that the dynamic replication algorithm does not cause heavy load on the system. Our dynamic algorithm aims to balance the space utilization and access latency tradeoff by selectively replicating files among grid sites. Data access patterns commonly change over time, so any dynamic replication strategy must track file accesses over time to decide when, what and where to replicate. The “popularity” of a file is determined by its access rate by the clients and we assume that recently popular files will tend to be accessed more frequently than others in the near future. In PBRP, popular data files are identified by analyzing file access histories. Our replica placement algorithm is invoked at regular intervals and it processes the access histories to determine new replica locations based on file popularity. Old replicas are retained at those replica locations that are common between the new and old replica sets. The rest of the replicas from the old set are deleted and new replicas are created for the remaining new locations. New replica locations are determined after each interval since file popularity varies with time. Our algorithms clear the history logs at the beginning of each time interval to capture access pattern dynamics. The interval chosen is determined by the arrival rate of data accesses so a short interval is chosen for high arrival rates. This incurs greater overhead but adapts more quickly to changing access patterns. Over time, the replica servers will become filled so a replacement strategy is needed. Such a scheme must ensure that popular files are retained and not displaced when new files arrive. We use a popularity-based form of the Least Recently Used (LRU) replacement policy with one constraint added to ensure that replicas created in the current replication interval will not be replaced. This additional constraint is needed to avoid the deletion of newly created replicas by the dynamic replication algorithms. If the available space on a given replica server is less than the size of the new replica, some removable replicas need to be deleted to make room for the new replica. Removable replicas are defined as those replicas that were created before the current replication interval and which are not used by any client at present. Let Rs be the set of all replicas in server s, then the set of removable replicas Rs is: Rs = {r|r ∈ Rs , r is created before the current replication interval, and r is currently unused}. The first condition prevents the deletion of any newly created replicas, and the second condition avoids the interruption of any ongoing data accesses. The idea behind PBRP is to create replicas as close as possible to those clients that frequently request the corresponding files. The file access count as a measure of popularity is, in itself, not new. The novelty with the (PBRP) algorithm is its aim to balance the space utilization and access latency tradeoff by selectively replicating files. All the replication algorithms from the literature except ABU process the records in the access history individually for a client and do not study the relations among these records. In hierarchical data grids, every node accesses replicas only from its ancestor nodes. Thus, the relationship among the access records of the clients that are siblings can be used to determine the effective utilization of various replicas. For example, in

Adaptive popularity-driven replica placement in hierarchical data

379

Fig. 2 Bottom-up aggregation of access counts and top-down placement of replicas

Fig. 2, if the threshold value is set to 5 and no aggregation of access counts is considered, no replica will be created in tier-3. However, due to the aggregation of access counts, four replicas are created in different nodes in tier-3 because their new access counts exceed or become equal to the threshold value. The whole replication process is done in two phases as described below. 3.1.1 Bottom-up access aggregation The bottom-up aggregation phase aggregates access history records for each file to upper tiers, step by step, until the root is reached. The computation simply adds up the access counts for records whose nodes are siblings and which refer to the same files. The result record after aggregation is stored in the parent node. An example of the computation of access counts of a file (F) by different clients is shown in Fig. 2 (client counts shown at leaves). 3.1.2 Top down replica placement Using the aggregated information, replicas are placed from the top to the bottom of the tree. The idea is to traverse down the hierarchy as long as the aggregated access count is greater than or equal to a pre-defined threshold that is used to determine sufficiently popular files. A replica is placed at a node if the threshold prevents further traversal through one or more of its children. An example of replica placement is shown in Fig. 2 where we traverse down the tree from the root to node d through node a since both nodes have access counts greater than the threshold value of 5. From node d further traversal through node i does not occur since its access count is less than the threshold. Hence, a replica is placed on node d. Node j is also traversed through since its access count is 6. A replica is also placed on this node since none of its descendants’ counts exceed the threshold. 3.1.3 The basic algorithm The algorithm for replica placement is shown in Fig. 3. Function getAccessHistory is called to scan the most recent access history covering the last interval. The results are

380

M. Shorfuzzaman et al.

Fig. 3 Algorithms for bottom-up computation of data access counts and placement of replicas in a top-down fashion

stored in recentHistory. In line 2 Bottom-up-compute aggregates the access records in recentHistory for all tiers. The details of function Bottom-up-compute are also shown in Fig. 3. The input parameter recentHistory contains the file access records whose nodeIDs are in the same tier (temp is a buffer with the same structure as recentHistory). The outer for loop (lines 3–13) processes the access records from the tier above the clients to the root. The inner for loop (lines 4–10) aggregates all records in recentHistory. Lines 5–7 try to merge each record r with a record in temp. If there is a record in temp, whose nodeID is the parent of r.nodeID and its fileID is the same as r’s, then record r is merged with the corresponding record in temp by adding corresponding accessCounts. If merging is not possible a new record is added to temp with a nodeID equal to the parent of r.nodeID and fileID and accessCount the same as r’s. In the replica placement algorithm, the for loop (lines 3–12) processes each middle-tier from the tier below the root to the tier above the clients. Function getRecords (line 4) retrieves the aggregated records of the current tier. For each record r in records if the accessCount is greater than or equal to the threshold it is processed in lines 7–8. Function checkChild checks if any of the children of r.nodeID have accessCount less than the threshold or if the children are client nodes. If so, a request is sent to the replica handler to replicate the file at the current node. PBRP improves on ABU by making replicas accessible nearer to clients with lower access counts (which don’t exceed the threshold value). This, in turn, reduces overall data access latency and bandwidth consumption. A bottom-up replica placement is also done in ABU but if the access count of a file at a replica server becomes greater than or equal to the threshold value, a replica is created there and the corresponding access record for that file is deleted. Consider Fig. 2. A replica would be created in node j (with access count 6) using ABU but due to the deletion of this access

Adaptive popularity-driven replica placement in hierarchical data

381

count at node j the aggregated count in d would become 4 which is less than the threshold value and hence no other replica would be created. However, PBRP retains all the aggregated access records and place replicas in a top-down fashion. A replica is placed at a node if the threshold prevents further traversal through one or more of its children. In the example, this creates a replica at node d. 3.2 Adaptive replica placement As described, the effectiveness of PBRP depends on careful selection of the popularity threshold value. Our Adaptive-PBRP (APBRP) algorithm determines the threshold value dynamically using such factors as file request arrival rates and available storage capacities at replica servers. APBRP tries to balance the storage utilization and access latency tradeoff by selectively replicating data files through this dynamic adjustment method. Request access arrival rate and replica server capacities are logical factors to use in modifying the threshold. A high access request arrival rate indicates frequent access requests from the clients which reflects an increased number of popular files whose access counts exceed the threshold. This will, in turn, require creating more replicas which will incur additional replication overhead (in terms of both bandwidth and storage usage). In such a scenario, increasing the threshold will lessen the number of replicas that will be created. On the other hand, if the arrival rate becomes low, the number of popular files will be less which will result in fewer replicas even though the system might be capable (in terms of available bandwidth and storage) of creating more replicas. In this case, decreasing the threshold will increase the number of replicas that are created. Also, the threshold can be decreased to create more replicas if replica servers have sufficient available capacity. Alternatively, the threshold can be increased to decrease the number of replicas if the servers are nearly full with existing replicas. The challenge is to determine how much change (increase or decrease) in the threshold the system should make based on changes in arrival rate or server storage capacities. If we consistently increase the threshold value, at some point the number of replicas will drop drastically which will decrease access performance and storage utilization. On the contrary, if the threshold is decreased consistently, the increased number of replicas will make the system costly to manage. Hence, the threshold must be adjusted so that the space utilization and access latency tradeoff is balanced. 3.3 Determining the initial threshold value The initial threshold value is set based on the average aggregated access counts at the replica servers in the lower tier of the data grid. The value of the average aggregated access count is calculated by dividing the total number of aggregated access counts for a file at the replica servers in the second to the lowest tier of the hierarchy by the number of replica servers at that tier. This is done during the bottom-up aggregation phase of PBRP. The initial value is then adjusted dynamically (described in the next subsection) based on available storage at the replica servers and the request arrival rates.

382

M. Shorfuzzaman et al.

3.4 Dynamic adjustment of the threshold value As mentioned, adjustment of the threshold value is done based on changes in the request arrival rate. However, changes to the threshold are not applied immediately to avoid reacting to transient changes in the arrival rate. Changes are only made to reflect an ongoing trend over an interval of time. The time interval is calculated as a fraction of the length for sampling access histories of clients. The threshold value is increased or decreased by the difference between the current and previous average aggregated access counts of replica servers in the lower tier of the data grid hierarchy. For example, the threshold value for the ith sampling interval, thresholdi , is calculated as follows: Assume, Ri = New average aggregated access rate in the ith interval and Ri−1 = Average aggregated access rate in the (i − 1)st interval thresholdi = thresholdi−1 +  where  is defined as:  0, = Ri − Ri−1 ,

for the first interval of access histories otherwise

(1)

(2)

Once the threshold value is changed, available storage capacities of replica servers are checked. Further adjustment of the threshold value is done based on the available storages of the replica servers. The threshold controller updates the threshold value based on the ratio between the desired percentage of storage usage and the actual percentage of storage usage by replica servers. The new threshold value for the ith interval is thus calculated as: thresholdi (updated) = thresholdi × ratio

(3)

We define three storage utilization states for when the system is lightly, moderately, and highly loaded corresponding to the percentage of storage capacity used by replica servers (less than 50%, 50% to 75%, and greater than 75%, respectively). If the system is heavily loaded or under utilized then the calculated ratio is used in updating the threshold.

4 Simulation setup To evaluate APBRP we used an extended version of OptorSim [4] created to support the necessary information gathering needed for the ABRP algorithm. The simulated data grid topology and network bandwidths between the sites are based on estimates for the CMS experiment and are shown in Fig. 4. All data requests are generated by the nodes in tier-3 and the available network bandwidths between nodes are shown. In our simulations we considered three different storage configurations. Configuration one sets the same replica storage capacity (10 GB) for all nodes in each tier except

Adaptive popularity-driven replica placement in hierarchical data

383

Fig. 4 The simulated data grid topology and different storage configurations

tier-0. Configurations two and three show a hierarchical drop in the size of replica storage from one tier to another. In configuration two, the nodes in tier-1, tier-2, and tier-3 have storage capacities of 10 GB, 5 GB, and 2 GB, respectively. Finally, in configuration three, capacities in tier-1, tier-2, and tier-3 are set to 5 GB, 2 GB, and 2 GB, respectively. The absolute capacities are of little interest but the relative capacities affect placement decisions. Simulated jobs request files in an order determined by a selected access pattern. We used five access patterns: sequential (files are accessed in the order stated in the job configuration file), random (files are accessed using a flat random distribution), unitary random (file requests are one element away from previous file request but the direction is random), Gaussian random walk (files are accessed using a Gaussian distribution), and Zipf distribution (given by Pi = K is , where Pi is the frequency of the ith ranked item, K is the popularity of the most frequently accessed data item and s determines the shape of the distribution). The selected data access patterns (specifically Gaussian and Zipf) reflect the behavior of many scientific applications which adopt Data Grids as their data and computing infrastructure. Moreover, the Gaussian distribution is the most widely used family of distributions in statistics and many statistical tests are based on the assumption of normality. As such, it is a good base measure which can be used for easy informal comparison to known applications. In Zipf, the frequency of a request is the inverse of its rank in the frequency. This means that some file requests will occur frequently while many others will occur rarely. Zipf-like distributions exist widely in the Internet. Further, in a system that is designed to react to file popularity, the Zipf distribution offers a natural testing ground. We ran all the simulations for 150 jobs of various types. The jobs are submitted with a fixed probability such that some jobs are more popular than others. Each job is submitted at 25 millisecond intervals. A resource broker acts as a meta-scheduler that controls job scheduling to different client nodes with computing resources based on the estimated data access cost for the current and all queued jobs. A job requests a set of logical filename(s) for data access. Each file is assumed to be 1 GB. The order in which the files are requested is determined by the selected access pattern.

384

M. Shorfuzzaman et al.

Fig. 5 Job execution times for different replication methods using configuration one

5 Simulation results The performance metrics we chose were job execution time, average bandwidth use, and storage use. Execution time is the total time to execute all jobs. Average bandwidth use is calculated as follows. For each file transmission, the bandwidth cost is the file size multiplied by the sum of costs along the file transmission path. The average bandwidth cost is the total bandwidth cost divided by the number of client requests. Storage use is the percentage of the available storage used by the replicas. We compared our placement algorithm (PBRP) with five other replication algorithms: aggregate bottom-up (ABU), Fast Spread, Cascading, Best Client, and Caching with LRU replacement. To determine the effectiveness of our adaptive technique we also compared APBRP with PBRP considering different replica server configurations as data request rate fluctuates regularly. 5.1 Execution time Figure 5 shows the job execution times for the non-adaptive placement algorithms using storage configuration one. Not surprisingly, Caching’s performance is better than the other algorithms but the Caching strategy requires significant storage capacity at the client sites. As already mentioned, in Caching, the files are only replicated at client nodes. The client stores a local copy of each file upon initial request. Since in this case the clients have substantial storage capacity (same as all middle-tier nodes) for replicating files locally the Caching technique significantly reduces the access time. In a more realistic grid scenario, the client nodes (having both computing and storage resources) which are primarily meant for job execution are likely to have far reduced space for data storage compared to the middle-tier replica servers. For example, the Large Hadron Collider (LHC) [9] project at CERN is expected to produce roughly 15 Petabytes (15 million Gigabytes) of data annually, which thousands of scientists around the world will access. Individual scientists (clients) will access these data through the lowest tier centers, which might consist of local clusters in a University Department having storage capacity far less than the total produced data size. Due to this limited storage capacity of clients, with caching files will get replaced quickly which in turn will increase access time causing an increase in job execution time (as will be shown in Fig. 6). Thus, apart from Caching, PBRP offers the best execution time for all data access patterns. Also, PBRP requires only a small number

Adaptive popularity-driven replica placement in hierarchical data

385

Fig. 6 Comparison of execution times for Zipf and sequential distributions

of replicas compared to Fast Spread and a slightly higher number of replicas than ABU. For example, using the Zipf distribution, the approximate number of replicas created by PBRP, ABU, and Fast Spread are 58, 35, and 150, respectively. The storage capacity of the replica servers has a major impact on the performance of the placement algorithms. With decreasing capacity, the execution times of all methods are increased but by different degrees. Figure 6 shows the execution times for the three storage configurations using the Zipf and Sequential distributions. The execution time for Caching increases drastically as the capacities of the client sites decrease (‘Config2’ and ‘Config3’). Since the storage size in the client-tier is the same in both configurations two and three, the job execution times for Caching and Best Client remain almost the same. This is because files are replicated on the client sites in both strategies. In both configurations, PBRP shows consistently better performance than the other algorithms. In particular when the available capacity is small, the benefit of PBRP over ABU increases significantly. Figure 7 (top) shows the execution times of APBRP and PBRP using configuration one as the client request rate fluctuates regularly. APBRP offers better execution times for all request access patterns. APBRP adjusts the threshold value based on the varying arrival rate which leads to the creation of more replicas compared to PBRP which decreases the execution time. For example, using a Zipf distribution, the approximate number of replicas created by APBRP and PBRP are 92 and 75 respectively. Like PBRP, APBRP shows the lowest job time for the Zipf access pattern.

386

M. Shorfuzzaman et al.

Fig. 7 Execution times for configuration one (top) and job times by configuration (bottom) as request rate fluctuates

The benefit of APBRP over PBRP is most significant when the access pattern shows some randomness. Figure 7 (bottom) compares the execution times of PBRP and APBRP for the three storage configurations with fluctuating access rate. With decreasing storage size, the execution times of both algorithms increase but by different amounts. APBRP shows better job execution times for all three configurations. However, when the available storage capacity is small, the benefit of APBRP over PBRP decreases for the first three data access patterns. This is due to frequent replica replacement in APBRP

Adaptive popularity-driven replica placement in hierarchical data

387

when the servers have small storage capacities. Thus, the increased total number of replicas offers little benefit in terms of latency. The Random and Sequential access patterns are an exception to this trend due to a lower replica replacement frequency in APBRP. 5.2 Average bandwidth consumption Figure 8 shows the average bandwidth cost for configuration one. For all access patterns, the costs of Caching are, naturally, the lowest. Among the other strategies, PBRP performs best since more client requests are served by mid-tier nodes. As a result, the bandwidth used in the upper tier links is decreased and the average bandwidth used by PBRP is low. For the Zipf access pattern, the difference between PBRP and other strategies is more pronounced. Figure 9 shows the bandwidth cost of all repliFig. 8 Average bandwidth cost for different replication methods using configuration one

Fig. 9 Comparison of average bandwidth cost for Zipf and sequential patterns

388

M. Shorfuzzaman et al.

Fig. 10 Average bandwidth for configuration one (top) and by configuration (bottom) as request rate fluctuates

cation strategies for the three storage configurations with the Zipf and Sequential distributions. As the storage decreases, the bandwidth costs of all strategies increase. Figure 10 (top) shows the average bandwidth costs of APBRP and PBRP using storage configuration one when the data access arrival rate from the clients fluctuates regularly. APBRP gives better average bandwidth cost between the two placement methods for all data access patterns. APBRP adjusts the threshold value based on the varying access arrival rate which leads to the creation of an increased number of replicas close to the clients compared to PBRP. This in turn decreases the bandwidth

Adaptive popularity-driven replica placement in hierarchical data

389

consumption. Like PBRP, APBRP shows the lowest bandwidth consumption for Zipf distribution compared to other access patterns. Average bandwidth costs using three different storage configurations are compared in Fig. 10 (bottom) for regular fluctuation in access rate. With decreasing storage size, the bandwidth costs of both the techniques are increased but by different degrees. APBRP shows better bandwidth costs for all three storage configurations. However, the benefit of APBRP over PBRP decreases when the storage capacities of replica servers are reduced. 5.3 Storage use The storage used by the placement schemes for configuration one are shown in Fig. 11. For all access patterns, the costs of Caching and Fast Spread are high, PBRP Fig. 11 Storage cost for different placement methods for configuration one

Fig. 12 Comparison of storage cost for Zipf and sequential patterns

390

M. Shorfuzzaman et al.

is medium, and Best Client, Cascading and ABU are low. The storage used by PBRP is for its moderate number of replicas created down the hierarchy. The capacity of the servers has a clear impact on the percentage of storage used by different strategies. Reducing the storage size leads to a significant increase in the percentage of storage used as shown in Fig. 12. For example, 34.88% of storage is used by PBRP for Zipf in configuration one which increases to 66.66% in configuration two. One might expect that the reduction of storage size should lead to 100% use of storage but some grid sites use their storage completely while others might not use any space at all, depending on access pattern. Figure 13 (top) shows the storage uses of APBRP and PBRP using replica server configuration one when the data access arrival rate from the clients fluctuates regularly. APBRP requires more storage resources than PBRP for all data access patterns. This is due to the creation of an increased number of replicas in APBRP compared to PBRP. Like PBRP, APBRP shows the lowest storage consumption for Sequential distribution compared to other access patterns due to the creation of a relatively less number of replicas. Figure 13 (bottom) compares storage use by PBRP and APBRP for all three storage configurations as access rate fluctuates. With less storage, the percentage of storage use for both techniques increase but by different degrees. When the available storage is smaller, the storage use for APBRP for most access patterns decreases due to frequent replica replacement but, again, the Random and Sequential access patterns are an exception.

6 Conclusions and future work This paper introduced a popularity-driven dynamic replica placement algorithm (PBRP) and an adaptive technique to control the degree of replication as the file request rate fluctuates. Simulation results show that our approach can shorten execution time greatly and reduce bandwidth consumption at the cost of only moderate increases in storage use compared to other dynamic replication methods. For all tested data access patterns, PBRP performs better than the other studied algorithms in terms of both job execution time and average bandwidth consumption when the storage size of the replica servers is limited (i.e., Config 2 and Config 3). Although Caching’s performance for job execution time and average bandwidth cost is better than others when client sites have significant space to store replicas (i.e., Config 1), Caching is not a generally practical replication strategy for Data Grids due to its high storage requirements at the client sites. For all studied simulation cases, the storage costs of Caching and Fast Spread are high, PBRP is medium, and Best Client, Cascading and ABU are low. The moderate use of (relatively cheap) storage space by PBRP makes it a good candidate when file access time and bandwidth cost are of primary concern. Simulation results further show that our new adaptive strategy achieves better performance compared to its non-adaptive counterpart in terms of access time and network bandwidth savings as the access rate fluctuates regularly. For future work, we will investigate dynamic replica maintenance (e.g. replica consistency) and work to extend our approach to more general Data Grid network models. We also plan to explore the

Adaptive popularity-driven replica placement in hierarchical data

391

Fig. 13 Storage cost for configuration one (top) and by configuration (bottom) as request rate fluctuates

possibility of exploiting network knowledge in making placement decisions. Finally, we would like to incorporate the QoS requirements of the clients into our placement process.

References 1. Allcock B, Bester J, Bresnahan J, Chervenak AL, Foster I, Kesselman C, Meder S, Nefedova V, Quesnal D, Tuecke S (2002) Data management and transfer in high performance computational grid environments. Parallel Comput J 28(3):749–771

392

M. Shorfuzzaman et al.

2. Allcock W, Foster I, Nefedova V, Chervenak A, Deelman E, Kesselman C, Lee J, Sim A, Shoshani A, Drach B, Williams D (2001) High-performance remote access to climate simulation data: a challenge problem for data grid technologies. In: Proceedings of the supercomputing, 2001, pp 46–60 3. Bell W, Cameron D, Capozza L, Millar A, Stockinger K, Zini F (2002) Simulation of dynamic grid replication strategies in optorsim. In: Proceedings of the 3rd international IEEE workshop on grid computing (Grid’2002), 2002, pp 46–57 4. Bell W, Cameron D, Capozza L, Millar P, Stockinger K, Zini F (2003) Optorsim—a grid simulator for studying dynamic data replication strategies. Int J High Perform Comput Appl 17:403–416 5. Bell WH, Cameron DG, Carvajal-Schiaffino R, Millar AP, Stockinger K, Zini F (2003) Evaluation of an economy-based file replication strategy for a data grid. In: Proceedings of the 3rd IEEE/ACM international symposium on cluster computing and the grid, 2003, pp 667–674 6. Foster I, Alpert E, Chervenak A, Drach B, Kesselman C, Nefedova V, Middleton D, Shoshani A, Sim A, Williams D (2001) The earth system grid: turning climate datasets into community resources. In: Proceedings of the American meteorological society conference, 2001 7. Holtman K (2001) CMS Data grid system overview and requirements. CMS Experiment Note 2001/037, CERN 8. Kesselman C, Foster I (1998) The grid: blueprint for a new computing infrastructure. Morgan Kaufmann, San Mateo 9. LHC Computing Grid (2009) http://lcg.web.cern.ch/lcg/. Distributed production environment for physics data processing 10. Lin Y, Liu P, Wu J (2006) Optimal placement of replicas in data grid environments with locality assurance. In: Proceedings of the 12th international conference on parallel and distributed systems (ICPADS’06), 2006, vol 1, pp 465–474 11. Park S, Kim J, Ko Y, Yoon W (2003) Dynamic data grid replication strategy based on Internet hierarchy. In: Proceedings of the second international workshop on grid and cooperative computing (GCC’2003), 2003, pp 838–846 12. Ranganathan K, Foster I (2001) Design and evaluation of dynamic replication strategies for a high performance data grid. In: Proceedings of the international conference on computing in high energy and nuclear physics, 2001 13. Ranganathan K, Foster IT (2001) Identifying dynamic replication strategies for a high-performance data grid. In: Proceedings of the international workshop on grid computing (GRID’2001), 2001, pp 75–86 14. Revees CR (1993) Modern heuristic techniques for combinatorial problems. Oxford Blackwell Scientific Publication, Oxford 15. Russel M, Allen G, Daues G, Foster I, Seidel E, Novotny J, Shalf J, von Laszewski G (2002) The astrophysics simulation collaboratory: a science portal enabling community software development. Clust Comput 5(3):297–304 16. Tang M, Lee B, Yeo C, Tang X (2005) Dynamic replication algorithms for the multi-tier data grid. Future Gener Comput Syst 21(5):775–790 17. The ATLAS experiment (2009) http://atlas.ch/. Particle Physics Experiment at CERN 18. The European Data Grid project (2001) The datagrid architecture. http://eu-datagrid.web.cern.ch/ eu-datagrid/ 19. Venugopal S, Buyya R, Ramamohanarao K (2006) A taxonomy of data grids for distributed data sharing, management, and processing. ACM Comput Surv 1:1–53 20. Wang H, Liu P, Wu J (2006) A QoS-aware heuristic algorithm for replica placement. J Grid Comput, 96–103