Паксос — алгоритм принятия решений в распределённых системах, лежащий в основе многих современных инструментов — Consul, Zookeeper, etcd и других.
Зачастую при работе распределенной системы возникает необходимость принимать общие решения, например, на каком из инстансов запустить задачу, которая должна быть выполнена один раз.
Задача решается просто, когда есть арбитр — главный в принятии решений. Проблема в том, что такой арбитр становится узким местом и при его отказе происходит сбой в работе.
Устойчивая к неполадкам система должна состоять из равноправных участников, способных договариваться между собой — достигать консенсуса.
Алгоритм Паксос (Paxos), придуманный и доказанный Лесли Лампортом, говорит нам о том, как этого консенсуса можно достичь. Критерием достижения является согласие с предложением более половины участников.
Алгоритм состоит из двух этапов:
Подготовительный этап:
- Предлагающий рассылает анонс, что он планирует сделать предложение n (в момент времени n).
- Принимающие получившие анонс посылают в ответ обещание не принимать никаких предложений с номерами меньшими n (до момента n), а также последнее принятое предложение (номер и значение) или не отвечают вовсе, если номер последнего принятого принимающим предложения превосходит n.
Предложение:
- Предлагающий, получив ответы от большинства принимающих, выбирает в качестве значения предложения v значение из ответа с максимальным номером предложения и рассылает предложение (n, v).
- Принимающий, получив предложение (n, v), обязан принять его если он, конечно, не пообещал другому предлагающему не принимать предложений с номерами меньшими n*, где n* > n.
Интересные моменты:
— Консенсуса можно вовсе не достигнуть из-за большого количества предлагающих. Для решения этой проблемы можно ввести случайные задержки.
— Повреждение данных на доле узлов может расколоть вашу систему на несколько частей.
Ссылки:
— https://habr.com/ru/post/346180/
— https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
— https://en.wikipedia.org/wiki/Paxos_(computer_science)
Доклад на ближайшем Highload++ “Паксос в картинках” Консантина Осипова.