这篇是2020年12月22日写的。

6.824 Lab2B

做的過程中遇到了很多坑，我覺得把這些坑記錄下來比較有幫助。雖然現在這個實驗幾乎快做完了，很多遇到的坑也快忘記了，先開一個坑，以後慢慢補充吧。我覺得這個實驗做一遍是不夠的，以後再做第二遍。

Follower 超時之後，如果它立刻自增 Term 並且發起選舉，並且它的 Log 不如 majority 新，此時它一定會競選失敗，其實它浪費了其它 Server 的時間。假設有一個唯一有資格成爲 Leader 的 Server B 一直收到 Server A 的 RequestVote 請求，並且 Server A 的 Term 比較新，此時 B 需要重置自己的超時時間，這樣 B 的超時一直被 A 打斷。或者如果 B 超時了之後，在 A 接到 B 的 RequestVote 請求之前，A 也超時了，此時 A 會投票給自己，B 還是得不到 A 的選票。這兩種情況如果反覆發生，可能會導致 A 永遠也無法成爲 Leader，這個 cluster 可能在很長的時間內都選不出 Leader。

所以 Server 在超時之後，成爲 Candidate 之前，需要進行預選舉，確保自己的 Log 比 majority 都新。這樣就減少了其它 Server 超時被打斷的次數，讓有機會成爲 Leader 的 Server 更容易被選舉出來。

其實這中間有個問題需要考慮。爲什麼 Receiver 接收到 Term 更新的 RequestVote 的時候，需要重置超時時間呢？首先，更新 Receiver 的 Term 肯定是必須的。假設我們只更新了 Receiver 的 Term，但是沒有重置超時時間，會發生什麼呢？

如何實現 PreVote

  1. 給 Server 添加一個 preCandidate 的狀態
  2. 在 Follower 超時之後，Term 先不自增，發起預選舉
  3. 復用 RequestVote 請求，添加預選舉標記
  4. 如果請求是預選舉，需不需要更新 Receiver 的 Term 呢？不需要。目的是爲了儘量不打擾其它 Server
  5. 在 RequestVote handler 的開頭判斷如果是預選舉，則比較日誌，結束 handler。不需要做 Term 的對比和更新。因爲 RequestVote 的目的只是爲了比較日誌，儘量做到不改變其它 Server 的狀態。
  6. 如果 preCandidate 的 Log 比 receiver 新，返回真
  7. 接收到預選舉的返回之後，需要判斷 Term 是否變更。如果發生了變更，說明 Server Term 已經更新了，此時一定有其它 Server 成爲了了 Candidate 或者 Leader。這也就意味着有其它 Server 至少有資格成爲 Leader，所以當前 Server 直接結束預選舉，退位成 Follower 即可。實現上比較簡單，讓預選舉結束即可，它沒有得到足夠的票，自然會退位成 Follower。
  8. 如果 preCandidate 獲得了 majority 選票，並且它的 Term 沒有改變，轉換成 Candidate，發起真正的選舉。
  9. 如果 pre-vote 失敗了，那麼轉換成 Follower
  10. 如果 pre-vote 超時了，那麼重新開始 pre-vote 過程

按照這個思路還是比較清晰的，花了很少的時間實現了之後，跑了之前 Fail 的 Backup2B 之後，很意外地通過了 100 次測試。我還以爲需要仔細調試一番。目前測試還在跑，3k+ 次還沒掛。非常有成就感。

預選舉看來還是很有必要的，它節約了大部分 Server 的時間，提高了選舉效率，讓能夠成爲 Leader 的 Follower 更有可能更快地被選舉成 Leader。這樣其實也能夠比較有效地降低那種長時間內（之前 Fail 的 Backup2B 是 10s）選不出 Leader 的概率。並且之前 Backup2B 平均每次跑 10s，現在平均下降到了 8s。

注意到有趣的一點，筆記本盒蓋睡眠的時候，測試有比較大的概率會掛掉，可能之前 Fail 也有這個原因，還是應該把電腦一直保持在喚醒狀態跑實驗。

Too may RPC count

昨天加上預選舉的功能之後，實驗可以成功地連續跑了 6.5k 次。不過之前改過測試文件，把 RPCCount 那個 case 中的限制放寬了 10 次。打開之後，果然很快就掛了。看日誌是多調用了幾次 RPC，嘗試了很多次，每次都是多調用了小於 10 次的 RPC。

原來在 Log 被 Leader 成功提交之後，Leader 會立即廣播心跳，推進 Follower 的 CommitIndex。也許這個過程不需要？只需要等到下一次心跳的時候再順便告知其它 Follower 即可。嘗試之後發現並不能這麼做，很快就 failedto reach agreement 了。

接下來想的方法是，當 Leader 提交 Log 之後，檢查 Leader 給 Follower 的 AppendEntry 請求的返回，如果成功，則不需要再發送心跳推進這個 Follower，如果失敗，則立即發送心跳給 Follower。試過之後還是不行，依然會 failed to reach agreement。原因可能是成功的那些 Follower 沒有及時更新自己的 CommitIndex，可能在下次心跳之前測試就已經失敗了。

或許是心跳時間設置得太短了？加長心跳時間，並沒有解決問題。

只能一行一行看日誌了，分析了一波日誌之後，發現確實有的時候在相隔十幾毫秒給某個 Follower 連續發送心跳。這種情況就是 Leader 提交日誌之後，立即發送心跳推進 Follower 的進度。在很短的時間內，Leader 的心跳時間到，此時 Leader 再廣播心跳。所以對同一個 Follower 的兩次心跳間隔只有十幾毫秒。

這個問題貌似也比較好解決。Leader 需要記錄上次給每個 Follower 發送心跳的時間，當 Leader 給任何一個 Follower 發送心跳的時候，先檢查當前時間和上次發送心跳的時間的時間差，如果小於心跳時間，則不發送這次心跳。實現也比較容易，在節點中保持一個時間戳數組，當 Server 晉升成 Leader 之後，清空這個數組。當 Leader 給 Follower 發送心跳之前，先檢查時間差，再更新對應位置的時間戳。

實現完之後跑了幾次測試目前還沒掛，看來還是有點兒穩的。除去 RPCcount 這個 case，其它 Case 已經連續跑了 1w 次左右（在放寬 10 次的限制的情況下），看來這次有希望了哈哈。