マルレク Googleの分散技術 第1回

ちょっと前にJJUGクロスカンファレンスでGoogleの分散技術の講演を聴いてきたんだけど、今日から隔週で3回に分けてより詳しく突っ込んでお勉強です。各回の内容はこんな感じ

  1. GoogleFile SystemとBigTable
  2. MapReduceとSawzall
  3. Apache HadoopAmazon EC2/S3

会場は秋葉ダイビル稚内サテライト校舎。60ぐらい来ていたのかかなり混んでた。*1前の席が無くて後ろに座ったらパワポの下半分が見えないという悲惨な感じでした↓

GFS(GoogleFileSystem)
  • Googleの基礎を支える仕組み
  • 2003年ごろに導入された
  • 2000台以上のPCで構成される
    • 1000台のPCがあるり1台が3年に一度故障するとすると1000台のうち常に1台は故障している。
      • 100万台あると1000台は故障している。
    • そこでGFSではハードの故障は例外などではなく当たり前の動作として捕らえられている。
    • 信頼の高いハードは技術者をなまけものにする*2
  • クローラーがHPを集めてきてIndexとして書き込んだら後は読むだけ
  • ペタバイトのデータを扱うことを前提に作られている
    • ブロックサイズは64M
    • Liniuxのファイルとして格納されている
    • 読み書きの性能が抜群に良く2000MB/Sを叩く
      • 2000台あるから1台あたりだと1mぐらい
    • この1000の掛け算がとてもつよい。
      • 2Gメモリ500GのPCを2000台集めると
      • 4テラメモリ&1ペタHDDになる
      • 1台だったら同時に読み書きできないけど複数台あれば見た目パラレルが可能
    • 書き込みはアトミックに行われる
      • 排他しなくても勝手にキューができる
  • ランダムアクセスは行わず常にシーケンシャルアクセス
    • 修正ではなく追記
    • 削除は苦手
  • 「Co-design」
    • アプリケーションの目的に合わせシステムを構成する。
  • まさにGoogleのビジネスに最適化して作られた仕組み
    • コストで30倍近い競争力をつけることができる
      • Googleがこんだけ強い理由の一つ
    • 仕組みの横展開
  • 命令はSnapShot、Read、Append
    • SnapShotはノード間のコピー専用
  • クライアントからのアクセスの仕組み
    1. クライアントはマスターに場所を問い合わせ
    2. マスタはメモリ上にキャッシュしているメタデータからチャンクの場所を返却
    3. チャンクは最低3台でレプリカされている
    4. クライアントはチャンクの中で一番近いレプリカにアクセス*4
    5. 以後クライアントはメタ情報をキャッシュしマスタへのアクセスは抑えられる
  • マスタを一つにすることでデザインがとてもシンプルになる。
    • ここでもブロックサイズが64Mという巨大であることが生きてくる
      • 読み書き減るしTCPIPのオーバーヘッドも無くなる。
      • 更にマスタ上のメタ情報を減らすことができる。*5
    • しかし問題もありアクセス集中するとボトルネックになる。
      • アクセス多発部分(実行可能ファイル格納場所など)はレプリカを増やすことで対応している
  • メタデータの構成
    • チャンクの名前空間、Fileとの対比マップ、レプリカの場所
    • マスタサーバーが起動し以後定期的にチャンクとHBしたりしながら更新されていく
      • その中で使用されなくなったチャンクをGCしたりする
    • 64Mデータのためのメタデータは64バイトになる。
    • それをがぼ〜〜っと4Gぐらいのメモリに突っ込んでいる。
    • 変更履歴はトランザクションログに出力されリカバリに使用される
      • オンメモリDBみたいな感じ
      • 一昔前の「テープ⇒DISK」と同じように「DISK⇒メモリ」になっている
      • Googleはメモリの使い方が非常にうまい。Bigメモリアプリケーションもとっても大事な技術
    • しかしレプリカの場所はトランザクションログには含まれない。
      • ハードは当たり前に壊れるという思想からレプリカは常に変わり続けている為
      • 動いているものが偉い
        • チャンク>>(越えられない壁)>>マスタ
    • トランザクションログの出力時は完全にアトミックに処理が行われる
      • この辺りはとても慎重
    • クライアントは書き込みをする際必ず3つのレプリカに書き込みを行う
      • 原理的には3台のメモリにまず書き込み、プライマリのディスクに書き込みをし完了後セカンダリディスクに書き込み
    • 3台のうち失敗したものがあってもクライアントは正常と判断する。
    • defineではないがconsistentである為*6
BigTable
  • GFSの上に成り立つデータベース
    • ペタバイトのデータを扱うために作られた
      • Googleは現在50万〜100万台のPCサーバーで動いている
      • コンシューマーの出荷台数よりGoogle、アマゾンなどのマシンの方が出荷が多くなってきている
    • URLなどの半構造化データを格納している
      • リレーショナルじゃなくてよい
    • 現在の容量(想定)
      • Google検索       800テラ
      • Google検索インデックス  50テラ
      • Googleアナリティクス  200テラ
      • Googleアース       70テラ
    • 現在のアクセス(想定)
      • 毎秒数1000万リクエスト
  • 目指すもの
    • 非同期書き込みの高速化
  • 分散多次元マップ
    • ROW、COLUMN、TIMESTAMPE
    • ROWアクセスはアトミック
      • ROWにはURLが逆になって入っている。(javaの命名規約のような感じ)
      • これによりアクセスがしやすくなる。*7
    • カラム名は「ファミリー」と「クオリファイア」の2つで構成される
      • これもファミリーで引っ掛けたり出来るようにするため
    • 出来たのは結構最近で2006年
      • 現在BigTableのセルが100程度あるらしい
      • これも基本C++
    • TABLEはTABLETという要素で構成される
      • TABLETは何時でも分割可能でテーブルのキーの順番さえ守られていればすぐに分割可能
      • もちろんサーバーを跨いで分割、分散可能
    • 1台のマシンが100個程度のTABLETを管理している
      • 1台壊れても周りの100台が1つずつ拾ってあげれば大丈夫という思想らしい
    • TABLETは分割され分散されるのでアクセスするには情報がどこに格納されているのか知る必要がある
    • BigTableはGFSとは違い必ずマスタに問い合わせにいく。
      • BigTableでは1kb単位の情報から格納されるためメタ情報が巨大になり一つのメモリに入りきらないため
      • メタ情報は1kbデータで2チャンク(128M)のデータを格納できる。そうすると2^34必要になる
    • マスタ内でメタ情報はIndexリーフのように3段階になって格納される。
  • 書き込み時
    • メモリ上に書き込んでいきある程度溜まった時点でSSTableに書き出し圧縮される(Logにコミットされる)
  • 読み出し時
    • メモリ上に無い場合はSSTableの圧縮を回答してファイルを探しながらSSTableをマージする
      • マージだがKey順に並んでいるためマージは高速に行える
    • SSTableが増えてくるとSSTableどうしを結合させ1つにする
      • これによりSSTableの数を一定に保つ
感想

めっちゃ濃い2時間でした。資料が出たら復習しないと全くわからん

関連リンク+

サブセミナーのHP(今夜HPが更新されるらしい)
http://www.wakhok.ac.jp/tyo-sat/subsemi2007.html
クロスカンファレンス Google分散技術
http://d.hatena.ne.jp/pentasa/20071106/1194366316
Googleの資料
http://research.google.com/pubs/papers.html

*1:そういえばid:dewaさんらしい人を見かけた。会社の先輩と思われる人もいた。

*2:前回これハードとソフト間違えました。。すみません

*3:まじしらんかった〜

*4:GoogleはIPでサーバーの物理的位置が分かるようになっているらしい。同じラックにいるかとか分かるらしい

*5:全部メモリに乗せるため少ないほうが有利

*6:3台ともに完全に正常終了していないが、書き込み完了したものは一貫的である。失敗したチャンクには後でコピーしとけばいいという考えらしい

*7:jp.co.garaとなるので日本の〜とかで引っ掛けやすい