__scatter__ プロパティを利用してエンティティを分割する

前のエントリで id:kissrobber さんにコメントを頂きました。

Datastoreのスプリット処理ですが、"__scatter__"プロパティを使ってバラす方法もありますよ。
http://goo.gl/gNeh4 が参考になるかと思います。
App Engineで動く並列処理フレームワーク ElShard - GeekFactory

やりましょう（笑）ということで早速調べたところ、以下のことが分かりました。

__scatter__プロパティを使うと、データストア上のエンティティを分割できる。
いい感じに分割される。
分割サイズや個数は指定できない。
均等には分割されない。
開発環境では使えない。少なくとも1.4.0ではダメ。

今のところ公式ドキュメントに記載がないため、正確なことは分かりません。情報源は appengine-mapreduce のコード*1と実験結果からの推測のみです。

Datastore Viewerで確認する

管理コンソールのDatastore Viewerで以下のGQLを実行してみましょう。

SELECT * FROM kind ORDER BY __scatter__

1,000件のエンティティが入っていたら10行ちょっと返ってくると思います。これらはエンティティを分割する頂点になります。

エンティティを分割する

先ほどのGQLが返すキーを K = {k₁, k₂, ..., k_n} として、

s₀ = { キーが k₁ より小さいエンティティ }

s₁ = { キーが範囲 [k₁, k₂) にあるエンティティ }

s_n-1 = { キーが範囲 [k_n-1, k_n) にあるエンティティ }

s_n = { キーが k_n 以上のエンティティ }

のようにエンティティを分割します。

コードで書くと以下のようになります。

  List<Key> scatterKeys = Datastore.query(m)
    .sort("__scatter__", SortDirection.ASCENDING)
    .asKeyList();
  Collections.sort(scatterKeys, new Comparator<Key>() {
   @Override
   public int compare(Key o1, Key o2) {
    return o1.compareTo(o2);
   }
  });
  int scatterCount = scatterKeys.size();

  // 最初のシャード（s_0）
  {
    Key endKey = scatterKeys.get(0);
    List<Key> shardKeys = Datastore.query(m)
      .filter(m.key.lessThan(endKey))
      .asKeyList();
  }

  // 中間シャード（s_1〜s_n-1）
  for(int i=0; i < scatterCount-1; i++) {
    Key startKey = scatterKeys.get(i);
    Key endKey = scatterKeys.get(i+1);
    List<Key> shardKeys = Datastore.query(m)
      .filter(m.key.greaterThanOrEqual(startKey), m.key.lessThan(endKey))
      .asKeyList();
  }

  // 最後のシャード（s_n）
  {
    Key startKey = scatterKeys.get(scatterCount-1);
    List<Key> shardKeys = Datastore.query(m)
      .filter(m.key.greaterThanOrEqual(startKey))
      .asKeyList();
  }

ちなみに、開発環境では order by __scatter__ が何も返さないためこのコードは動きません。結果行がない場合はすべてのキーをシャードに入れる等の対策が必要です。

実験

1,110件のエンティティに先ほどの手法を適用したところ、14個のシャードに分割されました。シャードごとの件数は以下のようになり、かなりバラツキが見られました。

キー範囲	件数
- Book(10028)	27
Book(10028) - Book(13016)	138
Book(13016) - Book(13038)	22
Book(13038) - Book(18034)	246
Book(18034) - Book(18049)	15
Book(18049) - Book(21047)	148
Book(21047) - Book(23012)	65
Book(23012) - Book(23019)	7
Book(23019) - Book(24043)	74
Book(24043) - Book(27044)	151
Book(27044) - Book(28004)	10
Book(28004) - Book(30030)	96
Book(30030) - Book(31046)	66
Book(31046) -	45