紅岸智能 周雪松新系列知識點
帶你突破兩個重要的分布式算法
大家在閱讀 TiKV 源碼時，如果不了解 Raft 和 Percolator 算法，就很容易迷失方向，不知如何下手。就算了解這兩個算法，實操過程中也有可能出現「知道大體做什麼，卻不明白為什麼要這麼做」的情況。因此在 Rust 語言課程完成之後，我們將繼續帶大家學習這兩個重要的分布式算法。
關於 Raft,我們直接採用 MIT 6.824 課程，並將 Golang 的教材移植到了 Rust。6.824 提供豐富的測試，從 leader 選舉一路測到線性一致性。在移植教程的時候，我們想儘可能地使用最簡單的代碼來實現，方便大家理解課程內容。但是移植過程並非一帆風順，其中最大困難是 goroutine 的代碼。在 Golang 可以隨時開啟 goroutine 執行異步的代碼，但是 Rust 沒有類似的功能，考慮再三，我們最後決定使用 Future 來寫這類代碼。
在移植完代碼後，我們還驗證了代碼的正確性，驗證 Raft 的測試框架教程的思路也很簡單，用一個正確實現了 Raft 的庫來跑一遍教程中的考核測試。我們選擇了 github.com/pingcap/raft-rs 這個項目，測試一遍後修復了幾個 BUG。不過事實證明只測試一遍是不夠的，課程發布後社區小夥伴在學習過程中，又陸陸續續發現並解決了幾個 BUG,在這裡特別感謝 @wjhuang 和 @NingLin-P 兩位同學的貢獻。
至於 Percolator,由於沒有現成的教學課程，我們決定從零開始設計。好在有一部分可以直接復用 6.824 代碼，比如網絡框架，它是比較通用的網絡測試框架，可以模擬多種常見的網絡錯誤，比如丟包、亂序等。Percolator 的測試也比較豐富，從 TSO 到 lost update 再到 read/write skew 最後到網絡錯誤，都有覆蓋。
學完這兩個算法後，相信大家能達到「知其然，又知其所以然」的程度，再看 TiKV 代碼的時候不會一頭霧水。之後我們還將補充更多內容，比如 multi-raft、集群調度等，終極目標是讓大家可以實現一個簡易版 TiKV。
另外值得一提的是，在線下課程中，我們將著重介紹 TiDB/TiKV 架構，帶領大家了解實現原理與細節，還有專門的 Mentor 指導大家深度參與 TiDB/TiKV 開發。更多的細節已在 這篇文章 中披露，在這就不贅述了。