Транзакционные параллельные СУБД: новая волна

Сергей Кузнецов

Назад Содержание

4.2 Разным данным разная согласованность: новая парадигма транзакций?

В [9], как и в [38], речь идет о возможности реализации средств управления данными поверх "облачных" сред хранения данных. Основная идея исследования состоит в том, что не все данные требуется обрабатывать на одном и том же уровне согласованности (в этой статье делается попытка "примирить" понятия согласованности из областей баз данных и распределенных систем, хотя, на мой взгляд, это не всегда у авторов получается – С.К.). Например, в онлайновом магазине данные о кредитных картах клиентов и состоянии их счетов должны поддерживаться на более высоком уровне согласованности, чем данные о предпочтениях покупателей.

Поскольку существующие "облачные" платформы хранения данных предоставляют только базовые гарантии согласованности данных (согласованность в конечном счете), обеспечение дополнительных уровней согласованности значительно повышает стоимость выполнения операций. С другой стороны, стоимость несогласованности данных также можно измерить, оценив относительное число операций, которые выполняются некорректно из-за отсутствия согласованности, и переведя эту оценку в денежные расходы, которые должна понести компания, допустившая такое некорректное выполнение операций (например, для компенсации ущерба от ошибочно выполненных заказов).

Нахождение баланса между стоимостью выполнения операций, согласованностью данных и их доступностью является нетривиальной задачей. Этот баланс зависит от нескольких факторов, включая семантику приложений. Предлагается использовать динамическую стратегию поддержки согласованности данных – снижать уровень требований к согласованности, когда это не приводит к слишком большим убыткам, и повышать их, если убытки могут оказаться слишком большими. Авторы [9] называют этот подход рационализацией согласованности (consistency rationing) по аналогии с понятием рационализации управления запасами (inventory rationing), когда запасы отслеживаются с разной точностью в зависимости от их наличного объема.

При применении подхода рационализации согласованности все управляемые данные разделяются на три категории A, B и C, и для каждой категории применяются свои методы обработки в зависимости от обеспечиваемого уровня согласованности. К категории A относятся данные, нарушение согласованности которых привело бы к крупным убыткам. Несогласованность данных категории C является приемлемой (несогласованность либо вызывает лишь небольшие убытки, либо в действительности не возникает). Наконец, категория B включает данные, требования к согласованности которых изменяются во времени. Для данных категории B можно добиться оптимального соотношения расходов на выполнение операций и обеспечиваемого уровня согласованности.

Гарантии согласованности в [9] обеспечиваются для данных, а не для транзакций. Как утверждается, в результате ослабляются только свойства изоляции и согласованности ACID-транзакций, а атомарность и долговечность обеспечиваются в полном объеме. На самом деле, здесь нужно было бы привести определение возникающего понятия транзакции, но такое определение в [9] отсутствует, и придется обойтись предыдущим расплывчатым предложением. Для данных возможны два уровня согласованности – сессионная согласованность (session consistency) [47] и сериализуемость (serializability).

Сессионная согласованность данных подразумевает, что клиенты подключаются к системе в контексте сессий (что такое "сессия", ни в [9], ни в [47] не определяется – С.К.). Во время сессии система гарантирует монотонность по чтению собственных записей (read-your-own-writes monotonicity) (согласно [41], система "обладает свойством монотонности по чтению собственных записей, если удовлетворяется то условие, что результат записи процесса в элемент данных x всегда виден последующим операциям чтения x того же процесса" – С.К.). За границы сессии гарантии монотонности не распространяются: в новой сессии того же клиента могут быть не видны записи, произведенные в предыдущей сессии; в сессии одного клиента могут быть не видны записи, выполненные в сессии другого клиента. Сессионная согласованность поддерживается для данных категории C.

Для данных категории A обеспечивается сериализуемость в традиционном транзакционном смысле. Все транзакции, модифицирующие данные категории A, изолируются и оставляют данные согласованными (здесь имеются в виду и согласованность в смысле ACID, и строгая согласованность в смысле распределенных систем). Для поддержки сериализуемости требуются значительные накладные расходы, и данные следует относить к категории A, только если их согласованность и актуальность являются обязательными. В [9] для поддержки сериализуемости используется двухфазный протокол синхронизационных блокировок.

Для данных категории B во время работы системы на основе разработанных авторами политик производится переключение между режимами сессионной согласованности и сериализуемости. Если одна транзакция работает с некоторой записью в режиме сериализуемости, а другая обновляет ее в режиме сессионной согласованности, то обеспечивается сессионная согласованность (т.е., насколько я понимаю, транзакции, работающие с данными категории B в режиме сериализуемости, не изолируются от транзакций, работающих с теми же данными в режиме сессионной согласованности – С.К.).

Если в одной транзакции одновременно обрабатываются данные категорий A и C, то при выполнении операции чтения данных категории A эта транзакция всегда получает их последнее согласованное состояние и оставляет их согласованными после своей фиксации. При чтении данных категории C транзакция может получить их в несогласованном и/или устаревшем состоянии.

Как считают авторы [9] в ряде случаев можно будет разделить процессы разработки приложений и рационализации данных. В процессе разработки можно предполагать наличие традиционной согласованности данных и следовать обычной модели программирования с явно определяемыми транзакциями. На стадии внедрения приложения можно произвести рационализацию данных в соответствии с оценками расходов на выполнение операций и ущерба от несогласованности данных. Рационализацию мог бы производить специалист не из числа разработчиков приложения.

В [9] подробно описываются разработанные авторами политики переключения режимов согласованности для данных категории B, однако в данной статье я не хочу затрагивать эту тему, поскольку для наших целей она не очень важна. Не буду также говорить о деталях реализации разнообразных протоколов поддержки транзакций и согласованности данных, потому что в [9] эти вопросы освещены не слишком внятно, а в подробном техническом отчете [48] соответствующие описания занимают слишком много места.

Главный вывод, который, на мой взгляд, следует сделать на основе публикаций, посвященных Sausalito, состоит в том, что разработчики этой системы вполне смогли справиться с поддержкой ACID-транзакций и ослабляют требования к согласованности совсем не на основе ограничений, которые ставит теорема CAP, а с целью вполне разумной оптимизации стоимости службы управления данными.

5. Заключение

Основные цели этой статьи заключались в обсуждении истинной сути теоремы CAP и рассмотрении нескольких новых архитектур транзакционных СУБД, хорошо масштабируемых в динамических кластерных средах. Я попытался показать, что теорема CAP Эрика Брювера не имеет никакого отношения к возможности или невозможности поддержки ACID-транзакций в горизонтально масштабируемых кластерных системах.

Проект H-Store показывает, что в параллельной архитектуре shared-nothing основную проблему представляют распределенные транзакции, накладные расходы на фиксацию которых могут заметно снижать пропускную способность системы. Однако полученные результаты показывают, что для ряда важных типов рабочей нагрузки этих расходов можно избежать.

Другую проблему транзакционных параллельных систем без совместно используемых ресурсов составляет потребность в массовой физической пересылке данных при балансировке нагрузки. И здесь, как мне кажется, может несколько помочь подход проекта DORA, в котором вместо физического разделения данных в многоядерном компьютере используется их логическое разделение за счет наличия общей памяти.

Наконец, подход Sausalito показывает, во-первых, что при отказе от основных принципов разработки СУБД – контроля над данными и передачи запросов – в угоду более точному следованию архитектуре SOA расходы на поддержку ACID-транзакций существенно возрастают. Во-вторых, эта поддержка по-прежнему возможна, и разумна оптимизация системы управления данными, позволяющая снизить расходы на управление транзакциями, если приложениям не требуется качественная согласованность данных.

По всей видимости, исследования и разработки массивно-параллельных транзакционных СУБД в ближайшие годы будут активно продолжаться, и нам предстоит еще увидеть и услышать много интересного.

6. Литература

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.
   Перевод на русский язык: Майкл Стоунбрейкер, Угур Кетинтемел. "Один размер пригоден для всех": идея, время которой пришло и ушло, 2007.
2. 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.
3. Michael Stonebraker, David J. DeWitt. MapReduce: A major step backwards, Database Column, January 17, 2008.
4. Michael Stonebraker, David J. DeWitt. MapReduce II, Database Column, January 25, 2008.
5. С.Д. Кузнецов. MapReduce: внутри, снаружи или сбоку от параллельных СУБД?, Труды Института системного программирования, т. 19, М., ИСП РАН, 2010, стр. 35-40.
6. 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.
   Перевод на русский язык: Пэт Хелланд, Дейв Кэмпбел. Дом на песке, 2010.
7. Eric Brewer, Towards Robust Distributed Systems, Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, July 2000, p. 7.
8. Daniel Abadi, Alexander Thomson. The problems with ACID, and how to fix them without NoSQL. DBMS Musings, August 31, 2010.
   Перевод на русский язык: Дэниел Абади и Александер Томсон. Проблемы с ACID, и как их устранить, не прибегая к использованию NoSQL, 2010.
9. 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.
   Перевод на русский язык: Тим Краска, Мартин Хеншель, Густаво Алонсо, Дональд Коссман. Рационализация согласованности в "облаках": не платите за то, что вам не требуется, 2010.
10. Домашняя страница проекта H-store, 2010.
11. Официальный сайт компании VoltDB, 2010.
12. Michael Stonebraker. Errors in Database Systems, Eventual Consistency, and the CAP Theorem. BLOG@CACM, April 5, 2010.
    Перевод на русский язык: Майкл Стоунбрейкер. Ошибки в системах баз данных, согласованность "в конечном счете" и теорема CAP, 2010.
13. Michael Stonebraker. Clarifications on the CAP Theorem and Data-Related Errors. VoltDB.com, October 21, 2010.
    Перевод на русский язык: Майкл Стоунбрейкер. Уточнения по поводу теоремы CAP и ошибок, связанных с данными, 2010.
14. 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.
    Перевод на русский язык: Карло Курино, Эван Джонс, Янг Жанг и Сэм Мэдден. Schism: управляемый рабочей нагрузкой подход к репликации и разделению баз данных, 2010.
15. 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.
    Перевод на русский язык: Иппократис Пандис, Райан Джонсон, Никос Харадавеллас и Анастасия Айламаки. Выполнение транзакций, ориентированное на данные, 2010.
16. Theo Haerder, Andreas Reuter. Principles of transaction-oriented database recovery. ACM Computing Surveys, Volume 15, Issue 4, December 1983, pp. 287 - 317.
17. 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.
18. 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.
19. 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.
20. Julian Browne. Brewer's CAP Theorem, January 11, 2009.
21. Daniel Abadi. Problems with CAP, and Yahoo’s little known NoSQL system. DBMS Musings, April 23, 2010.
22. 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.
    Перевод на русский язык: Майкл Стоунбрейкер, Сэмюэль Мэдден, Дэниэль Абади, Ставрос Харизопулос, Набил Хачем, Пат Хеллэнд. Конец архитектурной эпохи, или Наступило время полностью переписывать системы управления данными, 2007.
23. 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.
    Перевод на русский язык: Майкл Стоунбрейкер, Чак Беэ, Угур Кетинтемел, Мич Черняк, Тиньян Ге, Набил Хачем, Ставрос Харизопулос, Джон Лифтер, Дженни Роджерс, Стэн Здоник. Пригоден ли один размер для всех? Часть 2: результаты тестовых испытаний, 2007.
24. 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.
25. Using VoltDB, V1.2, VoltDB, Inc., June 13, 2010.
26. 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.
27. 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.
    Перевод на русский язык: Эван Джонс, Дэниэль Абади и Сэмуэль Мэдден. Управление параллелизмом с низкими накладными расходами для разделенных баз данных в основной памяти, 2010.
28. 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.
    Перевод на русский язык: Дэниел Абади и Александер Томсон. Доводы в пользу детерминизма в системах баз данных, 2010.
29. 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.
    Перевод на русский язык: Ставрос Харизопулос, Дэниэль Абади, Сэмюэль Мэдден, Майкл Стоунбрейкер. OLTP в Зазеркалье, 2010.
30. Домашняя страница проекта Shore, 2010.
31. G. Karypis. METIS - Family of Multilevel Partitioning Algorithms, 2010.
32. Домашняя страница проекта WEKA (Waikato Environment for Knowledge Analysis), 2010.
33. Домашняя страница проекта Shore-NT, 2010.
34. 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.
35. Spinlock. Материал из Википедии – свободной энциклопедии, 2010
36. Сергей Кузнецов. Базы данных. Вводный курс. 13.3.1. Синхронизационные блокировки, 2008.
37. TPC BENCHMARK C. Standard Specification. Revision 5.11. Transaction Processing Performance Council, 2010.
38. Daniela Florescu, Donald Kossmann. Rethinking Cost and Performance of Database Systems. SIGMOD Record, Vol. 38, No. 1, March 2009, pp. 43-48.
    Перевод на русский язык: Даниела Флореску, Дональд Коссман. Переосмысление стоимости и производительности систем баз данных, 2009.
39. 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.
40. 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.
41. A. Tanenbaum and M. van Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, Upper Saddle River, NJ, 2002.
    Перевод на русский язык: Э. Таненбаум, М. ван Стеен. Распределенные системы. Принципы и парадигмы. СПб.: Питер, 2003, 889 стр.
42. Н.А. Олифер, В.Г. Олифер, П.Б. Храмцов, В.И. Артемьев, С.Д. Кузнецов. Стратегическое планирование сетей масштаба предприятия. Центр Информационных Технологий, 1997.
43. Домашняя страница компании 28msec/проекта Sausalito, 2010.
44. Домашняя страница Amazon Simple Storage Service (Amazon S3), 2010.
45. Домашняя страница Amazon Elastic Compute Cloud (Amazon EC2), 2010.
46. XQuery 1.0: An XML Query Language (Second Edition), W3C Recommendation, 14 December 2010.
47. Werner Vogels. Eventually Consistent. ACM Queue, Vol. 6 No. 6, October 2008, pp. 15-19.
48. Matthias Brantner, Daniela Florescu, David Graf, Donald Kossmann, Tim Kraska. Building a Database in the Cloud. Technical Report, ETH Zurich, 2009.

Назад Содержание