クラウドマップ開発ブログ

今日は、Google App Engine(GAE)の地理データ処理について書きます。GAEによるクラウドマップのAPI化を試みているのですが、その中で多少特殊なテクニックが必要とされる部分がこれでした。

まず目的は、x,y,z (latitude,longitude,elevation)で表される点の集合を地理的な範囲で絞り込むことです。具体的には、xmin<x<xmax, ymin<y<ymax,zmin<zの範囲の中にある点集合を取り出すことです。

普通のデータベースなら何の問題もないのですが、GAEの場合、範囲指定が一つの変数にしか使えないという制約があるので、この絞込みを素直に実行できません。つまり、xmin<x<xmaxのみならいいが、それに加えて, ymin<y<ymaxやzmin<zなど行うことはできないということです。

結論から言うと、xmin<x<xmax, ymin<y<ymaxの絞込みはgeohashと呼ばれるもので、zmin<zの絞込みはListPropertyで行うのがベターだと思います。

■　GAEでgeohashがいいというのはこちらを参考にしました(googleも採用しているそうです→ソース)。geohashは、ある領域を011011111111000001000001などのビット列で表し(それをBase32等でエンコードし)たものです。奇数番目のビット列(0111110000000)がx座標を表し、偶数番目のビット列(101111001001)がy座標を表します。それぞれのビット列の、左端のビットから、全体領域を2分割していったときに左(上)にあるか右(下)にあるかを示し、徐々に細かい粒度の領域を指し示すようになります。図で表すと次のようなものです：

最初の2×2分割を表すのに00,01,10,11というビット列が使われ、次の4×4分割を表すのに、後ろ2ビットが新たに追加されます。

この表現方法でうれしいのは、例えば、011011111111000001000001としたときに最初の01という大まかな領域にあることが分かることです。そして、01の領域の内部を表すには、01≦pt<10とすればいいことです。これにより、x座標の絞込みとy座標の絞込みが同時に行え、GAEの制約を回避することができます。制約がなくても、速度の面から見てこのような方式は有用だろうと思います。

■　さて、geohashでめでたくx,y座標の絞込みはできたのですが、クラウドマップではまだz座標の絞込みをする必要があります。ある高さ以上の点を表示したいというものです。このような絞込みはgeohashのような分割木的な絞込みとは様相が異なります。ここではListPropertyによってその制約を切り抜けました(調査不足で他にこの手の問題を扱っているものが見当たらなかったので確立された方法かどうか分かりません)。

ListPropertyはGAE特有のデータ型で、リストを格納できます。さらに特殊なのは、where句で例えば、list_data = 2とすると[0,1,2]とか[1,2,3,4]など、リストの中にどれか一つ”2″があれば選択されるようになることです。つまり、”In”クエリ的な働きをします。z座標の絞込みはこの特性を利用します。

方法はまず、z座標をn分割します。そして、第1の層にある点をlayer=[0,1,..,n-1]、第2の層にある点をlayer=[1,2,...,n-1]、第３の層にある点をlayer=[2,3,...,n-1]、として格納します。そうすれば、layer=1と指定して第１、第2の層の点を、layer=2と指定して第1、第2、第３の層の点を取り出すことができます。この絞込みは範囲指定でなくイコールなので、geohashの範囲指定と同時に使うことができます。連続的なz座標の絞込みは、この離散的な絞込みの後、GAE本体以外で実行させても問題ないでしょう。

クラウドマップのAPI化を推し進めるための選択肢として、今日はGoogle App Engine (GAE)に挑戦しました。ひとまず、所感や最初の手続き、はまった点などをblogにまとめてみます。

１．GAEの登録。

数ヶ月前に発表された当時は、登録が定員に達していたので使用をあきらめていたのですが、今回はすんなり登録できました。基本、携帯認証です。登録すると、固有のアプリケーション(ウェブサイト)が(現時点で)最大10個まで使用できます。

２．チュートリアルを一通りこなす。

GAEの開発は少し特殊です。まずSDKをインストールして、それでできたフォルダ上に、プロジェクトを作成します。そのプロジェクトのフォルダ内でいろいろファイルを作成します。ローカルサーバーで行う場合は、dev_appserver.pyでサーバーを立ち上げれば、すぐにプロジェクトのアプリケーションを見ることができます。ファイルを変更すれば動的にアプリケーションも変更します。本番サーバーで行う場合は、appcfg.pyを使います。これを実行するとプロジェクトのフォルダが独自にアップロードされます。更新されたファイルだけがアップロードされます。通常のFTPアップロードが(おそらく)ないところが、興味深いです。また、バージョンを分けることでき、テストと本番を使い分けることができるみたいです（参照）。

GAEのプログラムは、既存のwebフレームワークに慣れていればすんなり利用できるのではないかと思います。特に、pythonのDjangoとかなり似たものになっています。Djangoの機能も利用できます(simplejson等)。特殊な点としては、独自のユーザークラスによって、Googleのアカウント機能が利用できることや、様々な独自のデータタイプがあることなどがあることです。また、独自のSQL文（GQL）が利用できます。しかしこれは、join文などは使用できません。基本はORマッパーで操作し、リレーションはReferencePropertyによって設定するようです。

３． Bulk uploadにはまる。GAEを用いる上で確認しておきたかったのが、Bulk upload(データベースに一括アップロード)です。CSV形式のファイルをBulk uploadできるようです。

ここでまず軽くはまったのがcookieの処理です。こちらを参照にしたがうまくいかず、別のこちらの方法があり試すもなぜか無理でした。結局、後者にて、–cookie=‘ACSID=AJKiYcE[...]1Hh4′のところでシングルクォーテーションをはずして–cookie=ACSID=AJKiYcE[...]1Hh4としたらうまくいきました。windowsのコマンドラインの問題でしょうか？

次に、結構はまったのが日本語処理です。現状、GAEのBulk uploadはasciiしか対応していないので、パッチを当てるしかありません。幾つか方法が載っていたのですが、結局、こちらを参照しました。ただし、一つ落とし穴があって、本番サーバーで使用するとき、修正した__init__.pyをbulkload.pyとしてプロジェクトフォルダに置き、アップローダーのfrom google.appengine.ext import bulkloadをimport bulkloadとする必要があります（こちらを参照）。pythonで、日本語処理はいつも悩まされていたのでまたかという感じです。とりあえず、めでたく日本語でアップロードできました。

全体として、日本語の問題はありましたが、必要そうなものはひととおりそろっている感じです。すでにGAEを利用したアプリケーションも多数出ており(例１、例２、gallery)かなり使えそうです。

※追記1：

GAEにはやはりそれなりに制約がありました。ただこの制約は、ノーフリーランチというか、スケールすることを最大限に考慮した結果でもあると思います。この点に関して、以下のブログ記事が非常に参考になりました。

http://highscalability.com/google-appengine-second-look

※追記２：

現時点で、決定的な問題点はバルクアップロードの遅さです。

http://sprovoost.nl/2008/06/17/google-app-engine-on-uploading-serious-bulk-data/

このブログでは、これまで1分だったところが3日かかったと書いてあります。ローカルではさらに遅いです。これは致命的な気がしてきました…

※追記３：

データエクスポート(backup/restore)の別なソリューションが提案されています(こちらを参照)。

“データを小さな Python code に分割して保存し、うまく GAE の制限を切り抜けているようです。 “  （ただあまり進展はないようです）

※追記４：

GAE関連のデータベース設計に関して、弊社の技術勉強会で発表したネタです：

セマンティックウェブ時代のデータベース設計

こちらも参考までに。

抜粋（追記1）：

“Yes, this means that everything that we think we know about building web applications is suddenly wrong. But this is actually a good thing. Having been on the wrong side of trying to scale up web app code, Ican honestly say it is better to push the requirements of scaling into the face of us developers so that we do the right thing from the beginning. It’s easier to solve the issues at the start, than try and retrofit hacks at the end of the development cycle.

A truly excellent explanation of the differences between MySQL thinking and GAE thinking.

…

RedMonk Clouds Rolling In: The Google App Engine Q&A gives covers a lot of GAE territory. List some of the cons: Python only, not database export, lock-in, and no cron. “…all of the current offerings have limitations that throttle their usage. Many of which are related to the lack of open standards. Apart from the mostly standard Python implementation, App Engine is decidedly non-standard.

…

Groovy: Google Datastore and the shift from a RDBMS. An excellent comparison of how BigTable differs from a RDBMS. The conclusion: The end result of this, is that the standard way a developer writes out the table schema for a RDBMS should be dumped almost entirely when considering an app using Google Datastore.”

抜粋（追記2）：

“It is possible to test your application offline, before uploading it; the SDK comes with an offline data store. Of course, the offline data store is not the real thing. After 10 hours, it had only inserted about 10% of 1 tile. I also noticed that after each insert, the next insert would take longer.

So I skipped ahead and tried the real thing online. The good news is that the slowdown effect had disappeared, as I expected. The bad news is that I could only insert about 100 points each time. Any more and the server would kick me. This means I would need to send an HTTP POST request 15.000 times to upload 1 tile. That would take roughly 3 days with my current connection (remember: 1 minute with Postgres). In addition, even though I used small chunks , the connection got broken by the server after a while. That means starting over again, because the bulk upload script does not have a resume function.”