読者です 読者をやめる 読者になる 読者になる

HBase 0.96 で導入される新しいコンパクション「Exploring Compaction」

Hadoopアドベントカレンダー2013、3日目を担当する @shiumachi です。
今回は HBase 0.96 の新機能を一つ紹介します。

要約


HBase 0.96 は賢くなったのでみんな使おう。

コンパクションのおさらい


HBase では、Log Structured-Merge tree (LSM-tree) というデータ構造を使っています。
LSM-tree を簡単に説明すると、入力されたデータをログとメモリ上のデータストア(Memstore、メモリストア) に書き込みます。
メモリストアがいっぱいになると、まとめてディスクにフラッシュし、新しいストアファイルを生成します。
このストアファイルがたまってきたときに、少しづつ一まとめにしてなるべくファイル数を少なくするようにします。これがコンパクションです。


コンパクションを実行することにより、ファイルは一つにまとまります。これにより、ディスク上の連続した領域にデータをまとめることができ、ディスクシークの回数を少なく保った上で予測可能にできます(最大でストアファイルの数と同回数だけ)


しかし、このコンパクション操作は非常に重い処理になります。
コンパクションを単純に説明すると、ディスク上のストアファイルを読込み、新しいストアファイルに書き出してマージしていくというものです。これだけで多大なディスクの負荷がかかることが分かるでしょう。
また、HBaseは普通HDFSを始めとした分散ファイルシステムをストレージとするため、ネットワーク転送も発生します。
かといってコンパクションを実行しなければ、ストアファイルが多くなり、一度のキーのルックアップに必要なディスクシークの回数が増え、やはり性能が劣化します。
現在のディスクIOと将来のディスクIOのトレードオフを考えることが、コンパクション戦略に必要となります。しかし、将来どれだけのディスクシークが発生するかは誰にもわかりません。そのため、ヒューリスティックな手法で現実解を求めていくことになります。

HBase 0.94 までのコンパクションアルゴリズム


コンパクションには2種類あります。メジャーコンパクションとマイナーコンパクションです。
メジャーコンパクションは、全ストアファイルを読み込んで一つのストアファイルに書き出していく(まとめる)処理です。このとき、以下の条件に当てはまるキーバリューのみを書き出します。

  • tombstone マーカーがついていない ( delete されたときに付与される、論理削除のマーカー)
  • TTL (生存時間) が残っている
  • バージョンが最大バージョン数を超えていない。例えばバージョン保持数が3のとき、4つ前のバージョンのセルはこのタイミングで物理削除される


もう一つはマイナーコンパクションです。今回の記事ではこちらの方に注目します。
マイナーコンパクションは、たくさんあるストアファイルのうち、あるアルゴリズムに基づいて抽出されたファイル群のみを一つにまとめます。このとき「なるべく小さいファイルを(ディスクIO低減のため)、なるべく多くの数(将来のディスクシーク数低減のため)コンパクションする」ことが重要となります。

まず、ストアファイルが一列に並んでいるとします。左のファイルの作成時刻が一番古く、右に行くにしたがって新しくなるとします。

  1. 1番左のストアファイルを選択する( F0 とする )。F0 のファイルサイズを S0 とする。
  2. F0 より右の全ストアファイルのサイズの和 S(1_N) を求める。
  3. もし S0 > S(1_N) * hbase.hstore.compaction.ratio (デフォルト 1.2) なら、選択ストアファイルを1つ右にずらし、同様の手順を実行する。
  4. もし S0 < S(1_N) * hbase.hstore.compaction.ratio (デフォルト 1.2) なら、F0 の一つ右のファイルから最大 hbase.hstore.compaction.max 個(デフォルト10) のストアファイルをコンパクション対象とする。
  5. もしコンパクション対象数が hbase.hstore.compaction.min 個 (デフォルト 3) より少なかったら何もせずに終了。
  6. コンパクション対象のファイル群をコンパクションして終了。


具体例が hbase bookのコンパクションのページ に載っています。


たとえばストアファイルのサイズが 100、50、23、12、12 と並んでいる場合、23、12、12 がコンパクションされます。
ここで注意しなければいけないのは、ファイルのソートはあくまで「作成日時」です。サイズではありません。
このアルゴリズムは、「ほとんどの新しいファイルは古いファイルより小さい」という前提に基づいています。


ストアファイルはメモリストアのフラッシュによって作成されます。このフラッシュ上限は決まっていて、hbase.hregion.memstore.flush.size (デフォルト64MB) * hbase.hregion.memstore.block.multiplier (デフォルト2) = 128MB となります。
古いファイルはコンパクションされていて大きくなっているはずなので、この前提は多くのケースにおいて成り立ちます。


しかし、当然成り立たないケースもあります。
例えば HBase のバルクロードは、ストアファイルを直接 HBase のリージョン内に配置する方法で、非常に高速にデータをロードできるのですが、新しいファイルなのに非常に大きいストアファイルをロードすることになり、上記の前提を崩してしまいます。
先程紹介したアルゴリズムは、あくまでコンパクション対象の最初の一つしか判定を行いません。アルゴリズム内で条件を満たしたストアファイルがあれば、そこから一定数のファイルを自動的に取り込みます。
これにより、この大きなストアファイルがあると、より古いファイルはコンパクション対象として判定されてしまいます。こうして大きいファイルがマイナーコンパクションの対象になってしまう可能性が高くなるわけです。

新しいコンパクションアルゴリズム


そこで 0.96 からは、Exploring コンパクションポリシーという新しいアルゴリズムをデフォルトアルゴリズムに採用しました。(HBASE-7842)



基本方針は単純で、「可能性のある組み合わせ全部計算して最適なものを選ぶ」です。
コンパクション対象を検索するところまでは既存のアルゴリズムと変わりません。
検索した後、以下のようなアルゴリズムで最適解を選んでいきます。

  1. コンパクション対象となった最初のストアファイルを F1 とする。
  2. F1から右に min 個以上 max 以下の連続したストアファイルを全て吟味していく。(デフォルトだと3〜10個) つまり、F1〜F3の組み合わせ、F1〜F4の組み合わせ、……というように吟味していく。
  3. このうち以下の条件に当てはまるものを選択する。
    1. 最も対象ストアファイル数が多い
    2. もしストアファイル数が同じものが複数ある場合、最もファイルサイズが小さい


これにより、バルクロードを用いている環境でも無駄なIOを生じることなくマイナーコンパクションを行うことができるようになりました。
この機能は、プラガブルコンパクションポリシーという HBase 0.96 から導入された新しい機能を前提として実装されています。(HBASE-7516)


今後、より効率のいい、あるいは特殊な状態に特化したコンパクションポリシーなどが実装されていくことでしょう。

おまけ: CDH の話


CDH5 では HBase 0.96 ベースになると思われますので、Exploring Compaction はデフォルトでオンになっています。
実は CDH4 でも使用することができます。CDH4.4 で、HBase 0.94 に Exploring Compaction をバックポートするパッチが入っています。(HBASE-8283)

githubのコミットログ


HBase 0.94 にはプラガブルコンパクションポリシーがないため、コンパクションのコードにそのまま追加しています。
デフォルトはもちろんオフです。
hbase.hstore.useExploringCompation を true にすると使うことができるため、興味のある人は試してみてください。