Если ваша работа не связана с компьютерными технологиями, вы, вероятно, не особо задумывались о том, как данные хранятся на компьютерах или в облаке.
Я говорю не о физических механизмах жестких дисков или микросхем памяти, а о чем-то более сложном и более понятном, чем вы думаете.
Если у вас есть фрагмент данных, который многие люди хотят прочитать и отредактировать немедленно, например, общий текстовый файл, банковский счет или мир в многопользовательской игре, как вы можете заставить всех согласиться с тем, что содержится в документе, и следить, чтобы никто не перезаписывал чужое? работа? Этот проблема консенсуса в распределенных системах , и чтобы с этим разобраться, мне придется поговорить об овцах, диктаторах и вымышленных островах Древней Греции.
«Какие еще островаЭ» ты спрашиваешь?
Оказывается, оригинальная научная статья об одном из важнейших методов решения этой проблемы была написана как пространное обсуждение того, как вымышленный парламент древнегреческого острова Паксос с его неполным составом сумел принимать законы, несмотря на Дело в том, что никто не мог достоверно сказать из числа парламентариев, когда он появится в парламенте.
Это отличная метафора того, как группа людей может договориться о том, что писать в файле, учитывая, что часть группы может быть недоступна в течение неопределенного периода времени.
Оригинальная статья — одна из самых забавных серьезных научных работ, когда-либо опубликованных, и одно из лучших объяснений сложного алгоритма, которые я когда-либо видел.
Поскольку эта метафора хорошо помогла объяснить часть проблемы консенсуса в распределенных системах и поскольку она гораздо интереснее, чем разговор о файловых системах, я собираюсь использовать ее в этой статье.
Причина, по которой эта метафора работает так хорошо, заключается в том, что в обоих случаях с файлами и законами у нас есть некоторые данные, которые многие люди хотят изменить, многие люди хотят прочитать, но никто не хочет тратить все на этот процесс.
время.
Одновременное чтение книги законов ограничено количеством людей, которые могут одновременно просмотреть книгу, точно так же, как чтение файла может быть ограничено скоростью, с которой данные могут быть получены с диска.
Для одновременного написания требуется, чтобы все согласились не отменять решение друг друга, но без длительных дебатов для его достижения.
Как мы можем решить эту проблему, если не считать того, что каждый человек в мире будет по очереди пользоваться книгой? Вместо того, чтобы говорить о файловых системах и операциях с базами данных, перенесемся на острова фальшивого «гей-моря», где совпадения с реальностью случайны, а жители одержимы изданием указов и законов.
Нам просто нужно сделать так, чтобы каждый мог прочитать закон, когда ему это необходимо.
Далее следует несколько запутанных историй, и к тому времени, как мы закончим, вы поймете проблему распределенного консенсуса, с которой сталкиваются ИТ-специалисты.
За исключением овец.
Островов, кстати, будет много, и названия их полностью выдуманы, кроме того, который стал поводом для этой истории, но об этом позже.
Отшельники и мексиканская еда
Начнем наш рассказ с простейшего случая на острове Псевдемоксос.
Живет отшельник, который пишет законы и указы для себя.
Сначала он использовал очень простой и понятный метод: блокнот и карандаш.
Он мог добавлять законы, изменять законы и реорганизовывать законы по своему желанию, просто стирая и записывая новые там, где он хотел (именно так работали диски на наших компьютерах до конца 90-х годов).
Этот метод, казалось, работал довольно хорошо, за исключением того, что бумага слишком изнашивалась при стирании.
Однако отшельник осознал ужасную обратную сторону этого решения, когда однажды на берег выбросило коробку сомнительных буррито.
Внося изменения в закон – стирая текст и начиная что-то писать, отшельник пережил то, что мы вежливо назвали бы «промышленной чрезвычайной ситуацией».
Когда несколько потрепанный отшельник вернулся к своему кодексу, он обнаружил, что не только забыл то, что собирался написать, но теперь пустое место в середине книги не было заполнено ни старым, ни новым законом, и каракули, написанные наспех, читать было невозможно! Метафора описывает, что происходит с компьютером или программой в случае сбоя: данные на диске могут быть безнадежно испорчены.
Более серьезные неудачи отшельника можно сравнить с такими событиями, как поломка блока магнитной головки, которая может нанести ущерб не только написанным словам, но и оставить довольно неприятный и неизгладимый след на всей странице.
Эти проблемы были решены с помощью ведения журнала.
Идея состоит в том, чтобы ничего не стирать, подобно тому, как люди ведут журналы или лабораторные дневники.
Теперь наш отшельник хранит стопку бумаг, а когда хочет изменить законы, добавляет в свой журнал новую запись: 4 июня, 10:32 — Добавьте к законам о безопасности пищевых продуктов: запрещено употребление буррито, находившихся в море в течение неопределенного периода времени.
Каждое редактирование, будь то вставка, изменение или удаление, записывается ручкой в конце журнала.
Отшельник защищен от чрезвычайной ситуации, потому что он никогда не стирает свои записи.
В худшем случае имеется неполная, поврежденная запись журнала или следы неудачной попытки записи, которые можно просто игнорировать.
Журнал имеет дополнительное преимущество: он фиксирует все изменения.
Чтобы увидеть, как выглядел закон год назад, наш отшельник может просто прочитать журнал и остановиться на этой дате.
Одним из очевидных недостатков журнала является то, что его труднее читать, чем блокнот. Чтобы узнать о текущей редакции закона о пищевой безопасности, нужно начать с начала журнала и прочитать до конца, отслеживая все изменения.
Поскольку объем журналов со временем увеличивается, этот процесс становится все более трудоемким.
Чтобы облегчить задачу, наш отшельник держит стопку пустых справочников.
Всякий раз, когда журнал становится слишком объемным, он находит время для составления свода законов: он читает журнал от начала до конца, излагая весь закон в актуальном состоянии, а затем записывает это положение в свод законов.
На обложке свода законов он пишет: «Таково состояние закона на [такое-то число]».
Продолжение использования закона требует лишь того, чтобы он прочитал свод законов и журнал изменений, внесенных после даты сбора закона.
Журналы старше этой даты можно сохранить, если иногда требуется история изменений перед хранилищем, или просто удалить.
Если наш отшельник слишком занят разработкой нового законодательства, чтобы регулярно писать книгу законов, мы можем вызвать писца (то есть вторую компьютерную программу, работающую параллельно с первой), чтобы тот помог ему.
Переписчик прочитает журнал раньше оговоренного времени, напишет свод законов и сообщит отшельнику, что он закончил, чтобы он мог начать использовать новую коллекцию.
Писцу не нужно ничего говорить, чтобы он выполнил свою работу, поэтому отшельник может продолжать свою работу молча.
Этот метод имеет еще больше преимуществ.
Наш отшельник стал широко известен своей мудростью (например, его уроками об отказе от мексиканской кухни, прибывшими морем), многие, возможно, захотят прочитать его законы.
Пока этих читателей устраивает свод законов определенной даты, они могут делать свои собственные копии и читать их свободно, не беспокоя мудреца.
Обращаться к нему напрямую должен только тот человек, которому нужна последняя редакция законов.
(Использование журналирования на персональных компьютерах началось в конце 1990-х годов и получило широкое распространение в середине 2000-х годов.
Вероятно, ваш компьютер использует журналирование и сейчас.
)
Хаос на острове Фотас
Рядом с островом Псевдомоксос находится более крупный остров Фотас.
Этот остров малонаселен, но людей достаточно, и все жители согласны с тем, что им нужна консолидированная система законов, регулирующих их жизнь.
Однако фотасанцы известны своей яростной независимостью: они не позволяют никакому другому жителю или группе управлять ими, и поэтому решили, что любой житель Фотаса будет иметь право принимать законы.
Для этого вы просто записываете закон на листе бумаги с датой, временем и своим именем и отправляете с ним гонца в библиотеку Фотас, где писец добавит его в юридические журналы.
(Это означает, что многие люди пытаются сохранять изменения в одном файле за раз, не пытаясь сначала достичь консенсуса относительно того, что будет в файле.
) Чтобы увидеть, почему что-то может пойти не так, давайте начнем с Агнии, которая живет на одном из побережий острова и очень обеспокоена чистотой ритуальных жертвоприношений.
Она представляет закон: 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 уже устанавливает Национальный день оливок и нигде не упоминается «равный одной монете».
Что он должен сделать? Представьте себе, что Базил заменяет «платить в общий фонд библиотеки» на «платить Базилу!» Аналогичные ситуации возникают, когда несколько авторов конкурируют за редактирование одного и того же свода законов.
Существует множество решений, каждое из которых имеет свои плюсы и минусы.
Эти решения можно разделить на два основных типа моделей.
Одним из типов является «конечная согласованность» или «конечная согласованность», когда несколько правил, регулирующих запись, позволяют всем записывать одновременно, не разговаривая друг с другом.
Эта модель гарантирует, что если в течение некоторого времени не будет новых обновлений, все копии данных (реплики) станут согласованными.
Цена такого подхода в том, что никто не может знать точное состояние закона на текущий момент, каждый может знать только то, каким оно было совсем недавно.
Другая модель — «строгий консенсус», в котором возможны все типы написания, и каждый может знать текущее состояние закона, но с ценой достижения консенсуса для каждой записи.
Оба типа моделей оказываются полезными.
Иногда у вас есть информация, для которой вполне нормально быть немного устаревшей.
Например, когда жители Фотаса делают свой ежегодный фотоальбом.
Они делятся фотографиями друг с другом, и нет необходимости иметь самые последние фотографии, поэтому будет полезно использовать более простую «конечную согласованность».
С другой стороны, для реальных законов «строгая последовательность» будет более полезной, несмотря на ее издержки.
(Это справедливо и для компьютеров.
Например, изображения, которые вы загружаете в Google, хранятся в системе с использованием «конечной согласованности», а списки ACL, определяющие права просмотра, хранятся с использованием строгой согласованности) Вернемся на остров Фотас.
В конце концов, все имеет смысл
Мы могли бы легко решить первую из наших проблем — конфликтующие законы с одинаковой временной меткой — просто добавив правило тай-брейка, чтобы никакие две временные метки не могли быть одинаковыми.
Например, мы могли бы добавить к метке имя автора в алфавитном порядке, чтобы в случае гонки изменения от Агнии всегда были сделаны раньше Василия.
(Или, если имена одинаковы, мы можем присвоить каждому жителю уникальный номер).
Как только временные метки перестанут совпадать, путаницы не будет. В город приходит Галатея, и закон Василия — единственный.
Если такая перезапись представляет собой проблему, ее можно избежать, заранее договорившись, кто и что может писать.
Например, в течение одной недели Агния может редактировать только четные законы, а Василий — нечетные, и наоборот, следующую неделю.
(На компьютерах файловое пространство часто разделено, поэтому два автора вообще никогда не пытаются писать в один и тот же файл, а тем более одновременно.
Например, каждой вновь загруженной фотографии может автоматически присваиваться уникальное имя.
) Для решения второй проблемы мы исключаем возможность ее существования: меняем правила логирования, запрещающие внесение изменений, разрешающие только полную замену, добавление или удаление.
Это означает, что никакая формулировка в журнале не может зависеть от текущего состояния закона при ее толковании.
Агнии пришлось бы записать свой закон в виде 1 июня, 10:02 - Закон 32.1.3 изменен на "Любое лицо, продающее козу, обязано уплатить Сенату налог в размере двух монет".
Агния.
Поскольку ее запись имела более позднюю временную отметку, ее версия закона легко опровергает версию Бэзила.
Преимуществом этой системы написания законов является скорость и простота: любой может написать закон в любое время, не консультируясь ни с кем.
Однако использование законов становится удивительно сложным.
Если вы хотите узнать действующую ставку налога на продажу коз, вы идете в библиотеку и просите прочитать Закон 32.1.3. Придя в 10:05, вы прочтете свод законов и журнал изменений.
Закон гласит: «Любой человек, продающий козу, должен заплатить Сенату налог в размере одной монеты».
Видите ли, Агния изменила закон в 10:02, а ее посланник еще не прибыл! Чтобы немного упростить задачу, гонцы могут зарегистрироваться в библиотеке: всякий раз, когда приходит гонец от каждого жителя деревни, после доставки сообщения они пишут на доске заметку о том, что все сообщения Фотасмана были доставлены в такое-то время.
Тогда посетитель сможет, глядя на доску, увидеть, что последнее сообщение от Агнии было в 9 утра, а от Василия в 7 часов предыдущего вечера.
Теперь вы, по крайней мере, знаете, что законы, которые вы читаете, верны по состоянию на 7 часов предыдущего вечера — самое раннее время, указанное на доске, и все изменения, написанные до этого времени, уже должны были поступить.
(Это время называется «низкой отметкой») Конечно, если конкретный гражданин не очень противоречив, обновления от него могут быть редкими, и все будут задаваться вопросом: «Изменения просто еще не дошли до библиотеки или их просто нетЭ» Чтобы избежать этой проблемы, каждый фотачан должен регулярно отправлять мессенджер в библиотеку и независимо от того, есть ли у них обновления или нет, чтобы поддерживать доску в актуальном состоянии.
Жители Фотаса — творческие люди, поэтому они быстро поняли, что этот постоянный поток посланников может облегчить им жизнь и другими способами.
Вместо утомительного похода в библиотеку они могут просто хранить у себя копию свода законов и журнала изменений.
Теперь их мессенджер каждый раз возвращается со всеми последними изменениями в журнале, а также копией дат, которые были на доске.
Они обновляют свои копии и могут ссылаться на них.
Однако по мере увеличения населения Фотаса передвижение гонцов, бегущих в библиотеку, стало проблемой.
Для переписчиков, копирующих журналы и кодексы, задача просто принять закон об изменении налога на коз стала решаться ужасно медленно.
К счастью, фотаситяне поняли, что свою проблему они уже решили: имея свои экземпляры закона, им уже не нужна одна центральная библиотека! Вместо этого было открыто несколько библиотек-филиалов.
Мессенджеры могут доставлять и получать обновления в близлежащие филиалы, а другие мессенджеры будут путешествовать между каждой парой библиотек-филиалов, чтобы доставлять копии всех обновлений.
В результате была построена «деревовидная карта»: структура, соединяющая каждую ветку друг с другом и каждого жителя с веткой.
Обновления доставляются только по маршрутам, указанным на карте, но поскольку каждый гражданин или филиал связан с другим гражданином или библиотекой, в конечном итоге все изменения, внесенные любым гражданином, будут доступны всем на Fotas. В конечном итоге у всех в руках будет один и тот же журнал, а своды законов — в в конечном итоге будет согласовано ! У этого подхода есть много преимуществ.
Например, когда речь идет о путешествии по опасной и платной дороге, которая является единственным путем от центра острова к его восточным горам, по этому пути достаточно пройти только одному посыльному.
Он будет передавать обновления с запада на восток и обратно, а с ответвлениями на противоположных концах дороги он будет распространять информацию по остальной части острова.
(На этом этапе можно отметить, что никакой значимой разницы между отдельными жильцами и филиалами библиотеки уже нет. Копия есть у каждого, и, пока они продолжают отправлять гонцов по соответствующим маршрутам, каждый может изменить закон, просто написав это в свой журнал и распространив информацию через систему) Этот метод очень эффективен, но имеет три заметных недостатка.
Во-первых, никто не может знать с уверенностью текущее состояние закона.
В отличие от отшельника с Псевдомоксоса, который писал в своем дневнике, житель Фотаса больше не имеет гарантии, что после внесения изменений любой, кто прочтет этот закон в будущем, увидит эти изменения.
Только те, кто прочитает это в далеком будущем, увидят это изменение.
(Это называется отсутствием согласованности без «проверки чтения после записи»).
Во-вторых, чтение-изменение-запись выполнить невозможно.
Если два фатасианца попытаются изменить один и тот же закон, последствия будут непредсказуемыми.
Чтобы обойти эту проблему, фотасианин должен найти способ гарантировать, что он единственный человек, пытающийся изменить данный закон, и что он прочитал последнюю версию закона, прежде чем вносить изменения.
Третий, этот метод уязвим к сбоям в сети: представьте, что дорога, ведущая к удаленному дому одного из жильцов, отрезана обвалом камня.
Никакие обновления не могут быть получены им из внешнего мира, и никто не может предполагать, что у него есть все обновления за какое-то время после его последнего сообщения.
Также никто не может предположить, что с тех пор он ничего не передавал.
Остальные предполагают, что житель не знает о камне и продолжает писать в своем дневнике, ожидая гонца, который никогда не придет. Таким образом, вся система останавливается, никто не двигается вперед с нижней отметкой, никто не может создать новый свод законов, потому что единственный путь потерян! В компьютерной практике такие проблемы реальны и серьезны.
Всякий раз, когда один узел (компьютер или, возможно, центр обработки данных) выходит из строя, инженерам необходимо немедленно оценить ситуацию и определить, можно ли восстановить узел и снова подключить его к сети.
В противном случае другие серверы не смогут формировать сводку, и их журналы будут продолжать расти, создавая проблемы для читателей.
При этом изолированный писатель будет все больше и больше рассинхронизироваться.
Если проблему не удается устранить быстро, изолированные узлы часто полностью отключаются, а для маршрутизации людей, желающих подключиться к ним, используются другие методы (часто гораздо более медленные внешние сети).
Однако остальные узлы продолжают ждать.
Если станет ясно, что проблема не решится быстро, то остается только один вариант: полностью удалить недостающие узлы из сети, предложив другим узлам сделать вид, что этих узлов больше нет и обновлений от них не будет. Узлы развиваются, но любые записи, сделанные изолированным узлом, будут потеряны навсегда, если они не будут скопированы и перенесены в основную сеть другими способами.
Клиенты Fotas и строгая последовательность
Итак, то, что мы видели выше, — это разумное решение для яростно независимых островитян, таких как фотанцы, которые хотят иметь возможность быстро писать и не особо заинтересованы в возможности читать последнюю версию чего-либо.Но что происходит в ситуациях, когда это просто недопустимо? Законы на самом деле являются хорошим примером: если вы совершили преступление в 10:00, имеет большое значение, был ли закон против него принят в 9:00 или в 11:00. Знать закон в настоящем времени важно.
Проблем стало гораздо больше, когда Фотас начал развивать свой юридический бизнес.
Видите ли, Фотас окружен множеством гораздо меньших островов, каждый из которых имеет свою промышленность и, следовательно, нуждается в своем своде законов.
Будучи маленькими островами, они не имеют ресурсов для содержания системы писцов и посланников, подобных Фотасу.
Они никогда не смогли бы обучить своих писцов и посланников работать так быстро и эффективно.
Так что эти маленькие острова продолжали в течение многих лет использовать самое простое решение: на каждом острове был свой отшельник с журналом в псевдоэмоксосском стиле, и все желающие прочитать или изменить закон просто выстраивались в очередь, чтобы пообщаться с отшельником.
Метод медленный и малоэффективный, особенно если отшельник заболел или был смыт приливной волной.
Но без ресурсов Фотаса они просто пошли своим путем.
Фотасианцы, почувствовав возможность, предложили свои кодексы права в качестве услуги своим соседям (LaaS).
Клиентские острова могли читать и писать свои указы как часть свода законов Фотаса, причем каждый остров получал свою собственную главу, которую никто другой не мог писать.
Соседи поначалу обрадовались: им больше не пришлось выстраиваться в очередь, чтобы поговорить с отшельником.
Процесс стал гораздо быстрее, даже с учетом времени в пути до Фотаса.
(На самом деле фотасианцы работали над сокращением времени в пути, открывая посольства на различных островах, которые стали частью сети).
Кроме того, это было намного надежнее.
Когда цунами разрушило несколько островов и серьезно повредило Фотас, у каждого жителя Фотаса были копии всего свода законов, и систему можно было легко восстановить.
Поскольку Фотас находился недалеко от многих островов, острова начали использовать систему Фотас как способ надежной пересылки сообщений.
Но две проблемы, о которых мы говорили ранее, стали более очевидными.
Например, на острове Парафоитас (один из островов-клиентов) винная компания Андрос использовала складское помещение Фотаса для отслеживания своих заказов.
Однажды Андрос получил заказ на 100 амфор вина для свадьбы местного политика и сделал запись в книге заказов.
На следующий день один из его удаленных сотрудников проверил книгу заказов, но мессенджер к этому времени не смог доставить запись, будучи заблокированным в другом порту из-за шторма.
Сотрудник не знал о заказе, а вино не было готово до дня свадьбы! На острове Сиранос дела обстояли не лучше.
Пытаясь решить проблему чтения-изменения-записи так, чтобы только один человек мог изменить закон одновременно, они назначили Бавкиса ответственным за законы понедельника с четными номерами, а Галена — за остальные.
Во вторник наоборот и так далее.
Однако Гален был очень нетерпелив и изменил законы четности в полночь во вторник, как только представилась такая возможность.
К сожалению, Бавкида изменила тот же закон вчера вечером в 11:58, и ее изменения еще не доставлены Галену.
Гален узаконил и непреднамеренно переписал работу Бавкиды.
Некоторые из соседних островов остались вполне довольны.
Например, Опитоитас использовал репозиторий Fotas для архивирования местной поэзии.
После того, как стихотворение было заархивировано, оно никогда не менялось, а перечитывалось и добавлялось новые стихи.
Для них система «Фотас» была одновременно надежной и недорогой.
Но в целом островов было достаточно, для которых стали очевидны недостатки системы «Фотас».
Парламент Паксоса
Итак, вот мы прибыли на остров Паксос.
Это настоящее название острова в Весёлом море с парламентской системой, придуманной Лесли Лэмпортом.
Он привел меня ко всем этим метафорам, а описанный им метод широко известен как «алгоритм Паксоса».
(Все остальные названия островов в этой статье — собственное изобретение автора) Хорошая новость об этом алгоритме заключается в том, что он не сложнее того, что мы обсуждали ранее, и статья Лэмпорта описывает проблему в том же стиле.
Вот эта статья «Неполный парламент» .
Плохая новость заключается в том, что я не смог придумать объяснения короче, чем объяснение Лэмпорта.
Это превратило бы эту длинную историю в безумно длинную.
Хорошо, что я могу кратко изложить вам эту идею! Жители Паксоса были заинтересованы в отслеживании изменений в своих законах и хотели, чтобы каждый гражданин мог знать действующие законы страны.
Они также хотели согласованности чтения, изменения и записи, поскольку в противном случае могли быть приняты противоречивые законы.
Этот тип согласованности часто называют сильной согласованностью, тогда как системы с более слабой согласованностью, такие как Fotas, называются итоговой согласованностью.
У Паксоса были свои проблемы: их законы принимались только их парламентом, который собирался в одном здании, и поэтому им не приходилось беспокоиться о том, что парламентарии внезапно станут недоступными из-за оползня или приливной волны.
Однако это было свободный парламент : законодатели были склонны приходить и уходить когда им заблагорассудится, порой будучи недоступными в течение длительных периодов времени, не из-за стихийного бедствия, а из-за хорошей амфоры вина.
Плохая акустика в зале делала ораторское искусство невозможным, и законодатели общались друг с другом через посланников, как и Фотачане.
Поэтому, несмотря на поверхностные разногласия, свободно посещающий парламент на Паксосе представлял все те же логистические трудности, что и более рассредоточенный парламент Фотаса.
Основная идея Паксоса проста: чтобы изменить законы, нужно добиться того, чтобы большинство парламентариев сделали то же самое.
Если кто-то на этом этапе пытается внести спорные изменения, пытаясь собрать свое большинство, среди вас гарантированно найдется хотя бы один человек, который знает об изменениях, которые вы предлагаете, и он поможет остановить это, сказав: «Подождите».
! Мы уже голосуем за что-то другое!» Точно так же, когда вы захотите прочитать законы, вы спросите большинство парламентариев о последней версии закона.
Опять же, если были внесены какие-либо изменения, то хотя бы одно из них должно было быть задействовано.
Отслеживание того, какие голоса происходят в данный момент, основано на данных каждого парламентария, у которого есть свой журнал и блокнот, в котором он отслеживает поданные голоса и полученные сообщения.
Метод Лэмпорта дает несколько важных гарантий: он позволяет читать закон сразу после его написания, поскольку, как только достигнуто состояние консенсуса по поводу закона, гарантируется, что при каждой будущей попытке прочитать закон любой увидит этот консенсус; Это делает возможным чтение-изменение-запись, поскольку как только начнется процесс внесения изменений в закон, если он окажется успешным, в течение этого периода никакие другие записи производиться не будут. Это также удовлетворяет «условию прогресса», поскольку «если бы в Палате было большинство парламентариев, и никто не входил и не выходил в течение достаточно длительного периода времени, то изменение, предложенное законодателем в Палате, было бы принято, и принятые изменения появятся в книге каждого законодателя в Палате представителей».
Однако это достигается определенной ценой.
Принятие закона, то есть вхождение в систему, требует формирования консенсуса среди большинства членов.
Если некоторые из участников далеки от того, чтобы инициировать изменения, то это потенциально очень медленный процесс.
Вы больше не сможете вносить изменения в закон, просто записывая их в свой журнал.
Чтение закона также становится медленнее, поскольку теперь этот процесс включает в себя опрос кворума парламента.
Поэтому на практике Paxos предлагает два метода чтения: «Read-latest», который опрашивает кворум, и «read-recent», который просто проверяет ваш собственный реестр.
Методу «read-recent» не хватает гарантий согласованности Paxos, но он работает быстро.
На практике многие системы требуют строгих гарантий согласованности только в некоторые моменты времени.
(Например, Агния и Василий, возможно, захотят получить самую свежую информацию о законе, когда спорят о продаже овец, но в обычный день, когда один из них идет на рынок, он довольствуется чтением собственного журнала) .
Это означает, что метод Paxos всегда имеет ненулевые накладные расходы из-за низкой скорости, которые быстро возрастают по мере увеличения количества задействованных людей.
Комбинированные системы и выборы диктаторов: вернемся к сэру
Теги: #Сетевые технологии #ИТ-инфраструктура #Хранение данных #Облачные вычисления #облако #Распределенные системы #консенсус #согласованность #Paxos-
Обзор Нетбука Meego Samsung N100
19 Oct, 24 -
Введение В Распознавание Эмоций
19 Oct, 24
