アコーディオン: HBase の「呼吸」メモリ圧縮アルゴリズム

導入

現在、HBase を搭載した最新の製品では、HBase の読み取りおよび書き込みパフォーマンスに対する期待がますます高まっています。理想的には、HBase は信頼性の高い永続ストレージを確保しながら、インメモリ データベースの速度も実現したいと考えています。コミュニティ貢献者は HBase 2.0 に Accordion と呼ばれる新しいアルゴリズムを導入し、これにより Hbase は理想的な目標に向けて新たな重要な一歩を踏み出すことができました。

Hbase RegionServer は、データを複数のリージョンに分割する役割を担います。 RegionServer 内のスケーラビリティ (垂直方向) は、エンドユーザー エクスペリエンスと全体的なシステム使用率にとって重要です。 Accordion アルゴリズムは、RAM をより有効に活用することで、RegionServer のスケーラビリティをさらに向上させます。アコーディオン アルゴリズムは、メモリ内により多くのデータを収容し、ディスクへの書き込み頻度を減らすことができます。これはまさに多くのシナリオで必要なことです。まず、HBase のディスク使用量と書き込み増幅が削減されます。次に、より多くのデータの読み取りと書き込みが RAM から直接取得され、ディスク I/O に基づく読み取りと書き込みが減少します。つまり、HBase のパフォーマンスが向上します。バージョン 2.0 より前では、これらの異なる指標を同時に満たすことはできず、互いに制限されていました。アコーディオン アルゴリズムを使用すると、これらすべてが同時に改善されます。

[[230102]]

Accordion は、HBase の LSM ツリー設計パターンに触発されています。 HBase リージョンは、一連の検索可能なキーと値のマッピングとして保存されます。一番上には MemStore と呼ばれる変更可能なメモリ ストアがあり、***Put からデータを受信します。残りは HFiles と呼ばれる不変の HDFS ファイルです。 MemStore がいっぱいになると、ディスクにフラッシュされ、新しい HFile が作成されます。 HBase はマルチバージョン同時実行制御を使用します。つまり、MemStore は変更されたすべてのデータを独立したバージョンとして保存します。したがって、データの複数のバージョンが MemStore レイヤーと HFile レイヤーの両方に存在します。読み取り操作が行われると、Hbase はまず BlockCache 内の Hfile をスキャンして最新バージョンのデータを取得します。ディスク アクセス回数を減らすために、HFiles はバックグラウンドで非同期的に圧縮およびマージされます。このプロセスでは、削除されたデータが実際にクリアされ、小さな HFile ファイルがマージされます。

LSM ツリーは、ランダムなアプリケーション レベルの I/O をシーケンシャルなディスク I/O に変換することで、優れた書き込みパフォーマンスを提供します。ただし、従来の設計ではメモリ データを圧縮しようとはしません。これは歴史的な理由によるものです。LSM ツリーが設計された当時、RAM はまだ非常に希少なリソースであったため、MemStore の容量は非常に小さかったです。ハードウェア環境が変化し続けると、RegionServer によって管理される MemStore 全体が数ギガバイトになる可能性があり、Hbase の最適化に大きく余裕が生まれます。

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

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

使い方

メモリ内圧縮は、グローバルおよび列ファミリ レベルで構成できます。なし (従来の実装)、基本、および即時の 3 つの構成レベルがサポートされています。

デフォルトでは、すべてのテーブルは基本的なメモリ内圧縮を使用します。このグローバル構成は、次のように hbase-site.xml で上書きできます。

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

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

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

パフォーマンスの向上

私たちは、人気の Yahoo Cloud Services ベンチマークである YCSB を使用して HBase を徹底的にテストしました。私たちの実験では、100～200 GB のデータセットを使用し、さまざまな代表的なワークロードを実行しました。結果は、アコーディオン アルゴリズムによってもたらされたパフォーマンスの向上が大幅に改善されたことを示しています。

ヘビーテール (Zipf) 分布: 最初の実験では、行キーがほとんどの実際のシナリオで発生する 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%)、アクティブ セグメントはメモリ内パイプラインに移動され、不変になります。これをメモリ内フラッシュと呼びます。取得操作は、これらのセグメントと HFiles をスキャンしてデータを取得します (後者は、HBase への通常のアクセスと同様に、ブロック キャッシュを介してアクセスされます)。

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

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

図 1 は、CompactingMemStore の構造と従来の設計を示しています。

セグメント構造:

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

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

圧縮アルゴリズム

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

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

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

結論

この記事では、Accordion のメモリ圧縮アルゴリズムの基本原理、構成、パフォーマンスの向上、およびいくつかの詳細について紹介しました。不足している点がありましたら、アドバイスを頂ければ幸いです。