Abstract
Future servers will be equipped with thousands of CPU cores and deep memory hierarchies. Traditional concurrency control (CC) schemes---both optimistic and pessimistic---slow down orders of magnitude in such environments for highly contended workloads. Optimistic CC (OCC) scales the best for workloads with few conflicts, but suffers from clobbered reads for high conflict workloads. Although pessimistic locking can protect reads, it floods cache-coherence backbones in deep memory hierarchies and can also cause numerous deadlock aborts.
This paper proposes a new CC scheme, mostly-optimistic concurrency control (MOCC), to address these problems. MOCC achieves orders of magnitude higher performance for dynamic workloads on modern servers. The key objective of MOCC is to avoid clobbered reads for high conflict workloads, without any centralized mechanisms or heavyweight interthread communication. To satisfy such needs, we devise a native, cancellable reader-writer spinlock and a serializable protocol that can acquire, release and re-acquire locks in any order without expensive interthread communication. For low conflict workloads, MOCC maintains OCC's high performance without taking read locks.
Our experiments with high conflict YCSB workloads on a 288-core server reveal that MOCC performs 8× and 23× faster than OCC and pessimistic locking, respectively. It achieves 17 million TPS for TPC-C and more than 110 million TPS for YCSB without conflicts, 170× faster than pessimistic methods.
- H. Berenson, P. A. Bernstein, J. Gray, J. Melton, E. J. O'Neil and P.E. O'Neil. A critique of ANSI SQL isolation levels. SIGMOD, pages 1--10, 1995. Google ScholarDigital Library
- M. J. Cahill, U. Röhm, and A. D. Fekete. Serializable isolation for snapshot databases. TODS, 34(4):20, 2009. Google ScholarDigital Library
- M. Cao, M. Zhang, A. Sengupta, and M. D. Bond. Drinking from both glasses: Combining pessimistic and optimistic tracking of cross-thread dependences. PPoPP, 2016. Google ScholarDigital Library
- T. Craig. Building FIFO and priority-queuing spin locks from atomic swap. University of Washington Technical Report TR 93-02-02, 1993. ftp://ftp.cs.washington.edu/tr/1993/02/UW-CSE-93-02-02.pdf.Google Scholar
- C. Curino, E. Jones, Y. Zhang, and S. Madden. Schism: a workload-driven approach to database replication and partitioning. VLDB, 3(1-2):48--57, 2010. Google ScholarDigital Library
- C. Diaconu, C. Freedman, E. Ismert, P.-A. Larson, P. Mittal, R. Stonecipher, N. Verma, and M. Zwilling. Hekaton: SQL server's memory-optimized OLTP engine. SIGMOD, 2013. Google ScholarDigital Library
- D. Dice, V. J. Marathe, and N. Shavit. Lock cohorting: A general technique for designing NUMA locks. PPoPP, 2012. Google ScholarDigital Library
- J. M. Faleiro and D. J. Abadi. Rethinking serializable multiversion concurrency control. PVLDB, 2015. Google ScholarDigital Library
- J. Gray and A. Reuter. Transaction Processing: Concepts and Techniques. 1st edition, 1992. Google ScholarDigital Library
- Hewlett Packard Enterprise. HPE Superdome Servers. https://www.hpe.com/us/en/servers/superdome.html.Google Scholar
- Hewlett Packard Labs. The Machine: A new kind of computer. http://labs.hpe.com/research/themachine/.Google Scholar
- R. Johnson, I. Pandis, and A. Ailamaki. Improving OLTP scalability using speculative lock inheritance. PVLDB, 2009. Google ScholarDigital Library
- R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and B. Falsafi. Shore-MT: a scalable storage manager for the multicore era. EDBT, pages 24--35, 2009. Google ScholarDigital Library
- R. Johnson, I. Pandis, R. Stoica, M. Athanassoulis, and A. Ailamaki. Aether: A scalable approach to logging. PVLDB, 3(1-2):681--692, 2010. Google ScholarDigital Library
- G. K. R. Kakivaya, D. N. Cutler, and J. M. Lyon. Concurrency-safe reader-writer lock with time out support. United States Patent US 6546443 B1, 1999.Google Scholar
- K. Kim, T. Wang, R. Johnson, and I. Pandis. ERMIA: Fast memory-optimized database system for heterogeneous workloads. SIGMOD, 2016. Google ScholarDigital Library
- H. Kimura. FOEDUS: OLTP engine for a thousand cores and NVRAM. SIGMOD, pages 691--706, 2015. Google ScholarDigital Library
- H. Kimura, G. Graefe, and H. A. Kuno. Efficient locking techniques for databases on modern hardware. ADMS'12.Google Scholar
- E. Koskinen and M. Herlihy. Dreadlocks: Efficient deadlock detection. SPAA, pages 297--303, 2008. Google ScholarDigital Library
- H. T. Kung and J. T. Robinson. On optimistic methods for concurrency control. ACM TODS, 6(2):213--226, June 1981. Google ScholarDigital Library
- L. Lamport. A new solution of dijkstra's concurrent programming problem. CACM, 17(8):453--455, Aug. 1974. Google ScholarDigital Library
- Y. Lev, V. Luchangco, and M. Olszewski. Scalable reader-writer locks. SPAA, pages 101--110, 2009. Google ScholarDigital Library
- J. Levandoski, D. Lomet, and S. Sengupta. The Bw-tree: A B-tree for new hardware platforms. ICDE, 2013. Google ScholarDigital Library
- J. Levandoski, D. Lomet, S. Sengupta, R. Stutsman, and R. Wang. High performance transactions in deuteronomy. CIDR, 2015.Google Scholar
- D. Lomet, A. Fekete, R. Wang, and P. Ward. Multi-version concurrency via timestamp range conflict managements. ICDE, pages 714--725, 2012. Google ScholarDigital Library
- D. B. Lomet. Key range locking strategies for improved concurrency. PVLDB, pages 655--664, 1993. Google ScholarDigital Library
- Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed GraphLab: a framework for machine learning and data mining in the cloud. PVLDB, 2012. Google ScholarDigital Library
- D. Makreshanski, J. Levandoski, and R. Stutsman. To lock, swap, or elide: on the interplay of hardware transactional memory and lock-free indexing. PVLDB, 2015. Google ScholarDigital Library
- Y. Mao, E. Kohler, and R. T. Morris. Cache craftiness for fast multicore key-value storage. EuroSys, pages 183--196, 2012. Google ScholarDigital Library
- J. M. Mellor-Crummey and M. L. Scott. Algorithms for scalable synchronization on shared-memory multiprocessors. TOCS, 9(1):21--65, 1991. Google ScholarDigital Library
- J. M. Mellor-Crummey and M. L. Scott. Scalable reader-writer synchronization for shared-memory multiprocessors. PPoPP, pages 106--113, 1991. Google ScholarDigital Library
- C. Mohan. ARIES/KVL: A key-value locking method for concurrency control of multiaction transactions operating on B-tree indexes. PVLDB, pages 392--405, 1990. Google ScholarDigital Library
- R. Morris. Counting large numbers of events in small registers. Communications of the ACM, 21(10):840--842, 1978. Google ScholarDigital Library
- K. Ren, J. Faleiro, and D. J. Abadi. Design principles for scaling multi-core oltp under high contention. SIGMOD'16. Google ScholarDigital Library
- K. Ren, A. Thomson, and D. J. Abadi. Lightweight locking for main memory database systems. PVLDB, 2012. Google ScholarDigital Library
- K. Ren, A. Thomson, and D. J. Abadi. An evaluation of the advantages and disadvantages of deterministic database systems. VLDB, 7(10):821--832, 2014. Google ScholarDigital Library
- M. L. Scott and W. N. Scherer. Scalable queue-based spin locks with timeout. PPoPP, pages 44--52, 2001. Google ScholarDigital Library
- SGI. UV3000. https://www.sgi.com/products/servers/uv/uv_3000_30.html.Google Scholar
- A. Thomasian. Distributed optimistic concurrency control methods for high-performance transaction processing. IEEE TKDE, 10(1):173--189, Jan 1998. Google ScholarDigital Library
- TPC. TPC benchmark E standard specification.Google Scholar
- S. Tu, W. Zheng, E. Kohler, B. Liskov, and S. Madden. Speedy transactions in multicore in-memory databases. SOSP, pages 18--32, 2013. Google ScholarDigital Library
- T. Wang, M. Chabbi, and H. Kimura. Be my guest: MCS lock now welcomes guests. PPoPP, pages 21:1--21:12, 2016. Google ScholarDigital Library
- T. Wang, R. Johnson, A. Fekete, and I. Pandis. The serial safety net: Efficient concurrency control on modern hardware. DaMoN, pages 8:1--8:8, 2015. Google ScholarDigital Library
- T. Wang and H. Kimura. Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores (Extended Version). Hewlett Packard Labs Technical Report HPE-2016-58, 2016. http://www.labs.hpe.com/techreports/2016/HPE-2016-58.pdf.Google Scholar
- P. S. Yu and D. M. Dias. Analysis of hybrid concurrency control schemes for a high data contention environment. IEEE Transactions on Software Engineering, 18(2):118--129, 1992. Google ScholarDigital Library
- X. Yu, G. Bezerra, A. Pavlo, S. Devadas, and M. Stonebraker. Staring into the abyss: An evaluation of concurrency control with one thousand cores. PVLDB, 2015. Google ScholarDigital Library
- X. Yu, A. Pavlo, D. Sanchez, and S. Devadas. Tictoc: Time traveling optimistic concurrency control. SIGMOD, pages 1629--1642, 2016. Google ScholarDigital Library
- M. Zhang, J. Huang, M. Cao, and M. D. Bond. Low-overhead software transactional memory with progress guarantees and strong semantics. PPoPP, pages 97--108, 2015. Google ScholarDigital Library
- O. Ziv et al. Composing concurrency control. PLDI, 2015. Google ScholarDigital Library
Index Terms
- Mostly-optimistic concurrency control for highly contended dynamic workloads on a thousand cores
Recommendations
Adaptive optimistic concurrency control for heterogeneous workloads
Optimistic concurrency control (OCC) protocols validate whether a transaction has conflicts with other concurrent transactions after this transaction completes its execution. In this work, we demonstrate that the validation phase has a great influence ...
Distributed optimistic concurrency control with reduced rollback
Concurrency control algorithms have traditionally been based on locking and timestamp ordering mechanisms. Recently optimistic schemes have been proposed. In this paper a distributed, multi-version, optimistic concurrency control scheme is described ...
Infinite Resources for Optimistic Concurrency Control
NetCompute '18: Proceedings of the 2018 Morning Workshop on In-Network ComputingOptimistic concurrency control (OCC) is inefficient for high-contention workloads. When concurrent transactions conflict, an OCC system wastes CPU resources verifying transactions, only to abort them. This paper presents a new system, called Network ...
Comments