分散ストレージアーキテクチャを1つの記事で理解するには、この分析を収集する価値があります

  [[325799]]

1. 集中型ストレージ構造

分散ストレージに関しては、まず従来のストレージがどのようなものかを見てみましょう。

従来のストレージは集中型ストレージとも呼ばれます。概念的には集中化されており、つまりストレージ全体が 1 つのシステムに集中しています。ただし、集中型ストレージは単一のデバイスではなく、システム内に複数のデバイスが集中しています。たとえば、下の図の EMC ストレージを保管するには、複数のキャビネットが必要です。

[[325800]]

このストレージシステムには、ヘッド（コントローラ）、ディスクアレイ（JBOD）、スイッチなどのコアデバイスに加えて、管理デバイスなどの補助デバイスも含まれており、多くのコンポーネントが含まれています。

この構造には、ストレージ システムの最も重要なコンポーネントであるヘッドが含まれています。通常、ヘッドには 2 つのコントローラがあり、ハードウェア障害によってストレージ システム全体が使用できなくなるのを防ぐために、相互にバックアップとして機能します。ヘッドには通常、フロントエンド ポートとバックエンド ポートが含まれます。フロントエンド ポートはサーバーのストレージ サービスを提供しますが、バックエンド ポートはストレージ システムの容量を拡張するために使用されます。バックエンド ポートを介してさらに多くのストレージ デバイスをヘッドに接続できるため、非常に大きなストレージ リソース プールを形成できます。

全体の構造において、ヘッドはストレージシステム全体の中核コンポーネントであり、ストレージシステム全体の高度な機能がヘッドに実装されています。コントローラ内のソフトウェアはディスクを管理し、ディスクをストレージ リソース プールに抽象化してから、サーバーが使用できるように LUN に分割します。ここでの LUN は、実際にはサーバー上で表示されるディスクです。もちろん、一部の集中型ストレージは、共有ファイル サービスを提供できるファイル サーバーでもあります。いずれにせよ、上記から、集中型ストレージの最大の特徴は、統一された入口があり、すべてのデータがストレージ システムの先頭であるこの入口を通過する必要があることであることがわかります。これは、集中型ストレージと分散型ストレージを区別する最も重要な機能です。次の図に示すように:

2. 分散ストレージ

分散ストレージは、大規模な高同時実行シナリオで安価なサーバーを使用して Web へのアクセスを提供することを目的として、Google によって最初に提案されました。拡張可能なシステム構造を採用し、複数のストレージサーバーを使用してストレージ負荷を分散し、ロケーションサーバーを使用してストレージ情報を検索します。システムの信頼性、可用性、アクセス効率が向上するだけでなく、拡張も容易になります。

1. 分散ストレージの台頭

分散ストレージの台頭は、インターネットの発展と密接に関係しています。インターネット企業は通常、データ量が多く資本蓄積が少ないため、大規模な分散ストレージシステムを使用します。

インターネット企業の分散ストレージ システムは、従来のハイエンド サーバー、ハイエンド ストレージ、ハイエンド プロセッサとは異なり、ネットワークを介して接続された多数の低コストで費用対効果の高い通常の PC サーバーで構成されています。主な理由は次のとおりです。

（１）インターネットビジネスは急速に発展しており、コスト意識が高まっています。つまり、ストレージ システムは、従来の垂直拡張アプローチ、つまり最初にミニコンピュータを購入し、それでは不十分な場合はミッドレンジ コンピュータ、さらにはメインフレームを購入するというアプローチに頼ることはできません。インターネットバックエンドの分散システムでは、通常の PC サーバーを追加することでシステム全体の処理能力を高める、つまり水平拡張をサポートすることが求められています。

（２）一般的なPCサーバーはコスト効率に優れていますが、故障率が高いです。データの一貫性を確保するには、ソフトウェア レベルで自動フォールト トレランスを実装する必要があります。

（３）さらに、サーバの台数が増えるにつれて、システムの処理能力を直線的に拡張できるように、ソフトウェアレベルで自動負荷分散を実装できる必要がある。

2. 分散ストレージの重要性

単一マシン単一ユーザーから単一マシンマルチユーザー、そして現在のインターネット時代に至るまで、アプリケーション システムは多くの変化を遂げてきました。分散システムは依然として議論の的となっている話題です。では、分散システムは私たちに何をもたらすのでしょうか、あるいはなぜ分散システムが必要なのでしょうか?

（１）１台のマシンの処理能力をアップグレードする費用対効果はますます低下している。

企業は、垂直拡張のためにハードウェアを交換してパフォーマンスを向上させることがますます非経済的になっていることに気づいています。

（２）１台のマシンの処理能力にボトルネックがある。

ある特定の時点では、単一のプロセッサに独自のパフォーマンスのボトルネックが発生します。つまり、コンピューティング能力を購入するためにさらにお金を費やしても、それを購入することはできないということです。

（３）安定性と可用性を考慮する

ワンクリックシステムを使用すると、マシンが正常に動作しているときは問題ありませんが、問題が発生すると、システムは完全に使用できなくなります。もちろん、災害復旧やその他のソリューションを検討することもできます。これらのソリューションにより、システムは分散システムへと進化します。

（４）クラウドストレージとビッグデータの発展に不可欠な要件

クラウド ストレージとビッグ データは、分散ストレージ上に構築されたアプリケーションです。モバイル端末の計算能力とストレージ容量には限りがあり、複数のデバイス間でリソースを共有したいという強い要望があるため、ネットワークディスクやフォトアルバムなどのクラウドストレージアプリケーションが急速に普及しました。しかし、状況がどのように変化しても、クラウド ストレージの中核はバックエンドの大規模分散ストレージ システムです。ビッグデータはさらに一歩進みます。膨大な量のデータを保存するだけでなく、データを分析して貴重な部分を抽出するための適切なコンピューティング フレームワークまたはツールの使用も必要です。分散ストレージがなければ、ビッグデータを分析することはできません。注意深く分析すると、分散ストレージ技術がインターネット バックエンド アーキテクチャの魔法の武器であることがわかります。このスキルを習得すると、将来的には他のテクノロジーの本質を理解するのが非常に簡単になります。

3. 分散ストレージの種類と比較

分散ストレージには、分散ファイルシステム、分散ブロックストレージ、従来の意味での分散オブジェクトストレージのほか、分散データベースや分散キャッシュなど、さまざまな種類があります。ただし、アーキテクチャは次の 3 種類にすぎません。

A. 中間制御ノードアーキテクチャ

HDFS（Hadoop Distribution File System）に代表されるアーキテクチャが代表的なものです。このアーキテクチャでは、ノードの一部である NameNode に管理データ (メタデータ) が保存され、ノードの別の部分である DataNode にビジネス データが保存されます。このタイプのサーバーは、特定のデータの管理を担当します。このアーキテクチャは、企業の階層型組織構造に似ています。 Namenode は、下位のマネージャー (データノード) のみを管理するボスのようなもので、下位のマネージャーはノードの下にあるローカル ディスク上のデータを管理します。

上の図では、クライアントがファイルからデータを読み取る必要がある場合、まず NameNode (具体的にはどの DataNode) からファイルの場所を取得し、次に NameNode から特定のデータを取得します。このアーキテクチャでは、NameNode は通常、プライマリ NameNode とセカンダリ NameNode として展開され、DataNode は多数のノードで構成されるクラスターです。メタデータのアクセス頻度と量はデータよりもはるかに少ないため、通常、NameNode はパフォーマンスのボトルネックにはなりません。 DataNode クラスター内のデータはコピーできるため、高可用性を確保し、クライアント要求を分散できます。したがって、この分散ストレージ アーキテクチャでは、データノードの数を水平方向に拡張することで収容能力を高めることができ、つまり動的な水平方向の拡張が可能になります。

B. 完全に分散化されたアーキテクチャ - コンピューティングモデル

Ceph に代表されるアーキテクチャはその典型的な例です。このアーキテクチャと HDFS の違いは、このアーキテクチャには中央ノードが存在しないことです。クライアントはデバイス マッピング関係を通じてデータを書き込む場所を計算し、ストレージ ノードと直接通信できるようにすることで、中央ノードのパフォーマンスのボトルネックを回避します。

上図に示すように、Ceph ストレージ システム アーキテクチャのコア コンポーネントには、MON サービス、OSD サービス、MDS サービスが含まれます。

（１）MONサービスは、ストレージシステムのハードウェア論理関係、主にサーバとハードディスクのオンライン情報を維持するために使用されます。 MON サービスは、クラスタリングを通じてサービスの可用性を保証します。

（２）OSDサービスはディスクの管理と実際のデータの読み書きを実現するために使用されます。通常、1 つのディスクは 1 つの OSD サービスに対応します。

（3）MDSはファイル階層を追跡し、CephFSファイルストレージシステムのメタデータのみを保存します。 Ceph ブロック デバイスと RADOS はメタデータを必要としないため、Ceph MDS デーモンも必要ありません。

（4）RADOS：RADOSは、上記の3つのサービスを含むCephストレージクラスターです。 Ceph 内のすべてのデータはオブジェクトの形式で存在し、RADOS オブジェクト ストレージはデータの種類に関係なくこれらのオブジェクトを保存する役割を担います。 RADOS レイヤーは、データの一貫性が常に保たれることを保証します。これを実現するには、データの複製、障害の検出と回復、データの移行とクラスター ノードのバランスが必要です。

（5）RBD（ブロックデバイス）：以前はRADOSブロックデバイスとして知られており、信頼性の高い分散型で高性能なブロックストレージディスクをクライアントに提供します。

(6) CephFS: Cephファイルシステムは、Cephストレージクラスターを使用してユーザーデータを保存するPOSIX互換のファイルシステムを提供します。

（7）Librados：libRADOSライブラリは、PHP、RUBY、Java、Python、C++などの言語のRADOSインターフェースへの便利なアクセスを提供します。

（８）RADOS GW：RGWはオブジェクトストレージサービスを提供します。これにより、アプリケーションは Ceph オブジェクト ストレージとの接続を確立できるようになります。 RGW は、Amazon S3 および OpenStack Swift と互換性のある RUSTFUL API を提供します。

クライアントがストレージにアクセスする一般的なプロセスは、起動後、クライアントがまず RADOS GW を経由して入り、MON サービスからストレージ リソースのレイアウト情報を取得し、次にレイアウト情報と書き込まれたデータの名前に基づいて予想されるデータの場所 (特定の物理サーバー情報とディスク情報を含む) を計算し、その後、位置情報の CephFS に対応する場所と直接通信してデータを読み書きします。

C. 完全に分散化されたアーキテクチャ - 一貫性のあるハッシュ

Swift に代表されるアーキテクチャはその代表的なものです。 Ceph の計算によってデータの場所を取得する方法とは異なり、一貫性のあるハッシュによってデータの場所を取得する方法もあります。一貫性ハッシュ方式は、デバイスをハッシュ リングにして、データ名に応じて計算されたハッシュ値をハッシュ リング内の特定の位置にマッピングしてデータを見つける方法です。

Swift には 2 種類のマッピング関係があります。ファイルの場合、ハッシュ アルゴリズム (MD5) (1 対 1 のマッピング関係) を通じて対応する仮想ノードが検索され、仮想ノードはマッピング関係 (リング ファイル内の 2 次元配列) を通じて対応するデバイス (多対多のマッピング関係) を検索します。このようにして、デバイスに保存されているファイルのマッピングが完了します。

D. 分散ストレージの比較

ここで問題になるのは、分散ストレージを選択する場合、どれを選択すべきかということです。実際、特定のニーズに応じて、それぞれに独自の利点と使用シナリオがあります。

（１）HDFS

これは主にビッグデータ ストレージ シナリオで使用され、Hadoop ビッグデータ アーキテクチャのストレージ コンポーネントです。 HDFS が最初に設計されたとき、そのアプリケーション シナリオはビッグ データ サービスとして明確に定義されていました。主な適用シナリオは次のとおりです。

a.数百メガバイトや数GBのファイルなど、大きなファイルを保存する場合のパフォーマンスが比較的高いです。 HDFS はメタデータを使用してファイルを管理し、メタデータに関連するディレクトリやブロックの情報は NameNode のメモリに保存されるため、ファイル数が増加すると NameNode のメモリを大量に占有することになります。小さなファイルが大量にあると、メモリを大量に占有し、分散ストレージ全体のパフォーマンスが低下するため、大きなファイルを保存する場合は HDFS を使用する方が適切です。

b.書き込みが少なく、読み取りが複数回行われるビジネスに適しています。ビッグデータ分析ビジネスにおける処理モードは、一度書き込み、複数回読み取り、その後データ分析を実行するというものです。 HDFS のデータ転送スループットは比較的高いですが、データ読み取りレイテンシが比較的低いため、頻繁なデータ書き込みには適していません。

紀元前HDFS はマルチコピー データ保護メカニズムを使用します。通常の X86 サーバーを使用することで、データの信頼性を保証できます。仮想化環境での使用はお勧めしません。

（２）セフ

現在、Ceph は最も広く使用されているオープンソースの分散ストレージ システムであり、多くのメーカーによってサポートされています。多くのハイパーコンバージド システムの分散ストレージは、Ceph に基づいて高度にカスタマイズされています。さらに、Ceph は、それぞれのストレージ システムをサポートするための LINUX システムと OpenStack の「標準構成」となっています。 Ceph は、オブジェクト ストレージ、ブロック デバイス ストレージ、ファイル システム ストレージ サービスを提供できます。 3 つの異なるタイプのストレージ サービスを同時にサポートする機能は、分散ストレージ システムでは珍しいものです。

a. Ceph は HDFS のメタデータ アドレス指定ソリューションを使用せず、バランスの取れたデータ分散と高い並列性を備えた CRUSH アルゴリズムを使用します。さらに、ブロック ストレージ機能をサポートすることで、データの一貫性が強化され、従来の集中型ストレージと同様のユーザー エクスペリエンスを実現できます。

b.オブジェクト ストレージ サービスである Ceph は、Swift および S3 API インターフェースをサポートしています。ブロック ストレージに関しては、シン プロビジョニング、スナップショット、クローン作成がサポートされています。ファイル システム ストレージ サービスに関しては、Posix インターフェイスとスナップショットをサポートしています。ただし、Ceph のファイル サポートの現在のパフォーマンスは、他の分散ストレージ システムと同等ですが、展開が若干複雑で、パフォーマンスが若干劣っています。 Ceph は通常、ブロックおよびオブジェクトのストレージに使用されます。

紀元前Ceph は、事前の計画と設計が必要で、技術チームに対する要件が比較的高い分散型ソリューションです。特に Ceph を拡張すると、バランスのとれたデータ分散特性により、ストレージ システム全体のパフォーマンスが低下します。

（３）スウィフト

主にオブジェクトストレージを対象としています。 Ceph が提供するオブジェクト ストレージ サービスに似ています。主に非構造化データストレージの問題を解決するために使用されます。 Ceph のオブジェクト ストレージ サービスとの主な違いは次のとおりです。

a.クライアントがオブジェクト ストレージ システム サービスにアクセスすると、Swift はクライアントが Swift ゲートウェイにアクセスしてデータを取得することを要求します。 Ceph は、各ストレージ ノード上で実行されている OSD (オブジェクト ストレージ デバイス) を使用してデータ情報を取得します。別個のエントリポイントがなく、Swift よりも柔軟性があります。

b.データの一貫性の点では、Swift のデータは最終的に一貫性があり、大量のデータを処理する際の効率が高くなります。ただし、データの一貫性に対する要件は高くないが、データ処理の効率性に対する要件が比較的高いオブジェクト ストレージ ビジネスで主に使用されます。 Ceph はクラスター全体で常に強力な一貫性を保ちます。主な適用シナリオは、OpenStack では、オブジェクト ストレージ サービスが Ceph ではなく Swift を使用することです。

3. 分散理論の簡単な分析

1. 一貫性と可用性

異常の存在のため、分散ストレージ システムは、多くの場合、データを複数のコピー (それぞれレプリカと呼ばれる) に冗長的に格納するように設計されます。この方法では、ノードに障害が発生した場合、他のレプリカからデータを読み取ることができます。分散ストレージ システムにおけるフォールト トレランス技術の唯一の手段はレプリケーションであると言えます。複数のレプリカが存在するため、レプリカ間の一貫性をどのように確保するかが、分散システム全体の理論的な中核となります。

データの一貫性という言葉は、日常の開発やさまざまな記事でよく見かけます。何かのデータが矛盾しているために損失が発生し、すぐに修復する必要があるという話をよく耳にします。一貫性にはいくつの種類がありますか?

a.時間一貫性: すべてのデータ コンポーネントのデータがいつでも完全に一貫していることを要求します。

b.トランザクションの一貫性: トランザクションの一貫性は、トランザクションの開始前とトランザクションの完了後にのみ存在します。トランザクション中にデータが不整合になる可能性があります。たとえば、A が B に 100 元を送金し、A が 100 元を差し引き、B が 100 元を加算します。取引の開始前と取引の完了後、両者のアカウントが一致していることが保証されます。これはトランザクションの一貫性です。しかし、取引中に、Aが100元を差し引いたが、Bが100元を追加しなかった可能性があります。これは矛盾です。

紀元前複数の異なるスタンドアロン トランザクションを含むアプリケーションでは、すべてのスタンドアロン トランザクションが完了する前と完了した後のみ、データが完全に一貫しています。

実際には、これら 3 種類の一貫性だけでは複雑な状況を明確に説明することは難しいため、一貫性モデルを導入しました。ここでは、強いものから弱いものまで、いくつかの一般的な一貫性モデルを簡単に紹介します。

A. 線形化可能性

強力な一貫性とも呼ばれ、シングルコア プロセッサのみを備えているとみなすことも、データのコピーが 1 つだけあり、すべての操作がアトミックであるとみなすこともできます。

上の図に示すように、イベント e1 と e2 について、イベント e1 の応答がイベント e2 の呼び出しの前である場合、e1 は e2 の前に発生すると言います。

同じスレッドの場合、前のイベントは次のイベントの前に発生する必要があります。ただし、異なるスレッド上の 2 つのイベントの場合、タイムライン上でそれらのイベントの間に交差がない場合にのみ、先行発生関係が存在します。下の図の event2 と event3 のように、交差するイベントの場合、2 つのイベントの間には「前に発生する」関係はありません。私たちが求めている合法的な順次実行プロセスの場合、2 つの順序は任意です。

B. 順序一貫性

順次一貫性は厳密な一貫性よりも弱いです。変数への書き込み操作は必ずしも瞬時に確認される必要はありませんが、異なるプロセッサによる変数への書き込み操作は、分散システム内のプロセッサが異なるノードに置き換えられる可能性があるすべてのプロセッサで同じ順序で確認される必要があります。

2 つのスレッド A と B が同時に実行されているとします。スレッド A は 3 つの操作で構成され、プログラム内での順序は A1->A2->A3 です。スレッド B にも 3 つの操作があり、プログラム内での順序は B1->B2->B3 です。順次一貫性モデルにおける効果が上記の 2 つの図のようになると仮定します。

C. 因果関係の一貫性

因果的一貫性は、順序的一貫性よりも弱い一貫性モデルです。順次一貫性では、すべての操作の順序が単一のプロセッサ (ノード) の順序に従う必要がありますが、因果一貫性では、因果関係のある操作のみが順次一貫していることが要求されます。

簡単に言えば、誰かがあなたに質問をし、あなたが答える場合、その 2 つは因果関係にありますが、質問する前に答えを与えると、因果関係に違反することになります。たとえば、ノード 1 がデータ A を更新し、ノード 2 がデータ A を読み取ってデータ B を更新する場合、ここでのデータ B はデータ A に基づいて計算される可能性があるため、因果関係があります。ただし、ノード 3 が最初に B が更新され、次に A が更新されたことを認識した場合、因果一貫性は破壊されます。

D. 結果的一貫性

実際、強い一貫性を除いて、他の一貫性は結果的一貫性と見なすことができます。ただし、さまざまな一貫性モデルのさまざまな要件に基づいて、多くの特定の一貫性モデルが派生しています。もちろん、最も単純な結果整合性では、中間の変更の順​​序に注意を払う必要はなく、特定の時点での一貫性を確保するだけで済みます。ただ、この特定の時点は、さまざまなシステムやさまざまなビジネスに基づいて測定する必要があるだけです。最終的な一貫性が達成される前は、任意の値が返される可能性があり、これらの値に関する順序の保証はありません。

E. 可用性

可用性とは、「読み取りと書き込みが常に成功する」こと、つまりサービスが常に利用可能であり、応答時間が正常であることを意味します。分散システムが利用可能であるためには、障害が発生していないすべてのノードがすべての要求に応答する必要があります。したがって、システムの可用性を測定する場合、通常はダウンタイムで計算します。

通常、システムの可用性について説明するときは、Taobao のシステムの可用性は 5 ナインに達することができると言います。これは、可用性レベルが 99.999% であること、つまり、年間のダウンタイムが (1-0.99999)36524*60 = 5.256 分を超えないことを意味し、これは非常に高い要件です。

優れた可用性とは、主に、ユーザー操作の失敗やアクセス タイムアウトなどのユーザー エクスペリエンスの低下を招くことなく、システムがユーザーに適切にサービスを提供できることを意味します。分散システムには、負荷分散、Web サーバー、アプリケーション コード、データベース サーバーなど、多くの上流システムと下流システムが存在します。いずれかのノードが不安定になると、可用性に影響する可能性があります。

F. 分散システムの一貫性

2000 年 7 月、カリフォルニア大学バークレー校の Eric Brewer 教授が ACM PODC カンファレンスで CAP 予想を提唱しました。 2年後、MITのセス・ギルバートとナンシー・リンチがCAPを理論的に証明しました。その後、CAP 理論は分散コンピューティングの分野で正式に認められた定理となりました。

CAP 理論の概要: 分散システムは、一貫性、可用性、およびパーティション耐性の 3 つの要件のうち、最大で 2 つしか同時に満たすことができません。

CAP における一貫性は、すべてのノードが同時に同じデータを参照すること、つまり線形一貫性である点に留意する必要があります。

一貫性は次の 2 つの側面から見る必要があります。

（１）クライアントの観点から見ると、複数のプロセスが同時にアクセスする場合、非分散データベースでは、更新されたデータが後続のアクセスで参照でき、すべてが強く一貫性があることが求められます。

（２）サーバー側から見ると、更新されたデータをできるだけ早くシステム全体に配布し、最終的な一貫性を実現するための時間枠を短縮することが、システムの可用性とユーザーエクスペリエンスを向上させる上で非常に重要な側面です。

次の式を参照してください。

N — データのコピー数

W — データの更新時に書き込みを完了することが保証される必要があるノードの数

R — データを読み取るときに読み取るノードの数

（１）W+R>Nの場合、書き込みノードと読み取りノードが重複し、強い一貫性が保たれます。たとえば、マスター 1 つとスレーブ 1 つの同期レプリケーションを持つ一般的なリレーショナル データベースの場合、N = 2、W = 2、R = 1 となり、マスター データベースまたはスレーブ データベースから読み取られたデータは一貫しています。

（２）W+R<=Nの場合、それは弱い一貫性である。例えば、マスター 1 台とスレーブ 1 台の非同期レプリケーションを持つリレーショナル データベースの場合、N=2、W=1、R=1 で、スレーブ データベースを読み取ると、マスター データベースで更新されたデータを読み取ることができない可能性があるため、弱い一貫性になります。

分散システム用。 Pは基本要件です。 3 つの CAP のうち、CA と P の間でトレードオフを行い、P を向上させるように最善を尽くすしかありません。

2 つのシステムが含まれます: A** なしの CP、C** なしの AP

上で挙げた HDFS、Ceph、Swift はいずれも A なしの CP の範疇に属しますが、完全に A なしというわけではありません。一定の可用性を実現するために、レプリカ数は N>=3 に設定されるのが一般的です。 N、W、R のさまざまな組み合わせにより、可用性と一貫性のバランスが保たれ、さまざまなアプリケーション シナリオに適応できます。

さて、現実には、C のない AP のケースもいくつかあります。CAP 図に示されているように、それらのほとんどは Nosql、CoachDB、および Cassandra データベースです。シナリオは何ですか?

実際、Xiaomi での携帯電話の購入ラッシュや 12306 での列車のチケットの購入ラッシュなど、正確さが求められない場面もあります。最初の数秒で商品を閲覧すると、ページに在庫があることが通知される場合があります。製品を選択して注文する準備ができたら、注文が失敗し、製品が売り切れたというメッセージが表示されます。これは実際には、まずシステムが A (可用性) の点で通常のサービスを提供できることを確認し、次にデータの一貫性の点でいくらか犠牲を払うことを意味します。

2. データ配信

分散システムと従来の単一マシン システムの違いは、データを複数のノードに分散し、複数のノード間で負荷分散を実現できることです。データ配信には主に 2 つの方法があります。 1つはハッシュ分散であり、例えばコンシステントハッシュはシステムを次のように表す。

Amazon の Dynamo システム、Openstack の Swift システム。もう一つの方法はシーケンシャル分散、つまり各テーブル上のデータが主キーに従って全体として順序付けられるというもので、代表的なシステムは Google の Bigtable システムです。 Bigtable は、主キーに基づいて大きなテーブルを順序付けられた範囲に分割し、各順序付けられた範囲がサブテーブルになります。

A. ハッシュ分布（Swift）

ハッシュ関数のハッシュ特性は非常に優れており、ハッシュ方式によりクラスター内でデータをより均等に分散できます。さらに、ハッシュ方式で記録する必要があるメタデータも非常にシンプルです。各ノードは、ハッシュ関数の計算方法とモジュールのサーバー数を知るだけで、処理されたデータがどのマシンに属するかを計算することができます。

ただし、ハッシュ特性が優れたハッシュ関数を見つけるのは困難です。これは、主キーに従ってハッシュ化を行うと、同じユーザー ID のデータが複数のサーバーに分散され、同じユーザー ID の複数のレコードを一度に操作することが困難になるためです。ユーザー ID に従ってハッシュ化を実行すると、「データ スキュー」問題が発生しやすくなります。つまり、一部の大規模ユーザーのデータ量は非常に大きく、クラスターの規模に関係なく、これらのユーザーは常に 1 つのサーバーによって処理されます。

大規模ユーザー問題に対処するには、一般的に 2 つの方法があります。 1 つの方法は手動で分割することです。つまり、システム内の大規模ユーザーをオフラインとしてマークし (たとえば、MapReduce ジョブを実行する)、これらの大規模ユーザーのデータ量に基づいて複数のサーバーに分割します。これは、ハッシュ分散に基づいてこれらの大規模ユーザーに対して特別な処理を施すことに相当します。

もう 1 つの方法は自動分割です。つまり、データ分散アルゴリズムを動的に調整して、大規模ユーザーのデータを複数のサーバーに自動的に分割できます。 2 つのアルゴリズムが含まれています。

1 つは従来のハッシュ アルゴリズムです。データにアクセスするときは、まずハッシュ値が計算され、次にメタデータ サーバーにクエリが実行されて、ハッシュ値に対応するサーバーが取得されます。このアルゴリズムでは、サーバーのオンラインおよびオフライン操作によって大量のデータ移行が発生し、本番環境には適していません。

別の一貫性ハッシュ (分散ハッシュ テーブル、DHT) アルゴリズム。アルゴリズムの考え方は次のとおりです。システム内の各ノードにランダムなトークンを割り当て、これらのトークンがハッシュ リングを形成します。データ保存操作を実行する場合、まずキー（主キー）のハッシュ値が計算され、時計回り方向にハッシュ値以上の最初のトークンが配置されているノードに保存されます。一貫性ハッシュの利点は、ノードが追加または削除された場合、ハッシュ リング内の隣接ノードにのみ影響し、他のノードには影響がないことです。

上の図に示すように、アルゴリズム自体の特性により、ディスクをより均等に分散された仮想パーティションに分割できます。各仮想パーティションはハッシュ リング上のノードです。リング全体は 0 から最大値の 32 ビットまでの間隔であり、端から端まで接続されています。データ（またはデータ名）のハッシュ値を計算すると、ハッシュリングの特定の間隔に必然的に収まり、その後時計回り方向にノードが見つかります。そして、このノードはデータが保存される場所です。ノードが 1 つしかなく、32 までノードが見つからない場合、データは最初の一意のノードにあることがわかります。

データの全体の場所は、前述の一貫したアルゴリズムに基づいており、処理のために要求をデバイスにリダイレクトします。

（１）オブジェクトストレージでは、アカウント名、コンテナ名、オブジェクト名の組み合わせで場所を識別します。この一意の識別子から整数を計算できます。

（２）ストレージデバイスに関しては、Swiftは仮想パーティションテーブルを構築します。テーブルのサイズはクラスターの作成時に決定されます (通常は数十万)。このテーブルは実際には配列です。

（３）整数値とこの配列は、一貫性のあるハッシュアルゴリズムを通じて配列内の整数の位置を決定するために使用することができます。

原則として、一貫性アルゴリズムはデータのバランスと単調性を確保し、データの分散を回避し、データの一貫性を効果的に確保して、負荷を可能な限り特定のキャッシュ領域にマッピングできるようにします。

一貫性ハッシュ アルゴリズムがサービスを提供するノードが少なすぎると、ノードの分散が不均一になるため、データ スキューの問題が発生しやすくなります。したがって、実際のアプリケーションでは、仮想ノードの数は通常 32 より大きい値に設定され、少数のサービス ノードでも比較的均一なデータ分散を実現できます。

B. シーケンシャル分散（Bigtable）

ハッシュハッシュはデータの秩序性を破壊し、ランダム読み取り操作のみをサポートし、順次スキャンはサポートしません。一部のシステムでは、アプリケーション層で妥協が生じる可能性があります。たとえば、インターネット アプリケーションでは、多くの場合、データをユーザーごとに分割し、ハッシュ方式でデータを配布します。同じユーザーのデータは同じストレージノードに分散されるため、同じユーザーのデータの順次スキャンが可能になります。アプリケーション層は、複数のユーザーにわたる操作上の問題を解決します。さらに、この方法では、一部のユーザーにとってデータが多すぎるという問題が発生する可能性があります。ユーザーのデータは 1 つのストレージ ノードに制限されるため、分散ストレージ システムの複数マシンの並列処理機能を活用することはできません。

分散テーブル システム (Bigtable) では、順次分散が一般的です。一般的な方法は、大きなテーブルを連続した範囲に順番に分割することです。各範囲はサブテーブルと呼ばれます。マスター コントロール サーバーは、特定の戦略に従ってこれらのサブ テーブルをストレージ ノードに割り当てる役割を担います。

図に示すように、ユーザーテーブルの主要なキー範囲は1〜7000で、分散ストレージシステムの複数のサブテーブルに分割され、データの範囲1〜1000、1001〜2000、... 6001〜7000です。メタテーブルは、より大きなクラスターサイズをサポートするように設計されています。元のインデックスレイヤーを2つのレイヤーに分割し、メタテーブルを使用して、ユーザーのサブテーブルが配置されているノードを維持し、それによりルートノードの負担を軽減します。

シーケンシャル分布は、B+ツリーデータ構造に似ています。各サブテーブルは、リーフノードに相当します。データが挿入されて削除されると、一部のサブテーブルが非常に大きくなり、一部は非常に小さくなり、不均一なデータ分布が生じる場合があります。順次分布が採用されている場合、システム設計中にサブテーブルの分割とマージを考慮する必要があり、システムの複雑さが大幅に向上します。

C.クラッシュ分布

クラッシュアルゴリズム、フルネームは、複製されたデータの制御されたスケーラブル、分散型配置です。厳密に言えば、クラッシュアルゴリズムは実際にはハッシュアルゴリズムに基づいています。マッピング方法が一貫したハッシュとは異なるというだけです。 CEPH分布プロセスを使用して説明します。

CEPH分布データのプロセス：最初に、データxのハッシュ値を計算し、結果のモジュラスとPGの数を取得して、データxに対応するPG数を取得します。次に、PGはCrushアルゴリズムを介してOSDのセットにマッピングされます。最後に、データXはPGに対応するOSDに保存されます。注：PGは配置グループの略です。

このプロセスには、2つのマッピングが含まれます。 1つ目は、データXからPGのマッピングです。 PGがストレージノードと見なされる場合、従来のハッシュアルゴリズムは同じです。違いは、PGが抽象的なストレージノードであり、物理ノードの追加または出発では増加または減少しないため、PGへのデータのマッピングは安定しています。

Dynamoを例にとると、このプロセスではPGが2つの役割を果たします。最初の役割は、データパーティションを分割することです。各PGは同じデータ間隔を管理するため、データをPGで均等に分散できます。 2番目の関数は、ダイナモのトークンとして、つまりパーティションの場所を決定することです。実際、これはダイナモのパーティションの数を修正し、パーティションの数を仮想ノードの数に等しく保つことと同じ原則です。

Cephを例にとると、Crush Algorithmは、データを2回マッピングしてデータを保存および取得する方法を決定することにより、データストレージの場所を計算します。 Crushは、CEPHクライアントが集中サーバーやプロキシを使用するのではなく、OSDと直接通信できるようにします。

データストレージと検索に対するアルゴリズム的に決定されたアプローチを通じて、CEPHは、そのスケーラビリティに対する単一の障害、パフォーマンスのボトルネック、および物理的制限を回避します。クラッシュにはクラスターのマップが必要であり、クラッシュマップを使用してOSDの間で擬似ランダムリーを保存および取得し、クラスター全体にデータを均等に配布します。

3。コピー

分散ストレージシステムの高い信頼性と高可用性を確保するために、データは一般にシステム内の複数のコピーに保存されます。レプリカが配置されているストレージノードが失敗すると、分散ストレージシステムは自動的に他のレプリカにサービスを切り替えることができ、それにより自動障害トレランスを実現できます。分散ストレージシステムは、レプリケーションプロトコルを介してデータを複数のストレージノードに同期させ、複数のコピー間のデータの一貫性を確保します。

A.強力な同期複製

クライアントは書き込み要求をプライマリレプリカに送信し、プライマリレプリカは他のバックアップレプリカに書き込み要求をコピーします。一般的な慣行は、操作ログ（コミットログ）を同期することです。プライマリレプリカは最初に操作ログをバックアップレプリカに同期させ、バックアップレプリカは操作ログを再現し、完了後にプライマリレプリカに通知します。次に、プライマリコピーはローカルマシンを変更し、すべての操作が完了するまで待機してから、クライアントに書き込みの成功を通知します。以下の図の複製プロトコルでは、クライアントが書き込み成功を返す前に、マスターとスレーブデバイスを正常に同期する必要があります。このプロトコルは、強力な同期プロトコルと呼ばれます。

すべてのレプリカの数がn、つまりn> 2、つまりバックアップレプリカの数が1を超えると仮定します。その後、強力な同期プロトコルを実装すると、プライマリレプリカは操作ログをすべてのバックアップレプリカに同時に送信し、返信を待つことができます。少なくとも1つのバックアップレプリカが成功を返す限り、クライアントに操作の成功を通知することができます。強力な同期の利点は、一次コピーが失敗した場合、完全なデータを備えた少なくとも1つのバックアップコピーがあり、分散ストレージシステムがデータの損失を心配することなくサービスを最新のバックアップコピーに自動的に切り替えることができることです。

B.非同期複製

強い同期に対応する複製モードは、非同期複製です。非同期モードでは、プライマリレプリカはバックアップレプリカからの応答を待つ必要はありません。ローカルの変更が成功している限り、書き込み操作が成功していることをクライアントに通知する必要があります。さらに、プライマリレプリカは、個別の複製スレッドなどの非同期メカニズムを介して、クライアントの変更操作を他のレプリカにプッシュします。非同期複製の利点は、システムの可用性が向上しますが、一貫性が低いことです。プライマリコピーで回復不可能な障害が発生した場合、更新操作の最後の部分が失われる可能性があります。

C. NWRレプリケーション

複数のストレージノードへの書き込みに基づいた複製されたワイトプロトコルも、分散ストレージシステムで使用できます。たとえば、ダイナモシステムのNWRレプリケーションプロトコルは、nはレプリカの数、wは書き込み操作のレプリカの数、rは読み取り操作のレプリカの数です。

NWRプロトコルでは、複数のレプリカがプライマリとバックアップを区別しなくなりました。クライアントは、wレプリカにデータを書き込み、特定の戦略に従ってRレプリカからデータを読み取ります。 W+r> nである限り、読み取りレプリカの少なくとも1つに最新のアップデートが含まれていることが保証されています。ただし、このプロトコルの問題は、異なるレプリカの操作の順序が一貫していない可能性があり、複数のレプリカから読み取ると競合が発生する可能性があることです。この方法は実際のシステムではまれであり、推奨されません。

4。分散プロトコル

多くの分散プロトコルがあり、その中には2相のコミットとPaxosプロトコルが最も代表的です。 2フェーズのコミットプロトコル（2PC）または3相のコミット（3PC）を使用して、複数のノードにわたって動作の原子性を確保するために、つまり、複数のノードにわたる操作がすべてのノードで正常に実行されるか、完全に失敗します。 Paxosプロトコルは、複数のノードが投票でコンセンサスに達するようにするために使用されます（たとえば、どのノードがマスターノードであるか）。

A.二相コミット

第2段階の提出のアルゴリズムのアイデアは、次のように要約することができます。参加者は、コーディネーターに操作の成功または失敗を通知し、コーディネーターは、各参加者がすべての参加者のフィードバック情報に基づいて操作を提出するか、操作を終了するかどうかを決定します。

（1）リクエストフェーズ（投票）：

取引コーディネーターは、コーディネーターにトランザクションの参加者に、トランザクションを提出またはキャンセルする準備をするように通知し、投票プロセスに入ります。投票プロセス中、参加者はコーディネーターに自分の決定を通知します。

（2）提出段階（実行）：

この段階では、コーディネーターは最初の段階の投票結果に基づいて決定を下します：送信またはキャンセル、およびコーディネーターは、すべての参加者がトランザクションの提出に同意した場合にのみ、すべての参加者にトランザクションを提出するように通知します。参加者は、コーディネーターからメッセージを受信すると応答操作を実行します。

（3）2段階の提出で解決できない問題

a）参加者が投票を遅らせた場合、ステージ全体が待機状態になりますが、これはタイムアウトメカニズムによって解決できます。

b）コーディネーターがエラーを犯し、参加者もエラーを犯した場合、2つの段階ではトランザクション実行の整合性を保証できません。

Commitメッセージを送信した後、コーディネーターがダウンしたことを考慮してください。このメッセージを受け取った唯一の参加者もダウンしました。

その後、コーディネーターが選挙契約を通じて新しいコーディネーターを作成したとしても、取引のステータスは不確実であり、取引が提出されたかどうかは誰にもわかりません。

B. 3段階の提出

3段階の提出には、Cancommit、Precommit、Docommitの3つの段階があります

（1）Cancommit段階は、2つの段階の要求段階とほぼ同等です。 Docommitは、2つの段階のコミットステージとほぼ同等です。 Precommitは準備段階でのバッファーであり、各参加ノードの状態が最終的なコミット段階の前に一貫していることを保証します。

（2）第3段階の提出物は、2段階の提出の第1段階と2番目の段階の間に準備段階（前提条件）を挿入します。そのため、コーディネーターが提出またはABORTを解決できない「不確実な状態」にある参加者が引き起こす可能性のある長い遅延の問題を解決できます。

（3）提出の3つの段階で解決できない問題

コーディネーターが事前委員会を入力した後にコミットリクエストを発行し、1人の参加者のみがコミット操作を受信して​​実行すると仮定した場合、他の参加者はネットワーク割り込みを受け取らないと仮定すると、3PCに従って中止操作を選択します。現時点では、システムステータスは一貫性がありません。

C、Paxosプロトコル

Paxosについて話すには、まずビザンチンの問題から始めなければなりません。ストーリーの背景は次のとおりです。ビザンチンは現在のトルコのイスタンブールにあり、東ローマ帝国の首都です。ビザンチンのローマ帝国は当時広大だったため、防衛目的のために、各軍隊は非常に遠くに分離されており、将軍はメッセンジャーにしか頼ってニュースを広めました。戦争中、ビザンチン軍のすべての将軍は、敵のキャンプを攻撃する前に勝つ機会があるかどうかを決定するためにコンセンサスに達しなければなりません。しかし、陸軍は裏切り者と敵のスパイを持っている可能性があり、これらの裏切り者将軍は意思決定プロセスを混乱または移動させるでしょう。現時点では、反乱の既知のメンバーがいるとき、残りの忠実な将軍は、ビザンチンの一般的な問題である裏切り者の影響を受けずに合意に達しました。

仮定を否定し、非ビザンチンモデルの定義を示します。

（1）一貫性モジュールの動作は任意の速度で実行でき、実行が故障し、故障後に再び再起動して実行できます。

（2）一貫性モジュールは、非同期に情報通信を送信します。通信時間は任意に長くなる可能性があります。情報は送信中に失われる可能性があります。また、同じ情報を繰り返し送信できます。複数の情報の順序はarbitrarily意的です。しかし、1つのことは、情報を改ざんすることは許可されていないことです。

このことから、Paxosの基本的な2つの段階を締めくくりました。ステージを準備し、ステージを受け入れます。これら2つの段階の論理は非常に複雑であり、相互信頼アルゴリズムの基礎です。この記事では、深みのある解釈を行うつもりはありません。興味のある読者は、本「ブロックチェーンアルゴリズム」を参照できます。

D.ラフトプロトコル

Raftは、Paxosの単純化されたバージョンである複製された障害トレラントの略語です。

分散システムでは、システムの堅牢性、可用性、データセキュリティを改善する最も正しい方法は何ですか？もちろん、複数のバックアップ、サービスの複数のバックアップ、およびデータの複数のバックアップに依存し、単一ポイントを削除して、一部の関連コンポーネントが吊り下げられていても、システムが健康的なサービスを提供できるようにします。

単一のポイントを削除して固定された権限を持たないのは良いことですが、問題は、情報が失われる可能性のある環境で、誰の意見に基づいているということです。これは非常に困難です（コミュニケーションがどれほど重要かがわかります）！

1990年に提案されたとき、それを理解できる人はほとんどいませんでした。著者がGoogleなどのチームの実用的なレクリエーションや再解釈を含む、著者が何度も簡素化し、説明した後、徐々に実際の基準になり、すべての人に理解され、受け入れられるまで10年以上経過しました。しかし、これまで、非常に抽象的なPaxosアルゴリズムを理解できる人はほとんどいませんでした。

方法は簡単です！これは永遠の真実です。 RAFTの目標は、理解し、構築しやすい分散一貫性プロトコルを構築し、簡単に理論が正しいことを確認することです。

RAFTプロトコルがテキストに従って読み取られている場合でも、時間がかかります。この記事では、一般的な方法を使用して説明します。

ラフトの一般的な原則は、リーダーの選択のアイデアを備えたアルゴリズムです。クラスター内の各ノードには、3つの可能な役割があります。

（1）リーダー

クライアントコミュニケーションへの入り口と、DATA内同期のイニシエーター。通常、クラスターにはリーダーノードが1つしかありません。

（2）フォロワー：

非リーダーノードは、リーダーからのデータ要求を受動的に受け入れます

（3）候補者：

リーダーの選挙段階にのみ存在する一時的な役割。ノードがリーダーになりたい場合、投票要求を開始し、候補者自体になります。選挙が成功した場合、それは候補者になり、そうでなければフォロワーに返されます。

アルゴリズムは、リーダーの選挙とログコピーの2つのプロセスで構成されています。

（1）選挙プロセス：（ 5つのノードがあるとします、S1〜S5）

a.最初の状態では、誰もが平等なフォロワーです。では、誰が従うべきですか？上司を選ぶ必要があります。誰もが移動する準備ができており、各フォロワーは内部のランダムタイマーを維持します。

b.時間が来たときにタイマーに連絡するために誰もイニシアチブを取得しない場合、それは候補者になり、他の人に投票要求（RequestVote）を発行します。 S1とS3が候補になると仮定します

紀元前同じ状態の候補者の場合、フォロワーは最初の最初の投票戦略を採用します。フォロワーの半数以上が彼がリーダーシップに適していると考えている場合、おめでとうございます、新しいリーダーが現れました。 S3が新しいリーダーになった場合。

d. S1残念ながら、誰もこの悲劇的な候補者を選ぶことをいとわないので、それは弟の状態に正直に変換されるだけです。

e.同様に、タイマー期間中に兄からの接触を受けていない場合、兄がすでにひざまずいている可能性が非常に高いです。下の図に示すように、すべての弟が再び動きそうになっており、新しいラウンドの（学期）選挙が始まっています。

（2）ログレプリケーション：（ 5つのノードがあるとします、S1〜S5）

a.リーダーは、分散トランザクションでコーディネーターの役割を果たします。データの更新があるたびに、2フェーズのコミットが生成されます。リーダーがデータ操作のリクエストを受信した場合、ローカルデータを急いで更新しないでください（データはディスクで持続します）が、対応するログを生成し、すべてのフォロワーにログを生成するリクエストをブロードキャストします。

b.各フォロワーには、リクエストを受け取った後に2つの選択肢があります。1つはリーダーのコマンドに従い、ログを書き、成功を返すことです。もう1つは、いくつかの条件が満たされない場合、フォロワーはそれがリーダーの命令に従うべきではないと信じており、偽りを返すことです。

紀元前この時点で、フォロワーの半数以上がログを正常に書き込む場合、リーダーは第2段階の提出を開始します。正式にデータを書き、それをフォロワーにブロードキャストします。フォロワーはまた、それ自体の状況に従って書くか書かないかを選択し、結果をリーダーに返します。最後に、すべてのノードのデータは契約に達します。

d.これらの2つの段階のいずれかがフォロワーの半分以上が虚偽を返しているか、まったく返さない場合、分散トランザクションは失敗します。現時点ではロールバックプロセスはありませんが、データはほとんどのノードで実際には提出されないため、後続のプロセスで上書きされます。

RAFTプロトコルは、_Leader_の強力なリーダーシップを保証し、クライアント_Leadingと執筆は_Leader__を通じて非常に一貫していますが、一部の学生は分散の価値はどこにありますか？ロードバランスはロードバランシングにするにはどうすればよいですか？実際には、マルチラフトアーキテクチャを採用し、アプリケーションを組み合わせて、さまざまなアプリケーションが異なるリーダーノードを選択してバランスを削減します。

5。クロスコンピュータールームの展開

分散システムでは、クロスコンピューターの部屋の問題は常に困難でした。コンピュータールーム間のネットワークには大きな遅延があり、不安定です。クロスコンピュータールームの問題には、主にデータの同期とサービススイッチングの2つの側面が含まれています。 3つのクロスコンピュータールームの展開ソリューションがあります。全体的なクラスタースイッチング、シングルクラスタークロスコンピュータールーム、Paxosマスターおよびレプリカの選択です。以下は個別に導入されています。

A.全体的なクラスタースイッチング

全体的なクラスタースイッチングが最も一般的なソリューションです。図に示すように、システムが2つのコンピュータールームに展開されているとします。コンピュータールーム1とコンピュータールーム2です。2つのコンピュータールームは独立したままで、各コンピュータールームには個別の一般的なコントロールノードが展開され、各一般的なコントロールノードにはバックアップノードがあります。メインコントロールノードが失敗すると、コンピュータールームのバックアップノードをメインコントロールノードに自動的に切り替えて、サービスを提供し続けることができます。さらに、同じ数のコピーが両方のコンピュータールームに展開されます。たとえば、コンピュータールーム1のデータシャードAに保存されているコピーはA11とA12であり、コンピュータールーム2に保存されているコピーはA21とA22です。ある時点で、コンピュータールーム1はメインのコンピュータールームで、コンピュータールーム2はバックアップコンピュータールームです。

コンピュータールーム間のデータ同期方法は、強力な同期または非同期である可能性があります。非同期モードを使用すると、バックアップコンピュータールームのデータは常にメインのコンピュータールームの後ろに遅れます。ホストルームが全体的に失敗した場合、2つのオプションがあります。サービスをバックアップルームに切り替えて、データ損失のリスクに耐えます。または、ホストルームが回復するまでサービスを停止します。したがって、データが非同期である場合、メインとバックアップのコンピュータールームの切り替えは多くの場合マニュアルであり、ユーザーはビジネスの特性に従って「失われたデータ」または「停止サービス」を選択できます。

強力な同期モードを使用すると、バックアップコンピュータールームのデータはメインコンピュータールームと一致します。ホストルームが失敗した場合、手動の切り替えに加えて、自動スイッチングも採用できます。つまり、ホストルームのサービスを分散ロックサービスで検出できます。ホストルームが失敗すると、バックアップルームが自動的にホストルームに切り替えられます。

B.コンピュータールームを横切るシングルクラスター

図3-11に示すように、単一のクラスターを複数のコンピュータールームに展開すると、さまざまなデータシャードのメインとレプリカを異なるコンピュータールームに配置できます。各データフラグメントはコンピュータールーム1とコンピュータールーム2にあり、その中にはA1、B1、およびC1がメインコピー、A1、B1はコンピュータールーム1にあり、C1は1つの一般的なコントロールノードにしかありませんメインコントロールノードに。

この展開方法が採用されている場合、一般的なコントロールノードは、データ分布を実行するときにコンピュータールームの情報を考慮する必要があります。つまり、同じデータフラグメントの複数のコピーを複数のコンピュータールームに配布して、単一のコンピュータールームが通常のサービスに失敗し、影響を与えないようにします。

c、paxosマスターコピーを選択します

Paxosプロトコルを使用してプライマリレプリカを選択する場合、各データシャードの複数のレプリカがPaxosレプリケーショングループを形成します。図に示すように、B1、B2、B3、およびB4は複製グループを形成します。ある時点で、B1は複製グループの主要なレプリカです。 B1が失敗すると、他のレプリカはメインレプリカに切り替えようとします。 Paxosプロトコルは、1つのレプリカのみが成功することを保証します。このようにして、メインコントロールノードと作業ノードの間にリースを維持する必要はなく、メインコントロールノードの障害は作業ノードに影響しません。その利点は、全体的な制御ノードへの依存を減らすことができることであり、その欠点は、エンジニアリングの複雑さが高すぎて、すべての異常な状況をオフラインでシミュレートすることを困難にすることです。

4。分散ファイルシステム

分散ファイルシステムには2つの主な機能があります。1つは、ドキュメント、画像、ビデオなどのブロブタイプのデータを保存することです。もう1つは、分散テーブルシステムの持続層として機能することです。

1。Googleファイルシステム（GFS）

GFS、ビッグテーブル、MAP ReduceはGoogleのTroikaとして知られており、多くの基本的なサービスの礎石です。

GFSは2003年に分散ファイルシステムとして提案されました。これは、以前の多くの分散システムの前提とは大きく異なり、以下のシナリオに適用されます。

（1）コンポーネント障害は正常状態であり、断層トレランスメカニズムと自動負荷分散を提供し、分散ファイルシステムが安価なマシンで実行できると考えられています。

（2）大規模なファイルストレージの場合、システムの主なワークロードは大規模なストリーミングの読み取りであり、ライティング操作は主に付録モードで記述されており、ランダムな書き込みはほとんどありません。

（3）一度書いて、インターネット上のWebページストレージなど、複数回読む

GFSファイルは固定サイズのチャンク（チャンク）に分割され、マスターサーバーは、作成時に64ビットのグローバルにユニークなチャンクハンドルを割り当てます。 CSは、通常のLinuxファイルとしてディスクにチャンクを保存します。信頼性を確保するために、Chunkは異なるマシンの複数のコピーをコピーして、3つのコピーをデフォルトします。

マスターサーバーは、ファイルやチャンクネームスペース、ファイルとチャンク間のマッピング、チャンクの位置情報など、システムのメタデータを維持します。また、チャンクリース管理、ガベージコレクションの役に立たないチャンク、チャンクレプリケーションなど、システム全体のグローバルな制御を担当します。マスターサーバーは、ハートビートを通じてCSと定期的に情報を交換します。

クライアントは、GFSがアプリケーションに提供するアクセスインターフェイスです。これは、POSIX仕様に従わず、ライブラリファイルの形式で提供される専用のインターフェイスのセットです。クライアントがGFSにアクセスすると、最初にマスターサーバーノードにアクセスし、それと対話するCS情報を取得し、次にこれらのCSSに直接アクセスしてデータアクセス作業を完了します。

GFSのクライアントはファイルデータをキャッシュしないが、GFSのアプリケーション特性によって決定されるマスターサーバーで得られたメタデータのみをキャッシュすることに注意する必要があります。 GFSには2つの主要なアプリケーションがあります：MapReduceとBigTable。 MapReduceの場合、GFSクライアントはシーケンシャルな読み取りと書き込みを使用しており、ファイルデータをキャッシュする必要はありません。 Bigtableは、分散テーブルシステムとして、内部的にキャッシュメカニズムを実装します。さらに、クライアントキャッシュと実際のデータの一貫性を維持する方法は、非常に複雑な問題です。

HadoopのHDFSは実際にはGFSの単純化されたバージョンであり、Dr。Cuttingの「コピー」GFSの製品であることがわかります。それは火を盗むことの産物です。

2。Taobaoファイルシステム（TFS）

インターネットアプリケーションは、多くの場合、ドキュメント、写真、ビデオなどを保存する必要があります。Facebookアルバム、Taobao Pictures、Dropbox Documentsなどのユーザーによってアップロードされます。ドキュメント、写真、ビデオは一般にBLOBデータと呼ばれます。 BLOBファイルシステムの特徴は、データが執筆後に基本的に読み取り専用であり、更新操作がほとんどないことです。これは、Taobaoファイルシステム（TFS）の主な機能です。

TFSアーキテクチャはGFSを借用しますが、GFSとは大きく異なります。

（1）TFSは、ファイルディレクトリツリーを内部的に維持していません。ファイル名をファイルの物理アドレスにマップし、ファイルアクセスプロセスを簡素化できるフラットデータ組織構造があります。

（2）タバオの小さなファイルストレージの需要を満たし、さまざまなTaobaoアプリケーションで広く使用されている大規模な小さなファイルのランダム読み取りおよび書き込みアクセスパフォーマンスのために特別な最適化が行われました。

（3）HAアーキテクチャとスムーズな拡張が採用され、ファイルシステム全体の可用性とスケーラビリティが確保されます。

TFSクラスターは、2つの名前アーバーノード（1つのマスターと1つのバックアップ）と複数のDataServerノードで構成されています。名前サーバーは、ハートビートを介してDataSrverのステータスを監視します。名前サーバーはGFSのマスターと同等であり、DataServerはGFSのChunkServerと同等です。名前サーバーは、プライマリネームサーバーとバックアップネームサーバーに分かれています。プライマリネームサーバーのみがサービスを提供します。プライマリネームサーバーが失敗すると、ハートビートデーモンによって検出され、サービスをバックアップネームサーバーに切り替えることができます。各DataServerは複数のDSPプロセスを実行し、1つのDSPはマウントポイントに対応します。これは通常、独立したディスクに対応し、それにより複数のディスクを管理します。

TFSでは、多数の小さなファイル（実際のデータファイル）が大きなファイルに統合されます（これはHDFSで最適化および改善されます）。この大きなファイルはブロック（ブロック）と呼ばれます。各ブロックには、クラスターに一意の数字（ブロックID）があります。ファイルは、<ブロックID、ブロックオフセット>を使用して一意に決定できます。 TFSのブロックの実際のデータはDataServerに保存され、一般に64MBのサイズがあり、3つのコピーがデフォルトで保存されます。これはGFSのチャンクに相当します。アプリケーションクライアントは、TFSがアプリケーションに提供するアクセスインターフェイスです。アプリケーションクライアントはファイルデータをキャッシュしませんが、名前サーバーのメタデータのみをキャッシュします。

3。FacebookHaystackファイルシステム

2014年までに、Facebookには約4,000億の写真があり、合計サイズは30pbです。計算により、各写真の平均サイズは約100kbで30pb/260GBであると結論付けることができます。 1週間あたりのユーザーが追加する新しい写真の数は10億（合計サイズは60tb）であり、1秒あたりの新しい写真の平均数は109/7/40000（1日あたり40,000で計算）であり、1秒あたり約3800の書き込み操作であり、ピーク読み取り操作は1秒あたり数百万に達することがあります。

FacebookのフォトアルバムBackEndは、初期にNASベースのストレージを使用し、NASのNFSマウントを介してサービスを提供しました。その後、パフォーマンスとコストの考慮事項のために、Facebook Haystackは独立してアルバムデータを保存するために開発されました。

TFSと同様に、Facebook Haystackの新しいアーキテクチャは、主に過度の画像アクセス時間のあるファイルを解決します。主なアイデアは、同じ物理ファイルを複数の論理ファイルと共有することです。 Haystackアーキテクチャと読み取りリクエストのプロセスフローチャートは次のとおりです

Haystackアーキテクチャには、HayStack Directory、Haystack Store、Haystackキャッシュの3つの主要な部分があります。 Haystack Storeは、物理リールの形でストレージスペースを整理する物理的なストレージノードです。一般に、各物理リールは100GBなどの大きさであるため、10TBのデータを備えた物理リールは100しかありません。各物理リールは物理ファイルに対応するため、各ストレージノードの物理ファイルメタ情報は非常に小さいです。複数の物理ストレージノードの物理リールは、バックアップ用の論理リールを形成します。 Haystackディレクトリは、論理リールと物理リールの間の対応を保存します。各リールのサイズが100GBであると仮定すると、対応するリールの数は20pb / 100GB = 0.2MBであり、占有されているメモリは無視できます。 Haystackキャッシュは、主にCDNプロバイダーへの過度の依存の問題を解決するために使用され、最近追加された画像にキャッシュサービスを提供します。

Haystack画像の読み取り要求の一般的なプロセスは次のとおりです。ユーザーがページにアクセスすると、WebサーバーはHayStackディレクトリを要求してURLを作成します：http：// <cdn> / <cache> / <machine id> / <論理ボリューム、写真>、次に、各部品の情報に従ってCDN、キャッシュ、およびバックエンドヘイスタックストアストレージにアクセスします。 HayStackディレクトリは、URLを構築するときに部分を省略して、ユーザーがCDNを使用することなくHayStackキャッシュを直接要求するようにすることができます。 Haystackキャッシュが受け取った要求には、ユーザーブラウザのリクエストとCDNのリクエストの2つの部分が含まれています。 HayStackキャッシュは、リクエストを要求するユーザーブラウザとHaystackストアストレージノードから送信されたリクエストのみをキャッシュします。一般的に言えば、Haystackストアのストレージノードは、しばらく書いた後、上限の制限に達し、読み取り専用になります。したがって、書き込み可能なノードの画像は最近追加された画像であり、ホットデータです。

Haystackの書き込み要求のプロセス（画像アップロード）は次のとおりです。Webサーバーは、最初にHayStackディレクトリを要求して画像IDと書き込み可能な論理リールを取得し、それぞれの対応する物理リールにデータを書き込みます（一般的に3）。

Facebook HaystackやTaobao TFなどのファイルシステムは、一般にBlobファイルシステムと呼ばれます。それらはすべて、多数の小さな画像ファイルの問題を解決するため、アーキテクチャは非常に似ており、違いは含まれます。

（1）HayStackが100GBの論理リールサイズを選択するなど、論理リールサイズを選択し、TFSのブロックサイズは通常64MBです。

（2）HayStackはRAID 6を使用し、基礎となるファイルシステムはパフォーマンスが向上してXFSを使用します。 Taobaoは後にRAIDメカニズムを排除し、ファイルシステムでExt3を使用します。

（3）HaystackはAkamai＆LimelightのCDNサービスを使用していますが、Taobaoはすでに独自のCDNを使用しています。もちろん、Facebookは独自のCDNの構築も検討しています。

4。CDNコンテンツ配信ネットワーク

CDNのフルネームはコンテンツ配信ネットワークであり、コンテンツ配信ネットワークです。目的は、既存のインターネットに新しいネットワークアーキテクチャを追加することにより、ユーザーに最も近いネットワークの「エッジ」にWebサイトのコンテンツを公開することです。次の3つの目的を達成します

（1）分布、帯域幅、およびサーバーのパフォーマンスによって引き起こされるアクセス待ちの問題を解決し、サイト加速、オンデマンド、ライブブロードキャスト、その他のシナリオに適しています。これにより、ユーザーは近くの必要なコンテンツを取得し、インターネットネットワークの混雑を解決し、ユーザーのWebサイトへのアクセスの応答速度と成功率を改善できます。

（2）遅延を制御することは、間違いなく最新の情報技術の重要な指標です。 The intention of CDN is to minimize resources and ensure the consistency of information in the case of forwarding, transmission, link jitter, etc. as much as possible.

( 3 ) CDN 就是扮演者护航者和加速者的角色，更快准狠的触发信息和触达每一个用户，带来更为极致的使用体验。

如下图所示DNS 在对域名解析时不再向用户返回源服务器的IP ，而是返回了由智CDN 负载均衡系统选定的某个边缘节点的IP 。用户利用这个IP 访问边缘节点，然后该节点通过其内部DNS 解析得到源服务器IP 并发出请求来获取用户所需的页面，如果请求成功，边缘节点会将页面缓存下来，下次用户访问时可以直接读取，而不需要每次都访问源服务器。

Taobao 的CDN 架构是自研的，用于支持用户购物，尤其是“双11” 光棍节时的海量图片请求，图片存储在后台的TFS 集群中， CDN 系统将这些图片缓存到离用户最近的边缘节点。CDN 采用两级Cache ：L1-Cache 以及L2-Cache 。用户访问淘宝网的图片时，通过全局调度系统( Global Load Balancing )调度到某个L1-Cache 节点。如果L1-Cache 命中，那么直接将图片数据返回用户;否则，请求L2-Cache 节点，并将返回的图片数据缓存到L1-Cache 节点。如果L2-Cache 命中，直接将图片数据返回给L1-Cache 节点;否则，请求源服务器的图片服务器集群。每台图片服务器是一个运行着Nginx 的Web 服务器，它还会在本地缓存图片，只有当本地缓存也不命中时才会请求后端的TFS 集群，图片服务器集群和TFS 集群部署在同一个数据中心内。

对于每个CDN 节点，其架构如图4-11 所示。从图中可以看出，每个CDN 节点内部通过LVS+Haproxy 的方式进行负载均衡。其中， LVS 是四层负载均衡软件，性能好;Haproxy 是七层负载均衡软件，能够支持更加灵活的负载均衡策略。通过有机结合两者，可以将不同的图片请求调度到不同的Squid 服务器。

上图是CDN 的单节点架构，它有以下三个特点

(1) Squid 服务器构成淘宝单节点中的CDN 中的分布式缓存，这个实现比分布式缓存简单很多，因为不需要考虑数据持久化。

(2) 分级缓存，由于缓存数据有较高的局部性，在Squid 服务器上使用SSD+SAS+SATA 混合存储，图片随着热点变化而迁移，最热门的存储到SSD ，中等热度的存储到SAS ，轻热度的存储到SATA 。通过这样的方式，能够很好地结合SSD 的性能和SAS 、 SATA 磁盘的成本优势;

(3) 低功耗服务器定制， CDN 缓存服务是IO 密集型而不是CPU 密集型的服务，因此，选用Intel Atom CPU 定制低功耗服务器，在保证服务性能的前提下大大降低了整体功耗。

五、分布式键值系统

分布式键值系统是用于存储关系简单的半结构化数据，半结构化数据均封装成由键值对组成的对象，其中key 为唯一标示符;value 为属性值，可以为任何类型，如文字、图片，也可以为空;timestamp 为时间戳，提供对象的多版本支持。分布式键值系统以键值对存储，它的结构不固定，每一元组可以有不一样的字段，可根据需要增加键值对，从而不局限于固定的结构，适用面更大，可扩展性更好。

分布式键值系统支持针对单个键值对的增、删、查、改操作，可以运行在PC 服务器集群上，并实现集群按需扩展，从而处理大规模数据，并通过数据备份保障容错性，避免了分割数据带来的复杂性和成本。

总体来说，分布式键值系统从存储数据结构的角度看，分布式键值系统与传统的哈希表比较类似，不同的是，分布式键值系统支持将数据分布到集群中的多个存储节点。分布式键值系统可以配置数据的备份数目，可以将一份数据的所有副本存储到不同的节点上，当有节点发生异常无法正常提供服务时，其余的节点会继续提供服务。

1、 Amazon Dynamo

Dynamo 以很简单的键值方式存储数据，不支持复杂的查询。Dynamo 中存储的是数据值的原始形式，不解析数据的具体内容。Dynamo 主要用于Amazon 的购物车及S3 云存储服务。在实现过程中解决了如下问题：

Dynamo 采用一致性哈希将数据分布到多个存储节点中，概括来说：给系统中的每个节点分配一个随机token ，这些token 构成一个哈希环。执行数据存放操作时，先计算主键的哈希值，然后存放到顺时针方向的第一个大于或者等于该哈希值的token 所在的节点。一致性哈希的有点在于节点加入/ 删除只会影响到在哈希环相邻的节点，而对其他节点没影响。

A 、 Dynamo 架构

考虑到节点的异构性，不同节点的处理能力差别很大， Dynamo 使用了改进的一致性哈希算法：每个物理节点根据其性能的差异分配多个token ，每个token 对应一个虚拟节点，每个虚拟节点的处理能力基本相当，并随机分布在哈希空间中。存储时，数据按照哈希值落到某个虚拟节点负责的区域，然后被存储到该虚拟节点所对应的物理节点。

如下图，某Dynamo 集群中原有3 个节点，每个节点分配3 个token 。存放数据时，首先计算主键的哈希值，并根据哈希值将数据存放到对应token 所在的节点。假设增加节点4 ，节点token 分配情况发生变化，这就实现了自动负载均衡。

为了找到数据所属的节点，要求每个节点维护一定的集群信息用于定位。Dynamo 系统中每个节点维护整个集群的信息，客户端也缓存整个集群的信息，因此，绝大部分请求能够一次定位到目标节点。

B 、 Gossip 协议

由于机器或者人为的因素，系统中的节点成员加入或者删除经常发生，为了保证每个节点缓存的都是Dynamo 集群中最新的成员信息，所有节点每隔固定时间(比如1s )通过Gossip 协议的方式从其他节点中任意选择一个与之通信的节点。如果连接成功，双方交换各自保存的集群信息。

Gossip 协议用于P2P 系统中自治的节点协调对整个集群的认识，比如集群的节点状态、负载情况。我们先看看两个节点A 和B 是如何交换对世界的认识的。

( 1 ) A 告诉B 其管理的所有节点的版本(包括Down 状态和Up 状态的节点);

( 2 ) B 告诉A 哪些版本它比较旧了，哪些版本它有最新的，然后把最新的那些节点发给A (处于Down 状态的节点由于版本没有发生更新所以不会被关注);

( 3 ) A 将B 中比较旧的节点发送给B ，同时将B 发送来的最新节点信息做本地更新;

( 4 ) B 收到A 发来的最新节点信息后，对本地缓存的比较旧的节点做更新。

由于种子节点的存在，新节点加入可以做得比较简单。新节点加入时首先与种子节点交换集群信息，从而对集群有了认识。DHT ( Distributed Hash Table ，也称为一致性哈希表)环中原有的其他节点也会定期和种子节点交换集群信息，从而发现新节点的加入。

集群不断变化，可能随时有机器下线，因此，每个节点还需要定期通过Gossip 协议同其他节点交换集群信息。如果发现某个节点很长时间状态都没有更新，比如距离上次更新的时间间隔超过一定的阈值，则认为该节点已经下线了。

2、 Taobao Tiar

Tair 是一个分布式的key/value 系统。

Tair 有四种引擎：mdb, rdb, kdb 和ldb 。分别基于四种开源的key/value 数据库：memcached, Redis, Kyoto Cabinet 和leveldb 。Tair 可以让你更方便地使用这些KV 数据库。比如Redis 没有提供sharding 操作，如果有多个Redis Server ，你需要自己写代码实现sharding ， Tair 帮你封装了这些。

Tair 有以下优点：

( 1 )统一的API 。无论底层使用何种引擎，上层的API 是一样的。

( 2 ) Tair 将集群操作封装起来，解放了开发者。淘宝内部在使用Tair 时，一般都是双机房双集群容错，利用invalid server 保证两个集群间的一致性，这些对于开发者都是透明的。

A 、 Tair 使用场景

( 1 )非持久化(mdb,rdb)

• 数据可以以key/value 的形式存储
• 数据可以接受丢失
• 访问速度要求很高
• 单个数据大小不是很大，一般在KB 级别
• 数据量很大，并且有较大的增长可能性
• 数据更新不频繁

( 2 )持久化(kdb,ldb)

• 数据可以以key/value 的形式存储
• 数据需要持久化
• 单个数据大小不是很大，一般在KB 级别
• 数据量很大，并且有较大的增长可能性
• 数据的读写比例较高

B 、 Tair 的架构

Tair 作为一个分布式系统，是由一个中心控制节点和若干个服务节点组成，

a. config server function:

( 1 )通过维护和data server 心跳来获知集群中存活节点的信息;

( 2 )根据存活节点的信息来构建数据在集群中的分布表;

( 3 )根据数据分布表的查询服务;

( 4 )调度data server 之间的数据迁移、复制;

b. Data server function

( 1 )提供存储引擎;

( 2 )接受client 的put/get/remove 等操作;

( 3 )执行数据迁移，复制等;

( 4 )插件：在接受请求的时候处理一些自定义功能;

( 5 )访问统计;

c 、 client 功能

( 1 )在应用端提供访问tair 集群的接口;

( 2 )更新并缓存数据分布表和invalid server 地址等;

( 3 ) local cache ，避免过热数据访问影响tair 集群服务;

( 4 )流控;

在下图中，。客户端首先请求Config Server 获取数据所在的Data Server ，接着往Data Server 发送读写请求。Tair 允许将数据存放到多台Data Server ，以实现异常容错。

C 、数据分布均衡性

Tair 的分布采用的是一致性哈希算法，对于所有的key ，分到Q 个桶中，桶是负载均衡和数据迁移的基本单位， config server 根据一定的策略把每个桶指派到不同的data server 上，因为数据按照key 做hash 算法，保证了桶分布的均衡性，从而保证了数据分布的均衡性。

D 、容错

当某台Data Server 故障不可用时， Config Server 能够检测到。每个哈希桶在Tair 中存储多个副本，如果是备副本，那么Config Server 会重新为其指定一台Data Server ，如果是持久化存储，还将复制数据到新的Data Server 上。如果是主副本，那么ConfigServer 首先将某个正常的备副本提升为主副本，对外提供服务。接着，再选择另外一台Data Server 增加一个备副本，确保数据的备份数。

E 、数据迁移

增加或减少data server 的时候， config server 会发现这个情况， config server 负责重新计算一张新的桶在data server 上的分布表，将原来由减少的机器服务的桶的访问重新指派到其他的data server 中，这个时候就会发生数据的迁移。比如原来由data server A 负责的桶，在新表中需要由B 负责，而B 上并没有该桶的数据，那么就将数据迁移到B 上来，同时config server 会发现哪些桶的备份数目减少了，然后根据负载均衡情况在负载较低的data server 上增加这些桶的备份。当系统增加data server 的时候， config server 根据负载，协调data server 将他们控制的部分桶迁移到新的data server 上，迁移完成后调整路由;

数据迁移时data server 对外提供服务的策略，假设data server A 要把桶1,2,3 迁移到data server B ，因为迁移完成前，客户端的路由表没有变化，客户端对1,2,3 的访问请求都会路由到A ，现在假设1 还没迁移， 2 正在迁移， 3 已经迁移完成，那么如果访问1 ，则还是访问data server A ，如果访问3 ，则A 会把请求转发给B ，并且将B 的返回结果返回给客户，如果访问2 ，则在A 上处理，同时如果是对2 的修改操作，会记录修改log ，当桶2 完成迁移的时候，还有把log 发送给B ，在B 上应用这些log ，最终AB 数据一致才是真正完成迁移。如果A 是由于宕机而引发的迁移，客户端会收到一张中间临时状态的分配表，把宕机的data server 负责的桶临时指派给有其备份的data server 来处理，此时服务是可用的，负载可能不均衡，当迁移完成后，又能达到一个新的负载均衡状态。

3、 ETCD

ETCD etcd 是一个高可用的键值存储系统，主要用于共享配置和服务发现。

(1) 由CoreOS 开发并维护的，灵感来自于ZooKeeper 和Doozer ;

(2) 它使用Go 语言编写，并通过Raft 一致性算法处理日志复制以保证强一致。

(3) Google 的容器集群管理系统Kubernetes 、开源PaaS 平台Cloud Foundry 和CoreOS 的Fleet 都广泛使用了etcd ;

(4) 当集群网络出现动荡，或者当前master 节点出现异常时， etcd 可以进行master 节点的选举工作，同时恢复集群中损失的数据

A 、 ETCD 的特点

( 1 )简单：基于HTTP+JSON 的API 让你用curl 就可以轻松使用。

( 2 )安全：可选SSL 客户认证机制。

( 3 )快速：每个实例每秒支持一千次写操作。

( 4 )可信：使用Raft 算法充分实现了分布式。

B 、提供的能力

Etcd 主要提供以下能力

(1) 提供存储以及获取数据的接口，它通过协议保证Etcd 集群中的多个节点数据的强一致性。用于存储元信息以及共享配置。

(2) 提供监听机制，客户端可以监听某个key 或者某些key 的变更。用于监听和推送变更。

(3) 提供key 的过期以及续约机制，客户端通过定时刷新来实现续约( v2 和v3 的实现机制也不一样)。用于集群监控以及服务注册发现。

(4) 提供原子的CAS ( Compare-and-Swap )和CAD ( Compare-and-Delete )支持( v2 通过接口参数实现， v3 通过批量事务实现)。用于分布式锁以及leader 选举。

C 、 ETCD 架构

( 1 ) Etcd v2 存储， Watch 以及过期机制

Etcd v2 是个纯内存的实现，并未实时将数据写入到磁盘，持久化机制很简单，就是将store 整合序列化成json 写入文件。数据在内存中是一个简单的树结构。

store 中有一个全局的currentIndex ，每次变更， index 会加1. 然后每个event 都会关联到currentIndex.

当客户端调用watch 接口(参数中增加wait 参数)时，如果请求参数中有waitIndex ，并且waitIndex 小于currentIndex ，则从EventHistroy 表中查询index 小于等于waitIndex ，并且和watch key 匹配的event ，如果有数据，则直接返回。如果历史表中没有或者请求没有带waitIndex ，则放入WatchHub 中，每个key 会关联一个watcher 列表。当有变更操作时，变更生成的event 会放入EventHistroy 表中，同时通知和该key 相关的watcher 。

( 2 ) Etcd v3 存储， Watch 以及过期机制

Etcd v3 将watch 和store 拆开实现，我们先分析下store 的实现。Etcd v3 store 分为两部分，一部分是内存中的索引， kvindex ，是基于google 开源的一个golang 的btree 实现的，另外一部分是后端存储。

按照它的设计， backend 可以对接多种存储，当前使用的boltdb 。boltdb 是一个单机的支持事务的kv 存储， Etcd 的事务是基于boltdb 的事务实现的。Etcd 在boltdb 中存储的key 是reversion ， value 是Etcd 自己的key-value 组合，也就是说Etcd 会在boltdb 中把每个版本都保存下，从而实现了多版本机制。

4 、产品选型比较( Etcd ， Zookeeper ， Consul 比较)

这三个产品是经常被人拿来做选型比较的。

(1) Etcd 和Zookeeper 提供的能力非常相似，都是通用的一致性元信息存储，都提供watch 机制用于变更通知和分发，也都被分布式系统用来作为共享信息存储，在软件生态中所处的位置也几乎是一样的，可以互相替代的。二者除了实现细节，语言，一致性协议上的区别，最大的区别在周边生态圈。Zookeeper 是apache 下的，用java 写的，提供rpc 接口，最早从hadoop 项目中孵化出来，在分布式系统中得到广泛使用( hadoop, solr, kafka, mesos 等)。Etcd 是coreos 公司旗下的开源产品，比较新，以其简单好用的rest 接口以及活跃的社区俘获了一批用户，在新的一些集群中得到使用(比如kubernetes )。虽然v3 为了性能也改成二进制rpc 接口了，但其易用性上比Zookeeper 还是好一些。

(2) Consul 的目标则更为具体一些， Etcd 和Zookeeper 提供的是分布式一致性存储能力，具体的业务场景需要用户自己实现，比如服务发现，比如配置变更。而Consul 则以服务发现和配置变更为主要目标，同时附带了kv 存储。在软件生态中，越抽象的组件适用范围越广，但同时对具体业务场景需求的满足上肯定有不足之处。