Если ваша работа не связана с компьютерными технологиями, вы, вероятно, не думали долго о том, как хранятся данные на компьютерах или в облаке. Я говорю не о физических механизмах работы жёстких дисков или чипов памяти, а о чём-то одновременно более сложном и более понятном, чем вы думаете.
Если у вас есть часть данных, которую многие люди хотят прочесть и сразу отредактировать, например, общий текстовый файл, банковский счёт или мир в многопользовательской игре, как достичь общего согласия с тем, что находится в документе, и убедиться, что никто не перезаписывает чужую работу? Это проблема консенсуса в распределённых системах, и для того, чтобы разобраться с этим, мне придётся рассказать об овцах, диктаторах и вымышленных островах древней Греции.
«Каких ещё островах?», — спросите вы?
Оказывается, оригинальная научная статья об одном из наиболее важных методов, используемых для решения этой проблемы, была написана в виде продолжительного обсуждения того, как вымышленный парламент древнегреческого острова Паксос (Paxos) в неполном составе сумел принять законы, несмотря на то, что ни о ком из парламентариев нельзя было достоверно сказать, когда он появится в парламенте. Это прекрасная метафора о том, как группа людей может договориться, что записать в файл, при условии, что часть группы может быть недоступна в течение какого-то неопределённого времени. Оригинальная статья является одной из самых смешных когда-либо опубликованных серьезных научных статей и одним из лучших объяснений сложного алгоритма, которое я когда-либо видел. Так как эта метафора прекрасно сработала при объяснении части проблемы консенсуса в распределённых системах, и так как это намного интереснее, чем говорить о файловых системах, я собираюсь использовать её в этой статье.
Причина, по которой эта метафора работает настолько хорошо, заключается в том, что в обоих случаях с файлами и законами у нас есть некоторые данные, которые многие люди хотят изменять, многие люди хотят читать, но ни один человек не хочет тратить на этот процесс всё своё время. Одновременное чтение книги со сводом законов ограничено количеством людей, которые могут видеть книгу за раз, так же как чтение файла может быть ограничено скоростью, с которой данные могут получены с диска. Одновременная запись требует, чтобы все согласились не перезаписывать решение друг друга, но без длительных дебатов для его принятия. Помимо того, что каждый человек в мире по очереди будет использовать книгу, как мы можем решить эту проблему?
Вместо разговоров о файловых системах и операций в базах данных, давайте переместимся на острова ненастоящего Эгейского моря, где совпадения с реальностью случайны, а жители одержимы изданием указов и законов. Нам просто нужно убедиться, что каждый может прочитать закон, когда ему потребуется. Предстоит путь через несколько извилистых историй, и к тому времени, когда мы закончим, вы осознаете проблему распределённого консенсуса, в том виде в котором с ней сталкиваются IT-профессионалы. За исключением овец.
Кстати, будет множество островов, и их названия полностью выдуманы, кроме того, который был причиной этой истории, но об этом позже.
Мы начинаем нашу историю с самого простого случая на острове Псевдомоксос (Pseudemoxos). Здесь живет один отшельник, который пишет законы и указы для собственного использования. Сначала он использовал очень простой и понятный метод: записную книжку и карандаш. Он мог добавлять законы, менять законы и реорганизовывать законы по своему желанию, просто стирая и записывая новые, куда бы он ни пожелал (по сути, это то, как диски на наших компьютерах работали до конца 90-х годов).
Этот метод, казалось, работал достаточно хорошо, кроме слишком изнашиваемой при стирании бумаги. Однако, отшельник осознавал ужасный недостаток такого решения, когда однажды на берег выбросило ящик сомнительных буррито. Внося изменения в законе — стирая текст и начав что-то писать, отшельник испытал то, что вежливо назовём «чрезвычайной ситуацией на производстве». Когда несколько потрепанный отшельник вернулся к своему кодексу, он обнаружил, что он не только забыл, что собирался писать, но теперь пустое место в середине книги не заполнено ни старым, ни новым законом, а каракули, написанные в поспешности, невозможно прочитать!
Метафора описывает то, что происходит с компьютером или программой при сбое — данные на диске могут быть безнадежно искаженны. Более серьезные неудачи отшельника могут сравниться с такими событиями, как повреждение блока магнитных головок, которые могут нанести ущерб не только написанным словам, но и оставить довольно неприятную и постоянную отметку на всей странице.
Эти проблемы решены с помощью журналирования. Схема заключается в том, чтобы ничего не стирать, точно так же, как люди ведут журналы учёта или лабораторный дневник наблюдений. Теперь наш отшельник держит стопку бумаг, и, когда он хочет внести изменения в законы, он добавляет новую запись в свой журнал:
4 июня, 10:32 — Добавить к законам по безопасности пищевых продуктов: запрещено потребление буррито, которое находилось в море в течение неопределенного периода времени.
Каждое редактирование, будь то вставка, изменение или удаление, записывается в конце журнала ручкой. Отшельник защищен от чрезвычайной ситуации, потому что никогда не стирает записи. В худшем случае есть неполная, повреждённая запись в журнале или следы неудачной попытки записи, которые можно просто игнорировать. Журнал имеет дополнительное преимущество — запись всех изменений. Чтобы посмотреть, как закон выглядел год назад, наш отшельник может просто прочитать журнал и остановиться на этой дате.
Один очевидный недостаток журнала заключается в том, что читать его сложнее, чем записную книжку. Чтобы узнать о текущей версии закона о безопасности пищевых продуктов, нужно начинать с самого начала журнала и читать до конца, отслеживая все изменения. Так как со временем объём журнала увеличивается, процесс становится всё более обременительным.
Чтобы всё упростить, наш отшельник хранит стопку пустых справочников. Всякий раз, когда журнал становится слишком объёмным, он выделяет время, чтобы сделать свод законов: он читает журнал от начала до конца, формулируя весь закон в актуальном состоянии, а затем записывает это состояние в сборник законов. На обложке свода законов он пишет: «Это состояние закона на [такую-то дату]». Дальнейшее использование закона требует только, чтобы он прочитал свод законов и журнал изменений, сделанный после даты сбора закона. Журналы старше этой даты можно сохранить, если иногда требуется история изменений до свода, или просто выбросить.
Если наш отшельник слишком занят разработкой нового законодательства и не может регулярно делать свод законов, можно позвать писаря (то есть вторую компьютерную программу, работающую параллельно с первой), чтобы помочь ему. Писец прочитает журнал до некоторого согласованного времени, напишет свод законов и сообщит отшельнику, что закончил, чтобы он мог начать использовать новый сборник. Не нужно ничего говорить писцу, чтобы он выполнял свою работу, поэтому отшельник может продолжать свои труды в тишине.
У этого метода ещё больше преимуществ. Наш отшельник стал широко известен своей мудростью (например, своими уроками об отказе от мексиканской кулинарии, доставленной морем), многие люди, возможно, захотят прочитать его законы. До тех пор, пока эти читатели удовлетворены сводом законов от определённой даты, они могут сделать свои собственные копии и свободно их читать без необходимости беспокоить мудреца. Только человек, который нуждается в самой последней версии законов, должен обратиться к нему напрямую.
(Использование журналов в персональных компьютерах началось в конце 1990-х годов и получило распространение в середине 2000-х годов. Вероятно, ваш компьютер сейчас использует журналирование.)
Рядом с островом Псевдомоксос находится более крупный остров Фотас (Fotas). Этот остров мало населен, но людей достаточно, чтобы все жители согласились, что им нужна сводная система законов для управления их жизнью. Тем не менее, фотасчане известны своей непримиримой независимостью: они не позволяют любому другому жителю или группе властвовать над ними, и поэтому решили, что любой житель Фотаса будет иметь власть, чтобы принять закон. Для этого нужно просто записать закон на листе бумаги с датой, временем и своим именем и отправить гонца с ним в Библиотеку Фотаса, где писарь добавит его в юридические журналы.
(Это означает, что многие люди пытаются одновременно сохранить изменения одного файла, не делая прежде попыток достичь консенсуса по вопросу того, что будет в файле.)
Чтобы увидеть некоторые случаи, когда что-то может пойти не так, начнем рассказ с Агнии, которая живёт на одном из побережий острова и очень обеспокоена чистотой ритуальных жертвоприношений. Она вводит закон:
1 июня, полдень — Закон 32.1.2 о продаже овец изменяется следующим образом: Под страхом смерти запрещается продавать или приобретать овец, чья шерсть не абсолютно белая. Подписано, Агния.
На другой стороне острова, Базил, у которого есть несколько черных овец, с которыми он испытывает трудности при продаже, пишет свой закон:
1 июня, полдень — Закон 32.1.2 о продаже овец изменяется следующим образом: Никто не может отказаться покупать или продавать овец из-за цвета шерсти. Подписано, Базил.
Чуть позже писарь обнаруживает у себя два новых закона с одинаковой отметкой о времени. Что он должен сделать? Когда Базил приходит в город, чтобы продать чёрную овцу Галатее, а она отказывается покупать небелых овец, они пойдут читать свод законов. Какую из версий закона они должны использовать? И что будет, когда писарь попытается собрать следующий свод законов? (Если два человека попытались одновременно записать разные данные в одну и ту же часть одного и того же файла, результат может быть абсолютно любым.)
Чтобы проиллюстрировать более деликатную проблему, представьте, что Агния хочет выполнить операции «чтение-модификация-запись» закона — она смотрит на действующий закон, решает внести изменения, а затем записывает его. Но в то время, как она это делает, Базил вносит противоречие в закон. Например, в 10:00 Агния читает закон
Раздел 32.1.3. Любой человек, продающий козу, должен уплатить налог, равный одной монете, в общий фонд библиотеки.
Она размышляет и в 10:02 пишет следующее послание:
1 июня, 10:02 — В Законе 32.1.3 нужно изменить «равный одной монете» на «равный двум монетам». Подписано, Агния.
К сожалению, в 10:01 Базил, который терпеть не может козьих налогов, пишет:
1 июня, 10:01 — Закон 32.1.3 заменяется на «Середина февраля — национальный оливковый день». Так-то вот. Подписано, Базил.
Наш писец, пытаясь примирить законы и привести их в порядок, будет очень смущен: когда он доходит до послания от Агнии, закон 32.1.3 уже устанавливает Национальный оливковый день и нигде не упоминается «равный одной монете». Что ему делать? А представьте, что Базил заменит «уплатить в общий фонд библиотеки» на «уплатить Базилу!».
Подобные ситуации случаются, когда несколько авторов конкурируют при редактировании одного и того же свода законов. Существует множество решений, каждое из которых имеет свои плюсы и минусы. Эти решения можно разделить на два основных типа моделей. Один тип — «согласованность в конечном счёте» или «слабая согласованность» (eventual consistency), где несколько правил, регулирующих запись, позволяют каждому записывать одновременно, не разговаривая друг с другом. Эта модель гарантирует, что при отсутствии новых обновлений в течение некоторого времени все копии данных (реплики) станут согласованными. Издержки этого подхода заключаются в том, что никто не может знать точное состояние закона в текущий момент, все могут знать только то, каким оно было совсем недавно. Другая модель — «строгая согласованность», при которой возможны все виды записи, и каждый может знать текущее состояние закона, но с издержками на достижение консенсуса для каждой записи.
Оба типа моделей оказываются полезными. Иногда у вас есть информация, для которой норма быть немного устаревшей. Например, когда жители Фотас делают свой ежегодный фотоальбом. Они обмениваются фотографиями друг с другом и нет необходимости иметь самые свежие фотографии, поэтому более простая «согласованность в конечном счёте» будет хороша. С другой стороны, для настоящих законов «строгая согласованность» окажется более полезной, несмотря на её издержки. (Это верно и для компьютеров. Например, изображения, которые вы загружаете в Google, хранятся в системе с «согласованностью в конечном счёте», тогда как списки управления доступом, которые определяют права на просмотр, хранятся с использованием строгого согласования)
Вернемся на остров Фотас.
Мы могли бы легко решить первую из наших проблем — противоречивые законы с одинаковой временной меткой, просто добавив правило для тай-брейка, чтобы ни какие метки не могли быть одинаковыми. Например, мы могли бы добавить к метке имя автора в алфавитном порядке, так что в случае гонки, изменения от Агнии всегда будут внесены до Базила. (Или, если имена совпадают, мы можем назначить каждому жителю уникальный номер). После того, как временные метки больше не совпадают, нет путаницы. Галатея приходит в город, и закон Базила является единственным.
Если подобная взаимная перезапись является проблемой, ее можно избежать, предварительно договорившись о том, кто может что-либо писать. Например, в течение одной недели Агния может редактировать только чётные законы, а Базил нечётные, и наоборот на следующей неделе. (В компьютерах файловое пространство часто делится так, что два автора никогда не пытаются записать один и тот же файл вообще, а тем более в одно и то же время. Например, каждой вновь загруженной фотографии может автоматически присваиваться уникальное имя.)
Чтобы решить вторую проблему, мы уничтожаем возможность её существования: мы меняем правила журналирования с целью запретить поправки, допуская только полную замену, добавление или удаление. Это означает, что никакая формулировка в журнале не может зависеть от текущего состояния закона для его толкования. Агния пришлось бы написать свой закон в форме
1 июня, 10:02 — Закон 32.1.3 заменяется на «Любое лицо, продающее козу, должно уплатить налог, равный двум монетам, в Сенат». Агния.
Поскольку у её записи была более поздняя временная метка, её версия закона легко побеждает версию Базила.
Такая система написания законов обладает преимуществами скорости и простоты: каждый может писать закон в любое время, не консультируясь ни с кем другим. Однако использование законов становится удивительно сложным занятием. Если вы хотите узнать текущую ставку налога на продажу коз, вы идёте в библиотеку и просите прочитать Закон 32.1.3. Прибыв в 10:05, вы прочтёте свод законов и журнал изменений. Закон гласит: «Любой человек, продающий козу, должен уплатить налог, равный одной монете, в Сенат».
Видите ли, Агния изменила закон в 10:02, но её посланник еще не прибыл! Чтобы сделать ситуацию немного проще, гонцы могут регистрироваться в библиотеке: всякий раз, когда посыльный прибывает от каждого жителя, после доставки сообщения, они пишут записку на доске, указывающую, что все сообщения фотасчанина были доставлены в такое-то время. Затем посетитель может, взглянув на доску, увидеть, что последнее сообщение от Агнии было в 9 утра, а от Василия в 7 часов накануне вечером. Теперь вы, по крайней мере, знаете что законы, которые вы читаете, точны с 7 часов предыдущего вечера — самое раннее время, показанное на доске, и все изменения, написанные до этого времени должны были уже прибыть. (Это время называется «low-water mark»)
Конечно, если конкретный гражданин не очень конфликтный, обновления от него могут быть редкими, и каждый будет задаваться вопросом: «Изменения просто ещё не дошло до библиотеки или их просто нет?» Чтобы избежать этой проблемы, каждый фотасчанин должен отправлять гонца в библиотеку регулярно и независимо от того, есть ли у них какие-либо обновления или нет, чтобы доска оставалась актуальной.
Жители Фотаса — творческие люди, поэтому они быстро поняли, что этот постоянный поток гонцов может упростить их жизнь иначе. Вместо того, чтобы делать утомительные походы в библиотеку, они могут просто хранить свою собственную копию свода законов и журнала изменений. Теперь их гонец каждый раз возвращается со всеми последними изменениями в журнале, а также с копией дат, которые были на доске. Они обновляют свои копии и могут ссылаться на них.
Тем не менее, по мере того как население Фотаса увеличивалось, передвижение гонцов, бегающих в библиотеку, стало проблемой. Для книжников, копирующих журналы и своды, задача простого принятия закона об изменении козьего налога стала решаться ужасно медленно. К счастью, фотасчане поняли, что они уже решили свою проблему: имея свои собственные копии закона, им больше не требуется одна центральная библиотека!
Вместо этого было открыто несколько библиотек-филиалов. Гонцы могут доставлять и получать обновления в ближайших филиалах, а другие гонцы будут путешествовать между каждой парой библиотек-филиалов, чтобы передать копии всех обновлений. В итоге была построена «древовидная карта»: структура, соединяющая каждую ветвь друг с другом и каждого жителя с филиалом. Обновления доставляются только по маршрутам, показанным на карте, но поскольку каждый гражданин или филиал связаны с другим гражданином или библиотекой, в конечном итоге все изменения, сделанные любым жителем, будут доступны для всех на Фотасе. Каждый в конечном счёте будет иметь в руках одинаковый журнал, а своды законов в конечном счёте будут согласованы!
У такого подхода много преимуществ. Например, когда приходится перемещаться по опасной и платной дороге, которая является единственной тропой из центра острова к её восточным горам, только одному гонцу нужно пройти этот путь. Он доставит обновления с Запада на Восток и обратно, а ветвь филиалов на противоположных концах дороги, распространит информацию по остальной части острова.
(На этом этапе можно отметить, что больше нет какой-либо значимой разницы между отдельными жителями и филиалами библиотеки. У каждого есть копия и до тех пор, пока они продолжают отправлять гонцов по соответствующим маршрутам, каждый может изменить закон, просто написав это в своем собственном журнале и распространив информацию через систему)
Этот метод очень эффективен, но имеет три заметных недостатка.
Во-первых, никто не может с уверенностью знать о текущем состоянии закона. В отличие от писавшего в свой собственный журнал отшельника на Псевдомоксосе, у жителя Фотаса больше нет гарантии, что после внесения изменений кто-нибудь, читающий в будущем этот закон, увидит это изменение. Только тот, кто читает это в достаточно отдалённом будущем, увидит это изменение. (Это называется недостатком согласованности без «проверки чтением после записи»)
Во-вторых, невозможно выполнить чтение-модификацию-запись. Если два фотасчанина, пытаются изменить один и тот же закон, последствия будут непредсказуемы. Чтобы обойти эту проблему, фотасчанин должен найти какой-то способ гарантировать, что он является единственным человеком, пытающимся изменить данный закон, и что он прочитал последнюю версию закона до внесения изменений.
В-третьих, этот метод уязвим для сетевых сбоев: представьте, что дорога, ведущая к удаленному дому одного из жителей, отрезана обрушением скалы. Никакие обновления не могут быть получены им из внешнего мира, и никто не может предположить, что у них есть все обновления любого времени, более позднее, чем последнее его сообщение. Также никто не может предположить, что с тех пор он ничего не передавал. Остальные предполагают, что житель не знает о скале и продолжает писать в свой собственный журнал, ожидая гонца, который никогда не придёт. Таким образом, вся система останавливается, никто не продвигает вперёд «low-water mark», никто не может создать новый свод законов, потому что единственный путь потерян!
В компьютерной практике подобные проблемы реальны и серьезны. Всякий раз, когда один узел (компьютер или, возможно, центр обработки данных) отключается, инженерам необходимо немедленно оценить ситуацию и определить, может ли узел быть восстановлен и снова подключён. Если это не так, другие сервера не смогут сформировать свод, и их журналы будут продолжать расти, что создаст проблемы для читателей. При этом изолированный писатель будет становиться всё более и более несинхронизированным. Если проблему не удаётся устранить быстро, изолированные узлы зачастую полностью отключаются, для маршрутизации людей, которые хотят подключиться к ним, используются другие методы — часто гораздо более медленные внешние сети. Однако, остальные узлы продолжают ждать. Если станет ясно, что быстро проблема не решится, то есть только одна возможность: полностью удалить отсутствующие узлы из сети, сказав другим узлам, сделать вид, что тех узлов больше не существуют и никаких обновлений от них не будет. Узлы развиваются, но любые записи, которые изолированный узел выполняет будут потеряны навсегда, если только они не будут скопированы и переданы в основную сеть другими способами.
Итак, то, что мы видели выше, является разумным решением для яростно независимых островитян, таких как Fotans, которые хотят иметь возможность писать быстро и не совсем заинтересованы в возможности прочитать последнюю версию чего-то. Но что происходит в ситуациях, когда это просто неприемлемо? Законы на самом деле являются хорошим примером — если вы совершили преступление в 10:00, это имеет большое значение, был ли закон против него принят в 9:00 или 11:00. Важное значение имеет знание закона в настоящем времени.
Проблем стало гораздо больше, когда Фотас стал развивать юридический бизнес. Видите ли, Фотас окружен множеством гораздо меньших островов, каждый из которых имеет свою собственную отрасль и, следовательно, нуждается в собственном своде законов. Будучи маленькими островами, у них нет ресурсов для поддержания системы книжников и гонцов как на Фотасе. Они никогда не смогли бы обучить своих книжников и гонцов работать так же быстро и эффективно. Поэтому эти небольшие острова продолжали в течение многих лет использовать самое простое решение: у каждого острова был свой отшельник с журналом в псевдоэмоксосианском стиле, и все, кто хотел прочитать или изменить закон, просто выстраивались в очередь для общения с отшельником. Способ медленный и неэффективный, особенно если отшельник заболел или был смыт приливной волной. Но не имея ресурсов как на Фотасе, они просто шли своим путём.
Фотасчане, почуяв возможность, предложили свои своды законов как услугу своим соседям (LaaS). Острова-клиенты могли читать и записывать свои указы как часть свода законов Фотаса, каждый остров получал свою собственную главу, в которой никто больше не мог писать.
Сначала соседи были в восторге: больше им не приходилось выстраиваться в очередь, чтобы поговорить с отшельником. Процесс стал намного быстрее, даже с учётом времени на дорогу до Фотаса. (Фактически, Фотасчане работали над сокращением времени на дорогу, создав посольства на разных островах, которые стали частью сети). Также это было намного надежнее. Когда цунами уничтожило несколько островов и сильно повредило Фотас, у каждого фотасчанина были копии всего свода законов и систему легко восстановили. Поскольку Фотас находился недалеко от стольких островов, острова начали использовать систему Фотаса как способ надежной пересылки сообщений.
Но две проблемы, о которых мы ранее говорили, стали более очевидными. Например, на острове Парафоитас (один из клиентских островов) винная компания Андрос использовала хранилище Фотаса для отслеживания своих заказов. Однажды Андрос получил заказ на 100 амфор вина на свадьбу местного политика и сделал запись в книгу заказов. На следующий день один из его удалённых сотрудников проверил книгу заказов, но гонец не смог к этому времени доставить запись, оказавшись заблокированным в другом порту из-за шторма. Сотрудник не знал о заказе, и вино не было готово до дня свадьбы!
На острове Сиранос дела шли не лучше. В попытке разрешить проблему чтения-модификации-записи, дыба только один человек мог изменять закон одновременно, они назначили Бавкиду ответственной за законы с чётными номерами в понедельник, а Галена за остальные. Во вторник — наоборот, и так далее. Однако, Гален был очень нетерпелив и изменил чётные законы точно в полночь во вторник, как только появилась возможность. К сожалению, Бавкида изменила тот же закон в 11:58 прошлой ночью и её изменения еще не было доставлено Галену. Гален издал закон и непреднамеренно перезаписал работу Бавкиды.
Некоторые из соседних островов были вполне удовлетворены. Например, Эпифоитас использовал хранилище Фотаса для архива местной поэзии. Как только стихотворение было предано в архив, оно никогда не изменялось, но перечитывалось и добавлялись новые стихи. Для них система Фотаса была и надежной, и недорогой. Но в целом было достаточно островов, для которых недостатки системы Фотаса стали ясными.
Итак, теперь мы прибыли на остров Паксос (Paxos). Это настоящее название острова в Эгейском море с системой парламента, придуманной Лесли Лампортом. Он привел меня ко всем этим метафорам, а метод, который он описал, повсеместно известен как «алгоритм Paxos». (Все остальные названия островов в этой статье были собственным изобретением автора)
Хорошая новость об этом алгоритме заключается в том, что он не сложнее, чем то, что мы обсуждали ранее, а статья Лампорта описывает проблему в том же стиле. Вот эта статья «The Part-Time Parliament». Плохая новость заключается в том, что я не смог придумать ни одного объяснения короче, чем объяснение Лампорта. Это превратило бы эту длинную историю в безумно длинную. Хорошо, что я могу дать вам краткое описание идеи!
Жители Паксоса были заинтересованы в отслеживании изменений в своих законах и хотели, чтобы каждый гражданин мог знать действующий закон страны. Они также хотели иметь согласованность при чтении-модификации-записи, поскольку в противном случае могли бы быть приняты противоречивые законы. Такой тип согласованности часто называется строгой согласованностью, тогда как системы с более слабой согласованностью, как на Фотасе, называются согласованностью в конечном счёте.
На Паксосе были свои проблемы: их законы принимались только их парламентом, который собирался в одном здании, и поэтому им не приходилось беспокоиться о том, что парламентарии внезапно станут недоступными из-за оползня или приливной волны. Однако, это был парламент свободного посещения: законодатели были склонны к приходу и уходу по своему усмотрению, временами подолгу недоступные, но не по причине стихийного бедствия, а из-за хорошей амфоры вина. Плохая акустика в зале делала ораторство невозможным, и законодатели общались друг с другом через посланников, как и Фотасчане. Поэтому, несмотря на поверхностные разногласия, парламент свободного посещения на Паксосе создавал всё те же логистические сложности, что и более рассредоточенный парламент Фотаса.
Основная идея Paxos проста: для того, чтобы внести изменения в законы, вам нужно собрать большинство парламентариев, которые должны сделать то же самое. Если кто-то пытается внести противоречивые изменения в этот момент, попытавшись собрать своё собственное большинство, в нем гарантировано будет хотя бы один человек, который знает о предложенных вами изменениях, и он поможет остановить это, сказав: «Подождите! Мы уже голосуем за что-то другое!» Аналогичным образом, когда вы захотите прочитать законы, Вы спросите большинство парламентариев о последней версии закона. Опять же, если какие-либо изменения были сделаны, по крайней мере один из них, должен был в этом участвовать. Отслеживание того, какие голосования в настоящее время проводятся, происходит на основе данных от каждого парламентария, имеющего свой собственный журнал и записную книжку, в которых он отслеживает отданные голоса и полученные сообщения.
Метод Лампорта даёт несколько важных гарантий: он позволяет выполнить чтение закона сразу после записи, поскольку после достижения состояния консенсуса в отношении закона гарантируется, что при каждой будущей попытке прочитать закон любой увидит этот консенсус; Он делает возможным чтение-модификацию-запись, поскольку после того, как начнётся процесс внесения изменения в законе в случае его успешности, никакие другие записи не будут произведены за этот период. Он также удовлетворяет «условию прогресса», так как «если большинство парламентариев находилось в Палате, и никто не входил и не выходил в течение достаточно длительного периода времени, тогда изменение, предложенное законодателем в Палате, было бы принято, а принятое изменение, появилось бы в книге каждого законодателя в Палате».
Однако, достигается это определённой ценой. Принятие закона, то есть запись в системе, требует формирования консенсуса среди большинства членов. Если некоторые из участников далеки от инициатора изменений, то это потенциально очень медленный процесс. Вы больше не можете вносить изменения в закон, просто записывая их в свой собственный журнал. Чтение закона также становится медленным, так как этот процесс теперь предполагает опрос кворума парламента.
Поэтому на практике системы Paxos предлагает два метода чтения: «Read-latest», который опрашивает кворум, и «read-recent», который просто проверяет ваш собственный журнал учёта. В «read-recent» методе отсутствуют гарантии согласованности Paxos, но он быстр. На практике многие системы требуют гарантий строгой согласованности только в некоторые моменты времени. (Например, Агния и Базил, возможно, пожелают получить последнюю информацию о законе, когда ведут свой спор о продаже овец, но в обычный день, когда один из них отправляется на рынок, он будет довольствоваться чтением собственного журнала).
Это означает, что метод Paxos всегда имеет ненулевые издержки из-за низкой скорости, которые быстро растут по мере роста числа вовлеченных людей.
Одним из интересных свойств этих систем является то, что их можно комбинировать. Например, как в системах Фотас, так и в Паксос, у каждого законодателя были собственные копии журналов изменений и записная книжка. Различия только в том, с какими гарантиями строгой согласованности можно делать записи в них.
Представьте себе сеть островов, каждый из которых мал, но сильно отдалён от других, как острова в Тихом океане. (Или в компьютерных терминах, представьте себе сеть центров обработки данных, каждый из которых находится внутри здания, но они разбросаны по всему миру). Обеспечение строгой согласованности хранилищ с использованием Paxos на таких расстояниях будет ужасно непрактичным, поскольку для каждого чтения или записи потребуется собрать кворум. Это потребует несколько поездок между островами. Тем не менее, каждый остров может поддерживать своё собственное согласованное хранилище, а затем отдельная межостровная организация может обрабатывать собственные законы любыми способами, просто заменяя отдельные записные книжки на отдельные островные хранилища. Клиент, ограниченный одним островом, может тогда иметь дело только с законодательной системой этого острова, в то время как клиенты, занимающиеся межотраслевым бизнесом, могут использовать другую систему, но получить все преимущества устойчивости, имея больше, чем одну точку контакта на своем острове.
Эта возможность привела к тому, что на Сираносе пересмотрели свою собственную систему. Помните, что этот остров пытался добиться строгой согласованности, разделив законотворчество так, чтобы Бавкида могла писать законы с чётным номером в понедельник, а Гален во вторник. Несмотря на то, что эта простая система вызвала проблемы, она показала важную истину. Если кто-то интересуется законами о продаже коз в понедельник, вероятно, он всё ещё будет интересоваться этим во вторник, так как изменения интересов относительно редки. Также мы узнали, что многие строго согласованные методы очень медленные, но это норма, если вам придётся использовать их в редких случаях.
Это заставило жителей Сираноса спросить себя, могут ли они избрать диктатора по какому-либо вопросу, который будет отвечать за все законы, связанные с этим вопросом. Пока каждый может легко найти диктатора по какой-либо конкретной теме, а сам диктатор не перегружен запросами, это обеспечивает более простую форму строгой согласованности. Любой, кто хотел бы изменить или прочитать актуальные законы по этому вопросу будет общаться с диктатором. Если кто-то хочет просто получить представление о законе, он может прочитать свою собственную копию свода законов, скопированного как в системе Фотаса.
Основной принцип прост. Скажем, Бавкида хочет знать закон о продаже овец. Бавкида спрашивает в центральном реестре диктаторов: «Кто нынче овечий диктатор?» Узнав, что Филимон — тематический диктатор, Бавкида понимает куда идти. Если в реестре говорится, что диктатор не назначен, то она просто предлагает закон для этого реестра: «Бавкида будет овечьим диктатором». Если этот закон будет принят, Бавкида будет диктатором и может действовать полностью самостоятельно по этому вопросу. Если закон не прошёл согласование, значит другой закон был на согласовании, поэтому она повторяет свой запрос.
Как вы, возможно, догадались, центральный реестр диктаторов — это не что иное, как ещё одно строго согласованное хранилище. Для очень маленьких групп один отшельник может быть рабочей схемой, но по причинам масштаба и надежности, обычно лучше использовать метод Paxos для создания центрального реестра диктаторов. При этом межостровной Paxos может быть очень медленным, но вам нужно получить доступ к нему только в редких случаях, когда вы хотите узнать диктатора (или стать им).
Этот метод имеет ряд замечательных преимуществ. Если только один человек заинтересован в конкретном вопросе (бывает и такое, если вопрос достаточно узкий), тогда этот человек может стать диктатором и не иметь дел с соседями вообще. Если многие люди интересуются конкретной темой, тогда этим людям придётся стоять в очереди, чтобы поговорить с одним диктатором, но он сможет сразу дать им ответ, не дожидаясь пока информация будет передана откуда-то ещё.
Однако, есть несколько проблем. Первая — смерть диктатора. Бавкида была диктатором по овечьему вопросу в течение многих лет, но однажды у неё случился сердечный приступ. Никто не знал об этом, и поэтому все, кто занимался овцами, оказались в очереди к её дверям. Ожидая, когда она появится, вся отрасль остановилась на несколько дней. Наконец, дверь сломалась. Обнаружив её смерть, жители Сираноса приняли закон, отменяющий её диктатуру. После этого они формализовали решение, установив срок полномочий. Вместо «Бавкида будет овечьим диктатором» стало «Бавкида будет овечьим диктатором до полудня в четверг». Если она всё ещё жива и заинтересована в овцах, то утром в четверг она может предложить новый закон для голосования, который продлит её правление.
Вторая проблема — перегрузка диктаторов. Одно дело быть диктатором по овцам на маленьком Эгейском острове, совсем другое быть им в Новой Зеландии, где овцы превосходят людей численностью в пропорции 7:1. Очереди перед дверью диктатора были бы огромными!
К счастью, в этой системе не требуется, чтобы диктатор был только один. Диктатор должен обеспечить строго-согласованное представление по своему вопросу, а также передавать обновления во все другие журналы, используя надёжный метод. Поэтому в Новой Зеландии не избрали одного диктатора по овцам. Из группы заинтересованных фермеров было сформировано Новозеландское Общество Овечьих Диктаторов. Будучи относительно небольшой группой относительно надёжных людей, они могут вести общий свод законов, используя Paxos (или любую другую систему) с разумной лёгкостью и скоростью. Если они понимают, что становятся перегруженными, они зовут новых членов в организацию, чтобы обслужить запросы всех клиентов.
Они могут постоянно совершенствовать свои методы. Когда Общество небольшое, они могут использовать один журнал. Они могут разделить рабочие темы между собой, и, если кто-то временно недоступен, рассмотреть его вопрос на разовой основе с использованием Paxos. В конечном счёте, по мере роста Общества они могут внедрить структуру, чтобы определять, скажем, младшего диктатора по вопросам стрижки овец в Отаго. Приятно в этом то, что их клиентам не нужно понимать и знать, как они хранят информацию внутри компании. До тех пор, пока Общество обеспечивает гарантию того, что кто-либо, приходящий к ним, получит строго согласованное представление об овечьем законе, методы Общества могут меняться по их желанию.
Классическая версия этого протокола выборов правителя называется Chubby, и вы можете узнать больше об этом по ссылке.
Авторская иллюстрация, Yonatan Zunger, Distinguished Engineer on Privacy at Google
Если вы дочитали до этого места, вы только что изучили некоторые из наиболее сложных тем в распределенных вычислениях. Почти каждая проблема в вычислениях на базе центров обработки данных сводится к этим проблемам: как получается, что множество компьютеров, удаленных друг от друга, подключенных через ненадежные каналы, склонных к непредсказуемым переменам, тем не менее согласованно хранят информацию?
На практике существует четыре метода, которые обычно используются:
* Единые хранилища данных (Отшельник Псевдомоксоса), в которых один компьютер хранит свою собственную копию, все желающие должны использовать её по очереди. Система уязвима для одиночной катастрофы, строго согласована, жутко проста, и все остальные системы построены на её основе.
* Согласованная в конечном счёте репликация (система Фотаса), при которой каждый участник имеет своё (строго согласованное) хранилище, все читают свою собственную копию, обмениваясь обновлениями между всеми узлами и затем учитывая их. Такая система имеет преимущества скорости и простоты, а также надежности при многих видах катастроф, но не имеет гарантий строгой согласованности, при которых все будущие читатели узнают об изменении, как только вы его запишите. Эта система очень полезна в тех случаях, когда такая гарантия не требуется, например, распространение копий изображений (или других объёмных данных), которые никогда не будут изменяться после их записи и не требуют постоянного обновления.
* Решение кворума (система Паксоса, в отличие от других примеров, она на самом деле называется «Paxos»). Чтение и запись подразумевают получение подтверждений от большинства участников. Это обеспечивает строгую согласованность и надежность, но оказывается очень медленным методом, особенно при распределении системы на большой территории.
* Выборы диктатора (система Сираноса) — дорогое, строго согласованное хранилище используется для определения диктатора, который на какое-то время отвечает за какой-либо вопрос. Затем ответственная выбранная сторона использует своё собственное, более мелкое, строго согласованное хранилище, чтобы использовать и изменять закон по этому вопросу.
Самое лучшее в этих системах заключается в том, что с точки зрения клиента они различаются не методами, а гарантиями, которые они предоставляют. Теперь я оставлю вас. Мы бродили по цепочке смешных рассказов о вымышленных островах, но то, что вы узнали, не детская версия компьютерной науки. Это реальность, с которой IT-профессионалы сталкиваются каждый день. Поэтому я надеюсь, что, даже если вы сами не являетесь айтишником и не планируете им стать, у вас теперь есть лучшее понимание того, как организованы компьютерные вычисления в наше время.
Если у вас есть часть данных, которую многие люди хотят прочесть и сразу отредактировать, например, общий текстовый файл, банковский счёт или мир в многопользовательской игре, как достичь общего согласия с тем, что находится в документе, и убедиться, что никто не перезаписывает чужую работу? Это проблема консенсуса в распределённых системах, и для того, чтобы разобраться с этим, мне придётся рассказать об овцах, диктаторах и вымышленных островах древней Греции.
«Каких ещё островах?», — спросите вы?
Оказывается, оригинальная научная статья об одном из наиболее важных методов, используемых для решения этой проблемы, была написана в виде продолжительного обсуждения того, как вымышленный парламент древнегреческого острова Паксос (Paxos) в неполном составе сумел принять законы, несмотря на то, что ни о ком из парламентариев нельзя было достоверно сказать, когда он появится в парламенте. Это прекрасная метафора о том, как группа людей может договориться, что записать в файл, при условии, что часть группы может быть недоступна в течение какого-то неопределённого времени. Оригинальная статья является одной из самых смешных когда-либо опубликованных серьезных научных статей и одним из лучших объяснений сложного алгоритма, которое я когда-либо видел. Так как эта метафора прекрасно сработала при объяснении части проблемы консенсуса в распределённых системах, и так как это намного интереснее, чем говорить о файловых системах, я собираюсь использовать её в этой статье.
Причина, по которой эта метафора работает настолько хорошо, заключается в том, что в обоих случаях с файлами и законами у нас есть некоторые данные, которые многие люди хотят изменять, многие люди хотят читать, но ни один человек не хочет тратить на этот процесс всё своё время. Одновременное чтение книги со сводом законов ограничено количеством людей, которые могут видеть книгу за раз, так же как чтение файла может быть ограничено скоростью, с которой данные могут получены с диска. Одновременная запись требует, чтобы все согласились не перезаписывать решение друг друга, но без длительных дебатов для его принятия. Помимо того, что каждый человек в мире по очереди будет использовать книгу, как мы можем решить эту проблему?
Вместо разговоров о файловых системах и операций в базах данных, давайте переместимся на острова ненастоящего Эгейского моря, где совпадения с реальностью случайны, а жители одержимы изданием указов и законов. Нам просто нужно убедиться, что каждый может прочитать закон, когда ему потребуется. Предстоит путь через несколько извилистых историй, и к тому времени, когда мы закончим, вы осознаете проблему распределённого консенсуса, в том виде в котором с ней сталкиваются IT-профессионалы. За исключением овец.
Кстати, будет множество островов, и их названия полностью выдуманы, кроме того, который был причиной этой истории, но об этом позже.
Отшельники и мексиканская еда
Мы начинаем нашу историю с самого простого случая на острове Псевдомоксос (Pseudemoxos). Здесь живет один отшельник, который пишет законы и указы для собственного использования. Сначала он использовал очень простой и понятный метод: записную книжку и карандаш. Он мог добавлять законы, менять законы и реорганизовывать законы по своему желанию, просто стирая и записывая новые, куда бы он ни пожелал (по сути, это то, как диски на наших компьютерах работали до конца 90-х годов).
Этот метод, казалось, работал достаточно хорошо, кроме слишком изнашиваемой при стирании бумаги. Однако, отшельник осознавал ужасный недостаток такого решения, когда однажды на берег выбросило ящик сомнительных буррито. Внося изменения в законе — стирая текст и начав что-то писать, отшельник испытал то, что вежливо назовём «чрезвычайной ситуацией на производстве». Когда несколько потрепанный отшельник вернулся к своему кодексу, он обнаружил, что он не только забыл, что собирался писать, но теперь пустое место в середине книги не заполнено ни старым, ни новым законом, а каракули, написанные в поспешности, невозможно прочитать!
Метафора описывает то, что происходит с компьютером или программой при сбое — данные на диске могут быть безнадежно искаженны. Более серьезные неудачи отшельника могут сравниться с такими событиями, как повреждение блока магнитных головок, которые могут нанести ущерб не только написанным словам, но и оставить довольно неприятную и постоянную отметку на всей странице.
Эти проблемы решены с помощью журналирования. Схема заключается в том, чтобы ничего не стирать, точно так же, как люди ведут журналы учёта или лабораторный дневник наблюдений. Теперь наш отшельник держит стопку бумаг, и, когда он хочет внести изменения в законы, он добавляет новую запись в свой журнал:
4 июня, 10:32 — Добавить к законам по безопасности пищевых продуктов: запрещено потребление буррито, которое находилось в море в течение неопределенного периода времени.
Каждое редактирование, будь то вставка, изменение или удаление, записывается в конце журнала ручкой. Отшельник защищен от чрезвычайной ситуации, потому что никогда не стирает записи. В худшем случае есть неполная, повреждённая запись в журнале или следы неудачной попытки записи, которые можно просто игнорировать. Журнал имеет дополнительное преимущество — запись всех изменений. Чтобы посмотреть, как закон выглядел год назад, наш отшельник может просто прочитать журнал и остановиться на этой дате.
Один очевидный недостаток журнала заключается в том, что читать его сложнее, чем записную книжку. Чтобы узнать о текущей версии закона о безопасности пищевых продуктов, нужно начинать с самого начала журнала и читать до конца, отслеживая все изменения. Так как со временем объём журнала увеличивается, процесс становится всё более обременительным.
Чтобы всё упростить, наш отшельник хранит стопку пустых справочников. Всякий раз, когда журнал становится слишком объёмным, он выделяет время, чтобы сделать свод законов: он читает журнал от начала до конца, формулируя весь закон в актуальном состоянии, а затем записывает это состояние в сборник законов. На обложке свода законов он пишет: «Это состояние закона на [такую-то дату]». Дальнейшее использование закона требует только, чтобы он прочитал свод законов и журнал изменений, сделанный после даты сбора закона. Журналы старше этой даты можно сохранить, если иногда требуется история изменений до свода, или просто выбросить.
Если наш отшельник слишком занят разработкой нового законодательства и не может регулярно делать свод законов, можно позвать писаря (то есть вторую компьютерную программу, работающую параллельно с первой), чтобы помочь ему. Писец прочитает журнал до некоторого согласованного времени, напишет свод законов и сообщит отшельнику, что закончил, чтобы он мог начать использовать новый сборник. Не нужно ничего говорить писцу, чтобы он выполнял свою работу, поэтому отшельник может продолжать свои труды в тишине.
У этого метода ещё больше преимуществ. Наш отшельник стал широко известен своей мудростью (например, своими уроками об отказе от мексиканской кулинарии, доставленной морем), многие люди, возможно, захотят прочитать его законы. До тех пор, пока эти читатели удовлетворены сводом законов от определённой даты, они могут сделать свои собственные копии и свободно их читать без необходимости беспокоить мудреца. Только человек, который нуждается в самой последней версии законов, должен обратиться к нему напрямую.
(Использование журналов в персональных компьютерах началось в конце 1990-х годов и получило распространение в середине 2000-х годов. Вероятно, ваш компьютер сейчас использует журналирование.)
Хаос на острове Фотас
Рядом с островом Псевдомоксос находится более крупный остров Фотас (Fotas). Этот остров мало населен, но людей достаточно, чтобы все жители согласились, что им нужна сводная система законов для управления их жизнью. Тем не менее, фотасчане известны своей непримиримой независимостью: они не позволяют любому другому жителю или группе властвовать над ними, и поэтому решили, что любой житель Фотаса будет иметь власть, чтобы принять закон. Для этого нужно просто записать закон на листе бумаги с датой, временем и своим именем и отправить гонца с ним в Библиотеку Фотаса, где писарь добавит его в юридические журналы.
(Это означает, что многие люди пытаются одновременно сохранить изменения одного файла, не делая прежде попыток достичь консенсуса по вопросу того, что будет в файле.)
Чтобы увидеть некоторые случаи, когда что-то может пойти не так, начнем рассказ с Агнии, которая живёт на одном из побережий острова и очень обеспокоена чистотой ритуальных жертвоприношений. Она вводит закон:
1 июня, полдень — Закон 32.1.2 о продаже овец изменяется следующим образом: Под страхом смерти запрещается продавать или приобретать овец, чья шерсть не абсолютно белая. Подписано, Агния.
На другой стороне острова, Базил, у которого есть несколько черных овец, с которыми он испытывает трудности при продаже, пишет свой закон:
1 июня, полдень — Закон 32.1.2 о продаже овец изменяется следующим образом: Никто не может отказаться покупать или продавать овец из-за цвета шерсти. Подписано, Базил.
Чуть позже писарь обнаруживает у себя два новых закона с одинаковой отметкой о времени. Что он должен сделать? Когда Базил приходит в город, чтобы продать чёрную овцу Галатее, а она отказывается покупать небелых овец, они пойдут читать свод законов. Какую из версий закона они должны использовать? И что будет, когда писарь попытается собрать следующий свод законов? (Если два человека попытались одновременно записать разные данные в одну и ту же часть одного и того же файла, результат может быть абсолютно любым.)
Чтобы проиллюстрировать более деликатную проблему, представьте, что Агния хочет выполнить операции «чтение-модификация-запись» закона — она смотрит на действующий закон, решает внести изменения, а затем записывает его. Но в то время, как она это делает, Базил вносит противоречие в закон. Например, в 10:00 Агния читает закон
Раздел 32.1.3. Любой человек, продающий козу, должен уплатить налог, равный одной монете, в общий фонд библиотеки.
Она размышляет и в 10:02 пишет следующее послание:
1 июня, 10:02 — В Законе 32.1.3 нужно изменить «равный одной монете» на «равный двум монетам». Подписано, Агния.
К сожалению, в 10:01 Базил, который терпеть не может козьих налогов, пишет:
1 июня, 10:01 — Закон 32.1.3 заменяется на «Середина февраля — национальный оливковый день». Так-то вот. Подписано, Базил.
Наш писец, пытаясь примирить законы и привести их в порядок, будет очень смущен: когда он доходит до послания от Агнии, закон 32.1.3 уже устанавливает Национальный оливковый день и нигде не упоминается «равный одной монете». Что ему делать? А представьте, что Базил заменит «уплатить в общий фонд библиотеки» на «уплатить Базилу!».
Подобные ситуации случаются, когда несколько авторов конкурируют при редактировании одного и того же свода законов. Существует множество решений, каждое из которых имеет свои плюсы и минусы. Эти решения можно разделить на два основных типа моделей. Один тип — «согласованность в конечном счёте» или «слабая согласованность» (eventual consistency), где несколько правил, регулирующих запись, позволяют каждому записывать одновременно, не разговаривая друг с другом. Эта модель гарантирует, что при отсутствии новых обновлений в течение некоторого времени все копии данных (реплики) станут согласованными. Издержки этого подхода заключаются в том, что никто не может знать точное состояние закона в текущий момент, все могут знать только то, каким оно было совсем недавно. Другая модель — «строгая согласованность», при которой возможны все виды записи, и каждый может знать текущее состояние закона, но с издержками на достижение консенсуса для каждой записи.
Оба типа моделей оказываются полезными. Иногда у вас есть информация, для которой норма быть немного устаревшей. Например, когда жители Фотас делают свой ежегодный фотоальбом. Они обмениваются фотографиями друг с другом и нет необходимости иметь самые свежие фотографии, поэтому более простая «согласованность в конечном счёте» будет хороша. С другой стороны, для настоящих законов «строгая согласованность» окажется более полезной, несмотря на её издержки. (Это верно и для компьютеров. Например, изображения, которые вы загружаете в Google, хранятся в системе с «согласованностью в конечном счёте», тогда как списки управления доступом, которые определяют права на просмотр, хранятся с использованием строгого согласования)
Вернемся на остров Фотас.
В конце концов, всё имеет смысл
Мы могли бы легко решить первую из наших проблем — противоречивые законы с одинаковой временной меткой, просто добавив правило для тай-брейка, чтобы ни какие метки не могли быть одинаковыми. Например, мы могли бы добавить к метке имя автора в алфавитном порядке, так что в случае гонки, изменения от Агнии всегда будут внесены до Базила. (Или, если имена совпадают, мы можем назначить каждому жителю уникальный номер). После того, как временные метки больше не совпадают, нет путаницы. Галатея приходит в город, и закон Базила является единственным.
Если подобная взаимная перезапись является проблемой, ее можно избежать, предварительно договорившись о том, кто может что-либо писать. Например, в течение одной недели Агния может редактировать только чётные законы, а Базил нечётные, и наоборот на следующей неделе. (В компьютерах файловое пространство часто делится так, что два автора никогда не пытаются записать один и тот же файл вообще, а тем более в одно и то же время. Например, каждой вновь загруженной фотографии может автоматически присваиваться уникальное имя.)
Чтобы решить вторую проблему, мы уничтожаем возможность её существования: мы меняем правила журналирования с целью запретить поправки, допуская только полную замену, добавление или удаление. Это означает, что никакая формулировка в журнале не может зависеть от текущего состояния закона для его толкования. Агния пришлось бы написать свой закон в форме
1 июня, 10:02 — Закон 32.1.3 заменяется на «Любое лицо, продающее козу, должно уплатить налог, равный двум монетам, в Сенат». Агния.
Поскольку у её записи была более поздняя временная метка, её версия закона легко побеждает версию Базила.
Такая система написания законов обладает преимуществами скорости и простоты: каждый может писать закон в любое время, не консультируясь ни с кем другим. Однако использование законов становится удивительно сложным занятием. Если вы хотите узнать текущую ставку налога на продажу коз, вы идёте в библиотеку и просите прочитать Закон 32.1.3. Прибыв в 10:05, вы прочтёте свод законов и журнал изменений. Закон гласит: «Любой человек, продающий козу, должен уплатить налог, равный одной монете, в Сенат».
Видите ли, Агния изменила закон в 10:02, но её посланник еще не прибыл! Чтобы сделать ситуацию немного проще, гонцы могут регистрироваться в библиотеке: всякий раз, когда посыльный прибывает от каждого жителя, после доставки сообщения, они пишут записку на доске, указывающую, что все сообщения фотасчанина были доставлены в такое-то время. Затем посетитель может, взглянув на доску, увидеть, что последнее сообщение от Агнии было в 9 утра, а от Василия в 7 часов накануне вечером. Теперь вы, по крайней мере, знаете что законы, которые вы читаете, точны с 7 часов предыдущего вечера — самое раннее время, показанное на доске, и все изменения, написанные до этого времени должны были уже прибыть. (Это время называется «low-water mark»)
Конечно, если конкретный гражданин не очень конфликтный, обновления от него могут быть редкими, и каждый будет задаваться вопросом: «Изменения просто ещё не дошло до библиотеки или их просто нет?» Чтобы избежать этой проблемы, каждый фотасчанин должен отправлять гонца в библиотеку регулярно и независимо от того, есть ли у них какие-либо обновления или нет, чтобы доска оставалась актуальной.
Жители Фотаса — творческие люди, поэтому они быстро поняли, что этот постоянный поток гонцов может упростить их жизнь иначе. Вместо того, чтобы делать утомительные походы в библиотеку, они могут просто хранить свою собственную копию свода законов и журнала изменений. Теперь их гонец каждый раз возвращается со всеми последними изменениями в журнале, а также с копией дат, которые были на доске. Они обновляют свои копии и могут ссылаться на них.
Тем не менее, по мере того как население Фотаса увеличивалось, передвижение гонцов, бегающих в библиотеку, стало проблемой. Для книжников, копирующих журналы и своды, задача простого принятия закона об изменении козьего налога стала решаться ужасно медленно. К счастью, фотасчане поняли, что они уже решили свою проблему: имея свои собственные копии закона, им больше не требуется одна центральная библиотека!
Вместо этого было открыто несколько библиотек-филиалов. Гонцы могут доставлять и получать обновления в ближайших филиалах, а другие гонцы будут путешествовать между каждой парой библиотек-филиалов, чтобы передать копии всех обновлений. В итоге была построена «древовидная карта»: структура, соединяющая каждую ветвь друг с другом и каждого жителя с филиалом. Обновления доставляются только по маршрутам, показанным на карте, но поскольку каждый гражданин или филиал связаны с другим гражданином или библиотекой, в конечном итоге все изменения, сделанные любым жителем, будут доступны для всех на Фотасе. Каждый в конечном счёте будет иметь в руках одинаковый журнал, а своды законов в конечном счёте будут согласованы!
У такого подхода много преимуществ. Например, когда приходится перемещаться по опасной и платной дороге, которая является единственной тропой из центра острова к её восточным горам, только одному гонцу нужно пройти этот путь. Он доставит обновления с Запада на Восток и обратно, а ветвь филиалов на противоположных концах дороги, распространит информацию по остальной части острова.
(На этом этапе можно отметить, что больше нет какой-либо значимой разницы между отдельными жителями и филиалами библиотеки. У каждого есть копия и до тех пор, пока они продолжают отправлять гонцов по соответствующим маршрутам, каждый может изменить закон, просто написав это в своем собственном журнале и распространив информацию через систему)
Этот метод очень эффективен, но имеет три заметных недостатка.
Во-первых, никто не может с уверенностью знать о текущем состоянии закона. В отличие от писавшего в свой собственный журнал отшельника на Псевдомоксосе, у жителя Фотаса больше нет гарантии, что после внесения изменений кто-нибудь, читающий в будущем этот закон, увидит это изменение. Только тот, кто читает это в достаточно отдалённом будущем, увидит это изменение. (Это называется недостатком согласованности без «проверки чтением после записи»)
Во-вторых, невозможно выполнить чтение-модификацию-запись. Если два фотасчанина, пытаются изменить один и тот же закон, последствия будут непредсказуемы. Чтобы обойти эту проблему, фотасчанин должен найти какой-то способ гарантировать, что он является единственным человеком, пытающимся изменить данный закон, и что он прочитал последнюю версию закона до внесения изменений.
В-третьих, этот метод уязвим для сетевых сбоев: представьте, что дорога, ведущая к удаленному дому одного из жителей, отрезана обрушением скалы. Никакие обновления не могут быть получены им из внешнего мира, и никто не может предположить, что у них есть все обновления любого времени, более позднее, чем последнее его сообщение. Также никто не может предположить, что с тех пор он ничего не передавал. Остальные предполагают, что житель не знает о скале и продолжает писать в свой собственный журнал, ожидая гонца, который никогда не придёт. Таким образом, вся система останавливается, никто не продвигает вперёд «low-water mark», никто не может создать новый свод законов, потому что единственный путь потерян!
В компьютерной практике подобные проблемы реальны и серьезны. Всякий раз, когда один узел (компьютер или, возможно, центр обработки данных) отключается, инженерам необходимо немедленно оценить ситуацию и определить, может ли узел быть восстановлен и снова подключён. Если это не так, другие сервера не смогут сформировать свод, и их журналы будут продолжать расти, что создаст проблемы для читателей. При этом изолированный писатель будет становиться всё более и более несинхронизированным. Если проблему не удаётся устранить быстро, изолированные узлы зачастую полностью отключаются, для маршрутизации людей, которые хотят подключиться к ним, используются другие методы — часто гораздо более медленные внешние сети. Однако, остальные узлы продолжают ждать. Если станет ясно, что быстро проблема не решится, то есть только одна возможность: полностью удалить отсутствующие узлы из сети, сказав другим узлам, сделать вид, что тех узлов больше не существуют и никаких обновлений от них не будет. Узлы развиваются, но любые записи, которые изолированный узел выполняет будут потеряны навсегда, если только они не будут скопированы и переданы в основную сеть другими способами.
Клиенты Фотаса и строгая согласованность
Итак, то, что мы видели выше, является разумным решением для яростно независимых островитян, таких как Fotans, которые хотят иметь возможность писать быстро и не совсем заинтересованы в возможности прочитать последнюю версию чего-то. Но что происходит в ситуациях, когда это просто неприемлемо? Законы на самом деле являются хорошим примером — если вы совершили преступление в 10:00, это имеет большое значение, был ли закон против него принят в 9:00 или 11:00. Важное значение имеет знание закона в настоящем времени.
Проблем стало гораздо больше, когда Фотас стал развивать юридический бизнес. Видите ли, Фотас окружен множеством гораздо меньших островов, каждый из которых имеет свою собственную отрасль и, следовательно, нуждается в собственном своде законов. Будучи маленькими островами, у них нет ресурсов для поддержания системы книжников и гонцов как на Фотасе. Они никогда не смогли бы обучить своих книжников и гонцов работать так же быстро и эффективно. Поэтому эти небольшие острова продолжали в течение многих лет использовать самое простое решение: у каждого острова был свой отшельник с журналом в псевдоэмоксосианском стиле, и все, кто хотел прочитать или изменить закон, просто выстраивались в очередь для общения с отшельником. Способ медленный и неэффективный, особенно если отшельник заболел или был смыт приливной волной. Но не имея ресурсов как на Фотасе, они просто шли своим путём.
Фотасчане, почуяв возможность, предложили свои своды законов как услугу своим соседям (LaaS). Острова-клиенты могли читать и записывать свои указы как часть свода законов Фотаса, каждый остров получал свою собственную главу, в которой никто больше не мог писать.
Сначала соседи были в восторге: больше им не приходилось выстраиваться в очередь, чтобы поговорить с отшельником. Процесс стал намного быстрее, даже с учётом времени на дорогу до Фотаса. (Фактически, Фотасчане работали над сокращением времени на дорогу, создав посольства на разных островах, которые стали частью сети). Также это было намного надежнее. Когда цунами уничтожило несколько островов и сильно повредило Фотас, у каждого фотасчанина были копии всего свода законов и систему легко восстановили. Поскольку Фотас находился недалеко от стольких островов, острова начали использовать систему Фотаса как способ надежной пересылки сообщений.
Но две проблемы, о которых мы ранее говорили, стали более очевидными. Например, на острове Парафоитас (один из клиентских островов) винная компания Андрос использовала хранилище Фотаса для отслеживания своих заказов. Однажды Андрос получил заказ на 100 амфор вина на свадьбу местного политика и сделал запись в книгу заказов. На следующий день один из его удалённых сотрудников проверил книгу заказов, но гонец не смог к этому времени доставить запись, оказавшись заблокированным в другом порту из-за шторма. Сотрудник не знал о заказе, и вино не было готово до дня свадьбы!
На острове Сиранос дела шли не лучше. В попытке разрешить проблему чтения-модификации-записи, дыба только один человек мог изменять закон одновременно, они назначили Бавкиду ответственной за законы с чётными номерами в понедельник, а Галена за остальные. Во вторник — наоборот, и так далее. Однако, Гален был очень нетерпелив и изменил чётные законы точно в полночь во вторник, как только появилась возможность. К сожалению, Бавкида изменила тот же закон в 11:58 прошлой ночью и её изменения еще не было доставлено Галену. Гален издал закон и непреднамеренно перезаписал работу Бавкиды.
Некоторые из соседних островов были вполне удовлетворены. Например, Эпифоитас использовал хранилище Фотаса для архива местной поэзии. Как только стихотворение было предано в архив, оно никогда не изменялось, но перечитывалось и добавлялись новые стихи. Для них система Фотаса была и надежной, и недорогой. Но в целом было достаточно островов, для которых недостатки системы Фотаса стали ясными.
Парламент Паксоса
Итак, теперь мы прибыли на остров Паксос (Paxos). Это настоящее название острова в Эгейском море с системой парламента, придуманной Лесли Лампортом. Он привел меня ко всем этим метафорам, а метод, который он описал, повсеместно известен как «алгоритм Paxos». (Все остальные названия островов в этой статье были собственным изобретением автора)
Хорошая новость об этом алгоритме заключается в том, что он не сложнее, чем то, что мы обсуждали ранее, а статья Лампорта описывает проблему в том же стиле. Вот эта статья «The Part-Time Parliament». Плохая новость заключается в том, что я не смог придумать ни одного объяснения короче, чем объяснение Лампорта. Это превратило бы эту длинную историю в безумно длинную. Хорошо, что я могу дать вам краткое описание идеи!
Жители Паксоса были заинтересованы в отслеживании изменений в своих законах и хотели, чтобы каждый гражданин мог знать действующий закон страны. Они также хотели иметь согласованность при чтении-модификации-записи, поскольку в противном случае могли бы быть приняты противоречивые законы. Такой тип согласованности часто называется строгой согласованностью, тогда как системы с более слабой согласованностью, как на Фотасе, называются согласованностью в конечном счёте.
На Паксосе были свои проблемы: их законы принимались только их парламентом, который собирался в одном здании, и поэтому им не приходилось беспокоиться о том, что парламентарии внезапно станут недоступными из-за оползня или приливной волны. Однако, это был парламент свободного посещения: законодатели были склонны к приходу и уходу по своему усмотрению, временами подолгу недоступные, но не по причине стихийного бедствия, а из-за хорошей амфоры вина. Плохая акустика в зале делала ораторство невозможным, и законодатели общались друг с другом через посланников, как и Фотасчане. Поэтому, несмотря на поверхностные разногласия, парламент свободного посещения на Паксосе создавал всё те же логистические сложности, что и более рассредоточенный парламент Фотаса.
Основная идея Paxos проста: для того, чтобы внести изменения в законы, вам нужно собрать большинство парламентариев, которые должны сделать то же самое. Если кто-то пытается внести противоречивые изменения в этот момент, попытавшись собрать своё собственное большинство, в нем гарантировано будет хотя бы один человек, который знает о предложенных вами изменениях, и он поможет остановить это, сказав: «Подождите! Мы уже голосуем за что-то другое!» Аналогичным образом, когда вы захотите прочитать законы, Вы спросите большинство парламентариев о последней версии закона. Опять же, если какие-либо изменения были сделаны, по крайней мере один из них, должен был в этом участвовать. Отслеживание того, какие голосования в настоящее время проводятся, происходит на основе данных от каждого парламентария, имеющего свой собственный журнал и записную книжку, в которых он отслеживает отданные голоса и полученные сообщения.
Метод Лампорта даёт несколько важных гарантий: он позволяет выполнить чтение закона сразу после записи, поскольку после достижения состояния консенсуса в отношении закона гарантируется, что при каждой будущей попытке прочитать закон любой увидит этот консенсус; Он делает возможным чтение-модификацию-запись, поскольку после того, как начнётся процесс внесения изменения в законе в случае его успешности, никакие другие записи не будут произведены за этот период. Он также удовлетворяет «условию прогресса», так как «если большинство парламентариев находилось в Палате, и никто не входил и не выходил в течение достаточно длительного периода времени, тогда изменение, предложенное законодателем в Палате, было бы принято, а принятое изменение, появилось бы в книге каждого законодателя в Палате».
Однако, достигается это определённой ценой. Принятие закона, то есть запись в системе, требует формирования консенсуса среди большинства членов. Если некоторые из участников далеки от инициатора изменений, то это потенциально очень медленный процесс. Вы больше не можете вносить изменения в закон, просто записывая их в свой собственный журнал. Чтение закона также становится медленным, так как этот процесс теперь предполагает опрос кворума парламента.
Поэтому на практике системы Paxos предлагает два метода чтения: «Read-latest», который опрашивает кворум, и «read-recent», который просто проверяет ваш собственный журнал учёта. В «read-recent» методе отсутствуют гарантии согласованности Paxos, но он быстр. На практике многие системы требуют гарантий строгой согласованности только в некоторые моменты времени. (Например, Агния и Базил, возможно, пожелают получить последнюю информацию о законе, когда ведут свой спор о продаже овец, но в обычный день, когда один из них отправляется на рынок, он будет довольствоваться чтением собственного журнала).
Это означает, что метод Paxos всегда имеет ненулевые издержки из-за низкой скорости, которые быстро растут по мере роста числа вовлеченных людей.
Комбинированные системы и выборы диктатора: назад на Сиранос
Одним из интересных свойств этих систем является то, что их можно комбинировать. Например, как в системах Фотас, так и в Паксос, у каждого законодателя были собственные копии журналов изменений и записная книжка. Различия только в том, с какими гарантиями строгой согласованности можно делать записи в них.
Представьте себе сеть островов, каждый из которых мал, но сильно отдалён от других, как острова в Тихом океане. (Или в компьютерных терминах, представьте себе сеть центров обработки данных, каждый из которых находится внутри здания, но они разбросаны по всему миру). Обеспечение строгой согласованности хранилищ с использованием Paxos на таких расстояниях будет ужасно непрактичным, поскольку для каждого чтения или записи потребуется собрать кворум. Это потребует несколько поездок между островами. Тем не менее, каждый остров может поддерживать своё собственное согласованное хранилище, а затем отдельная межостровная организация может обрабатывать собственные законы любыми способами, просто заменяя отдельные записные книжки на отдельные островные хранилища. Клиент, ограниченный одним островом, может тогда иметь дело только с законодательной системой этого острова, в то время как клиенты, занимающиеся межотраслевым бизнесом, могут использовать другую систему, но получить все преимущества устойчивости, имея больше, чем одну точку контакта на своем острове.
Эта возможность привела к тому, что на Сираносе пересмотрели свою собственную систему. Помните, что этот остров пытался добиться строгой согласованности, разделив законотворчество так, чтобы Бавкида могла писать законы с чётным номером в понедельник, а Гален во вторник. Несмотря на то, что эта простая система вызвала проблемы, она показала важную истину. Если кто-то интересуется законами о продаже коз в понедельник, вероятно, он всё ещё будет интересоваться этим во вторник, так как изменения интересов относительно редки. Также мы узнали, что многие строго согласованные методы очень медленные, но это норма, если вам придётся использовать их в редких случаях.
Это заставило жителей Сираноса спросить себя, могут ли они избрать диктатора по какому-либо вопросу, который будет отвечать за все законы, связанные с этим вопросом. Пока каждый может легко найти диктатора по какой-либо конкретной теме, а сам диктатор не перегружен запросами, это обеспечивает более простую форму строгой согласованности. Любой, кто хотел бы изменить или прочитать актуальные законы по этому вопросу будет общаться с диктатором. Если кто-то хочет просто получить представление о законе, он может прочитать свою собственную копию свода законов, скопированного как в системе Фотаса.
Основной принцип прост. Скажем, Бавкида хочет знать закон о продаже овец. Бавкида спрашивает в центральном реестре диктаторов: «Кто нынче овечий диктатор?» Узнав, что Филимон — тематический диктатор, Бавкида понимает куда идти. Если в реестре говорится, что диктатор не назначен, то она просто предлагает закон для этого реестра: «Бавкида будет овечьим диктатором». Если этот закон будет принят, Бавкида будет диктатором и может действовать полностью самостоятельно по этому вопросу. Если закон не прошёл согласование, значит другой закон был на согласовании, поэтому она повторяет свой запрос.
Как вы, возможно, догадались, центральный реестр диктаторов — это не что иное, как ещё одно строго согласованное хранилище. Для очень маленьких групп один отшельник может быть рабочей схемой, но по причинам масштаба и надежности, обычно лучше использовать метод Paxos для создания центрального реестра диктаторов. При этом межостровной Paxos может быть очень медленным, но вам нужно получить доступ к нему только в редких случаях, когда вы хотите узнать диктатора (или стать им).
Этот метод имеет ряд замечательных преимуществ. Если только один человек заинтересован в конкретном вопросе (бывает и такое, если вопрос достаточно узкий), тогда этот человек может стать диктатором и не иметь дел с соседями вообще. Если многие люди интересуются конкретной темой, тогда этим людям придётся стоять в очереди, чтобы поговорить с одним диктатором, но он сможет сразу дать им ответ, не дожидаясь пока информация будет передана откуда-то ещё.
Однако, есть несколько проблем. Первая — смерть диктатора. Бавкида была диктатором по овечьему вопросу в течение многих лет, но однажды у неё случился сердечный приступ. Никто не знал об этом, и поэтому все, кто занимался овцами, оказались в очереди к её дверям. Ожидая, когда она появится, вся отрасль остановилась на несколько дней. Наконец, дверь сломалась. Обнаружив её смерть, жители Сираноса приняли закон, отменяющий её диктатуру. После этого они формализовали решение, установив срок полномочий. Вместо «Бавкида будет овечьим диктатором» стало «Бавкида будет овечьим диктатором до полудня в четверг». Если она всё ещё жива и заинтересована в овцах, то утром в четверг она может предложить новый закон для голосования, который продлит её правление.
Вторая проблема — перегрузка диктаторов. Одно дело быть диктатором по овцам на маленьком Эгейском острове, совсем другое быть им в Новой Зеландии, где овцы превосходят людей численностью в пропорции 7:1. Очереди перед дверью диктатора были бы огромными!
К счастью, в этой системе не требуется, чтобы диктатор был только один. Диктатор должен обеспечить строго-согласованное представление по своему вопросу, а также передавать обновления во все другие журналы, используя надёжный метод. Поэтому в Новой Зеландии не избрали одного диктатора по овцам. Из группы заинтересованных фермеров было сформировано Новозеландское Общество Овечьих Диктаторов. Будучи относительно небольшой группой относительно надёжных людей, они могут вести общий свод законов, используя Paxos (или любую другую систему) с разумной лёгкостью и скоростью. Если они понимают, что становятся перегруженными, они зовут новых членов в организацию, чтобы обслужить запросы всех клиентов.
Они могут постоянно совершенствовать свои методы. Когда Общество небольшое, они могут использовать один журнал. Они могут разделить рабочие темы между собой, и, если кто-то временно недоступен, рассмотреть его вопрос на разовой основе с использованием Paxos. В конечном счёте, по мере роста Общества они могут внедрить структуру, чтобы определять, скажем, младшего диктатора по вопросам стрижки овец в Отаго. Приятно в этом то, что их клиентам не нужно понимать и знать, как они хранят информацию внутри компании. До тех пор, пока Общество обеспечивает гарантию того, что кто-либо, приходящий к ним, получит строго согласованное представление об овечьем законе, методы Общества могут меняться по их желанию.
Классическая версия этого протокола выборов правителя называется Chubby, и вы можете узнать больше об этом по ссылке.
В итоге
Авторская иллюстрация, Yonatan Zunger, Distinguished Engineer on Privacy at Google
Если вы дочитали до этого места, вы только что изучили некоторые из наиболее сложных тем в распределенных вычислениях. Почти каждая проблема в вычислениях на базе центров обработки данных сводится к этим проблемам: как получается, что множество компьютеров, удаленных друг от друга, подключенных через ненадежные каналы, склонных к непредсказуемым переменам, тем не менее согласованно хранят информацию?
На практике существует четыре метода, которые обычно используются:
* Единые хранилища данных (Отшельник Псевдомоксоса), в которых один компьютер хранит свою собственную копию, все желающие должны использовать её по очереди. Система уязвима для одиночной катастрофы, строго согласована, жутко проста, и все остальные системы построены на её основе.
* Согласованная в конечном счёте репликация (система Фотаса), при которой каждый участник имеет своё (строго согласованное) хранилище, все читают свою собственную копию, обмениваясь обновлениями между всеми узлами и затем учитывая их. Такая система имеет преимущества скорости и простоты, а также надежности при многих видах катастроф, но не имеет гарантий строгой согласованности, при которых все будущие читатели узнают об изменении, как только вы его запишите. Эта система очень полезна в тех случаях, когда такая гарантия не требуется, например, распространение копий изображений (или других объёмных данных), которые никогда не будут изменяться после их записи и не требуют постоянного обновления.
* Решение кворума (система Паксоса, в отличие от других примеров, она на самом деле называется «Paxos»). Чтение и запись подразумевают получение подтверждений от большинства участников. Это обеспечивает строгую согласованность и надежность, но оказывается очень медленным методом, особенно при распределении системы на большой территории.
* Выборы диктатора (система Сираноса) — дорогое, строго согласованное хранилище используется для определения диктатора, который на какое-то время отвечает за какой-либо вопрос. Затем ответственная выбранная сторона использует своё собственное, более мелкое, строго согласованное хранилище, чтобы использовать и изменять закон по этому вопросу.
Самое лучшее в этих системах заключается в том, что с точки зрения клиента они различаются не методами, а гарантиями, которые они предоставляют. Теперь я оставлю вас. Мы бродили по цепочке смешных рассказов о вымышленных островах, но то, что вы узнали, не детская версия компьютерной науки. Это реальность, с которой IT-профессионалы сталкиваются каждый день. Поэтому я надеюсь, что, даже если вы сами не являетесь айтишником и не планируете им стать, у вас теперь есть лучшее понимание того, как организованы компьютерные вычисления в наше время.
