Logo Море(!) аналитической информации!
IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Ошибки в системах баз данных, согласованность "в конечном счете" и теорема CAP

Оригинал: Michael Stonebraker. Errors in Database Systems, Eventual Consistency, and the CAP Theorem. BLOG@CACM, April 5, 2010

От переводчика, или об уместности применения теорем и потребности в среднем классе

Честно скажу, что не люблю переводить заметки, публикуемые в блогах. Не тот это жанр. Обычно авторы подобных заметок совершенно не стремятся к достижению высокого качества текста, для них главное – побыстрее высказаться на интересующую их тему. И, по-видимому, опыт перевода заметки Майкла Стоунбрейкера, предлагаемого вашему вниманию, – это одно из исключений из моих правил (возможно, я позволю себе еще несколько таких исключений). Постараюсь объяснить, почему я решился на это деяние.

Во-первых, меня уже сравнительно давно раздражают повсеместные ссылки на теорему CAP Эрика Брювера (Eric Brewer; кстати, наверное, правильнее называть его по-русски Брюером, но я буду продолжать использовать свой вариант). Во-первых, заметьте, что поголовно все ссылаются на публикацию [1], которая даже не является статьей, а всего лишь представляет собой набор небольшого числа слайдов, в которых, естественно, отсутствуют какие-либо пояснения. Поэтому теорема CAP, которая гласит, что в одной распределенной системе невозможно одновременно обеспечить свойства согласованности, высокой доступности и устойчивости к разделению сети, часто интерпретируется, на мой взгляд, спекулятивным образом.

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

Чтобы не быть голословным, поясню, по какой причине я не уверен в абсолютной правоте Майкла Стоунбрейкера. Прочитав заметку, вы увидите, что больше всего в ней говорится об исключительно небольшой вероятности основного случая, для которого, собственно, и вводится понятие "согласованности в конечном счете" (eventual consistency), – разделения сети на несколько участков, каждый из которых содержит несколько обрабатывающих узлов. Возможно, это так на самом деле. Но у меня имеется подозрение, что к такому разделению совсем не устойчива архитектура системы H-Store, положенная в основу новой коммерческой OLTP-ориентированной СУБД VoltDB (отцом-основателем этого стартапа, естественно, является Стоунбрейкер). Очень может быть, что в VoltDB со временем будут подкручены какие-то гайки, и мнение Майкла изменится. Может быть, я и ошибаюсь, посмотрим.

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

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

Так вот, все комментарии к заметки Стоунбрейкера интересны и написаны людьми грамотными и квалифицированными. Первый комментатор – Дуайт Мерримен (Dwight Merriman) – является основателем компании 10gen и одним из лидеров проекта MongoDB. Аларик Снелл-Пим (Alaric Snell-Pym) – главный архитектор компании GenieDB, разрабатывающей новую СУБД для использования в "облачной" инфраструктуре. Майкл Мелоун (Michael Malone) отвечает за создание сильно масштабируемых приложений в компании SimpleGeo. Расселл Окамото (Russell Okamoto) занимает руководящий пост в компании GemStone И так далее. Всем этим людям небезразличны распределенные системы управления данными, у них имеется своя точка зрения на теорему CAP и согласованность в конечном счете. Их комментарии все по делу (хотя местами имеют маркетинговый акцент).

Хочу, чтобы и в русском Internet на технические статьи писались заинтересованные и грамотные комментарии. Чтобы было кому их писать... Честно говоря, и статей хотелось бы видеть, мягко говоря, побольше. А для этого нужно, чтобы у людей были желание и потребность их писать. Нужно, чтобы были отечественные исследовательские и коммерческие проекты, связанные с разработкой новых систем управления данными, чтобы возникали свои стартапы. Даешь средний класс сообщества баз данных в России!

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

В последнее время возродился значительный интерес с теореме CAP [1], которая имеет отношение к приложениям систем управления базами данных (СУБД), выполяемых в нескольких узлах сети. Коротко говоря, в этой теореме утверждается, что имеются три интересных свойства, которые могли бы потребоваться в приложениях СУБД:

C: Consistency (согласованность). Цель состоит в том, что позволить многоузловым транзакциям иметь знакомую семантику "все-или-ничего", обычно поддерживаемую коммерческими СУБД. Кроме того, в тех случаях, когда поддерживаются реплики, можно было бы пожелать, чтобы реплики находились в согласованном состоянии.

A: Avalability (доступность). Цель состоит в поддержке СУБД, которая всегда находится в состоянии готовности. Другими словами, если происходит какой-либо сбой, система должна оставаться работоспособной, переключаясь при надобности на какую-нибудь реплику. Это свойство популяризировалось компанией Tandem Computers более 20 лет тому назад.

P: Partition-tolerance (устойчивость к разделению). Если возникает сбой в работе сети, приводящий в расщеплению узлов обработки на две группы, которые не могут общаться, то цель состоит в том, чтобы допустить возможность продолжения обработки в обеих этих группах.

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

В сообществе NoSQL эта теорема используется для обоснования жертвования согласованностью. Поскольку в большинстве систем NoSQL обычно не допускаются транзакции, распространяющиеся за границы одного узла, согласованность распространяется только на реплики. Следовательно, теорема CAP используется для обоснования отказа от согласованности реплик, и эта цель заменяется "согласованностью в конечном счете" ("eventual consistency"). При использовании этого ослабленного понятия единственной гарантией является то, что реплики когда-нибудь придут к одному и тому же состоянию, т.е. это произойдет, когда связность сети восстановится, и после этого пройдет достаточное время для очистки реплик. Обоснованием жертвования свойством C является возможность обеспечения свойств A и P.

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

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

  1. Ошибки в приложениях. Приложение выполняет одну или несколько некорректных операций обновления данных. Как правило, это обнаруживается в течение нескольких минут, а иногда и нескольких часов. Базу данных необходимо откатить к точке, предшествующей выполнению транзакции-нарушителя (или нескольких таких транзакций) и повторно воспроизвести последующие активности.
  2. Повторяющиеся ошибки СУБД. СУБД "падает" в некотором узле обработки. Выполнение той же транзакции в узле обработки, содержащем реплику требуемых данных, приводит к "падению" этой резервной копии. Такие ошибки называют "борбагами" (Bohr bug) [2].
  3. Неповторяющиеся ошибки СУБД. СУБД "падает", но при работе с репликой данных, вроде бы, все в порядке. Так часто случается при наличии асинхронных операций, и подобные ошибки называют "гейзенбагами" (Heisenbug) [2].
  4. Ошибки операционной системы. В некотором узле "падает" ОС, демонстрируя "синий экран смерти" ("blue screen of death").
  5. Сбой аппаратуры в локальном кластере. К числу таких ситуаций относятся сбои основной памяти, дисков и т.д. Обычно это приводит к аварийному останову ОС или СУБД. Однако иногда такие сбои проявляются в виде гейзенбагов.
  6. Разделение сети в локальном кластере. В результате сбоя в работе локальной сети узлы кластера не могут больше общаться.
  7. Стихийное бедствие. Локальный кластер уничтожается в результате наводнения, землетрясения и т.д. Кластер больше не существует.
  8. Сбой в работе сетевой аппаратуры, связывающей кластеры в территориально-распределенную сеть. В результате кластеры не могут больше общаться.
Заметим теперь, что ошибки i и ii вызывают проблемы при использовании любой схемы обеспечения высокого уровня доступности. При наличии этих двух сценариев невозможно сохранить работоспособность системы баз данных; т.е. доступность системы обеспечить просто нельзя. Кроме того, согласованность реплик лишена смысла; текущее положение дел в СУБД является просто неправильным. Восстановить базу данных после возникновения ситуации vii можно только в том случае, когда локальная транзакция фиксируется исключительно после того, как эта транзакция получена другим кластером, поключенным к территориально-распределенной сети. Лишь немногие разработчики приложений согласятся допустить такую задержку. Следовательно, согласованность "в конечном счете" гарантировать невозможно, поскольку при возникновении стихийного бедствия некоторые транзакции могут быть полностью утрачены в соответствующем локальном кластере до того, как их удастся успешно переслать куда-либо еще. Другими словами, разработчики приложений предпочтут потерять данные в результате возникновения какого-либо редкого события (такого как стихийное бедствие), поскольку, чтобы можно было избежать этого, требуются слишком большие расходы, снижающие производительность.

Ситуации i, ii и vii являются примерами случаев, в которых теорема CAP просто не применима. Любая реальная система должна быть готова к восстановлению при возникновении подобных ситуаций. Здесь невозможно руководствоваться теоремой CAP.

Обратимся теперь к случаям, в которых теорему CAP можно было бы применять. Рассмотрим случай vi, в котором возникает разделение локальной сети. По моему опыту, эта ситуация возникает исключительно редко, особенно при использовании репликации локальной сети (как это делала Tandem). Подавляющее число локальных сбоев (случаи iii, iv, v и vi) приводит к выходу из строя какого-либо одного узла, что является вырожденным случаем разделения сети, с которым легко справляется множество алгоритмов. Поэтому, по моему мнению, намного лучше отказаться от свойства P, чем жертвовать свойством C. (Я думаю, что в среде LAN следует выбирать пару CA, а не AP.) В новейших SQL-ориентированных системах категории OLTP (например, VoltDB и NimbusDB) делается именно это.

Далее, рассмотрим случай viii – разделение территориально-распределенной сети. В сегодняшней технологии WAN имеется достаточно большая избыточность, так что подобное разделение происходит довольно редко. По моему опыту, более вероятны локальные сбои и ошибки в приложениях. Кроме того, в большинстве подобных случаев от большей части узлов сети отделяется небольшой участок. В таких случаях в большей части узлов можно продолжать использовать простые алгоритмы, и только в этом небольшом участке работу нужно блокировать. Поэтому кажется неразумным все время жертвовать согласованностью в пользу доступности небольшого набора узлов при достаточно редком сценарии событий.

Наконец, рассмотрим случаи замедления работы ОС, СУБД или сетевого менеджера. Это может вызываться неравномерностью нагрузки, проблемами с буферным пулом и многочисленными другими причинами. Единственным решением, которое можно принять в таких сценариях, является перевод соответствующего компонента в разряд "сбойных", т.е. расценивание замедления работы как сбоя одной из разновидностей, рассмотренных ранее. С моей точки зрения, так делать почти всегда плохо. Проблему просто придется решать где-то в другом месте, а для последующего восстановления потребуется существенная дополнительная работа. Кроме того, такие проблемы неизбежно возникают при наличии высокого уровня нагрузки, и их решение за счет отказа от использования части аппаратных средств кажется сомнительным.

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

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

Литература

[1] Eric Brewer. Towards Robust Distributed Systems. PODS Keynote, July 19, 2000

[2] Jim Gray. Why Do Computers Stop and What Can be Done About It. Tandem Computers Technical Report 85.7, Cupertino, Ca., 1985.

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


Комментарии читателей BLOG@CACM

Дуайт Мерримен (Dwight Merriman), 7 апреля 2010 г.
Очень правильно замечено про "вырожденное разделение сети" – моя практика показывает, что большая часть случаев разделения сетей в реальном мире относится к этому классу.

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

Аларик Снелл-Пим (Alaric Snell-Pym), 7 апреля 2010 г.
Я думаю, что многие дискуссии относительно семантики распределенных баз данных, как и дискуссий, в которых противопоставляются SQL и MoSQL, омрачаются недостатком практичности. Поэтому анализ теоремы CAP в терминах реальных практических ситуаций является приятным исключением :-)

Моя компания (GenieDB) разработала сервер баз данных, поддерживающий репликацию, а также "буфер согласованности", обеспечивающий согласованное представление базы данных – при отсутствие сбоев сервера или сети. Кроме того, пользователям предоставляется возможность работы в ухудшенном режиме, когда некоторая часть записей базы данных становится "согласованной в конечном счете", а другая часть остается "немедленно согласованной". Обеспечение "ухудшенного" режима доступа к базе данных, а не запрещение доступа вообще, – это правильная вещь, поскольку это позволяет сократить стоимость разработки приложений. Но это совсем не то, к чему могли бы склониться люди, затуманенные теоремой CAP!

Аналогичным образом, мы обеспечиваем в своей системы как SQL-, так и NoSQL-интерфейсы, в обоих этих интерфейсах допускаются различные способы использования другого вида интерфейса, и оба интерфейса можно одновременно использовать при доступе к одним и тем же данным... Людям пора перестать сражаться за какое-то X против какого-то Y и подумать над тем, как можно на практике использовать лучшие черты обоих подходов!

Майкл Мелоун (Michael Malone), 7 апреля 2010 г.
Привет, Майкл,

Читать было интересно. Во многом я с Вами согласен. Но несколько замечаний у меня имеется...

Сбои категории i – это ошибки приложений.

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

Сбои категорий iii, iv, v, vi (разделение в локальном кластере) – как кажется, именно в этом состоит суть Ваших доводов... но Вы полностью умалчиваете свое решение. Я не уверен том, что разделение сети (даже выход из строя отдельного узла) легко переживается путем применения многих алгоритмов. Или, более точно, а не думаю, что такую ситуацию можно благополучно пережить с сохранением согласованности (в смысле CAP, а не ACID). В своем недавнем выступлении я привел сверхупрощенное доказательство того, что в этой ситуации согласованность, по существу, невозможна. См. здесь слайды с 16 до 20. Какие здесь подойдут алгоритмы? Если реплика отсоединится, то производить репликацию станет невозможно, и либо это следует признать сбоем, либо можно решить продолжать работу в любом случае, и тогда релика станет несогласованной.

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

Сбои категории vii, вероятно, приведут к потери некоторых данных (как Вы и говорите), если только не смириться с задержками, связанными с поддержкой записи данных в нескольких центрах данных. Но иметь такой вариант было бы совсем не плохо, и мне бы хотелось иметь возможность его выбора на уровне отдельных записей. Например, я бы предпочел наличие задержки при фиксации крупных финансовых транзакций. Еще одно соображение, относящееся к той же теме: если произвести много записей одних и тех же данных в основную память разных узлов, то полученный результат будет "устойчивее", чем если записать данные на диск в одном узле. Так что можно предпочесть выполнить с умеренной задержкой реплицированные записи в основную память нескольких центров данных, если эти центры данные не настолько удалены друг от друга, чтобы ограничивала скорость света. Это должно обеспечить устойчивость хранения данных, достаточную для того, чтобы пережить исчезновение, по крайней мере, всего Восточного побережья.

Сбои категории viii представляют еще одну ключевую проблему, которую, на мой взгляд, Вы обошли молчанием. Сбои в территориально-распределенных сетях (в особенности, недолговременных) могут возникать (и действительно возникают) регулярно. Проблемы маршрутизации обычно разрешаются быстро, но имеются и другие причины, обуславливаемые законом больших чисел. Например, в Amazon AWS (Amazon Web Services) имеется некоторая проблема, приводящая к переводу в состояние офлайн целого центра данных. Чего только не бывает... В терминах CAP эти виды сбоев, по существу, представляют собой то же самое, что и виды сбоев iii, iv, v, vi и vii. Так что здесь применимы те же доводы. Кстати, по поводу того Вашего аргумента, что обычно отделяется только небольшой сегмент, – что произойдет, когда именно в этот сегмент поступят запросы на чтение данных (может быть, от клиента того же центра данных)? Если к этому времени в большом сегменте данные обновятся, их невозможно будет реплицировать, так что опять либо пользователю будут предоставлены старые данные, либо хранилище данных будет недоступно.

Спасибо за то, что Вы все это скомпоновали, читать было действительно интересно. Надеюсь услышать больше по поводу этих проблем!

Пол Прескод (Paul Prescod,), 7 апреля 2010 г.
Я нахожу этот пост несколько путаным. Основной причиной моего непонимания является следующий абзац: "Восстановить базу данных после возникновения ситуации vii можно только в том случае, когда локальная транзакция фиксируется исключительно после того, как эта транзакция получена другим кластером, поключенным к территориально-распределенной сети. Лишь немногие разработчики приложений согласятся допустить такую задержку."

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

Так что Вы говорите, что выступаете против согласованности в конечном счете, но я понимаю ваши слова следующим образом: "если вы работаете в мастштабе WAN, то единственным вариантом является согласованность в конечном счете". И к тому же выводу пришли Amazon, Yahoo, Google, Facebook, Twitter и Rackspace. Вы соглашаетесь с ними или нет?

Вы утверждаете, что сбои в LAN случаются редко. В Facebook имеется, по меньшей мере, 60000 серверов. По некоторым оценкам, число серверов в Google достигло 250000 тысяч. В Yahoo около 150000 серверов. В Rackspace – более 50000. Примерно столько же серверов имеется в Amazon. Мне кажется, что они не могут работать в таких масштабах без наличия частых сбоев в локальной сети и серверах. Согласованность в конечном счете – это именно тот механизм, который позволяет справиться с временным выходом из строя компонентов крупномасштабной распределенной системы.

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

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

Пол Прескод (Paul Prescod,), 7 апреля 2010 г.
Еще одно соображение. Большая часть людей, осуждающих эти тенденции, не знает, что (например) при использовании Cassandra на уровне отдельного запроса (на чтение или запись) можно указать, требуется ли строгая согласованность (ConsistencyLevel.ALL) или же слабая согласованность (ConsistencyLevel.ONE). Соответствующая возможность поддерживается в API, и разработчики приложений могут делать выбор на основе семантики конкретного запроса. При записи мгновенного сообщения лучше использовать низкий уровень согласованности для обеспечения небольшой задержки. При записи финансовой транзакции лучше убедиться, что данные дошли до каждой реплики, чтобы потом не пришлось платить еще раз.

И конечно, я стал бы работать с финансовыми данными с использованием, как минимум, версии 0.7 этой системы... (К середине мая 2010 г. последней версией Cassandra была 0.6.1. Прим. переводчика.)

Майкл Мелоун (Michael Malone), 8 апреля 2010 г.
Пол, небольшая поправка... я могу быть и неправ. На, честно говоря, я думаю, что даже при использовании в Cassandra ConsistencyLevel.ALL при отказе узла Вы сможете получить только согласованность в конечном счете. Я полагаю, что ALL означает "запись в N узлов", где N – это установленный пользователем коэффициент репликации. Если все N основных узлов для заданного ключа выходят из строя, то, я думаю, Cassandra будет производить запись в следующие N узлов кластера. И, если я понимаю правильно доводы Майка, он говорит, что этого делать не следует... Вместо этого следует признать запись невозможной.

Затруднение состоит в том, что после восстановление работоспособности N основных узлов к ним будут направляться операции чтения. И даже при поддержке режима ConsistencyLevel.ALL результаты этих операций будут несогласованными до тех пор, пока не будет выполнена какая-либо процедура согласования реплик (Hinted Handoff, AntiEntropy или Read Repair (я не пытаюсь переводить и даже пояснять эти специфичные для Cassandra (и Dynamo) доморощенные термины; см. документацию – прим. переводчика)).

Я думаю, что во всех прочих случаях (при наличии или отсутствии сбоев) до тех пор, пока хотя бы один из N основных узлов для требуемого элемента данных сохраняет работоспособность, ConsistencyLevel.ALL будет обеспечивать строгую согласованность. При отсутствии разделения Cassandra обеспечивает строгую согласованность даже в режиме ConsistencyLevel.ONE.

Поэтому, как мне кажется, доводы Майкла состоят в том, что в ситуации, в которой имеется много сбоев, следует просто отказаться от обеспечения доступности, поскольку такие ситуации в действительности возникают очень редко (например, ситуация, в которой для выполнения операций чтения/записи невозможно обеспечить представительный кворум узлов (authoritative quorum)). Однако я по-прежнему с этим не согласен. Я полагаю, что в высоконагруженных системах часто возникают ситуации, в которых недоступно более N узлов, что означает недоступность некоторой части данных. Было бы хорошо иметь возможность оперативно перезапускать, выводить из состава кластера отдельные узлы или делать с ними что-то еще, не беспокоясь о возможной потере данных. Но разумные точки зрения могут различаться.

Луи Монтулли (Lou Montulli), 8 апреля 2010 г.
Мне редко встречаются обсуждения, затрагивающие разработку систем баз данных на основе консенсуса кворума (quorum consensus). Вероятно, это связано с отсутствием реализации подобного подхода для реляционных систем. Консенсус кворума решает многие проблемы CAP и может использовать в исключительно устойчивых реализациях.

Что Вы об этом думаете?

Расселл Окамото (Russell Okamoto), 9 апреля 2010 г.
Спасибо Майку за убедительное изложение его соображений по поводу CAP.

Меня удивляет, что в разговорах относительно CAP не упоминается другая важная работа Эрика Брювера – Harvest, Yield, and Scalable Tolerant Systems. В этой статье 1999 г. Брювер описывает стратегии решения проблем CAP на основе вероятностной доступности и декомпозиции приложений, что позволяет обеспечить сохранение работоспособности системы при ухудшении ее характеристик (graceful degradation) и поддержку режимов частичной утраты работосособности. Например, за счет декомпозиции приложений на независимые подсистемы сбои в одной подсистеме можно изолировать от других подсистем, что позволяет продолжать функционировать системе в целом (но, возможно, с сокращенным набором функциональных врозможностей).

Поскольку у отдельных подсистем имеются разные требования к тому, что может быть ослаблено (например, в одной подсистеме приоритет может отдаваться CA, а в другой – AP), такое разделение также наводит на мысль о "настраиваемых характеристиках CAP", т.е. о возможности разработчиков системы выбирать, в каких потоках работ масштаба всей системы следует использовать CA или CP, или AP. Не у всех актитвностей (подсистем) в сложном потоке работ имеются одни и те же требования к данным. Например, в подсистеме биллинга приоритет могла бы иметь согласованность, а в подсистеме Web-рекомендаций можно было бы допустить согласованность в конечном счете, чтение устаревших данных. Следовательно, возможность по-разному ослаблять требования C или A, или P в разных частях системы и в разное время может привести к оптимальной разработке системы в целом. Здесь уместен еще один Стоунбрекизм: "один размер не пригоден для всех". Идеи настраиваемых характеристик CAP в действительности уже используются (в течение нескольких лет) в новейших продуктах управления данными, применяемых во всех ведущих банковских организациях для поддержки масштабируемых, постоянно доступных высокоскоростных трейдинг-приложений (см., например, здесь).

Декомпозиция приложений, являясь подходом к решению проблем CAP, также дает возможность разработчикам приложений выявлять и использовать "ортогональные механизмы" (Брювер, стр. 3) для неинвазивного управления подсистемами. Например, ортогональным механизмом могут стать политики взаимозависимости схем баз данных, позволяющие пользователям настраивать требуемую семантику доступности для отдельных подсистем. Ценность этого подхода состоит в том, что политики взаимозависимости данных могут объявляться "на этапе компиляции" (во время конфигурирования системы), что позволяет заранее выявлять проблематичные/рисковые конфигурации, которые могут быть быстро исправлены администраторами. Кроме того, "на этапе выполнения" процесс принятия решений относительно поддержки жизнеспособности системы может основываться на здравой логике зависимостей схем, а не на случайностях, свойственных основным моделям разделения сети (где отделившийся участок сети выбирается в качестве жертвы произвольным образом).

И наконец, последствием применения настраиваемых характеристик CAP и декомпозиции приложений является то, что преобразование системы в целостный ряд автономных бизнес-фрагментов, общающихся на основе обмена сообшениями и являющихся транзакционно-независимыми, приводит к абстракции "сервис-сущности" в духе предложений Пэта Хелланда (Pat Helland) из статьи Life Beyond Distributed Transactions. В свою очередь, эту модель сервис-сущностей можно считать акторной моделью (Actor model) для параллельных вычислений. Так что, подводя итоги:

CAP ==> Декомпозиция приложений ==> Сервис-сущности ==> Акторная модель

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

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

Имеется масса данных относительно сбоев конкретных аппаратных средств, например, известна частота аварийных отказов дисков или сбоев основной памяти. Однако в действительности требуется относительная частота возникновения всех видов сбойных ситуаций, упомянутых в моем блоге. В 1980-е годы Джим Грей (Jim Gray) опубликовал именно такой анализ ошибочных ситуаций в системах компании Tandem. К сожалению, я не смог найти эту статью, которая, к тому же, была тесно связана с особенностями Tandem. Одним словом, я бы очень приветствовал публикацию данных о распределении ошибочных ситуаций в современных приложениях баз данных. При отсутствии надежных данных я привожу здесь собственные (не научные) рассуждения на эту тему. Конечно, вы можете придти к другим результатам ("your mileage will vary").

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

    По моему мнению, это происходит с приложениями примерно один раз в каждые три года. Однако это сильно зависит от того, насколько хорошо приложение оттестировано.

  2. Повторяющиеся ошибки СУБД. СУБД "падает" в некотором узле обработки. Выполнение той же транзакции в узле обработки, содержащем реплику требуемых данных, приводит к "падению" этой резервной копии. Такие ошибки называют "борбагами" (Bohr bug) [2].

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

  3. Неповторяющиеся ошибки СУБД. СУБД "падает", но при работе с репликой данных, вроде бы, все в порядке. Так часто случается при наличии асинхронных операций, и подобные ошибки называют "гейзенбагами" (Heisenbug) [2].

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

  4. Ошибки операционной системы. В некотором узле "падает" ОС, демонстрируя "синий экран смерти" ("blue screen of death").

    Частота проявления ошибок ОС очень сильно зависит от того, как используется операционная система. Золотым стандартом является MVS, которая является сверхнадежной и "падает" реже одного раза в год. Большинство других ОС терпит крах значительно чаще. По моему опыту, производственная ОС в каждом узле "падает" примерно один раз в каждые шесть месяцев.

  5. Сбой аппаратуры в локальном кластере. К числу таких ситуаций относятся сбои основной памяти, дисков и т.д. Обычно это приводит к аварийному останову ОС или СУБД. Однако иногда такие сбои проявляются в виде гейзенбагов.

    По моему опыту, ошибка диска в каждом узле проявлется примерно раз в год (хотя это зависит от числа подключенных дисков), и с такой же частотой проявляются аппаратные ошибки, не связанные с дисками. В среднем, каждый узел "падает" по аппаратным причинам каждые шесть месяцев. Кроме того, аппаратные проблемы достаточно сильно "скошены" во времени, т.е. проблемы в основном создают "детская смертность" ("infant mortality") и "престарелый возраст" ("old age").

  6. Разделение сети в локальном кластере. В результате сбоя в работе локальной сети узлы кластера не могут больше общаться.

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

  7. Стихийное бедствие. Локальный кластер уничтожается в результате наводнения, землетрясения и т.д. Кластер больше не существует.

    По моему опыту, каждый узел полностью исчезает каждые 20 лет или реже.

  8. Сбой в работе сетевой аппаратуры, связывающей кластеры в территориально-распределенную сеть. В результате кластеры не могут больше общаться.

    По моему опыту, сбои в WAN, приводящие к разделению частной сети (не Internet), возникают примерно раз в год. Наиболее вероятным является сбой в интерфейсе между локальным кластером и территориально-распределенной сетью, т.е. разделение, при котором от WAN отсоединяется один узел, в 20 раз более вероятно, чем более общее разделение сети. Другими словами, примерно раз в месяц некоторый узел теряет подключение к WAN.

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

Группа A: Приложение не может продолжать свое выполнение (виды сбоев i и ii). В нашем сценарии ошибочная ситуация в группе A возникает через каждые шесть месяцев. Независимо от используемой стратегии обеспечения высокого уровня доступности, блокировка приложения неизбежна.

Группа B: Имеется легко переносимая ошибочная ситуация, проявляемая в виде сбоя одного узла или в изоляции одного узла от остальных обрабатывающих узлов кластера (виды сбоев iii, iv, v и отчасти vi). Ошибочная ситуация в этой группе проявляется через каждые шесть дней.

Группа C: Имеется сбой, приводящий к отказу некоторого кластера или его изоляции от остальных узлов WAN (виды сбоев vii и отчасти viii). Эта ситуация возникает раз в месяц.

Группа D: Возникает разделение сети общего вида (некоторые ситуации видов vi и viii). Это случается раз в два года.

Грубо говоря, легко переносимые ошибочные ситуации (группы B и C) возникают раз в неделю, ошибочная ситуация, приводящая к блокировке системы, возникает раз в шесть месяцев, и разделение сети общего вида происходит раз в два года. Можно легко произвести подобный анализ, имея в виду собственные аппаратную среду и характеристики сбойных ситуаций. Это может привести к изменению оценки частоты возникновения разных типов сбоев, но я был бы удивлен, если бы изменились соотношения этих частот.

По сути, я стараюсь показать, что потеря работоспособности из-за ошибок в приложении или наличия борбагов более вероятна, чем разделение сети общего вида. По другому говоря, устойчивость к разделениям сети общего вида не устраняет возможности блокировки приложений.

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

Второе мое соображение касается репликации в WAN. Рассмотрим некоторую конкретную последовательность событий (очевидно, что она представляет не единственный способ выполнения работы, но в нескольких известных мне системах используется именно такой подход):

  1. приложение посылает транзакцию координатору (обычно размещаемому в "основном" узле хранения данных);
  2. координатор выполняет эту транзакцию локально; в параллель с этим он посылает транзакцию в резервный узел;
  3. основной узел отвечает координатору о завершении транзакции;
  4. координатор отвечает приложению о завершении транзакции;
  5. резервный узел завершает выполнение транзакции.
Эта система относится к категории "активный-активный", и транзакции в ней выполняются дважды – один раз в первичном узле и один раз в резервном узле, который, скорее всего, находится на другом конце WAN. Очень возможный сценарий сбойной ситуации заключается в том, что координатор завершает выполение транзакции в первичном узле, сообщает об этом приложению (шаг iv), а затем теряет работоспособность (например, из-за редкого, но все же возможного стихийного бедствия). В этом случае транзакция в первичном узле навсегда теряется. А если, в придачу в этому, до резервного узла не дойдет сообщение о транзакции, транзакция будет полностью потеряна, хотя пользователю было сообщено, что она успешно завершилась. Следовательно, согласованность (или, если хотите, согласованность в конечном счете) оказывается невозможной. Единственный способ избежать потери данных состоит в использовании двухфазной фиксации, тактики, вызывающей большие задержки, за которую мало кто хочет платить. Я хочу сказать, что бывают редкие нестандартные случаи, подобные описанным выше, в которых разработчики приложений не готовы платить ни за строгую согласованность, ни за согласованность в конечном счете. Другими словами, согласованность и согласованность в конечном счете не даются со стопроцентной гарантией, здесь всегда действует компромисс между стоимостью, величиной задержки и сложностью кода.
Франк Пац-Брокманн (Frank Patz-Brockmann), 7 мая 2010 г.

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

Комментарии

Григорьев Ю.А., Пт 24 май 2013 18:32:29:
Стоунбрейкер: "В теореме CAP утверждается, что при наличии ошибок невозможно одновременно достичь все трех этих целей. Следовательно, какой-то одной целью придется поступиться".

Стоунбрейкер неправильно трактует теорему CAP. В ней утверждается, что одновременно можно гарантировать только два из трёх свойств. Здесь не говорится о "наличии ошибок". В этом случае рассуждения Стоунбрейкера во многом теряют смысл.
Сергей, Чт 24 мар 2011 15:44:49:
Интересно а всё вышесказанное, как соотнести с нераспределённой клиентсерверной архитектурой. Если наводнение просто уничтожит сервер вместе с архивами - чем это отличается. Да и отказ сетевой аппаратуры - дисков, ОС чем отличается.
аноним, Ср 09 мар 2011 12:56:42:
Интересная статья.
аноним, Вт 08 мар 2011 02:16:45:
спасибо за перевод !
Сергей Знаменский, Вт 25 май 2010 21:33:47:
Отмечу, что теорема CAP доказана в дополнительном предположении об отсутствии сихронизации узлов по времени.

Добавлю Институт программных ситем имени А.К. Айламазяна РАН. Мы разрабатываем СУБД на основе сохранения полной истории изменений. В отличие от битемпоральных реляционных СУБД у нас сохранение полной истории осуществляется на низком уровне, что кардинально упрощает проблему синхронизации и избавляет от потерь информации при конкурентном доступе. Физически удалять ненужные неактуальные данные можно автоматически (см. нашу работу на rcdl2009). В аспирантуру берём.
Сергей Кузнецов, Чт 20 май 2010 16:37:51:
Мало таких учреждений. Вот то, что известно мне: Институт системного программирования РАН, группа MODIS, Вычислительный центр им. Дородницына РАН, Отдел систем математического обеспечения, Институт проблем информатики РАН, лаборатория композиционных методов и средств построения информационных систем, Санкт-Петербургский государственный университет, группа исследования методов организации информации. Более подробно могу рассказать (и дать координаты) по электронной почте.
Михаил, Чт 20 май 2010 07:21:44:
>Нужно, чтобы были отечественные исследовательские >и коммерческие проекты, связанные с разработкой >новых систем управления данными

Может кто-нибудь подскажет, какие научные учреждения в России работают в этом направлении? Особенно интересует аспирантура в них.

Ваш комментарий

Имя:

Текст комментария (HTML-теги не допускаются):

Новости мира IT:

Архив новостей

Последние комментарии:

Loading

IT-консалтинг Software Engineering Программирование СУБД Безопасность Internet Сети Операционные системы Hardware

Информация для рекламодателей PR-акции, размещение рекламы — adv@citforum.ru,
тел. +7 985 1945361
Пресс-релизы — pr@citforum.ru
Обратная связь
Информация для авторов
Rambler's Top100 TopList liveinternet.ru: показано число просмотров за 24 часа, посетителей за 24 часа и за сегодня This Web server launched on February 24, 1997
Copyright © 1997-2000 CIT, © 2001-2015 CIT Forum
Внимание! Любой из материалов, опубликованных на этом сервере, не может быть воспроизведен в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Подробнее...