2010-03-13

Google App Engineでの検索パターン

GAE Datastore

id:higayasuo さんにTwitter上でいろいろ教わったので、メモ。

検索条件が複雑な場合

業務アプリなどでよく見かける、複雑（不特定）な条件で、かつ、特定の並び順でデータを抽出するような場合のパターンです。

例えば、
データを抽出する条件が
「場所」「日時」「部署」「担当者」...と複数あったとして、
それぞれの項目が、
ユーザーによって指定されたり、されなかったりした場合、ソートがあるために、
入力、未入力の組み合わせの数だけ複合インデックスが必要ですが、
（Datastoreではフィルターとソートのプロパティが異なると複合インデックスが必要です。）
これを全て静的に（事前に）定義するのは非現実的です。

で、id:higayasuo さんのアドバイス

adhokなqueryはeq filterだけqueryで実行してnot_eqやsortはin-memoryでやるのが最も簡単。pagingや件数の問題さえなければそれで大丈夫 #appengine

eqだけであれば、複数のfilterを重ねてもマージジョインで動的に処理されるため、
複合インデックスの定義は不要です。

メモリ上でのnot_eqやsortは、slim3を使えば簡単です。
http://sites.google.com/site/slim3documentja/documents/slim3-datastore/queries-and-indexes#TOC-18

範囲検索の場合

例えば、「現在、受付期間中のイベントを検索」のような場合、

#appengine で範囲検索するときはstartからendまでの各値をListにいれてeq filterを使うのが良いと思う。startからendまでの値が大きい場合は、適度にブロック化すると良い...

例えば、日付のstartとendなら月をListにいれて月のeq filterで絞り込んだ後にin-memory filterで<=と>=を使う

start:3/1 end:3/31なら[20100301,20100302,...,20103031]をリストに書いておき、eq(20100312)でfilterをかければ良い

もう、何も言う事はありません。これしか無いですね。

2010-03-07

図解インデックス爆発

GAE Datastore

Google App EngineのDatastoreにはインデックス爆発という現象があります。
こちらで公式に説明されているのですが、
http://code.google.com/intl/ja/appengine/docs/java/datastore/queriesandindexes.html#Big_Entities_and_Exploding_Indexes
自分にとってはすごく分かりにくく、理解するのにとても苦労しましたので、自分なりにメモを残しておきます。

まず2,3の前提を。

基本的な事ですが用語が統一されてなくて惑わされましたw
複合インデックス＝カスタムインデックス＝コンポジットインデックス
です。

またGoogle App Engine for Javaでは
WEB-INF/appengine-generated/datastore-indexes-auto.xml に自動的に作成されるのが、
必要とされる複合インデックスです。
一見、複雑に見えるクエリでも、ここに追記されない場合は複合インデックスが必要ないケースです。

複合インデックスが必要ない場合
Datastore API内部にて、
複数の（自動的に生成される）シングルプロパティインデックスを元に、
マージジョインという手法によりクエリ結果が求められます。

インデックス爆発とは

順を追って説明します。

シングルプロパティ(String)インデックス

これは自動的に作られるものですが、比較のために載せます。
これは説明不要ですね。

シングルプロパティ(List)インデックス

これも自動的に作られるものですが、
Listプロパティの場合、エンティティは１つ（RDBでいう１レコード）にも関わらず
List内のすべての値に対してインデックスのエントリーが用意されます。

複合インデックス

これが複合インデックスです。
一つ前の例と同じく、エンティティは１つなのに、Datastoreは
すべての組み合わせに対してインデックスのエントリーを用意する必要があります。
なぜなら、
x=aaa and y=ddd
x=bbb and y=fff
など、どんな組み合わせにのクエリにもヒットする必要があるからです。

インデックス爆発を起こすケース

上記のように１エンティティに対して複数のインデックスエントリーが生成される場合において、
そのエントリーが5000を超えた場合に「インデックス爆発」となり、
該当インデックスは使用不可となります。

具体的には例えば、Listプロパティが３つあった場合、
値のバリエーションがそれぞれ１８個あった場合、18×18×18でその複合インデックスは爆発します。
（もちろん複合インデックスを必要としなければデータの格納自体に問題はありません。）

間違いやすいケース１

（私だけかもしれませんが）勘違いしやすいケースとしてこんな場合があります。
この場合、複合インデックスであっても
１エンティティに対するインデックスのエントリーは１つなので、何の問題もありません。

間違いやすいケース２

複合インデックスが必要ない場合、Listプロパティがいくつあっても問題ありません。
この場合はマージジョインで処理されます。

ちなみに複合インデックスが必要なケースというのが意外に分かりづらいです。以下引用です。

次のような他の形式のクエリはインデックスが datastore-indexes.xml で指定されている必要があります。
・複数の並び替え順序を持つクエリ
・キーに降順の並び替え順序の指定されているクエリ
・1 つのプロパティに対して 1 つ以上の不等式フィルタを持ち、その他の~~クエリ~~プロパティに対して 1 つ以上の等式フィルタを持つクエリ
・不等式フィルタと祖先フィルタを持つクエリ

まとめ

結論としては、「複合インデックス」と「Listプロパティ」が合わさると意外に簡単に発生します。
が、上記を理解していれば、絶対に防げる現象でもあります。
後からモデルの設計を変更するのは非常に大変なため、事前によく吟味することをおすすめします。

間違っていたら突っ込みおねがいします！

2010-02-27

Google App Engineでランキングを実現する方法

準備

まず、例えば以下のようなリストをTaskQueueを使って事前に用意します。
これは単純に、得点の上位から1000人区切りでキリ番の人がそれぞれ何点なのかを記録してます。

1000人目　98432点
2000人目　83563点
3000人目　68779点
.
.
.

これが基準点となります。
ポイントは「人数」で区切っていること。
これで得点の分布がどうであろうと関係なくなります。

そしたら実行。

1

例えば77777点の人が自分は何位なのか知りたい場合、
まず、上の表で77777点より一つ上の基準点を探します。(点asc, limit 1で見つかる)
この場合は、83563点が見つかってその時点で自分が2000位より下であることが分かります。

２

後は、実際の点数表から83563点から77777点まで、
何人の人がいるかを数えるだけで順位がわかります。
(点desc, 83563>点, 点>77777のリストサイズを調べる)

コスト高そうですが、1000人単位で区切っているため、
サイズ1000以上のリストが帰ってくることはないです。

7687698998432点とか取っちゃった人は1000以内確定として、
~~98432点から逆に人数を数えればいいと思います。~~
点desc, 点>7687698998432で問い合わせればいいと思います。

３

ここまでが、大枠の考え方ですが、一つ困ることがあります。
例えば、基準点である83563点を取った人が999人いる場合です。
(1000人いた場合は自ずと基準点が次になるはず。)
83563点+1点の人は本当は2999位なのに、2001位に見えてしまう。

これには最初の表を以下のようにすることで対処します。

1000人目　98432点　5人
2000人目　83563点　999人
3000人目　68779点　1人
.
.
.

~~同じように、77777点に複数人いた場合も実行時に同点の人数をチェックすることで調整できます。~~
~~（点＝77777点の人を、(2)と同じ並び順で自分まで数える）~~
自分の得点より前の人数を出すのでここは必要ないですね。
id:bufferingsさん、ありがとうございます。

まとめ

- 準備　○人単位でそれぞれ何点か（＝基準点）の表を持つ

1. 自分はどの基準点のすぐ下なのか問い合わせ
2. 基準点から自分まで何人いるのか問い合わせ
3. ~~自分と同点の人が何人いるのか問い合わせ~~

どうでしょうか？
実際に組んでないのでアレですが、、、
どんな規模や分布にも左右されず、
必ず~~３クエリ~~2クエリで答えが出せるという点でいいかなと思っています。
パフォーマンスも一定です。

あとは、人数単位の基準表をいかに素早く更新するか、ですが、
TQのとかの工夫でどうにかなると思っています（適当w）

追記

元の点数表に更新がある度に、基準表を更新すれば、
総なめは初回だけでいいかもしれないですね。
元の点、新しい点を更新機能に渡すようにして、
基準点をまたぐ時だけ、基準点を±すればいいのでは、と思っています。
あたらしく基準点が生まれるタイミングをどうにか捕まえる必要がありますが。

そう考えると、基準点が生まれるタイミングさえ逃さなければ、
最初から総なめではなく、その方式でいいかもしれない。

2010-02-27

Google App Engineでランキングを実現する方法を考えてみた

twitter上の議論で、GAEでランキングを実現する方法について盛り上がっていました。
んで、俺も思いついたのでさらします。

2010-02-14

Google App Engineのdeployでconflictエラー

Eclipseからアプリケーションをデプロイ中に固まってしまったので、
Eclipseを強制終了したら、次から

409 Conflict
Another transaction by user xxx is already in progress for this app and major version. That user can undo the transaction with appcfg.py's "rollback" command.

コンフリクトエラーとなり次回からデプロイできなくなります。。。

そんなときは、Windowsのコマンドプロンプトから以下のコマンドを実行。

 \plugins\com.google.appengine.eclipse.sdkbundle.<バージョン>\appengine-java-sdk-<バージョン>\bin\appcfg.cmd  rollback <ワークスペース>\<プロジェクト名>\war

これで、コンフリクトが解消されるはず。

詳しくはこちら、
http://code.google.com/intl/ja/appengine/docs/java/tools/uploadinganapp.html#Command_Line_Arguments

2010-02-11

Google App Engine for JavaでOpenIDを試してみた。

フレームワークには、slim3を使っています。（今回はあまり関係ないけど。）

ライブラリを探したところ以下の二つが見つかりました。
http://code.google.com/p/openid4java/
http://code.google.com/p/dyuproject/

openid4javaはGAE上では動かないというので、
http://groups.google.co.jp/group/google-appengine/browse_thread/thread/9e4381f41c7d942f?pli=1
試してもいません^^

今回はdyuprojectを使います。

まず、ダウンロードページから、
dyuproject-openid-1.1.6-jarjar.jarをダウンロードし（jar、jar言い過ぎです。）
war/WEB-INF/libに配置して、パスを通します。

マニュアルでは、web.xmlについて、
http://code.google.com/p/dyuproject/wiki/QuickStartOpenid
という記述になっていますが、このままですと、
mixiのOpenIDで試すとニックネームが取得できませんでしたので、
オリジナルのFilterを拡張しました。

拡張Filter

public class OpenIdFilter extends OpenIdServletFilter {

    public static final String NICKNAME = "nickname";

    @Override
    public void init(FilterConfig config) throws ServletException {

        // 本来のメソッドを呼ぶ
        super.init(config);

        // nicknameを返すように指示
        RelyingParty.getInstance().addListener(
            new AxSchemaExtension().addExchange(NICKNAME));
    }

web.xml

    
        javax.servlet.jsp.jstl.fmt.localizationContext
        application
    

    
    	openidFilter
    	slim3.filter.OpenIdFilter
      	
        	forwardUri
        	/finish
      	
    
    
        hotReloadingFilter
        org.slim3.controller.HotReloadingFilter

    
    	openidFilter
    	/finish
        REQUEST

これで、ID Providerとの通信部分は大丈夫なはずです。

最後に、認証が通ったあとは、

        // ユーザーオブジェクトの取得
        OpenIdUser user =
            (OpenIdUser) request.getAttribute(OpenIdUser.ATTR_NAME);

        // Identityの取得
        String identity = user.getIdentity();

        // nicknameの取得
        Map axschema = AxSchemaExtension.get(user);
        String nickName = axschema.get(OpenIdFilter.NICKNAME));

といった感じでデータが取り出せます。

せっかくなのでデモも公開します。
デモ
 ソース

ですが！

いろいろ試してみると、不具合もあるようです。
私が気づいた不具合は

ログインと同時に渡すパラメータは、認証後には情報から落ちている。（これは仕様？Filterで実装しているのがいけない？）
キャンセルの時、オリジナルのOpenIdServletFilterでは174行目を通るように期待してるようですが、実際には136行目の戻りがnullなので、エラーなのか、キャンセルなのかわかりません。

といったところです。

自分で直せばいいのですが、知識とモチベーションが足りません^^
おそらくRelyingPartyクラスを直せばいいはずです。(Finalクラスですが、、、)

GAEでは、Socketが使えないとのことですが、dyuprojectでは大丈夫でした。
こまかい実装までは追っていませんが、SimpleHttpConnectorなるクラスが通信していると思います。

実用には手を加える必要があると思いますが、
ともかく、GAE/JでもOpenIDが使えることは確認できました！