ブログ  前の記事  次の記事  2008-04-21 

たけまる / Google App Engine のデータストアは Bigtable をどのように使っているのか


2008-04-21

_ Google App Engine のデータストアは Bigtable をどのように使っているのか [gae][bigtable]

Google App Engine (GAE) が発表されてから2週間ほど経ちます.GFS や
Bigtable という名前だけはよく耳にするようになりましたが,Bigtable
と GAE のギャップについては話題になっていないように思います.

Bigtable は multi dimensional sorted table と言われるように,
primary key (row key) でソートされたテーブルでしかありません.つま
り,GAE のデータストアが提供するような多様な検索機能は持たないわけ
です.というわけで,GAE のデータストアを実現するために,Bigtable
がどのように使われているのかを考えてみました.

# この件について,もし論文などが発表されていたら教えてくれると嬉しいです.

■ Bigtable

まず,僕が理解している Bigtable の姿について書いておきます.

Bigtable は行単位でデータを操作します.各行は row key を持ち,row
key によってソートされています.カラム (column family) 数は固定です
が,各カラムの中にサブカラムのようなものを自由に指定することができ
ます.また,過去のバージョンを保持することもできます.このように,
カラムの中に新たな "次元" を追加することができ,かつソートされたテー
ブルであるため,multi dimensional sorted table と呼ばれます.

一般に Bigtable のテーブルは巨大であるため,ひとつのテーブルが複数
のサーバによって管理されます.分割されたテーブルをタブレットと呼び,
管理するサーバをタブレットサーバといいます.タブレットは,さらに
SSTable に分割されます.SSTable は GFS 上のファイルです.

SSTable には row key を高速に検索するためのインデックスが追加されま
す.インデックスや最近の更新情報はメモリ上で処理されます.このため,
SSTable は row key に対する範囲検索やソートを高速に行うことができま
す.

タブレットサーバと row key の対応関係は,Chubby というサーバに問い
合わせることによって (間接的に) 知ることができます.このように,
Bigtable は row key による検索を効率的に行うことができます.

ただし,カラムに対してはインデックスが設定されません (少なくとも論
文によれば).つまり,カラムに対する検索を行うためには,すべてのデー
タをフルスキャンする必要があります.

■ GAE データストア

GAE のデータストアは,スキーマのない Object DB です.GAE では個々の
データ (object) を entity と呼び,カラムの値を property と呼びます.
property は後から自由に設定 (追加) することができます.

また,index.yaml というファイルを使えば,指定した property にインデッ
クスを設定できます.ただし,複数の property にインデックスを設定す
る場合でも,個々の property を指定するだけでかまいません.複数
property のインデックスを指定することはありません.

検索を実行するには,GQL という SQL のような言語を使うか,python
object にマッピングして操作します.

GAE では以下のような検索を行うことができます.

- entity 間の関係 (foreign key のようなもの)
- property による一致・範囲検索 (==, <, <=, >=, >)
   - property 値を持たない entity にはヒットしない
   - 範囲検索に使える property はひとつ
- property によるソート (order by)
   - 範囲検索とソートを同時に行うときは,property が同じであること
     (厳密には,最初のソート条件が一致すればよい)

Bigtable と異なり,カラム (property) による検索が可能になっていま
す.

■ GAE は Bigtable をどのように使っているのか

まず,通常のようにデータ (entity) を Bigtable に格納しておきます.
この時点では row key (entity key) によってデータはソートされていま
す.つまり,通常の Bigtable の使い方であっても,entity key での検索
や,entity 間の関係 (foreign key) による検索を高速に行うことができ
そうです.

次に,index.yaml によってインデックス作成が指示されたとします.する
と,そのカラム (property) を row key とし,entity key をカラム値と
するデータを作成し,Bigtable に追加します.元の row key (entity
key) と新たな row key (property) を区別するために,prefix を与える
必要があるかもしれません.たとえば,インデックスを作成する
property 名を "name" とします.すると,Bigtable には以下のようにデー
タを格納しておくわけです.

_row:000001 name:foo, ...
_row:000002 name:bar, ...
...
_row:000100 ...
name:bar 000002
name:foo 000001
...

こうすることにより,row key に対して検索を行うときは,"_row:<key>"
を検索すればよいですし,name property であれば "name:<value>" を検
索すればよいということになります.このようにして, property に対し
ても row key と同じく高速検索を行うことができます.

数値型を格納するときには,桁をそろえるために内部的に 0 padding を
行います (sprintf("%06d", i) のように).

この方法だと,property 値を持たない entity にはヒットしない理由もよ
くわかります.

# SimpleDB ではユーザが明示的に padding しなければなりません

複数の条件で検索するときは,それぞれの結果に対して entity key のリ
ストをマージする (intersection を求める) のでしょう.

■ GAE で禁止されているクエリについて

GAE のデータストアはいくつかのクエリを制限しています.複数のタブレッ
トサーバに渡るような大量な検索結果に対して,大がかりなソートを行う
のは避けたいところです.なので,そうなりそうなクエリを制限している
ように思えます.たとえば,不一致 (!=) による検索はできません.また,
範囲検索を行うときは,同じ property でソートしなければなりません.

# SimpleDB はソートの機能を持っているのに利用できないようにしています

複数の property を使った範囲検索も制限されています.一般論としては,
範囲検索は一致検索より多くの結果をもたらすので,その intersection
や union の計算を避けているのでしょうか.

# SimpleDB は,範囲検索でも intersection や union を求められたような?

クエリプランナについてはまったくわからないです.ひとつのサーバ内で
あればプランニングも有効そうですが,全体的なプランニングをやろうと
すると scale しなそうなので,やらなそうです.

ところで,Bigtable はオフラインのバッチ処理向け (インデックス作成の
ため) に開発されたと思うので,「平均性能は高いけど,ときどき性能が
落ちることがありそうだ」と思っていました.たとえば,タブレットサー
バが compaction が行っていると,レスポンスが悪化しそうです.その点
では,最初からオンライン処理を想定している (と思われる) SimpleDB の
ほうが問題が少なそうです.

とはいえ,Analytics, Base, Earth, Finance など多くのサービスで問題
なく使われているようなので,なんらかの解決策はあるのでしょう (2重構
成にして,速いほうを使うとか).

一言メッセージをこっそり送信できます (非公開)
 今年の西暦→