論文メモ Spanner: Google's Globally Distributed Database

November 27, 2020

Spannerは、世界中のデータセンタにデータを複製する高可用な分散データベースで、外部整合性のある分散トランザクションを保証する。ユーザからみると半リレーショナルなデータモデルのデータベースであり、各テーブルに一つ以上の順序つき主キーが必要なところがリレーショナルデータモデルと違う。一方、内部は文字列とタイムスタンプの組をキーにしたキーバリューストアであり、Single Paxos状態機械でデータの一貫性を守りながら複数のデータセンタにデータを複製する。

Spannerは、並行制御のために、現在時刻を提供するTrueTime APIをつかう。 APIは、次のインターフェースを備え、返す現在時刻の誤差が一定値以下であることを保証する。クラスタ内の正確な時刻が$\texttt{TT.now()}$の$\texttt{earliest, latest}$の範囲にあることを保証する。 TrueTime APIは、GPSと原子時計によって時刻の精度を確保している。

truetimeapi

Spannerは、スナップショットトランザクション、スナップショット読み込み、読み込み書き込みトランザクションを提供する。最初の2つは、読み込み専用のロックフリーなトランザクションであり、スナップショットトランザクションはスナップショット分離を実現し、Spannerが決めたある時点の状態のデータを読み込む。スナップショット読み込みは、ユーザの指定した時刻のデータを読み込むことができる。読み込み書き込みトランザクションは、悲観ロックであり、また、書き込みをサポートする唯一のトランザクションである。

外部整合性は、複数のサーバでトランザクションが実行されても、トランザクションが現時点でコミット済みの情報を参照できることを保証する。いいかえると、トランザクションT1のコミット後にトランザクションT2が開始した場合、T2のコミットタイムスタンプはT1のコミットタイムスタンプよりも常に大きい。トランザクション$T_i$の開始とコミットのイベントを$e^{\text{start}}_i, e^{\text{commit}}_i$, コミットタイムスタンプを$s_i$とおく。ただし、トランザクション$T_i$のコミットリクエストをサーバが受理するイベントを$e^{\text{server}}_i$とすると、$s_i$は、$e^{\text{server}}_i$の後に呼び出された$\texttt{TT.now().latest}$以上の値になっている。イベント$e$の発生時刻を$t_{\text{abs}}(e)$、True Time API(TT)より、 $$ tt=\texttt{TT.now()}, \texttt{tt.earlist}\le t_{\text{abs}}(e_{\text{now}})\le \texttt{tt.latest} $$ とすると、外部整合性を$t_{\text{abs}}(e^{\text{commit}}_1)<t_{\text{abs}}(e^{\text{start}}_2)\Rightarrow s_1<s_2$と書ける。

このとき、$s_1<t_{\text{abs}}(e^{\text{commit}}_1)$が成立するようにロック期間を伸ばすと

$$ \begin{align} s_1&<t_{\text{abs}}(e^{\text{commit}}_1)\\\ t_{\text{abs}}(e^{\text{commit}}_1)&<t_{\text{abs}}(e^{\text{start}}_2)\\\ t_{\text{abs}}(e^{\text{start}}_2)&\le t_{\text{abs}}(e^{\text{server}}_2)\\\ t_{\text{abs}}(e^{\text{server}}_2)&\le s_2\\\ s_1&< s_2 \end{align} $$ となり、外部整合性が成立する。

論文をこちらからダウンロードできます。
画像は論文から引用されています。