Google App Engineでランキングやページングを実現する

昨日一昨日、Google App Engine (GAE)に関する日本最大の勉強会(だと思う)appengine ja night #7 (ajn7)が行われました。

その中で『ランキング問題』が話題に上がりました。『ランキング問題』とは、何十万件もの点数のデータがあるときに、App Engine上で、「◯点は何位です」と高速に求めることは難しい、という問題です。(◯ページ目を表示、というページングもこれと同じ種類の問題になります。)

ajn7では「上位でない限り正確な順位は必要ないのではないか」という話になりましたが、Skiplistを用いた検索アルゴリズムを使えば正確かつ高速に順位を求めることができるのではないかと思い、実装&検証してみました。

ランキング(順位取得)のデモ

下記ページで順位取得のデモを動かしています。スコア(点数)を入力すると順位と取得にかかった時間が表示されます(時間にはばらつきが大きいため、取得が遅い場合は何回か試してみて下さい)。

このデモでは、順位は事前に計算されておらずアクセス時にその場で計算しています(事前に計算しておく方法は、挿入時に後ろの順位をすべて付け替える必要があるため、現実的ではありません)。また、このデモでは順位を入力しても新しいデータは挿入されないようにしています(順位取得の時間だけを計測するデモのため)。

http://appengine.koherent.org/ranking

独自ドメインになっていますが、App Engine上で動いています。http://koherence.appspot.com/rankingからもアクセスできます。

Skiplistとは

Skiplistは1990年に発表されたデータ構造(およびそれを利用した検索アルゴリズム)です。シンプルな実装ながら、平衡木と同じように参照・挿入・削除・置換をすべてO(log N)で実行することができます。

Skiplistの解説はこちらにあります。Skiplistは連結リストを複数組み合わせたようなデータ構造なのですが、電車の特急・急行・各駅停車を乗り継げば効率良く目的の駅に到着できるように、ノード(App Engineのノードではなく、Skiplistのノード。駅に相当する)の間引かれた複数の連結リストを乗り換えながら探索することで、高速な参照・挿入・削除・置換を実現しています。

通常のSkiplistでは平衡木等と同じく「何番目か」という情報を取得することができないので、今回はSkiplistの改良型であるIndexable Skiplistを実装しました。

どの程度のパフォーマンスが出るのか

1万件のデータを登録してパフォーマンスを検証してみました。本当は10万件で検証したかったのですが、それだけの件数をすぐに登録することはできなかったのでとりあえず1万件で検証しました。

0〜999999点のスコアをランダムで100個生成して、それぞれの順位を取得するのに要した時間の平均値および標準偏差を求めました。

実時間 [ms] CPU時間 [ms] API時間 [ms]
平均 2774.7 223.4 709.7
標準偏差 2062.7 102.9 308.6

重要なのは、この結果が導くのは10万件のデータのときに10倍(約27秒)かかるということを意味「しない」ことです。Skiplistでは件数に対して操作時間が対数関数的に増加するため、おそらく10万件で3〜5秒、100万件でも5〜8秒程度で順位を取得できると思います。10万件に関しては追加して実験してみたいと思います。また、今回はputの時間を検証していませんがこれも追加して実験したいと思います。感覚的には順位取得の2、3倍程度の時間がかかっているように思います。

パフォーマンスを考えると、実用の際には頻繁にアクセスされる上位の結果をMemcacheに入れて、個々人の順位を取得する場合だけSkiplistにアクセスするという使い方になるでしょう。

ページングに関しても、基本的にSkiplistで同じように実現できると思います(指定した順位から指定した件数のデータを取得するという操作が可能です)。

考察

Skiplistは連結リストのように順々にノードたどっていくため、これをDatastore上に実装しようとすると一つの順位を得るために何度もDatastoreにアクセスしなければなりません。Datastoreは1回読み書きが遅いので、その点で本来連結リストのようなデータ構造には不向きと言えます。ただ、SkiplistではO(log N)で読み書きが可能なので、件数が増えてもアクセス回数の増加は極めてゆるやかです。ですので、何度もDatastoreにアクセスするのは望ましくないけどそれほど回数は多くならないはず、その上で許容可能な回数におさまるかどうか、というのが検証ポイントでした。今回の結果を見る限り、数秒程度の処理時間を許容できるのであれば数万、数十万件規模のランキングを必要とするシステムでも実用可能なのではないかと思います。

ただし、Skiplistの性質上1件ずつしか更新を行うことができないため、更新が極めて多いシステムでは利用が難しいと思います。仮に1件の更新に5秒が必要とすると、それ以上のペースで更新が行われるシステムでは利用できません。

また、一度の操作で複数回のDatastoreアクセスが必要になるため、通常のDatastore操作に比べて多くのリソースを消費します。特にputの処理では複数のノード(一つのノードを一つのエンティティで表現)のポインタの付け替えが発生するため、リソース消費が激しいです。今回1万件を登録するために、無料枠のQuota*1をCPU Timeで65%以上、Datastore API Callsを8%以上使用してしまいました(ただし、put以外の、データ作成や出力などのすべての処理を含んだ消費量です)。

プログラムのソース

Indexable SkiplistをGoogle Collections LibraryのMultimapとして実装しています。が、現在まだ順位を求める部分だけを実装した中途半端な状態なので、きちんと実装できてからオープンソースのライブラリとして公開したいと思います。

その他

今回、僕はajn7に関西のサテライト会場から参加しました。

このサテライト会場は京都GTUGのid:bufferingsさんによって提案され、実施されました。GTUGとはGoogle Technology User Groupの略で、Googleの技術に関するユーザ団体です。GTUGは世界中で活動しており、京都GTUGはその中でも最も活発なグループの一つです。京都GTUGではappengine ja night in kansaiというApp Enigine勉強会を開催しています(まだ1回だけですが、近々第2回が開催されると思います)。App EngineやGoogleの技術(GWTAndroid、...)に興味のある方はぜひ京都GTUGにご参加下さい(僕もつい先日初参加したばかりです)。

また、京都GTUGの活動の会場は、京都リサーチパーク株式会社にご提供いただいています。最近では町屋スタジオという京都らしい施設もオープンされたそうです(そのうち町屋ハッカソンも開催されるとかされないとか)。その他にも様々活動をされているので、興味のある方はチェックしてみて下さい。

*1:一日の無料分のQuotaはCPU TImeが6.50 CPU時間、Datastore API Callsが10,368,000回です。