分散データベースシステムが直面する問題と課題

[[431029]]

分散データベース システムは論理的には完全なシステムとみなすことができ、ユーザーはスタンドアロン データベース システムを使用しているかのように使用します。しかし、物理的な観点から見ると、物理的に分散した複数のノードを含むネットワーク システムであり、ノードはネットワークを介して接続され、ネットワーク プロトコルを介してデータを交換し合います。

分散データ システムでは、ネットワーク障害やノード障害に対処する必要があります。ネットワーク障害はパーティションイベント（CAP）に直接つながる可能性がある

原則の P、つまり、ネットワーク障害が発生し、ネットワークが複数のサブパートに分割されると、システムの可用性に影響が出ます。ノード障害により単一点障害が発生する可能性があります。つまり、データが単一のコピーである場合、ノード障害により一部のデータが直接アクセス不能になります。単一障害点を回避するには、データのコピーを複数作成してシステムの可用性を大幅に向上させる必要があります。ノード障害によってパーティション イベントが発生する可能性もあります。

上記の問題に加えて、分散データベース システムでは不整合の問題も発生する可能性があります。たとえば、データ項目が更新された後に読み取り操作が行われると、古い読み取りの問題が発生します。このとき、データ項目の最新の値が読み取られるべきですが、代わりに古い値が読み取られます。この問題の原因は、分散データベース システムに統一されたクロックがないため、データが逆の順序で読み取られることです。この状況はスタンドアロン システムでは発生しません。ここで言及した不整合現象、および類似の不整合現象は、ここではデータの読み取り順序がデータの生成順序と一致しない、分散不整合と呼ばれます。

分散不整合の問題を解決するために、多くの学者が広範な研究を経て、線形化可能性、順次整合性、因果整合性、Google Spanner の外部整合性など、さまざまな分散整合性の概念を提案してきました。

分散データベース システムでは、分散不整合の問題を解決して、オブザーバーが一貫性要件を満たすデータを読み取って、データ間のロジックが常に正しいことを保証できるようにする必要があります。このセクションの残りの部分では、この問題について説明します。まず、一般的な分散システムが直面する問題について説明し、次にデータの異常によって生じる一貫性の問題について説明し、最後に分散データベースに関連するその他の問題について説明します。

分散データベースシステムが直面する問題

スタンドアロン データベース システムでは、トランザクションの失敗に対処し、トランザクションを管理するために、トランザクションのロールバックを実装することを目的として、UNDO ログ、ロールバック セグメントなどの手段が提供されます。システム障害に対処するために、トランザクションの前に永続的なストレージを実行することを目的として、WAL テクノロジがログに使用されます。メディア障害に対応するため、論理バックアップ、物理バックアップなどの手段が提供され、データレベル、ログレベル、物理データブロックレベルでの冗長データストレージの実現を目指しています。

上記の問題に加えて、分散データベース システムは、スタンドアロン データベース システムと比較して、より多くの課題に直面します。これらの課題は、分散データベース システムのアーキテクチャに起因します。分散データベース システムはスタンドアロン データベース システムとは異なるため、技術レベルで違いがあります。

1. 建築上の異常

アーキテクチャ異常とは、データベース アーキテクチャによって発生するデータ異常を指します。厳密に言えば、これらはデータベース システムのデータ異常の分野には属しません。ユーザーから見ると、トランザクションは常に実行されていますが、データの読み取りや書き込みを行う際には、上記と同様の順序の問題やデータの異常が発生します。この本では、このような異常を総称して建築異常と呼んでいます。アーキテクチャ例外は分散アーキテクチャに関連しており、これには 1 つのアクティブと 1 つのスタンバイのアーキテクチャ、1 つのアクティブと複数のスタンバイのアーキテクチャ、および複数のアクティブと複数のスタンバイのアーキテクチャが含まれます。分散アーキテクチャでは、フロントエンドにプロキシに似たコンポーネントが含まれ、ユーザーに透過的な高可用性サービスを提供する場合があります。プロキシ コンポーネントは、バックエンドでの複数の単一マシン システム障害を遮断します。したがって、ユーザーの観点からは、分散アーキテクチャ上のすべての操作は 1 つのトランザクションで実行され、アーキテクチャによって発生する例外もデータ例外になります。

一貫性のない読み取りデータを引き起こす可能性がある既知のアーキテクチャ上の異常については、以下で説明します。説明のために、MySQL のマスター/スレーブ アーキテクチャを例に挙げます (他のデータベースの同様のアーキテクチャにも同様のリスクが存在します)。このような矛盾はこのようにして生じます。 MySQL はマスタースレーブアーキテクチャをサポートしています。トランザクション T がマスター上で実行されると仮定します。このとき、「スコア＞90」という条件に従ってクエリが実行されます。条件を満たすトランザクションが存在しないことが判明しました。したがって、Binlog ファイルへのデータの書き込みは成功しており、95 (トランザクション コミット) であると想定されます。その後、レプリケーション プロセス中にマシンがクラッシュし、レプリケーションが失敗します。マスターが再起動されると、データ 95 が直接コミットされ、その後、マスターはデータ 95 をスレーブに非同期的にコピーします。ただし、この時点で、元のスレーブがマスターに切り替えてサービスを提供し始めている可能性があります。たとえば、新しいトランザクションはデータ 98 を書き込みますが、元のマスター上のデータ 95 は新しいマスターにコピーされないため、2 つの MySQL ホスト間でデータの不整合が発生します。

プライマリおよびバックアップ MySQL サービスの前にプロキシ サーバーが存在する場合、ユーザーの視点からバックグラウンドのプライマリおよびバックアップ サービスが保護されます。すると、ユーザーは「サービスを提供する MySQL は 1 つだけ」と考えるため、95% のデータ損失はユーザーにとって受け入れられません。

もう一つの状況があります。元のマスターがクラッシュした後、プロキシ サーバーがユーザーのトランザクション T を終了しない場合は、トランザクション T を元のスタンバイ マシンに接続し、元のスタンバイ マシンを新しいマスターに変更します。このとき、新しいマスターに対して 2 つのトランザクションが発生します。 1 つは、特定の WHERE 条件の下で 98 を書き込む新しいトランザクション T1 であり、もう 1 つは実行を継続する元のトランザクション T です。この時点で元のトランザクション T が再度読み取り操作を開始すると (論理的にはまだ同じトランザクション内)、書き込んだデータ 95 が消えていることがわかり、これはユーザーにとって受け入れられません。分散一貫性の観点から見ると、これは「Read-your-writes」の原則に違反します。トランザクションの観点から見ると、「ファントム リード」が発生する可能性があります。つまり、「スコア > 90」という条件に従ってクエリが再度実行されると、トランザクション T1 によって書き込まれた追加の 98 が読み取られ、トランザクション データに異常が発生します。

上記と同様に、MySQL上でマスターとスレーブ間でデータの不整合が発生する状況についても説明されています。

下の図 1 に示すように、データが複数のコピーに拡張され、読み取り操作が拡張されて任意のコピーからデータを読み取れるようになり、書き込み操作が拡張されて任意のコピーにデータを書き込めるようになった場合、分散型アーキテクチャ (つまり、単一のグローバル トランザクション管理メカニズムがない) であり、ネットワークの分断や遅延が発生すると、トランザクションの一貫性と分散一貫性の観点からデータの読み取りまたは書き込み操作を観察すると、より複雑な問題が明らかになります。

図1. 複数コピー異常図

分散アルゴリズムとプロトコルでは、複数のレプリカがある場合のレプリカ間のデータ同期とデータ可視性の異常な状況について説明します。使用される例を図 1 に示します。ワールドカップ サッカーの試合結果が発表され、その結果はリーダー ノードを通じてデータベースに記録されます。実際の結果は、ドイツがワールドカップで優勝したというものでした。ただし、データがリーダー ノードから 2 つの異なるフォロワー ノードに同期されると、アリスとボブは同じ部屋にいて、異なるフォロワー ノードからワールド カップの試合情報を照会します。その結果、アリスはドイツが優勝したことを知り、ボブは試合がまだ終わっていないという知らせを受け取ります。両者は異なる情報を受け取っていたため、矛盾が生じていた。これは、分散アーキテクチャでフォロワー読み取りをサポートする複数のコピーによって発生する不整合の問題でもあります。

2. 分散一貫性とトランザクション一貫性

分散システムに存在する問題を誰もが十分に理解できるように、例え話をしてみましょう。

もしこの世に人が一人しかいなかったら、この世の関係性は非常に単純なものになりますが、人が複数になると「社会」が形成されます。このうち、社会関係とは人と人との間に築かれる関係を指し、人の数が増えるにつれて関係はますます複雑になっていきます。この複雑な社会的関係とデータベースを組み合わせることで、分散データベース システムが実現します。社会における人々は、分散データベース システム内の物理ノード、または物理ノード内のデータのコピーに相当します。図 2 では、分散データベースに存在する複数の問題を説明するために、NewSQL システムのアーキテクチャを例として使用しています。

分散データベースでは大量のデータを保存する必要があり、データを分割して管理する必要があるため、データ シャーディングの概念が導入されています。論理的な観点から見ると、各ノードのデータは 1 つ以上のデータ シャードですが、データベースは「高可用性、高信頼性」の特性を満たし、オンライン リアルタイム サービスを提供する必要があるため、各データ シャードには複数のコピーがあります。データの複数のコピーにより、分散データベースの「一貫性」の問題がより複雑になります。

分散データベースの不整合を、読み取りと書き込みという 2 つの異なる観点から見てみましょう。

まず、図 2 に示す分散データベース システムには、A、B、C、D の 4 つのデータ シャードがあります。各シャードには 3 つのレプリカがあり、各シャードの 3 つのレプリカのうち 1 つはリーダーで、他の 2 つはフォロワーです (Raft 分散プロトコルのリーダーとフォロワーなど)。

図2 分散データベースの一貫性問題の関係図

次に、書き込み操作の場合、図2に示すように次の2つのケースがあります。

1) 単一のデータ シャードを書き込みます (W1): この場合、トランザクションは複数のノードで動作できないため、このようなトランザクションは、スタンドアロン データベース システムのトランザクションと同様に、典型的な単一ノード トランザクションになります。単一のデータ シャードを書き込むと、単一ノード上のトランザクション処理メカニズムによって ACID プロパティが確保されます。単一のデータ シャードを書き込むときにデータの一貫性を実現するには、2PL (2 フェーズ ロック)、TO (タイムスタンプ順序付け)、MVCC (マルチ バージョン同時実行制御) など、データベース システム内の同時アクセス制御テクノロジのみを使用できます。

2) 複数のデータ シャードの書き込み - W2: 1 つのトランザクションを通じて複数のデータ シャードを書き込むのは、典型的な分散トランザクションです。このとき、分散トランザクションの一貫性を保証するために分散同時アクセス制御などの技術が必要であり、ノード間の書き込み操作のアトミック性を保証するために 2PC (2 フェーズ コミット) 技術が必要です。また、強い一貫性が必要な場合（詳細は5.6節を参照）、分散データベースの範囲内でACIDのCとCAPのCの強い一貫性（つまり、直列化可能性と線形一貫性、順次一貫性の組み合わせ）を確保することも考慮する必要がある。 Spanner などの多くのデータベース システムでは、線形一貫性、SS2PL (Strong Strict 2PL) テクノロジ、および 2PC テクノロジを使用して、分散書き込みトランザクションの強力な一貫性を実現します。 CockroachDB や Percolator などの分散データベースは、同時アクセス制御に OCC のようなテクノロジを使用してトランザクションの一貫性 (直列化可能性) を確保し、2PC を使用して分散コミットの原子性を確保しますが、強力な一貫性は実現しません。 CockroachDB は順次シリアル化のみを実現します。分散トランザクションの一貫性を確保するための手法は他にも多数ありますが、それらについては第 4 章で詳しく説明します。

複数のデータシャードに書き込む場合、各データシャード内に複数のコピーが存在するため、コピー間のデータの一貫性をどのように確保するかも、分散システムの典型的な一貫性の問題です（第 2 章では分散システムの一貫性の問題について詳しく説明し、第 3 章ではコンセンサス アルゴリズムのサポート下での複数のコピーの一貫性の問題について詳しく説明します）。有名な Paxos、Raft などのプロトコルは、分散システムのマルチコピー合意問題を解決するために使用されます。この場合、図 1-6 に示すように、通常、A のリーダーと B のフォロワーの組み合わせでは書き込み操作は発生しません。

システムが複数の書き込み操作をサポートしている場合、複数のデータ シャードのリーダーで複数の書き込みが同時に発生します。

読み取り操作の場合、図2に示すように次の2つのケースもあります。

1) 単一のデータ シャードの読み取り - R1: トランザクションが単一のノードのみに関係する場合、トランザクション読み取り操作のデータ一貫性は保証されます (ノード上のトランザクション メカニズムを通じて)。複数のノードが関係する場合、R1 は R11 と R12 の 2 つの読み取りモードに分割されます。

R11 メソッドはリーダーの読み取りに使用されます。書き込み操作中にリーダーが最初に書き込まれるため、書き込みトランザクションがコミットされている場合、R11 によって読み取られるデータはコミットされた最新のデータであることが保証されます。書き込みトランザクションがコミットされていない場合、リーダーで MVCC テクノロジが使用されていると、R11 は古いデータを読み取ります。このような読み取りメカニズムにより、R11 読み取りデータの一貫性を確保できます。リーダーがブロッキング同時アクセス制御メカニズムを使用する場合、書き込みトランザクションがコミットされるまで読み取り操作はブロックされます。したがって、このメカニズムでは、R11 はコミットされた値を読み取り、読み取られたデータの一貫性を保証します。つまり、この場合、データの一貫性は、単一ノード上のトランザクション同時アクセス制御メカニズムに依存します。同時に、これは、分散データベース システム内の単一ノードのトランザクション処理メカニズムが完全なトランザクション処理機能を持つ必要があることも意味します。

フォロワーの読み取りには R12 メソッドが使用されます。フォロワーの読み取りには 2 つのケースがあります。

シャード内では、プライマリ レプリカとスレーブ レプリカ (つまり、リーダーとフォロワー) が強力に同期されます (リーダーはすべてのフォロワーにデータを同期し、アプリケーションが成功した後に結果をクライアントに返します)。この場合、リーダーを読み取る場合でもフォロワーを読み取る場合でも、データはまったく同じであり、読み取られたデータは一貫している必要があります。

リーダーとフォロワー間の同期は弱いです (リーダーは、すべてのフォロワーがデータを同期して正常に適用するまで待たずに、結果をクライアントに返します)。弱い同期は多数決プロトコルを使用することで実現できます。このとき、リーダーとフォロワーの間でデータ書き込みの遅延が発生します。つまり、フォロワーから読み取られるデータは古いデータである可能性がありますが、トランザクションの読み取り操作には 1 つのノードのみが関与するため、読み取り操作データの不一致の問題は発生しません。これは、読み取り専用サービスを提供できる MySQL のマスター スレーブ レプリケーション システムのバックアップ マシンとまったく同じです。

2) 複数のデータ シャードの読み取り - R2: この場合の読み取り操作は複数のシャード/ノードにまたがるため、トランザクション処理メカニズムが適切でない場合は不整合の問題が発生することに注意してください。このような不整合の問題は、トランザクションの不整合または分散システムの不整合のいずれかである可能性があります。以下、図1-6を例に紹介します。 2 つのデータ シャード A と B のみが読み取られると仮定すると、次の 4 つの状況が考えられます。

A のリーダーと B のリーダーを読み取ります。この状況は、完全 L 問題と呼ばれます。

• トランザクションの一貫性: グローバル トランザクション マネージャーがある場合、複数のデータ シャードを読み取る操作は、単一マシン システムでデータを読み取る操作とまったく同じになります。同時アクセス制御プロトコルや MVCC (グローバル スナップショット ポイント) などのテクノロジをブロックすることで、読み取り操作中にデータ異常が発生しないことを保証できます。他のトランザクションの書き込み操作により、このトランザクションの読み取り操作でデータの不整合の問題が発生するため、グローバル同時アクセス制御プロトコル (グローバル ブロッキング同時アクセス制御プロトコルやその他のテクノロジなど) を使用すると、トランザクション レベルでデータの不整合の問題を回避できます。ただし、グローバル同時アクセス制御コーディネーターが存在しない場合は、ノード間でデータの異常が発生しやすくなるため、特定の同時アクセス制御プロトコルによって制御する必要があります。
• 分散システムの一貫性: このタイプの問題は、「A のリーダーと B のリーダーを読み取る」という構造にのみ存在します。分散データベースでは、分散と同時実行によって生じる分散トランザクション データ システムの一貫性の問題を回避するために、「強力な一貫性」を実装する必要があります。具体的な問題については第 2 章で紹介します。

A のリーダーと B のフォロワーを読み取ります。この状況は LF 問題と呼ばれます。 B のリーダーとフォロワーの間に遅延、つまり伝送の遅延が発生し、プライマリ レプリケーションとバックアップ レプリケーション間でデータの不整合が発生します。 「A のリーダーと B のフォロワーを読み取る」方法がサポートされている場合、読み取り対象のノード (A のリーダー ノードと B のフォロワー ノード) に共通のトランザクション状態が存在することを確認する必要があります。

A のフォロワーと B のリーダーを読み取ります。この状況は FL 問題と呼ばれます。問題の分析と解決は上記と同じです。

AのフォロワーとBのフォロワーを読み取ります。この状況は完全 F 問題と呼ばれます。問題の分析と解決は上記と同じです。

データの読み取り時にトランザクションの一貫性と分散システムの一貫性の両方の問題が発生する場合、それらを解決するには強力な一貫性が必要です。

一般に、トランザクションの一貫性は、同時トランザクション間での同じデータ項目への同時アクセス (読み取りと書き込み、書き込みと読み取り、書き込みと書き込みの競合) によって発生しますが、分散一貫性は、複数のノードの分散、ノードによる独自のクロックの使用、および各ノードで発生する操作の順序付けの欠如によって発生します。

この本は「分散データベースの原則、アーキテクチャ、および実践」から抜粋したもので、出版社の許可を得て出版されています。