RAID 6

いい加減タグが適当すぎる。RAID 6がsoftwareタグっておかしいだろう。そのうちこの手のねたはtechnologyタグとかでまとめたほうがよさそうだ。

まぁそれはさておきReed-Solomonについて勉強しているわけだが、ようやくなんとなくわかってきた。一般的に使われているReed-Solomonではx^8 + x^4 + x^3 + x^2 + 1の原始多項式が使われているわけだが、じゃぁ3次の原始多項式x^3 + x^2 + 1で得られるコードはどんなもんだろう、というのを自分への宿題にしてみるテスト。

そのうちちゃんとまとめたいのだが、原子多項式x^3 + x^2 + 1からとりあえず以下のような配列が得られる

x^3 + x^2 + 1 = 0
 x^0 = 1, x^1 = 2, x^2 = 4, x^3 = x^2 + 1 = 5, x^4 = x^3 x = x^3 + x = x^2 + x + 1 = 7, x^5 = x^3 + x^2 + x = 1 + x = 3, x^6 = x^2 + x = 6, x^7 = x^3 + x^2 = 1
 -> A[8] = {0, 1, 2, 4, 5, 7, 3, 6}

で符号としては

Q = D0・A[0] + D1・A[1] + ... + D7・A[7]

となる。ここで＋はxorで、・はガロア乗算である。xorはともかく、ガロア乗算はどう計算するのか。ここでDnはx^kであるとする。で、A[n]はx^nであるので、その積はx^(n + k)となる。で、n + kはGF(2^3)の和算となる。

Reed-Solomonの何がいいのかというと、変換のための係数をいちいち計算しないでテーブル化できることだろうか。テーブル化してしまえば残りは簡単な足し算とxorで実装可能である。で、逆に欠点は、テーブルのサイズが2^(シンボル長）*シンボル長byte必要になることか？つまり、上記の生成多項式を8次のx^8 + x^4 + x^3 + x^2 + 1にすると、上の例ではDは1つあたり1byteとなる。これだとRAID6でストライプ幅nByteのパリティを作成するのに、n * Drive数のガロア乗算と(n-1)*Drive数のxorが必要になる。で、32bitCPUでは1byteのxorコストと4byteのxorコストにそんなに差はないわけで、1シンボルを4byteにすることで4倍の性能を、ということが思いつく。しかしReed-Solomonでは4byteシンボルのデータのコードを作成しようとすると2^32 * 4byte必要になる。ざっと8GByte。しかも実際に必要になるテーブルはデコードを考えると2倍以上である。というわけであまり現実的ではなくなる。

そんなことを最近ちょっと考えていたわけで。

まったくまとまってない文章だなぁ。ガロア体とかあんまり理解できていないのでそのあたりちゃんと理解したらもう一回整理して書いてみよう。