Hatena::ブログ(Diary)

スティルハウスの書庫 このページをアンテナに追加 RSSフィード

2012-06-07

Spannerお勉強メモ

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

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

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

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

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

佐藤先生の感想:

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

Togetterまとめ(6/8追記)

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

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
    • 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グループ(パーティション)ごとに多数のレプリカを収容可能にする

2012-04-12

Google Cloud PlatformチームでSolutions Architectのお仕事をします #gaeja

昨年1月にGoogleに入社して以来ほとんどApp Engineとは関係のない仕事をしてきましたが、4/23よりCloud PlatformチームのSolutions Architectという職につくことになりました。GoogleのCloud products(App Engineをはじめ、Google Cloud SQL、Google Cloud Storage、BigQuery、Prediction APIなど)を導入するパートナー企業に対して技術コンサルティングを提供したり、実開発におけるノウハウやデザインパターンの蓄積と共有などを担当するお仕事です。松尾さんのお仕事(Developer Advocate)と重なりますが、もうちょっと実案件に深く関わる立場で、扱う案件も日本に限らずUSやAPACの案件が中心となります。

かねてからの目標であった「GoogleでApp Engineのお仕事をする」ことが実現し、いまはとても嬉しいです。また、appengine ja nightの運営を始めとするコミュニティ活動も、今後は晴れて本業の一部として取り組めます。最近はajnの運営のかなりの部分をshin1ogawaさんに頼ってしまってましたが、またがしがし積極的に関わっていきたいと思います。社内で蓄積した知見や、BigQueryやPrediction APIのようにすごく面白いけど国内でほとんど知られていない技術をブログ等を通じてコミュニティで共有できればいいな〜と思っています。今後ともどうぞよろしくお願いします!

明日はappengine ja night 20です。ちょっと着くのが9時ごろになってしまいますが会場でお会いしましょう〜。

2011-06-26

ニュータウンLOVE!

液状化で一躍有名となった新浦安に住み始めて12年ほどになりますが、引っ越してくる前から数年くらい前まではよく都市公団(UR都市機構)の各所のニュータウンを歩いて回ってました。ニュータウンマニアです!

新浦安のマリナイーストはもちろん、千葉ニュータウンの印西牧の原、中央、白井、シーリアお台場、そして多摩ニュータウンの稲城、若葉台、永山、聖ケ丘、センター、唐木田、堀之内、南大沢などなどを踏破しました。そのなかでも私が「ここは住んでみたい!」と思った場所をピックアップします。共通するのは、街並みがきれい、電柱がない、戸建てでもせせこましくない、スーパー等の駅前施設は十分だがパチンコ屋はない、比較的新しい、駅や都心からは割と遠くても構わない(フリーランスだったので)、そしていずれも都市公団が開発している、といった点です。

  • 幕張ベイタウン

http://bit.ly/jgs9uZ

http://baytown.dokkoisho.com/chiba/baytown/residence.html

パティオのあるヨーロッパ風の低層住宅で統一されつつ、各ブロックは別々の建築家が担当しててよく見ると多彩。ご近所と共有された中庭のある生活は楽しそう。通り沿いに並ぶお店もネパール料理とかビレッジヴァンガードなど個性的で、駅との間にある広大な公園もよい。ただし駅前は液状化被害が大きかった。

  • 多摩ニュータウン若葉台

http://goo.gl/tSH6z

http://townphoto.net/tokyo/wakabadai.html

最近できた新しい街。電柱がなく空が広い一戸建て街区は希少。公団らしく一戸建て、低層、中層・高層ときちんと整理されてる景観がよい。まだ空き地や緑が多い。

  • 多摩ニュータウン堀之内/別所

http://bit.ly/kIjuTF

昔ながらの雑木林が所々に残されつつゆったりした一戸建て街区やマンションが組み合わされててグッド。せせらぎ緑道沿いの低層マンションは一見の価値あり。ただし坂が多い。

  • 多摩ニュータウン唐木田

http://www.natsuzora.com/may/town/karakida.html

http://goo.gl/AIfHr

成熟した一戸建ての街。メインストリートは電線埋設。ここもからきだの道など古い雑木林が残されているのがよい。新規分譲はなく中古でも6-7000万くらいするしあまり流通してない。まめちしき:唐木田は谷を数10mほど埋立して作られた造成地で神社も引き上げられた。

  • 千葉ニュータウン印西牧の原

http://www.pananavi.jp/home/dearland.php

一戸建てでも4〜5000万円台とリーズナブル。しかし遠いし電車賃高い。

番外編

以下は、景観等は文句なしであるものの、高すぎるなどいろいろな理由で検討しにくい場所です。

  • ワンハンドレッドヒルズ(a.k.a. チバリーヒルズ。東急)

http://goo.gl/Z0rY1

500〜1000坪くらいで、USの高級住宅街そのままって感じ。ひとけがない。遠い。

  • 新浦安の碧浜

http://bit.ly/m2FUih

http://goo.gl/0h7m9

ハウスメーカーのCMのようなきれいな街並み。新浦安マリナイーストでは唯一の一戸建てで駅近。(ちなみに私の家はここではありません)

  • 季美の森(東急)

http://baytown.dokkoisho.com/chiba2/kiminomori.htm

ゴルフ場を囲むように一戸建てが並ぶユニークな分譲地。とくにゴルフ場沿いの物件はいずれも100坪くらいあり目の前は広々としたゴルフコースを望む抜群の眺望。思ったほど高くはないが、大網駅からさらに森の向こうにある千と千尋のようなロケーションで通勤は困難。

2011-05-02

#appengine タグから #gaeja タグに移りましょう!

久々の更新です!

最近、Twitterの#appengineタグがスパムっぽいアカウントのつぶやきであふれて、あまり使い物になってませんでした。そんななか、

@higayasuo さん:

今後 #appengine 関連の日本語のつぶやきは #gaeja を使うことにしましょうか #appengineja はちょっと長い。軽く調べた限りはノイズも少なげ

というつぶやきに皆さん賛成して、App Engineなつぶやきは #gaeja で行われるようになりました。ぜひぜひこちらを使いましょう。

2010-07-12

Google Megastoreのお勉強メモ #appengine

BrettさんのSTMに関する記事の中でGoogle Megastoreについて言及されていて、そのリンク先がハミルトン先生の2008年7月の記事(内で紹介されていたPhil Bernsteinさんのメモ)でした。つまりどうやらMegastoreに関する公開情報でGooglerのお墨付きなものはこれしかなさそうです。そこで改めて要点を写経しつつ、App Engineレベルから見た疑問点等をまとめてみました。なお、青色部分は私の訳注および感想です。同じ記事について解説したkuenishiさんの記事もありますので、合わせてご参照ください。

ところでここでは「BigTable」表記です。BigtableのTが大文字か小文字かについてguidoは「う〜ん論文ではtだったから小文字じゃないかな〜」と言ってました。つまりGoogle社内でも統一されてません。

Google Megastore

What follows is a guest posting from Phil Bernstein on the Google Megastore presentation by Jonas Karlsson, Philip Zeyliger at SIGMOD 2008:
Megastore is a transactional indexed record manager built by Google on top of BigTable. It is rumored to be the store behind Google AppEngine but this was not confirmed (or denied) at the talk. 
  • 以下の内容は、SIGMOD 2008におけるJonas KarlssonとPhilip ZeyligerによるGoogle Megastoreのプレゼンテーションに関するPhil Bernsteinによるゲストポストである
  • Megastoreは、GoogleがBigTable上に構築した、トランザクショナルかつインデックスベースのレコードマネージャ
  • Google App Engineのデータストアの中身はこのMegastoreであると言われている(これは確認済み。DatastoreはMegastore上に実装されています
·A transaction is allowed to read and write data in an entity group.
·The term “entity group” refers to a set of records, possibly in different BigTable instances. Therefore, different entities in an entity group might not be collocated on the same machine. The entities in an entity group share a common prefix of their primary key.  So in effect, an entity group is a hierarchically-linked set of entities.
·A per-entity-group transaction log is used. One of the rows that stores the entity group is the entity group’s root. The log is stored with the root, which is replicated like all rows in Big Table.
  • エンティティグループの中では、データの読み書き時にトランザクションを利用できる
  • 「エンティティグループ」という用語は、複数のレコードの集まりを指す。各レコードは異なるBigTableインスタンス(タブレットサーバーのこと?)にあってもよい。よって1つのエンティティグループ内の各エンティティは、それぞれ異なるマシン上に配置される場合もある。あるエンティティグループ内の個々のエンティティは、プライマリキーに共通の接頭辞を持つ。そのためエンティティグループは「階層的にリンクされたエンティティの集まり」となる
    • 「エンティティ」「エンティティグループ」という概念は、Datastore由来ではなくMegastore由来なんですね
    • 「エンティティグループ」の「エンティティ」は複数のマシンに分散していてもよい。ということは、エンティティグループのトランザクションは分散トランザクション(=グローバルトランザクション)。。ですよね?
  • エンティティグループ単位のトランザクションログを使用する。各行のうち、エンティティグループのルート(ルートエンティティ)にエンティティグループ(のログ?)が保存される。ログはルートに保存され、Big Tableのすべての行と同じくレプリケーションされる。
·To commit a transaction, its updates are stored in the log and replicated to the other copies of the log. Then they’re copied into the database copy of the entity group.
·They commit to replicas before acking the caller and use Paxos to deal with replica failures. So it’s an ACID transaction.
·Optimistic concurrency control is used. Few details were provided, but I assume it’s the same as what they describe for Google Apps.
  • トランザクションのコミット時には、更新内容がログに記録され、そのログがレプリケーションされる。つづいてエンティティグループのデータベースコピー(データ本体を表す行?)に更新内容が書き込まれる。
    • Datastoreのドキュメントで説明されているcommitやapplyといったフェーズは、Megastore内部のフェーズなのかな?
  • レプリカ(コピー)へのコミット時には、コピー先からコピー元へのackを待たない。レプリカの障害時にはPaxosで対処する。よってこの処理はACIDトランザクションとなる。
    • Paxosを使うことで(2PCのように)いちいちコピー先の返事を待たずにレプリケーションしつつ障害時の整合性も確保(ACID)される。。かな? すべての書き込み時にPaxosを使うのか障害時にのみ使うのかよくわからない
  • 楽観的排他制御を用いる。詳細は不明だが、Google Apps(App Engineの間違い)での説明内容と同じはず
·Schemas are supported.
·They offer vertical partitioning to cluster columns that are frequently accessed together.
·They don’t support joins except across hierarchical paths within entity groups. I.e., if you want to do arbitrary joins, then you write an application program and there’s no consistency guarantee between the data in different entity groups.
·Big Table does not support indexes. It simply sorts the rows by primary key. Megastore supports indexes on top. They were vague about the details. It sounds like the index is a binary table with a column that contains the compound key as a slash-separated string and a column containing the primary key of the entity group.
  • スキーマをサポートする(
  • 頻繁にアクセスされるカラムをたばねた垂直パーティショニング をサポートする(これはDatastoreのAPIでは提供されてない
  • joinはサポートしない。ただしエンティティグループの階層構造内でのjoinはサポートする(Ancestor Queryのこと?)。アプリケーション側で任意のjoinを実装することも可能だが、エンティティグループが異なるデータ間では整合性が保証されない
  • Big Tableはインデックスをサポートしない。プライマリーキーで行をソートするだけである。Megastoreでは、Big Table上でインデックス機能を提供する。詳細は不明。「/」で区切られた文字列からなる複合キーと、エンティティグループのプライマリーキーを含むカラムを備えたバイナリーテーブルがインデックスの実体のようだ
    • このあたりはApp Engineのインデックステーブルのことを指すと思われる。しかし、もしインデックステーブルがMegastoreレベルで実装されているなら、App Engineクエリ機能の改良等はMegastore内部で実施されているということ。。?
·Referential integrity between the components of an entity group is not supported.
·Many-to-many relationships are not supported, though they said they can store the inverse of a functional relationship.  It sounded like a materialized view that is incrementally updated asynchronously.
·It has been in use by apps for about a year.
  • エンティティグループ内のエンティティ間の参照整合性は保証しない
  • N:N関係はサポートしないが、they can store the inverse of a functional relationshipとのこと(わかりません)。非同期かつインクリメンタルに更新されるマテリアライズドビューみたいだ
  • 複数のアプリケーションでおよそ1年間使用されてきた

また混乱してきましたw

...エンティティグループも複数マシン上でのACIDを保証するので、つまりは分散トランザクション/グローバルトランザクション。。なんですよね?

しかしどうやって? 2PCは使っていないです。ではPaxos? DC間レプリにはPaxosを使っているとgooglerも言ってましたが、エンティティグループ内のコミット時に毎回Paxos使っているとは思えない。。ああよくわかりません。 Slim3やその他のいわゆる「アプリレベルの分散トランザクション」と、エンティティグループの分散トランザクション、それぞれのpros/consや実装の違いをだれかうまくまとめてくだされ。。

追記

ひがさんのつぶやき

.@kazunori_279 エンティティグループのACIDはルートエンティティのログ(のみ)で実現されているので、単一マシンに閉じていて、分散トランザクションではないと思います #appengine

ふむ〜。データの保管場所が物理的に分散していても、それらを保護するタイムスタンプやロック自体が単一マシン上にあれば、ローカルトランザクションと見なせる。。という理解でいいかな?