MOT Concurrency Control Mechanism

After investing extensive research to find the best concurrency control mechanism, we concluded that SILO based on OCC is the best ACID-compliant OCC algorithm for MOT. SILO provides the best foundation for MOT's challenging requirements.

NOTE: MOT is fully Atomicity, Consistency, Isolation, Durability (ACID)-compliant, as described in the MOT Introduction section.

The following topics describe MOT's concurrency control mechanism -

MOT Local and Global Memory

SILO manages both a local memory and a global memory, as shown in Figure 1.

• Global memory is long-term shared memory is shared by all cores and is used primarily to store all the table data and indexes
• Local memory is short-term memory that is used primarily by sessions for handling transactions and store data changes in a primate to transaction memory until the commit phase.

When a transaction change is required, SILO handles the copying of all that transaction's data from the global memory into the local memory. Minimal locks are placed on the global memory according to the OCC approach, so that the contention time in the global shared memory is extremely minimal. After the transaction’ change has been completed, this data is pushed back from the local memory to the global memory.

The basic interactive transactional flow with our SILO-enhanced concurrency control is shown in the figure below -

Figure 1 Private (Local) Memory (for each transaction) and a Global Memory (for all the transactions of all the cores)

For more details, refer to the Industrial-Strength OLTP Using Main Memory and Many-cores document [Comparison - Disk vs. MOT].

MOT SILO Enhancements

SILO in its basic algorithm flow outperformed many other ACID-compliant OCCs that we tested in our research experiments. However, in order to make it a product-grade mechanism, we had to enhance it with many essential functionalities that were missing in the original design, such as -

• Added support for interactive mode transactions, where transactions are running SQL by SQL from the client side and not as a single step on the server side
• Added optimistic inserts
• Added support for non-unique indexes
• Added support for read-after-write in transactions so that users can see their own changes before they are committed
• Added support for lockless cooperative garbage collection
• Added support for lockless checkpoints
• Added support for fast recovery
• Added support for two-phase commit in a distributed deployment

Adding these enhancements without breaking the scalable characteristic of the original SILO was very challenging.

MOT Isolation Levels

Even though MOT is fully ACID-compliant (as described in the section), not all isolation levels are supported in MogDB 2.1. The following table describes all isolation levels, as well as what is and what is not supported by MOT.

Table 1 Isolation Levels

The following table shows the concurrency side effects enabled by the different isolation levels.

Table 2 Concurrency Side Effects Enabled by Isolation Levels

In the near future release, MogDB MOT will also support both SNAPSHOT and SERIALIZABLE isolation levels.

MOT Optimistic Concurrency Control

The Concurrency Control Module (CC Module for short) provides all the transactional requirements for the Main Memory Engine. The primary objective of the CC Module is to provide the Main Memory Engine with support for various isolation levels.

Optimistic OCC vs. Pessimistic 2PL

The functional differences of Pessimistic 2PL (2-Phase Locking) vs. Optimistic Concurrency Control (OCC) involve pessimistic versus optimistic approaches to transaction integrity.

Disk-based tables use a pessimistic approach, which is the most commonly used database method. The MOT Engine use an optimistic approach.

The primary functional difference between the pessimistic approach and the optimistic approach is that if a conflict occurs -

• The pessimistic approach causes the client to wait.
• The optimistic approach causes one of the transactions to fail, so that the failed transaction must be retried by the client.

Optimistic Concurrency Control Approach (Used by MOT)

The Optimistic Concurrency Control (OCC) approach detects conflicts as they occur, and performs validation checks at commit time.

The optimistic approach has less overhead and is usually more efficient, partly because transaction conflicts are uncommon in most applications.

The functional differences between optimistic and pessimistic approaches is larger when the REPEATABLE READ isolation level is enforced and is largest for the SERIALIZABLE isolation level.

Pessimistic Approaches (Not used by MOT)

The Pessimistic Concurrency Control (2PL or 2-Phase Locking) approach uses locks to block potential conflicts before they occur. A lock is applied when a statement is executed and released when the transaction is committed. Disk-based row-stores use this approach (with the addition of Multi-version Concurrency Control [MVCC]).

In 2PL algorithms, while a transaction is writing a row, no other transaction can access it; and while a row is being read, no other transaction can overwrite it. Each row is locked at access time for both reading and writing; and the lock is released at commit time. These algorithms require a scheme for handling and avoiding deadlock. Deadlock can be detected by calculating cycles in a wait-for graph. Deadlock can be avoided by keeping time ordering using TSO or by some kind of back-off scheme.

Encounter Time Locking (ETL)

Another approach is Encounter Time Locking (ETL), where reads are handled in an optimistic manner, but writes lock the data that they access. As a result, writes from different ETL transactions are aware of each other and can decide to abort. It has been empirically verified that ETL improves the performance of OCC in two ways -

• First, ETL detects conflicts early on and often increases transaction throughput. This is because transactions do not perform useless operations, because conflicts discovered at commit time (in general) cannot be solved without aborting at least one transaction.
• Second, encounter-time locking Reads-After-Writes (RAW) are handled efficiently without requiring expensive or complex mechanisms.

Conclusion

OCC is the fastest option for most workloads. This finding has also been observed in our preliminary research phase.

One of the reasons is that when every core executes multiple threads, a lock is likely to be held by a swapped thread, especially in interactive mode. Another reason is that pessimistic algorithms involve deadlock detection (which introduces overhead) and usually uses read-write locks (which are less efficient than standard spin-locks).

We have chosen Silo because it was simpler than other existing options, such as TicToc, while maintaining the same performance for most workloads. ETL is sometimes faster than OCC, but it introduces spurious aborts which may confuse a user, in contrast to OCC which aborts only at commit.

OCC vs 2PL Differences by Example

The following shows the differences between two user experiences - Pessimistic (for disk-based tables) and Optimistic (MOT tables) when sessions update the same table simultaneously.

In this example, the following table test command is run -

table "TEST" - create table test (x int, y int, z int, primary key(x));

This example describes two aspects of the same test - user experience (operations in the example) and retry requirements.

Example Pessimistic Approach - Used in Disk-based Tables

The following is an example of the Pessimistic approach (which is not Mot). Any Isolation Level may apply.

The following two sessions perform a transaction that attempts to update a single table.

A WAIT LOCK action occurs and the client experience is that session #2 is stuck until Session #1 has completed a COMMIT. Only afterwards, is Session #2 able to progress.

However, when this approach is used, both sessions succeed and no abort occurs (unless SERIALIZABLE or REPEATABLE-READ isolation level is applied), which results in the entire transaction needing to be retried.

Table 1 Pessimistic Approach Code Example

Example Optimistic Approach - Used in MOT

The following is an example of the Optimistic approach.

It describes the situation of creating an MOT table and then having two concurrent sessions updating that same MOT table simultaneously -

create foreign table test (x int, y int, z int, primary key(x));

• The advantage of OCC is that there are no locks until COMMIT.
• The disadvantage of using OCC is that the update may fail if another session updates the same record. If the update fails (in all supported isolation levels), an entire SESSION #2 transaction must be retried.
• Update conflicts are detected by the kernel at commit time by using a version checking mechanism.
• SESSION #2 will not wait in its update operation and will be aborted because of conflict detection at commit phase.

Table 2 Optimistic Approach Code Example - Used in MOT