Облака и византийские генералы

В основе подавляющего большинства современных отказоустойчивых решений лежат те или иные схемы резервирования процессоров, памяти, систем хранения, данных на разных аппаратно-программных уровнях, однако все это не более чем резервирование отдельных составляющих, а не всей системы в целом. Если система достаточно сложна, то даже при наличии самых развитых средств резервирования остается вероятность возникновения неисправностей на системном уровне. Выходом может быть комплексное резервирование — «репликация автоматов», или «репликация машин с состоянием» (state machine replication). Любой сервис, предоставляемый вычислительной системой, можно описать как автомат, или машину с состоянием, получающую запросы от машины-клиента, изменяющей ее состояние. Если собрать систему из некоторого количества идентичных, дублирующих друг друга автоматов и снабдить ее соответствующим механизмом взаимодействия, то можно создать надежную систему. В случае выхода из строя одного или нескольких автоматов оставшиеся смогут их заменить и система продолжит функционирование. Очевидно, что такой подход предполагает не просто удвоение или утроение, как при обычном резервировании, а использование существенно большего объема оборудования.

На первых порах облака вызывали тревогу с точки зрения обеспечения безопасности данных в случае несанкционированного доступа к ним, что вполне понятно в условиях больших объемов оборудования, однако реальная проблема не в этом — обеспечить защиту конкретных данных проще, чем организовать безопасное хранение. Сегодня для решения этой задачи основную надежду связывают с византийскими методами обеспечения отказоустойчивости (Byzantine Fault Tolerance, BFT).

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

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

Ситуация с византизмом отдельных процессоров в распределенных системах выглядит несколько проще. Традиционно единственно возможной формой нарушения в работе процессора представляется его фатальная поломка (модель fail-stop или fail-silent). Этот тип ошибки просто диагностируется и столь же просто исправляется заменой вышедшего из строя компонента. Реже случаются поломки, замедляющие работу процессора, которые являются следствием плавной деградации (модель slowdown) — неисправность подобного рода может быть диагностирована пользователем, другими узлами или специальным оборудованием. Совсем редко встречаются византийские ошибки (модель Byzantine), отличающиеся своим коварством, — в целом процессор работает корректно, но почему-то иногда выдает неверный результат. В некоторых случаях византийская ошибка процессора может быть обнаружена, например, проверкой контрольных сумм, а в иных ситуациях не может быть вовсе диагностирована. Чаще всего ситуацию, в которой возникает византийская ошибка, повторить не удается, однако последствия могут быть печальными, а предотвратить их практически невозможно.

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

Диагностировать византийские ошибки сложно, однако есть прецеденты — например, две ошибки обнаруженные в работе компьютерных сетей программы космического челнока. В обоих случаях сеть состояла из четырех компьютеров, работавших на общую шину. Первую ошибку зафиксировали 25 лет назад — она была вызвана неточностью, допущенной при расчете величины сопротивления, используемого в качестве терминаторы шины. Из-за нее при определенных условиях в шине возникала стоячая волна, которая нарушала взаимодействие между компьютерами и разделяла компьютеры на две группы по два в каждой. Во втором случае причиной возникновения византийской ошибки оказалось физическое разрушение полупроводникового слоя в одном диоде, находившемся в модуле подключения компьютера к сети. В нем полупроводниковый слой между электродами деградировал и превратился в диэлектрик — как следствие, из диода прибор превратился в конденсатор и сеть перешла в нештатный режим. Эпизод имел место при выполнении миссии STS-124, когда из-за одного диода корабль «Атлантис» был заменен на «Дискавери».

Разумеется, приложение византизма к технике — это всего лишь красивая метафора, и ни о каком коварстве электроники речи быть не может, а ошибки имеют вполне рациональное объяснение. Однако из-за неопределенности у инженеров возникает впечатление, будто техника начинает вести себя по своим правилам. В реальности причина непредусмотренного поведения систем кроется в не видимых инженерами физических свойствах машин, механизмов и сооружений. Большинству инженерных методов расчета и инженерных моделей свойственна упрощенность, и они не всегда точно соответствуют физике изделий. Например, оставаясь в рамках электротехники, невозможно объяснить, куда девается половина энергии при замыкании заряженного конденсатора равным ему по емкости. Инженерам свойственно забывать о реальных физических процессах, происходящих в создаваемых ими изделиях, — свои расчеты они ограничивают принятыми в их прикладной науке традициями, формулами и нормативами. Но изредка вдруг происходит нештатная ситуация, не предусмотренная каноническими методами расчетов, и вот тогда выходит из строя электрогенератор, рушится купольная конструкция или мостовое полотно.

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

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

Количественный рост системных компонентов влияет на представление о вероятностях возникновения ошибок. До сих пор вероятность «один на миллион» считалась пренебрежимо малой, но если число компонентов измеряется миллионами, то возникновение ошибок с подобной вероятностью уже оказывается вполне реальным. Скверность византийских неисправностей в том, что из-за редкой повторяемости их сложно диагностировать. Подобное встречается и в жизни общества. Скажем, есть какое-то редко встречающееся заболевание, и до тех пор, пока эпидемиологами не накоплен достаточный объем знаний, болезнь не может быть диагностирована и не могут быть выработаны средства для лечения.

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

На первый взгляд, задача создания работоспособной системы из ненадежных компонентов внешне похожа на передачу пакетов по стеку протоколов TCP/IP, однако в Сети имеются маршрутизаторы, контролирующие прохождение пакетов, а в распределенных системах все узлы автономны и ничего не знают о работоспособности соседей, поэтому должны сами выбирать тактику поведения. В простейшем случае коммуникации работают в определенном такте — каждый узел в начале очередного такта посылает сообщения остальным и, получив либо нет ответные сообщения, решает, что ему делать. Математической основой таких систем является решение задачи о византийских генералах.

Данная задача формулируется следующим образом: «Надежная компьютерная система должна сохранять работоспособность при наличии неверно работающих компонентов, передающих противоречивую информацию из разных частей системы». В качестве иллюстрации используется образное представление ситуации. Пусть есть несколько армий, штурмующих город. Известно, что совместными действиями определенной части этих армий город может быть взят. Армии связаны между собой ненадежными коммуникациями, и к тому же среди генералов, командующих армиями, могут быть предатели. Каждый из генералов действует автономно, он может пойти на штурм, но если сочтет, что количество лояльных генералов меньше минимального, то может отказаться. Задача сводится к обеспечению возможности принятия генералами согласованного решения в условиях географической разделенности их армий, при ненадежности связей и при наличии генералов-предателей. В такой образной формулировке задачу описали Лесли Лэмпорт, Роберт Шостак и Маршал Пис в 1982 году в статье “The Byzantine Generals Problem (BGP)” в бытность своей работы в Стэнфордском исследовательском институте, финансируемом DARPA.

BGP относится к области знаний, которую называют «Протоколы соглашений», а сама статья будет полезна тем, кого заинтересует строгая математическая постановка задачи. В 2008 году в журнале Dr.Dobb's была опубликована объемная статья с тем же названием, где задача и подходы к ее решению изложены на популярном уровне (drdobbs.com/cpp/206904396).

Перед исследователями из Стэнфорда была поставлена задача создания отказоустойчивой системы для летательных аппаратов. Ее решение потребовало создания новой теории прежде всего потому, что входящие в сборку компьютеры работали в асинхронном режиме с неопределенным временем задержки при передаче сообщений. Автором идеи «репликации машины с состоянием» стал Лесли Лэмпорт, а позже на основе этой идеи был разработан протокол Paxos, используемый, в частности, Google. Ядром протокола Paxos, предназначенного для создания отказоустойчивых распределенных систем, стал алгоритм достижения консенсуса, напоминающий голосование в синоде на греческом острове Паксос.

После работ Лэмпорта и его коллег исследования по проблемам BGP сосредоточились в двух группах. Одну из них возглавили Далия Малхи и Майкл Рейтер, которые к тому времени перешли на работу в AT&T Labs. Математические основы их работы, посвященной «византийским кворумам» (Byzantine Quorum Systems, BQS), изложены в статье “Byzantine Quorum Systems”. Идея BQS состоит в расширении классических кластер-кворумов (сборок, состоящих из равных по значимости компонентов) — когда при выходе из строя одного или нескольких компонентов нагрузка перераспределяется между оставшимися, вплоть до достижения некоторого предельного количества. Суть BQS в дополнении кластера набором регистров, размещаемых в каждом из узлов. Их состояние служит источником информации для управления кластером, обнаружения и компенсации византийских ошибок. Наличие этих регистров отличает BQS от протокола Paxos.

Второй группой руководила Барбара Лисков из Массачусетского технологического института. Эта группа предложила практический подход к византийской отказоустойчивости PBFT (Practical Byzantine Fault Tolerance). Основополагающая статья “Practical Byzantine Fault Tolerance” вышла в 1999 году. Преимущество PBFT — в способности к компенсации так называемых мягких сбоев (benign failure), которые обнаруживаются с большим трудом, но обычно не являются фатальными для работающей системы.

Работа Лисков стала спусковым механизмом — после нее последовало большое число публикаций и диссертаций, а на практике подход PBFT впервые был внедрен в облачной системе хранения Atmos подразделения EMC Cloud Infrastructure and Services Division.