Figure 1.  	Accessing multiple servers in a mobile computing environment.
s := BeginSesion(guarantees)
result := Read(s, query)
Write(s, update)
EndSession(s)
Figure 2.  	A service interface for accessing replicated data.
Towards a Quality of Service Model for Replicated Data Access
Douglas B. Terry
Computer Science Laboratory
Xerox Palo Alto Research Center
Palo Alto, California 94304 U.S.A.
Abstract
This paper introduces the notion of a quality of service model for read and write access to a replicated database or file system. The goal is to provide clients with a choice of service guarantees and to separate the specification of a client's needs from the mechanisms implemented to meet those needs. An analogy is drawn with the quality of service models being explored for communications protocols.
1.  Introduction
Replicated databases and replicated file systems have traditionally presented one of two consistency models to their clients: strong consistency based on one-copy serializability and weak consistency with eventual convergence. In the strong consistency model, the database appears to clients as a centralized service even though it may be replicated among many servers. In the weak consistency model, the only guarantee typically provided to clients is that the various replicas will eventually converge to a mutually consistent state if update activity ceases; clients that access different servers can observe inconsistent replicas. Are there intermediate forms of replicated data consistency that may be useful to clients? What model should be presented to clients to allow them to choose the level of consistency and service that is appropriate for their particular application? 
Why isn't strong consistency sufficient for all applications? Some have argued that one-copy serializability, where the concurrent execution of operations on replicated data is equivalent to a serial execution on non-replicated data, is the one true "correctness" criterion for replicated databases [2][5]. This argument overlooks two important points. First, the cost of maintaining mutually consistent replicas to ensure one-copy serializability, particularly in terms of performance, may be unreasonably high for those clients that do not require strong consistency. Second, weak network connectivity in some environments may render strong consistency an unviable option. As an example, this is true for mobile computing users who hold replicas on their laptop computers that they access locally and only communicate with each other or with servers at irregular intervals.
At the same time, weakly consistent systems in which operations are performed at some subset of the replicas and updates are propagated to the other replicas in a lazy fashion also present problems for many clients and users, especially those that access various, potentially inconsistent servers over time. Consider the scenario where a user is carrying a small portable computer, such as a Personal Digital Assistant (PDA). Suppose that database replicas reside at fixed servers and are accessed over a wireless, cell-based communications network. As depicted in Figure 1, the user writes some data, moves to a new location, and then attempts to read the data that was previously written. The read request is sent to the server in the user's current cell (Server B), which, in this example, is different than the server that processed the user's write operation (Server A). If the two servers have not synchronized their replicas in between the user's write and read operations, then the user will not see the data that he just wrote and may find this confusing.
Ideally, clients of a replicated database or file system should be given some degree of control over the trade-offs between consistency, availability, performance, and other characteristics that are intrinsic to replication algorithms. The choices made could quite possibly vary from client to client and application to application. Clients should be able to specify their requirements in an abstract way, and the system in turn should decide how best to meet these needs or whether they can be met at all. In other words, replicated data clients should be able to choose the quality of service for their data accesses similar to how communicating entities can choose the quality of service provided by modern networks and transport protocols [4][6][7].
The important open question is what should be included in a quality of service (QoS) model for replicated data access. This paper discusses the characteristics of such a model and proposes some choices that might be provided. It should be viewed as simply a first cut at trying to define a service model for replicated data. 
2.  Basics of a Service Model
In general, quality of service models permit clients to select a number of abstract guarantees that apply to a sequence of operations. These guarantees govern properties such as the timing, ordering, and reliability of the operations. The system promises to ensure these properties for operations performed by clients or else inform them that the guarantees cannot be met and perhaps refuse to accept further operations. Typically, rather than enforcing the guarantees for all operations performed by all clients, guarantees are provided within the scope of a session, and different guarantees can be selected for different sessions.
For transport protocols, the basic operations are Send and Receive and the sessions are generally end-to-end connections or flows or multicast groups. The QoS model might allow clients to choose the bandwidth that should be allocated to a particular session or to specify bounds on the variance in message delay [4][6]. As another example, the ISIS tool-kit permits clients to choose from a variety of multicast protocols with different atomicity and ordering guarantees [3].
For replicated data access, the QoS model could be defined mainly in terms of Read and Write operations. A session would then be a sequence of Read and Write operations performed by a given client or clients on a given replicated database or databases. Clients would choose from a list of service guarantees when they create sessions. The guarantees selected for a session apply to those operations within the session. The service interface might be something like that presented in Figure 2.
Notice that this service interface does not include any mention of individual replicas, much in the same way that a communications service model does not mention particular links or routers. Applications care about the service guarantees being provided, not the details of how that service is implemented. For each operation on each session, the replicated database or file system, with full knowledge of the previous operations performed within the session and the current state of various replicas, takes actions, such as acquiring locks and routing the operation to appropriate servers, to ensure that the guarantees requested for this session can be enforced. 
What types of guarantees might be desired in a QoS model for replicated data access? Certainly, strong consistency may be one option. For one-copy serializability, the system provides a serialization order for all operations and guarantees that a Read operation will see the effects of all previous Write operations. Clients for which weak consistency is acceptable can select no guarantees and rely on the system's "best effort" service. What about intermediate service levels that relax strong consistency but still provide useful guarantees?
Some guarantees may involve the timeliness of data that is Read. An existing example is "quasi copies" where the system places bounds on how out-of-date a replica may become [1]. As a generalization of this concept, the QoS model could include guarantees such as: a Read operation will see the effects of any Write operation that was performed more than N time units ago.
Within the Bayou project at Xerox PARC, we have been exploring different "session guarantees" that control the ordering of operations and propagation of updates as seen by clients [8]. For instance, the "Read Your Write" guarantee ensures that a Read operation will see the effects of any Write operation that was performed previously within the same session. The Bayou system also permits clients to select "Monotonic Reads", "Writes Follow Reads", and "Monotonic Writes" guarantees in any combination.
3.  A Usage Example
Let's look at a specific application to see how QoS guarantees may be used in practice. Consider a calendar database that manages a user's daily appointments. This database is replicated for increased availability. It is shared with the user's secretary, who occasionally schedules meetings and business trips, and with the user's spouse, who occasionally adds social events. 
Strong consistency is not required. In particular, it is okay for the user's secretary or spouse to read an out-of-date copy of the user's appointment calendar. The "outdatedness" of a calendar does not prevent it from being useful, but simply increases the likelihood that conflicting updates may be introduced. In this application, update conflicts can be readily corrected.
However, the people accessing this calendar want some guarantees from the replicated database system. Suppose that the application displays the calendar in some graphical format on a user's screen and periodically refreshes this display by re-reading the database contents. Users may want the ability to specify bounds on the timeliness of the data being displayed.
This calendar application does not require, but probably wants, the guarantee that scheduled meetings will not disappear from a user's display (and perhaps reappear later) simply because the system routes the application's read operations to different servers that have seen different sets of writes. This is the motivation for the "Monotonic Read" guarantee provided in the Bayou system [8]. 
This application also could use the "Read Your Writes" guarantee to ensure that users see the entries that they themselves have added. Note that users do not need to share sessions; it is sufficient for each instance of the application that is running to create a session for its own reads and writes. 
Most writes to the calendar database simply add new appointments. These writes are generally independent and can be applied in any order. In fact, they can be processed in different orders at different servers and still produce mutually consistent replicas. Thus, having the system enforce a global serialization order would be overkill for this application. The main exception involves writes that modify an existing entry. In this case, each server must process these writes in an order that is consistent with the order that the updates were done by users. This can be ensured by performing modifications in a session with some sort of "Monotonic Writes" guarantee.
4.  Conclusions
This paper introduces the notion of a quality of service model for read and write access to a replicated database or file system. The goal is to provide clients with a choice of service guarantees and to separate the specification of a client's needs from the mechanisms implemented to meet those needs. An analogy is drawn with the quality of service models being explored for communications protocols.
A number of important questions remain unanswered:
What are the appropriate QoS guarantees that can be provided to clients of replicated data? A few concrete guarantees regarding the ordering, timing, and propagation of read and write operations have been proposed in the Bayou system and elsewhere, but other useful guarantees are undoubtedly waiting to be discovered. Also, experimentation with real applications is needed to verify the utility of the proposed guarantees.
How should the service model present trade-offs to clients in an understandable way? For example, how can a client determine or predict the effect that selecting a particular consistency guarantee will have on performance or availability? These effects depend on a number of complex and subtle factors.
How can the system best implement the provided guarantees? This paper has not discussed implementation issues. The Bayou design includes efficient implementations for its four session guarantees based on certain assumptions about server behavior [8]. Developing implementations for a wide-variety of guarantees and mediating between clients that request different guarantees is a challenge.
In conclusion, more work, both theoretical and experimental, is needed to develop a comprehensive, practical quality of service model for replicated data.
5.  Acknowledgments
The ideas presented in this paper have benefited from conversations with a number of colleagues, especially other members of the Bayou project: Alan Demers, Karin Petersen, Mike Spreitzer, Marvin Theimer, and Brent Welch.
6.  References
[1]	R. Alonso, D. Barbara, and H. Garcia-Molina. Data caching issues in an information retrieval system. ACM Transactions on Database Systems 15(3):359-384, September 1990.
[2]	P. A. Bernstein and N. Goodman. An algorithm for concurrency control and recovery in replicated distributed databases. ACM Transactions on Database Systems 9(4):596-615, December 1984.
[3]	K.P. Birman and T.A. Joseph. Reliable communication in the presence of failures. ACM Transactions on Computer Systems 5(1):47-76, February 1987.
[4]	D. D. Clark, S. Shenker, and L. Zhang. Supporting real-time applications in an integrated services packet network: Architecture and mechanism. Proceedings SIGCOMM `92, August 1992, pages 14-26.
[5]	S. Davidson, H. Garcia-Molina, and D. Skeen. Consistency in a partitioned network: A survey. ACM Computing Surveys 17(3):341-370, September 1985.
[6]	D. Ferrari. Client requirements for real-time communications services. IEEE Communications Magazine 28(11):65-72, November 1990.
[7]	J. Kurose. Open issues and challenges in providing quality of service guarantees in high-speed networks. Computer Communication Review 23(1):6-15, January 1993.
[8]	D. Terry, A. Demers, K. Petersen, M. Spreitzer, M. Theimer, B. Welch. Session guarantees for weakly consistent replicated data. Proceedings International Conference on Parallel and Distributed Information Systems (PDIS), Austin, Texas, September 1994, pages 140-149.