C-Store

http://db.csail.mit.edu/projects/cstore/vldb.pdf:M. Stonebraker, "C-Store: A Column-oriented DBMS, " VLDB(2005).を読んでみてのメモ。

  • これまでは、DBMSでOLAP(キューブタイプ)をになっていたが、比較的複雑なアドホッククエリへのレスポンスタイムを小さくするため、アーキテクチャの再設計を行う。
  • テーブルを複数のカラム集合に分けて、ストレージに格納。各カラム集合は、sort keyによってソートされる。これにより、さまざまなOrderBy/GroupByに対応しやすくしているのかなと思う。面白いところは、各カラム集合には、同じカラムを重複して含んでも良いところ。複数サーバで管理されりているC-Storeは、K-safeを実現することができるが、そのためのレプリカにもなっている。
  • カラム分割だけでなく、水平にも分割して、分割単位をsegmentと呼ぶ。カラム集合に対応するsegmentを用いて、元のテーブルを構成できるようにするために、別のカラム集合に含まれるsegment間には、join indexを作成する。join indexは、SegmentIDとStorageKeyからなる。分割された各レコードは、join indexによって1対1で結び付けられる。
  • Read-Optimized Store (RS)とWrite-Optimized Store (WS)から構成される。WSである程度書き込みがたまると、RS上のsegmentとマージされて、join indexも作成される。クエリを発行したばあい、RSとWSのどちらからも検索を行う。RS上では、データタイプによって4つの圧縮方式があり、これらの圧縮方式では、圧縮したまま演算処理を行うことが出来るように工夫されている。最終的に解凍するのは、ユーザにデータを渡すときのみ。重要な方式としてランレングスとビットマップがあり、ランレングスはソート済み、ビットマップはソートはしていないが出てくる値がある程度グルーピング出来る場合に有効。
  • WSの基本的な構造は、RSと変わらない。オプティマイザを二つ作りたくないから。WSに格納されるデータ量は小さいので圧縮は考えず、B-treeとして構築し、論理的なオーダーを担保する。
  • 複数サーバ上でsegmentは配置される。その配置戦略は、
    • join indexは、join時のsender側にあったほうが良い。というかそういうjoin indexの作り方をしていると思う。
    • WS/RS上の同じキーレンジを持つsegmentは、同じところに配置したほうがよい。
  • 更新データは、カラムごとに各WSに書き込まれるけど、同じレコードであることはStorage Keyが同じことで保証する。Storage Keyは、必ず一意になるように更新要求を受け付けたサーバで決定。
  • 既存のRDBMSでの並行制御をまともにやると、沢山のアドホッククエリに耐えられないのでsnapshot isolationを採用。
    • WOS->ROSへ移行するところにおいて、snapshot isolationが効いてくる。Hiveやdremelではこれが出来ていない。
  • WOSやROSに対するクエリオプティマイザは、Selinger-styleで実装。これは、いわゆるコストベースのクエリオプティマイザで、RDBMSでは基本。
  • リレーショナルオペレータは、10種類程度規定しており、ソースコードを読むところvolcano(有名なデータベースマシン)で培われたパイプライン処理を用いている。
  • 他のカラムストアに比べて面白いのは、Bigtableで言うところのカラムファミリグループみたいな概念をDurabilityやOrderByへの対応などに対してうまく使っていること。シンプルなカラムストアでは、カラムファミリグループとカラムファミリは一対一にする。が、C-storeでは、分散ファイルシステムを利用していないのでそのへんの柵がなく、ひとつのカラムファミリを複数のカラムファミリグループに重複して登録することで、物理マシンのクラッシュ時にデータの喪失を防ぐとともに、複数のガラムファミリグループでソートしているカラムファミリを切り替えている。そうすると、一番重たいソートクエリ対する部分的な実体化ビューを準備済みになる。