Erasure Coding

在學過 Galois field arithmetic 提供的代數工具以及 RAID 的磁碟冗餘策略之後，我們可以進入更通用的 erasure coding 框架。Erasure coding 與 error correction 的關鍵差異在於：erasure 情境下我們已經知道哪些資料區塊遺失了（例如某顆磁碟故障），只需要從剩餘的區塊中重建資料，而不需要像 error correction 那樣先定位錯誤。我們會介紹 Reed-Solomon code 如何在 GF(2^w) 上建構編碼矩陣，以及 MDS（Maximum Distance Separable）property 與 Singleton bound 的意義——MDS code 能以理論上最少的冗餘達到最大的容錯能力，可以視為 RAID 5/6 的數學推廣。實務上，我們會討論如何使用 Cauchy matrix 來建構高效的編碼矩陣，使得 encoding 和 decoding 只需要 XOR 運算即可完成。此外，我們也會介紹 Local Reconstruction Codes（LRC）的設計動機：在大規模分散式儲存系統中，修復單一區塊故障時若需要讀取所有存活區塊，網路開銷會過於龐大，LRC 透過增加 local parity 來大幅降低單一區塊修復所需的 I/O 量。

Key Concepts

我理解 erasure coding 與 error correction 的關鍵差異：erasure 情境下已知遺失資料的位置，只需重建資料，不需要先定位錯誤

我理解 Reed-Solomon code 如何在 GF(2^w) 上透過 encoding matrix 將 k 個資料區塊編碼為 n 個區塊，使得任意 k 個區塊即可還原原始資料

我理解 MDS（Maximum Distance Separable）property 與 Singleton bound 的意義：MDS code 以理論上最少的冗餘達到最大容錯能力

我了解 Cauchy matrix 如何建構高效的 encoding matrix，使得 encoding 與 decoding 只需要 XOR 運算即可完成

我理解 LRC（Local Reconstruction Code）的設計動機：透過增加 local parity 來大幅降低分散式儲存系統中單一區塊修復所需的 I/O 量，避免讀取所有存活區塊的龐大網路開銷

Recommended Resources