スティルハウスの書庫の書庫

はてなダイアリーで書いてた「スティルハウスの書庫」を移転してきました。

Bigtableの内部構造

Bigtableの概要

  • Bigtableとは
    • 構造化データを管理するための分散化ストレージ
    • 膨大な数の汎用サーバーをつなげてペタバイト規模のデータを扱えるよう設計されている
  • Bigtableの歴史
    • およそ7人年の開発作業を経て、2005年4月からプロダクション利用を開始
    • 2006年時点では、Googleの60以上のプロジェクトがBigtableを利用
      • 検索, Analytics, Finance, Orkut, Earth, YouTube, Mapなど

Bigtableが動くサーバーの構成


Googleの典型的なクラスターノード構成:引用元

  • 個々のノードの基本構成
    • Intelベースの安いPC
    • Linux OS
    • Schedulerスレーブ
      • Schedulerマスターの指示に従ってノード上に各種サービスをデプロイする
    • GFSチャンクサーバー
      • GFSのチャンク(データ)を保存する
    • タブレットサーバー
  • Bigtableクラスター全体を管理するサービス群
    • Schedulerマスター
      • 各ノードに各種サービスをデプロイする
    • Chubby
      • 分散ロックサービス
    • GFSマスター
      • GFSチャンクサーバー群を統括する
    • Bigtableマスター
      • tablet server群を統括する

Bigtableの構成要素

  • Bigtableのテーブル
    • Bigtableのテーブルは、「分散化された多次元ソートマップ」
      • 簡単に言うと、ソート済みのExcel表のようなもの
      • 個々のセルは履歴を残せる(multidimensional)
    • テーブルの実体は、巨大なkey-value store
      • キー(行キー+カラムキー+タイムスタンプ) → 値(string)
      • 行キーは最大64KBまで(大半は10〜100バイト)
    • 行単位のCRUD操作は、カラムの数にかかわらず、アトミックに実行される
      • 複数行にまたがる操作は原子性が保証されない
    • 古い履歴データや削除された行は、自動的にGCされる
    • テーブルは行キーの辞書順でソートされている


Bigtableの構造:引用元

タブレットサーバーのメカニズム

  • タブレットサーバーの検索
    • あるキーのデータを取得するとき、クライアントはタブレットサーバーのIPアドレスを取得する必要がある。このとき、DNSライクな階層問い合わせが用いられる
    • クライアントはまず、ブートストラップとなるChubbyサービスにアクセスし、METADATAタブレットを持つタブレットサーバーのIPアドレスを取得する
    • METADATAテーブルには、各キーに対応するタブレットサーバーのIPが記録されている
    • 以上の階層問い合わせには、最大で3回のネットワーク通信が必要となる。しかし通常はクライアント側にMETADATAタブレット内容がキャッシュされており、クライアントはタブレットサーバーに直接接続できる


タブレットサーバーの階層問い合わせ:引用元

キャッシュ管理とディスクアクセス

  • memtableによるキャッシュ管理とマイナーコンパクション
    • memtableは、タブレットにコミットされた更新内容を記録するソート済みのバッファ
    • 個々の更新処理はディスク上のコミットログに記録され、更新内容はmemtableに記録される
    • memtableがいっぱいになると、その内容がSSTableにフラッシュされる(マイナーコンパクション)
    • OracleのDBWR+チェックポイントと同様)
  • SSTableによるディスク保存とメジャーコンパクション
    • SSTableとは、memtableの内容保存に利用されるファイルフォーマット
    • ソート済みのイミュータブル(変更不可)なマップ(key-valueペア)
      • イミュータブルなのでファイルアクセス時のロックが不要、同時アクセスを効率的に扱える
      • コピーオンライトですばやくタブレットを分割できる
    • 削除されたデータがゴミとして残るので、マーク&スウィープGCを実行する(メジャーコンパクション)
  • GFSによるディスクへの書き込み
    • GFS(Google File System)とは、SSTable等のファイル保存に用いられるファイルシステム
    • ファイルは必ず3台以上のサーバーに書き込みされる
      • ローカルのGFSチャンクサーバーが空いていれば、そこに1つを書き込み
      • 残り2つは、離れた場所(少なくても同じラックではない場所)のGFSチャンクサーバーに書き込み
    • タブレットが移動しない限り、タブレットサーバーはローカルのGFSチャンクサーバーにアクセスする
    • 負荷分散のためタブレットが移動すると、データは残したままタブレットのみ移動する
    • バイナリアップグレード時などに、できるだけローカルに置くようにデータを再配置する


<GFSによるデータのレプリケーション引用元