Optimistic Replication Using Vector Time Pairs Russ Cox MIT CSAIL William Josephson Cornell CS rsc csail mit edu wkj cs cornell edu Abstract Anyone who uses more than one computer system is aware of the data management problem posed by doing so sharing files among systems requires propagation of changes to the other systems by some synchronization method The proliferation of mobile and small devices with low bandwidth or intermittent network connectivity introduces new constraints on synchronization algorithms We present new algorithms for tracking updates in a optimistically replicated hierarchical data The algorithms use a pair of vector times one tracking modifications and a second tracking synchronizations previous systems have typically used only a single vector conflating the two meanings Algorithms using vector time pairs are considerably simpler and more flexible than traditional algorithms using single vectors Vector time pairs are also significantly easier to compress than single vectors These claims are supported by a theoretical analysis as well as simulation of the algorithms on various synthetic workloads derived from real world traces 1 Introduction Data replication plays an increasingly important role in today s computing environments A typical computer user might store data on a shared file server an office PC a home PC a notebook and a PDA The industry wide SyncML initiative 27 is aimed at making replication of data easier and thus more commonplace than it is today The increasing storage capacities of handheld devices like PDAs music players and even USB memory sticks make them attractive ways to transfer large amounts of data as well It seems a safe bet that handheld devices will continue to decrease in size but increase in storage capacity All of these trends suggest that the management of replicas and replicated data will become ever more central in tomorrow s computing environments The replication in the examples just given is typically optimistic meaning that any replica can initiate changes to any data Previous research on the use of optimistic replication has found that conflicts are rare in many applications For instance in file systems most files are written only by one user who acts as a human write token 19 Indeed disconnected AFS 13 Coda 14 and Ficus 7 all employ optimistic replication to provide a high availability file system in the face of limited communication Optimistically replicated systems must employ some bookkeeping scheme to propagate changes and also to detect concurrent changes or conflicts that need to be reconciled We present vector time pairs as a new way to track changes in an optimistically replicated system Vector time pair algorithms have the following desirable properties can support an arbitrary number of replicas with arbitrary dynamic communication patterns replicas do not need to be added to or removed from the system explicitly synchronizations focus very quickly on the data that needs to be transferred partial synchronizations are easily implemented sink replicas which never initiate file system changes cause no extra work for other replicas the performance of the system is independent of the synchronization frequency among the replicas none of the algorithms attempt to construct global knowledge about the system As discussed later in the paper no current algorithms used for optimistic replication have all of these properties The main contribution of this paper is the insight that traditional synchronization metadata can be separated into metadata tracking what you have and metadata tracking what you know The vector time pair algorithms follow immediately from this insight Roadmap In the remainder of this paper we review the scenarios that a synchronization algorithm must handle section 2 Then we present the vector time pair algorithms section 3 We describe one concrete implementation of vector time pairs in a user level file synchronizer section 4 Using a simulation framework to level the playing field we then compare vector time pairs with version vec 2 tors section 5 empirically Finally we discuss related work and how it has been constrained by less flexible algorithms section 6 2 Synchronization semantics Before discussing synchronization algorithms we must define synchronization A strictly formal mathematical definition is an ongoing research topic see for example Balasubramanian and Pierce 1 Ramsey and Csirmaz 24 and Pierce and Voilloun 22 so we will make do with a less formal but still precise definition We believe our characterization is reasonable because it is similar to the characterization given by Parker in the original paper on version vectors 20 and because when restricted to a pair of replicas it is equivalent to the definition of synchronization used by the popular Unison synchronizer 1 We consider only unidirectional synchronizations in which changes from one replica are propagated to a second but changes on the second do not propagate to the first There are many cases in which this is desirable For example the second machine might be less trusted than the first More importantly unidirectional synchronization is the more general case we can build bidirectional synchronization by applying unidirectional synchronization once in each direction When we say that B synchronizes from A we mean that a unidirectional synchronization propagated information from B to A We want synchronization to provide a no lost updates guarantee Specifically suppose each file is represented as a log of updates made over the course of its lifetime beginning with its initial creation If two replicas have different copies of a file call the copies F A and F B it is safe for F A to replace F B only if F A s log is a prefix of F B s If this is satisfied then all of the updates represented by F B are also present in F A eliminating F B will not lose updates To explore how the no lost updates rule guides synchronization we present a sequence of examples Suppose a single file is kept on a pair of replicas A and B Consider the following three graphs showing how information about the file might propagate between the replicas A B 1 m A B A B m m 2 3 m m 4 m m i ii iii In each picture each row shows the state of the replicas at one time unit Each circle represents the file as it exists on a particular replica at some point in time Modifications to the file contents are marked by an m As a further reminder file contents are represented by the