erasure

Daily Hacker News 上看到的紋章，「Erasure Coding for Distributed Systems」這篇討論了 Erasure code。

以前在學校裡面學 coding theory 的時候有學到一些經典的演算法，尤其是一定會教到 Reed-Solomon error correction 這個演算法，不過實務上 Reed-Solomon 因為用到 finite field 運算 (又稱 Galois field，所以簡寫常用 $GF$ )，所以效率並不算好，在 RAID 系統上面除非 controller 的 CPU 或是晶片對 GF 運算加速，不然大多都會用替代算法。

For the special cases of 1-3 parity chunks ( $m \in {1,2,3}$ ), there are algorithms not derived from Reed-Solomon and which use only XORs:

允許掛一顆的演算法就是 RAID 5，這邊用 XOR 就很容易導出來，並且分析證明。

開始有難度的是允許掛兩顆的演算法，也就是一般熟知的 RAID 6，在這篇文章裡面提到了好幾個演算法，不過有些有專利問題：

$m=2$ is also known as RAID-6, for which I would recommend Liberation codes[8][9] as nearly optimal with an implementation available as part of Jerasure, and HDP codes[10] and EVENODD[11] as notable but patented. If $k+m+2$ is prime, then X-Codes[12] are also optimal.

允許掛三顆的則是提到 STAR coding：

$m=3$ can be done via STAR coding

算是留個記錄好了，這些演算法又讓我想到先前剛進 Migo 的時候還學到 Raptor code，但使用場景不對反而遇到問題，又是另外一個故事了...

回到開頭的 Reed-Solomon，會印象很深還是因為當初在數學系的集合論學了 finite field 好幾年後，在資工系第一次看到居然可以用 finite field 解決這個問題...

Tag: erasure

RAID6 的 Erasure code 實作