Optimistic Concurrency Control (OCC)

In this lesson, we will describe a way through which the optimistic concurrency control method controls concurrent operations.

Optimistic concurrency control (OCC) is a concurrency control method that was first proposed in 1981 by Kung et al.H. T. Kung and J. T. Robinson, “On optimistic methods for concurrency control,” ACM Transactions on Database Systems, Volume 6, Issue 2, 1981., where transactions can access data items without acquiring locks on them.

In this method, transactions execute in the following three phases:

  • Begin
  • Read & modify
  • Validate & commit/rollback

Begin phase

In this phase, transactions are assigned a unique timestampA timestamp is a monotonically increasing number, often based on the system clock. that marks the beginning of the transaction referred to as the start timestamp.

Read & modify phase

During this phase, transactions execute their read and write operations tentatively. This means that when an item is modified, a copy of the item is written to a temporary, local storage location. A read operation first checks for a copy of the item in this location and returns this one, if it exists. Otherwise, it performs a regular read operation from the database.

Validate & commit/rollback phase

The transaction enters this phase when all operations have been executed.

During this phase, the transaction checks whether there are other transactions that have modified the data this transaction has accessed, and have started after this transaction’s start time. If there are, then the transaction is aborted and restarted from the beginning, acquiring a new timestamp. Otherwise, the transaction can be committed.

This is shown in the following illustration.

The commit of a transaction is performed by copying all the values from write operations, from the local storage to the common database storage that other transactions access.

It’s important to note that the validation checks and the associated commit operation need to be performed in a single atomic action as part of a critical sectionA critical section is some part of a program that can only be executed by one process at a time because it accesses shared resources for which concurrent access can lead to an erroneous behavior. In this case, this could happen if some other transaction commits in between the validation and commit of this transaction, which would make the validation results of this transaction invalid..

This requires some form of locking mechanism, so there are various optimizations of this approach that attempt to reduce the duration of this phase to improve performance.

Ways to implement validation logic

There are two ways to implement validation logic.

Version checking

One way is via version checking, where every data item is marked with a version number. Every time a transaction accesses an item, it can keep track of the version number it had at that point.

During the validation phase, the transaction can check if the version number is the same. If it is, it would mean that no other transaction has accessed the item in the meanwhile.

Timestamp ordering

Another way is by using timestamps assigned to transactions, a technique also known as timestamp ordering, since the timestamp indicates the order in which a transaction must occur relative to the other transaction.

In this approach, each transaction keeps track of the items that are accessed by read or write operations, known as the read set and the write set.

During validation, a transaction performs the following inside a critical section:

It records a fresh timestamp, called the finish timestamp, and iterates over all the transactions that have been assigned a timestamp between the transaction’s start and finish timestamp.

These are essentially all transactions that have started after the running transaction and have already been committed.

For each of those transactions, the running transaction checks if their write set intersects with its own read set. If that’s true for any of these transactions, it means that the transaction essentially reads a value “from the future.”

As a result, the transaction is invalid and must be aborted and restarted from the beginning with a fresh timestamp. Otherwise, the transaction is committed, and is assigned the next timestamp.

Get hands-on with 1400+ tech skills courses.