Комментарии 24
Отличный алгоритм. Спасибо за разъяснение — вроде все понятно и правильно объяснено. Но тут самая засада, как я понимаю, что хоть и алгоритм отличный, но некоторые импленментации его могут быть некорректными. И какова ценность делать рафт руками, когда можно взять готовую библиотеку или переложить весь этот головняк на базу типа etcd/consul/zookeeper?
Есть же более низкоуровневые реализации рафта, тот же https://github.com/hashicorp/raft Сверху можно напилить любое domain-specific api.
А чем это лучше, чем просто завязаться на базу типа etcd/consul/zookeeper?
Если кейс это некая распределённая система с необходимостью выбора мастера, то получается минус зависимость, потенциально больше управляемости/предсказуемости.
Так то тот же consul использует Raft для своих выборов мастера.
А уж что лучше в конкретном случае — атомарно пытаться записать себя как мастера, полагаясь на выборы внутри стораджа и его консистенси или самому делать выборы поверх Raft — это уже от ситуации решать надо.
Действительно многие имплементации могут отклоняться от оригинального описания. Автор рафт приводит алгоритм Paxos как контрпример — там вообще тёмный лес, чёткого описания как алгоритм может работать на долгой дистанции нет, поэтому большинство имплементаций включают в себя некоторую долю додумок, рафт же designed for understability, поэтому здесь ситуация получше
Меня, знаете, что еще волнует. Рафт, как будто, не дает никаких гарантий относительно того как скоро будет произведена синхронизация всех узлов. Ну, когда-нибудь в будущем, когда будет связность между всеми нодами — ну, ок. А пока — мы валяемся и пытаемся обмениваться пакетами. Т.е. рафт — это не плохо, это прекрасный алгоритм, но скорее всего он хорошо работает только тогда, когда сбои единичны и каналы передачи относительно надежны и есть запас bandwidth.
Остаётся только ждать когда изобретут квантовый телепорт.
Несомненно Вы правы, но здесь больше вопрос о том, что есть разные типы систем.
Которые гарантируют какое-то время отклика или вообще не работают и дают ошибку.
А есть системы, которые вроде как гарантируют, что не упадут, но при этом тормоооооооооооозят.
И я тут даже не знаю, что лучше. Наверное, лучше, когда есть четкое понимание его ожидать. Вот поэтому я такие вопросы и задаю.
Это вечный трейдофф consistency vs availability. Чтобы сделать что-то более надёжным, нужно где-то лишний раз записать данные на диск/сделать сетевой вызов/иным способом удостовериться что всё хорошо. Когда нужно сделать что-то
распределённое надёжным, приходится идти на ещё большие жертвы в производительности/доступности. Есть не так уж и много ситуаций, в которых совсем уж никак не обойтись без распределённого консенсуса
У Raft логика, что большинство нод будут работоспособны (так как выберут нового лидера, если что). А отвалившееся меньшинство уйдёт в read-only (не смогут выбрать лидера, но если очень нужно, могут продолжать работать со старым состоянием). Когда связь восстановится, они догрузят с большинства все изменения, которые произошли за их отсутствие (своих изменений у них нет, так что конфликтов не будет), а потом продолжат нормальную работу.
Если допустить, что наиболее часто потеря связи с большинством нод означает потеряю связи с внешним миром вообще (например, сбой сетевого подключения), то проблем никаких нет. Нода физически не может отвечать на запросы и пофиг в каком она состоянии, а когда сможет отвечать на запросы, тогда же она и сможет подтянуть новые данные и отвечать актуально.
Вопрос "когда это случится" здесь не может быть задан к алгоритму, так как всё упирается в ситуацию вызвавшую сбой связи. Может сервер вообще физически сгорел и тогда ответом будет "никогда".
Если связь с большинством утеряна, но связь с внешним миром сохранилась, то у нас выбор - либо отвечать во внешний мир старые данные, отвергая запросы на запись, либо перестать отвечать на внешние запросы вообще (выбор зависит от конкретного ТЗ).
Опять же, магии здесь никакой нет. Если физически нет связи с большинством, нам неоткуда взять новые данные. Когда связь восстановится, тогда и получим свежие данные. Зависит от физического мира, а не алгоритмов.
Отдельный особый случай, когда связь с большинством не восстановится никогда (например, сгорел датацентр), обрабатывается админом вручную (ему нужно будет донести до меньшинства, что оно теперь большинство, а их копия данных - самая актуальная). Меньшинство без какого-то внешнего источника информации (причём по иному каналу связи нежели упавший канал связи с большинством) физически неспособно узнать, что большинства больше нет.
То есть Raft даёт вполне разумные гарантии там, где его область ответственности. Ответы на другие вопросы находятся на пределами информационной системы. Условно, чтобы узнать "когда" надо звонить провайдеру Интернета и спрашивать, никакая компьютерная программа не может рассчитать, когда его техники починят оптоволокно перебитое экскаватором.
Можно, конечно, отказаться от перехода в read-only при потере связи с большинством, но тогда это будет вообще другой класс распределённых систем, которые устраивает, что ноды находятся в разном состоянии и что у нас постоянно возникают конфликты синхронизации и их надо решать. Raft не для таких систем, а там где нужно быть уверенным, что конфликтов не будет и всегда есть основная рабочая версия данных (а те у кого основной рабочей версии нет могут быстро понять это и либо перейти в RO, либо перестать обслуживать запросы вообще).
Спасибо за публикацию, как раз недавно заходил на интерактивную демонстрацию этого алгоритма:
http://thesecretlivesofdata.com/raft/
Ссылки этой у вас не увидел, но она заслуживает внимания для изучающих Ruft протокол
Да, эту интерактивную демонстрацию видел, она хороша. На raft.github.io более интерактивная, в которой можно потыркать сервера.
И всё ради того чтобы впарить мусорную еду?
В базовой версии алгоритма кол-во серверов задано вручную, и все они друг про друга знают.
Raft поддерживает динамическое изменение состава кластера — об этом можно подробнее почитать в статье в главе 6. Вкратце — изменение состава происходит в две фазы — в первой фазе старые участники узнают обо всех новых участниках, но новые участники пока не являются полноправными членами кластера. С наступлением второй фазы кластер начинает работать в новой конфигурации
Не очень понятна клиентская и околоклиентская сторона. Судя по описанию, клиенты всегда обращаются к лидеру (дилеру, как предлагает свайп, что, в принципе, тоже подходит :) ). Спрашивается, чем оно обеспечивается — клиенты узнают про нового лидера, или предполагается использование редиректора на лидера? Но и редиректор тоже должен узнавать про изменения, а об этом в статье не сказано.
Если же клиенты будут обращаться к разным серверам, включая бывших лидеров — тут совсем зоопарк может получиться.
Опять же, смущает пример (который хороший пример, но с трагическим началом), где лог фолловера содержит запись, отсутствующую у лидера. Откуда-то она же там появилась? А в результате оказывается затёрта.
В общем, с работой клиентов надо поразбираться.
Предполагается что клиент знает про все сервера в кластере, обращается к произвольному, и в случае если это фолловер, то фолловер сам редиректит клиента на тот сервер, который он считает лидером.
Это не нарушает гарантий алгоритма, поскольку допустим из пяти серверов один считает себя лидером 3го срока, двое фолловерами 3го срока, а ещё два сервера почему-то отстали и считают себя лидером и фолловером 2го срока.
Допустим клиент произвольно пришёл к фолловеру второго срока. Тот отправил его к лидеру второго срока. Лидер пытается добавить запись, но у него не выйдет закоммитить запись, отправив большинству, потому что 3 сервера из 5 будут игнорировать его запросы из-за устаревшего номера срока. Тогда лидер со вторым сроком обновляется до третьего, становится фолловером и отвечает клиенту ошибкой. Клиент ретраит и в следующий раз уже попадает к серверу с 3-им сроком.
С записью, отсутствующей у лидера всё проще. Сервер, содержащий эту запись "3", мог бы быть выбран лидером третьего срока, принять запрос от клиента, записать к себе и не успев отправить AppendEntries вырубиться. Остальные сервера выбрали лидера 4-го срока, у которого нет этой записи, что соответсвует алгоритму, т.к. он ещё не закоммичена. Когда фолловер включится обратно и возникнет ситуация, когда у фолловера есть лишняя запись.
Спасибо, все четко объяснили. Видно, что Raft отлично работает.
Я так понял, что все записи в лог сериализированы с самыми строгими гарантиями. Отсюда получаются достаточно жесткие требования на скорость доступа и записи лога — т.к. если мы пишем его на диск, то ожидаем, что он там сохранится. Если просто держим в ОЗУ, то есть риск, что в какой-то момент при отключении электричества на всем кластере мы отгребем.
Единственное, что вылезло за скоуп самого алгоритма — способ хранения лога. Потому что в теории все круто — если лог одинаковый на двух серверах, то он одинаковый. Но фактически могут быть ошибки чтения с диска, повреждение ОЗУ и прочие неприятные вещи. Интересно, как реализуют защиту от этого.
Raft предполагает, что кроме своего лога, каждый сервер хранит в надёжном хранилище свой текущий срок и голосовал ли в текущем сроке этот сервер. При повреждении этого хранилища, сервер больше не может быть участником кластера, он должен "выйти и зайти нормально". Как именно сервер должен определить, что хранилище было повреждено в описании алгоритма я не нашёл, думаю простенькие хэш-суммы хорошо справятся с этой задачей
"единственная операция, которую лидер может совершать со своим логом – дописывать записи в конец"
Если я не ошибаюсь, это не совсем так. Кроме дозаписывания можно отрезать часть устаревших логов с конца.
MikiRobot Это верно, расширенная версия алгоритма поддерживает Log Compaction, когда мы пачку записей из начала лога группируем в одну и перезаписываем, чтобы не тратилось место. Например были записи X SET 3, Y SET 2, X ADD 2. Мы можем их заменить на Y SET 2 & X SET 5. Такие снэпшоты находятся за рамками статьи, почитать про них можно в статье в главе 7.
P.S. Промахнулся по кнопке "Ответить"
Как сервера договариваются друг с другом: алгоритм распределённого консенсуса Raft