分散ストレージシステム（問題、概念、ドメイン言語）面接で必ず知っておくべきポイント

意味

分散ストレージシステムは、インターネットを介して接続された多数の一般的な PC サーバーであり、外部全体にストレージ サービスを提供します。

分類

• 非構造化データ、一般文書
• リレーショナルデータベースに保存された構造化データ
• 半構造化データ、HTML ドキュメント

さまざまな分散ストレージ システムは、さまざまなタイプのデータの処理に適しています。

分散ファイルシステム

• オブジェクトの形式で編成された非構造化データには、異なるオブジェクト間の関連性がありません。このようなデータは一般にBlob（バイナリラージオブジェクト）データと呼ばれます。
• 典型的な例としては、Facebook HaystackやTaobao File Systemなどがある。
• さらに、分散ファイルシステムは、分散テーブルシステムや分散データベースの基盤となるストレージとしてよく使用されます。たとえば、Google の GFS は、分散テーブル システム Google Bigtable の基盤ストレージとして使用でき、Amazon の EBS (Elastic Block Storage) システムは、分散データベース (Amazon RDS) の基盤ストレージとして使用できます。
• 一般的に、分散ファイル システムには、Blob オブジェクト、固定長ブロック、および大きなファイルの 3 種類のデータが保存されます。

[[245104]]

分散型キーバリューシステム

• よりシンプルな半構造化データ。主キーのCRUD（作成、読み取り、更新、削除）のみを提供します。
• 代表的な例としてはAmazon DynamoやTaobao Tairなどがある。

分散テーブルシステム

• より複雑な半構造化データ。CRUDをサポートするだけでなく、特定の主キー範囲のスキャンもサポートします。
• データをテーブルに整理します。各テーブルには多数の行が含まれます。行は主キーによって識別されます。主キーに基づく CRUD および範囲検索機能がサポートされています。
• 代表的な例としては、Google Bigtable および Megastore、Microsoft Azure Table Storage、Amazon DynamoDB などが挙げられます。

分散データベース

• 通常は単一マシンのリレーショナルデータベースから拡張された構造化データを保存します。
• 代表的な例としては、MySQLデータベースシャーディングクラスタ、Amazon RDS、Microsoft SQL Azureなどがあります。

問題領域

分散ストレージは、単一マシン ストレージのパフォーマンスと単一点障害の問題を解決します。最初は容量は二次的なものですが、アプリケーションの規模が大きくなるにつれて、問題を解決するために容量も分散する必要があります。

• 分散ストレージが容量の問題、つまりスケーラビリティを解決する方法は、データ シャーディングです。スケーラビリティは分散ストレージによってすでに解決されている問題であり、分散ストレージの既存の問題についての議論では、スケーラビリティは考慮されなくなります。
• データ シャーディングはパフォーマンスの問題を部分的に解決することもできます。パフォーマンスの問題を解決する他の方法には、データのレプリケーションがあります。
• 分散ストレージは、おそらくレプリケーションのみによって、単一点障害の問題を解決します。
• レプリケーションによって一貫性の問題が発生します。

容量の問題を解決する手段は新たな問題を引き起こさないため、分散ストレージ メカニズムを実装する場合、解決またはバランスを取る必要がある問題は、パフォーマンス (または可用性)、単一点障害 (またはパーティション許容度)、および一貫性です。

インフラストラクチャー

通常は2～3層構造

• 分散ファイルシステムの最初のレイヤーは、データのセグメンテーション、レプリケーション、読み取り、書き込みなどのニーズを解決します。
• 上位層はデータ構造層であり、データ モデル、CAP トレードオフなどを解決します。
• その上には、トランザクションなどの問題を解決する高レベルの API があります。

実装上の懸念

データ配信戦略

考慮事項には、読み取りおよび書き込みのシナリオ（ランダムまたはシーケンシャル）や、パフォーマンスを向上させるために負荷分散を確実に行う方法などが含まれます。

• ハッシュ分散、一貫性ハッシュなど。
• 順次配布

一貫性戦略

• 強力な一貫性: 強力な一貫性 (即時一貫性) A が最初にストレージ システムに値を書き込むと、ストレージ システムは、A、B、C の後続の読み取り操作で最新の値が返されることを保証します。
• 弱い一貫性: A が最初にストレージ システムに値を書き込む場合、ストレージ システムは、A、B、C の後続の読み取り操作で最新の値を読み取ることができることを保証できません。この場合、「不整合ウィンドウ」という概念があり、これは具体的には、A が値を書き込んでから、後続の操作 A、B、C が最新の値を読み取るまでの期間を指します。
• 結果的一貫性: 結果的一貫性は弱い一貫性の特殊なケースです。 A が最初にストレージ システムに値を書き込む場合、ストレージ システムは、A、B、C がその後その値を読み取る前に他の書き込み操作によって同じ値が更新されなければ、すべての読み取り操作によって最終的に A によって書き込まれた最新の値が読み取られることを保証します。この場合、障害が発生しなければ、「不整合ウィンドウ」のサイズは、相互作用の遅延、システム負荷、およびレプリケーション テクノロジのレプリカ数 (マスター/スレーブ モードのスレーブ数として理解できます) などの要因によって決まります。結果整合性の最も有名なシステムは DNS システムであると言えます。ドメイン名の IP を更新すると、構成戦略とキャッシュ制御戦略に応じて、最終的にすべての顧客に最新の値が表示されます。

最終的に一貫性のあるバリアント

• 因果一貫性: プロセス A がプロセス B にデータを更新したことを通知すると、プロセス B のその後の読み取り操作では A によって書き込まれた最新の値が読み取られますが、A と因果関係のない C は結果一貫性を実現できます。
• 書き込みの読み取り一貫性: プロセス A が最新の値を書き込むと、プロセス A の後続のすべての操作で最新の値が読み取られます。ただし、他のユーザーがそれを見るまでにはしばらく時間がかかる場合があります。
• セッションの一貫性: この一貫性には、クライアントとストレージ システム間の対話のセッション フェーズ全体を通じて、読み取りと書き込みの一貫性が必要です。 Hibernate のセッションによって提供される一貫性の保証は、この種類の一貫性に属します。
• 単調な読み取り一貫性: この一貫性では、プロセス A がオブジェクトの値を読み取った場合、後続の操作では以前の値を読み取らないことが求められます。
• 単調な書き込み一貫性: この一貫性により、システムはプロセス内のすべての書き込み操作をシリアル化することが保証されます。

障害監視戦略

• リース
• ハートビート

クラスター管理戦略

• マスターコントロール、Paxosプロトコル
• ピアツーピア

分散トランザクション戦略

• 2 フェーズ コミット プロトコル

データモデル

• 表面
• クヴ
• 書類
• 列ファミリー
• 写真

列ファミリとドキュメントは、ある程度は外部インターフェイス モデルではなく、ストレージ モデルです。列ストレージは OLAP に適しており、列ファミリはアクセス パフォーマンスの最適化です。

クエリメソッド

• 構文
• 主キー
• パス
• 索引
• 重合

ドメイン言語

CAP理論

分散ストレージ ネットワーク内のマシンが他のマシンとの接続を失ったが、クライアントとの接続がまだある場合、つまり読み取りおよび書き込み要求がまだ受信されている場合、次のようになります。

• ローカル コンピューターに保存された結果が返される場合、AP は保証され、C は犠牲になります。つまり、要求に対する応答は制限時間内に返され、サービスは停止されませんが、結果が正しいことは保証されません。
• 要求を完了できないことをクライアントに伝えると、AC が保証され、P が犠牲になります。つまり、限られた時間内に要求に対する応答が返され、結果が正しいか、結果がないことが保証されますが、サービスは停止されます。
• ネットワーク接続が回復するのを待ち続けると、CP を保証し、A を犠牲にすることができます。つまり、引き続きサービスを提供し、正しい結果を返すことはできますが、読み取りおよび書き込み操作を終了できることは保証できません。

一貫性のあるハッシュ

従来のハッシュ テーブルでは、ノードを追加または削除するには、ほぼすべてのキーワードの再マッピングが必要です (N を法として計算すると、N-1 または N+1 を法として計算されるため、大きな影響があります)。ハッシュ アルゴリズムのメトリックの 1 つは単調性であり、次のように定義されます。

• 単調性とは、ハッシュを通じて対応するノードに何らかのコンテンツが割り当てられている場合、新しいノードがシステムに追加されることを意味します。ハッシュ結果により、元の割り当てられたコンテンツが新しいノードにマッピングされ、古いノード セット内の他のノード領域にはマッピングされないことが保証されます。

コンシステント ハッシュは特別なハッシュ アルゴリズムです。一貫性のあるハッシュ アルゴリズムを使用した後、ハッシュ テーブル ノードの数 (サイズ) の変更には、平均して K/n 個のキーワードの再マッピングのみが必要になります。ここで、K はキーワードの数、n はノードの数です。

ベクトルクロック

システム内に同じデータのコピーが複数ある場合、グローバル クロックがないため、更新順序を決定し、更新の競合に対処する方法が問題になります (グローバル クロックがある場合は、更新ごとにグローバル クロックの値を記録できるため、順序は明確になります)。したがって、分散環境で明確な順序定義を持つメカニズムを発明する必要があります。従来の順序定義はバージョンによって定義されます (クロックはバージョンを実装するための手段にすぎません)。バージョンの概念を分散環境に拡張すると、ベクトル クロックが得られます。同じデータの N 個のコピーごとに、それぞれが独立して独自のバージョン番号を保持し、これらのバージョン番号が結合されて、データのバージョンとして N 要素のベクトルが形成されます。各ノードはこのようなベクトルを保持しており、初期値は 0 になる場合があります。データが更新されるたびに、ベクトル内の自身のノードに対応するバージョン番号が一緒に更新され、その後、ベクトルと更新されたデータが他のノードに伝播されます。このようにして、各ノードはこれに基づいて更新の競合を検出できます。

リース契約

リースは主にハートビートの誤解を解決するために使用されます。一般的なクラスター システムでは、ハートビートを使用してノードの状態を検出します。ただし、通常の心拍メカニズムでは誤報が発生する可能性があります。通常のハートビートは、通常、指定された時間制限内に検出ノードに生存レポートを定期的に送信します。一定期間ハートビート レポートが受信されない場合、検出ノードはノードに障害が発生した可能性があると判断し、一連の対策 (アラーム、ノード ユーザーへの通知) を実行します。このメカニズムの問題点は、検出ノードが一方的にノードが無効であると判断することであり、一部のビジネス クラスター システムではリスクが生じる可能性があります。ノード自体は無効と判断されたことを認識せず、通常のサービスを提供し続けます。ノードがクラスター内の唯一のプライマリノードの役割を引き受け、検出ノードの障害判定によって新しいプライマリノードの再選出が開始されると、「デュアルプライマリ」問題が発生します。

リースは二者間の契約であり、通常は発行者が保有者に一定期間内に特定の権利を付与する契約として定義されます。これは、一定期間内の発行者のコミットメントを表明するものであり、発行者は、期限が切れない限り、リースで合意されたコミットメントを厳守する必要があります。リースの保有者は、期間内は発行者のコミットメントを使用することができますが、リースの有効期限が切れると、使用を放棄するか、発行者との契約を更新する必要があります。

リースの有効期限が切れる前に、発行者に更新して引き続き使用する必要があります。したがって、さまざまな理由で更新が失敗した場合、ユーザーはリースで規定された権利を放棄する必要があり、発行者は他のノードに権利を発行することができます。

リースは、非常に広範囲にわたるプロトコルコミットメントです。

• 契約内容が依頼者の生存を確認するものである場合、このリースはハートビートに相当します。
• 契約によりコンテンツが変更されないことが保証されている場合、このリースは読み取りロックと同等になります。
• 契約内容が特定のクライアントによってのみ変更されることが保証されている場合、このリースは書き込みロックと同等になります。

パクソスプロトコル

Paxos は分散選択アルゴリズムであり、その主な目的は複数のノード上のデータの一貫性を維持することです。メッセージ パッシング通信モデルに基づく分散システムでは、プロセスが遅くなったり、クラッシュしたり、再起動したりするなどのエラーは避けられません。メッセージが遅延したり、失われたり、重複したりする可能性があります。基本的な Paxos シナリオでは、メッセージの改ざんの可能性は考慮されません。 Paxos アルゴリズムが解決する問題は、上記の例外が発生する可能性がある分散システムで、どのような例外が発生しても解決の一貫性が損なわれないようにしながら、特定の値について合意に達する方法です。

典型的なシナリオとしては、分散データベース システムでは、各ノードの初期状態が一貫しており、各ノードが同じ一連の操作を実行すると、最終的に一貫した状態が得られます。ここでの問題は、各ノードが同じコマンドシーケンスを実行するようにするために、各命令に対して「一貫性アルゴリズム」を実行して、各ノードが認識する命令が一貫していることを確認する必要があることです。 Paxosはそのような「一貫性アルゴリズム」です

Paxos アルゴリズムを説明するために、その提案者である Lamport は Paxos と呼ばれる架空のギリシャの都市国家を創造しました。この島は議会制民主主義の政治モデルに従って法律を制定しましたが、誰もそのような問題に時間とエネルギーをすべて捧げようとはしませんでした。したがって、国会議員も議長も、メモを配る係員も、必要なときにそこにいることを約束することはできないし、決議を承認したりメッセージを届けたりする時間を約束することもできない。しかし、ここではビザンチン将軍問題 (ビザンチン障害、つまり、メッセージが 2 回配信される可能性はあるものの、誤ったメッセージは存在しない) は存在しないと仮定します。十分な時間を待てば、メッセージは配信されます。さらに、パクソス島評議会のメンバーは、他のメンバーが提案した決議に反対しません。

分散システムに対応して、国会議員は各ノードに対応し、制定された法律はシステムの状態に対応します。各ノードは一貫した状態に入る必要があります。たとえば、独立したキャッシュを備えた対称型マルチプロセッサ システムでは、各プロセッサがメモリのバイトを読み取るときに同じ値を読み取る必要があります。そうでない場合、システムは一貫性の要件に違反します。一貫性を保つためには、法律文書のバージョンは 1 つだけである必要があります。カウンセラーとウェイターの不確実性は、ノードとメッセージング チャネルの信頼性の低さに対応します。

具体的なアルゴリズムについてはオンライン資料を参照してください。

ノースウェスタン

NWR は、分散ストレージ システムの一貫性レベルを制御するために使用される戦略です。このうち、N は同じデータのレプリカの数を表し、W はデータ オブジェクトを更新するときに正常に更新されることを保証する必要があるコピーの数です。 R は、データを読み取るために読み取る必要があるレプリカの数を表します。

• R = N または W = N、強い一貫性、弱い可用性、つまり、データが完全に一貫している場合にのみ、すべてのレプリカが成功したと見なされます。
• W + R < N、可用性は強いが一貫性は弱い
• W < N、R < Nだが、W + R > N、可用性と一貫性が比較的バランスが取れている
• W + R > N、特定のデータが2つの異なるトランザクションによって同時に読み書きされないことを保証する
• W > N / 2、2つのトランザクションが同時に特定のデータを書き込むことができないことを保証する

一般的な実装手法

• ランダムな読み取りと書き込みをシーケンシャルな読み取りと書き込みに変換します: 操作ログ + メモリの変更 + 定期的なディスク更新 (最初にログを書き込み、次にメモリを更新)
• バッチ送信、グループ送信: レイテンシは増加しますが、スループットは向上します
• A から書き込み、B から読み取る場合、一貫性の問題が発生します。常に 1 つのエントリから読み取りと書き込みを行い、レプリケーションと自動選択によって信頼性と可用性を解決します。これは、従来のホットスタンバイ データベース クラスターの考え方です。 Mongo はマスタースレーブ構造ですが、ユーザーはマスターノードとのみ対話できます。マスターノードがダウンすると、従来のホットスタンバイデータベースクラスタと同様に、CAに焦点を当てて新しいマスターが自動的に選出されます。
• エンティティ グループ、エンティティ グループ、集約ルート: Megastore の革新の 1 つは、エンティティ グループの概念です。これは、RDBMS (エンティティ グループ内) と Nosql (エンティティ グループ間) の利点を統合するために使用されます。
• 更新されたレコードを個別に保存: OceanBase は、ベースラインと更新を分離することで、書き込み操作の負担を 1 台のマシンが負担できる量まで大幅に削減し、一貫性と信頼性の両方を実現します。
• ロックを必要とする操作と、書き込み操作の同時実行の最適化などの同時実行可能な操作を分離します。プレースホルダとコピーを分離します。プレースホルダにはロックが必要ですが、位置が競合しない限り、コピーには必要ありません。