アコーディオン: HBase メモリ圧縮アルゴリズム

最近では、HBase ベースの製品の読み取り速度と書き込み速度に対する要件がますます高まっています。理想的には、HBase が信頼性が高く永続的なストレージを確保しながら、メモリ内でデータの読み取りと書き込みの速度を実現できることが期待されます。この目的のために、HBase 2.0 でアコーディオン アルゴリズムが導入されました。

Hbase RegionServer は、データを複数のリージョンに分割する役割を担います。 RegionServer 内のスケーラビリティ (垂直方向) は、エンドユーザー エクスペリエンスと全体的なシステム使用率にとって重要です。アコーディオン アルゴリズムは、RAM の使用率を向上させることで、RegionServer のスケーラビリティを向上させます。これにより、より多くのデータをメモリに保存できるようになり、ディスク読み取りの頻度が減ります (つまり、HBase のディスク占有量と書き込み方法が減り、RAM の読み取りと書き込みが増え、ディスクへの IO アクセスが減ります)。 HBase 2.0 より前では、これらの指標を同時に満たすことができず、互いに制限し合っていました。この状況は、Accordion の導入後に改善されました。

[[228381]]

アコーディオン アルゴリズムは、HBase のコア アーキテクチャである LSM アルゴリズムから派生したものです。 HBase リージョンでは、データはキーと値の形式で検索可能なストレージにマッピングされ、新しいデータが入力され、最上位のデータがメモリ (MemStore) に保存され、残りは変更されていない HDFS ファイル、つまり HFiles になります。 MemStore がいっぱいになると、データはハードディスクにフラッシュされ、新しい HFile が生成されます。 HBase はマルチバージョン同時実行制御を使用し、MemStore は変更されたすべてのデータを独立したバージョンとして保存します。データの複数のバージョンが MemStore と HFile に同時に保存される場合があります。複数バージョンのデータを読み取るときは、キーに従って HBase から BlockCache 内の HFile をスキャンし、最新バージョンのデータを取得します。ディスク アクセスの頻度を減らすために、HFiles はバックグラウンドでマージされます (つまり、冗長なセルを削除してより大きなファイルを作成する圧縮プロセス)。

LSM は、ランダムな読み取りと書き込みを順次的な読み取りと書き込みに変換することで、書き込みパフォーマンスを向上させます。以前の設計では、圧縮されたメモリ データは使用されていませんでした。主な理由は、LSM ツリーが最初に設計されたとき、RAM がまだ非常に希少なリソースであったため、MemStore の容量が非常に小さかったことです。ハードウェアが進化し続けると、RegionServer によって管理される MemStore 全体が数ギガバイトになる可能性があり、HBase の最適化に大きく余裕が生まれます。

Accordion アルゴリズムは、データがまだ RAM 内にある間に冗長性やその他のオーバーヘッドを排除できるように、LSM を MemStore に再適用します。そうすることで、HDFS へのフラッシュの頻度が減り、書き込み増幅とディスク使用量が削減されます。 フラッシュ回数が減ると、MemStore のディスクへの書き込み頻度が減り、HBase の書き込みパフォーマンスが向上します。ディスク上のデータが少なくなると、ブロック キャッシュへの負荷も軽減され、読み取り応答時間が改善されます。最終的には、ディスクへの書き込みが減るということは、バックグラウンドでの圧縮も減ることを意味し、読み取りと書き込みのサイクルも減ります。全体として、メモリ圧縮アルゴリズムの効果は、システム全体の実行速度を高速化する触媒として考えることができます。

現在、Accordion は、基本と即時の 2 つのレベルのメモリ圧縮を提供しています。前者はすべてのデータ更新の最適化に適用できますが、後者は生産消費キュー、ショッピング カート、共有カウンターなど、データ フローが大量にあるアプリケーションに非常に役立ちます。これらすべてのユースケースでは、行キーが頻繁に更新され、データの複数の冗長バージョンが生成されますが、ここでアコーディオン アルゴリズムが役立ちます。一方、積極的な圧縮最適化により計算オーバーヘッド (メモリ コピーとガベージ コレクションの増加) が増加する可能性があり、データ書き込みの応答時間に影響する可能性があります。 MemStore がオンヒープ MemStore-Locally Allocated Buffers (MSLAB) を使用する場合、追加のオーバーヘッドが発生する可能性があります。したがって、この構成を Eager 圧縮と組み合わせて使用​​することはお勧めしません。

使い方

メモリ内圧縮は、グローバルにも列ファミリ レベルでも構成できます。現在、なし (従来の実装)、基本、および即時の 3 つの構成レベルがサポートされています。デフォルトでは、すべてのテーブルは基本的なメモリ内圧縮を使用します。この構成は、hbase-site.xml で次のように変更できます。

 <プロパティ>
        <名前> hbase.hregion.compacting.memstore.type </名前>
        <値> <なし|基本|積極的> </値>
 </プロパティ>

次のように、HBase シェルで各列ファミリを個別に構成することもできます。

作成する  '<テーブル名>' ,
    { NAME => '<cfname>' ,
    IN_MEMORY_COMPACTION => ' <なし|BASIC|EAGER>' }

パフォーマンスの向上

HBase は、YCSB (Yahoo Cloud Service Benchmark) を利用して徹底的にテストされました。実験で使用されたデータセットのサイズは 100 ～ 200 GB であり、結果から、アコーディオン アルゴリズムによって HBase のパフォーマンスが大幅に向上したことが示されました。

ヘビーテール (Zipf) 分布: テスト ワークロードでは、rowkey は実際のほとんどのシナリオで発生する Zipf 分布に従います。この場合、操作の 100% が書き込みである場合、Accordion は書き込み増幅を 30% 低減し、書き込みスループットを 20% 向上し、GC を 22% 低減します。操作の 50% が読み取りの場合、末尾の読み取りレイテンシは 12% 減少します。

均等な分散: 2 番目のテストでは、行キーが均等に分散されます。操作の 100% が書き込みの場合、Accordion は書き込み増幅を 25% 低減し、書き込みスループットを 50% 向上し、GC を 36% 低減します。末尾の読み取りレイテンシは影響を受けません (ローカリゼーションがないため)。

アコーディオンの仕組み

高レベル設計:

Accordion では、MemStore の内部圧縮 (CompactingMemStore) 実装方法を導入しています。デフォルトの MemStore と比較して、Accordion はすべてのデータを完全なデータ構造に保存し、セグメントを使用して管理します。最新のセグメントはアクティブ セグメントと呼ばれ、変更可能で、Put 操作の受信に使用できます。アクティブ セグメントがオーバーフロー条件 (デフォルトでは 32 MB、MemStore のサイズの 25%) に達すると、メモリ内パイプラインに移動され、不変セグメントとして設定されます。このプロセスをメモリ内フラッシュと呼びます。 Get 操作は、これらのセグメントと HFiles をスキャンしてデータを取得します (後者の操作は、HBase への通常のアクセスと同様に、ブロック キャッシュを介してアクセスされます)。

CompactingMemStore は、より大きなセグメントを形成するために、バックグラウンドで複数の不変セグメントを随時マージする場合があります。したがって、パイプラインはアコーディオンのふいごのように「呼吸する」（膨張したり収縮したりする）ので、Accordion もアコーディオンと翻訳されます。

RegionServer は、メモリを解放するために 1 つ以上の MemStore をディスクにフラッシュするときに、パイプラインに移動された CompactingMemStore 内のセグメントをディスクにフラッシュします。基本的な原則は、MemStore のライフサイクルを延長してメモリを効果的に管理し、全体的な I/O を削減することです。フラッシュが発生すると、パイプライン内のすべてのセグメントが削除されてスナップショットが形成され、マージとストリーミングによって新しい HFile が形成されます。図 1 は、CompactingMemStore の構造と従来の設計を示しています。

図 1. CompactingMemStore と DefaultMemStore

セグメント構造:

デフォルトの MemStore と同様に、CompactingMemStore はセル ストアの上部にインデックスを維持し、キーによる高速検索を可能にします。両者の違いは、MemStore インデックス実装では、Java スキップリスト (ConcurrentSkipListMap - 動的だが贅沢なデータ構造) を通じて多数の小さなオブジェクトを管理することです。 CompactingMemStore は、不変のセグメント インデックスの上に、効率的でスペースを節約するフラット レイアウトを実装します。この最適化により、すべての圧縮戦略で RAM のオーバーヘッドが削減され、データの冗長性がほぼなくなることもあります。セグメントがパイプラインに追加されると、CompactingMemStore はそのインデックスを CellArrayMap と呼ばれる順序付けられた配列にシリアル化し、バイナリですばやく検索できるようになります。

CellArrayMap は、Java ヒープからのセルの直接割り当てと、MSLAB (オンヒープまたはオフヒープ) のカスタム割り当ての両方をサポートし、実装の違いはインデックスによって参照される KeyValue オブジェクトを通じて抽象化されます (図 2)。 CellArrayMap 自体は常にヒープ上に割り当てられます。

図 2. フラットな CellArrayMap インデックスと MSLAB セル ストレージを備えた不変セグメント

圧縮アルゴリズム:

メモリ内圧縮アルゴリズムは、パイプライン内のセグメント全体にわたって単一の平坦化されたインデックスを維持します。この設計により、ストレージ スペースが節約され、特にデータ項目が小さい場合は、データを時間内にディスクにフラッシュできます。単一のインデックスを使用すると、検索操作を単一のスペースで実行できるため、テール読み取りの待ち時間が短縮されます。

アクティブ セグメントがメモリにフラッシュされると、圧縮パイプラインのキューに入れられ、非同期マージ スケジューラ タスクが直ちにトリガーされます。このスケジュールされたタスクは、パイプライン内のすべてのセグメントを同時にスキャンし (ディスク上の圧縮と同様)、それらのインデックスを 1 つにマージします。基本圧縮戦略と積極的圧縮戦略の違いは、セル データを処理する方法にあります。基本圧縮では、物理的なコピーを避けるために冗長なデータ バージョンを削除するのではなく、KeyValue オブジェクトの参照を再配置するだけです。一方、Eager 圧縮では冗長なデータが除外されますが、追加の計算とデータ移行が必要になります。たとえば、MSLAB メモリでは、生き残ったセルが新しく作成された MSLAB にコピーされます。

将来の圧縮では、基本圧縮戦略と積極的な圧縮戦略の自動選択が実装される可能性があります。たとえば、アルゴリズムは一定期間、積極的な圧縮を試行し、渡された値 (削除されたデータの割合など) に基づいて次の圧縮をスケジュールする場合があります。このアプローチにより、システム管理者は事前の決定を行う必要がなくなり、変化するアクセス パターンに適応できるようになります。