Optimistic concurrency control

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In computer science, in the field of databases, optimistic concurrency control (OCC) is a concurrency control method used in relational databases without using locking. It is commonly referred to as optimistic locking, a reference to the non-exclusive locks that are created on the database.

Optimistic concurrency control is based on the assumption that most database transactions don't conflict with other transactions, allowing OCC to be as permissive as possible in allowing transactions to execute.

There are three phases in an OCC transaction:

  1. Read: The client reads values from the database, storing them to a private sandbox or cache that the client can then edit.
  2. Validate: When the client has completed editing of the values in its sandbox or cache, it initiates the storage of the changes back to the database. During validation, an algorithm checks if the changes to the data would conflict with either
    • already-committed transactions in the case of backward validation schemes, or
    • currently executing transactions in the case of forward validation schemes.
    If a conflict exists, a conflict resolution algorithm must be used to resolve the conflict somehow (ideally by minimizing the number of changes made by the user) or, as a last resort, the entire transaction can be aborted (resulting in the loss of all changes made by the user).
  3. Write: If there is no possibility of conflict, the transaction commits.

Optimistic concurrency is generally used in environments with a low contention for data. When conflicts are rare, validation can be done efficiently, leading to higher throughput than other concurrency control methods.[1] However, if conflicts happen often, the cost of repeatedly restarting transactions hurts performance significantly; other non-lock concurrency control methods have better performance under these conditions.

Contents

[edit] Web usage

The stateless nature of HTTP makes locking infeasible for web user interfaces. It's common for a user to start editing a record, then leave without following a "cancel" or "logout" link. If locking is used, other users who attempt to edit the same record must wait until the first user's lock expires.

OCC is a natural choice. It is simple to implement and avoids unnecessary waiting or silently overwritten records. Typically the form presented to the user includes a hidden field with the record's original content, a timestamp, a sequence number, or an opaque token. On submit, this is compared against the database. If it differs, the conflict resolution algorithm is invoked.

[edit] Examples

  • MediaWiki's edit pages use OCC. The conflict resolution algorithm is described here.
  • Bugzilla uses OCC; conflicts are called "mid-air collisions". [1]
  • The Ruby on Rails framework has an API for OCC. [2]
  • Most revision control systems support the "merge" model for concurrency, which is OCC.

[edit] References

  1. ^ There are two basic strategies to database concurrency: pessimistic and optimistic locking. Pessimistic locking takes the "pessimistic" view that users are highly likely to corrupt each other's data, and that the only safe option is to serialize data access, so at most one user has control of any piece of data at one time. This ensures data integrity, but can severely reduce the amount of concurrent activity the system can support.

[edit] Web links

  • Kung, H. T.; John T. Robinson (June 1981). "On optimistic methods for concurrency control". ACM Transactions on Database Systems 6 (2): 213-226. doi:10.1145/319566.319567. 
  • Enterprise JavaBeans, 3.0, By Bill Burke, Richard Monson-Haefel, Chapter 16. Transactions, Section 16.3.5. Optimistic Locking, Publisher: O'Reilly, Pub Date: May 16, 2006,Print ISBN-10: 0-596-00978-X,

[edit] See also

Retrieved from "http://en.wikipedia.org/wiki/Optimistic_concurrency_control"
Personal tools