Loser story

Loser story

Наконец-то получил загран! Кстати разбираю сейчас EPaxos, статью и алгоритм в целом, думаю напишу подробнее об этом, было бы круто если кто нибудь тоже прочитает и готов обсудить (в комментах)

В итоге Epaxos оказался сложной и интересной темой, и я решил написать несколько постов о leaderless replicated state machine.
А потом оказалось что у меня куча дел и в итоге вы читаете первый пост только сейчас.

Наверно многие из вас в какой-то степени знают Raft/Paxos/MultiPaxos.
Исторически сложилось так, что Raft стал самым популярным алгоритмом для RSM.
Какие оптимизации (относительно запуска single decree Paxos в каждой ячейке реплицируемого лога, что очевидно проще) используются в нем?
1) То что у нас есть лидер, причем строгий, то есть никогда не может существовать несколько лидеров одновременно (это ключевое отличие от MultiPaxos, где тоже обычно есть лидер, но не строгий, выбираемый по иным правилам. А ещё это переносит livelock в Raft с фаз Prepare/Accept на выбор лидера, по сути остался только выбор лидера и Accept). Главное, эта оптимизация позволяет лидеру практически не сталкиваться с конкуренцией.
2) То что после фазы Prepare/выбора лидера мы отправляем Accept-ы батчами, это позволяет нам делать 1 rtt вместо 2 (без учёта клиента, которого редиректят на лидера, и собственно самого выбора лидера/первого Prepare для MultiPaxos)

К сожалению эти оптимизации не лишены недостатков:
1) Страдает доступность, ведь в случае каких-то проблем с лидером: падает, тормозит, сеть медленная, етс. У нас возникают проблемы в целом, от долгих перевыборов до чего то посложнее (пример решения части из них https://decentralizedthoughts.github.io/2020-12-12-raft-liveness-full-omission)
2) В случае WAN происходит 2 WAN коммуникации (клиент лидер, лидер фоловеры)
3) В целом так или иначе, но лидер это бутылочное горлышко

Поэтому мне кажется мысль, которая возникает у многих, особенно в случае WAN, а нельзя ли как-то оставить алгоритм leaderless, и при этом получить хороший throughput и низкую latency.

Собственно о статьях про такие алгоритмы я и хочу рассказать.

#leaderless_0

decentralizedthoughts.github.io

Raft does not Guarantee Liveness in the face of Network Faults

Last month, Cloudflare published a postmortem of a recent 6-hour outage caused by a partial switch failure which left etcd unavailable as it was unable to establish a stable leader. This outage has understandably led to discussion online about exactly what…

www.tgoop.com/reverse13/682

1.15K viewsedited  May 10, 2022 at 22:32

В итоге Epaxos оказался сложной и интересной темой, и я решил написать несколько постов о leaderless replicated state machine.
А потом оказалось что у меня куча дел и в итоге вы читаете первый пост только сейчас.

Наверно многие из вас в какой-то степени знают Raft/Paxos/MultiPaxos.
Исторически сложилось так, что Raft стал самым популярным алгоритмом для RSM.
Какие оптимизации (относительно запуска single decree Paxos в каждой ячейке реплицируемого лога, что очевидно проще) используются в нем?
1) То что у нас есть лидер, причем строгий, то есть никогда не может существовать несколько лидеров одновременно (это ключевое отличие от MultiPaxos, где тоже обычно есть лидер, но не строгий, выбираемый по иным правилам. А ещё это переносит livelock в Raft с фаз Prepare/Accept на выбор лидера, по сути остался только выбор лидера и Accept). Главное, эта оптимизация позволяет лидеру практически не сталкиваться с конкуренцией.
2) То что после фазы Prepare/выбора лидера мы отправляем Accept-ы батчами, это позволяет нам делать 1 rtt вместо 2 (без учёта клиента, которого редиректят на лидера, и собственно самого выбора лидера/первого Prepare для MultiPaxos)

К сожалению эти оптимизации не лишены недостатков:
1) Страдает доступность, ведь в случае каких-то проблем с лидером: падает, тормозит, сеть медленная, етс. У нас возникают проблемы в целом, от долгих перевыборов до чего то посложнее (пример решения части из них https://decentralizedthoughts.github.io/2020-12-12-raft-liveness-full-omission)
2) В случае WAN происходит 2 WAN коммуникации (клиент лидер, лидер фоловеры)
3) В целом так или иначе, но лидер это бутылочное горлышко

Поэтому мне кажется мысль, которая возникает у многих, особенно в случае WAN, а нельзя ли как-то оставить алгоритм leaderless, и при этом получить хороший throughput и низкую latency.

Собственно о статьях про такие алгоритмы я и хочу рассказать.

#leaderless_0

BY Loser story