Spannerお勉強メモ

Spannerお勉強メモです。かなり久々の技術系エントリだ。。

朝起きてTwitterみてたら@ichiro_satoh先生のこんなつぶやきが。

現時点ではGoogle Spannerの一番詳しい資料かも。berlinbuzzwords.de/sites/berlinbu…

— ICHIRO SATOHさん (@ichiro_satoh) 6月 6, 2012

。。やっぱりGoogleのインフラ情報は学会発表で流れてくるケースが多いなぁと思いつつ、先日公開されたF1（Google規模でスケールするRDB。AdWords用に使われてる）でもSpannerが重要なカギを握っているので、ついカッとなってスライドの要点を訳してみました。

原文はこれです：Building Spanner - Better clocks → stronger semantics（セッションのビデオ）

一行に要約すると、GPSと原子時計で正確なタイムスタンプを全サーバーに供給して、グローバル規模で整合性とれた分散データベース作ったよって話です。だと思います。

佐藤先生の感想：

続き。分散アルゴリズム研究では高精度の時計がないことを前提に複雑なら手順を数多く提案してきましたが、GPSによる時刻合わせを前提にしたら、その多くは無駄になるということ。

— ICHIRO SATOHさん (@ichiro_satoh) 6月 7, 2012

ですよね。。Lamportクロックとか（ちゃんと読めばそんなに難しくないそうです）難しい論文理解して実装したりしなくてよいわけですね。。シンプルでGooglyなソリューションかも！

Togetterまとめ（6/8追記）

皆さんのSpannerに関するつぶやきをまとめました：

• Google Spannerまとめ

Linealizabilityについて（6/12追記）

Linearlizabilityってなんぞ。。と考えてみました。

• SerializabilityとLinearlizabilityの違いの俺的理解

Building Spanner - Better clocks → stronger semanticsの試訳

注）公開情報のみを元にした個人的な試訳なので、内容はけっこう間違ってると思いますし、私の雇用者とは関係ありません。
注）全角カッコ内（）は訳者補足です。

• Spannerを作る
  • クロックをよくすればセマンティクスも強くなる
  • Alex Lloyd, Senior Staff Software Engineer

• 地球規模でserializableなDBの作り方
  • bounded absolute error（なにそれ）なクロックを作ってタイムスタンプを発行
  • 半順序なTX（での利用）を前提とした全順序なタイムスタンプ
  • 全体でserializableなクエリを実現

• Spanner
  • Bigtableの末裔、Megastoreの子孫
  • Paxosでレプリケーションを実現したスケーラブルでグローバルなDB
  • 地理的パーティショニング
    • 流動的：オンラインでのデータの移動
    • （インフラ詳細の）隠蔽：DBのセマンティクスレベルでは（地理的パーティショニングを）意識しなくてよい

• なぜSpannerか？
  • 目標：Googleスケールの高機能なアプリケーションを簡単に開発（できるインフラを提供）
  • Megastoreで学んだこと
    • （長所：）ACIDを確保した（同期）レプリケーション
    • （課題：）パフォーマンス、クエリ言語のサポート、しっかりしたパーティショニング
  • Bigtableで学んだこと
    • （長所：）スケーラビリティ、スループット
    • （課題：）複数のエンティティ（グループ）をまたがると生じる結果整合性の扱いにくさ（←でいいのかな？）

• Spannerのデータモデル概要

• Spannerの物理的表現

• Spannerの並行性
  • デフォルト設定：serializability（＝SERIALIZABLE？違う意味と @masayh さんからご指摘いただきました。）
    • read-modify-read TXには厳格な2相ロックを実施
      • パーティションを超えると2PCになりかなり遅い（2PCと2PLって違うの？）
    • read-only TXにはsnapshot isolationを提供（ロック不要）
      • パーティションを超えてもタイムスタンプ確認程度なのでそんなに遅くない
  • オプション機能：過去に遡ったserialize read（過去のスナップショットで読めるってこと？）
    • すべてのデータを対象に一貫性確保したMap Reduce（が可能に）
    • Boundedly-stale reads (useful at lagging replicas) （意味不明。。）

• 何を保証してほしいか？
  • それをどうやってそこそこのコストで実現するか？

• コミット順序の保存：スキーマの例

• SnapshotベースのMapReduceとクエリ

• 正しいトランザクション順序

• linearizability (マルチプロセッサ文脈での意味で)とは
  • 一定の順序性を保証
  • コミット順序は入れ替わらない。トランザクション間のhappens-before関係を保存。
    • 検知不可能な依存性がある場合でもOK
    • 複数マシン間でもOK

• スケーリングの選択肢
  • WAN通信を増やす
    • すべてのトランザクションにすべてのパーティションを参加させる
    • タイムスタンプを集中管理
  • 通信を増やさない
    • 外部のシステムやプロトコルとのすべてのやりとりでタイムスタンプを伝播させる(Lamportクロック)
    • タイムスタンプを分散管理
      • TrueTime: now = {time, epsilon} をGPSから取得、原子時計でバックアップ（そうくるか）

• どうやって実現するか？

• 天文航法（星の導きに従え！って感じ？）

• TrueTime
  • Time Daemon（時間の問い合わせクライアント？）
  • 原子発振器ベースのTime Master（マスタークロックサーバーみたいなもん？）
  • GPSベースのTime Master

• TrueTime
  • Time Daemon（がGetTimeをリクエスト）
  • Time Master（が時間tを返す）
    • t + e（レスポンスまでのレイテンシ）が現在の時間

• TrueTime:マーズロのアルゴリズム（NTPも利用）

• TrueTimeによるタイムスタンプ書き込み
  • TX AとBがあるとき、AとBが別パーティションにある場合でも、A happens-before Bならばtimestamp(A) < timestamp(B)
  • 実時間でAの結果がBの開始より先に見えた場合、A happens-before B
    • 見えるとは、クライアントにackが返ったか、レプリカのいずれかに更新が適用されたことを指す。
    • 開始とは、Spannerサーバーに最初のリクエストが届いたことを指す。
  • あとで任意のタイムスタンプに対してsnapshot readを行う際にserializabilityを保証

• なぜこれで動くか

• 時間がかかるケース

• TrueTime epsilon（レイテンシ）
  • 実際のシステムでは1 - 7 ms間隔のノコギリ曲線を描く
  • 曲線の傾斜：発振器の誤差による
  • 最小値：Time Masterまでのレンテンシ

• TrueTime epsilonを減らすには
  • Time Masterへのポーリングを増やす（現在は30秒ごと）
  • ポーリングリクエストのQoS（優先度）を高くする
    • カーネル内での優先処理も必要
  • NICドライバでタイムスタンプを記録する
  • もっといい発振器を買う
  • そしてカーネルのバグに注意！

• 読む時はどうするか？

• readの種類
  • read-modify-writeにおけるread
    • Paxos leader(s)のロックマネージャーでロックを取得
  • "Strong"なread
    • Spannerでタイムスタンプを取得して（スナップショットを）読む
  • Boundedly-stale（なにそれ。。）reads
    • staleness bounds内でコミット済みタイムスタンプの最大値をSpannerで取得する
  • MapReduceやバッチ処理のread
    • クライアント側でタイムスタンプを取得

• strong readのためのタイムスタンプ
  • TrueTimeを使う
  • コミット履歴を使う
    • 最近の書き込みにおけるコミット済みタイムスタンプを保持
    • 先にスコープを明示する必要がある
      • 単独クエリではそれほど重要ではない
      • "ユーザーalloydからのオーダー"など
    • preparedな（？）分散トランザクションがあると複雑な状況になる

• 効果的な使い方
  • やっぱりデータのローカリティを考えてスキーマを設計する必要がある
    • 例：customerとordersは同じパーティションに入れて、大きなユーザーの場合はパーティションを分ける
  • 「正しさ」を目指したアプリ設計（？）
  • きちんと検証された高トラフィッククエリについてはセマンティクスの制約を緩和させる

• 最初のビッグユーザー：F1
  • 売上に大きく係るsharded MySQLインスタンスをSpannerに移行
  • Spannerのデータモデルに多大に影響を与えた
  • SIGMOD 2012 talk onlineのスライドあります

• （Spanner設計段階における）データモデルの進化
  • 1. 分散ファイルシステムのメタファを検討：ディレクトリが地理的配置の単位となる
  • 2. ディレクトリとファイル名に構造化キーが追加された
  • 3. （当初は）階層化された“Protocol Bufferのストレージ”としてSpannerが設計された
    • 同時にSQLエンジンの開発も始めた
  • 4. Spanner上にF1のリレーショナルスキーマが構築されたのを受けて、（Spanner自体も）リレーショナルモデルに移行

• 現在実施中の作業の例
  • SQLエンジンの改善
    • 異なるサーバーバージョンをまたぐ、再実行可能なSQLクエリ(!) （。。なんだろう？）
  • よりしっかり作る
    • メモリ利用のきめ細かな制御
    • CPUスケジューリングのきめ細かな制御
  • SIベースのstrong read
    • Paxosグループ（パーティション）ごとに多数のレプリカを収容可能にする