Spannerの原論文を読む1

Spannerは面白い

お久しぶりです。最近、分散システムやPublic Cloudの裏側を支えるシステムについて理解したいと思うことが増えました。てなわけで、気になるサービスの元論文を読もうと決断したわけです。
率直に一番すごいサービスに思えたSpannerを理解したい！がモチベです。分散システムとRDBの皮を被ったキーバリューシステムであるSpanner。面白いのでぜひ見てってください！

Spannerの基礎知識

SpannerはGoogleによって設計、構築されたScalableでグローバルに分散したデータベースです。
Spannerはデータ量やサーバの数に応じてデータを自動で分割し、負荷分散や障害対応のためにデータをマシン間で自動的に移行します。Spannerのすごいところは、高可用性を維持するために、非常に低遅延で大陸を超えたレプリケーションを実現しているところです。元々はGoogleの広告バクエンドであるF1の裏側を支えるプロジェクトだったようです。概要はこれくらいにして実装レベルを見ていきましょう。

Spannerの実装

まず、Spannerのデプロイメントはユニバースと呼ばれます。Spannerはデータをグローバルに管理しますが、それを支えるのがこのユニバースです。Spannerはこのユニバースの上に乗ってます。
ユニバースとは別に、管理上のデプロイメント単位としてゾーンというものがあります。ゾーンは物理的隔離の単位です。同じデータセンターの中に複数のゾーンがあることもあります。
下の図はSpannerユニバース内のサーバーを表しています。

まず、シングルトンなインスタンスとしてユニバースマスターとPlacement Driverが存在します。
ユニバースマスターは全ゾーンの情報を一元的に見ることができるインターフェース(Console)であり、Placement Driverは数分単位でゾーン間のデータ移動を自動処理してくれます。
また、更新されたレプリケーション制約に対応するために、データを移動してくれたりします。
レプリケーション制約の更新とは、データがどのZoneに複製されるか、いくつのコピーを作成するかなどの設定です。例えば、新しいデータセンター（新しいZone）が追加された場合、SpannerはそのZoneを使ってデータのレプリケーションを増やす必要があるかもしれません。逆に、あるZoneが使用停止となった場合、そのZoneにあるデータを他のZoneに移動する必要があります。
1つのゾーンには1つのゾーンマスターと数千台のSpan Serverがあります。ゾーンマスターはSpan Serverにデータを割り当て、Span Serverはクライアントにデータを提供します。
ここまでで大まかな概要を説明したので、ここからはさらに詳しく見ていきましょう。

Span Serverのソフトウェアスタック

ここでは、Span Serverの実装に焦点を当てて、どのようにしてレプリケーションと分散トランザクションが実装されているかを説明します。

上の図はSpannerのソフトウェアスタックが示されています。各Span ServerがTabletと呼ばれるデータ構造のインスタンスを100-1000個担当しており、Tabletのデータ構造は以下のようになっています。

(key:string, timestamp:int64) -> string

Spannerはデータにタイムスタンプを割り当てている点がBigTableとは違います。この点においてSpannerは単なるキー•バリューストアよりも多バージョンデータベースに近いと言えます。
Tabletの状態はBTreeに似たファイルセットとGFSの後継である分散ファイルシステムColossus上のWALに保存されます。Tabletには現在のデータ状態だけでなく、過去のバージョンやトランザクションの一貫性を保つための情報が保存されていますが、Tabletに対して書き込みが発生するためにWALに書き込み、障害耐性のためにもWALは同じPaxosグループに登録されてるノードにもレプリケートされます。Paxosグループとは、特定のトランザクションによる書き込みを反映させるノードのグループであり、レプリケートを置くノードのグループです。Paxosアルゴリズムとは分散システムにおける合意形成アルゴリズムの一種ですが、僕も深くは理解してないのでそういう物だと受け入れました。
各ノードにはPaxos状態マシンが実装されています。Paxos状態マシンとは、Paxosアルゴリズムによって管理される「状態」を一貫性のある形で保持・更新するためのシステムです。
この状態システムを各ノードが実装していることでレプリケーションを配置するPaxosグループ間で、一貫してデータの更新を行うことができます。Paxosグループ間で一貫して更新をかけるための仕組みとして、それぞれのレプリカグループには、マスターレプリカとスレーブレプリカが存在し、更新はマスターレプリカのみにかけられ、その後スレーブにもその変更が伝播されます。一方読み取り操作に関しては、スレーブからでもマスターからでも行うことができます。
各グループのマスターレプリカには、書き込みをリードするだけでなく、各Span Serverが並行制御を実装するためのロックテーブルも実装されています。ロックテーブルには、どのデータがロックされているかが記録されているため、例えロックを取る操作が並行に走ったとしても競合が起きないようにマネージすることができます。
また、各Paxosグループのマスターレプリカには、各Span Serverが分散トランザクションをサポートするためのトランザクションマネージャーも実装してます。トランザクションの中には、単体のPaxosグループで完結するものもあれば、複数のPaxosグループを跨ぐものもあります。トランザクションマネージャが必要なのは後者の時で、各グループのリーダーが協力してTwo-Phase Commitを実行します。Two-Phase Commitとは、コーディネータと呼ばれるリーダ役がそれ以外のノードにトランザクションを行う準備ができたかを確認し、全員が準備完了ならコミット、そうでないならロールバックする仕組みのことです。

ディレクトリと配置

ここではディレクトリという新たな概念が登場します。
SpannerはデータをTabletという単位で管理してますが、それをさらに柔軟に扱うためにディレクトリという概念が導入されています。Tabletは物理的なデータの格納と整合性を担保する単位でしたが、ディレクトリはデータを地域やアクセス頻度に基づいて配置し、ローカリティとレプリケーションを管理するための単位です。ディレクトリは共通のPrefixを持つキーの集まりで、データがbucketのように集められているイメージです。Spannerはディレクトリ単位でデータの配置を管理し、同じディレクトリ内のデータはすべて同じレプリケーション設定を持ちます。例えば、ディレクトリ内のデータが頻繁にアクセスされる場合、Spannerはそのディレクトリ全体をアクセス頻度の高い場所に移動させて、パフォーマンスを向上させることができます。また、異なるPaxosグループにデータを移動する場合、ディレクトリ単位での移動が可能です。移動する際にクライアントからのRead-Write操作共に続行できるため、パフォーマンスを落ちる心配もありません。
ディレクトリが大きくなりすぎると、Spannerはそのディレクトリを複数のフラグメントに分割され、管理されます。要するにデータはディレクトリという単位にまとめられた上で、複数のタブレットにまたがって格納され、Paxosプロトコルによりデータの整合性が確保されています。

データモデル

Spannerのデータモデルは、リレーショナルデータベースのテーブルに似ています。テーブルにはスキーマ（構造）があり、行と列を持ち、各値はバージョン管理されています。半リレーショナル」とされるのは、純粋なリレーショナルデータベースとは異なり、キー・バリューストアの要素も取り入れているからです。SpannerはSQLに似たクエリ言語を提供しており、ユーザーは複雑なデータクエリを実行することができます。さらに、Googleが開発した「プロトコルバッファー」というデータ形式にも対応しています。またSpannerのテーブルには階層構造があり、親子関係でデータがまとめられます。この階層構造により、同じ親データに関連する子データを近い場所に保管できるため、効率的なアクセスが可能です。たとえば、あるユーザーのデータが1か所に集まることで、分散システムでも高いパフォーマンスを発揮できます。

まとめ

一旦ここまで！True timeのところは次の記事でまとめますー