Skip to main content

山椒の実

A Tale of Two Erasure Codes in HDFS (Mingyuan Xia, McGill University; Mohit Saxena, Mario Blaum, and David A. Pease, IBM Research Almaden)

読んだ感想を、ちょっと実況風に。

HACFS。Hadoop HDFSのErasure Codeの話。Erasure Codeってのは、知ってる人も多いと思うけど、高度なパリティみたいなもんですね。一部が壊れても復元できるようにしている。例えば身近なところだとQRコードとか、一部が読み取れなくても情報が伝わるようになってたりするでしょ? ああいう種類のコード化の名前がErasure Code。←これで説明になってる??

HDFS-RAIDというもののモジュールを書いて実験している。元職の近所でもErasure Codeのリカバリ時間の問題に取り組んでいたのを思い出しながら読んだ。

ここでは故障時のread時間とリカバリ時間がトレードオフになっている。ほとんどは1重故障で、多重故障を救わなければならないケースは2%くらいみたい。いろいろ分散ファイルシステムのErasure Code対応の特性について調べていて、Google ColussusFSとかFacebookのやつはReed Solomonでパラメータ違い、AzureのやつはLRCだが、HACFSは両方使う。ReadにはRSを使って、リカバリにはLRC、それでいいとこ取り? …という気持ちで読んでいたがそういう話ではなく、とりあえずread hotかどうかでコードを変えるという判断をしているみたいだった。

よく知らないけどこの分野ではLDPCとか使わないのかな。RS/LRCの他にProduct Codeという聞きなれないものの紹介があった。これは2次元のXOR。RAID6で昔は使われていた記憶があるやつに似ているが、縦パリティがナナメじゃないのはなんでだろう…セクタエラーへの対処か?? →1個のハコが1個のディスクだった!!

このProduct Codeはとても良い。おれはこれをなんで知らなかったんだろう。Product Codeに無知だった自分を恐れた。Introduction to Coding Theoryって本に書いてある常識的な? やり方らしいね。むかしむかし、16進ダンプが雑誌に載っていた時代に縦横のチェックサムがあったじゃん。あれと同じレイアウトでXORをつけていく。そう考えると単純で、教科書に書いてあってもおかしくない。

HACFSではコード化をadaptiveにしたいので、upcode/downcodeできるコードにして、hotデータ(fast code)とcoldデータ(compact code)のパラメータを選べるようにしておく。

ここから先はスライドを見たほうが理解は早い…2種類のコードを使い分けるんじゃなくて、read hot/coldでパラメータを変えることで最初のほうに出てきた特性グラフの点をハコにする話だったのだ。そして実装したのはRSではなくてLRCとProduct。

少し考えてみたが、Productでは1つの故障ディスクのデータを再現するのに縦横2つの別々のセットがあるので、2多重を確保できる。例えばリカバリの復元を縦、readの復元を横で構成するとか…。

Product Codeを知っただけで読んだ価値はあったな。

ただ、これって最初のほうの問題提起(だと私が思った)、read時間とリカバリ時間のトレードオフは解消しないんじゃないかと思う。readにしてもリカバリにしても、復元のために読み込むデータ量が少ないほうが良いわけだよ。それはcoldデータが主にリカバリで必要になり、hotデータが主にreadで必要になると考えたところで、どっちだって同じ条件でfast codeのほうを使ったほうが良くなるじゃないかと。

そのへんでちょっと混乱したまま最後の方まで来てしまった。なんとなく、問題提起のところを読み違えたまま読み進んでしまったんじゃないかって感触がある。また読み返すべきだろうか…それとも、どんどん次を読んでったほうが有益か?