Loser story

Loser story

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

В процессе изучения темы, я столкнулся с тем что leaderless алгоритмы: EPaxos, FPaxos, Atlas, etc довольно сложны, при том что сам по себе Paxos довольно прост.

Так что начну я с обзора одной несложной статьи, автор которой опирается на собственные исследования в рамках CASPaxos (https://arxiv.org/abs/1802.07000)

Идея CASPaxos крайне проста: если state RSM меньше чем команда лога, компактный, то можно реплицировать его вместо лога. И выиграть как с точки зрения упрощения алгоритма, так и с точки зрения перфоменса, то есть в батчинге (можно отправлять/записывать результат не каждой отдельной команды батча, а его финальное состояние)

http://rystsov.info/2020/06/27/pacified-consensus.html:
Собственно идея самого алгоритма который позволит реплицировать leaderless и быстро произвольный RSM (а не только регистр) очень прикольна. Давайте возьмём условный MultiPaxos, и вместо того чтобы выбирать лидера, уменьшим конфликты засчет порядка на запросах клиентов, то есть сделаем батчинг, и определим позицию в логе заранее (сделаем это с помощью CASPaxos, так как реплицируемый стейт это просто набор запросов), а ещё этот CASPaxos можно не fsync-ать, так как даже если что-то разломается, сам наш алгоритм -- примитивный Paxos, и продолжит работать, пусть и медленее.

#leaderless_1

www.tgoop.com/reverse13/683

1.4K viewsedited  May 10, 2022 at 22:37

В процессе изучения темы, я столкнулся с тем что leaderless алгоритмы: EPaxos, FPaxos, Atlas, etc довольно сложны, при том что сам по себе Paxos довольно прост.

Так что начну я с обзора одной несложной статьи, автор которой опирается на собственные исследования в рамках CASPaxos (https://arxiv.org/abs/1802.07000)

Идея CASPaxos крайне проста: если state RSM меньше чем команда лога, компактный, то можно реплицировать его вместо лога. И выиграть как с точки зрения упрощения алгоритма, так и с точки зрения перфоменса, то есть в батчинге (можно отправлять/записывать результат не каждой отдельной команды батча, а его финальное состояние)

http://rystsov.info/2020/06/27/pacified-consensus.html:
Собственно идея самого алгоритма который позволит реплицировать leaderless и быстро произвольный RSM (а не только регистр) очень прикольна. Давайте возьмём условный MultiPaxos, и вместо того чтобы выбирать лидера, уменьшим конфликты засчет порядка на запросах клиентов, то есть сделаем батчинг, и определим позицию в логе заранее (сделаем это с помощью CASPaxos, так как реплицируемый стейт это просто набор запросов), а ещё этот CASPaxos можно не fsync-ать, так как даже если что-то разломается, сам наш алгоритм -- примитивный Paxos, и продолжит работать, пусть и медленее.

#leaderless_1

BY Loser story