分散システム

前提知識

グロッシュの法則

コンピュータの性能は価格の 2 乗に比例する

グロッシュの法則は 1980 年代以降のコンピュータに対して成り立たなくなってきた。

それに伴い、システムのスループットを向上させるために、より優れたハードウェアを導入する方法 (スケールアップ, scale-up) より安価なハードウェアの台数を増やす方法 (スケールアウト, scale-out) が、コスト面で有利であると考えられるようになった。

分散システムの原則

分散システムは以下の原則を満たすことを期待する。

分散が透過的であること
- 位置に対する透過性
- 複製 (レプリケーション) に対する透過性
- 分割に対する透過性
トランザクションが透過的であること

「透過的である」とは、ユーザー (ex. 分散データベースの場合はアプリケーション開発者) がそのシステムの技術的詳細を意識することなく使えることを意味する。

分散システムの落とし穴

ネットワークは信頼できない。
レイテンシはゼロではない。
帯域幅が存在する。
トランスポートコストはゼロではない。

アムダールの法則

アムダールの法則は、並列処理において並列度を上げた場合に並列化できない部分の存在がボトルネックになることを示した法則である。

アムダールの法則を分散システムに適用すると、処理の分散によるシステム全体の性能向上率は次の式で表される。

\begin{aligned} &=\frac{1}{(1-P)+\frac{P}N}\\ P&:\text{並列化可能な部分の割合}\\ N&:\text{ノード数} \end{aligned}

一方で並列化可能な部分は、処理の大きさに関わらず一定であるとし、「十分に大きな規模の処理は、効率的に分散化して解くことができる」ことを示した法則もある → グスタフソンの法則

CAP 定理

CAP 定理 (CAP theorem) とは、ノード間のデータ複製において、同時に次の 3 つの保証を提供できないことを示す定理である。

一貫性 (Consistency): すべてのデータ読み込みにおいて、最新の書き込みデータもしくはエラーのどちらかを受け取る性質。

可用性 (Availability): ノードの障害により生存ノードの機能性が損なわれない性質。つまり、単一障害点 (SPoF = Single Point of Failure) が存在しないという性質。

分断耐性 (Partition-tolerance): システムは任意の通信障害などによるメッセージ損失に対し、継続して動作する性質。

CP 型は基幹系システムや勘定系システムなど、ミッションクリティカル (mission critical) な SoR (System of Records) 領域に適している。 AP 型は UX (= User eXperience, ユーザ体験) や可用性を重視する SoE (System of Engagement) 領域に適している。

BASE 特性

BASE 特性とは前述の CAP 定理の制約の下、高可用性を達成するシステムの特性である。

Basically Available (基本的に利用可能)
Soft state, Eventually consistent (結果整合性)

結果整合性とは、厳密な一貫性は保証しないものの、時間経過で正しい状態に収束する性質のことである。

NoSQL に代表されるデータストアでは、結果整合性を採用することで、容易なスケールアウトを実現している。

クラスタリング

クラスタリング (clustering) とは、複数のコンピュータを結合し、あたかも 1 つの大きなシステム (クラスタ, cluster) として利用可能にすることをいう。

クラスタリングには以下の目的がある。

処理性能のスケーラビリティ (scalability)
冗長性 (redundancy)

クラスタは目的によって以下の 2 つに分類される。

HPC (= High Performance Cluster, 高性能クラスタ) → 処理性能のスケーラビリティに特化
高可用 (HA = High-Availability) クラスタ → 冗長性に特化

また、クラスタはリソースの共有形態によって以下の 2 つに分類される。

密結合クラスタ: クラスタを構成するノード間で一部のリソース (CPU/メモリ/ディスク) を共有するもの。共有リソースは単一障害点となるため、別の冗長化と併用する場合が多い。

疎結合クラスタ: クラスタを構成するノード間でネットワーク以外に直接のリソース共有がないもの。ネットワークがボトルネックになりやすい。

2 相コミット

2 相コミット (two-phase commit) は、分散システムでトランザクションのコミットについての一貫性を保証するためのプロトコルである。要求を受け取ったノードが調整者 (coordinator) となり、参加者 (cohort) であるリモートノードを調整する。

2 相コミットは完全な一貫性を保証するものではない。コミット可否の問い合わせとコミットを連続して行い、コミットの処理中に障害が起きる確率を下げるものである。

2 相コミットの処理内容を、コミット要求フェーズとコミットフェーズに分けて下記に示す。

コミット要求フェーズ

調整者は全参加者にコミット可否を問い合わせる。
参加者はトランザクションをコミットが行える状態まで進める。 (ここでロックが獲得される)
参加者はトランザクションのコミット可否を調整者に返す。

コミットフェーズ

全参加者がコミットに合意した場合の処理を以下に示す。

調整者は全参加者にコミットを要求する。
参加者はトランザクションをコミットする。 (ここでロックが解放される)

コミットに合意しない参加者がいた場合の処理を以下に示す。

調整者は全参加者にロールバックを要求する。
参加者はトランザクションをロールバックする。 (ここでロックが解放される)

2 相コミットは以下のようなデメリットがある。

全参加者が応答するまでリソースがロックされる
1 つの参加者の障害により、調整者と全参加者が待機させられる

レプリケーション

レプリケーション (replication, 複製) とはリソース (ex. 分散データベースにおけるコミットログやデータ) の複製、あるいは複製する処理のことをいう。

複製するデータによる分類

論理レプリケーション (トランザクション・レプリケーション, 計算レプリケーション): トランザクションログのレプリケーション。ログ構造化ファイルシステムは論理レプリケーションの 1 つである。

物理レプリケーション (データレプリケーション, 状態機械レプリケーション): 変更されたデータのレプリケーション。

操作を完了とみなすタイミングによる分類

同期レプリケーション: ローカルストレージとリモートノードの両方から完了通知があるまで、書き込み要求が完了したとはみなさない。そのため、全体の性能が低下する。また、一部ノードに障害が発生している間の書き込み要求は全て失敗となるため、可用性は保証できない。

非同期レプリケーション: ローカルストレージで書き込み完了すると同時に書き込み要求が完了したとみなす。リモートノードのストレージ更新までには遅延があるため、一貫性は保証できない。

Quorum

write quorum: 書き込み要求が完了したとみなすために必要な最低限の票 (リモートノードからのコミット完了通知) の数。前述の同期レプリケーションでは write quorum = リモートノードの数, 非同期レプリケーションでは write quorum = 0 とみなすことができる。

read quorum: 読み込み要求を完了するために必要な最低限の票 (同一なレプリケーションの数)。

あるデータのレプリケーション数を V, write quorum を $V_w$ , read quorum を $V_r$ とすると、以下の条件を満たすとき、強い一貫性が保証される。

\begin{aligned} V_w+V_r&>V\\ V_w&>\frac{V}{2} \end{aligned}

パーティション

パーティション (シャード, shard) は分散システムにおけるデータの分割を指す。

テーブルの分割方法には以下の 2 種類がある。

水平分割: 1 つのテーブルを行単位で複数のパーティションに分割する

垂直分割: 1 つのテーブルを列単位で複数のパーティションに分割する

ブルームフィルタ

あるデータがどのパーティションに含まれるかを管理するデータ構造に、MurmurHash をハッシュ関数とするブルームフィルタ (bloom filter) がしばしば使われる。

ブルームフィルタには偽陰性 (false negative) はないが、偽陽性 (false positive) による誤検出の可能性がある。偽陽性の発生率 $p$ は以下の式で表される。

\begin{aligned} p&=(1-(1-\frac1m)^{kn})^k\approx(1-e^{-kn/m})^k\\ m&:\text{配列のビット数}\\ n&:\text{要素数}\\ k&:\text{ハッシュのビット数} \end{aligned}

ブルームフィルタは同様の集合的データ構造の中で、圧倒的に空間効率 (メモリ使用量) において優れる。

アーキテクチャ

シェアード・エブリシング

シェアード・エブリシング (shared everything) は、分散システムにおいて、各ノードが同じパーティションを共有するモデルを指す。

プライマリ/バックアップ (マスター/スレーブ): 古典的な分散システムの多くがこのモデルを採用している。書き込み要求を司るプライマリノードと読み込み要求を司るバックアップノードに役割を分担する。プライマリノードが何らかの障害で停止すると、バックアップノードが役割を交代して計算を引き継ぐ。(フェイルオーバー) 非同期レプリケーションではプライマリノードの障害発生のタイミングによってはログの一部が失われる。

マルチプライマリ (マルチマスター): 任意のノードに更新要求を送ることができ、そこから他のサーバーに通知する。トランザクションがかち合うのを防ぐことが課題となり、非同期レプリケーションでは衝突を防ぐことはできないため、何らかの方法 (ex. 分散ロックマネージャ) で一貫性を保証しなければならない。

RAC (Real Application Clusters, シェアード・ディスク): Oracle RAC が採用している、各ノードが同じストレージを共有する構成。ここでは詳しく解説しない。

シェアード・ナッシング

シェアード・ナッシング (shared nothing) は、分散システムにおいて、各ノードが同じパーティションを共有しないモデルを指す。いずれかのノードが何らかの障害で停止すると、そのノードに割当てられていたパーティションが読めなくなるため、分断耐性は保証できない。

シェアード・ナッシングでは、異なるパーティションに対する結合を含むような問い合わせにおいて、シェアード・エブリシングよりも処理時間がかかる。

データが属するパーティションを決定する (パーティショニング, partitioning) 方法には以下の 2 つがある。

コンシステントハッシュ法: データの任意の部分 (ex. パーティションキー) にハッシュ関数を適用し、そのハッシュ値をパーティション数で割ったときの剰余によってパーティションを決定する。

アプリケーションパーティショニング: トランザクションが参照するパーティション数 (問い合わせるノード数) が最小になるよう、アプリケーションのユースケースの知識を含めて、アプリケーション側で最適なパーティションを決定する。前述した「異なるパーティションに対する結合を含むような問い合わせ」というシェアード・ナッシングの弱点を解消する。

ロードバランサ

ロードバランサ (load balancer) は、クライアントからの要求を適切なノードに割り当てることで負荷を分散 (ロードバランシング, load balancing) する。ロードバランサをマスター, 処理を行うノードをワーカー (worker) と呼ぶ。

また、ロードバランサはワーカーの死活状態を確認して (ヘルスチェック, health check) を行い、応答がないワーカーを選択対象から除外する。

ロードバランサには以下の 2 種類が存在する。

アプリケーションロードバランサ: リバースプロキシ (reverse proxy) として機能する。

ネットワークロードバランサ: L4 (トランスポート層) レイヤーで NAT (= Network Address Translator) として機能する。宛先 IP アドレスを選択されたワーカーの IP アドレスに書き換える。

ワーカーのヘルスチェックには以下のようなものがある。

L3 (ネットワーク層) チェック: ICMP (= Internet Control Message Protocol) echo リクエストを送信し、echo リプライが返ってくるかを確認する。

L4 (トランスポート層) チェック: TCP ハンドシェイクを行う。

L5 (セッション層) チェック: アプリケーションにリクエストを送信し、レスポンスを確認する。

ワーカーの選択方法には以下のようなものがある。

ランダム: ランダムにワーカーを選択する。

最小コネクション: 確立しているコネクションが最も少ないワーカーを選択する。

ラウンドロビン: 順番にワーカーを選択する。

DNS ラウンドロビン: ラウンドロビンを採用するロードバランシングにおいて、DNS (Domain Name System) をロードバランサとして利用する。ワーカーの情報がクライアントにキャッシュされたり、ヘルスチェックが不可能だったりと問題点が多い。

Web アプリケーションのロードバランシングでは、異なるワーカー間でセッションを共有する必要がある。具体的に以下のような方法がある。

常にセッション ID を発行したワーカーに割り当てる (スティッキーセッション)
高速なインメモリデータベース (ex. Redis, memcached) にセッションデータを共有する
セッションデータに秘密鍵で暗号化と署名を施したもの (ex. JWT トークン) をクライアントに送信させる

UUID

分散システム上で統制なしに作成できるデータの識別子の設計として UUID がある。

UUID v1 は 48 ビットのノードの MAC アドレス, 60 ビットのタイムスタンプ, 14 ビットのクロックシーケンスをもつ。

UUID v4 は乱数から 122 のビットのビットを生成する。 2 つの ID が偶然一致するまでの生成数の期待値は $2^{61}$ である。

カテゴリ