分散ストレージの7つの問題

モチベーション

なぜ7つの側面の問題なのでしょうか? 7 辺は 6 辺より 1 辺多く、8 辺より 1 辺少ないだけですが、これは意図的なものではありません。ストレージ分野における多くの知識は、レプリケーション、ストレージエンジン、トランザクション、分析、マルチコア、コンピューティング、コンパイルの 7 つの側面に要約できます。

分散ストレージ

分散ストレージとは何ですか?オブジェクト、ブロック、ファイル、KV、ログ、OLAP、OLTP のいずれのストレージシステムでも、管理するデータのパーティショニングとレプリケーションを実行する場合、そのアプローチが正しいかどうかに関係なく、実際には分散ストレージとして分類できます。分散ストレージとは、複数のマシン規模に対応するパーティショニングと、災害復旧およびフォールトトレランスに対応するレプリケーションを意味します。

[[399749]]

1. コピー

レプリケーションは、可用性、スケーラビリティ、高パフォーマンスの鍵となります。災害復旧には、データの冗長ストレージが必要です。高可用性を実現するには、サービスにホットスタンバイが必要です。災害復旧機能のないシステムは、実稼働環境で使用することが困難です。メタデータとデータのメンテナンスにはレプリケーションが必要ですが、これは転送することはできますが削除することはできません。レプリケーションでは複数のコピー間の一貫性の問題が発生し、一貫性の保証にはさまざまなソフトウェアおよびハードウェアの障害や誤操作を考慮する必要があります。コンセンサスアルゴリズムとレプリケーションログは、レプリケーションの問題を解決するための中核であり、具体的には次のことが関係します。

瑕疵検査、賃貸借契約書
プライマリ選出アルゴリズム、プライマリ一意性不変、ネットワーク分離、スプリットブレイン、デュアルマスター、ビザンチン障害、フェイルファースト/フェイルストップ、フェイルオーバー。
ログレプリケーション、RSM;
メンバーシップの変更、または構成の変更、ホストのオンラインおよびオフライン管理、容量の拡張と縮小。
データ複製、データ再バランス、データ回復。
レプリカ配置ロジックとレプリカルーティングロジック。
プライマリとバックアップを区別するにはどうすればよいですか?
外部一貫性、線形化可能性。
パイプライン、ファンアウト、プライマリバックアップ、クォーラムベース、ゴシップ。
分散ログ、アクティブ/スタンバイアーキテクチャ、アクティブ/アクティブアーキテクチャ。
…

2. ストレージエンジン

ここでのエンジンは、ローカルの永続ストレージエンジンを指します。永続ストレージエンジンでは、CPU およびメモリシステムと永続デバイス間の速度と帯域幅の違いを考慮する必要があります。これは 1-3-5 にまとめることができます。

1-3-5

1 は fsync の呼び出しと fsync と同じステータスを持つ関数の呼び出しを指します。通話回数、通話頻度、通話に適用されるデータ量など。デバイスの帯域幅と使用率は適切ですか? fsync 呼び出しをより多くの IO 時間とスループットに分散するにはどうすればよいでしょうか?

3は読み取り/書き込み/スペースの拡大を指します。 1 つを犠牲にして他の 2 つを維持するというトレードオフをどのように行うのでしょうか?

5 は、WAL の 5 つの LSN、つまり準備ポイント、コミットポイント、適用ポイント、チェックポイント、およびプルーニングポイントを表します。

準備ポイントとコミットポイント間のデータにはグループコミットが必要です。
適用ポイントとコミットポイント間のコミットされたデータは、メモリ内のデータ構造に適用され、読み取り可能になる必要があります。
メモリデータ構造は、特定のスケジューリング戦略を使用して永続デバイスにアーカイブする必要があります。チェックポイントはアーカイブポイントです。
クラッシュから回復するには、最新のチェックポイントからコミットポイントまで復元する必要があります。
チェックポイントが完了すると、そのチェックポイントまでのログは切り捨てられる可能性があります。したがって、チェックポイントより大きくないポイント、つまりプルーニングポイントが存在します。その時点までのログと古いディスク上のイメージは安全に削除できます。
したがって、これら 5 つのポイントには常に制約があり、ポイント間には完全な順序関係があります。

データ構造とアルゴリズム

メモリとディスクデータの管理には、豊富なデータ構造とアルゴリズムを使用する必要があります。さらに、データのサイズを縮小するために使用される解凍およびエンコードとデコードのアルゴリズムも非常に興味深いものです。

3. 取引

トランザクションは ACID を参照します。多くのストレージシステムでは、実際にトランザクションを分析のベースラインとして使用して、システムが原子性、一貫性、分離性、および永続性に関してどの程度進歩したかを確認できます。実際、トランザクションは正確性と同時実行性の間の妥協を反映しています。トランザクションのユーザーとして、理論上は (必ずしも実際にはそうではありません)、ストレージシステムに同時にアクセスするときに誤った結果が生じることを心配する必要はありません。そのような懸念が存在する場合、それはトランザクション処理において同時実行性を優先して正確性がいくらか犠牲にされ、エラー処理と選択権がユーザーに委ねられているためであるに違いありません。ユーザーは、フェンスコードを挿入し、クライアントコードでフォールトトレランス処理を実行するために余分な時間を費やす必要があります。

ストレージエンジン部分は、実際には多かれ少なかれトランザクション処理コミットプロトコルに関係しており、主にトランザクション A と D を解決します。トランザクション処理の中核となるのは同時実行制御プロトコルです。同時実行制御は主に以下の問題を解決します。

2 つの同時トランザクションはどのように競合するのでしょうか (読み取り-書き込み、書き込み-読み取り、書き込み-書き込み)?競合が検出されたときにロックして待機するか、中止しますか?
コミットされたトランザクションがデータベースに与える影響を、現在の未処理トランザクションの読み取り操作で確認するにはどうすればよいでしょうか。

これら 2 つの問題の本質は、分離と一貫性です。競合するトランザクションは同期され、以前にコミットされたトランザクションは後続の未処理のトランザクションに表示されます。

理想的な正確性とは、競合の有無にかかわらず、すべてのトランザクションが時間的に重複することなく 1 つずつ連続して実行されることです。理想的な同時実行性とは、すべてのトランザクションに競合がなく、最高の並列度で同時に実行できることです。しかし現実には、紛争は常に存在します。競合を解決するということは、並列実行の特定の段階で同期ポイントを挿入することを意味し、競合があるかどうかを判断して調停する必要があります。

競合待機はロックベースの CC プロトコルです。競合中止再試行は、タイムスタンプ順序付け CC プロトコルです。前者はいわゆる悲観的な出来事であり、後者は楽観的な出来事である。トランザクション処理については、Jim Gray の本や有名な教科書で非常にわかりやすく説明されています。ここでは、楽観的トランザクションの競合チェックのシンプルで直感的な理解についてのみ説明します。2 つのトランザクションを順序付ける方法は 2 つあり、1 つは TSO によって割り当てられたタイムスタンプによって決定される順序であり、もう 1 つはデータ依存関係 (WAW、RAW、WAR) によって決定される順序です。これら 2 つの順序によってトランザクション間の部分的な順序関係が破壊されると、2 つのトランザクションは必然的に競合し、一方のトランザクションを中止して再試行することを選択できます。

順序付けは重要な問題です。たとえば、タイムスタンプの割り当ては、楽観的トランザクションの開始とコミットで使用され、悲観的トランザクションのタイムスタンプベースのデッドロック防止でもタイムスタンプの割り当てが使用されます。

ストレージシステム自体をパーティション分割すると、単一のパーティションのトランザクション処理をローカルストレージエンジンに転送できるようになります。ただし、操作に複数のパーティションの変更が含まれる場合は、パーティション間のトランザクション処理機能を考慮する必要があります。実際のところ、分散トランザクションの明確な定義はありませんが、「across」の意味が含まれています。コミットプロトコルか CC プロトコルかは、分散ストレージシステムの実装か、単一マシントランザクションの実装かによって異なります。 2PC と 3PC は多くの文献で繰り返し使用されていますが、コミットプロトコルを指す場合もあれば、CC プロトコルを指す場合もあり、コミットプロトコルと CC プロトコルのハイブリッドを指す場合もあります。

トランザクションは、ストレージシステムの動作を明確に定義し、保証します。トランザクションの観点から、ロックの粒度、マルチバージョン管理、グローバル同期ポイント、書き込みが遅すぎる問題への対処方法など、システムの実装を推測できます。

4. 分析

分析処理には多くのことが含まれます。ある観点から見ると、SQL 言語をどのように実装するかということです。別の観点から見ると、SQL によって駆動される分散システムをどのように実装するかということです。テキスト SQL ステートメントは、単語の分割、構文分析、カタログアクセスとセマンティック分析、およびリレーショナル代数の同等の変更を経て、論理クエリプランを形成します。次に、データ分布、オペレータ特性、コンピューティングリソースの状態に基づいて物理的な実行プランが生成されます。

1 つの SQL ステートメントは複数の論理実行プランに対応でき、1 つの論理実行プランは複数の物理実行プランに対応できます。たとえば、結合の順序や結合演算子の実装などです。フィルタリング時の述語の順序、および述語がシンクされているかどうか。関係代数の演算子には複数の異なる実装アルゴリズムがあり、複数の関係演算子は計算順序によって実行効率が異なります。事前の知識に基づいて、ヒューリスティックな戦略を使用します。または、データ分布に関する統計情報を使用し、コスト見積モデルを採用する。または、既存の実行経験に基づいて、最適または次善の実行プランに適応的に調整します。

コンピューティング層では、並列処理、パイプライン処理、バッチ処理という 3 つの主要な最適化戦略を通じて処理が高速化されます。例えば、パーティショニングによりデータを複数のパーティションに分割して複数のマシンに配置し、MPP方式により複数のマシンで並列処理を行います。計算プロセスは、関係を入力として受け取り、実行ツリーのリーフノードを通過し、ルートノードに収束するものと見ることができます。各ノードの対応するオペレータの特定のアルゴリズムが入力データを処理して出力します。計算モデルの観点からは、いくつかの状況が考えられます。

一度にタプル: イテレータモードを使用します。現在のイテレータが get_next を実行すると、子演算子に対応するイテレータの get_next を呼び出して計算に必要な入力タプルを取得し、計算コードを実行して出力タプルを生成し、親演算子を発行します。
完全なマテリアライゼーション: 各演算子はすべての入力データを受け取り、出力結果を計算し、次の演算子に渡して計算します。このアプローチはバッチ処理に似ています。
ベクトル化された実行: データは列ごとにメモリに格納され、配列として表されます。配列のサイズは、L1 データキャッシュに収まるように選択され、実行ツリー内の各演算子は、タイトな for ループを実行して、データ配列を配列ごとに処理します。これにより、完全な実現化のための過剰なリソース要求と、一度に 1 つのタプルを処理するオーバーヘッドが回避されます。また、キャッシュフレンドリーになり、誤った無効化が減り、投機的なキャッシュの欠落が改善されます。同時に、シンプルでタイトな for ループにより、コンパイラはそれを効率的な実行命令にコンパイルし、同時に CPU の命令パイプラインをより適切に満たし、CPU の複数発行機能を最大限に活用して、単純な命令の処理を高速化できます。

ストレージ層では、データは列形式で保存されるため、優れたエンコード効率を実現し、読み取り増幅とスペース増幅を削減し、永続ストレージにアクセスするための帯域幅を効率的に利用できます。 CPU とメモリの帯域幅の増加率は、永続ストレージの帯域幅の増加率と比較して大きな違いが見られます。 CPU の計算がディスク帯域幅と交換され、データ処理能力が向上します。

列ストレージ、ベクトル化実行エンジン、および MPP は、最新の分析データベースの重要なテクノロジです。

5. マルチコア

プログラミング実装の観点から見ると、マルチコアスケール、CC プロトコル、コンセンサスアルゴリズムは、コンピューターにおける比較的困難で、純粋に自然な問題です。データベース技術に深く関わっていないとしても、これら 3 つの問題には非常に関心があるはずです。データベース技術に惹かれ、この分野に参加することは、多かれ少なかれこれら 3 つの問題に関係しています。

マルチコアはなぜそれほど重要なのでしょうか?

ムーアの法則を前提とすると、パワーウォールの制限がなければ世界はどうなるでしょうか?当然、古いコードを変更する必要はありません。シングルコアトランジスタの数を増やす限り、古いコードは自然に改善されます。電力の壁にぶつかったとき、計算を高速化するにはコアを追加する必要があることに気付きました。ここで問題となるのは、私たちのコードはマルチスレッド実行用に記述されているかどうかです。では、コア数が増えてワーカースレッドプールのサイズが変更された場合、コア数の増加に伴って古いコードの計算能力も向上し続けるのでしょうか?明らかにそうではありません。マルチコアのスケールはアムダールの法則によって制約されるからです。コードのシリアル実行部分が 1% を占める場合、256 コアマシンでは最大 72 倍までしか高速化できません。 10%だと最大10倍までしか高速化できません。明らかに、スレッドプールのサイズを変更するのは良い考えではありません。コード内の競合を減らすことが重要です。

この場合、コア数に応じて高速化を図りたい場合、競合を減らすために、多くのアルゴリズム、データ構造、CC プロトコル、および分析と処理の演算子実装を個別に再構築する必要があることがわかります。再構築方法は、ロックフリーアルゴリズムを使用することです。しかし、これが真実のすべてではありません。マルチコアスケールに直面すると、実際には新しい分散システムに直面することになります。この新しい分散システムでは、インターコネクトをネットワークとして使用し、コアをコンピューティングリソースとして使用し、メモリシステムの遅延のシールドも考慮する必要があります。元の分散システムでは、各マシンに独自の作業を実行させ、データのバランスをとる傾向があるため、コンピューティングリソースを最大限に活用できます。同じ問題がマルチコアプログラミングにも当てはまります。つまり、元のタスクを複数のサブタスクに均等に分割して、複数のサブタスクが並行して進行し、同時に終了できるようにする方法です。明らかに、不均衡なデータ分割やコア間通信などの要因により、高速コアが低速コアに等しくなるという問題が発生します。同時に、複数のコアを処理する場合、各コアは単独で動作するのではなく、共通のタスクを完了するために連携する傾向があります。この場合、タスクをサブタスクに均等に分割するスケジューリングコード、共有データ構造へのアクセスコード、および複数のコア間の待機が同期ポイント、つまり競合になります。つまり、どうすれば争いを減らすことができるのでしょうか?

実際には、ロックフリーアルゴリズムの正確性をどのように記述し、検証するのでしょうか?他の 2 つの問題のアイデアを比較することで解決策が得られるかもしれません。たとえば、コンセンサスアルゴリズムでは、不変記述アルゴリズムが使用されます。 CC プロトコルでは、異常攻撃アルゴリズムが使用されます。おそらく、これら 2 つの方法を組み合わせることで、ロックフリーアルゴリズムの研究に役立つでしょう。

マルチコアのスケーリングは非常に困難ですが、これにより、優位性のある従来のデータベースと新しいデータベースの参入者が同じスタートラインからスタートし、ケースバイケースのコード最適化でどちらが優れたパフォーマンスを発揮するかを競うことができます。

また、異種コンピューティングを使用してデータ処理を高速化することを検討しているチームも多く、これにも多くのチャンスが存在します。しかし、洗練された高品質のコードを作成するためにプログラマーの頭脳に頼るのは、時間がかかり、手間がかかります。おそらく、この種の問題は、コンパイラのバックエンドテクノロジを通じて完全に解決されるはずです。今できないからといって、将来できないというわけではありません。その時が来れば、誰かが先人たちが書いた複雑なコードを見るとき、それは今日の私たちが粘土板や穴の開いたカードを見るのと同じことになるでしょう。

6. 計算

コンピューティングでは主に実行エンジンについて説明します。実行エンジンは非常に大きな範囲です。現在、ロードマップは確立されていますが、ベースラインが不足しています。両方とも準備が整い次第、追加されます。

7. コンパイル

コンパイルはデータベースに全般的な影響を及ぼします。たとえば、コンピューティングエンジンはベクトル化に加えてコンパイルテクノロジを使用してパフォーマンスを最適化できます。データベースにおけるケースバイケースのパフォーマンス最適化には、多くの場合、アーキテクチャに関する詳細な調査が必要であり、異種コンピューティングの高速化処理にもコンパイル技術の使用が必要です。ストリーミングおよびバッチ DSL スクリプトは、計算、UDF 拡張などに既存の SQL 実行エンジンを使用します。動機は明確ですが、ロードマップとベースラインはまだ確立されていません。準備が整い次第追加されます。

<<: インタビュー: 仮想マシンスタックに関する 5 つの質問それを聞いて嬉しかったです。

>>: エッジコンピューティングとIoTの共生関係