Alibaba データベースカーネルの詳細な分析: HLC に基づく分散トランザクションの実装

分散トランザクションは、分散データベースで克服するのが最も難しいテクノロジーの 1 つです。分散トランザクションは、分散データベースへの一貫したデータ アクセスをサポートし、グローバルな読み取りおよび書き込みの原子性と分離性を保証し、統合された分散データベースのユーザー エクスペリエンスを提供します。

[[282776]]

この記事では、主に分散データベースにおけるクロック ソリューションと分散トランザクション管理テクノロジ ソリューションについて説明します。ハイブリッド論理クロック (HLC) は、インスタンス間のトランザクションまたはイベントの因果関係 (以前に発生したもの) を維持しながら、ローカル取得を実現し、中央クロックのパフォーマンスのボトルネックと単一点障害を回避できます。

この共有は主に次の 2 つの側面に焦点を当てています。

• クロックスキーム
• 分散トランザクション管理

1. 時計ソリューション

1. データベースにクロックが必要なのはなぜですか?

データベースの目的は、すべてのトランザクションを順序付けることです。単一のマシンの場合、トランザクションの順序付けは非常に簡単に実装できますが、分散環境ではトランザクションを順序付けるにはどうすればよいでしょうか。

データベースは、トランザクションを通じてデータ関連操作の ACID を外部に提供します。データベースによるトランザクション順序の識別によって、トランザクションの原子性と分離性が決まります。アトミック性とは、トランザクションは完了しており、発生するか発生しないかのどちらかであることを意味します。つまり、各トランザクションは独立しています。分離とは、トランザクションが互いに分離されていることを意味します。クロックには、トランザクションの順序を識別するさまざまな方法があります。たとえば、各 Oracle ログには、ログ シーケンス番号 LSN、トランザクション ID、およびタイムスタンプがあります。

現在、多くの商用およびオープンソースのデータベース製品が MVCC をサポートしています。 MVCC は複数のデータ バージョンをサポートし、同じデータの読み取りと書き込みを可能にして同時実行性を実現し、書き込みよりも読み取りが多いシナリオでパフォーマンスを大幅に向上させます。

複数のバージョンが表示される場合、それ自体がトランザクションの順序を意味します。トランザクションが開始されると、データのどのバージョンが表示可能で、どのバージョンが非表示であるかを判断する必要があるため、複数のシステム、複数のバージョン、バージョンのリサイクルなどの問題が伴います。

典型的なシナリオは、Taobao や Tmall のショッピング シナリオです。商品記録あり。ユーザーが商品を購入するたびに、商品数量の記録が差し引かれます。製品レコードのバージョンは非常に長くなるため、すべてのバージョンを保存するのは不合理です。そうしないと、全体のストレージ容量が増加し続けます。では、バージョンをどのようにリサイクルするのでしょうか?リサイクル時に、どのバージョンをリサイクルするかを決定するための順序も必要ですか?

2. 分散データベースのクロック

分散データベースのクロックとスタンドアロン データベースのクロックの違いは何ですか?

まず、スタンドアロン データベースのソートは非常に単純で、トランザクションの順序はログ シーケンス番号またはトランザクション ID で表すことができます。分散データベースでは、データベースが複数のサーバー上で実行されるため、各データベース インスタンスには独立したクロックまたはログ (LSN) があり、各ローカル クロックはグローバル順序を反映できません。

サーバー間にはクロックのオフセットがあります。理想的な状況は、分散データベースが 100 個のノードで展開され、100 個のノードのクロックが完全に同期されていることです。しかし、実際には、サーバー間のクロックの速度に差があるため、分散データベースのクロックがグローバル設定を反映できないため、コンピューター ルームでクロックの調整が必要になります。

3. 時計ソリューション

統合された中央ノードを使用するか、独立したサーバーを使用して分散クロックを生成するなど、クロック ソリューションは多数あります。

もう 1 つの解決策は論理時間であり、Lamport クロックは論理クロックです。論理クロックとは、時間を生成する中央ノードが存在せず、各ノードが独自のローカル論理時間を持つことを意味します。

たとえば、Oracle データベースが 10 個あり、各ノードに独自の LSN がある場合、ノードにトランザクションが多数あると、トランザクション ID の実行速度が速くなります。ノード上のトランザクションが少ない場合、トランザクション ID の実行速度は遅くなります。

下の図は、現在利用可能ないくつかの主流のクロック ソリューションを示しています。その中でも、TIDBは中国人民の誇りです。 TIDB は中央クロックを使用します。さらに、Postgres-XL は中央クロックでもある GTM を使用します。 Oracle は論理クロック SCN を使用します。 Cockraoch DB は Spanner をモデルにした分散データベースで、ハイブリッド論理クロックを使用します。

最も有名な Google Cloud Spanner もあります。 Spanner はハードウェアに大きく依存しており、Truetime を使用します。 Truetime は本質的には原子時計であり、2 つのサーバー間のクロック オフセットが非常に狭い範囲内であることを保証します。

4. 論理クロック

分散環境で論理クロックを実装するにはどうすればよいですか?次の図に示すように、A、B、C の 3 つのノードがあります。各ノードには独自の論理時間があります。論理時間は、0、1、2、3... のように単調に増加する自然数として簡単に理解できます。この数値は、トランザクションの開始後に 1 ずつ増加し、新しいトランザクションが開始されると再び 1 ずつ増加します。

分散環境全体では、3 つのノードは完全に独立しており、相互に関係はありません。トランザクションが複数のノードにまたがり、複数のノード間の相互作用を伴う場合、トランザクションが生成されるとローカル クロックを 1 増やす必要があります。メッセージを送信するときは、メッセージの本文を送信するとともに、ローカル時間を別のノードに送信する必要があります。メッセージ ノードを受信した後、メッセージを処理し、受信したメッセージ内の時間とローカル論理時間から値を取得し、最大値をローカル時間として設定する必要があります。

ノード A がより速く公開する場合、最初のトランザクションが完了した後、2 番目のトランザクションを実行する必要があります。このとき、ノード B と通信します。A は 1 を追加し、クロックをノード B に渡します。ノード B は 0 から 2 に直接ジャンプします。このようにして、2 つのクロック間の接続が確立されます。接続を確立することで、2 つのノード間の論理クロックが調整されます。このとき、両者の間に事前発生関係が構築され、ノード B の新しいトランザクションが開始される前にノード A のトランザクションが完了することを意味します。

分散データベースでは、2 つのトランザクションが同じノードで動作しない場合、2 つのトランザクションは無関係なトランザクションです。関連性のない事項は順序なしとみなされます。ただし、トランザクションが複数のノードにまたがる場合、複数のノード間の関係が確立され、関連トランザクションとなり、トランザクション間の因果関係の順序が構築されます。

いわゆる因果順序とは、2 つのトランザクションが発生した場合、ノード B で接続を確立するため、1 つのトランザクションはノード AB で動作し、もう 1 つのトランザクションはノード BC で動作することを意味します。トランザクションの順序は、B ノード間の関係を通じて維持されます。

純粋論理クロックは因果の一貫性と因果の順序を提供できます。では、論理クロックの最大の問題は何でしょうか?

最も極端なケースでは、ノード間の接続がまったくなくなり、2 つのノードの論理クロック間のギャップがどんどん大きくなります。このとき、2 つのノード間でクエリやバックアップを実行すると、強制的に関係を確立する必要があり、2 つのノード間のギャップが非常に大きくなります。

5. ハイブリッドクロック

マシン間の物理クロックにはオフセットがありますが、NTP キャリブレーションや Google の Truetime などのクロック サーバーがあれば、物理クロックの差は非常に小さくなります。

ハイブリッド クロックは分散クロックを 2 つの部分に分割し、上部には物理クロックが、下部には論理クロックが配置されます。クロックは一緒に配置されて、ハイブリッド論理クロックである HLC クロックを形成します。物理クロック部分と論理クロック部分の両方を備えています。物理クロックサーバー間の差はそれほど大きくないので、物理クロックのサイズを比較することができます。物理的な時計には一定の偏差があります。一定の偏差範囲内であれば、論理クロックをキャリブレーションに使用できます。

次の図はハイブリッド論理クロックの例です。メッセージを送信するときは、まず論理クロックの物理クロック部分を現在のクロックと比較する必要があります。現在の物理クロックが 4 時の場合、新しいトランザクションが生成された後、物理クロックは変更されていないため、新しいトランザクションが論理クロックに追加されます (プラス 1)。

物理時計が 4 時から 4:01 に変わった場合は、物理時計を進めます。物理クロックが進まない場合は、論理クロックを追加します。物理クロックが変更された場合は、物理クロックを上に移動し、論理クロック部分をゼロに設定します。

6. HLCと中央クロックの違い

中央クロックベースのソリューションの時間は、すべてのトランザクションをソートするために使用されるトランザクション ID によって決定されます。分散データベースでは、中央ノードを排除する必要があります。 1 つの方法は純粋な論理クロックですが、論理クロックのサイズを比較することはできません。もう 1 つのアプローチは、データベースの因果トランザクションのクラスを定義するハイブリッド論理クロック (HLC) です。

ハイブリッド論理クロックには中央ノードがなく、ローカル物理時間と論理時間を使用します。ローカルで生成されたトランザクションは順序を保持しませんが、トランザクションがノードにまたがる場合、その因果関係は順序どおりになります。

次の図に示すように、T1、T2、T3 はコミット時間を表します。 T1 は分散トランザクション、T2 はスタンドアロン トランザクション、T3 は分散トランザクションです。 T1 は分散トランザクションであるため、データベース ノードではステップ 1 がステップ 2 の前に実行されます。したがって、クロック全体では、ステップ 1 はステップ 2 よりも小さく、ステップ 1 もステップ 3 よりも小さくなります。このように、関連するトランザクションが順番に配置されます。

7. 集中型 vs. 分散型 vs. リアルタイム型

下の図に示すように、集中型クロックの利点は一目瞭然です。グローバルに一貫した時間を確保できます。

分散データベースにおけるクロックの利点は、集中タイミング サービスが不要であるため、分散化されたパフォーマンスと HA ボトルネックがないことです。分散データベースのクロックには、主に 2 つの機能があります。 1 つ目は、コンピューティングとストレージの水平拡張を実現する機能です。

さらに、分散データベースはビジネスのワークロードを異なるマシンに分割するため、単一点障害の影響が軽減されます。コア データベースを数百のコピーに分割することで、単一のポイント データベースの障害によって引き起こされるシステム全体の可用性の低下が非常に小さくなります。

これが、配信とインターネット+の組み合わせが現在非常に人気がある理由です。重要な理由の 1 つは、分散によって単一点障害がビジネスの可用性に与える影響が軽減されることです。

インターネット企業だけでなく、金融機関も流通へと移行したいと考えています。一方では、容量とスケーラビリティの問題を解決し、他方では、高可用性の問題を解決することです。

集中型アプローチの欠点は、単一障害点が存在することです。分散クロックは単一ポイントの影響を排除しますが、クロックをソートすることはできず、真の周辺一貫性は実現できません。外部一貫性とは、2 つのトランザクションごとに順序付けできることを意味します。分散クロックは、因果順序を実現するために関連するトランザクションのみをソートできます。

Google の Truetime の利点は、グローバルに一貫した時間を保証し、アプリケーション開発を簡素化することです。最初の欠点は、専用のハードウェアが必要になることです。 Truetime の原子時計をタイミングに使用すると、物理的に克服できない一定のクロック偏差が発生します。 Google Spanner の論文から、各トランザクションの送信には一定期間待機する必要があることがわかります。つまり、このクロックの偏差期間を待機する必要があるということです。

2. 分散トランザクション管理

1. 2フェーズコミット

分散トランザクション管理は、グローバルな読み取りおよび書き込みの原子性と分離性を保証します。トランザクションは 2 つのノードにまたがる必要があるため、失敗する可能性があります。 1 つのノードが成功し、他のノードが失敗した場合、表示される結果に矛盾が生じ、トランザクションのアトミック性が失われます。

もう 1 つの状況は、両方のノードで送信が成功したが、2 つのノード自体の時間が異なるため、送信時間も異なるというものです。 MVCC を使用してこのトランザクションを読み取る場合、トランザクションの半分は表示されますが、残りの半分は表示されない可能性があるため、トランザクションのアトミック性は保証されません。

トランザクションのアトミック性に関しては、関連するテクノロジ、つまり 2 フェーズ コミットはすでに非常に成熟しています。分散トランザクションの成功または失敗を確実にしたい場合は、2 フェーズ コミット テクノロジを使用できます。まず、トランザクションを準備します。すべての準備が問題なければ、コミットします。

2. その他の分散トランザクション管理技術

一般的な分散トランザクション管理テクノロジは、3 つのカテゴリに分類されます。

最初のカテゴリは、準備フェーズとコミット フェーズを含む 2 フェーズ送信テクノロジです。

2 番目のカテゴリは MVOCC に基づいています。 FOUNDATION DB は、OCC (楽観的同時実行制御) とも呼ばれる MVOCC を使用する Apple のオープンソース分散データベースです。 OCC とは、トランザクションが送信されるときに競合があるかどうかを確認し、競合に基づいて競合検出アルゴリズムと重み付けアルゴリズムを設定し、最終的にどのトランザクションを破棄または送信するかを選択することを意味します。ロックについては、事前および更新時にロックし、コミット時に競合をチェックします。競合が深刻でない場合は、ロックのオーバーヘッドがないため、全体的なスループットは非常に高くなります。重大な競合が発生した場合、多数の中止トランザクションが繰り返しロールバックされます。

3 番目のカテゴリのテクノロジは、FAUNA テクノロジなどの決定論的なトランザクションを主に対象としています。

アメリカのある教授が決定論的トランザクションを提唱し、決定論的トランザクションモデルに基づいた会社を設立し、分散データベース（FAUNA）を作成しました。決定論的トランザクションとは、トランザクションが対話型ではなく完全であることを意味します。

たとえば、Taobao のようなインターネット企業は非決定論的なトランザクションを扱っています。非決定論的トランザクションには、開始トランザクション、選択トランザクションなどのみが含まれます。各操作は対話型です。つまり、APP はデータベースと対話する必要があります。

データベースの観点から見ると、データベースは次のステートメントを予測することはできません。そのようなことは非決定論的です。決定論的トランザクションとは、トランザクションのすべてのロジックが一度に書き込まれ、データベースに送信されるトランザクションです。データベースはトランザクションを受信すると、トランザクションがどのテーブルを操作する必要があるか、どのレコードを読み取るか、どの操作を実行するかを認識します。データベースの観点から見ると、トランザクションは完全に決定論的です。決定論的なトランザクションを作成したら、これらのトランザクションを事前に並べ替えることができます。 2 つのトランザクションが同じレコードに対して実行される場合、それらは順番に配置されます。同じレコードに対して操作が行われない場合は、同時に送信されます。

この方法により、後で送信するときにロックや競合検出を行う必要がなくなります。しかし、その要件では、トランザクションは対話型にはできません。

3. HLCと2相コミット

ハイブリッド論理クロック (HLC) の形式は次のとおりです。 64 バイトある場合は、互換性を確保するためにまず 5 バイトを予約します。システム設計を行う際には、通常、何らかの問題が発生したときに何も利用できない場合に備えて、いくつかのバイトを予約する必要があります。中央の 43 バイトは物理クロック用に予約されています。次の 16 バイトは論理クロックとして使用されます。クロックがミリ秒単位の精度である場合、43 バイトの物理クロックは 279 年を意味します。つまり、データベースはハングアップすることなく 279 年間継続的に実行されることになりますが、これは通常あり得ないことです。

物理時計が毎日のレベルに達し、1 日に 1 桁しか変更できない場合、物理時計は意味を失います。 16 バイトは 65536 なので、1 ミリ秒で 65536 件のトランザクションを開始できることになります。通常、開始時と終了時に 2 つのクロックが消費されます。これを 2 で割ると、1 ミリ秒で 30,000 件を超えるトランザクションを処理でき、1 つのノードでは 1 秒間に 3,000 万件を超えるトランザクションを処理できます。

4. HLCクロックオフセット問題

HLC は物理クロックを持ち、異なるノード間のクロックの差を表示できるため、トランザクション スループットに関係します。クロックスキューが発生した場合はどうなりますか?

下の図は簡単な式を示しています。偏差がない場合、ノードは理論的には 3000 万 TPS を達成できますが、これはもちろんエンジニアリング上不可能です。

2 つのノード クロック間のオフセットが 5 ミリ秒の場合、論理クロックは 5 ミリ秒以内でしかそれを補うことができません。元の 60,000 論理クロックが 1 ミリ秒以内に完了できた場合、現在は 5 ミリ秒かかるため、トランザクション全体のスループットが 600 万減少します。したがって、クロック スキューにより、ピーク TPS が大幅に低下します。

下の図はいくつかの解決策を示しています。比較的簡単な方法は、最大クロック オフセットの設定を許可することです。コンピュータ ルームまたはクラスター全体の 2 つのノード間の最大オフセットが 100 ミリ秒を超えると、異常なノードはクリアされます。現在、すべてのコンピュータ ルームには NTP タイミング サービスがあるため、このような大きなクロック オフセットが発生する可能性は非常に低くなります。もう 1 つの方法は、異常なノードをクリアするのではなく、論理クロックを物理クロック部分にオーバーフローさせて論理クロックを大きくし、現在のクロック内でより多くのトランザクションが発生するようにすることです。