NET·VI Сети Глава 44 из 65
Парламент острова Паксос
Законодатели острова то и дело уходят на рынок, гонцы теряются, а закон всё равно должен быть принят — один, и записан у всех одинаково. Глава пересказывает притчу Лесли Лэмпорта, которую рецензенты велели переписать без греков, а вы управляете парламентом и ломаете его: убиваете председателя, насылаете шторм, подкупаете генерала.
Опирается на: 43 · Анатомия этой страницы 39 · Гонки
Что вы унесёте из главы
- почему «распределённое» трудно: отличать мёртвого от медленного, упорядочивать события без общих часов, договариваться при потерях и предательстве
- как работает консенсус: кворумы, протокол Паксоса и Raft с выборами председателя и журналом, — и что значит «закон принят»
- что выбирает система, когда сеть разрезана (теорема CAP), и как живут системы с согласованностью в конечном счёте
6Как миллиарды компьютеров работают вместе, если ни один из них не главный?
Прошлая глава кончилась тремя копиями одного счёта, которые разошлись: часть сообщений потерялась, и на вопрос «сколько денег на счёте» у системы стало три ответа. Повторять сообщения, как это делает TCP, тут мало: копия может умереть вместе с сообщением или надолго замолчать. Как заставить тысячу ненадёжных машин вести себя как одну надёжную, если главной среди них нет и назначить её некому? В конце 1980-х Лесли Лэмпорт попытался доказать, что это невозможно. Доказательство не вышло. Вышел алгоритм, и рассказал его Лэмпорт в виде притчи о парламенте греческого острова.
Отчёт о раскопках
Дальше — притча в пересказе. Основной текст — хроника острова, а врезки с комментариями переводят её на язык компьютеров, как это делал Марзулло. Хронику можно не только читать: вы будете отправлять законодателей на рынок, насылать шторм, подкупать генерала и смотреть, что выдерживает, а что ломается.
Остров, где никто не главный
Парламент Паксоса принимал законы: «оливки не продавать после заката», «козы пасутся по чётным дням». Каждый законодатель вёл свою книгу законов, и книги обязаны были совпадать: если в одной седьмым записан закон об оливках, то в любой другой седьмым записан он же, а не закон о козах. Общей книги не было, и главного законодателя тоже. Законодатели общались через гонцов.
Трудность в том, что паксосцы были людьми занятыми. Законодатель мог в любой момент уйти из зала на рынок и вернуться через час — или через неделю. Гонец мог заблудиться, задержаться в таверне или прийти дважды. Зато, к чести острова, никто не лгал: ушедший на рынок молчал, а гонец, если уж доходил, доносил послание в точности.
Список бед кажется знакомым: потери пакетов чинила глава 42, порядок событий у потоков наводила глава 39. Но у распределённой системы есть беда, которой не было ни там, ни там, и с неё начинаются все остальные.
Умер или задумался?
Законодатель Алкей ждёт ответа от Бианта. Ответа нет уже две минуты. Биант ушёл на рынок? Или гонец заблудился? Или Биант просто задумался над ответом и вот-вот пришлёт его? Изнутри зала эти случаи неотличимы: во всех трёх Алкей видит одно и то же — тишину. Остаётся договориться ждать определённое время, а потом считать молчуна ушедшим. Тот же вопрос — сколько ждать расписку — решал будильник TCP в главе 42, только там ошибка стоила лишнего повтора, а здесь — похорон живого. Сторожевой таймер Pathfinder из главы 39, который перезагружал компьютер, когда важная задача не успевала к сроку, был таким же договором. Пусть Биант каждые 100 мс шлёт гонца «я здесь», а Алкей решает, сколько ждать, прежде чем объявить его ушедшим.
Биант весь час жив, но короткий тайм-аут хоронит его десятки раз за час. Длинный не ошибается, зато смерть, когда она случится, заметит только через секунды, и всё это время парламент будет ждать мертвеца. Идеального тайм-аута нет, это всегда размен между скоростью и ложными тревогами. Наша модель тут ни при чём. В 1983 году Майкл Фишер, Нэнси Линч и Майкл Патерсон доказали: если сообщения могут задерживаться сколь угодно долго, то никакой детерминированный алгоритм не гарантирует, что узлы договорятся, даже когда отказать может всего один из них. Результат так и называют по фамилиям, FLP; в журнале статья вышла в 1985 году. Он не запрещает договариваться — он запрещает гарантировать, что договоришься за конечное время при любом поведении сети. Поэтому все алгоритмы этой главы устроены одинаково: что бы ни случилось, двух разных законов они не примут, а принять какой-нибудь закон обещают, только когда сеть хоть ненадолго успокоится.
В распределённой системе нельзя отличить мёртвый узел от медленного. Любое решение «он умер» — догадка по тайм-ауту, и алгоритм должен оставаться правильным, даже когда догадка неверна: «мёртвый» может вернуться и заговорить.
Часы без часовщика
У каждого законодателя были свои песочные часы, и шли они как попало. Поэтому в книгах острова вместо «в полдень» писали «после того, как», и неспроста: если доверять часам, получается чепуха. Вот три законодателя, они же три потока из главы 39, которые обмениваются гонцами через очереди. Часы Бианта отстают на 40 мс, часы Главка спешат на 25. Каждый записывает в общий журнал время по своим часам.
По стенным часам Биант получил гонца об оливках раньше, чем Алкей предложил закон. Отстающие часы на 40 мс переставили следствие впереди причины. Серверы сверяют часы по сети, но расхождение в миллисекунды остаётся всегда, а события на быстрых машинах разделяют микросекунды. Второй список упорядочен иначе, и в нём всё на месте: каждый ответ стоит после вопроса.
Лэмпорт предложил измерять время в распределённой системе причинами и следствиями. Событие $a$ случилось раньше события $b$ (пишут $a \to b$), если $a$ могло повлиять на $b$. Это бывает в трёх случаях: оба события у одного законодателя и $a$ было первым; $a$ — отправка гонца, $b$ — его получение; или от $a$ до $b$ ведёт цепочка таких шагов. Если ни $a \to b$, ни $b \to a$, события параллельны: ни одно не могло знать о другом, и спрашивать, какое из них было «на самом деле» раньше, бессмысленно — как в теории относительности.
Порядок «случилось раньше» поддерживают часы Лэмпорта, хотя от часов у них одно название: это счётчик у каждого законодателя. Правил два. Перед каждым событием прибавь к счётчику единицу; отправляя гонца, дай ему с собой значение счётчика. Получив гонца, поставь счётчик в максимум из своего и принесённого — и тоже прибавь единицу. Так в ячейке выше Биант, у которого было 0, получил от Алкея отметку 2 и стал 3.
Если $a \to b$, то отметка $C(a) < C(b)$.
Достаточно проверить один шаг цепочки: дальше неравенства складываются, как $C(a) < C(c) < C(b)$. Если $a$ и $b$ у одного законодателя и $a$ раньше, то между ними счётчик только рос, и перед $b$ ещё прибавилась единица. Если $a$ — отправка, а $b$ — получение, то гонец принёс $C(a)$, а получатель поставил себе не меньше $C(a) + 1$.
Обратное неверно, и это стоит запомнить: в ячейке у «Биант получил „я за“» и «Главк ушёл на рынок» одна и та же отметка 7, а будь у Главка ещё пара дел, его уход получил бы и бо́льшую отметку, чем ответ Бианта, хотя эти события параллельны. Меньшая отметка не значит «было раньше» — она значит «не было позже». Зато если упорядочить все события по отметке, а равные — по имени законодателя, получится один общий ряд, в котором ни одно следствие не стоит перед причиной. Его Лэмпорт и предлагал использовать: если все законодатели выполняют законы в этом порядке, их книги совпадут. Нарисуйте свою историю гонцов и проверьте, как ведут себя отметки.
Векторные часы: как отличить «раньше» от «параллельно»
Часы Лэмпорта не умеют сказать, параллельны ли два события. Это умеют векторные часы. Идею в начале 1980-х независимо придумывали несколько авторов, а имя и строгую теорию дали в 1988 году, тоже независимо друг от друга, Колин Фидж и Фридеман Маттерн. Здесь каждый законодатель хранит целый вектор, по числу на каждого законодателя острова: сколько событий того-то он знает. Своё число он увеличивает перед каждым событием, гонец несёт весь вектор, а получатель берёт покомпонентный максимум. Тогда $a \to b$ ровно тогда, когда вектор $a$ во всех позициях не больше вектора $b$ и хоть где-то меньше; а если в одной позиции больше, а в другой меньше — события параллельны. Платят за это размером: у тысячи узлов вектор из тысячи чисел едет с каждым сообщением. Похожие векторы версий хранила для каждого объекта база Dynamo, к которой мы вернёмся в конце главы.
Счётчик Лэмпорта с отправкой и получением — первая задача главы, «Часы острова». Подвох там в том, что журналы законодателей приходят раздельно, и получение гонца в одном журнале нельзя обработать, пока не обработана его отправка в другом.
Подкупленный законодатель
Паксосцы были честны. Если бы среди них завёлся лжец, протоколу острова пришлось бы куда хуже, и как именно хуже, Лэмпорт выяснил ещё до Паксоса — на других героях.
Несколько дивизий осаждают город. Командир решает, наступать или отступать, и рассылает приказ лейтенантам через гонцов. Лейтенанты могут переговариваться между собой. Среди генералов, возможно, есть предатель — он может врать кому угодно и что угодно, в том числе разным генералам разное. Нужно, чтобы все верные лейтенанты выполнили один и тот же приказ, и если командир верен — именно его. Такой отказ, при котором узел шлёт противоречивую ложь, называют византийским. Сломанный датчик, повреждённая память, взломанный сервер ведут себя именно так.
С тремя генералами предатель всегда может сорвать дело, и причина видна, если встать на место первого лейтенанта. Командир говорит ему «наступать», второй лейтенант говорит, что ему командир велел «отступать». Кто из двоих лжёт? Если лжёт второй лейтенант, верный командир требует наступать. Если лжёт командир, то и второй лейтенант мог честно пересказать своё. Первый лейтенант видит в обоих случаях одно и то же и не может их различить, а правильные действия в них разные. С четырьмя генералами у каждого лейтенанта три голоса, и одна ложь их не перевешивает. Проверим это перебором всех способов предательства для алгоритма из статьи 1982 года, OM(1).
У трёх генералов предатель-лейтенант срывает совет в двух случаях из двенадцати: когда верный командир приказал наступать, а предатель пересказал «отступать», у верного лейтенанта ничья, и он отступает вопреки приказу. У четырёх — ни одного срыва из 32. Перебор доказывает это только для одного алгоритма, а статья 1980 года — для любого. Общий итог такой: при обычных, неподписанных сообщениях $f$ предателей выдерживает система из $3f + 1$ узлов, и не меньше. Византийскую устойчивость строят там, где цена ошибки высока или участникам нельзя доверять: по данным открытых источников, её используют, например, системы управления полётом Boeing 777 и 787. Парламент Паксоса, как и большинство систем в дата-центрах, исходит из того, что узлы честны и только падают, — и платит за отказы меньше: чтобы пережить $f$ ушедших на рынок, ему хватает $2f + 1$ законодателей. Почему именно столько, объясняет следующий раздел.
Как принять один закон
Начнём с самого простого: парламент должен принять один закон. Предложить его может кто угодно, предложений может быть несколько, и нужно, чтобы в итоге все книги назвали один и тот же закон. Это задача о согласии, или консенсус. Требований три. Принят может быть только предложенный закон — нельзя договориться, всегда принимая «ничего». Принятый закон один: двух разных не бывает никогда. И если большинство законодателей в зале и гонцы ходят, закон рано или поздно принимается.
Первая мысль — голосование: закон принят, если за него больше половины голосов. Половина выбрана не наугад: любые два большинства пересекаются, а значит, о каждом решении знает хотя бы один участник любого следующего решения.
Если в парламенте $n$ законодателей, а $A$ и $B$ — две группы, в каждой больше $n/2$ законодателей, то у $A$ и $B$ есть общий член.
Если бы общих членов не было, в $A$ и $B$ вместе было бы $|A| + |B| > n/2 + n/2 = n$ разных законодателей, а их всего $n$.
Группу, которой достаточно, чтобы решение считалось принятым, называют кворумом. Большинство — самый простой кворум, и проверить свойство из теоремы на пяти законодателях можно перебором.
Двойки могут не пересекаться, тройки пересекаются всегда. Поэтому парламенту из пяти законодателей не страшен уход двоих: оставшиеся трое — кворум. Из $2f + 1$ законодателей можно потерять $f$, а больше — нельзя: тогда кворума не соберётся, и парламент замрёт, хотя и не ошибётся.
Но одного кворума мало. Пусть два законодателя одновременно предложили разные законы — об оливках и о козах, и гонцы разнесли предложения в разном порядке. Если каждый голосует за первое услышанное и больше не меняет голос, может выйти два голоса за оливки, два за коз и один пропавший гонец — и закона не будет никогда. Если разрешить менять голос на последнее услышанное, закон рано или поздно наберёт большинство, но потом может набрать его и другой. Паксосцы решили это так.
Закон предлагает жрец, и каждое его предложение — голосование со своим номером, у разных жрецов номера разные. Голосование идёт в две фазы. В первой жрец спрашивает законодателей: «Обещаете ли вы не участвовать в голосованиях с номером меньше моего? И за что вы уже голосовали?» Законодатель обещает, если не обещал уже кому-то с бо́льшим номером, и называет свой последний голос. Получив обещания от кворума, жрец смотрит на эти голоса. Если кто-то из кворума уже голосовал, жрец обязан предложить закон из голосования с самым большим номером — свой закон он отбрасывает. Только если никто не голосовал, он предлагает свой. Во второй фазе жрец рассылает «голосуем за такой-то закон в голосовании номер такой-то», и законодатель голосует, если не нарушает этим своё обещание. Когда за один закон в одном голосовании проголосовал кворум, закон принят.
Проверим на опыте. Два жреца одновременно предлагают налог на оливки и налог на коз, пять законодателей, каждый пятый гонец теряется, гонцы идут от 10 до 100 мс. Не дождавшись принятия, жрец начинает новое голосование с бо́льшим номером. Сравним протокол Паксоса с простым правилом «голосуй за предложение с самым большим номером, какое услышал» — без первой фазы. Сценарий прогоняем две тысячи раз с разными случайными задержками и потерями. Очередь событий — куча из главы 18.
Без обещаний парламент почти в каждом прогоне принимает оба закона: сначала большинство голосует за оливки, потом жрец коз, не дождавшись ответа, начинает голосование с бо́льшим номером, и большинство переголосовывает. Две книги острова запишут разное, и ошибку уже не исправить. С обещаниями — ни одного такого случая из двух тысяч: второй жрец, собрав обещания, узнаёт о голосах за оливки и сам предлагает оливки. Ноль стоит и в столбце «ни одного»: при каждом пятом потерянном гонце и двух соперничающих жрецах закон всё-таки принимался за пять секунд. Гарантии этого нет — FLP запрещает, — и в неудачном раскладе два жреца могут бесконечно перебивать друг друга номерами. Поэтому на практике жреца выбирают одного.
Председатель
Одним законом остров не обойдётся. Нужна их череда — седьмой, восьмой, сотый, — и в каждой книге в том же порядке. Можно проводить синод для каждого места в книге, но в спокойное время разумнее выбрать одного жреца надолго — председателя. Пока он жив, он один предлагает законы, соперников у него нет, и первую фазу можно не повторять. Если он ушёл на рынок, выбирают нового. Так устроен «многократный Паксос», и так же — алгоритм, которым сегодня пользуются чаще.
Цель обоих алгоритмов — общая книга законов, которую в Raft называют журналом. Если все законодатели выполняют одни и те же законы в одном порядке, начиная с одинаковых книг, их книги совпадут: это идея Лэмпорта из статьи 1978 года, репликация конечного автомата. Достаточно договориться о журнале — остальное сделает детерминизм.
В Raft законодатель всегда в одной из трёх ролей: рядовой, кандидат или председатель. Время делится на сроки с номерами, и в каждом сроке не больше одного председателя. Председатель регулярно рассылает гонцов — с новыми законами или просто «я здесь». Рядовой, который долго не слышит председателя, объявляет новый срок, голосует за себя и просит голоса у остальных: так устроены выборы председателя. Каждый голосует в каждом сроке один раз, и только за кандидата, чья книга не отстаёт от его собственной. Кто собрал большинство, тот председатель. А чтобы двое не выдвигались одновременно и не делили голоса без конца, тайм-аут у каждого свой, случайный: в статье для примера — от 150 до 300 мс. Обычно кто-то просыпается первым и успевает собрать голоса, пока остальные ещё ждут.
Новый закон председатель сначала дописывает в свою книгу, потом рассылает остальным. Когда закон записан у большинства, председатель объявляет его принятым, и теперь его не сотрёт никакой следующий председатель: за следующего должно проголосовать большинство, большинства пересекаются, а за кандидата с отстающей книгой не голосуют. Рядовые, чьи книги разошлись с книгой председателя, — например, вернувшиеся с рынка с законами, которые так никто и не принял, — переписывают расхождение по книге председателя. Попробуйте.
Если председатель оказался в меньшей части острова, он продолжает рассылать законы, но кворума ему не собрать, и ни один его закон не будет принят: в книгах они висят незакрашенными. Тем временем большая часть выбирает нового председателя с бо́льшим сроком и принимает законы без него. Когда шторм стихает, старый председатель слышит о новом сроке, становится рядовым, а его непринятые законы стираются. Ничего принятого при этом не теряется.
Есть в Raft одна тонкость, которую авторы разбирают на отдельном рисунке. Закон из старого срока может лежать у большинства и всё же не быть принятым. Пусть председатель срока 2 успел записать закон только у себя и у одного соседа и ушёл на рынок. В сроке 3 председателем стал законодатель, до которого этот закон не дошёл; он записал на то же место в книге свой закон, тоже только у себя, и тоже ушёл. В сроке 4 вернулся первый, снова стал председателем и дописал закон срока 2 третьему законодателю: теперь закон лежит у большинства. Если председатель объявит его принятым и сразу уйдёт, выборы может выиграть хозяин закона срока 3: его книга считается новее — последний закон в ней из срока 3, а не 2, — и трое законодателей за него проголосуют. Новый председатель перепишет это место во всех книгах, и «принятый» закон исчезнет. Поэтому правило строже: подсчётом копий председатель принимает только законы своего срока, а старые становятся принятыми заодно, когда принят следующий за ними закон текущего срока. Это правило — задача «Кворум председателя».
Всё это можно запрограммировать на потоках и очередях из главы 39, где каждый законодатель — поток, а гонцы — сообщения в его очереди. Последняя задача главы, «Выборы старейшины», — более старый и простой способ выбрать председателя, алгоритм «задиры»: председателем становится старший из живых, а младшие уступают ему, как только услышат.
Шторм
Председатель в меньшей части острова в виджете выше вёл себя скромно: законы записывал и рассылал, но принятыми не объявлял, а на вопрос «какой сейчас закон о козах?» добросовестный законодатель из меньшей части должен был бы ответить «не знаю, связи нет». Это выбор, и у него есть цена: часть острова на время шторма перестаёт работать. Можно выбрать иначе — пусть каждая часть принимает законы сама, а после шторма разберёмся. Тогда работать будут обе, но книги разойдутся. Третьего не дано, и винить в этом Паксос или Raft бесполезно: так гласит теорема.
В 2000 году Эрик Брюер из Беркли на симпозиуме по принципам распределённых вычислений (PODC) представил гипотезу: распределённая система не может одновременно обеспечить согласованность (каждое чтение видит последнюю запись), доступность (каждый исправный узел отвечает) и устойчивость к разделению сети. В 2002 году Сет Гилберт и Нэнси Линч из MIT доказали её, и она стала теоремой CAP — по первым буквам английских слов consistency, availability, partition tolerance. Её часто пересказывают как «выберите два из трёх», и сам Брюер в 2012 году объяснял, почему это сбивает с толку. Разделение сети не выбирают, оно случается само. Выбор возникает именно в этот момент — отказаться отвечать или отвечать, рискуя разойтись. Пока сеть цела, можно иметь и то, и другое.
Многие системы в шторм выбирают доступность. Пусть копии расходятся — зато каждая половина острова продолжает работать, а когда связь вернётся, копии сведут. Такую гарантию называют согласованностью в конечном счёте: если изменения прекратятся, все копии со временем станут одинаковыми, а до того могут отвечать по-разному. Вы уже пользовались такой системой: это DNS из прошлой главы. Сменили адрес сайта — и ещё десять минут, пока не истёк срок жизни записей в кэшах, часть мира ходит по старому. Никто не ждёт, пока весь мир согласится, и никто от этого не страдает.
Хрестоматийный пример — корзина интернет-магазина из статьи Amazon о хранилище Dynamo 2007 года. Там прямо сказано, что покупатель должен иметь возможность смотреть корзину и класть в неё товары, даже если отказывают диски, сбоят сетевые маршруты, а дата-центры разрушает торнадо. Корзина хранится в нескольких копиях, и в шторм каждая принимает изменения. Как свести их потом?
«Побеждает последняя запись» потеряла вино: покупатель положил его в корзину, а оно исчезло. Объединение множеств ничего не теряет, но воскрешает удалённый сыр. Корзина на Dynamo сводит копии объединением, и в статье об этом сказано прямо: добавление в корзину никогда не теряется, но удалённые товары могут вернуться. Для корзины это разумно: лишний сыр покупатель уберёт сам, а пропавшее вино — потерянная покупка. Для банковского счёта не годится ни то, ни другое — там выбирают согласованность и кворум, как в Raft, и готовы на время шторма отказаться отвечать.
Миллиарды компьютеров работают вместе без главного, потому что каждый слой сети устроен так, чтобы ни от кого не зависеть целиком. Пакеты из главы 41 идут через маршрутизаторы, каждый из которых знает только, куда отправить пакет дальше, а таблицы маршрутов они строят, переговариваясь с соседями; сеть Пола Бэрана задумывалась так, чтобы пережить потерю многих узлов. Поверх ненадёжной доставки TCP из главы 42 договаривается двумя концами: номера, расписки и будильник делают надёжный поток, не спрашивая разрешения у сети, а управление перегрузкой — это миллионы отправителей, каждый из которых сам сбавляет скорость, заметив потери. DNS из главы 43 — дерево, в котором каждое поддерево отдано своему хозяину, а скорость держится на кэшах со сроками жизни. А там, где машинам действительно нужно одно мнение — в журнале банка, в базе GitHub, в хранилище Kubernetes, — его дают алгоритмы консенсуса этой главы: решает не главный, а большинство, и любые два большинства пересекаются, поэтому два противоречащих решения не пройдут. Отказ любой машины здесь — обычное событие: тайм-аут, новые выборы, новый срок. Цена такой независимости тоже известна: нельзя отличить мёртвого от медленного, нельзя одновременно отвечать всегда и всегда одинаково, когда сеть разрезана, и поэтому каждая система выбирает, какой ошибкой ей платить.
Задачи
Три задачи — три уровня острова: часы, кворум и выборы. Последняя решается на потоках и очередях, и тесты гоняют её по нескольку раз со случайными задержками гонцов: решение, которое работает «обычно», их не пройдёт.
Журналы законодателей собраны в словарь: имя законодателя → список его событий по порядку. Событие — кортеж: ("local",) — что-то своё, ("send", m) — отправил гонца с номером m, ("recv", m) — получил гонца m. Номер гонца — любое неизменяемое значение, у каждого гонца свой. Напишите lamport(trace): словарь с теми же именами и списками отметок часов Лэмпорта для каждого события. Часы у всех начинаются с нуля; перед каждым событием прибавляется единица, а получение ставит часы в максимум из своих и отметки отправки, плюс один. Гонец может быть отправлен и не получен — он потерялся. Если журналы невозможны — гонца получили, но никто не отправлял; получили дважды; два гонца с одним номером; законодатели ждут друг друга по кругу, — бросьте ValueError.
Для совета из ячейки часы.py — {"Алкей": [("local",), ("send", "m1"), ("recv", "m4"), ("local",)], "Биант": [("recv", "m1"), ("send", "m2"), ("recv", "m3"), ("send", "m4")], "Главк": [("recv", "m2"), ("send", "m3"), ("local",)]} — ответ {"Алкей": [1, 2, 9, 10], "Биант": [3, 4, 7, 8], "Главк": [5, 6, 7]}.
Заготовка обходит журналы по очереди и падает с KeyError, как только получатель записан в словаре раньше отправителя: гонец ещё «не отправлен». Двигать законодателя можно, пока его следующее событие не «получил гонца, которого ещё никто не отправил». На таком событии он останавливается и ждёт.
Заведите для каждого законодателя указатель на следующее событие, список тех, кого можно двигать, и словарь «номер гонца → кто его ждёт». Отправив гонца, верните ждущего его законодателя в список готовых. Каждое событие так обработается ровно один раз — линейное время.
Когда двигать больше некого, а у кого-то журнал не дочитан, — это круг ожидания, ValueError. Несуществующих и дважды отправленных гонцов удобно поймать заранее, одним проходом по всем отправкам.
Это топологическая сортировка из главы 19: события — вершины, а рёбра идут от каждого события к следующему у того же законодателя и от отправки к получению. Получается граф отношения «случилось раньше», и отметки Лэмпорта можно вычислять в любом порядке, согласованном с ним. Круг ожидания — цикл в графе: такого журнала не бывает, потому что получить можно только уже отправленное.
Председатель Raft знает, сколько законов его книги уже записано у каждого законодателя. Напишите commit_index(match, log, term, commit). match — список: для каждого законодателя, включая председателя, номер последнего закона, который у него точно есть (законы нумеруются с 1, ноль — нет ни одного). log — книга председателя: log[k - 1] — номер срока, в котором записан закон номер k. term — текущий срок председателя, commit — номер последнего уже принятого закона. Верните новый номер последнего принятого закона: наибольшее k, которое есть у строгого большинства законодателей и записано в текущем сроке. Если такого k больше commit нет, верните commit: принятое не отменяется.
Например, commit_index([7, 7, 5, 3, 7], [1, 1, 2, 2, 3, 3, 3], 3, 3) — 7: седьмой закон есть у троих из пяти, и он из срока 3.
В заготовке две ошибки, и одна — в условии большинства. Из четырёх законодателей большинство — трое, а 4 // 2 — два. Строгое большинство — больше половины: have * 2 > n.
Вторая ошибка — тонкость из раздела о председателе: закон из старого срока, даже лежащий у большинства, подсчётом принимать нельзя. Проверяйте log[k - 1] == term. Если подходящий закон текущего срока нашёлся, всё перед ним принимается заодно — достаточно вернуть его номер.
Проверять каждое k подсчётом по всем законодателям — $O(n \cdot L)$: при двух тысячах законодателей и двухстах тысячах законов это сотни миллионов шагов. Отсортируйте match по убыванию: элемент с индексом n // 2 — самый большой номер, который есть у большинства. Дальше достаточно идти вниз от него до первого закона текущего срока.
После сортировки по убыванию у законодателей с индексами от 0 до n // 2 — их n // 2 + 1, то есть большинство, — номер не меньше best, а номер больше best есть уже не у большинства. Это медиана, и найти её можно даже за линейное в среднем время — быстрым выбором из главы 21. Проверка срока — то, ради чего задача и написана: без неё алгоритм правилен почти всегда, и именно поэтому такая ошибка годами живёт в программах, пока не совпадут три отказа подряд.
На острове старейшиной становится старший из присутствующих — у кого больше номер. Кто присутствует, никто заранее не знает. Напишите elect(me, ids, inbox, send, timeout) — её запустят в отдельном потоке у каждого присутствующего законодателя одновременно. me — свой номер, ids — номера всех законодателей острова, и ушедших на рынок тоже. inbox — очередь queue.Queue с гонцами к вам; каждый гонец — кортеж (вид, от_кого). send(to, kind) отправляет законодателю to гонца (kind, me); вид — "ELECTION", "OK" или "LEADER". Гонец идёт от 1 до 30 миллисекунд, а гонцы к ушедшим пропадают. timeout — сколько секунд разумно ждать ответа (в тестах 0,15). Функция должна вернуть номер старейшины, и все присутствующие должны вернуть одно и то же — старший номер среди присутствующих.
Это алгоритм «задиры» (bully), его описал Гектор Гарсиа-Молина в 1982 году. Отправьте "ELECTION" всем, кто старше вас. Если за timeout никто не ответил "OK" — старших нет, старейшина вы: разошлите всем "LEADER" и верните свой номер.
Пока ждёте, отвечайте другим: на "ELECTION" от младшего — "OK", иначе младший решит, что старше него никого нет. Получили "LEADER" — верните номер отправителя. Ждать с ограничением удобно так: inbox.get(timeout=осталось) бросает queue.Empty, если за это время ничего не пришло.
Если старший ответил "OK", ждите его "LEADER" — дольше, например 4 * timeout, — и продолжайте отвечать младшим. Не дождались — старший успел уйти на рынок, начните выборы заново.
Всё держится на тайм-ауте, а значит, на допущении, что гонцы ходят быстрее timeout: «задира» правилен в синхронной системе, где задержки ограничены. Если гонец к живому старшему задержится дольше, младший объявит себя старейшиной — и на острове их станет двое. Raft защищается от этого номерами сроков и кворумом: председатель без большинства ничего не может принять. Зато «задира» прост и быстр, и в маленьких системах с надёжной локальной сетью его используют до сих пор.
Куда дальше
Парламент Паксоса добился своего: книги законов на всех концах острова совпадают, отказы и штормы этого не ломают. Теперь откройте одну такую книгу. В ней сто тысяч записей подряд, а жители приходят к ней с вопросами.
Каждый вопрос — новый цикл по всей книге, написанный заново. Третий вопрос — третий цикл, а когда книга вырастет до сотни миллионов записей и вопросов станет сто в секунду, перебирать всю книгу на каждый вопрос станет некогда. Узлы хранят данные. Как хранить и спрашивать миллионы записей так, чтобы вопрос можно было просто задать — «сколько законов о козах после 300 года», — а как его искать, решала бы машина? Этим полвека занимаются базы данных, и следующая глава устроена как архив, куда к вам, новому архивариусу, приходят посетители с вопросами.