あなたが知らないFirestoreのコアテクノロジー

クックパッドの新規サービス[Komerco](https://komer.co/)を設計した[@1amageek](https://twitter.com/1amageek)です。

クックパッドの新規サービス[Komerco](https://komer.co/)は[TechConf](https://speakerdeck.com/1amageek/dong-kichu-sitakutukupatudofalsectocbizinesu)でも発表した通り全てサーバーレスで開発されています。サーバーレスの利点や開発におけるメリットは[この資料](https://speakerdeck.com/1amageek/dong-kichu-sitakutukupatudofalsectocbizinesu)に説明しているので、今日はFirestoreについて深く説明したいと思います。また、**Firestore**のざっくりした説明に関してはこちらをご覧下さい。

- [Cloud Firestoreは進化したFirebase Realtime Database](https://qiita.com/1amageek/items/8179aebe871beb230194)
- [Firebase RTDB + GCP datastore = Firestoreについて第一印象](https://qiita.com/Yatima/items/54ea22d0cea1acc6cbcb)


# FirestoreはSpannerと同じテクノロジー構築されている

FirestoreはSpannerと同じテクノロジー構築されています。つまりSpannerの特性を理解することでFirestoreのコアを知ることが可能です。この記事ではSpannerにフォーカスして説明して行きます。

[Spanner](https://cloud.google.com/spanner/?hl=ja)をご存知でしょうか？ **Spanner**はGoogleが提供している**地球規模**のデータベースです。**地球規模**と表現しましたが、ここが重要なポイントなのでぜひこのまま読み進めて貰えると嬉しいです。

Spannerのページでは次のように説明されています。

> 水平スケーリング可能で高い整合性を備えた、初のリレーショナル データベース サービス

水平スケーリング可能で高い整合性とはどう言うことでしょうか？データベースの根幹からSpannerについて理解して行きましょう。

## データベースがかかえるハードウエアの限界

データベースの特性はハードウエアに大きく依存しています。データベースは一体どのようなハードウエアの特性に縛られているのか考えてみましょう。まず容易に想像できるのは**マシンの性能**です。マシンの性能はCPUの**処理速度**だけでなくストレージの`Read/Write`速度や、**故障率**などもあります。
次に、私たちが利用するデータベースのほとんどはクラウドに存在するので**ネットワーク**にも依存します。ネットワークについてもう少しブレイクしてみましょう。ネットワークは**回線速度**と**距離**に依存しています。

### データベースは次のことを考える必要がある。

- 処理速度
- 故障率
- 回線速度
- 距離

上記の課題をインターネットの歴史でどのように解決してきたのでしょうか？実は全て同じ方法で問題を解決しています。それは**冗長化・並列化**です。

- 一台のマシンでは**処理速度**に限界があるので複数のマシンで処理する。
- マシンは必ず故障するので**故障率**を考慮して複数のマシンで運用する。
- 一つのネットワーク帯域では**回線速度**に限界があるので複数の回線を使う。
- 拠点を一つにすると**距離**が離れている通信に遅延があるので複数拠点を置く。

データベースでは**シャーディング**と呼ばれています。シャーディングの技術はクラウドのニーズが高まるに連れて重要度を増して行きました。**クラウド技術の中核は分散処理である**と言っても過言ではないと思います。

冗長化・並列化は**スケールアウト（水平スケール）**と呼びます、一方でマシンの性能を上げていく方法を**スケールアップ（垂直スケール）**と呼びます。

あらゆるデータベースにシャーディングの機能は備わっています。`Spanner`にももちろん備わっています。では他のデータベースと`Spanner`では何が違うのでしょうか？

それを理解するためには、データベースの重要な機能であるトランザクションについて知る必要があります。

## トランザクション
データベースの中でも非常に重要な機能が**トランザクション**です。トランザクションとはなんでしょうか？ 

#### トランザクションとは
> コンピュータ システムにおける、永続的なデータに対する不可分な一連の処理。

よくわかりませんね。素晴らしい記事があるのでこちらをご参考ください。

- [データベースさわったこと無い新人向けトランザクション入門](https://qiita.com/komattio/items/838ea5df68eb076e8099)
- [トランザクションの基本](https://qiita.com/kumagi/items/e93a57535db04e66368f)

ざっくり言うとこんな感じです。

> 分散処理すると並列に複数の処理が同時に走ることになるので、データの整合性が取れなくなります。整合性を取るためにルールを設け運用する。

データの交通整理をする技術と想像してもらえるといいと思います。実際にデータベースは、データに対して赤信号（ロック）のようなものを出してデータをせき止めたりしています。

## トランザクションと同時実行制御

トランザクションについてもう少し理解を深めて行きましょう。Spannerは`直列化可能性`を持ったデータベースです。`直列化可能性`とは

> 分散コンピューティングにおいて、トランザクションスケジュール(履歴)の結果(最終的なデータベースの状態およびデータベースデータの値)がトランザクションを直列的に実行した場合、つまり、時間的な重複無くシリアルに実行した場合と結果が等しい時、直列化可能である、あるいは直列化可能性という性質を持っていると言う。


- [トランザクションを知ればデータベースがわかる―「データ復旧」「同時実行制御」を行う“不完全な”しくみ](http://gihyo.jp/dev/serial/01/db-academy/000203)

ざっくり言うとこんな感じです。

> 処理を並列化しても、直列的な結果を得られること

### Spannerのトランザクション
Spannerのトランザクションは次のように実行されます。

<img width="763" alt="スクリーンショット 2018-03-23 15.14.48.png" src="https://qiita-image-store.s3.amazonaws.com/0/80287/0831cba1-49ca-d0b7-7687-d5c39eb9c48c.png">

> 青色のトランザクション Txn1 は、データ A を読み取り、書き込みを A でバッファリングして、正常に commit します。緑色のトランザクション Txn2 は Txn1 の後に開始し、データ B を読み取った後、データ A を読み取ります。Txn2 は、Txn1 が A への書き込みを commit した後に A の値を読み取るので、Txn1 の完了前に Txn2 が開始したとしても、Txn2 は Txn1 が A に書き込んだ効果を見ることができます。

> Txn1 と Txn2 の実行時間には多少のオーバーラップがあるものの、commit タイムスタンプ c1 および c2 は線形のトランザクション順序に従います。つまり、Txn1 の読み取りと書き込みのすべての効果が単一の時点（c1）で発生したように見え、Txn2 の読み取りと書き込みのすべての効果が単一の時点（c2）で発生したように見えます。更に、c1 < c2 となります（これは、Txn1 と Txn2 の両方が書き込みを commit することで保証されます。

[直列化可能性と外部整合性](https://cloud.google.com/spanner/docs/transactions?hl=ja)より引用。

# トランザクションの性能

ここでトランザクションの性能は何に依存しているのか考えて見ましょう。データベースは、その性能と可用性を向上させるために分散させて来ました。しかし大規模に分散化させていくと一貫性を保証するトランザクション処理は困難になって行きます。なぜでしょうか？

その原因は時間にあります。分散化されたデータベースでは時間を原因としてどのような問題が発生するのでしょうか。その問題を理解するためまず外部整合性を理解して行きましょう。外部整合性は他のデータベースが持っていないSpannerの特徴でもあります。

### 外部整合性

外部整合性について、次のように説明されています。

> 外部整合性は、強整合性と追加的なプロパティ（直列化可能性と線形化可能性など）を兼ね備えたプロパティです。

> Spanner ではトランザクションの挙動が、トランザクションが順次実行された場合と同じになり、かつトランザクションが実際に実行される順序と、トランザクションの commit が認識される順序が必ず整合することを意味します。

> 外部整合性は、線形化可能性よりも強いプロパティです。線形化可能性は、単一オブジェクトに対する単一の読み取りまたは書き込みオペレーションのみがトランザクションに含まれる、外部整合性の特殊なケースと見なすことができます。

ざっくり言うと

> 順番に実行された2つのトランザクション`t1` `t2`を考え、最初に実行された`t1`よりも後に実行された`t2`のタイムスタンプは必ず`t1.timestamp < t2.timestamp`となる

もっとざっくり言うと

> 現実に実行された順番通りにデータベースに保存する

一つのマシンで直列実行していた場合であれば、至極当然のような整合性ですが、別々のマシンで並列化された場合であればそうも行きません。

2台のマシンを考えそれぞれほぼ同時にトランザクションが実行されたと想定します。この時２台マシンでタイムスタンプがずれていたとすればどうでしょうか？ 例えば2台のマシンでタイムスタンプが`Δt`ずれているとします、実際は`t1`より`t2`の方が後の実行されたとしても、次のようにずれの方が大きい場合、t2の方が先に実行されたように記録され整合性が保てなくなります。

```
t2.timestamp - t1.timestamp < Δt
```

<img width="741" alt="スクリーンショット 2018-03-23 21.18.56.png" src="https://qiita-image-store.s3.amazonaws.com/0/80287/fd1d2b97-cbf3-f427-82f4-e2fb7c6e9a67.png">

これが、分散化されたデータベースに起こる問題です。これを`クロック不確実性問題`と言います。
そして`Δt`を極限まで小さくすることが整合性を保つには非常に重要であると言えます。

- [Cloud Spanner: TrueTime と外部整合性](https://cloud.google.com/spanner/docs/true-time-external-consistency?hl=ja#2)
- [Cloud Spanner が外部整合性を提供する理由](https://cloudplatform-jp.googleblog.com/2018/03/why-you-should-pick-strong-consistency-whenever-possible.html)
- [Information Storage in a Decentralized Computer System](http://bitsavers.org/pdf/xerox/parc/techReports/CSL-81-8_Information_Storage_in_a_Decentralized_Computer_System.pdf)
- [Spanner](https://qiita.com/kumagi/items/7dbb0e2a76484f6c522b)


# TrueTimeとCommit Wait

Spannerは**TrueTime**と**Commit Wait**と呼ばれる技術を用い外部整合性を実現します。Commit Waitはコミットが完了した後`２ε`の時間の間意図的にロックを保持します。そして`ε`はTrueTimeによって保証されます。

### TrueTime

> TrueTime は、すべての Google サーバー上のアプリケーションに提供される高可用性分散クロックです。

簡単に言うとGoogleが提供するNTP(Network Time Protocol)です。普通のNTPとの違いは、極限まで**離れたサーバ同士の時間を同一に保つ**ことを実現していることです。NTPでは情報がネットワークを行き来する際に誤差が生まれ、完全に正確な時刻同期はできません。
TrueTimeはとってもGoogleらしく強力な方法でこの問題を解決しています。

#### TrueTimeのテクノロジー

**各データセンターに原子時計とGPS受信機を備え**、マスターサーバーへ接続されています。これにより地球上でどこにいても`ε`以下の誤差で同期された時間を取得出来るようになりました。

TrueTimeはSpanner内の時刻の誤差を`ε`以下に抑えるように時刻を頻繁に再同期し、同期が取れないマシンを故障としてサーバーから除外することに利用されています。

- [グーグル「Spanner」：地球大のリアルタイム・データベース](https://wired.jp/2012/11/28/google-spanner-time/)

- [Spanner: Google's Globally-Distributed Database](https://static.googleusercontent.com/media/research.google.com/ja//archive/spanner-osdi2012.pdf)

また、地球規模で分散化されたデータベースでは、通信速度に律速し、トランザクションの性能を落として行きます。Spannerでは次のようにそれを解決しています。

- すべてのデータセンターが3本以上の独立したプライベートな光ファイバー回線で接続されている
- 2フェーズコミットと[Paxos](https://ja.wikipedia.org/wiki/Paxos%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)グループを用いている
- TrueTimeを使って全てのデータベースの時間を高精度で同期する

# まとめ

- 分散化されたデータベースでトランザクションの性能を保つため、各データセンターの時間の誤差が小さくする必要がある。
- 誤差よりも長い時間データベースをロックするとことで整合性は保証できる。
- 誤差を最小にすることで性能を向上できる。
- Spannerは原子時計とGPSを用いで誤差を最小化している。