体系ガイド · 基礎から応用へ

合意・Raft・CAP・シャーディング

多数決の条件とネットワーク分断時の振る舞いを追い、複製と分割の役割を区別する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 複製とシャーディングは目的が違う
  2. 三台なら二台が過半数
  3. Raftでログの順を共有する
  4. 分断時のCAPを具体化する
  5. 二つのシャードをそれぞれ三台で複製する
  6. ログの合意と要求の一回性を分ける
  7. 分割の変更中に読書きを守る
  8. 担当数と複製数を求める課題
  9. この記事をロゲイアに質問する理解を確かめる

複製とシャーディングは目的が違う

レプリケーションは同じ論理データのコピーを複数ノードに持たせ、障害への耐性や読み取りの分散などに使います。シャーディングはデータを範囲やキーの規則で別々の担当へ分割します。データの総量を分けることと、同じ変更の順序を複数のコピーで共有することは別です。一つのシャード内でさらに複製する構成もあります。キーの偏り、シャードをまたぐ処理、移動時の一貫性が課題になるため、台数を増やせば全ての操作がそのまま速くなるとは限りません。

三台なら二台が過半数

三台の複製グループでは二台が過半数です。過半数どうしには少なくとも一台の共通ノードがあるため、合意プロトコルの安全性を組み立てる手がかりになります。しかし単に二台へ書けば、どんな実装でも合意が完成するわけではありません。任期、投票条件、ログの新しさ、永続化、再起動後の動作を合わせた規則が必要です。ノード数ではなく過半数の通信可能性が重要で、三台中一台が故障しても残り二台が互いに通信できなければ進行できない場合があります。

Raftでログの順を共有する

Raftでは任期ごとにリーダーを選び、リーダーがログ項目を複製します。現在の任期の項目を過半数へ複製してコミットする規則などが、安全なログの前進に関わります。古い任期の項目が何台かにあるという数だけで、同じようにコミットを判断してはいけません。分断された古いリーダーが存在しても、新しいリーダーと矛盾する結果を確定しないよう投票とログの規則が働きます。読み取りでも古いリーダーの手元の値を無条件で返せばよいわけではなく、要求する保証に応じたリーダーの正当性確認が必要です。

分断時のCAPを具体化する

ネットワークが二群に分かれ、互いの更新を見られない状況を考えます。全ての要求へ応答し続けることと、単一の最新状態と整合する強い読み書きを同時に保つことには制約があります。CAPの整合性と可用性には形式的な定義があり、「いつでも三つのうち二つを自由に選ぶ」という宣伝文句ではありません。過半数側だけで更新を進める方式は、少数側の書き込みを拒否または待機させることがあります。可用性を優先した書き込みには、分断後の競合解決と、利用者にどの状態を見せるかの規則が必要です。

二つのシャードをそれぞれ三台で複製する

注文キー0〜99をS1、100〜199をS2へ分割し、S1をA1、A2、A3、S2をB1、B2、B3へ複製するとします。キー70はS1の三コピー、キー150はS2の三コピーにあります。二つのデータ担当と、各担当の複製数三は別です。全体が六台だから一つのN=6の多数決を取る、と自動では決まりません。合意する履歴の単位とメンバーを囲んで数えます。

Partitioningはデータを区分する広い言い方で、一つのDB内の分割にも使われます。Shardingは複数の担当へ分散する構成を指すことが多いですが、製品の用語も確認します。言葉だけの比較を増やすより、この例でキーを分けたことと同じキーを複製したことを説明してください。分割と複製は同時に使えます。必要な比較は、実際の担当範囲と複製集合を並べると明確になります。

キーデータ担当複製集合
70S1A1、A2、A3
150S2B1、B2、B3

ログの合意と要求の一回性を分ける

S1で在庫を一つ減らすログが合意されても、クライアントが応答を失って同じ業務を別要求として送れば、二つの命令として合意する可能性があります。Raftはログの順序を共有しますが、それが同じ業務要求の再送かはアプリも識別する必要があります。処理済みの操作IDと結果を状態機械へ含め、snapshotにも必要な記録を残す設計が考えられます。

読み手が古いリーダーへ接続している場合の権限確認も別です。リーダーと名乗ることだけで、今の最新状態を返せるとは限りません。Raftの詳細記事では、保存、commit、apply、読みの条件を分けています。クォーラムのガイドへ進むときも、集合が交差するという式だけを全プロトコルの安全性の代わりにしないでください。共通ノードで何を許し、再起動後に何を覚えるかが必要です。

分割の変更中に読書きを守る

S1の後半を新しい担当へ移すとき、配置の計算だけではデータは移りません。コピー中に元へ届いた更新と削除を追い、新担当が必要位置へ追い付いた後に権限を切り替えます。古い配置で元の担当へ届いた再送を、両側が独立に確定しないように扱います。構成の世代やフェンシングも、実際の保存先が拒否できる境界まで実装する必要があります。

Range shardingは範囲検索をまとめやすくする一方、増え続けるキーの集中を作ることがあります。Consistent hashingとRendezvous hashingは配置変更を限定する候補ですが、ライブコピーや合意の代わりではありません。付属ハッシュ実験は担当の変化だけを計算します。分割、配置関数、コピー、権限、各シャードの複製を別の箱で描くと、何を実行した証拠がまだ必要かが分かります。

六台の例でS1の一台とS2の二台が停止した場合、S1には二台、S2には一台が残ります。三台グループごとの多数を使う構成なら、同じ全体の生存台数三でも、二シャードが同じように進めるとは限りません。全体の電源が入った台数より、各履歴の正しいメンバーと通信を確認することが重要です。

配置で容量を増やしたいのか、複製で故障へ備えたいのかを明記すると、この数え方を取り違えにくくなります。前者は移動量や偏り、後者は保存と合意の条件を検証し、どちらも通常処理へ与える負荷を観測します。

担当数と複製数を求める課題

課題はキー70の更新について、S1とS2の全六台を一つに数えてよいかです。解答は、この構成ではS1の履歴と三台を対象に考え、S2のコピーをS1の確認へ足さない、です。別シャードへある別データは、一つのキーのクォーラムの代わりになりません。両シャードへまたがる業務があるなら、その共同確定や補償は分散トランザクションの別の問題です。

追加課題はS1のA1だけが他の二台と通信できなくなった場合です。多数側の規則を守るなら、A1が生きていても独自に更新を確定し続けられるとは限りません。CAPの問いはそのような分断中の保証へ置きます。台数、通信、ログ、配置、業務の範囲を別々に説明できれば、Raftと配置変更の各教材へ進めます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

サーバーの中で起きていること · STEP 18

学習コースから次を選ぶ