Optimistic replication

From Wikipedia, the free encyclopedia

Optimistic replication[1] (also known as lazy replication[2][3]) is a strategy for replication in which replicas are allowed to diverge. Traditional pessimistic replication systems are based on the principle of single-copy consistency. that is, users should observe the system to behave as if there was only one copy of the data. Optimistic replication does away with this in favor of eventual consistency, meaning that replicas are guaranteed to converge only when a system is idle.

[edit] Algorithms

An optimistic replication algorithm consists of five elements:

  1. Operation submission: Users submit operations at independent sites.
  2. Propagation: Each site shares the operations it knows about with the rest of the system.
  3. Scheduling: Each site decides on an order for the operations it knows about.
  4. Conflict resolution: If there are any conflicts among the operations a site has scheduled, it must modify them in some way.
  5. Commitment: The sites agree on a final schedule and conflict resolution result, and the operations are made permanent.

There are two strategies for propagation: state transfer, where sites propagate a representation of the current state, and operation transfer, where sites propagate the operations that were performed (essentially, a list of instructions on how to reach the new state).

Scheduling and conflict resolution can either be syntactic or semantic. Syntactic systems rely on general information, such as when or where an operation was submitted. Semantic systems are able to make use of application-specific information to make smarter decisions. Note that state transfer systems generally have no information about the semantics of the data being transferred, and so they have to use syntactic scheduling and conflict resolution.

[edit] Examples

One well-known example of a system based on optimistic replication is the CVS version control system, or any other version control system which uses the copy-modify-merge paradigm. CVS covers each of the five elements:

  1. Operation submission: Users edit local versions of files.
  2. Propagation: Users manually pull updates from a central server, or push changes out once the user feels they are ready.
  3. Scheduling: Operations are scheduled in the order that they are received by the central server.
  4. Conflict resolution: When a user pushes to or pulls from the central repository, any conflicts will be flagged for that user to fix manually.
  5. Commitment: Once the central server accepts the changes which a user pushes, they are permanently committed.

A special case of replication is synchronization, where there are only two replicas. For example, personal digital assistants (PDAs) allow users to edit data either on the PDA or a computer, and then to merge these two datasets together. Note, however, that replication is a broader problem than synchronization, since there may be more than two replicas.

Other examples include:

[edit] References

  1. ^ Saito, Yasushi & Shapiro, Marc (2005), “Optimistic replication”, ACM Computing Survey 37 (1): 42-81, ISSN 0360-0300, <http://doi.acm.org/10.1145/1057977.1057980> 
  2. ^ Ladin, R.; Liskov, B.; Shrira, L.; Ghemawat, S. (1992). "Providing high availability using lazy replication". ACM Transactions on Computer Systems (TOCS) 10 (4): 360–391. doi:10.1145/138873.138877. 
  3. ^ Ladin, R.; Liskov, B.; Shrira, L. (1990). Lazy replication: exploiting the semantics of distributed services. ACM Press New York, NY, USA. 
  4. ^ Gray, J.; Helland, P.; O’neil, P.; Shasha, D. (1996). "The dangers of replication and a solution". Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data 173: 182. 
  5. ^ Terry, D.B.; Theimer, M.M.; Petersen, K.; Demers, A.J.; Spreitzer, M.J.; Hauser, C.H. (1995). "Managing update conflicts in Bayou, a weakly connected replicated storage system". Proceedings of the fifteenth ACM symposium on Operating systems principles: 172–182. doi:10.1145/224056. 
  6. ^ Kermarrec, A.M.; Rowstron, A.; Shapiro, M.; Druschel, P. (2001). "The IceCube approach to the reconciliation of divergent replicas". Proceedings of the twentieth annual ACM symposium on Principles of distributed computing: 210–218. doi:10.1145/383962.384020.