Путаница с алгоритмом плота

Question

В статье «В поисках понятного алгоритма консенсуса» на рис. 8 показана проблема в (d) и (e), что некоторые старые журналы могут быть перезаписаны и никогда не возвращаться.

В разделе 5.4.2 написано «Чтобы устранить проблемы, подобные той, что на рис. 8, Raft никогда не фиксирует записи журнала из предыдущих терминов путем подсчета реплик. Только записи журнала с текущего срока лидера фиксируются путем подсчета реплик; как только запись из текущего термина была зафиксирована таким образом, то все предыдущие записи фиксируются косвенно из-за свойства соответствия журнала ».

Я запутался в этой части, как она работает на рисунке 8? Что будет, а что нет?

Answer 1

При добавлении правила к рисунку 8.

Плот никогда не фиксирует записи журнала из предыдущих условий путем подсчета реплик.

Так что теперь мы никогда не фиксируем записи журнала из предыдущих условия, давайте посмотрим, что произойдет снова на рисунке 8. Я изменил рисунок 8, чтобы показать ситуацию после применения правила.

(a) и (b) работает одинаково.

Начиная с (c), запись в журнале по индексу 2 добавляется в термин 2 , начиная с шага (а), где я рисую желтый круг. Так что это из предыдущих терминов . Таким образом, лидер не будет повторять эту запись (желтые 2 с моим черным крестом) в соответствии с правилом. Он должен начать репликацию с записи в индексе 3.

Это правило также упоминается на рисунке 2, правило лидера «Правила для серверов» 3.1:

Отправка AppendEntries RP C с началом записи в nextIndex.

NextIndex инициализируется с last log index + 1, поэтому он должен начинаться с лог-индекса 3 с (c), а не с индекса 2.

Так что для Гипотетическая процедура в оригинале (c), , невозможно добавить журнал 2 к большинству до того, как журнал 3 (розовый, добавленный в термине 4) будет воспроизведен при большинстве. и (d) не произойдет.