TicToc: Time Traveling Optimistic Concurrency Control

By Xiangyao Yu, MIT CSAIL; Andrew Pavlo, Carnegie MellonDaniel Sanchez and Srinivas Devadas, MIT CSAIL

The TicToc algorithm enables scalable and high-performing concurrency control for future multi- and many-core systems. Large-scale, highly parallel transaction processing systems can be built with TicToc. We will present TicToc in a paper at the upcoming ACM SIGMOD/PODS 2016 Conference.

­­Multi-core systems are now pervasive, as parallelism has become the main approach to increase system performance. Systems with tens to hundreds of CPU cores are already on the market, and thousand-core chips will be available in the near future. Conventional DBMSs, however, still scale poorly beyond a few cores. The key bottleneck of on-line transaction processing (OLTP) DBMSs is their concurrency control algorithm. Prior work has shown that common concurrency control algorithms suffer from both fundamental and artificial scalability bottlenecks. Although recent work ameliorates some of the latter problems, fundamental bottlenecks remain.

Limitations of Common Concurrency Control Algorithms

Ideally, concurrency control schemes should restrict the inherent parallelism in transactional workloads as little as possible, while incurring small management overhead that scales well with the number of cores. Many legacy DBMSs use two-phase locking (2PL) as their concurrency control, which orders all the transactions in physical time. However, using locks limits the scalability of these algorithms. Most of the recently proposed concurrency control schemes are based on timestamp ordering (T/O). T/O schemes assign a unique, monotonically increasing timestamp to each transaction. The DBMS then uses these timestamps to process conflicting operations in the proper order. The two most common variants of T/O are multi-version concurrency control (MVCC) and optimistic concurrency control (OCC).

T/O algorithms are popular because they allow significant concurrency, but they suffer from a fundamental scalability bottleneck: timestamp allocation. Using a shared-memory counter to produce timestamps limits T/O schemes to a few million transactions per second, orders of magnitude lower than modern OLTP workload requirements.

Prior work has proposed hardware and software techniques to increase timestamp allocation throughput, but both approaches have serious limitations. On the hardware side, centralized asynchronous counters, atomic memory operations, and fully synchronized clocks alleviate the timestamp allocation bottleneck, but they are challenging to implement and are not available in current systems. On the software side, coarse-grained timestamp epochs with group commit reduces the frequency of timestamp allocations, but still limits concurrency in common scenarios.

Timestamp ordering (T/O) algorithms are popular because they allow significant concurrency, but they suffer from a fundamental scalability bottleneck: timestamp allocation…The TicToc algorithm achieves higher concurrency than state-of-the-art T/O schemes and completely eliminates the timestamp allocation bottleneck.

TicToc: Data-driven Timestamp Management 

The TicToc algorithm that we developed achieves higher concurrency than state-of-the-art T/O schemes and completely eliminates the timestamp allocation bottleneck. The key contribution of TicToc is a technique that we call data-driven timestamp management: instead of assigning timestamps to each transaction independently of the data it accesses, TicToc embeds the necessary timestamp information in each tuple to enable each transaction to compute a valid commit timestamp after it has run, right before it commits.

This approach has two benefits. First, each transaction infers its timestamp from metadata associated to each tuple it reads or writes. No centralized timestamp allocator exists, and concurrent transactions accessing disjoint data do not communicate, eliminating the timestamp allocation bottleneck. Second, by determining timestamps lazily at commit time, TicToc finds a logical-time order that enforces serializability even among transactions that overlap in physical time and would cause aborts in other T/O-based protocols. (See Figure 1.)  

Figure 1. Commit timestamp in TicToc is lazily computed based on the data access pattern of a transaction.

Figure 1. Commit timestamp in TicToc is lazily computed based on the data access pattern of a transaction.

In essence, TicToc allows commit timestamps to move forward in time to uncover more concurrency than existing schemes without violating serializability.

In the paper, we present a high-performance, OCC-based implementation of TicToc, and prove that it enforces serializability. We also design several optimizations that further improve TicToc’s scalability. Compared with four other modern concurrency control schemes in the DBx1000 main-memory DBMS, using two different OLTP workloads on a 4-socket, 80-core system, our results show that TicToc achieves up to 92% higher throughput than prior algorithms under a variety of workload conditions. (See Figure 2.)

Figure 2: TicToc achieves up to 92% higher throughput than prior algorithms under a variety of workload conditions.

Figure 2: TicToc achieves up to 92% higher throughput than prior algorithms under a variety of workload conditions.

As future work, we will generalize the TicToc algorithm to distributed transaction processing systems and study its scalability on a cluster of servers.

Download the paper:  TicToc: Time Traveling Optimistic Concurrency Control. Xiangyao Yu, Andrew Pavlo, Daniel Sanchez, Srinivas Devadas. Proceedings of SIGMOD, June 2016.

­­­­

This entry was posted in Big Data Architecture, Data Management, DBMS, ISTC for Big Data Blog, Math and Algorithms and tagged , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *


two × 7 =