Комментарии
20
Интересно, но жаль нет хотя бы ссылок на практические реализации
http://zookeeper.apache.org, наверное, самый известный проект. Это не совсем paxos, но близкий алгоритм.
Тоже читал статью и размышлял о zk.
В алгоритме не описаны права выбора лидера, если предыдущий пал.
В алгоритме не описаны права выбора лидера, если предыдущий пал.
Вы правы, в статье я рассмотрел только самый позитивный сценарий, основной идеей статьи было, скажем так, интро в проблему консенсуса в распределенных системах. Конечно, каждый из алгоритмов заслуживает отдельной подробной статьи и даже не одной.
Есть формальные спецификации Paxos (+ разновидности) и Raft на TLA+: https://github.com/tlaplus/DrTLAPlus
А если интересна практическая реализация близкого Raft, то можно обратить внимание на etcd которая используется в kubernetes
Вы имеете в виду ссылки на репозитории с кодом практических имплементаций алгоритма или про использование большими компаниями?
Если второе, то я натыкался на несколько статей, например, блог MySQL High Availability и блог Apache Cassandra, правда там совсем старая статья, не знаю, что используется сейчас.
Если второе, то я натыкался на несколько статей, например, блог MySQL High Availability и блог Apache Cassandra, правда там совсем старая статья, не знаю, что используется сейчас.
Было бы круто в такие статьи для наглядности анимации вкладывать. Ролик в конце с примерами такого голосования, например
Есть протокол Raft с восхитительным сайтом и визуализациями. А ещё у них там есть ссылка на интерактивное введение в протокол и консенсус.
а расскажите про PoS в картинках?
Я пока еще не изучал PoS и не готов к обсуждению этого вопроса, но я учту ваши пожелания :)
Статья очень интересная, спасибо!
По этой теме есть еще супер-интересная книга Designing Data-Intensive Applications, Martin Kleppmann, советую :)
Автору еще раз спасибо.
Да, Мартин Клеппман у нас почти настольная книга. Спасибо за упоминание :)
Спасибо большое за статью! Для тех, кто хочет погрузиться в «математику» распределенных систем, можно еще порекомендовать классическую книгу Gerard Tel «Introduction to Distributed Algorithms».
Спасибо за рекомендацию!
Задача с генералами ломает мой мозг. Уже на 3-4 итерациях оба генерала знают время, и знают, что время известно им обоим. Но напасть не могут, так как не могут быть уверены, что второй генерал тоже нападет.
В этом и состоит красота данной задачи. У нее еще есть любопытные вариации:
1) Например, гонцы ходят двумя дорогами, южная и северная. Причем генерал А1 — посылает гонца всегда южной дорогой, а А2 — всегда северной. Оппонент выставляет стражу на одну из дорог и случайно может перехватить, а может и не перехватить одного гонца.
2) Те же условия, что и в (1), но оппонент кидает монетку в самом начале, выбирает направление и всегда пытается поймать только на этом направлении.
3) Те же условия, что и в (2), но оппонент гарантированно ловит гонца на выбранном направлении.
В каких из этих кейсов генералы могут договориться, а в каких нет?
1) Например, гонцы ходят двумя дорогами, южная и северная. Причем генерал А1 — посылает гонца всегда южной дорогой, а А2 — всегда северной. Оппонент выставляет стражу на одну из дорог и случайно может перехватить, а может и не перехватить одного гонца.
2) Те же условия, что и в (1), но оппонент кидает монетку в самом начале, выбирает направление и всегда пытается поймать только на этом направлении.
3) Те же условия, что и в (2), но оппонент гарантированно ловит гонца на выбранном направлении.
В каких из этих кейсов генералы могут договориться, а в каких нет?
Как я понял, нужно, что бы была гарантия 1 удачной доставки сообщения.
В 1 случаи, все так же не известно, доставлено сообщение или нет, потому задача сводится к классической.
В 2 случаи мы все так же не можем быть уверены, нам повезло или путь гарантировано безопасен.
В 3 случаи если генералы знают правила, то достаточно каждому выслать по гонцу с временем, и если пришел гонец то атаковать в то время которое принес гонец, а если нет, то в то время, которое генерал выслал.
В 1 случаи, все так же не известно, доставлено сообщение или нет, потому задача сводится к классической.
В 2 случаи мы все так же не можем быть уверены, нам повезло или путь гарантировано безопасен.
В 3 случаи если генералы знают правила, то достаточно каждому выслать по гонцу с временем, и если пришел гонец то атаковать в то время которое принес гонец, а если нет, то в то время, которое генерал выслал.
Да, все так. Суть именно в гарантированном канале связи.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.
Кот Шрёдингера без коробки: проблема консенсуса в распределённых системах