Дом на песке

2010 г.

Дом на песке

Пэт Хелланд, Дейв Кэмпбел
Перевод: Сергей Кузнецов

8. CAP и ACID2.0

Как отмечалось выше, в теореме CAP [13, 14] утверждается, что из трех свойств – Consistency, Availability и Partition-tolerance (согласованность, доступность и терпимость к разделению) можно удовлетворить любые два, но не все три сразу. Мы с этим не спорим.

Однако интересно то, что под "согласованностью" в этой теореме понимается согласованность в смысле классических ACID-транзакций (Atomic, Consistent, Isolated и Durable – атомарность, согласованность, изолированность и долговечность). Целью ACID-транзакций является создание для каждого приложения такой среды, в которой якобы имеется только один компьютер, и он не делает ничего другого при обработке данной транзакции.

Рассмотрим новые свойства ACID (или ACID2.0). Эта аббревиатура раскрывается как Associative, Commutative, Idempotent и Distributed (ассоциативность, коммутативность, идемптентность и распределенность) [17]. ACID2.0-работа считается успешно выполненной, если каждая из ее частей выполнена

по крайней мере, один раз,
где бы то ни было в системе,
в любом порядке.

Таким образом определяется новый ВИД согласованности. Отдельные шаги выполняются в одной или нескольких системах. Приложение является явным образом устойчивым к изменению порядка работы. Оно также устойчиво к неоднократному выполнению одного и того же шага.

Заметим, что примеры 4 (корзина покупок) и 5 (обработка чеков) соответствуют этому стилю согласованности.

8.1 Отказоустойчивость при наличии ACID

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

При анализе абстракции отказоустойчивости, описанной в разд. 2, мы видем, что во главе угла находятся синхронные контрольные точки и линейная история. Если корректность определяется в соответствии с классическими свойствами ACID, то важно обеспечить упорядоченность транзакций. И это, конечно, сериализуемость [3, 10, 12].

Интересно сопоставить пример 1 (Tandem образца 1984 г.) и пример 2 (Tandem образца 1986 г.). В примере 1 установка контрольных точек с резервной системой происходит на основе операций записи и чтения. Это корректно, но не обязательно обеспечивает высокую производительность. В примере 2 синхронизация состояния происходит при завершении транзакции. Внутритранзакционным параллелизмом управляют традиционные методы СУБД. Только после завершения транзакции требуется гарантировать, что выполненная работа переживет отказ.

8.2 Отказоустойчивость при наличии ACID2.0

OK, посмотрим, что происходит с понятием отказоустойчивости когда вы НЕ стремитесь к сериализуемости (классические свойства ACID), а довольствуетесь новыми свойствами ACID – ассоциативностью, коммутативностью, идемпотентностью и распределенностью.

Если вы разбиваете алгоритм выполнения требуемой работы на части, то каждая часть должна быть идемпотентной (точно так же, как в базовом подходе к отказоустойчивости). Кроме того, мы считаем, что работа распределена по сети, а не сконцентрирована в какой-либо централизованной системе. Единственным способом обеспечить эту возможность при сохранении классических ACID-гарантий является использование хорошо описанных пессимистических или оптимистических механизмов управления параллелизмом. Обычно они являются взаимозаменяемыми.

Если приложение ограничивается дополнительными требованиями коммутативности и ассоциативности, мир становится ГОРАЗДО проще. Тогда не нужно больше согласовывать состояния основной и резервной систем в синхронном режиме. Можно очень пассивно относиться к совместно используемой информации. Это делает возможной автономную работу, использование медленных каналов связи, применение низкокачественных центров данных и т.д.

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

9. Предстоящая работа

По-видимому, было бы очень полезно проанализировать разные приложения в бизнес-среде, чтобы обнаружить повторяющиеся схемы их организации. Что за операции используются в различных приложениях? Когда они являются коммутативными? Какие приемы делают их идемпотентными? Имеются ли решения, для которых требуется лишь синтаксическая переработка для применения в разных средах? Имеется ли таксономия паттернов, к которым могут приводиться различные решения?

Наши предки были ОЧЕНЬ умны и для реализации своего бизнеса использовали слабо связанные системы. Они соединяли слабо связанные системы с использованием телеграмм, писем и почтовых систем. Для функционирования этих систем требовались переупорядочиваемые операции. Иногда одна и та же работа запрашивалась дважды, и в этих случаях требовались протоколы, поддерживающие идемпотентность. Как использовались эти схемы при прокладывании железных дорог и построении фордовских автомобилей серии Model-T? Не ждут ли эти паттерны своего использования в современных распределенных системах?

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

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

Многие годы технология построения отказоустойчивых систем обеспечивала их строгое транзакционное поведение за счет синхронной установки контрольных точек на границах отказов. По мере возрастания размеров единицы отказа задержки, вызываемые операцией установки контрольных точек, выросли настолько, что стали обременительными.

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

Мы постарались описать паттерны, используемые во многих современных приложениях для борьбы с отказами в территориально распределенных системах. Для обеспечения успешного выполнения приложений поверх хаоса распределенного мира требуются возможности переупорядочивания и повторяемости работ. Разработчики приложений интуитивно тяготеют к миру согласованности "рано или поздно" (обычно без использования формализмов, которые могли бы помочь им добиться успеха).

Наконец, мы проанализировали эти идеи, принимая во внимание теорию CAP, и показали, что в этом новом мире многие решения разрабатываются в расчете на некоторое ослабление классической согласованности для поддержки доступности и устойчивости к разделению. Это ослабленное понятие согласованности очень полезно и заслуживает больших академических исследований.

11. Благодарности

Мы хотим поблагодарить Декстера Барнеса (Dexter Barnes) и Свами Сивасубраманьяна (Swami Sivasubramanian) за их комментарии к этой статье.

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

John von Neumann, Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components, Automata Studies, Princeton University Press (1956).
Robert M. Pirsig, Zen and the Art of Motorcycle Maintenance: An Inquiry into Values. New York, Quill. 25th Anniversary Edition, ISBN: 0688171664 (1974). Перевод на русский язык М.Немцова: Роберт М. Пирсиг. Цзэн и искусство ухода за мотоциклом: исследование ценностей
Jim Gray, Notes on Data Base Operating Systems, Lecture Notes in Computer Science (60): 393-481 Springer-Verlag (1978).
Andrea Borr, Transaction Monitoring in ENCOMPASS, Proceedings of the 7th VLDB (September 1981).
Joel Bartlett, A NonStop Kernel, Proceedings of the Eighth Symposium on Operating Systems Principles (SOSP). Pp. 22-29. December, 1981.
L. Lamport, R. Shostak, and M. Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems 4 (3): 382-401. (July 1982)
Andrea Borr, Robustness to Crash in a Distributed Database: A Non Shared-Memory Multi-Processor Approach, Proceedings of the 9th VLDB (September 1984). Also Tandem Computers TR 84.2
Jim Gray, Why Do Computers Stop and What Can Be Done About It?, Tandem Computers TR85.7
O’Neil, Pat, The Escrow Transactional Method, ACT Transactions on Database Systems (TODS), Volume 11, Issue 4 (December 1986).
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman, Concurrency Control and Recovery in Database Systems. Addison-Wesley Longman (1987).
Pat Helland, Harald Sammer, Jim Lyon, Richard Carr, Phil Garrett, Andreas Reuter, Group Commit Timers and High Volume Transaction Systems, Proceedings of the 2nd International Workshop on High Performance Transaction Systems, also Lecture Notes in Computer Science, vol 359, Springer-Verlag, 1987.
Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann Publishers, Inc. 1993.
Eric Brewer, Towards Robust Distributed Systems, PODC (Principles of Distributed Computing) Keynote (July 2000)
Seth Gilbert and Nancy Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, and Partition-Tolerant Web Services, ACM SIGACT News, Volume 33, Issue 2 (June 2002).
Pat Helland, Life Beyond Distributed Transactions an Apostate’s Opinion, Conference on Innovative Database Research (CIDR) January 2007.
Pat Helland, Memories, Guesses, and Apologies, Blog entry (May 2007).
Shel Finkelstein invented the clever new acronym for ACID. Captured in private communication (September 2007).
Guiseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swami Sivasubramanian, Peter Vosshall and Werner Vogels, Dynamo: Amazon's Highly Available Key-Value Store, 21st ACM Symposium on Operating Systems Principles, Stevenson, WA, October 2007.
Pat Helland, The Irresistible Forces Meet the Movable Objects, Microsoft TechEd Developers EMEA Keynote, Barcelona, Spain (November 2007).
Werner Vogel. Eventually Consistent, ACM Queue Vol. 6, Number 6. October 2008.
Wikipedia. Futures Contract.

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