Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Database engines face growing scalability challenges as core counts exponentially increase each processor generation, and the efficiency of synchronization primitives used to protect internal data structures is a crucial factor in overall database performance. The trade-offs between different implementation approaches for these primitives shift significantly with increasing degrees of available hardware parallelism. Blocking synchronization, which has long been the favored approach in database systems, becomes increasingly unattractive as growing core counts expose its bottlenecks. Spinning implementations improve peak system throughput by a factor of 2x or more for 64 hardware contexts, but suffer from poor performance under load.

In this paper we analyze the shifting trade-off between spinning and blocking synchronization, and observe that the trade-off can be simplified by isolating the load control aspects of contention management and treating the two problems separately: spinning-based contention management and blocking-based load control. We then present a proof of concept implementation that, for high concurrency, matches or exceeds the performance of both user-level spin-locks and the pthread mutex under a wide range of load factors.

REFERENCES

• 1: Gene M. Amdahl, Validity of the single processor approach to achieving large scale computing capabilities, Proceedings of the April 18-20, 1967, spring joint computer conference, April 18-20, 1967, Atlantic City, New Jersey [doi>10.1145/1465482.1465560]
• 2: 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]
• 3: L. Boguslavsky , K. Harzallah , A. Kreinen , K. Sevcik , A. Vainshtein, Optimal strategies for spinning and blocking, Journal of Parallel and Distributed Computing, v.21 n.2, p.246-254, May 1994 [doi>10.1006/jpdc.1994.1056]
• 4: Bryan M. Cantrill , Michael W. Shapiro , Adam H. Leventhal, Dynamic instrumentation of production systems, Proceedings of the annual conference on USENIX Annual Technical Conference, p.2-2, June 27-July 02, 2004, Boston, MA
• 5: 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
• 6: B. He, W. N. Scherer III, and M. L. Scott. "Preemption adaptivity in time-published queue-based spin locks." In Proc. HiPC, 2005.
• 7: Ryan Johnson , Ippokratis Pandis , Anastasia Ailamaki, Critical sections: re-emerging scalability concerns for database storage engines, Proceedings of the 4th international workshop on Data management on new hardware, June 13-13, 2008, Vancouver, Canada [doi>10.1145/1457150.1457157]
• 8: Ryan Johnson , Ippokratis Pandis , Nikos Hardavellas , Anastasia Ailamaki , Babak Falsafi, Shore-MT: a scalable storage manager for the multicore era, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia [doi>10.1145/1516360.1516365]
• 9: 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]
• 10: Nokia. Network Database Benchmark. Specification and reference implementation available online at http://hoslab.cs.helsinki.fi/homepages/ndbbenchmark/

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Operational analysis

  E. Data
  E.5 FILES
      Subjects: Organization/structure

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design, Management, Performance