Наверно многие из вас в какой-то степени знают 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