読者です 読者をやめる 読者になる 読者になる

GeekFactory

int128.hatenablog.com

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

app engine java

前のエントリで 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 = {k1, k2, ..., kn} として、

s0 = { キーが k1 より小さいエンティティ }
s1 = { キーが範囲 [k1, k2) にあるエンティティ }
sn-1 = { キーが範囲 [kn-1, kn) にあるエンティティ }
sn = { キーが kn 以上のエンティティ }

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

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

  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

並列処理のためにエンティティを分割する方法としては十分と思います。シャードが大きすぎたらオンメモリで再分割すればいいし。どう考えても appengine-mapreduce 向けに追加された機能としか思えませんが、ajaxの分割読み込み等にも使えたら面白いですね。

*1:コメントを読むと中の人の話が垣間見られて面白いです。例えば、1.4.2で "__scatter__" がEntityクラスの定数になるとか。