以前紹介したHDFSのイレイジャーコーディング「HDFSが変わる？HDFSのイレイジャーコーディング対応」について詳しく書かれたブログがClouderaから公開されました。Hadoop 3.0をターゲットにして開発されているようです。

http://blog.cloudera.com/blog/2015/09/introduction-to-hdfs-erasure-coding-in-apache-hadoop/

背景から設計の方針、評価まで幅広くかなり詳しく網羅されており読み応えがあります。しかし、日本語訳が出るかわからないので、自分用にまとめてみました。間違いを発見したらご指摘下さい。

※Erasure Coding、イレージャーコーディングとイレイジャーコーディングのどちらが良いか迷いましたが、Erasureの発音より「イレイジャー」にしました。

イレイジャーコーディング(EC)の目的

現在のHDFSの実装は、データをブロック（デフォルトは128MB）に分割し、そのブロックを複製（レプリケーション：デフォルトは３）することにより耐障害性と可用性を持たせます。

レプリケーションの利点

• 単純な実装、ローカリティ、耐障害性

レプリケーションの欠点

• ストレージ効率。しかし、複製係数が３ということは２つの複製が必要になるためストレージ効率が悪化する（ストレージの効率＝33%）。
• 複製の際に生じるオーバーヘッド（ネットワーク帯域）
• 通常は利用されないブロックにもストレージ領域が消費されてしまう

このストレージの効率性を改善するために実装が進められているのがHDFS-EC (HDFS Erasure Coding)です。Facebookで実装しているHDFS-RAIDも同じ目的です。

---

※以降はブログから気になる点をピックアップしています。かなり大雑把なので詳細は元のブログも参照してください。。

ECとRAIDについて

レプリケーションとXOR（排他的論理和）についての利点と欠点、XORの制限に対処するリードソロモンについてはClouderaのブログを参照してください。HDFS-ECで用いられているリードソロモン（以降RS）は誤り訂正符号のことで、詳細はWikipediaに記載されています。RSを使うことでデータに対して複数のパリティを持たせることができます。RS (6,3)であれば、データのセルが6に対してパリティが3という意味です。

• 複製係数３・・・データの耐久性=2、ストレージの効率=33%
• 6データセルでのXOR・・・データの耐久性=1、ストレージの効率=86%
• RS(6,3)・・・データの耐久性=3、ストレージの効率=67%
• RS(10,4)・・・データの耐久性=4、ストレージの効率71%

分散ストレージシステムでのEC

分散システムでは、通常ファイルを固定長の「論理ブロック」に分けて分散配置することが一般的です。ECでこの論理ブロックをクラスタのストレージにどう配置するかにはブログのFigure 3にあるように、２通りの方法があります

• 連続(Contiguous)

  • 現在のHDFS実装のように、ファイルを連続した論理/ストレージブロックに分けて配置（Figure 3の上の図）
  • 連続してブロック配置することで、単純になり読み出すのは簡単
  • ファイルが大きい（128MBを超えるような）場合に適している
  • RS(10,4)のような場合、128MBのブロックだと非効率（データ1ブロック、パリティ4ブロックでストレージのオーバーヘッドが400%）
  • パリティの計算に多くのバッファが必要

• ストライピング(Striping)

  • 論理ブロックを「セル」というもっと小さな単位に分け、ラウンドロビンで複数のノードに配置していく（Figure 3の下の図）
  • データの読み込みに複数のセルを読み込まなければならない
  • セルが複数のディスク（スピンドル）に配置されることで、読み込みは複数のディスクが利用でき、スループットが良い。しかしほとんどの読み込みはリモートのノードからになるので、高速なネットワークが必要になる
  • ディスク効率が良い
  • ローカリティに影響のあるワークロードは最善にならない

従って、どちらが良いかは、どのようなファイルを格納するかというユースケースに依存します。Clouderaの大規模な顧客３社のストレージの使用状況を調査し、ブロック未満のファイルが大半であるという実証結果 (Figure 5)から、ストライピングで実装することになったようです。（詳細のデータも公開されています。これは興味深い）

NameNodeのブロックのコンセプト

ECでストライピングを利用する場合、NameNodeはDataNodeに配置された小さなセル（論理ブロック）を扱う必要があるため、今まで通りに扱うとNameNodeのメモリの使用量が増加することになります。この対処のため、Block IDの名前付けを工夫することにしました。単純にセルをブロックとしてマッピングするとメモリ使用量が250-440%の増加になりますが、この工夫により21-76%の増加で済むようです。うまい仕組みですね。詳細はFigure 7とTable3を参照してください。

FacebookのHDFS-RAIDでのECの実装のような RS (10,4)ではストレージの効率性は良いですが、リカバリのコストがかかるという欠点があります。

また、この論理ブロックの抽象化により、NameNodeでのunder replication, 複製のアルゴリズム、クォータ、fsckなど多くの変更が必要になります。

クライアント側の拡張

従来のDFSInputStreamとDFSOutputStreamは、データのストライピングとECをサポートするDFSStripedInputStreamとDFSStripedOutputStreamに拡張されました。クライアントは論理ブロックの複数のストレージブロックを並列で扱えるようになっています。（今まで複数のストリーム使えなかったような気が、、、）書き込みと読み込みについてはブログを参照してください。

DataNodeの拡張

クライアント側でのデータ再構築をさけるため、DataNode障害をバックグラウンドで検知して修復するリカバリについての処理が変更となり、ErasureCodingWorkerコンポーネントによって扱われるようになります。手順はブログを参照のこと。

コーデックの計算フレームワーク

EC-RAIDのエンコードとデコードの実装について、３つの実装を比較したグラフがFigure 8に掲載されています。

• HDFS-RAID (Facebookの実装）
• 新しくJavaで実装したCoder
• ISA-L coder (Intelligent Storage Acceleration Library: SSEのようなIntelのハードウェア実装のためのライブラリ。AVX、AVX2）

HDFS-RAIDと比較して、新しいJavaのcoderで4倍、ISA-Lを使うと20倍ほど良い性能になっています。CPUが対応しているならISA-L使わない理由はなさそうですね。

Figure 9にはHDFSの書き込みスループットと読み込みスループットのグラフが記載されています。ISA-Lによるハードゥェアのコーデックを使用した場合、現在のレプリケーションよりも３倍ほど良い性能が出ていますね。（ソフトウェアによるコーデックだと現在よりも遅い）読み込み時に２台のDataNodeをKillした場合でも同様に良いスループットが出ています。

今後の作業

• Read-Solomon以外にHitchHiker, LRCなどの複数のコーデックを利用できるようにし、新しいECアルゴリズムを容易に開発、実装できるようにする
• NameNodeのメモリ使用率の向上とデータ再構築の遅延の削減

• HDFS-EC フェーズ２ (HDFS-8030)
  • 遅延に影響のあるワークロードでストレージ領域を節約するために、連続したブロック配置のイレイジャーコーディングに対応する

 

追記：来週開催される Strata + Hadoop World でセッションがあるようです。

http://strataconf.com/big-data-conference-ny-2015/public/schedule/detail/42957