パート01 LSMツリーモデルMySQL、SQL Server、Oracle などの一般的なリレーショナル データベースでは、データ ストレージとインデックス作成の基本構造として B+ ツリーを使用しています。非リーフ ノードにはインデックス データのみが格納され、リーフ ノードにはすべてのデータと隣接ノードへのポインタが格納されます。これにより、読み取り増幅と領域増幅が比較的低く、効率的な範囲クエリと安定した検索パフォーマンスが実現します。ただし、B+ ツリーは、ディスク データ ページを読み取り/書き込みの最小単位として使用し、ランダム ディスク読み取り/書き込み操作を採用しています。大量のデータが挿入されると、リーフ ノードは継続的に分割され、最終的には論理的に連続したデータが異なる物理ディスク ブロックの場所に格納されることになります。これにより、大量のランダム読み取り I/O が生成され、範囲クエリの効率と読み取り/書き込み増幅が低下します。ディスクのランダム読み取り/書き込みが B+ ツリーのボトルネックとなるため、B+ ツリーは読み取りが多く書き込みが少ないシナリオに適しています。 BigTableより古いファイル構成手法であるログ構造化マージツリー（LSMR）は、Patrick O'Neilらによる1996年の論文にまで遡ります。この手法は、独自のデータ構成手法（ログ構造化）と、バックグラウンドでの継続的なマージによるメンテナンスの必要性にちなんで名付けられました。BigTableの登場後、LSMRはHBase、Cassandra、ClickHouse、LevelDB、RocksDB、TiDBといった書き込み集中型のキーバリューデータベースやストレージエンジンで高く評価され、広く利用されるようになりました。 LSMツリーは、実際には特定のデータ構造ではなく、シーケンシャルな追加、マルチレベルデータ構造、定期的なマージといった特徴を持つデータ処理ロジックです。離散的なランダム書き込みをバッチシーケンシャル書き込みに変換することで、ディスクシーク時間を短縮し、書き込みパフォーマンスを向上させるため、書き込み集中型のアプリケーションに適しています。Patrick O'Neilの論文では、マルチレベルログツリーマージ構造の構造が紹介されています。 写真 C0ツリーはメモリ内に存在し、C1からCkツリーはディスク上に存在します。Ckツリーは順序付けられたツリー構造です。データの書き込みはメモリ内のC0ツリーから開始され、ディスク上のより大きなCkツリーに継続的にマージされます。メモリの読み取りと書き込みの速度は外部ストレージよりもはるかに速いため、データの書き込み効率は非常に高くなります。さらに、データはメモリからディスクにフラッシュされる際に事前にソートされます。つまり、LSMツリーはランダムな書き込み操作をシーケンシャルな書き込み操作に変換し、書き込みパフォーマンスを大幅に向上させます。ただし、読み取りにはメモリとディスク上のデータをマージする必要があるため、読み取りパフォーマンスが多少犠牲になります。 パート02 HBaseシステムアーキテクチャHBaseはLSMベースのモデルを用いて分散列指向データベースを構築します。HBaseはマスター/スレーブアーキテクチャを採用し、クラスタを構築します。Hadoopエコシステムに属しています。データはHDFSに保存されます。システム全体のアーキテクチャは次の図に示されています。 写真 RegionServer は、1 つ (または複数) の HLog、1 つの BlockCache、および複数の Region で構成されます。 HLog はデータ書き込みの信頼性を確保するために使用されます。 BlockCache はデータ ブロックをメモリにキャッシュして、データの読み取りパフォーマンスを向上します。 • リージョンとは、HBase 内のテーブルのデータシャードです。通常、RegionServer は複数のリージョンのデータの読み書きを担当します。 写真 テーブルは複数のリージョンに水平に分割され、各リージョンはそれぞれの領域内でデータの読み取りと書き込みを行います。リージョンは複数のストアで構成され、各ストアには対応する列ファミリーのデータが格納されます。例えば、テーブルに2つの列ファミリーがある場合、そのテーブルのすべてのリージョンには2つのストアが含まれます。各ストアには、1つのMemStoreと複数のHFileが含まれます。ユーザーデータが書き込まれると、対応する列ファミリーのデータが適切なMemStoreに書き込まれます。書き込まれたデータのメモリサイズが設定されたしきい値を超えると、システムはMemStoreのデータをディスクに書き込み、HFileファイルを作成します。HFileはHDFSに保存され、ユーザーが簡単にデータを取得できるようにカスタマイズされたデータストレージファイル形式です。 パート03 MemStoreの実装MemStoreはLSMにおけるC0ツリーの実装です。書き込み可能なセグメントと1つ以上の書き込み不可能なセグメントで構成されます。すべてのデータ書き込み操作は、まずログHLogに書き込まれ、次にMemStoreに順番に書き込まれます。MemStoreのデータサイズがしきい値を超えると、データは一括してディスクに書き込まれ、新しいStoreFile（HFile）が生成されます。最後に、複数のStoreFile（HFile）が圧縮されます。 • MemStoreLAB（Local Allocation Buffer）を使用することで、KeyValueデータの保存にオフヒープの固定メモリセグメントChunkが使用されます。Regionがフラッシュを実行すると、KeyValueが占有する断片化されたメモリではなく、Chunkが占有する連続したメモリが解放されるため、メモリの断片化の問題が効果的に解決されます。 • すべてのKeyValueデータを格納するにはCellSetを使用してください。CellSetの中核はConcurrentSkipListMapです。データはキー値に従って順番に格納されます。さらに、高並列書き込み時のパフォーマンスはConcurrentHashMapよりもはるかに優れています。スキップリストを使用することで、効率的な挿入と高い並列性を実現します。 写真 HBaseV2.x以降では、書き込みメモリを統合したCompactingMemStoreが使用されます。MemStore内のアクティブなセグメントデータは、まず不変セグメントにフラッシュされます。複数の不変セグメントをメモリ内で圧縮することも可能です。一定のしきい値に達した場合にのみ、メモリ内のデータがHDFS内のHFileファイルに永続化されます。 パート04 HFileファイル構造HBase は列ファミリーストレージを使用し、列ファミリーのデータがまとめて保存されます。列ファミリーストレージは、行ベースストレージと列ベースストレージの中間に位置します。 列ファミリが 1 つだけあるテーブルは、行ベースのストレージと同等です。 • それぞれが 1 つの列のみを持つ多数の列ファミリを持つテーブルは、行を格納することと同じです。 ファイル構造について説明する前に、データの保存形式を見てみましょう。キーと値がHBaseに入力されると、新しいレコードが作成されます。 (テーブル、RowKey、ファミリ、修飾子、タイムスタンプ) -> 値 このレコードは、ディスク上の次の保存形式に対応するバイト ストリームとして保存されます。 写真 HBase 以降、HFile は 3 つのバージョンを経ており、主な変更点は次のとおりです。 HBase 0.92より前のバージョンで使用されていたHFile V1は、BigtableのSSTableとHadoopのTFileを参照するシンプルな構造でした。リージョンが開かれると、すべてのデータブロックインデックスデータを読み込む必要がありました。さらに、最初の読み取りでは、すべてのブルームフィルタデータをメモリに読み込む必要がありました。HFile内のブルームフィルタのサイズは数百MBに達することもあり、リージョンサーバーは起動時に数GBのデータブロックインデックスデータを読み込む必要がある場合もありました。 HFile V2は階層型インデックスを使用して、データブロックのインデックスデータとブルームフィルタデータをオンデマンドで読み取ります。これにより、リージョンオープン時または読み取りフェーズで大量のデータが一度に取り込まれるのを防ぎ、レイテンシを効果的に削減します。ロードオンオープンが完了すると、リージョンサーバーの起動が完了したとみなされるため、起動時間が短縮されます。 バージョン 0.98 から導入された HFile V3 は、主にタグ機能のサポートを目的としており、HFile V2 と比較してわずかな変更のみが行われています。 以下のテキストでは、主に HFile V2 の設計に焦点を当てます。 写真 データ ブロック インデックスとブルーム フィルターはどちらも階層型インデックス設計を採用しており、最大 3 レベルのインデックスをサポートします。 最上位層はルートデータインデックスで、ロードオンオープンセクションと呼ばれる領域に配置されています。これは、領域オープン時にメモリにロードされ、ルートデータインデックスから中間ブロックインデックスまでのインデックスが作成されます。 • 中間層は中間インデックス ブロックであり、中間ブロック インデックスからリーフ インデックス ブロックまでのインデックスを作成します。 最下位レベルはリーフ インデックス ブロックであり、データ ブロックを直接インデックスできます。 実際のシナリオでは、中間ブロックインデックスは実質的に存在しません。そのため、インデックスロジックは簡素化され、ルートデータインデックスからリーフインデックスブロックを直接インデックスし、リーフインデックスブロックから対応するデータブロックを見つけるという形になります。 パート05 HFileの圧縮とマージHBaseのコンパクションには、マイナーコンパクションとメジャーコンパクションの2種類があります。これらはそれぞれ、スモールマージとラージマージと呼ばれることもあります。これらのコンパクションは、短期間でI/O消費量を削減し、比較的安定した読み取りパフォーマンスを実現します。以下に簡略化した図を示します。 写真 マイナーコンパクションでは、隣接する複数の小さなHFileを選択し、それらを1つの大きなHFileにマージします。これによりI/Oが最小限に抑えられ、ファイル数が削減されるため、読み取りパフォーマンスが向上し、頻繁に実行するのに適したものになります。ただし、ローカルデータのみがマージされるため、マージ処理中にグローバルに削除されたデータを完全に削除することはできません。デフォルトでは、マイナーコンパクションは選択したHFileからTTL（Time-to-Live）期限切れのデータを削除します。 メジャーコンパクションとは、ストア内のすべてのHFileを単一のHFileにマージすることを指します。このプロセスでは、削除されたデータ（削除タグが付けられたデータ）、Time-To-Live（TTL）が期限切れになったデータ、および設定されたバージョン番号を超えたデータという3種類の不要なデータがクリーンアップされます。さらに、メジャーコンパクションは通常、長時間かかり、システムリソースを大量に消費し、上位レベルのビジネスロジックに大きな影響を与えます。そのため、本番環境では、メジャーコンパクションの自動トリガーは通常無効になっており、代わりにオフピーク時に手動でトリガーされます。 パート06の要約HBaseはLSMツリーモデルをベースとし、MemStoreとStoreFileを使用してメモリ内およびディスク上のログをマージします。シーケンシャルアペンドと定期的なマージを採用することで書き込みパフォーマンスを向上させ、大規模なデータストレージをサポートします。コンパクションにより、I/Oオーバーヘッドを最小限に抑えながら、比較的安定した読み取りパフォーマンスを実現します。実際のアプリケーションでは、適切なマージ戦略を設定し、読み取り増幅、書き込み増幅、およびスペース増幅のバランスを慎重に考慮する必要があります。 |
