Transactional Massive-Parallel DBMSs: A New Wave
Abstract
A possibility to build unlimitedly scalable cluster-based systems has lead to strong activation of research and development of "shared-nothing" architectures of data management systems. Two camps has been established: "NoSQL" that refutes the main principles related with DBMSs and "one size doesn’t fit all" that emphasizes needs of systems’ specialization saving the most important features of DBMS. The most interesting seems to be a confrontation of these camps in the area of "transactional" data management systems. Based on the CAP-"theorem" of Eric Bruwer, representatives of the camp of NoSQL declines to support traditional features of ACID of database transactions. This paper discusses the essence of the Bruwer’s "theorem" and proves that this theorem does not any relation with the ACID features. The paper also overviews the most interesting modern research projects provided classic ACID-transactions in parallel shared-nothing environments and the soundest approaches that partially relaxes requirements of ACID by purely pragmatic reasons (but not at all in relation with the CAP "theorem").
References
1. Michael Stonebraker, Ugur Cetintemel. "One Size Fits All": An Idea Whose Time Has Come and Gone. Proceedings of the 21st International Conference on Data Engineering, 2005, pp. 2-11, http://www.cs.brown.edu/~ugur/fits_all.pdf.
2. Перевод на русский язык: Майкл Стоунбрейкер, Угур Кетинтемел. "Один размер пригоден для всех": идея, время которой пришло и ушло, 2007, http://citforum.ru/database/articles/one_size_fits_all/.
3. Jeffrey Dean, Sanjay Ghemawat. MapReduce: Simplifed Data Processing on Large Clusters, Proceedings of the Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004, pp. 137-150, http://labs.google.com/papers/mapreduce-osdi04.pdf.
4. Michael Stonebraker, David J. DeWitt. MapReduce: A major step backwards, Database Column, January 17, 2008, http://databasecolumn.vertica.com/database-innovation/mapreduce-a-major-step-backwards/.
5. Michael Stonebraker, David J. DeWitt. MapReduce II, Database Column, January 25, 2008, http://databasecolumn.vertica.com/database-innovation/mapreduce-ii/.
6. С.Д. Кузнецов. MapReduce: внутри, снаружи или сбоку от параллельных СУБД?, Труды Института системного программирования, т. 19, М., ИСП РАН, 2010, стр. 35-40, http://citforum.ru/database/articles/dw_appliance_and_mr/.
7. Pat Helland, Dave Campbell. Building on Quicksand. Proceedings of the Fourth Biennial Conference on Innovative Data Systems Research (CIDR 2009), January 4-7, 2009, Asilomar, Pacific Grove, CA USA,
8. http://www-db.cs.wisc.edu/cidr/cidr2009/Paper_133.pdf.
9. Перевод на русский язык: Пэт Хелланд, Дейв Кэмпбел. Дом на песке, 2010, http://citforum.ru/database/articles/quicksand/.
10. Eric Brewer, Towards Robust Distributed Systems, Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, July 2000, p. 7, http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf.
11. Daniel Abadi, Alexander Thomson. The problems with ACID, and how to fix them without NoSQL. DBMS Musings, August 31, 2010, http://dbmsmusings.blogspot.com/2010/08/problems-with-acid-and-how-to-fix-them.html.
12. Перевод на русский язык: Дэниел Абади и Александер Томсон. Проблемы с ACID, и как их устранить, не прибегая к использованию NoSQL, 2010, http://citforum.ru/gazeta/164/.
13. Tim Kraska, Martin Hentschel, Gustavo Alonso, Donald Kossmann. Consistency Rationing in the Cloud: Pay only when it matters. Proceedings of the 35th VLDB Conference, August 24-28, 2009, Lyon, France, pp. 253-264, http://www.dbis.ethz.ch/research/publications/ConsistencyRationing.pdf.
14. Перевод на русский язык: Тим Краска, Мартин Хеншель, Густаво Алонсо, Дональд Коссман. Рационализация согласованности в "облаках": не платите за то, что вам не требуется, 2010, http://citforum.ru/database/articles/kossmann_vldb_2009/.
15. Домашняя страница проекта H-store, 2010, http://hstore.cs.brown.edu/.
16. Официальный сайт компании VoltDB, 2010, http://voltdb.com/.
17. Michael Stonebraker. Errors in Database Systems, Eventual Consistency, and the CAP Theorem. BLOG@CACM, April 5, 2010, http://cacm.acm.org/blogs/blog-cacm/83396-errors-in-database-systems-eventual-consistency-and-the-cap-theorem/fulltext.
18. Перевод на русский язык: Майкл Стоунбрейкер. Ошибки в системах баз данных, согласованность "в конечном счете" и теорема CAP, 2010, http://citforum.ru/gazeta/154/.
19. Michael Stonebraker. Clarifications on the CAP Theorem and Data-Related Errors. VoltDB.com, October 21, 2010,
20. http://voltdb.com/blog/clarifications-cap-theorem-and-data-related-errors.
21. Перевод на русский язык: Майкл Стоунбрейкер. Уточнения по поводу теоремы CAP и ошибок, связанных с данными, 2010, http://citforum.ru/gazeta/169/.
22. Carlo Curino, Evan Jones, Yang Zhang, Sam Madden. Schism: a Workload-Driven Approach to Database Replication and Partitioning. 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 48-57,
23. http://db.csail.mit.edu/pubs/schism-vldb2010.pdf.
24. Перевод на русский язык: Карло Курино, Эван Джонс, Янг Жанг и Сэм Мэдден. Schism: управляемый рабочей нагрузкой подход к репликации и разделению баз данных, 2010, http://citforum.ru/database/articles/madden_vldb2010/.
25. Ippokratis Pandis, Ryan Johnson, Nikos Hardavellas, Anastasia Ailamaki. Data-Oriented Transaction Execution. 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 928-939, http://infoscience.epfl.ch/record/141326/files/pvldb10pandis.pdf.
26. Перевод на русский язык: Иппократис Пандис, Райан Джонсон, Никос Харадавеллас и Анастасия Айламаки. Выполнение транзакций, ориентированное на данные, 2010, http://citforum.ru/database/articles/ailamaki_vldb2010/.
27. Theo Haerder, Andreas Reuter. Principles of transaction-oriented database recovery. ACM Computing Surveys, Volume 15, Issue 4, December 1983, pp. 287 – 317, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5548&rep=rep1&type=pdf
28. Jim Gray, Paul McJones, Mike Blasgen, Bruce Lindsay, Raymond Lorie, Tom Price, Franco Putzolu, Irving Traiger. The recovery manager of the System R database manager. ACM Computing Surveys, Volume 13, Issue 2, June 1981, 223-242, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.9008&rep=rep1&type=pdf
29. Eric Brewer. A certain freedom: thoughts on the CAP theorem. Proceeding of the 29th ACM SIGACT-SIGOPS Symposium on Principles of distributed Computing, 2010, p. 335, http://portal.acm.org/citation.cfm?id=1835701.
30. Seth Gilbert, Nancy Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. ACM SIGACT News, Volume 33 Issue 2, June 2002, pp. 51-59, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.6951&rep=rep1&type=pdf
31. Julian Browne. Brewer's CAP Theorem, January 11, 2009, http://www.julianbrowne.com/article/viewer/brewers-cap-theorem.
32. Daniel Abadi. Problems with CAP, and Yahoo’s little known NoSQL system. DBMS Musings, April 23, 2010,
33. http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html.
34. 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, 2007, pp. 1150-1160, http://cs-www.cs.yale.edu/homes/dna/papers/vldb07hstore.pdf.
35. Перевод на русский язык: Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд. Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными, 2007, http://citforum.ru/database/articles/end_of_arch_era/.
36. M. Stonebraker, C. Bear, U. Cetintemel, M. Cherniack, T. Ge, N. Hachem, S. Harizopoulos, J. Lifter, J. Rogers, and S. Zdonik. One Size Fits All?— Part 2: Benchmarking Results. Proceedings of the Third Biennial Conference on Innovative Data Systems Research (CIDR 2007), January 7-10, 2007, Asilomar, Pacific Grove, CA USA, http://nms.csail.mit.edu/~stavros/pubs/osfa.pdf.
37. Перевод на русский язык: Майкл Стоунбрейкер, Чак Беэ, Угур Кетинтемел, Мич Черняк, Тиньян Ге, Набил Хачем, Ставрос Харизопулос, Джон Лифтер, Дженни Роджерс, Стэн Здоник. Пригоден ли один размер для всех? Часть 2: результаты тестовых испытаний, 2007, http://citforum.ru/database/articles/one_size_fits_all_2/.
38. Pat Helland. Life beyond Distributed Transactions: an Apostate's Opinion. Proceedings of the Third Biennial Conference on Innovative Data Systems Research (CIDR 2007), January 7-10, 2007, Asilomar, Pacific Grove, CA USA, http://web.mit.edu/tibbetts/Public/CIDR_2007_Proceedings/papers/cidr07p15.pdf.
39. Using VoltDB, V1.2, VoltDB, Inc., June 13, 2010, http://community.voltdb.com/docs/UsingVoltDB/index.
40. Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alexander Rasin, Stanley Zdonik, Evan P. C. Jones, Samuel Madden, Michael Stonebraker, Yang Zhang, John Hugg, Daniel J. Abad. HStore: A HighPerformance, Distributed Main Memory Transaction Processing System. Proceedings of the VLDB Endowment, Volume 1 Issue 2, August 2008, pp. 1496-1499,
41. http://cs-www.cs.yale.edu/homes/dna/papers/hstore-demo.pdf.
42. Evan P.C. Jones, Daniel J. Abadi, Samuel Madden. Low Overhead Concurrency Control for Partitioned Main Memory Databases. SIGMOD’10, Indianapolis, Indiana, USA, June 6–11, 2010, http://cs-www.cs.yale.edu/homes/dna/papers/hstore-cc.pdf.
43. Перевод на русский язык: Эван Джонс, Дэниэль Абади и Сэмуэль Мэдден. Управление параллелизмом с низкими накладными расходами для разделенных баз данных в основной памяти, 2010,
44. http://citforum.ru/database/articles/h-store-sigmod2010/.
45. Daniel Abadi, Alexander Thomson. The Case for Determinism in Database Systems. 36th International Conference on Very Large Data Bases, September 13-17, 2010, Singapore. Proceedings of the VLDB Endowment, Vol. 3, No. 1, 2010, pp. 70-80, http://db.cs.yale.edu/determinism-vldb10.pdf.
46. Перевод на русский язык: Дэниел Абади и Александер Томсон. Доводы в пользу детерминизма в системах баз данных, 2010, http://citforum.ru/database/articles/abadi_vldb2010/.
47. Stavros Harizopoulos, Daniel J. Abadi, Samuel Madden, Michael Stonebraker. OLTP Through the Looking Glass, and What We Found There, Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada, June 2008, pp. 981-992, http://db.cs.yale.edu/hstore/oltpperf-sigmod08.pdf.
48. Перевод на русский язык: Ставрос Харизопулос, Дэниэль Абади, Сэмюэль Мэдден, Майкл Стоунбрейкер. OLTP в Зазеркалье, 2010, http://citforum.ru/database/articles/oltp_lg/.
49. Домашняя страница проекта Shore, 2010, http://www.cs.wisc.edu/shore/.
50. G. Karypis. METIS— Family of Multilevel Partitioning Algorithms, 2010, http://glaros.dtc.umn.edu/gkhome/views/metis.
51. Домашняя страница проекта WEKA (Waikato Environment for Knowledge Analysis), 2010, http://www.cs.waikato.ac.nz/ml/index.html.
52. Домашняя страница проекта Shore-NT, 2010, http://www.cs.wisc.edu/shore-mt/.
53. R. Johnson, I. Pandis, N. Hardavellas, A. Ailamaki, and B. 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 (EDBT 2009), 2009, pp. 24-35,
54. http://diaswww.epfl.ch/shore-mt/papers/edbt09johnson.pdf.
55. Spinlock. Материал из Википедии – свободной энциклопедии, 2010, http://ru.wikipedia.org/wiki/Spinlock.
56. Сергей Кузнецов. Базы данных. Вводный курс. 13.3.1. Синхронизационные блокировки, 2008, http://citforum.ru/database/advanced_intro/41.shtml#13.3.1.
57. TPC BENCHMARK C. Standard Specification. Revision 5.11. Transaction Processing Performance Council, 2010, http://www.tpc.org/tpcc/spec/tpcc_current.pdf.
58. Daniela Florescu, Donald Kossmann. Rethinking Cost and Performance of Database Systems. SIGMOD Record, Vol. 38, No. 1, March 2009, pp. 43-48, http://www.dbis.ethz.ch/research/publications/sigrec08.pdf.
59. Перевод на русский язык: Даниела Флореску, Дональд Коссман. Переосмысление стоимости и производительности систем баз данных, 2009, http://citforum.ru/database/articles/rethinking/.
60. С.Д. Кузнецов. Год эпохи перемен в технологии баз данных. Труды Института системного программирования, т. 19, М., ИСП РАН, 2010, стр. 9-34, http://citforum.ru/database/articles/epoch/.
61. Werner Vogels. Data Access Patterns in the Amazon.com Technology Platform. Proceedings of the 33rd International Conference on Very Large Data Bases, Sep 2007, p. 1, http://www.vldb.org/archives/website/2007/program/videos/p1-vogels.wmv.
62. M. Brantner, D. Florescu, D. Graf, D. Kossmann, and T. Kraska. Building a Database on S3. Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada, June 2008, pp. 251–264, http://www.dbis.ethz.ch/research/publications/sigmod08-s3.pdf.
63. A. Tanenbaum and M. van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, Upper Saddle River, NJ, 2002.
64. Перевод на русский язык: Э. Таненбаум, М. ван Стеен. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003, 889 стр.
65. Н.А. Олифер, В.Г. Олифер, П.Б. Храмцов, В.И. Артемьев, С.Д. Кузнецов. Стратегическое планирование сетей масштаба предприятия. Центр Информационных Технологий, 1997, http://citforum.ru/nets/spsmp/.
66. Домашняя страница компании 28msec/проекта Sausalito, 2010, http://www.28msec.com/.
67. Домашняя страница Amazon Simple Storage Service (Amazon S3), 2010, http://aws.amazon.com/s3/.
68. Домашняя страница Amazon Elastic Compute Cloud (Amazon EC2), 2010, http://aws.amazon.com/ec2/.
69. XQuery 1.0: An XML Query Language (Second Edition), W3C Recommendation, 14 December 2010, http://www.w3.org/TR/xquery/.
70. Werner Vogels. Eventually Consistent. ACM Queue, Vol. 6 No. 6, October 2008, pp. 15-19, http://queue.acm.org/detail.cfm?id=1466448.
71. Matthias Brantner, Daniela Florescu, David Graf, Donald Kossmann, Tim Kraska. Building a Database in the Cloud. Technical Report, ETH Zurich, 2009, http://www.dbis.ethz.ch/research/publications/dbs3.pdf.
Review
For citations:
Kuznetsov S.D. Transactional Massive-Parallel DBMSs: A New Wave. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2011;20. (In Russ.)
Email this article 