Cloud Datastore は Entity 毎になぜ秒間1回の書き込み制約があるのか
はじめに
Cloud Datastore では 1 write / entity group / sec という制約があります (公式ドキュメント)。
確かに Datastore を使っていると、同一 Entity Group に対する書き込み頻度が高い時に一部の書き込みが失敗することは経験上よくありましたが、 なぜこの制約が存在しているのかはドキュメントに詳しくは記載されていませんでした。 そこで Cloud Datastore のバックエンドである Megastore の論文「Megastore: Providing Scalable, Highly Available Storage for Interactive Services」をベースに、その理由を調べてみました。
※公開されている情報から推測しているので、間違っていた場合ご指摘下さい。
TL;DR
先に結論を述べると、レプリカ間で書き込みデータのレプリケーションを行なう手続きに、最大で1秒ほどの時間がかかるためです。
より詳しく述べると、Cloud Datastore の以下の特徴から書き込みスループットの制約が存在します。
- 高可用性を実現するためにデータセンターを跨いで複数のレプリカを動かしており、レプリカ間で同期的なレプリケーションを行っている
- どのレプリカからも読み込み・書き込みが開始でき、クエリによっては Strong Consistency なデータを取得できる
- レプリカ間でのレプリケーションには Paxos を用いており、Paxos の手続きの完了にデータセンター間で 1RTT もしくは 2RTT のネットワークレイテンシを要する
Megastore のアーキテクチャ
Megastore は高い可用性を実現するためにデータを地理的に離れた複数のデータセンターで保持していますが、 各ノードで一貫性のあるデータ読み込みを実現するために、ノード間で同期的なレプリケーションを行っています。
レプリケーションはマスター・スレーブのような構成ではなく、全てのノードから Read / Write を発行できるマルチマスターのようなレプリケーションとなっており、各ノードは「レプリカ」と呼ばれています。
つまり、同じ内容を保持しているデータベースが地理的に離れた箇所に複数デプロイされている形です。
Read 手順
Megastore での Write 手順を見る前に、参考までに Megastore からのデータ読み込みがどういう手順で行われるか見てみます。
論文の "4.6.2 Reads" から引用すると、読み込みは以下の手順で行われます。
- Query Local: 地理的に最も近いレプリカの Coordinator に、所持している Entity Group のデータが最新かどうかを問い合わせる。
- Find Position: 1番で最新だった場合、選択したレプリカから Entity Group の最新のログポジションとタイムスタンプを取得し、3番、4番の処理をスキップする。最新でなかった場合、他の全てのレプリカにログポジションを問い合わせ、過半数の結果を採用する。
- Catchup: 2番で取得した最新のログポジションを元に他のレプリカからログ (= Write Ahead Log) を取得し、自身のデータベースに適用していく。
- Validate: Coordinator に今持っている Entity Group のデータが最新であることを伝える。
- Query Data: 選択したレプリカから Engity Group のデータを読み出す
この手順を見ると、仮にあるレプリカが他のレプリカと比べて古いデータを保持していたとしても、一連のシーケンスの中で他のレプリカへの追いつきが走るようになっています。 つまりどのレプリカから Read しようとしても、必ずシステムに最後にコミットされた最新のデータが読み取れること (Strong Consistency) が保証されています。
Write 手順
次に書き込みの手順です。
書き込む値のレプリケーションは Paxos を使って行われます。 通常の Paxos は合意形成に至るまでノード間の通信が少なくとも2回 (Prepare phase & Accept phase) 必要ですが、 Megastore が実装している Paxos ではノード間の通信を最短で1回のラウンドトリップで済むような拡張を入れています。
論文の "4.6.3 Writes" から引用すると、書き込みは以下のような流れで行われます。
- Accept Leader: リーダーレプリカに proposal number = 0 で Proposal を投げる。これが成功した場合2番をスキップする。
- Prepare: 全てのレプリカに Prepare メッセージを投げる。
- Accept: リーダー以外の全てのレプリカに Proposal を投げる。全てのレプリカが Accept した場合4番をスキップする。
- Invalidate: 3番で一部のレプリカが Accept しなかった場合、そのレプリカの Coordinator に対して Invalidate メッセージを送る(そのレプリカが持つ現在の値を読ませないようにするため)。
- Apply: 合意した変更点を実際のストレージ(Bigtable)に適用させる
1番の Accept Leader フェーズが Paxos の拡張になっており、後続の Prepare フェーズをスキップ出来るようになっています。 これは1つ前の書き込みの完了に、その次の Prepare の意味も持たしていることから来ていますが、より詳細な前提条件の説明が必要なため、詳しくは論文の "4.4.2 Fast Writes" を参照して下さい。
Write が完了するタイミング
このシーケンスのなかで、元の Client に書き込みの完了 (Ack) を伝えれるのは3番、もしくは4番が終わったタイミングになります。 よって最短で書き込みに要するネットワークレイテンシは、
# 全てのレプリカが Accept した場合 RTT(Client, A) + MAX(RTT(Client, B), RTT(Client, C)) # 一部のレプリカが Accept しなかった場合 RTT(Client, A) + MAX(RTT(Client, B), RTT(Client, C)) + RTT(Client, C)
となりますが、Client ↔ Replica A 間は地理的になるべく近い場所にいる(ように Leader を選ぶ)ため、両者の RTT は非常に短い時間だと考えられます。 よってその時間は十分無視できるとすると、
# 全てのレプリカが Accept した場合 MAX(RTT(Client, B), RTT(Client, C)) # 一部のレプリカが Accept しなかった場合 MAX(RTT(Client, B), RTT(Client, C)) + RTT(Client, C)
となり、大体1RTT、もしくは2RTTかかることになります。
仮にレプリカがアメリカの西海岸と東海岸に配置されていると仮定すると、レプリカ間のRTTは約120msです。 (参考: AT&Tが公開しているネットワークレイテンシから、サンフランシスコとニューヨーク間のレイテンシ: 62ms を持ってきました。)
よって、書き込みのレイテンシはネットワークレイテンシに実際の各レプリカの処理時間を乗せたものになるので、150ms〜300msくらいが標準的な書き込み時間になるのではないでしょうか。
そしてトランザクション内での Entity Group に対する書き込みはシリアライズ化されているので、この書き込み1回あたりのレイテンシがそのままスループット制約となります。
Google で計測されたレイテンシ
論文の "4.10 Production Metrics" に Google の本番環境での Megastore の読み込み・書き込みレイテンシが載っていました。 それによると、平均的なアプリケーションは大体100ms〜500msで書き込みが完了しているようです。 ただし、この値はデータセンター間の距離や、レプリカ数に依存するとも述べられているので、場合によっては1秒近くかかってしまうこともあるのでしょう。
まとめ
Cloud Datastore の 1 write / entity group / sec の制約について調べ、データセンター間での同期的なレプリケーションに要する時間がネックになっていることを説明しました。 ちなみに Megastore の論文の中でも "4.8 Write Throughput" において、書き込みのスループットが高くないことを課題として挙げています。
Our implementation of Paxos has interesting tradeoffs in system behavior. Application servers in multiple datacenters may initiate writes to the same entity group and log position simultaneously. All but one of them will fail and need to retry their transactions. The increased latency imposed by synchronous replication increases the likelihood of conflicts for a given per-entity-group commit rate.
(訳) 私達の Paxos の実装はシステムの動作に興味深いトレードオフをもたらします。複数のデータセンタ上のアプリケーションサーバから、同一 Entity Group の同一ログポジションに同時に書き込みを行おうとするかもしれません。その場合、その内の一つを除いた全てのクライアントはトランザクションをリトライする必要があります。(Megastore が行っている)同期的なレプリケーションによって生じる高いレイテンシは、ある Entity Group に対するコミットがコンフリクトしてしまう可能性を上げることになります。
このパフォーマンス上のボトルネックを解決することを1つの目的として、後続のデータベースである Spanner の開発に繋がっていったようですね。
