Efficient bulk insertion into a distributed ordered table

ABSTRACT

We study the problem of bulk-inserting records into tables in a system that horizontally range-partitions data over a large cluster of shared-nothing machines. Each table partition contains a contiguous portion of the table's key range, and must accept all records inserted into that range. Examples of such systems include BigTable[8] at Google, and PNUTS [15] at Yahoo! During bulk inserts into an existing table, if most of the inserted records end up going into a small number of data partitions, the obtained throughput may be very poor due to ineffective use of cluster parallelism. We propose a novel approach in which a planning phase is invoked before the actual insertions. By creating new partitions and intelligently distributing partitions across machines, the planning phase ensures that the insertion load will be well-balanced. Since there is a tradeoff between the cost of moving partitions and the resulting throughput gain, the planning phase must minimize the sum of partition movement time and insertion time. We show that this problem is a variation of NP-hard bin-packing, reduce it to a problem of packing vectors, and then give a solution with provable approximation guarantees. We evaluate our approach on a prototype system deployed on a cluster of 50 machines, and show that it yields significant improvements over more naïve techniques.

REFERENCES

• 1: GridFTP. http://www.globus.org/grid_software/data/gridftp.php.
• 2: Hacmp for system p servers. http://www-03.ibm.com/systems/p/software/hacmp/index.html.
• 3: Oracle real application clusters 11g. http://www.oracle.com/technology/products/database/clustering/index.html.
• 4: Scalability and performance with oracle 11g database. http://www.oracle.com/technology/deploy/performance/pdf/db_perfscale_11gr1_twp.pdf, 2007.
• 5: Marcos K. Aguilera , Arif Merchant , Mehul Shah , Alistair Veitch , Christos Karamanolis, Sinfonia: a new paradigm for building scalable distributed systems, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 6: P. Bernstein, N. Dani, B. Khessib, R. Manne, and D. Shutt. Data management issues in supporting large-scale web services. IEEE Data Engineering Bulletin, December 2006.
• 7: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and zipf-like distributions: Evidence and implications. In Proc. INFOCOM, 1999.
• 8: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 9: Chandra Chekuri , Sanjeev Khanna, A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem, SIAM Journal on Computing, v.35 n.3, p.713-728, 2005 [doi>10.1137/S0097539700382820]
• 10: B. F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. Technical report, Yahoo! Research, 2008.
• 11: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 12: 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
• 13: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, Parallel sorting on a shared-nothing architecture using probabilistic splitting, Proceedings of the first international conference on Parallel and distributed information systems, p.280-291, December 1991, Miami, Florida, United States
• 14: Goetz Graefe, B-tree indexes for high update rates, ACM SIGMOD Record, v.35 n.1, p.39-44, March 2006 [doi>10.1145/1121995.1122002]
• 15: Community Systems Group, Community systems research at Yahoo!, ACM SIGMOD Record, v.36 n.3, September 2007 [doi>10.1145/1324185.1324195]
• 16: S. Hung and J. Fisk. An algorithm for 0-1 multiple knapsack problems. In Naval Res. Logist. Quart., pages 571--579, 1978.
• 17: H. V. Jagadish , P. P. S. Narayan , S. Seshadri , S. Sudarshan , Rama Kanneganti, Incremental Organization for Data Recording and Warehousing, Proceedings of the 23rd International Conference on Very Large Data Bases, p.16-25, August 25-29, 1997
• 18: R. Loulou and E. Michaelides. New greedy-like heuristics for the multidimensional 0-1 knapsack problem. Operations Research, 27:1101--1114, 1979.
• 19: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 20: S. Mishra. Loading bulk data into a partitioned table. http://www.microsoft.com/technet/prodtechnol/sql/bestpractice/loading_bulk_data_partitioned_table.mspx, September 2006.
• 21: C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
• 22: Patrick O'Neil , Edward Cheng , Dieter Gawlick , Elizabeth O'Neil, The log-structured merge-tree (LSM-tree), Acta Informatica, v.33 n.4, p.351-385, 1996 [doi>10.1007/s002360050048]
• 23: S. Senju and Y. Toyoda. An approach to linear programming with 0-1 variables. Management Science, 15(4):B196--B207, 1968.
• 24: S. Seshadri , Jeffrey F. Naughton, Sampling Issues in Parallel Database Systems, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.328-343, March 23-27, 1992
• 25: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 26: M. Vasquez and J. Hao. A hybrid approach for the 01 multidimensional knapsack problem. In IJCAI, pages 328--333, 2001.
• 27: Sage A. Weil , Scott A. Brandt , Ethan L. Miller , Darrell D. E. Long , Carlos Maltzahn, Ceph: a scalable, high-performance distributed file system, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 28: Janet L. Wiener , Jeffrey F. Naughton, OODB Bulk Loading Revisited: The Partitioned-List Approach, Proceedings of the 21th International Conference on Very Large Data Bases, p.30-41, September 11-15, 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Parallel databases

General Terms:
Performance

Keywords:
bulk loading, distributed and parallel databases, ordered tables