leader election again
Sep. 7th, 2013 02:42 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109вот статья, описывающая некий алгоритм под названием Raft. в начале статьи хорошо описаны проблемы с paxos. saves me some time, если я вдруг доберусь свою white paper написать. ну и я согласен с общим подходом ставить понятность во главу угла.
но, блядь, не получилось же опять. вот уже на странице №5 видно. не справились с поставленной задачей иметь только одного лидера в системе.
прокол №1: сразу после получения кандидатом большинства голосов возникает split brain, с новоизбранным лидером в меньшей половине. большая половина не получает извещения о новоизбранном лидере, и избирает своего. хоба-на, два лидера.
прокол №2, related to #1, но более generic. безо всяких выборов, не описано никакого механизма отдетектировать split brain. лидер, оказавшийся в меньшей половине, будет продолжать считать себя лидером.
и тут авторы делают хитрый трюк. да, говорят они, действительно, получается, что может быть больше одного лидера. но только один из них сможет закоммитить лог!
ну то есть, задача на самом деле не решается, а перекладывается на другое место. теперь, когда появилось новое действующее лицо - лог, который при нормальном решении проблемы на собственно выборы влиять никак не должен, авторам приходится заботиться о том, чтобы лидером мог стать только сервер, у которого самый длинный лог. к сожалению, коллективно решить, у кого самый длинный лог (который ещё и может расти прямо в процессе решения) - это задача, для решения которой нужен concensus algorithm, для которого нужен работающий leader election. круг замкнулся.
да, я вижу картинку 7, она не помогает на фига. представим себе следующее. три сервера S1..S3, S1 - лидер. update 1 закоммичен S1 и S2, update 2 закоммичен S1 и S3. теперь лидер падает. имеем S2 с первым апдейтом и S3 со вторым. никакого механизма merge алгоритмом не предусмотрено. или S3 не сможет закоммитить второй апдейт без первого? тогда, во-первых, liveness cтрадает, и во-вторых, где это написано?
но, блядь, не получилось же опять. вот уже на странице №5 видно. не справились с поставленной задачей иметь только одного лидера в системе.
прокол №1: сразу после получения кандидатом большинства голосов возникает split brain, с новоизбранным лидером в меньшей половине. большая половина не получает извещения о новоизбранном лидере, и избирает своего. хоба-на, два лидера.
прокол №2, related to #1, но более generic. безо всяких выборов, не описано никакого механизма отдетектировать split brain. лидер, оказавшийся в меньшей половине, будет продолжать считать себя лидером.
и тут авторы делают хитрый трюк. да, говорят они, действительно, получается, что может быть больше одного лидера. но только один из них сможет закоммитить лог!
ну то есть, задача на самом деле не решается, а перекладывается на другое место. теперь, когда появилось новое действующее лицо - лог, который при нормальном решении проблемы на собственно выборы влиять никак не должен, авторам приходится заботиться о том, чтобы лидером мог стать только сервер, у которого самый длинный лог. к сожалению, коллективно решить, у кого самый длинный лог (который ещё и может расти прямо в процессе решения) - это задача, для решения которой нужен concensus algorithm, для которого нужен работающий leader election. круг замкнулся.
да, я вижу картинку 7, она не помогает на фига. представим себе следующее. три сервера S1..S3, S1 - лидер. update 1 закоммичен S1 и S2, update 2 закоммичен S1 и S3. теперь лидер падает. имеем S2 с первым апдейтом и S3 со вторым. никакого механизма merge алгоритмом не предусмотрено. или S3 не сможет закоммитить второй апдейт без первого? тогда, во-первых, liveness cтрадает, и во-вторых, где это написано?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
костя,
Date: 2013-09-08 08:07 pm (UTC)(no subject)
Date: 2013-09-09 07:38 pm (UTC)