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

今日は、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本体以外で実行させても問題ないでしょう。

先日のエントリーにあるようにgoogle app engine をいじっているのですが、そこで、 RatingPropertyという独自のデータ型があるのを知りました。これは、テストの点のような0~100の整数値を表現するクラスです。普段全然気にしていなかったのですが、プログラムをやっていると0~100って少し違和感を感じますね。全部で101個の要素があるわけなんで。プログラム的には0~99点か、1~100点のほうがしっくりきます。テストで100点とったときは、実は101番目にいい得点だったんですね。

ちなみにこの手の問題、Flexのdate型を使うときは本当に効いてきます。この型では、1月は0、２月は1として表します。これがpythonのdatetime型になると、1月は1、２月は2として表します。これにはまったときもありました。

また、ほとんどのプログラム言語では基本0スタートですが、愛用するMathematicaでは基本1スタートです。

いずれにせよ、0~99か、1~100であり、0~100は特殊ですね。

追記：ただ0~100は複数の教科の合計の時、0点と満点(5教科のテストなら500点)がはっきり分かり、その差をとりやすいという特徴がありますね。0~99では、合計したとき0点のみがはっきり分かり、1~100では合計したとき満点のみがはっきり分かるだけです。

クラウドマップの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.”

前回の「タグ表」に引き続き、個々のアイテムを整理して表示する機能を追加しました。今回は、タグではなくコンテンツを一覧で表示するものです。「タグ表」の場合は全体のタグ分布を表していましたが、「コンテンツ一覧」は見ている領域内のコンテンツ群をテーブルで表します。上図では”iphone”領域に来たときにこの機能を立ち上げた様子を示しています。iphone関連の記事がまとめて表示されているのが分かると思います。右クリックメニューで使用可能です。

この機能は単に表示するだけでなく、テーブル内でアイテムをソートすることができます。最初は注目順（高さ順）でソートされてますが、日付でソートしたり、urlでソートしたりすることができます。これは列のヘッダーをクリックすれば可能です。

「タグ表」と「コンテンツ一覧」機能をうまく使えば、かなり一気にコンテンツを見ることができると思います。試してみてください。

右クリックメニューで「タグ表」をクリックすると上のようなウインドウが現れるようにしました。この表は、マップ全体を4×4分割して、それぞれの領域で、上位タグを列挙したものです。もともとタグは散らばって表示されていますが、このように整理することで視認性を向上させ、全体のタグ分布の把握を助けます。リスト内のアイテムをクリックすると、対応するマップ点に移動します。また、深い位置にいる場合は、今いる分割領域と対応するリストの背景がハイライトされます。ぜひ試してみてください。

クラウドマップに、個々のエントリー(webサイト)をエントリーの投稿時間順で(twittervisionのように)自動的に表示する機能を追加しました。一定の時間間隔で各エントリーに移動し、詳細情報が下に現れます。

右クリックメニューで使用可能です（現在は、はてな注目WEBのみ対応しています）。

この機能の狙いの一つは、ぼーっと眺めて情報を得るようにすることです。ある意味、究極の受動型検索と言えます。普段RSSリーダーで高速に記事を読んでる方も、たまにはゆったり見ることで、意外な発見が得られることを期待しています。

もう一つの狙いは、エントリーを時系列で表示することで、そのとき何が起こっていたのか、また、その後何が起こったのかといったといった、事象の因果関係を把握できるようにすることです。マップ自体にはそのような時間情報がないので、別のこのような形で見せるようにしました。時間情報をどのようにマップに組み入れていくかは、まだまだ面白い課題であり、今後もさらに検討していくつもりです。

トップページのデザインを更新しました。なんか未来的になった感じがします。

これまで、最初のページから図の中央のマップ部分だけを表示するページに直接飛ぶようになっていましたが、新バージョンでは、図のように同一ページで表示し、さらに、左のメニューバーと右の詳細ビューが見えるようにしました。

新しく加えた詳細ビューは、フラッシュ内のコンテンツをクリックすると、そのコンテンツの詳細情報が見えるようになります。クリックしたものはキューリストとして溜まっていき、後で一気に見るといったことができるようになります。

また、メインの3つに分割された表示領域はその境界線をドラッグすることで、サイズを変更することができます。マップを大きくしてみたいとき、詳細ビューを大きくしてみたいときに利用してみてください。

技術的には、ホームページはjavascriptのjqueryをもとにして作られています。初めて利用したのですが、評判どおり、非常に簡単に、動的なページを作ることができました。今後もいろいろと改良を加えていきたいと思います。

追記：その後、3コラムから2コラムにして、その右ペインを水平分割するというレイアウトに変えました。詳細を見るときに視線の動きが左右よりも、上下に動いたほうが見やすいと感じたからです。

これまで、タグやコンテンツの出現分布に大きな偏りがありました（左図）。これは、人気のあるものほど手前にくるという基準だけで表示させていたからです。どの辺が人気なのかを知るにはいいのですが、偏りがあるほどマイナーなコンテンツを探しづらくなります。そこで、この偏りを表示の際に緩和させました（右図）。ここでは、マップを4分割してそのなかでそれぞれ人気順で表示させました。9分割などもできますが、やりすぎると人気度が反映されなくなってしまいます。試行の末、4分割あたりがちょうどいいと判断しました。

ルーペ機能を実装しました。

タグor背景をダブルクリックするとルーペが現れます。

もう一度クリックorダブルクリックするとルーペが消えます　（ドラッグ機能はルーペ中そのまま使えます）。

ルーペ内では奥で見えなかったタグが拡大して表示されます。

（うまくいかない場合は、古いキャッシュが残っている可能性があります）

この機能を設けた理由は、最初に表示される地図だけではどこになにがあるかがやや分かりづらかった点を解消したかったからです。この問題はクラウドマップにおいて今後も課題となると思いますが、その一つの打開策としてこのルーペ機能をつけました。ルーペを用いることによって、個々をズームして見るのに比べ、高速に深いタグの分布まで見ることができます。ぼーっと無目的で眺める場合と、検索で一発でたどりつく場合の中間くらいの目的の時に有用なものと考えています。

クラウドマップに新しい道順表示機能を追加しました。地図上でクリックしたタグやサイトの訪問履歴を線でつないで表示する機能です。今まで、地図を深くたどると自分の居場所が分からなくなることが多かったのですが、これで多少は改善されたかと思います。また、グローバルマップにも道順が表示されるので、どこにいって、どこにいってないかを把握することができます。これは、マップを包括的に見たい場合に便利かと思います。（マップ上にミステリーサークルのように絵を描いて遊ぶこともできます）。ただし、いまのところキャッシュ機能はつけていないので、一度、ページを閉じるとリセットされます。デザインもまだシンプルです（見せ方を工夫すればかっこよくなる気がします）。この機能に名前をつけるとしたら、見た目的に”contrail”（コントレイル:飛行機雲）機能といったところでしょうか。

前記した「Flashの速度向上に関して」で、マップ上のコンポーネントの生成をなるべく抑えるようにしたと書きました。具体的にはこれは、描画するコンポーネントを使いまわすことで実現しています。今日はその点について解説します。

クラウドマップでは現在、大きいもので1万件ほどのコンテンツをマップ上に配置しています。もちろん、それと同数の描画コンポーネントを作るのは非効率です。そこで、位置情報だけ先に読み込んでおいて、見ている部分だけ、コンポーネントを作成すればよいと思われます。

このとき、見終わったコンポーネントを削除して、新たに描画領域に入ってくるコンポーネントを作成するという方法があります。しかし、これはコンポーネント作成の負荷が描画の度にかかってしまうので遅いです（旧バージョンではそうしていました）。

よりよい方法は、見終わったコンポーネントを削除せずプールしておいて、新規のコンポーネントでパラメタだけ変えて再利用させることです。つまり、deleteとnewの操作から、親コンポーネントのremoveChild(*)とaddChild(*)の操作だけで済ませるようにすることです。実際に、この方法で処理速度が向上したことを確認しました。

おそらく、このような方法は常套手段とは思いますが…。

Flash(flex)を始めてかれこれ1年近くたちました。この間、何段階か大幅なリファクタリングが行われました。マップ上のコンポーネントの生成をなるべく抑えるようにしたり、アニメーションの最中には簡略的に描画したり、データを分割して渡したりと。その甲斐あって、初期のプロトタイプに比べると大幅に速度向上しています。

思うに、FlexBuilderのリファクタリング機能は最高です（ある程度マシン性能が必要ですが）。簡単に名前を変更できたり、コンパイルが通るかどうかを動的に逐一チェックしてくれます。「発生をマーク」する機能も非常に便利で、変数のありかをすばやくチェックできます。

また、FlexBuilderのプロファイラーを使うと、ボトルネックの把握に便利です。速度だけでなく、メモリ使用量もチェックできます。私もこれで、見落としていた無駄な処理を発見したことがあります。

処理速度でよく問題になるなのは、使うマシンによって速度が異なることです。たいてい開発用のマシンは速いのですが、ノートパソコンで使うなど、一般的にはもっと遅いものです。なので、遅いマシンでチェックしておいたほうがいいです。

現在、クラウドマップのプログラムはFlash、Python、C++で書かれています。クライアントサイドは、FlashかJavascriptかの選択肢がありますが、ここでは処理速度の速いFlashを選びました。クラウドマップではマップ上に多数のコンポーネントを表示する必要があるためです。

サーバーサイドは主にPythonを使用しています。Pythonと対をなす言語としてRubyがありますが、ここではPythonを選びました。主な理由は科学計算と相性がいいことです。特に、数値計算ライブラリのNumpyとScipy、Matlab風の数値プロットができるMatplotlib、行列データをHDFファイルとして保存できるpytables、などの科学系ライブラリは完成度が高く、非常に便利です。クラウドマップでは様々な統計処理が行われますが、その要所要所でこれらのライブラリを使用しています。

また、科学計算のコアな部分は処理が高速なC++で実装しています。ただやはり開発のしやすさは動的言語のPythonにはかないません。そこで本当にコアな部分だけC++で実装し、pythonのctypesモジュールを用いて連携をとったうえで、開発を進めています。