この記事では、さまざまなシステムで積極的に調査され、正常に使用されている、チェーンレプリケーションを使用したシンプルで効率的なKVストレージのアーキテクチャを検討します。

これは、チェーン複製の記事の前半です。第二部はこちらです。最初は少し理論があり、次にさまざまな修正を加えた使用例がいくつかあります。

目標は、問題の記述とプライマリ/バックアッププロトコルとの比較です。
チェーンレプリケーションは基本的なアプローチです。
チェーンレプリケーション-分散リクエスト。
FAWN：Wimpyノードの高速配列。

1.はじめに

1.1目的

単純なキーと値のストアを設計したいとします。リポジトリには最小限のインターフェイスがあります。

書き込み（キー、オブジェクト）：キーキーによって値の値を保存/更新します。
読み取り（キー）：キーキーごとに保存された値を返します。

また、データサイズが比較的小さいこと（すべてが1つのサーバーに収まり、シャーディングの必要がないこと）がわかっていますが、書き込み/読み取り要求が大量に発生する可能性があります。

私たちの目標は、多数のリクエスト（ 高スループット、HT ）に耐え、高可用性（ HA ）、および強力な一貫性（ SC ）を持つことです。

多くのシステムでは、3つのプロパティをすべて満たすのは簡単な作業ではないため、SCはHA + HTの犠牲になります。 Amazon Dynamoは大きな前進であり、Cassandra、Riak、Voldemortなど、多くのDynamoスタイルのデータベースを生み出しました。

1.2プライマリ/バックアップ

このようなストレージシステムを構築するための最も一般的でシンプルなアプローチの1つは、プライマリ/バックアップレプリケーションを使用することです。

1つのプライマリサーバー、複数のバックアップサーバーがあり、書き込み/読み取り操作はプライマリサーバーのみを経由します。

ここでは、可能な相互作用プロトコルの1つを示します（プライマリをすべてのバックアップからのackを待ってからクライアントにackを送信します）。他のオプション（相互に排他的ではない）があります。

プライマリは書き込み要求を厳密に編成します。
プライマリは、バックアップの1つがackで応答するとすぐにackを送信します。
ずさんな定足数とヒント付きハンドオフ。
等

クラスターの状態を監視し（構成を参加者に配布する）、ホストサーバーがクラッシュした場合に新しいサーバーを選択（開始）し、スプリットブレインの場合の対処方法を決定する別のプロセスも必要です。繰り返しになりますが、要件に応じて、このロジックの一部はレプリケーションアルゴリズムの一部として、サードパーティアプリケーション（たとえば、構成を保存するための動物飼育係）として実行できます。

明らかに、遅かれ早かれ、プライマリ/バックアップレプリケーションのパフォーマンスは2つのボトルネックによって制限されます。

プライマリサーバーのパフォーマンス。
バックアップサーバーの数。

クラスタに提供される信頼性/一貫性の要件が多いほど、この瞬間は早くなります。

目標を達成する他の方法はありますか？

1.3チェーンレプリケーション

一般に、チェーンレプリケーションは、特別な役割HEAD（クライアントが通信するサーバー）とTAIL（チェーンの終わり、SC保証）を持つ一連のサーバー（チェーン）で構成されます。チェーンには、少なくとも次のプロパティがあります。

n-1台のサーバーへのドロップに耐えます。
書き込み速度は、SCプライマリ/バックアップの速度とそれほど変わりません。
HEADクラッシュが発生した場合のクラスターの再構成はプライマリよりもはるかに高速であり、残りのサーバーはプライマリ/バックアップよりも比較的高速です。

小さいが重要なポイント- サーバー間の信頼できるFIFO接続が必要です。

チェーンレプリケーションを構築するさまざまな方法をより詳細に検討してみましょう。

2.基本的なアプローチ

2.1運用アルゴリズム

クライアントは書き込み要求をヘッドノードに送信し、読み取り要求はテールノードに送信します。答えは常に尾から来ます。変更要求を受信したHeadは、必要な状態変更を計算して適用し、次のノードに送信します。テールがそれを処理するとすぐに、ACK応答がチェーンに送信されます。明らかに、読み取り要求がxの値を返す場合、すべてのノードに保存されます。

2.2複製プロトコル

サーバーの先頭から末尾に番号を付け、次に各ノードに番号を付けます

i

$i$ さらに保存します：

$Pending_i$ -テールによってまだ処理されていないノードによって受信された要求のリスト。
$Sent_i$ -サーバーによって後続サーバーに送信され、まだテールによって処理されていない要求のリスト。
$History_i（キー）$ -キー値の変更履歴（履歴と合計値の両方を保存できます）。以下に注意してください。

$H i s t o r y_{j} （キー） \サブセット e q H i s t o r y_{i} （キー）、 f o r a l l j > i$
$History_j（キー）\サブセットeq History_i（キー）、\ forall j> i$
そしてまた：

$S e n t_{i} \サブセット e q P e n d i n g_{i} H i s t o r y_{i} （キー） = H i s t o r y_{i + 1} （キー） c u p S e n t_{i}$
$Sent_i \サブセットeq Pending_i \\ History_i（キー）= History_ {i + 1}（キー）\ cup Sent_i$

2.3サーバーのフェイルオーバー

はじめに述べたように、次のようなマスタープロセスが必要です。

故障したサーバーを識別します。
回路の変更の前身と後継者に通知します。
サーバーがテールまたはヘッドの場合、クライアントに変更を通知します。

マスタープロセスは安定しており、クラッシュすることはありません。そのようなプロセスの選択は、この記事の範囲外です。

2番目の非常に重要な仮定は、サーバーがフェールストップであると仮定することです。

（内部）障害が発生した場合、サーバーは動作を停止し、誤った結果を返しません。
サーバー障害は、常にマスタープロセスによって決定されます。

新しいサーバーの追加方法を検討してください。

理論的には、新しいサーバーをチェーン内の任意の場所に追加することができ、テールへの追加は最も難しいようです-現在のテールのステータスを新しいサーバーにコピーし、チェーンの変更についてウィザードに通知し、リクエストをさらに送信する必要があることを古いテールに通知するだけです

最後に、考えられる3つの障害シナリオを検討します。

2.3.1ヘッドフォール

サーバーをチェーンから削除し、次の新しいヘッドを割り当てるだけです。からのこれらのリクエストの損失のみ

P e n d i n g_{h e a d}

$Pending_ {head}$ それ以上送られなかった-

P e n d i n g_{h e a d} s e t m i n u s S e n t_{h e a d}

$Pending_ {head} \ setminus Sent_ {head}$

2.3.2フォールテール

チェーンからサーバーを削除し、前のサーバーを新しいテールに割り当てます。その前に

S e n t_{t a i l - 1}

$Sent_ {tail-1}$ クリア（これらの操作はすべて処理済みテールとしてマークされます）

P e n d i n g_{t a i l - 1}

$Pending_ {tail-1}$ 減少します。

2.3.3落下中間ノード

k

$k$

ウィザードはノードに通知します

k - 1

$k-1$ そして

k + 1

$k + 1$ チェーン内の並べ替えについて。

損失の可能性

送 信 済 み_{k - 1}

$送信済み_ {k-1}$ ノードの場合

k

$k$ ノードを削除した後、後継者に送信することができませんでした

k

$k$ チェーンから最初のものが再び送信されます

送 信 済 み_{k - 1}

$送信済み_ {k-1}$ そしてその結び目の後のみ

k - 1

$k-1$ 新しいリクエストの処理を続けます。

2.4バックアップ/プライマリプロトコルとの比較

チェーンレプリケーションでは、1つのサーバー（テール）のみが読み取り要求の実行に関与し、すぐに応答しますが、P / Bプライマリでは書き込み要求の完了の確認を待つことができます。
どちらのアプローチでも、書き込み要求はすべてのサーバーで実行されますが、P / Bは並列実行により高速に実行します。

障害チェーンの複製遅延：

ヘッド：読み取り要求の実行は中断されません。書き込み要求は、マスターから新しいヘッドに関するすべてのサーバーへ、およびマスターから新しいヘッドに関するすべてのクライアントへの2つのメッセージによって遅延されます。
中間サーバー：読み取り要求は中断されません。記録要求は実行時に遅延する場合があります $Sent_i$ 更新の損失はありません。
テール：2つのメッセージの読み取りおよび書き込み要求の遅延-通知 $テール-1$ 新しいテールについて、お客様に新しいテールについて警告します。

障害P / B遅延：

プライマリ：新しいプライマリを選択して同期状態にするための5メッセージの遅延。
バックアップ：書き込み要求がない場合、読み取り遅延はありません。録音要求が表示されると、1メッセージの遅延が発生する可能性があります。

ご覧のとおり、チェーンレプリケーションの最悪のテール障害は、P / B（プライマリ）の最悪の障害よりも高速です。

このアプローチの作成者は負荷テストを実行し、P / Bプロトコルと同等のパフォーマンスを示しました。

3.分散クエリ（割り当てられたクエリを使用したチェーンレプリケーション-CRAQ）

基本的なアプローチには明らかな弱点があります-tailは、すべての読み取り要求を処理します。これにより、2つの問題が発生する可能性があります。

テールがホットスポットになります。他のノードよりもはるかに多くの要求を処理するサーバー。
複数のデータセンターにチェーンを配置すると、テールが非常に遠くなる可能性があり、書き込み要求が遅くなります。

CRAQの考え方は非常に単純です-読み取り要求をテール以外のすべてのサーバーに送信し、一貫性を確保するために、書き込み要求のオブジェクトバージョンのベクトルを保存します。あいまいな場合は、ノードがテールに要求を行って最新の修正バージョンを取得します。

3.1 CRAQ

CRAQアーキテクチャを形式化します。

テールを除く各ノードは、読み取り要求を処理して応答を返し、ヘッドは書き込み要求から応答を返します（基本的なアプローチと比較してください）。

各非テールノードには、同じオブジェクトの複数のバージョンを保存でき、バージョンは厳密に単調に増加するシーケンスを形成します。追加の属性「clean」または「dirty」が各バージョンに追加されます。最初は、すべてのバージョンがクリーンです。

ノードが書き込み要求を受け取るとすぐに、受け取ったバージョンをバージョンのリストに追加し、次のことを行います。

ノードがテールの場合、バージョンはクリーンであるとマークされ、この時点でバージョンは修正されたと見なされ、確認がチェーンに送信されます。
それ以外の場合、バージョンをダーティとしてマークし、チェーンのさらに下に要求を送信します。

ノードが後続から確認を受け取るとすぐに、そのバージョンにクリーンのマークを付け、以前のすべてのバージョンを削除します。

ノードが読み取り要求を受信するとすぐに：

ノードが認識しているオブジェクトの最後のバージョンがクリーンである場合、それを返します。
それ以外の場合、彼はオブジェクトの最新の修正バージョンを取得するためにtailを要求し、クライアントに返します。（構成上、このようなバージョンは常にノード上にあります）。

読み取り要求が多いアプリケーションでは、CRAQのパフォーマンスはノードの増加に比例して増加します。書き込み要求が多い場合、パフォーマンスは基本的なアプローチより悪くなりません。

CRAQは、1つまたは複数のデータセンターの両方に配置できます。これにより、顧客は最も近いノードを選択して、読み取り要求の速度を上げることができます。

3.2 CRAQの一貫性

CRAQは強力な一貫性を提供します。ただし、1つの場合を除きます。ノードがテールから最新のコミット済みバージョンを受信すると、ノードがクライアントに応答する前にテールが新しいバージョンをコミットできます。この状況では、CRAQはチェーン全体で 単調な読み取りを提供します（順次読み取り要求は過去のものではありませんが、古いデータを返すことができます）。

弱い一貫性も可能です：

最終的な整合性：ノードは最新のコミット済みバージョンをテールから要求しません。これにより、チェーン全体の単調な読み取りが中断されますが、同じノードでの単調な読み取りは維持されます 。さらに、 パーティションの許容値に耐えることができます。
限定された最終的な一貫性：特定のポイントまでのみダーティバージョンを返します。たとえば、ダーティバージョンとクリーンバージョンの違いは、Nリビジョンを超えてはなりません。または制限時間。

3.3サーバーのフェイルオーバー

基本的なアプローチに似ています。

3.4オプション

CRAQには興味深い機能が1つあります。記録操作中にマルチキャストを使用できます。 headがマルチキャストの変更を送信し、このイベントの識別子のみをチェーンに送信するとします。更新自体がノードに到着しなかった場合、Tailが変更の確認を送信するときに待機して次のノードから受信できます。同様に、tailはマルチキャストで固定の確認を送信できます。

4. FAWN：Wimpyノードの高速配列

この記事のトピックに直接関連していないが、チェーンレプリケーションの使用例として役立つ非常に興味深い研究。

高性能のキー値ストレージ（Dynamo、memcached、Voldemort）には共通の特性があります。I/ O、最小限の計算、大量のランダムキーへの並列独立アクセス、および最大1Kbの小さなキー値が必要です。

HDDを備えたサーバーは、長いシーク操作（ランダムアクセス時間）のためにこのようなクラスターには適さず、DRAMを大量に搭載するサーバーは驚くほど大量の電力を消費します。2GBDRAMは1Tb HDDに相当します。

最小の電力消費で効果的な（スループット）クラスターを構築することが、元の調査の目標です。 3年間のサーバーコストの50％は電力コストであり、最新の省エネモードは宣伝されているほど効果的ではありません-20％の負荷でのテストでは、CPU消費は50％のままで、さらにサーバーコンポーネントの残りには省エネモードがありません（たとえば、DRAMはすでに最低でも動作します）。このようなクラスターでは、CPUとI / Oの間のギャップが広がることに注意することが重要です。強力なCPUは、I / O操作が完了するまで待たされます。

4.1アーキテクチャ

FAWNクラスターは、統合された500MHz CPU、512Mb RAM、32Gb SSDを備えた250ドル（2009年価格）で古いサーバー上に構築されています。 Amazon Dynamoアーキテクチャまたは一貫したハッシュに精通している場合は、FAWNアーキテクチャに精通しています。

各物理サーバーには複数の仮想ノードが含まれ、それぞれに独自のVIDがあります。
VIDはリングを形成し、各VIDは「背後」の範囲を担当します（たとえば、A1は範囲R1のキーを担当します）。
信頼性を高めるために、データは次のノードのRに時計回りに複製されます。（たとえば、R = 2の場合、A1のキーはB1とC1に複製されます）、したがって、チェーンレプリケーションを取得します（基本的なアプローチ）。
読み取り要求はテールチェーン、つまり A1からキーを読み取ると、C1に移動します。
書き込み要求はヘッドチェーンに送られ、最後まで処理されます。

サーバーマップは、フロントエンドサーバーのクラスターに格納されます。各クラスターは、独自の特定のVIDリストを担当し、要求を別のフロントエンドサーバーにリダイレクトできます。

4.2テスト結果

負荷テストでは、FAWNはランダムリードフラッシュドライブのQPSの90％のQPS（クエリ/秒）に達します。

次の表は、さまざまな構成の総所有コスト（TCO）を比較したものです。トラディショナルの基本は、200Wの消費（2009年の価格）で1000ドルのサーバーです。

したがって、次の場合：

ビッグデータ、少数のクエリ：FAWN + 2Tb 7200 RPM
少量のデータ、多くのリクエスト：FAWN + 2GB DRAM
平均値：FAWN + 32GB SSD

チェーンレプリケーション：効率的なKVリポジトリの構築（パート1/2）