動機

下面紀錄做lab遇到的坑

我做完6.824的所有lab時，他們還在上課，所以code不能貼

能得到什麼

  1. 怎麼用lock
  2. 分散式系統怎麼設計
  3. 怎麼設計log要印什麼與用log去debug
  4. 面對絕望的勇氣與滿滿的成就感

這堂課好在哪

  1. 所有材料都在網路上，連同所有測試
  2. 有可以參考的code與心得 (但網路上的code真的就是參考而已，因為有的也沒有實現好或是實現得異常複雜)

lab1

實現一個單機版的mapreduce，這個基本上就是給大家練習golang的

可以不用任何一個lock完成這個lab

重點是知道mapper與reducer到底要做什麼 mapper把資料對到一個reducer(可以當成一個shard)，reducer做接下來的事

lab2

實現一個有基本功能、log compaction、log fast back的raft

細節十分多，十分可怕

下面是一些整體的重點

  1. 先用一個lock就好
    • 之後會引入其他lock，要嚴格遵守拿lock的order
    • 引入lock後method互相call可能會call到有lock的，要自己定義那些method需要lock那些不需要
    • lock與unlock可以用method包裝，之後如果有deadlock會很好trace
  2. 不要提早切太細分成很多struct與method (除了log的操作!!)
    • 之後上lock會把自己搞死，除了deadlock還是deadlock
    • debug的log也會很難看 (會不知道是哪台server做的)
  3. 思考為什麼raft不會錯，不是只有為什麼會對
    • 正確性的來源是?
      • 投票與log的關係是?
      • term的意義是?
    • 為什麼只需要persist那3項資料就好?
      • raft怎麼意識到時間流逝(事件發生)
    • persist的資料與正確性的關係是?
    • fig 2的描述怎麼實現(保持)正確性?
  4. log要把所有狀態與自己是誰print出來
    • 之後debug就是透過自己replay log來完成，沒有gdb，沒有
    • print可以直接用%v
  5. 去看student guide與lab hint

lab2a

這是實現投票的part(RequestVote rpc)，很簡單，也是惡夢的開始!!

因為這個不涉及log，導致隨便寫都能過test，但投票才是確保log會是最新的重要條件!!

lab2b

這是實現log的part(AppendEntries rpc)，情況變得複雜起來，要處理log與apply

這裡就會把前面lab2a沒寫好的部分暴露出來

  1. 要確認所謂的at least up-to-date是什麼意思 (log比較長 或是 一樣長但是last log的term比較大或等於)
  2. 有沒有處理term不對要變成follower (有人說可以只讓leader變成follower就好，但我試了之後會報錯)

接著就是AppendEntries，

  1. heartbeat不特別!! 如果你看到你的code有if len(entries) == 0有很高的機率你的code是錯的
    • 在client push東西後其實可以只透過heartbeat去更新log (但是很慢)
  2. candidate或是leader要變成follower，也只能是follower
  3. 有沒有處理term不對要變成follower
  4. 有沒有正確的trim log與merge entries

apply log到client的時候，

  1. 要確認是不是自己的term
  2. commit index夠不夠大 (其實只要有更新commit index就可以試著apply了，不用讓另一個thread去monitor commit index的變化)

lab2c

這是實現log fast back與persist的部分

persist不難，只要記得，只在persisting state變動時做persist!!

log fast back有很多版本，可以去看教授的也可以做conflict index

聽起來都還好，但是這裡的test多的unreliable，也就是network partition、restart都加進來測，所以

  1. test花的時間變多了
  2. test會過不代表你的code是對的，有可能只是幸運
    • 有一次是跑50次在第49次fail其他都pass…

這裡整理一下遇過的錯

  • apply error: 同一個index上傳了不同的log
    • 你的RequestVote或AppendEntries或apply log寫錯了，要回去看fig 2
  • fail to reach agreement(livelock): 怎麼沒有leader或是一直有candidate跳出來
    • 你的RequestVote與AppendEntries寫錯了
    • election&heartbeat timer有沒有在對的時候reset
      • term不對要變成follower時要reset (這邊fig 2沒有寫但是要)
    • heartbeat timer的時間太長 或 election timer太短
  • deadlock
    • 看看你的method有沒有用到lock

lab2d

這是實現log compaction，原本是在lab3b，但現在搬來這裡

要做InstallSnapshot，這不難，把前面的rpc拿來改，這裡的重點是

  • 怎麼處理被trim過的log
  • 同時，前面的code也要能動

當初就是在這邊把apply log改成appiler的，因為

  • 因為tester的channel沒有buffer，不這樣做就等於在raft的lock中拿另一個lock，之後就會deadlock

前往lab3之前

要先大量測試你的raft都會過所有test，在這邊查出的問題越多之後的問題越少 只會剩下性能問題

lab3

利用你的raft建立一個容錯、線性一致的key-value db

這裡要注意的就是如果遇到重複、過期的request要怎麼處理? 引入序列號，這裡要client與server定義怎麼處理序列號，之後server就是照序列號一個一個處理上去

還有要處理如果leader壞了，之前commit的東西其實要重新丟一次(index與term對不上，可以看student guide的Re-appearing indices)

這裡還會對kv db做performance test，如果太慢要回去看raft!! 像我是之前raft做persist太多次，時間花太久

還有get要放到raft中同步給大家，不然不會有線性一致

lab4

現在把kv db拆成一個一個shard，分散在不同的raft group中，shard會在不同的raft group中移來移去

lab4a

產生每個shard對應到哪個group的configuration

這裡就是把lab3拿來改就好，把put/get換成join/leave，但要注意的是產生config的演算法一定要determinstic 不能同一個input之後每台server產生的config不一樣 (go的map走訪是undeterminstic)

lab4b

要做提供kv db與shard migration的server

這裡要處理shard migration，也是當初卡最久的地方，因為要自己設計這一塊，不像raft還有paper可以參考 同時也可以把challenge 1與2一起考慮進去

shard migration有兩種方式一個是主動push或是自己pull，兩種都差不多，但要注意的是 只有在所有shard都完成migrate才能使用新的config，不然會看到兩個一樣的shard同時在服務或是shard去不到該去的地方!!

另外有人提到要做no-op，因為raft的leader只能commit自己term的log，之後前面沒有commit的log也會被一起commit (詳情見raft paper的fig 8) 所以可能有一種情況是在前一個leader commit之前就壞了，之後選出新leader，但是client沒有塞任何東西，導致raft不apply log以及client等不到commit 所以no-op就是在新leader產生時可以丟一個沒有任何意義的commit出去，把前面還沒commit的給commit上去 (但6.824的lab沒做也是pass)

在確定shard migration的設計之後遇到的bug是shard deletion (challenge 1)明明會pass但是因為花太久時間變成fail 這裡試過

  1. shard migration從一次一塊變成一次一個group
  2. 把大lock分成shard與pusher一人一個
    • 在處理的時候發現慢慢code變回OOP的樣子，很奇妙
  3. 從存一整個configuration變成只存用的到的部分
  4. get的結果不用raft傳回來

但頂多從330秒變成318秒而已 (還有看到有人用zlib，wow)

最後是把timeout重試的時間調短(從3秒變成500ms)，大概60秒就做完了，wow

所有lab之後

6.824其實沒有把每個用的分散式系統用到的手法的名字在課堂上介紹，反而是每堂課就是一篇paper看別人怎麼設計與遇到的困難是什麼，所以有人說6.824沒有什麼架構

但其實這些手法在做lab時就會被實現出來，但lab沒有涉及到transaction的部分，還有那些手法的名字還是可以認識一下，所以可以去讀data-driven internsive application

還有raft其實與實際用的差很多，工業的raft有許多優化手段，像readIndex或lease read，許多工業級的raft都可以看看

Ref

MIT 6.824 lab心得