Comments 23
Отличный алгоритм. Спасибо за разъяснение — вроде все понятно и правильно объяснено. Но тут самая засада, как я понимаю, что хоть и алгоритм отличный, но некоторые импленментации его могут быть некорректными. И какова ценность делать рафт руками, когда можно взять готовую библиотеку или переложить весь этот головняк на базу типа 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. Чтобы сделать что-то более надёжным, нужно где-то лишний раз записать данные на диск/сделать сетевой вызов/иным способом удостовериться что всё хорошо. Когда нужно сделать что-то
распределённое надёжным, приходится идти на ещё большие жертвы в производительности/доступности. Есть не так уж и много ситуаций, в которых совсем уж никак не обойтись без распределённого консенсуса
Спасибо за публикацию, как раз недавно заходил на интерактивную демонстрацию этого алгоритма:
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