ikemonn's blog

技術ネタをちょこちょこと

Bigtable: A Distributed Storage System for Structured Data を読んだ

Bigtable: A Distributed Storage System for Structured Data を読んだ時のメモ。

どんなもの?

  • ペタバイト級のデータ、何千台ものサーバまでスケールする大規模分散ストレージ
  • Google Analyics, Google Earth, Web indexing等に使われている

先行研究とくらべて何がすごい?

  • 低コストで高いパフォーマンスと可用性、スケーラビリティを達成した
  • Googleの既存のsystemを組み合わせて作られている

技術や手法の肝は?

f:id:ikemonn:20170625181051p:plain

  • Data Model

    • sparse, distributed, persistent multidimentsional sorted map
    • (row:string, column:string, time:int64) → string
      • row,column,timestampでindexingされている
    • row keyは任意の文字列
      • transaction consistencyの単位がrow
      • 辞書順にrow keyでソートされている
      • 最大64KBで一般的には10~100byte
    • column family
      • column keyをグループ化したもの
      • diskやmemoryへの割り当ての単位
    • timestampでindex化された複数バージョンのデータをもつ
      • read時には最新のデータから読まれる
      • client側で何世代保持しておくかを設定できる
    • filesystemはGFS
    • Chubbyでmaster serverやtabletサーバの管理、スキーマ情報の格納等を行う
  • 構成

    • master server
      • tablet serverとやり取りする
        • Chubbyに登録されたtablet serverのデータをもとにTabletの割当をおこなう
    • tablet server
      • tabletのread/writeのハンドル、tabletの分割
      • clientとのやりとりはmaster serverを介さずにtablet serverが行う
    • tablet
      • tableを分割した単位(1つあたり100~200MB)
        • 一定範囲のrow keyのデータを含む
      • memtableとSSTableから成る
        • memtable
          • tablet serverのメモリ上にある
          • 直近でcommitされたデータをもつ
        • SSTable
          • GFSに保存されている
          • BigTableのデータを保存している
          • memtableが消えてもSSTableから再構築できる

どうやって有効と検証した?

f:id:ikemonn:20170625181133p:plain

  • performance
    • tablet serverの台数を変えてread/writeのパフォーマンスを測定した
      • 1000bytesのread毎に64KBのブロックを転送した
    • random read
      • 一番遅い
      • read毎に、64KB SSTable blockを転送すると1200 read/secで75MB/sのデータをGFSから読み込むことになりネットワーク帯域がサチった
    • random write
      • random readよりもパフォーマンスが良い
        • 1つのcommit logに書き込みを行って、GFSに対してgroup commitを行っているから
    • sequential read
      • random readよりもパフォーマンスが良い
      • GFSからfetchしてくる64KB SSTable blockがblock cacheに含まれていて、64個のread requestとして使われるから

議論はある?

  • tablet serverが少ない時に負荷が偏ってしまい、パフォーマンスがあまり出ない
  • rebalance中はtabletの移動数が減少してしまう
  • secondary indexのサポート
  • multiple master replicaのcross-data-centerでのレプリケーション

次に読むべき論文は?

広告を非表示にする