Shore-MT: a scalable storage manager for the multicore era

ABSTRACT

Database storage managers have long been able to efficiently handle multiple concurrent requests. Until recently, however, a computer contained only a few single-core CPUs, and therefore only a few transactions could simultaneously access the storage manager's internal structures. This allowed storage managers to use non-scalable approaches without any penalty. With the arrival of multicore chips, however, this situation is rapidly changing. More and more threads can run in parallel, stressing the internal scalability of the storage manager. Systems optimized for high performance at a limited number of cores are not assured similarly high performance at a higher core count, because unanticipated scalability obstacles arise.

We benchmark four popular open-source storage managers (Shore, BerkeleyDB, MySQL, and PostgreSQL) on a modern multicore machine, and find that they all suffer in terms of scalability. We briefly examine the bottlenecks in the various storage engines. We then present Shore-MT, a multithreaded and highly scalable version of Shore which we developed by identifying and successively removing internal bottlenecks. When compared to other DBMS, Shore-MT exhibits superior scalability and 2--4 times higher absolute throughput than its peers. We also show that designers should favor scalability to single-thread performance, and highlight important principles for writing scalable storage engines, illustrated with real examples from the development of Shore-MT.

REFERENCES

• 1: Oracle BerkeleyDB. http://www.oracle.com/technology/products/berkeley-db/index.html
• 2: MySQL. http://www.mysql.com.
• 3: A. Ailamaki, D. J. DeWitt, and M. D. Hill. "Walking Four Machines By The Shore." In Proc. CAECW, 2001.
• 4: Roger Bamford , D. Butler , Boris Klots , N. MacNaughton, Architecture of Oracle Parallel Server, Proceedings of the 24rd International Conference on Very Large Data Bases, p.669-670, August 24-27, 1998
• 5: Philip A. Bernstein , Nathan Goodman, Multiversion concurrency control—theory and algorithms, ACM Transactions on Database Systems (TODS), v.8 n.4, p.465-483, Dec. 1983 [doi>10.1145/319996.319998]
• 6: Edouard Bugnion , Scott Devine , Mendel Rosenblum, Disco: running commodity operating systems on scalable multiprocessors, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.143-156, October 05-08, 1997, Saint Malo, France
• 7: 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
• 8: Hong-Tai Chou , David J. DeWitt, An evaluation of buffer management strategies for relational database systems, Proceedings of the 11th international conference on Very Large Data Bases, p.127-141, August 21-23, 1985, Stockholm, Sweden
• 9: 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.
• 10: John D. Davis , James Laudon , Kunle Olukotun, Maximizing CMP Throughput with Mediocre Cores, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.51-62, September 17-21, 2005 [doi>10.1109/PACT.2005.42]
• 11: Giuseppe DeCandia , Deniz Hastorun , Madan Jampani , Gunavardhan Kakulapati , Avinash Lakshman , Alex Pilchin , Swaminathan Sivasubramanian , Peter Vosshall , Werner Vogels, Dynamo: amazon's highly available key-value store, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 12: D. J. Dewitt , S. Ghandeharizadeh , D. A. Schneider , A. Bricker , H. -I. Hsiao , R. Rasmussen, The Gamma Database Machine Project, IEEE Transactions on Knowledge and Data Engineering, v.2 n.1, p.44-62, March 1990 [doi>10.1109/69.50905]
• 13: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 14: Dimitris Fotakis , Rasmus Pagh , Peter Sanders , Paul G. Spirakis, Space Efficient Hash Tables with Worst Case Constant Access Time, Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, p.271-282, February 27-March 01, 2003
• 15: J. Gray. "Tape is Dead, Disk is Tape, Flash is Disk, RAM Locality is King." Gong Show Presentation at CIDR, 2007.
• 16: Jim Gray , Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1992
• 17: B. He, W. N. Scherer III, and M. L. Scott. "Preemption Adaptivity in Time-Published Queue-Based Spin Locks." In Proc. HiPC, 2005.
• 18: P. Helland. "Life beyond Distributed Transactions: an Apostate's Opinion." In Proc. CIDR, 2007.
• 19: J. M. Hellerstein, and M. Stonebraker. "Anatomy of a Database System." In Readings in Database Systems, 4th ed.
• 20: 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]
• 21: 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]
• 22: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• 23: 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
• 24: 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]
• 25: C. Mohan, ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes, Proceedings of the 16th International Conference on Very Large Data Bases, p.392-405, August 13-16, 1990
• 26: C. Mohan , Frank Levine, ARIES/IM: an efficient and high concurrency index management method using write-ahead logging, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.371-380, June 02-05, 1992, San Diego, California, United States
• 27: Rasmus Pagh , Flemming Friche Rodler, Cuckoo Hashing, Proceedings of the 9th Annual European Symposium on Algorithms, p.121-133, August 28-31, 2001
• 28: Parthasarathy Ranganathan , Kourosh Gharachorloo , Sarita V. Adve , Luiz André Barroso, Performance of database workloads on shared-memory systems with out-of-order processors, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.307-318, October 02-07, 1998, San Jose, California, United States
• 29: Yaoping Ruan , Vivek S. Pai , Erich Nahum , John M. Tracey, Evaluating the impact of simultaneous multithreading on network servers using real hardware, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
• 30: Michael Stonebraker , Lawrence A. Rowe, The design of POSTGRES, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.340-355, May 28-30, 1986, Washington, D.C., United States
• 31: Michael Stonebraker , Samuel Madden , Daniel J. Abadi , Stavros Harizopoulos , Nabil Hachem , Pat Helland, The end of an architectural era: (it's time for a complete rewrite), Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 32: Mikkel Thorup, Even strongly universal hashing is pretty fast, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.496-497, January 09-11, 2000, San Francisco, California, United States
• 33: TPC (Transaction Processing Performance Council). TPC Benchmark C (OLTP) Standard Specification, Revision 5.9.