Critical sections: re-emerging scalability concerns for database storage engines

ABSTRACT

Critical sections in database storage engines impact performance and scalability more as the number of hardware contexts per chip continues to grow exponentially. With enough threads in the system, some critical section will eventually become a bottleneck. While algorithmic changes are the only long-term solution, they tend to be complex and costly to develop. Meanwhile, changes in enforcement of critical sections require much less effort. We observe that, in practice, many critical sections are so short that enforcing them contributes a significant or even dominating fraction of their total cost and tuning them directly improves database system performance. The contribution of this paper is two-fold: we (a) make a thorough performance comparison of the various synchronization primitives in the database system developer's toolbox and highlight the best ones for practical use, and (b) show that properly enforcing critical sections can delay the need to make algorithmic changes for a target number of processors.

REFERENCES

• 1: Rakesh Agrawal , Michael J. Carey , Miron Livny, Concurrency control performance modeling: alternatives and implications, ACM Transactions on Database Systems (TODS), v.12 n.4, p.609-654, Dec. 1987 [doi>10.1145/32204.32220]
• 2: T. E. Anderson, The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.1 n.1, p.6-16, January 1990 [doi>10.1109/71.80120]
• 3: Mike Blasgen , Jim Gray , Mike Mitoma , Tom Price, The convoy phenomenon, ACM SIGOPS Operating Systems Review, v.13 n.2, p.20-25, April 1979 [doi>10.1145/850657.850659]
• 4: Michael J. Carey , David J. DeWitt , Michael J. Franklin , Nancy E. Hall , Mark L. McAuliffe , Jeffrey F. Naughton , Daniel T. Schuh , Marvin H. Solomon , C. K. Tan , Odysseas G. Tsatalos , Seth J. White , Michael J. Zwilling, Shoring up persistent applications, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.383-394, May 24-27, 1994, Minneapolis, Minnesota, United States
• 5: T. Craig. "Building FIFO and priority-queueing spin locks from atomic swap." Technical Report TR 93-02-02, University of Washington, Dept. of Computer Science, 1993.
• 6: Mikhail Fomitchev , Eric Ruppert, Lock-free linked lists and skip lists, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011776]
• 7: Vibby Gottemukkala , Tobin J. Lehman, Locking and Latching in a Memory-Resident Database System, Proceedings of the 18th International Conference on Very Large Data Bases, p.533-544, August 23-27, 1992
• 8: B. He, W. N. Scherer III, and M. L. Scott. "Preemption adaptivity in time-published queue-based spin locks." In Proc. HiPC, 2005.
• 9: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 10: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 11: R. Johnson, I. Pandis, N. Hardavellas, and A. Ailamaki. "Shore-MT: A Quest for Scalability in the Many-Core Era." CMU-CS-08-114.
• 12: Poonacha Kongetira , Kathirgamar Aingaran , Kunle Olukotun, Niagara: A 32-Way Multithreaded Sparc Processor, IEEE Micro, v.25 n.2, p.21-29, March 2005 [doi>10.1109/MM.2005.35]
• 13: Orran Krieger , Michael Stumm , Ron Unrau , Jonathan Hanna, A Fair Fast Scalable Rea,der-Writer Lock, Proceedings of the 1993 International Conference on Parallel Processing, p.201-204, August 16-20, 1993 [doi>10.1109/ICPP.1993.21]
• 14: Maged M. Michael, High performance dynamic lock-free hash tables and list-based sets, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564881]
• 15: Peter S. Magnusson , Anders Landin , Erik Hagersten, Queue Locks on Cache Coherent Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.165-171, April 01, 1994
• 16: John M. Mellor-Crummey , Michael L. Scott, Algorithms for scalable synchronization on shared-memory multiprocessors, ACM Transactions on Computer Systems (TOCS), v.9 n.1, p.21-65, Feb. 1991 [doi>10.1145/103727.103729]
• 17: John M. Mellor-Crummey , Michael L. Scott, Scalable reader-writer synchronization for shared-memory multiprocessors, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.106-113, April 21-24, 1991, Williamsburg, Virginia, United States
• 18: Ravi Rajwar , James R. Goodman, Speculative lock elision: enabling highly concurrent multithreaded execution, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 19: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 20: David P. Reed , Rajendra K. Kanodia, Synchronization with eventcounts and sequencers, Communications of the ACM, v.22 n.2, p.115-123, Feb. 1979 [doi>10.1145/359060.359076]
• 21: John T. Robinson, A fast general-purpose hardware synchronization mechanism, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.122-130, May 1985, Austin, Texas, United States
• 22: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• 23: Nir Shavit , Dan Touitou, Software transactional memory, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.204-213, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224987]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Experimentation, Performance