分散ストレージシステムの一貫性とは何ですか?

「一貫性」という言葉は、分散システムに関連する説明でよく登場します。それはどういう意味ですか？

序文

分散ストレージ システム (OceanBase などの分散データベースを含む) を使用する場合、「一貫性」という言葉がよく使われますが、この用語はシステムや人によって意味合いが異なり、混乱が生じやすいです。

1 つのクライアント (単一プロセス) と 1 つのサーバー (単一プロセス サービス) のみを持つ最も単純なストレージ システムを想像してください。クライアントは読み取りおよび書き込み操作を順番に開始し、サーバーは各要求を順番に処理します。したがって、サーバーの観点でもクライアントの観点でも、前の操作の結果を後続の操作で確認できます。

すると、システムはより複雑になります。システムは単一のサービス プロセス (単一のコピー) のままですが、複数のクライアントが同時に動作します。このモデルでは、複数のクライアントの操作が相互に影響を与える可能性があります。たとえば、クライアントは、自分自身によって書き込まれていないデータ (別のクライアントによって書き込まれたデータ) を読み取る場合があります。一般に、複数のスレッドがメモリを共有するプログラムなど、単一マシンの並行プログラムはこのモデルに従います。

[[222885]]

すると、システムは別の方向でさらに複雑になります。バックエンド ストレージ システムをより堅牢にするために (ただし、この目的のためだけにではありません)、2 つの異なるサービス プロセス (異なるマシンに配置) に同じデータのコピーを同時に保存させ、何らかの同期メカニズムを使用して 2 つのコピーのデータの一貫性を保つことができます。これを「複数コピー」と呼びます。クライアント プロセスが読み取り操作と書き込み操作を順番に開始すると仮定すると、各操作は理論的には 2 つのレプリカが配置されている任意のサービスに送信できます。したがって、レプリカ間のデータが時間的に同期されていない場合、以前に書き込まれたデータを読み取ることができなかったり、以前に読み取ったデータを後で読み取ることができない可能性があります。

最初の 2 つのモデルを組み合わせると、実際のシステムでは、複数のクライアントが同時に読み取りと書き込みの操作を実行し、バックエンド ストレージ サービスの複数のコピーを読み書きすることになります。これらの異なるクライアントの読み取り操作と書き込み操作が同じデータ項目 (たとえば、ファイル システム内の同じファイルの同じ場所の範囲、またはデータベース システム内の同じテーブルの同じ行) に関係する場合、それらの操作は互いに影響を及ぼします。たとえば、2 つのクライアント A と B が同じデータ行を操作します。 A がこの行を変更する場合、B が最新のデータをすぐに読み取ることができる必要がありますか?マルチレプリカ システムでは、上記の保証が不要な場合は、A と B が異なるレプリカで動作できるようにすることも可能です。

さらに、以前のシステム モデルでは、各サービス プロセスがデータの「完全な」コピーを所有および管理していると想定されていました。より複雑なシステムでは、各サーバー プロセスはデータ セット全体のサブセットのみを処理します。たとえば、OceanBase のようなシステムでは、1 台のマシンにすべてのデータのコピーを保存できないことが多いため、データベース テーブルとテーブル パーティションは複数のマシンに分散されてサービスが提供され、各サービス プロセスは特定のテーブル パーティションのコピーのみを担当します。このようなシステムでは、読み取りまたは書き込み操作に関係する複数のパーティションが複数のサービス プロセスに配置されている場合、より複雑な読み取りまたは書き込みのセマンティック異常が発生する可能性があります。たとえば、書き込み操作 W が 2 つの異なるサービス プロセスの 2 つの異なるパーティションのレプリカ上の 2 つの異なるデータ項目を変更する場合、これらの 2 つのデータ項目を読み取る後続の読み取り操作では、W による 1 つのデータ項目の変更を読み取ることはできますが、他のデータ項目の変更を読み取ることはできませんか。

要約すると、ここで説明する一般的な分散ストレージ システムには、次の特性があります。

データは複数のシャードに分割され、複数のサービスノードに保存されます。

各シャードには複数のコピーがあり、異なるサービスノードに保存されます。

多くのクライアントが同時にシステムにアクセスし、読み取りおよび書き込み操作を実行しますが、システム内での各読み取りおよび書き込み操作にかかる時間は異なります。

特に明記しない限り、読み取りおよび書き込み操作はアトミックです。

データベーストランザクションの一貫性との違い

データベース トランザクションの ACID にも一貫性はありますが、その一貫性はこの一貫性とは異なります。 ACID における一貫性とは、データベース トランザクションの実行、またはトランザクションによって監視されるデータが、一意制約、外部キー制約などの特定のグローバル一貫性制約を常に満たす必要があることを意味します。この概念は、データベース データのコピーが複数あるかどうかとは関係ありません。この記事の一貫性は、複数のコピーのコンテキストでのみ意味を持ちます。したがって、データベース トランザクションの一貫性とは、データ項目間で特定の制約が常に満たされていること、または制約を満たすという意味でデータベース全体が正しいことを意味します。

さらにイライラさせられるのは、トランザクション分離が一貫性モデルに似ており、特定の同時操作の実行順序を制限するため、ここではトランザクション分離が一貫性と簡単に混同される可能性があることです。トランザクション分離とは、同時に実行されるトランザクションが互いを認識できる範囲を指します。この概念は、データに複数のコピーがあるかどうかとは関係ありません。単一コピーのスタンドアロン データベースでも、さまざまな分離レベルをサポートする必要があります。たとえば、データベースがシリアル化可能な分離レベルに設定されている場合、同時トランザクションを実行した結果は、これらのトランザクションを特定の順序でシリアルに実行した結果と同じである必要があります。トランザクション分離は、並行プログラム (クライアント プログラム) の正確性のために作成されたプログラミング抽象化です。これは、マルチスレッド プログラムが共有データにアクセスするときに解決する必要がある競合に例えることができます。実際のシステムでは、トランザクションは一連の読み取りおよび書き込み操作で構成され、アトミック トランザクションの中間状態は他の同時トランザクションによって「観察」される場合があります。一貫性モデルの説明では、読み取り操作と書き込み操作がサーバー側で「瞬時に」完了する、つまり読み取り操作と書き込み操作自体がアトミックであると想定しています。

クライアント側一貫性モデル

マルチコピー ストレージ システムでは、どのようなマルチコピー同期プロトコルが使用されているかに関係なく、複数のコピーの一貫性を保証するために、基本的に次のことが必要です。

1. 同じデータのすべてのコピーは、すべての書き込み操作を受け取ります（どれだけ時間がかかるかに関係なく）
2. すべてのレプリカは、これらの書き込み操作を何らかの決定論的な順序で実行する必要があります。

クライアント側の一貫性モデルでは、次の 4 つの異なる保証が定義されます。

1. 単調な読書。クライアントがデータの特定のバージョン n を読み取る場合、その後に読み取るバージョンは n 以上である必要があります。
2. あなたが書いたものを読んでください。クライアントが何らかのデータのバージョン n を書き込む場合、その後の読み取り操作ではバージョン n 以上のデータを読み取る必要があります。
3. 単調に書きます。モノトニック書き込みにより、同じクライアントからの 2 つの異なる書き込み操作が、ストレージ システムに到着した順序と同じ順序ですべてのレプリカに対して実行されることが保証されます。単調な書き込みにより、書き込み操作が失われるのを回避できます。
4. 書く前に読んでください。書き込み後の読み取り一貫性により、クライアントがバージョン n のデータ (他のクライアントによって書き込まれる可能性がある) を読み取った後、後続の書き込み操作はバージョン番号が n 以上のレプリカに対して実行される必要があります。

システムによって提供されるさまざまな一貫性レベルは、実際にこれらの保証の一部を提供します。一貫性レベルによって、実行できる操作の順序とデータの古さが制限されます。

異なる一貫性レベルを定義するのはなぜですか?もちろん、ユーザーにとっては、一貫性が厳格であればあるほど良いです。異常で複雑なシナリオでは、厳格な一貫性レベルによってアプリケーションの複雑さが大幅に簡素化されます。しかし、世の中にタダ飯はない。一般的に、一貫性モデルが厳格になるほど、パフォーマンス (レイテンシ)、可用性、またはスケーラビリティ (サービスを提供できるノードの数) が低下する可能性が高くなります。

CosmosDB の一貫性レベル

Azure Cosmos DB2 は、複数の場所への展開をサポートする分散 NoSQL データベース サービスです。豊富な設定可能な一貫性レベルを提供します。次の 5 つの整合性レベルにより、読み取りと書き込みのレイテンシが短縮され、可用性が向上し、フロントからバックまでの読み取りのスケーラビリティが向上します。

1. 強い一貫性

• 読み取り操作で常に最新バージョンのデータを読み取ることができることを保証する（つまり線形化可能性）
• 書き込み操作を正常に送信するには、その操作を大多数のレプリカに同期する必要があります。読み取り操作では、レプリカがクライアントに返される前に、レプリカの大部分が応答する必要があります。読み取り操作では、コミットされていない書き込み操作や部分的な書き込み操作の結果は表示されず、常に最新の書き込み操作の結果を読み取ることができます。
• グローバル（セッション間）の単調な読み取り、書き込んだ内容の読み取り、単調な書き込み、および読み取り後の書き込みを保証します。
• 読み取り操作のコストは他の一貫性レベルよりも高く、読み取り待ち時間も最も長くなります。

2. 境界付き古さ

• 読み取られたデータが最新バージョンと最大 K バージョン異なることを確認する
• スライディング ウィンドウを維持することにより、境界付き古い一貫性はウィンドウ外の操作のグローバルな順序を保証します。さらに、領域内では単調な読み取りが保証されます。

3. セッションの一貫性

1. 単調な読み取り、単調な書き込み、および独自の書き込みの読み取りはセッション内では保証されますが、セッション間では保証されません。
2. セッションの一貫性により、クライアント セッションで維持され、複数のコピー間で送信される読み取りおよび書き込み操作のバージョン情報を提供できます。

セッションの一貫性により、読み取りと書き込みのレイテンシが低くなります

4. 接頭辞の一貫性

• プレフィックスの一貫性により、すべてのレプリカが最終的に書き込み操作なしで一貫性を保つことが保証されます。
• プレフィックスの一貫性により、読み取り操作で順序どおりでない書き込み操作が発生しないことが保証されます。たとえば、書き込み操作が `A、B、C` の順序で実行される場合、クライアントは `A`、`A、B`、または `A、B、C` のみを表示でき、`A、C`、または `B、A、C` などを読み取ることはできません。
• 各セッション内で単調な読み取りが保証される

5. 最終的な一貫性。

• 最終的な一貫性により、書き込み操作がなくなった場合に、すべてのレプリカが最終的に一貫性を持つことが保証されます。
• 結果的一貫性は、クライアントが以前に読み取ったデータよりも古いデータを読み取ることができる弱い一貫性保証です。
• 結果整合性では、任意のレプリカの読み取りを選択できるため、読み取りと書き込みの待ち時間が最も短くなり、可用性が最高になります。

Cosmos DB のドキュメントには興味深い数字が記載されています。約 73% のユーザーがセッション一貫性レベルを使用し、20% のユーザーが境界付きレガシー一貫性レベルを使用しています。

Cassandra の一貫性レベル

Cassandra は、多数決プロトコルを使用する NoSQL ストレージ システムです。読み取りおよび書き込み操作によってアクセスされるレプリカの数と場所を制御することで、さまざまな一貫性レベルを実現できます。 NoSQL システムである Cassandra は、単一行の操作に対してのみアトミック性を提供することに注意してください。複数行の操作はアトミックではありません。次の読み取りおよび書き込み操作はすべて、単一行の操作を指します。

NoSQL システムの場合、一般的にサポートされている書き込み操作は PUT と呼ばれます (一部のシステムでは UPSERT と呼ばれます)。この操作の意味は、行が存在する場合（一意の主キー検索を通じて）、その行が変更されるということです。行が存在しない場合は挿入されます。このセマンティクスは、リレーショナル データベースの INSERT ON DUPLICATE KEY UPDATE ステートメント (セカンダリ インデックスが考慮されない場合) とほぼ同等です。この記事で前述した「書き込み操作」もこのセマンティクスを指します。このセマンティクスの何が特別なのでしょうか?まず、それはべき等性を持っています。したがって、メッセージの再送信を気にせずに PUT 操作を繰り返し実行できます。 2 番目に、上書きセマンティクスがあります。したがって、NoSQL システムの結果一貫性により、同じデータ行に対する書き込み操作が順序どおりに行われない可能性があります。書き込み操作が継続される限り、すべてのコピーは最終的に一貫性を保ちます。リレーショナル データベースでの挿入や更新などの変更ステートメントの内部実装には、読み取りと書き込みの両方が必要です。したがって、リレーショナル データベースの複数のコピーの一貫性を、SQL 変更ステートメントを複数のコピーに同期するだけで実現する場合、一貫した結果を保証するには、それらを同じ順序で実行する必要があります (もちろん、実際のシステムではこれを実現することはできません)。

書き込み操作の構成

書き込み操作の一貫性構成は、書き込み操作がクライアントに返される前にどのレプリカで成功する必要があるかを定義します。

• ALL: 書き込み操作はすべてのレプリカに同期され、メモリに適用される必要があります。最も強力な一貫性保証を提供しますが、単一障害点により書き込みエラーが発生し、システムが使用できなくなる可能性があります。
• EACH_QUORUM: 各データセンターでは、書き込み操作がレプリカ ノードの大部分に同期されます。複数のデータ センターに展開されたクラスターでは、各データ センターで QUORUM の一貫性保証を提供できます。
• QUORUM: 書き込み操作はレプリカ ノードの大部分に同期されます。いくつかのレプリカがダウンしても、書き込み操作は引き続き提供されます。
• LOCAL_QUORUM: 書き込み操作は、コーディネーター ノードが配置されているデータ センター内のレプリカの大部分に同期される必要があります。このモードでは、複数のデータセンターが展開されている場合に、データセンター間の同期によって発生する高い遅延を回避できます。単一のコンピューター室では、少数の停止は許容できます。
• 1: 書き込み操作は少なくとも 1 つのレプリカに書き込まれる必要があります。
• 2: 書き込み操作は少なくとも 2 つのレプリカに書き込まれる必要があります。
• 3: 書き込み操作は少なくとも 3 つのレプリカに書き込まれる必要があります。
• LOCAL_ONE: 書き込み操作は、ローカル データ センター内の少なくとも 1 つのレプリカに書き込まれる必要があります。複数のコンピュータ室に展開されたクラスターでは、ONE と同様の災害復旧効果が得られ、書き込み操作をローカルのコンピュータ室に限定することができます。

読み取り操作構成

• 各読み取り操作は、次のように異なる一貫性構成で設定できます。
• ALL: すべてのレプリカ ノードが応答した後にのみ、読み取り操作がクライアントに返されます。単一のポイントと単一のマシンでは書き込み操作が失敗し、システムが使用できなくなります。
• QUORUM: 大多数のレプリカが応答を返した後、読み取り操作がクライアントに返されます。
• LOCAL_QUORUM: ローカル ルーム内のレプリカの大多数が応答を返した後、読み取り操作がクライアントに返されます。データセンター間のアクセスにおける高遅延を回避できます。
• 1: 最も近いレプリカ ノードが応答し、クライアントに応答を返します。古いデータが返される可能性があります。
• 2: 2 つのレプリカ ノードが応答すると、その応答がクライアントに返されます。
• 3: 3 つのレプリカ ノードが応答し、クライアントに応答を返します。
• LOCAL_ONE: ローカル ルーム内の最も近いレプリカ ノードが応答し、メッセージをクライアントに返します。

システム一貫性レベル

システムの観点から見ると、Cassandra は強力な一貫性と最終的な一貫性という 2 つの一貫性レベルを提供します。複数のコンピュータルームの要因を考慮せずに、上記の読み取り操作と書き込み操作の一貫性構成を設定することで、書き込みコピー数と読み取りコピー数の合計が合計コピー数より大きい場合、読み取り操作では常に最新の書き込みデータを読み取ることができること、つまり強力な一貫性保証を保証できます。書き込みレプリカの数と読み取りレプリカの数の合計がレプリカの総数より少ない場合、読み取り操作で最新のデータを読み取ることができず、読み取り操作で前回の読み取り操作よりも古いデータを読み取る可能性があるため、このケースは結果整合性です。

レプリカの場所は、クラスター全体、各コンピュータ ルーム、ローカル コンピュータ ルームなどの要因によって決まります。これは、さまざまな災害復旧シナリオでコンピュータ室間の通信によって生じる高い遅延を最適化するためです。固有の一貫性レベルは影響を受けません。たとえば、EACH_QUORUM は書き込み操作に使用され、LOCAL_QUORUM は読み取り操作に使用されます。強力な一貫性の保証は引き続き提供されますが、異なるコンピューター ルームでの読み取り操作はローカルになり、読み取りの待機時間は短くなります。ただし、書き込み操作の QUORUM モードと比較すると、データ センターで多数派障害が発生した場合 (レプリカの総数が依然として少数派の場合)、書き込み操作は失敗します。たとえば、読み取り操作と書き込み操作の両方で LOCAL_QUORUM を使用する場合、コーディネーター ノードが配置されているコンピューター ルームのデータは強力な一貫性を保ち、コーディネーター ノードと同じではないコンピューター ルームでの読み取り操作では古いデータが読み取られる可能性があります。

OceanBase 一貫性レベル

一般的に、HBase、Cassandra4 などの NoSQL データベースは、単一行の操作に対してのみアトミック性の保証を提供します。リレーショナル データベースの基本的な操作は SQL ステートメントです。 SQL ステートメントは本質的に複数行の操作であり、複数ステートメントのトランザクションとトランザクションのロールバックをサポートします。アトミック性の保証は、SQL ステートメント レベルとトランザクション レベルの両方で必要です。当然のことながら、同じ一貫性レベルを実現するには、分散リレーショナル データベースは NoSQL システムよりも複雑でコストがかかります。

OceanBase は、Multi-Paxos 分散コンセンサス アルゴリズムを使用して、複数のデータ レプリカ間でトランザクション コミット ログを同期します。各変更トランザクションは、レプリカの大多数が応答した後にのみコミットされたと見なされます。複数のレプリカの中から、自律的な投票メカニズムを通じて 1 つがプライマリ レプリカ (リーダー) として選択されます。すべての変更ステートメントの実行を担当します。特に、過半数に達するトランザクション コミット ログには、プライマリ レプリカ自体が含まれている必要があります。通常の状況では、データベースは強力な一貫性セマンティクス (スタンドアロン データベースと同様) を確保する必要があります。私たちのアプローチは、プライマリレプリカで読み取りステートメントと書き込みステートメントの両方を実行することです。プライマリ レプリカがダウンすると、残りの大多数のレプリカが新しいプライマリ レプリカを選択します。この時点で、完了したすべてのトランザクションには、コミット ログを記録したレプリカが少なくとも 1 つ必要です。新しいプライマリレプリカは、他のレプリカと通信することでコミットされたすべてのトランザクションのログを取得できるため、リカバリが完了し、リカバリ後も引き続きサービスを提供できます。このメカニズムにより、OceanBase は少数の障害が発生した場合でもデータが失われないことを保証でき、強力な一貫性のある読み取りおよび書き込みサービスのダウンタイム回復時間は 1 分未満になります。

ステートメントの実行に複数のテーブルのパーティションが関係する場合、これらのパーティションのプライマリ レプリカは OceanBase 内の異なるサービス ノードに配置されることがあります。厳密なデータベース分離レベルでは、複数のパーティションを含む読み取り要求で「スナップショット」を参照する必要があります。つまり、部分的なトランザクションを参照することはできません。これには、何らかの形式のグローバル読み取りバージョン番号を維持する必要があり、コストがかかります。アプリケーションが許可する場合は、読み取り一貫性レベルを調整できます。システムは、書き込まれた最新のデータが読み取られることを保証しますが、異なるパーティション上のデータはスナップショットではありません。一貫性レベルの観点から見ると、これも強力な一貫性レベルですが、データベース トランザクションの ACID プロパティが破壊されます。

データベースを使用するインターネットビジネスでは、ビジネスコンポーネントが少し古いデータを読み取ることが許可されることがよくあります。 OceanBase は、より弱い一貫性レベルを 2 つ提供します。最も弱いレベルでは、すべてのレプリカを使用して読み取りサービスを提供できます。 OceanBase の実装では、マルチレプリカ同期プロトコルは、ログがディスクに書き込まれることを保証するだけで、ログが多数レプリカ (ストレージ エンジンの memtable に書き込まれる) で再生される必要はありません。したがって、任意のレプリカを使用して読み取りサービスを提供する場合、同じパーティションの複数のレプリカであっても、各レプリカによって再生されるデータ バージョンは異なるため、読み取り操作によって前回の読み取りよりも古いデータが読み取られる可能性があります。つまり、この場合は最終的な一貫性が提供されます。いずれかのレプリカがダウンした場合、クライアントは他のレプリカをすぐに再試行でき、大多数のレプリカがダウンした場合でもこの読み取りサービスを提供できます。

しかし、現実には、リレーショナル データベースを使用するほとんどのアプリケーションでは、順序どおりに読み取れないことを許容できません。データベース接続内で読み取りバージョン番号を記録することで、結果整合性よりも厳密なプレフィックス整合性も提供されます。各データベース接続内での単調な読み取りを保証できます。このモードは、通常、OceanBase クラスター内の読み取りデータベースにアクセスするために使用され、ビジネス自体は読み取りと書き込みの分離アーキテクチャです。

さらに、これら 2 つの弱い一貫性レベルでは、ユーザーは構成を通じて、古いデータの読み取りを許可する範囲を制御できます。 OceanBase が複数の場所に展開されている場合、クロスリージョンレプリカデータ間の遅延は必然的に発生します。たとえば、ユーザー構成で 30 秒以内にデータを読み取ることが許可されている場合、ローカル コピーの遅延が 30 秒未満であれば、読み取り操作でローカル コピーを読み取ることができます。要件を満たすことができない場合は、プライマリ レプリカが配置されている他のレプリカが読み取られます。それでも条件が満たされない場合は、プライマリ コピーが読み取られます。このアプローチにより、強力な一貫性の読み取りよりも最小限の読み取りレイテンシと優れた可用性を実現できます。このようにして、セッション レベルの単調な読み取りを保証しながら、制限された古さの一貫性レベルを提供します。

これらの弱い一貫性レベルでは読み取り操作のセマンティクスが緩和され、すべての書き込み操作はプライマリ レプリカ ノードに書き込まれる必要があることに注意してください。したがって、単調な書き込みと書き込み後の読み取りは常に保証されますが、書き込んだ内容の読み取りは保証されません。理論的には、後者の弱い一貫性レベルのそれぞれに対して、読み取られたデータが「スナップショット」であることが保証されるかどうかの 2 つの異なるセマンティクスを提供することもできますが、これは ACID セマンティクスに違反するため、提供されません。

要約すると、OceanBase は、リレーショナル データベースの完全な ACID トランザクション セマンティクスを確保しながら、強力な一貫性、境界付き古い一貫性、プレフィックスの一貫性、最終的な一貫性など、いくつかの一貫性レベルを提供します。

最後に、この記事を読んで、改訂のための貴重な提案をしてくださった @杨苏立 に特に感謝します。

参考文献

1 Wikipedia の一貫性モデル。 https://en.wikipedia.org/wiki/Consistency_model

Azure Cosmos DB の 2 つの調整可能なデータ一貫性レベル。 https://docs.microsoft.com/en-us/azure/cosmos-db/consistency-levels

3 Apache Cassandra でのデータ一貫性の構成。 https://docs.datastax.com/en/archived/cassandra/2.0/cassandra/dml/dml_config_consistency_c.html

4 Cassandra 2.0 は軽量トランザクションを提供します。詳細については、そのドキュメントを参照してください。