Как Raft гарантирует согласованность бревен?

Я изучаю Raft, и я уже знаю базовый механизм Raft.

Когда лидер избран, он обязан обновить журнал последователей до журнала лидера. При обновлении Последователя он находит первый совпавший <entry, term> в обратном направлении и обновляет Последователя следующими журналами.

Как Raft гарантирует, что журналы Лидера и Последователя до совпадения <entry, term> совпадают? Произойдет ли такой случай:

                |
Leader          v  
Entry   : 1 2 3 4 5 6 7 8 9 10
Term    : 1 1 1 2 2 3 3 3 3 3 

Follower
Entry   : 1 2 3 4 5 6 7
Term    : 1 1 1 1 2 3 3

distributed-computing algorithm distributed-system raft
person Dillion Wang    schedule 21.01.2020    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Это свойство алгоритма Raft называется Log Matching.

Если два журнала содержат запись с одинаковым индексом и термином, то журналы идентичны во всех записях до данного индекса.

Это справедливо, потому что:

При отправке RPC AppendEntries лидер включает индекс и термин записи в свой журнал, который непосредственно предшествует новым записям. Если подписчик не находит в своем журнале записи с тем же индексом и термином, он отклоняет новые записи. Проверка согласованности действует как шаг индукции: начальное пустое состояние журналов удовлетворяет свойству сопоставления журналов, а проверка согласованности сохраняет свойство сопоставления журналов всякий раз, когда журналы расширяются. В результате, всякий раз, когда AppendEntries возвращается успешно, лидер знает, что журнал последователя идентичен его собственному журналу с учетом новых записей.

Источник https://raft.github.io/raft.pdf

person msantl    schedule 27.01.2020
comment
Теперь я понимаю. До или после каждой операции AppendEntries Raft гарантирует, что каждые два участника в этом протоколе удовлетворяют свойству сопоставления журналов. - person Dillion Wang; 29.01.2020