前提知識
Google File System (現 Colossus)
Google File System (以下 GFS) は大量のデータを扱うための分散ファイルシステムである。
アーキテクチャ
- 1 つのマスターと最大 3 つのチャンクサーバーから構成される。
- 1 つのファイルは大量のチャンクに分割される。
- 1 つのチャンクは複数のチャンクサーバーにコピーされる。
- 同期レプリケーション
- 結果整合性
- GFS 自体にロック機能はない (後述の Chubby と組み合わせることで実現可能)
読み書き
読み込み
- クライアントはマスターに、ファイルを構成するチャンクの情報と、すべてのチャンクサーバーのアドレスを問い合わせる。
- クライアントはネットワーク距離が最も近いチャンクサーバーに各チャンクを要求する。
- チャンクサーバーからの読み込みに失敗した場合、クライアントは他のチャンクサーバーにチャンクを要求する。
書き込み
- クライアントはマスターにチャンクへの書き込みを要求する。
- マスターは書き込みのまとめ役となるチャンクサーバーを決定する。このチャンクサーバーをプライマリと呼び、それ以外のチャンクサーバーをセカンダリと呼ぶ。
- クライアントはネットワーク距離が最も近いチャンクサーバー (プライマリでなくてもよい) に書き込みたいデータを送信する。
- チャンクサーバーは、まだ書き込みデータを受け取っていないチャンクサーバーに同じデータを送信する。
- プライマリは書き込みデータのシリアルナンバーを決定し、マスターに通知する。
- プライマリは手元のチャンクにデータを書き込む
- プライマリは全てのセカンダリに対してデータを書き込むように要求する
Bigtable
Bitable は高性能な構造データのための分散ストレージシステムである。
アーキテクチャ
- Chubby と 1 つのマスターと複数のタブレットサーバーで構成される。
- テーブルは行キーとカラムキーとタイムスタンプから成る多次元構造になっている。 (多次元マップ, Multi Dimensional Sorted Map)
行キーとカラムキーとタイムスタンプの 3 つを指定することで 1 つのデータが得られる。
- テーブルデータは水平分割され、この分割 (パーティション) のことを Bigtable ではタブレット (tablet) と呼ぶ。
- 1 個のタブレットは、マスターによって 1 つのタブレットサーバーに割り当てられる。
1 つのタブレットサーバーは 10 個〜1000 個のタブレットを管理する。
- タブレットサーバーは定期的に自分の状態を Chubby に書き込み、マスターは Chubby を通してタブレットサーバーの状態を確認する。
- タブレットのデータは GFS 上に保存される。
タブレットデータの冗長化は GFS が担う。
- インデックス部分とデータ部分からなる読み取り専用ファイル SSTable
- コミットログ
- SSTable のインデックスと、SSTable に書き出される前のデータをメモリ上の領域 (memtable) に保持
読み書き
- クライアントは Chubby にルートタブレットを管理するタブレットサーバー (以下 META0) を問い合わせる
- クライアントは META0 に、目的のキーが含まれるメタデータタブレットを管理するタブレットサーバー (以下 META1) を問い合わせる
- クライアントは META1 に、目的のキーを含むタブレットを管理するタブレットサーバーを問い合わせる
書き込み
- タブレットサーバーは書き込みたいデータを GFS 上のコミットログに保存する。
- タブレットサーバーは memtable 上のデータを更新する。
- タブレットサーバーはクライアントにコミット完了を通知する。
読み取り
- タブレットサーバーは、memtable 上の SSTable に書き出される前のデータに目的のキーが存在していれば、そのデータをクライアントに返す。
- タブレットサーバーは、memtable 上のインデックスから SSTable に目的のキーが存在するか調べる。ここで何も見つからなければ、検索は失敗に終わる。
- タブレットサーバーは、目的のキーに対応するデータがメモリ上のキャッシュ (後述) 上に存在していれば、それをクライアントに返す。
- タブレットサーバーは、目的のキーに対応するデータを GFS 上の SSTable から取得してメモリ上のキャッシュに書き込み、クライアントに返す。
コンパクション
- マイナーコンパクション (minor compaction)
memtable が大きくなったときに、新しい SSTable に memtable の内容を書き出す。
- メジャーコンパクション (major compaction)
- SSTable が増えすぎたときに、それらを 1 つの SSTable に統合する。
障害からの復旧
タブレットサーバーの障害
- マスターは、障害が発生したタブレットサーバーに割り当てられていたタブレットを、他のタブレットサーバーに割り当てる。
- 新しいタブレットサーバーは、GFS 上の SSTable のインデックス部分を古いものから memtable に取り込む。
- 新しいタブレットサーバーは、コミットログから SSTable に書き出されていない最近の変更内容をロールフォワードする。
高速化の工夫
キャッシュ
- スキャンキャッシュ (Scan Cache)
- 最近アクセスされたキーに対応するデータを記憶するキャッシュ。
- ブロックキャッシュ (Block Cache)
SSTable からデータを読み込むときに、そのデータが含まれるブロック全体
(デフォルトで 64KB) を記憶するキャッシュ。
ローカリティグループ
同時に利用される可能性の高いカラムキーに対応するデータをローカリティグループ (Locality Group) としてグループ分けし、グループごとに SSTable を分離できる。
また、特定のローカリティグループの SSTable を完全にメモリ上に読み込むことができる。
Chubby
Chubby は小さなファイル (1kB 未満) の管理を目的とする高機能なネットワークファイルシステムである。
アーキテクチャ
- 1 つのマスターと 4 つのレプリカで Chubby セル (Chubby cell) を構成する。
- マスターが応答しなくなると、1 つのレプリカがマスターになる。
- 全てのノードが同等のデータベースを保持するシェアード・エブリシング・モデル。
- 非同期レプリケーション
- 結果整合性
- バックアップはその Chubby セルとは別のデータセンターの GFS に保存される。
これは GFS 自体が Chubby に依存しているためである。
機能
アクセスコントロール
ファイルロック
ロックは強制力をもたず、クライアントがロックに従ってアクセスを抑制する、アドバイザリロック (Advisory Lock) として機能する。
ロックモードは以下の 2 種類が存在する。
クライアントが応答しなくなった場合、一定時間で自動的にロックが解除される。
一時ファイル
使われなくなると自動的に削除されるファイルを作成できる。
各ノードは一時ファイルを作成することで自分がいま起動していることを他のノードに知らせる。
イベント通知
- Chubby ファイルを作成したり、その内容を書き換えると、それを監視しているクライアントにイベントが送られる。
- ディレクトリにファイルが作成 or 削除されると、そのディレクトリを監視しているクライアントにイベントが送られる。
Chubby を Broker, ファイルを Topic とする Pub/Sub 分散メッセージングシステムとして利用できる。
読み書き
ファイルの読み書きは全てマスターに対して要求する。
読み込んだファイルはクライアント側でキャッシュされる。
Chubby 側のファイルの内容が更新されるとき、Chubby は全てのクライアントにキャッシュを破棄するようにイベントを通知する。
特殊な Chubby セル
local
ネットワーク距離が最も近い Chubby セル。
/ls/local 以下への書き込み要求はクライアントからネットワーク距離が最も近い Chubby セルで処理される。
global
世界中のデータセンターをまたいで分散されている Chubby セル。
/ls/global/master 以下に書き込んだファイルは、 /ls/(任意の Chubby セル名)/slave から読み込むことができる。
global セルの主な用途を以下に示す。
- 各種アクセスコントロール
- サービスレジストリ
- Bigtable のメタデータを管理するタブレットサーバーの管理
障害からの復旧
Chubby セルのマスターが停止した場合、他のレプリカがマスターに切り替わる。 (フェイルオーバー)
このときに発生しうる問題を以下に示す。
- フェイルオーバーに時間がかかってクライアント側の処理がタイムアウトしてしまう。
- 古いマスターから送られるはずだったイベント通知が失われる。
利用用途
分散ロックサービス
ロック機能をもたない外部のリソースに対してロックサービスを提供する。
- クライアントは Chubby に対してリソースのロックを要求する。
- Chubby はリソースのロック状態を書き込み、シーケンサというロックの識別子をクライアントに返す。
- クライアントはリソースサーバーに対してシーケンサと要求を送信する。
- リソースサーバーはシーケンサで識別されるロックがまだ有効であるか Chubby に問い合わせる。
- クライアントは、Chubby に問い合わせたシーケンサが無効であれば、処理を中止してクライアントにエラーを返す。
DNS
一般的な DNS は生存期間 (TTL, Time To Live) を過ぎたレコードを破棄するため、DNS への問い合わせが頻繁に発生する。
Chubby を DNS として利用することで、DNS レコードはクライアント側でキャッシュされ、イベント通知によって Chubby セル全体で結果整合性が保たれる。
プライマリ/バックアップの交代
プライマリ/バックアップからなる分散システムにおいて、プライマリとなるノードを決定する。
Chubby 上にプライマリのサーバーアドレスを管理するファイルを作成しておき、そのファイルの排他ロックを獲得したノードが自分のアドレスを書き込むことでプライマリとなる。
プライマリから Chubby への応答がなくなると一定時間でロックが解除され、バックアップが新たに排他ロックを獲得し、プライマリが交代する。