Project Proposal

Adaptive soft-state protocol in replica location services

  1. Introduction

A replica location service (RLS) is one of core component in Data Grid system in which information about mapping the logical file names (LFN) to physical locations (PFN) is maintained. The RLS responds to user’s query with list of replica’s locations for given LFN. Scalability is one of the most important considerations in designing the RLS. In the current RLS architectures [1, 2, 3], the mapping information is distributed in participating Grid sites in order to support better scalability and reliability. Soft-state protocol, in which the state maintained by each site is exchanged in some interval, is used in the decentralized RLS as it provides the following two benefits:

Implicit removal of stale information via time out

Automatic reconstruction of state after system failures

The two important parameters in soft-state protocol are the interval to send the information (how often) and the amount of information to send (what). The two parameters suggest the trade-off between the accuracy (consistency) of information and the overhead of update. The more consistent information means the more frequent updates. In the current Grid RLS system the two parameters are statically set (e.g., send every information in every 1 hour) for the particular applications.

In this project, I propose to develop the adaptive RLS soft-state protocol where the two parameters are set adaptively in order to guarantee the less penalty caused by relaxed consistency while reducing the overhead caused by update. The main idea is to update the popular information more frequently than the less popular information.

  1. Related works

In the current Grid RLS architectures [1, 2, 3], the local site maintains the state about LFN-PFN mapping in the site’s local database (e.g., LRC in [1, 2]), and the global index collects the mapping information from distributed sites (e.g., RLI in [1, 2]) and provides interface for user’s query. The interval to send the state from the sites to the global index is either statically fixed [1, 2] or determined dynamically by considering the network traffics [3]. In their implementations, there are two options for determining what to send. They either send the full state (i.e., every entries of LFN-PFN mapping) in every fixed interval or incrementally update only the locally updated information and send the full information in less frequent interval. The performance evaluations suggest that the overhead caused by this soft state protocol is huge (e.g., few thousands second for fully updating 1 million entries). Incremental update does not solve the problem as it presents more overhead when the local update rate is big.

The replica location problem or distributed search and indexing in more general term also has been the topic of research in peer to peer computing [4, 5, 6]. They organize overlay networks to route the query request to peer nodes, and build search-efficient indexing structures to provide good scalability in fully decentralized manner. The system model in their research is little different from the Data Grid especially the scale of system in terms of number of nodes publishing and disseminating the information (tens of thousands in P2P and tens or hundreds in Data Grid). Thus, the approaches presented in their research cannot be applied directly to the Data Grid. In this project, the system model and the application requirements are based on the Data Grid. So the basic assumption about the underlying system model is the same as the one presented in [1, 2, 3].

  1. Proposed protocol

The disadvantage of soft state protocol is that information maintained in the global index may not represent the current state accurately. As an illustration, consider the state changes in the following figure.

The person in the right cannot get the LFN-PFN mapping in response to his query even though the LFN is already published by the person in the left. It is because the update is done later in time. The way to address the problem is to reduce the periodic update interval, but it increases the cost. So there is a trade off between the consistency and the cost in soft state protocol.

In many software systems, the performance optimization is based on the caching which utilizes the access locality properties. Locality properties are very common in any information systems. For example the ZIPF distribution has been identified as the model of distribution in web request [7] and used in designing the web caching. Thus, I believe that the information request in Data Grid also exhibits some kind of locality or distribution. In fact, some Data Grid researches have been based on this assumption [8]. It is hard to imagine that hundreds of millions logical file in Data Grid are requested the same number of times. If we assume that user’s request coming into the global index has some distribution, and thus some logical files are more popular target of query than the others, then it is better to enforce the more tight consistency for the popular files since their information is more valuable than the less popular files. For example, if a particular file is known to contain the valuable information to the Data Grid users such as scientists, and thus become the target of query many times, then it would be better to provide the complete list of replica locations corresponding to this file. The replica selection component will choose the best replica location among the replicas, and thus the more replica locations given to the component will results in the better selection.

In the system model I propose, the state (LFN-PFN mapping entry) maintained in a local replica catalog (LRC) is partitioned in many group of entries. The partition can be based on logical collection of files or namespace of logical files. I assume the partitioning is based on logical collection hereafter. Each logical collection in a site is a unit of soft state update and thus has different update interval. This is different from the previous research where the interval is statically set for every state entry in a site.The following table isan example of state maintained by LRC.

Table 1. State maintained in LRC

collection / Update interval / LFN / PFN (URL)
colA / 30s / Hep-a-123 / gridftp://cs.virginia.edu/hep-a-123
Hep-a-124 / gridftp://cs.virginia.edu/hep-a-124
Hep-a-125 / gridftp://cs.virginia.edu/hep-a-125
colB / 2m / Hep-b-100 / gridftp://cs.virginia.edu/hep-b-100
Hep-b-101 / gridftp://cs.virginia.edu/hep-b-101
colC / 5m / Hep-c-01 / gridftp://cs.virginia.edu/hep-c-01

The replica location index (RLI) maintains the information about mapping the LFN to LRCs. In my system, the information maintained in RLI becomes little more complicated as shown in the following tables.

Table 2. State maintained in RLI in previous system [1, 2]

LFN / LRCs / Update interval
Hep-a-123 / cs.virginia.edu / 30s
cs.uiuc.edu / 30s
ncsa.edu / 30s

In the table in previous RLI [1, 2], the LFN is associated with multiple LRCs which have copy of LFN. The update interval for each LRC indicates that the soft state update can be done using the different update interval per site. The following is a new table to be used in the proposed system.

Table 3. State maintained in RLI in new system

LFN / LRC / Collection / Update interval / Last Update to RLI / Last Update in LRC / Degree of consistency satisfaction
Hep-a-123 / cs.virginia.edu / colA / 30s / 10/10/06 7pm / 10/10/06 5pm / 0.7
colB / 1m / 11/10/06 2pm / 11/10/06 10am / 0.5
cs.uiuc.edu / colD / 2m / 2/10/05 10pm / 2/9/05 5pm / 0.3
ncsa.edu / colC / 5m / 7/20/06 7am / 7/19/06 7pm / 0.1

In the new table, RLI maintains the information about collection in addition to LRCs associated with LFN. Each collection is associated with the update interval. There are additional columns, last update to RLI, last update in LRC, and degree of consistency satisfaction. I introduce the degree of consistency satisfaction first. As the name implies, this is the degree representing how consistency of particular collection has affected the accuracy of information presented to users. The high value of this means that the information presented to users has been satisfactory in spite of the loose consistency of soft state. On the contrary, the low value represent that the consistency has been the problem to the accuracy of information presented to users. This value is used to determine the update interval for the collection. If the degree of satisfaction is too low, we need to reduce the update interval such that the collection’s state is more tightly synchronized with the LRC’s state, and thus present the users more accurate state. The system may have fixed lower and upper thresholds of the degree of consistency satisfaction and regulate the update interval in order to guarantee the desired level of consistency satisfaction has been met for the collections.

The next question is how we calculate such degree. We use the RLI’s query history to calculate the value. It considers the situation where the user’s query does not return the correct state but the state is already published in local LRCs, but has not updated in RLI. By considering the past result of query, we identify the false result where the information presented to users would have been more accurate if the update by LRC came early to the RLI. This means that, at the time of query history inspection, the correct state has arrived in the RLI, but not early enough. The next figure illustrates this.

Query history

lfnA / lfnC / lfnX / lfnY / lfnK / lfnZ / lfnU / lfnB / lfnO / ….

Time t0 t1 t2 t3 t4 t5 t6 t7 t8 ……

LFN / LRC / Update interval / Last Update in RLI / Last Update in LRC / Degree of consistency satisfaction
lfnY / cs.virginia.edu / 30s / t1 / t1 / 0.7
1m / < t0 / < t0 / 0.5
cs.uiuc.edu / 3m / t4 / t2 / 0.3
ncsa.edu / 5m / T2 / T2 / 0.1

The logical file lfnY has been requested at time t3, but the record indicates that update from ‘cs.uiuc.edu’ LRC was late in time. Furthermore, the last update in LRC indicates that it has updated before the logical file is requested by the user. Thus it suggests that if the update were earlier than t3, the information presented in response to the query were more accurate. This record will reduce the degree of consistency satisfaction for the collection.

There are three kinds of inaccurate information in the system. They are as follows:

No LFN : the state indicates there’s no LFN corresponding the user’s query but later the LFN is found to be published already, but not yet registered in RLI

LFN but no PFN: the state indicates that there are replicas corresponding to the LFN, but a particular PFN is not included in the state, but later it is found to exist in a site earlier than the query

Wrong PFN: one of the replica information returned to user is wrong, meaning that its location is changed or removed in the site

The three different situations will have different impact to the user. For example, the first case is more serious than the second one. Even if the second case occurs, the user may be able to complete its replication using the other replica locations returned from the RLI. However, in the first case, the user does not get any useful information from the RLI. Thus, the penalty applied to the degree of consistency satisfaction should be different for each case. The more detailed algorithm for calculating the degree of consistency satisfaction will be devised later.

Using the way the degree of consistency satisfaction is calculated, the more a logical collection is popular, the more frequently the inaccurate state will be found and the update interval of the collection will be reduced. Also if a particular site has published many files which become the popular logical collection its update interval is likely to reduce. Thus, the protocol presented will consider both the site and collection level information popularity.

In summary, compared to the previous research [1, 2, 3], the protocol presented will have the following benefits:

1)Overall RLI cost due to the frequent updates from LRCs will decrease

2)More accurate information for the popular files will be presented to the user

3)Load balancing between LRCs will be fair since the more popular site will generate the more frequent update

4)The size of state maintained in RLI may reduce since the implicit removal after time out can be applied to the states that are not requested frequently

However, the protocol may impose nontrivial amount of overheads such as the followings:

1)Additional information that the RLI must maintain (e.g., collection information, degree of consistency satisfaction, …)

2)The cost to store and process the query history

However, I expect the advantages the protocol brings will be far more than the disadvantages it causes, and will prove this claim through performance evaluation.

  1. Schedule

Date / Action Item / Remarks
- Oct 21 / Install and test Globus RLS / For the baseline and to know how much of their implementation can be used for my implementation
- Nov 4 / Design and implement the relational DB table
- Nov 25 / Implement the protocol’s algorithms
- Dec 2 / Experiments
- Dec 9 / Paper writing

References

[1].Giggle: A Framework for Constructing Sclable Replica Location Services. A. Chervenak, E. Deelman, I. Foster, L. Guy, W. Hoschek, A. Iamnitchi, C. Kesselman, P. Kunst, M. Ripeanu, B, Schwartzkopf, H, Stockinger, K. Stockinger, B. Tierney. Proceedings of Supercomputing 2002 (SC2002), November 2002.

[2].Performance and Scalability of a Replica Location Service. A.L. Chervenak, N. Palavalli, S. Bharathi, C. Kesselman, R. Schwartzkopf. Proceedings of the International IEEE Symposium on High Performance Distributed Computing (HPDC-13), June 2004.

[3].A Decentralized, Adaptive, Replica Location Service. M. Ripeanu, I. Foster; 11th IEEE International Symposium on High Performance Distributed Computing (HPDC-11)Edinburgh, Scotland, July 24-16, 2002.

[4].S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, “A Scalable Content-Addressable Network,” SIGCOMM 2001, San Diego USA, 2001

[5].I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H Balakrishnan, “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” SIGCOMM 2001, San Diego, USA 2001

[6].B. Y. Zhao, J. Kubiatowicz, and A. D. Joseph. Tapestry: an infrastructure for fault-tolerant wide-area location and routing. UCB Technical Report UCB/CSD--01--1141. Computer Science Division (EECS) University of California, Berkeley, April 2001. 40

[7].M. F. Arlitt and C. L. Williamson. Web Server Workload Characterization: The Search for Invariants. In ACM Sigmetrics Int. Conf. on Measurements and Modeling of Computer Systems, Philadelphia, PA, USA, May 1996.

[8].David G. Cameron, Ruben Carvajal-Schiaffino, A. Paul Millar, Caitriana Nicholson, and Kurt Stockinger Floriano Zini. Evaluating Scheduling and Replica Optimisation Strategies in OptorSim. In 4th International Workshop on Grid Computing (Grid2003), Phoenix, Arizona, November 17, 2003. IEEE Computer Society Press.