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なソリューションかも!
Linealizabilityについて(6/12追記)
Linearlizabilityってなんぞ。。と考えてみました。
Building Spanner - Better clocks → stronger semanticsの試訳
注)公開情報のみを元にした個人的な試訳なので、内容はけっこう間違ってると思いますし、私の雇用者とは関係ありません。
注)全角カッコ内()は訳者補足です。
- Spannerを作る
- クロックをよくすればセマンティクスも強くなる
- Alex Lloyd, Senior Staff Software Engineer
- 地球規模でserializableなDBの作り方
- bounded absolute error(なにそれ)なクロックを作ってタイムスタンプを発行
- 半順序なTX(での利用)を前提とした全順序なタイムスタンプ
- 全体でserializableなクエリを実現
- Spanner
- なぜSpannerか?
- Spannerのデータモデル概要
- Spannerの物理的表現
- Spannerの並行性
- デフォルト設定:serializability(
=SERIALIZABLE?違う意味と @masayh さんからご指摘いただきました。) - オプション機能:過去に遡ったserialize read(過去のスナップショットで読めるってこと?)
- すべてのデータを対象に一貫性確保したMap Reduce(が可能に)
- Boundedly-stale reads (useful at lagging replicas) (意味不明。。)
- デフォルト設定:serializability(
- 何を保証してほしいか?
- それをどうやってそこそこのコストで実現するか?
- コミット順序の保存:スキーマの例
- SnapshotベースのMapReduceとクエリ
- 正しいトランザクション順序
- linearizability (マルチプロセッサ文脈での意味で)とは
- 一定の順序性を保証
- コミット順序は入れ替わらない。トランザクション間のhappens-before関係を保存。
- 検知不可能な依存性がある場合でもOK
- 複数マシン間でもOK
- スケーリングの選択肢
- どうやって実現するか?
- 天文航法(星の導きに従え!って感じ?)
- TrueTime:マーズロのアルゴリズム(NTPも利用)
- TrueTimeによるタイムスタンプ書き込み
- なぜこれで動くか
- 時間がかかるケース
- TrueTime epsilon(レイテンシ)
- 実際のシステムでは1 - 7 ms間隔のノコギリ曲線を描く
- 曲線の傾斜:発振器の誤差による
- 最小値:Time Masterまでのレンテンシ
- TrueTime epsilonを減らすには
- 読む時はどうするか?
- readの種類
- strong readのためのタイムスタンプ
- TrueTimeを使う
- コミット履歴を使う
- 最近の書き込みにおけるコミット済みタイムスタンプを保持
- 先にスコープを明示する必要がある
- 単独クエリではそれほど重要ではない
- "ユーザーalloydからのオーダー"など
- preparedな(?)分散トランザクションがあると複雑な状況になる
- 効果的な使い方
- 最初のビッグユーザー:F1
- (Spanner設計段階における)データモデルの進化
- 1. 分散ファイルシステムのメタファを検討:ディレクトリが地理的配置の単位となる
- 2. ディレクトリとファイル名に構造化キーが追加された
- 3. (当初は)階層化された“Protocol Bufferのストレージ”としてSpannerが設計された
- 同時にSQLエンジンの開発も始めた
- 4. Spanner上にF1のリレーショナルスキーマが構築されたのを受けて、(Spanner自体も)リレーショナルモデルに移行