分散開発の歴史

一点集中型

**特徴： **アプリ、DB、FileServerを1台のマシンに配置。アクセスリクエスト数が少ない

アプリケーション・サービスとデータ・サービスの分割

**特徴： **アプリ、DB、FileServerを別サーバに配置。アクセスリクエスト数が少ない

キャッシュを使ったパフォーマンス向上

**特徴:**データベースで頻繁にアクセスされるデータはキャッシュサーバーに保存されるため、データベースへのアクセス回数が減り、データベースへの負担が軽減されます。

アプリケーションサーバクラスタ

**特徴：***複数のアプリケーションサーバーが負荷分散により同時に外部へサービスを提供し、1台のサーバーの処理能力の上限問題を解決します。

データベースの読み書き分離

特徴: **データベースの処理圧力を解決する読み書き分離の設計のための **データベース

![]

リバースプロキシとCDNアクセラレーション

**特徴：** リバースプロキシとCDNの採用により、システムのアクセス速度を高速化。

分散ファイルシステムと分散データベース

**特徴：*** データベースは分散データベース、ファイルシステムは分散ファイルシステム

ビジネスの発展に伴い、究極のデータベースの読み書き分離は、分散データベースと分散ファイルシステムをサポートするために使用する必要が需要を満たすことができなくなります。

分散データベースは、データベースを分割する最後の方法で、単一のテーブルのサイズが非常に大きい場合にのみ使用されます。

分散技術

同時実行

分散可能性

大規模なタスクを複数のタスクに分割し、複数のマシンにデプロイして外部にサービスを提供

グローバルクロックの欠如

時間は均一であるべき

ピアツーピア

複数のマシンにデプロイされたサービスは、何の違いもなく同じです。

失敗は必ず起こります

ハードディスクがクラッシュし、CPUが焼かれ......。

分散トランザクション

ACID

**トランザクション内のすべての操作は、すべて完了するか、まったく完了しないかのいずれかであり、途中で終了することはありません。トランザクションの実行中に発生したエラーは、トランザクションが実行されなかったかのように、トランザクション開始前の状態に復元されます。

**一貫性:** データベースの完全性は、トランザクションの開始時とトランザクションの終了時に損なわれることはありません。これは、書き込まれた情報が、情報の正確さ、連結、後続のデータベースが意図した作業を自発的に行う能力など、事前に定義されたすべての規則に完全に適合していなければならないことを意味します。

例えば、Aが500ドル、Bが300ドルを持っていて、AがBに100ドル送金した場合、何があってもAとBの合計は常に800ドルになります。

**複数のトランザクションが同時に実行された場合、相互実行によるデータの不整合を防ぎます。トランザクションの分離は、コミットされていない読み取り、コミットされた読み取り、繰り返し読み取り、直列化などの異なるレベルに分けられます。

**トランザクション処理完了後、データに対する変更は永続的であり、システム障害が発生しても失われることはありません。

2P/3P

2P= 二相コミット これは多くの場合、強力な一貫性を保証するメカニズムです)

3P= 三相コミット

**注: **2P/3PはトランザクションのACIDを保証するためのものです。

Pの2つのフェーズ

ステージ1：取引申込みの可能性を照会る取引申込みの提出

ステージ 2: トランザクション・コミットの実行 真のコミット・トランザクション

Pの3つのフェーズ

ステージ1：コミットするかしないか-トランザクションをコミットできるかどうかを尋ねます。

ステージ 2: プレコミット-トランザクションを事前にコミットします。

ステージ3：トランザクションコミットの実行-トランザクションを本当にコミットします。

注：3Pは2Pの第1ステージを前の2ステージに分割したもの

CAP

一貫性：分散データベースにまたがるデータの一貫性

可用性: ノードがハングアップしても、他のノードはサービスを提供し続けることができます。

パーティション耐性：データベースがあるマシンが故障した場合、例えばハードディスクが故障してデータが失われた場合、新しいマシンを追加して、他の正常なマシンからバックアップされたデータを同期することができます。

CAP理論の特徴： CAPは以下のうち2つしか満たすことができません。

CA（Pをあきらめる）：すべてのデータを1つのノードに配置。一貫性、可用性を満足。

AP（Cを放棄）：強い一貫性を放棄し、最終的な一貫性で保証。

CP(Aを放棄)：システムが障害に遭遇すると、影響を受けたサーバは一定期間待機する必要があり、復旧期間中は外部へのサービス提供が不可能。

CAP理論の例を挙げてください：

3つのマシンがあり、それぞれ3つのデータベースがあり、それぞれ2つのテーブルがあり、データは同じです。

マシン1-db1-tbl_person, tbl_order

マシン2-db2-tbl_person, tbl_order

マシン3-DB3-TBL_PERSON、TBL_ORDER

1）マシン1のdb1テーブルtbl_person, tbl_orderにデータを挿入するとき、挿入されたデータは、マシン2とマシン3に同時に同期される必要があります、 これは一貫性です。

(2)マシンの1台がダウンした場合、そのマシンは公衆にサービスを提供し続け、ダウンしたマシンを再起動してサービスを継続することができます。

(3）マシン1のマシンが故障したときに、すべてのデータが失われ、そこに問題が発生することはありませんので、マシン2とマシン3のデータ上で、マシンマシン4、マシン2とマシン3 1マシンのバックアップデータを同期するために再追加することができます、 これは、 パーティションのフォールトトレランスです。

BASE

基本的可用性、ソフト・ステート、最終的一貫性

**基本的可用性:** 分散システム障害時の部分的な可用性喪失を可能にします。

**ソフト状態:** 分散システムにおける中間状態を許容。また、中間状態はシステムの可用性には影響しません。

ここでいう中間状態とは、異なるデータ複製間のデータ更新の最終的な一貫性のことで、遅延する可能性があります。

CAP理論の例として、マシン1のdb1のテーブルtbl_personとtbl_orderにデータを挿入する場合、挿入されたデータは同時にマシン2とマシン3に同期されるはずですが、マシン3のネットワークに問題が発生すると同期に失敗し、しばらくしてネットワークが回復すると同期に成功するため、この同期に失敗した状態をソフト状態と呼びます。最終的に同期が成功するため、この同期失敗の状態をソフト状態と呼びます。

**最終的な整合性：**データの複製は、一定期間後に整合性に達します。

Paxos

パクソス・アルゴリズムの紹介 まずは短い話から始めましょう。

ビザンチン将軍に関する質問

ビザンチン帝国は5世紀から15世紀にかけての東ローマ帝国で、ビザンチウムは現在のトルコのイスタンブール。ビザンティン軍には多くの支部があり、敵の都市の外に駐屯し、それぞれの将軍が指揮を執っていたと考えられます。11人の将軍がいたと仮定すると、各将軍の連絡は通信員によってのみ可能でした。敵を観察した後、忠実な将軍たちは統一した行動計画を立てなければなりません。しかし、これらの将軍の中には、忠実な将軍たちの合意を望まない裏切り者がいるため、統一行動計画の策定と普及に影響が出ます。

問題なのは、すべての忠実な将軍が合意できるような合意が必要であり、少数の裏切り者が忠実な将軍に間違った計画、つまりある将軍が攻撃し、他の将軍が撤退するような計画を立てさせることはできないということです。

仮に9人の忠実な将軍がいて、5人が攻撃、4人が退却、2人のスパイが悪意を持って退却と判断したとします。これは、この11人の将兵が状態一貫性を保っているからです。

![]

概要

1)11人の将兵が都市を攻撃

2) 攻撃と撤退を同時に実行

3) 撤退するにしても攻撃するにしても、実行する前に将兵の半数の意見が一致すること

4）将兵内の裏切り者が決着生成を妨害

Paxosアルゴリズムを以下に説明します。

パクソス：多数決

Paxosアルゴリズムには、提案者、アクセプター、学習者という3つの役割があります。

**提案者：** 投稿者

動議提出、承認動議提出

**アクセプター：レシーバー

動議を受理または却下し、提案者に返答を与えます。

**学習者：学習者

動きがあれば、その動きを研究してください。

設定1： アクセプターがその動議を受け入れなかった場合、最初の動議を受け入れなければなりません。

設定2： 各モーションには数字が必要で、その数字は大きくなるだけで繰り返しはできません。数字は進むにつれて大きくなります。

設定3： 大きな番号のモーションを受け付け、受け付けたモーションの番号より小さければ受け付けません。

設定4： モーションは2種類

![]

1) 準備段階

a) 提案者はモーションVが欲しい。まず、ほとんどのアクセプターにprepare requestを送信。

b) アクセプターはK番としてPrepare要求を受信し、手持ちのPrepare要求を処理したかどうかをチェック。

c) アクセプターがいかなる準備要請も受け入れていない場合、アクセプターは最初に受け取った動 議を受け入れなければならないことを表明して、提案者にOKを返信(セット1)

d) そうでない場合、もしアクセプターが準備要求を受け入れていれば、モーション番号を比較し、もしK< />が

e) K>=MaxNの場合、承認された動議があるかどうかをチェックし、なければ提案者にOKを返信し、Kを記録します。

f) K>=MaxNの場合、承認された動議があるかどうかをチェックし、もしあれば、承認された動議番号と動議内容を返信。

2) 受け入れる段階

a) 提案者はアクセプターから半分以上の応答を受け取りますが、それらはすべてOKで、承認された動議番号や動議内容を伴っていません。その後、提案者は承認要求を提出し続けますが、その後、動議番号Kと動議内容Vを一緒に提出します。

b) 提案者は、半数以上のアクセプタから、承認された動議番号と動議内容を含む、すべてOKの返答を受け取ります。次に、提案者は半分以上の応答を持つものを見つけ、承認要求としてアクセプタに送ります。

c) 提案者が半数以上のアクセプタから返答を得られなかった場合、動議番号KはK+1に修正され、アクセプタに再送されます。

e) AcceptorはProposerからのAccept要求を受信し、K>=MaxNであればそのモーションを承認し、承認されたモーションを手元にセットしてProposerに返信。

f)一定時間後、プロポーザは手元に届いたAcceptの返答を比較し、半分以上であればプロセスを終了し、同時にLeanerにモーションを学ぶことができることを通知します。

g) 一定時間後、提案者は手元に届いたアクセプト回答を比較し、半数以下であれば、動議番号を変更し、再度準備段階に入ります。

Paxos

例1：連続提案シナリオ

![]

キャラクター

提案者：スタッフ・オフィサー1、スタッフ・オフィサー2

アクセプター：一般1、一般2、一般3

1) スタッフ・オフィサー1が、3人の将軍に手紙を添えた通信員を送る提案を開始；

2) 3人の将軍は幕僚1からの申し出を受け、まだ番号を保存していなかったので、忘れないように保存します；

3) 参謀1は少なくとも2人の将軍から返事を受け取り、再び特派員を派遣して3人の将軍に手紙を持参させます；

4) 3人の将軍は参謀1からの時間を受け取り、それを忘れないように保存し、同時に通信兵に手紙を持ち帰らせます；

5) 参謀1は少なくとも2人の将兵から内容を受け取り、攻撃時刻が全員に届いたことを確認します；

6) 参謀2が、通信兵を派遣し、3人の将軍にその内容の手紙を持参させる提案を開始；

7)参謀2からの申し出を受け取った3将兵は、その内容が大きいので、忘れないように保存し、参謀1の申し出をすでに受け入れているので、その内容の手紙を持ち帰るように特派員に依頼；

8) 参謀 2 は少なくとも 2 名の将兵から返信を受け取り、その返信には参謀 1 が受諾した申し出の内容が書かれていたため、参謀 2 は新たな攻撃時期の提案を控え、参謀 1 が提案した時期を受諾；

例2：クロスオーバーシナリオ

![]

キャラクター

提案者：スタッフ・オフィサー1、スタッフ・オフィサー2

アクセプター：一般1、一般2、一般3

1) スタッフ・オフィサー1が、3人の将軍に手紙を添えて通信員を派遣することを提案；

2) 3人の将軍は以下の通り。

a) 1将軍と2将軍は参謀1からの申し出を受け取ります。1将軍と2将軍は、他の参謀がこれより少ない数を提案した場合は却下することを記録に残し、同時に通信兵にその旨の書簡を持ち帰らせます；

b) 3大将に知らせる責任者であった通信兵が捕虜になったため、3大将は幕僚1からの申し出を受け取らず；

3) スタッフ・オフィサー2も同時に、この件に関して3人の将軍に手紙を添えた通信員を送る提案を始めました；

4) 3人の将軍は以下の通り。

a) 2将軍と3将軍は参謀2からの提案を受け取り、2将軍と3将軍は、他の参謀がこれより少ない数を提案した場合は却下することを記録に残し、同時に、通信兵に手紙を持ち帰らせます；

b) 1将軍に知らせる責任者であった通信兵が捕らえられたため、1将軍は幕僚長2からの申し出を受け取りません；

5) 参謀1は少なくとも2人の将軍から返事を受け取り、返事を受け取った2人の将軍に手紙を持たせるため、再び通信兵を派遣します；

6) 2人の将軍は以下の通り。

a) 1将軍はそれを受け取り、保存しておいたものと同じ番号なので、それを保存し、同時に特派員に手紙を持ち帰らせます；

b) 将軍2がそれを受け取り、すでに保存してあるものよりも小さいので、文通相手に手紙を持ち帰るように指示；

7) 参謀2は少なくとも2人の将軍から返事を受け取り、返事を受け取った2人の将軍に手紙を持ち帰るよう、再び特派員に指示；

8) 参謀2と参謀3は、保存しておいたものと同じ番号の手紙を受け取ったので、それを保存しておき、文通相手に手紙を持ち帰らせます；

9) 参謀2は、少なくとも2人の将兵から、攻撃の時期が多数派に受け入れられたことを確認する内容を受け取ります；

10) スタッフ・オフィサー1が受け取ったのは1人の将官のみで、1人は受け取ったものの、スタッフ・オフィサー1は3人の将官に内容を記した手紙を特派員に送り、オファーを再度開始；

11) 3人の将軍は以下の通り。

a) 1将軍は幕僚1からの申し出を受け取り、それが貯蓄より大きいので、貯蓄を入れます。1将軍はすでに幕僚1の以前の申し出を受け入れているので、特派員に次のような手紙を持ち帰らせます；

b)参謀1からの申し出を受け取った将軍2は、それが保存されているものよりも大きいので、保存されているものを置きます。将軍2は参謀2の申し出を受け入れているので、彼は通信兵にこう書かれた手紙を持ち帰るように伝えます；

c) 3大将に知らせる役割を担っていた通信兵が捕虜になったため、3大将は幕僚1からの申し出を受け取りません；

12) 参謀1は少なくとも2人の将軍から返信を受け取り、2つの返信の数字の大小を比較し、数字の大きい方に対応する攻撃時期を最新の提案として選びます；

13) 1将軍と2将軍は、保存したものと同じ番号の手紙を受け取り、保存します；

14) 参謀1が少なくとも2人の将兵から内容を受け取り、攻撃のタイミングが多数派に受け入れられたことを確認。

. Zookeeper ZAB

専門用語：

クォーラム: クラスタハーフの集合

つの状態のZAB（ズーキーパー）ノード

**リーダー選出状況

**従順：**従者である状態、リーダーの命令に従うこと

**現在のノードがリーダーであり、作業を調整する責任があります。

**オブザーバー: **observer (オブザーバー)、選挙には参加しません。

ZABの2つのパターンは

クラッシュリカバリ、メッセージ放送

）クラッシュの回復

リーダーは死に、新しいリーダーを選出する必要があります。

a.各サーバーは、例えば自分自身に投票するための投票用紙を持っています。

b.各サーバは自分自身に投票した後、まだ利用可能な他のサーバに別々に投票します。



例：Server3'sをServer4'sとServer5'sにそれぞれ1票ずつ類推投票 c.票の比較、ロジックの比較：Zxidを先に比較し、Zxidが同じときのみmyidを比較。Zxidを比較するときは大きい方がLEADER、myidを比較するときは小さい方がLEADER d.サーバーの状態の変更

関連概念の追加的明確化：

エポック値

acceptedEpoch: フォロワーはLEADERの年号変更の提案を受け入れました。

currentEpoch: 現在の年

lastZxid: 履歴で最も最近受信したオファーZxid (最大値)

history: 現在のノードがトランザクション提案を受け入れたログ。

Zxid データ構造の説明：

cZxid = 0x10000001b

64ビットデータ構造

上位32ビット：00100

リーダーのサイクル番号＋myidの組み合わせ

下位32ビット：001b

トランザクションの自己インクリメントシーケンスは、クライアントがそれを要求す るたびに+1されます。

新しいLeaderが生成されると、ローカルログの最大トランザクションZxidがこのLeaderサーバーから取得され、そこからepoch+1が新しいエポックとして読み込まれ、下位32位0

）メッセージのブロードキャスト

a.リーダーはリクエストを受け入れ、このリクエストにグローバルに一意な 64ビットの自己インクリメントIdを割り当てます。

b.このzxidをモーションとして全フォロワーに送信。

c.すべてのフォロワーはモーションを受け入れ、ハードディスクに書き込みたくなったらすぐにACKでリーダーに返信します。

d.リーダーが正当な数のACKを受け付けると、リーダーは全フォロワーにコミットコマンドを送信します。

e.フォロワーはコミットコマンドを実行します。

注：この段階で、ZKクラスタは正式にサービスを提供し、Leaderはメッセージをブロードキャストすることができます。

）データの同期

a.リーダー最大のlastZxidを取り出し

b.そのZxidに対応するデータを見つけ、同期化

c.クォーラムの同期が完了して初めて、準Leaderが本物のLeaderになれます。