Google App Engineでランキングやページングを実現する - $koherent->diary(情報元のブックマーク数)

GAEでのランキング計算問題。Skiplistを使えば拘束に求められるんじゃないか・・・らしい。確かに件数多いと都度ソートして上からカウントか。

Google App Engine (GAE)に関する日本最大の勉強会(だと思う)appengine ja night #7 (ajn7)が行われました。
その中で『ランキング問題』が話題に上がりました。『ランキング問題』とは、何十万件もの点数のデータがあるときに、App Engine上で、「◯点は何位です」と高速に求めることは難しい、という問題です。(◯ページ目を表示、というページングもこれと同じ種類の問題になります。)
ajn7では「上位でない限り正確な順位は必要ないのではないか」という話になりましたが、Skiplistを用いた検索アルゴリズムを使えば正確かつ高速に順位を求めることができるのではないかと思い、実装&検証してみました。

Google App Engineでランキングやページングを実現する - $koherent->diary

事前計算なしでその場で順位計算。

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

Google App Engineでランキングやページングを実現する - $koherent->diary

件数に関わらず一定の速度でレスポンスがある。

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

Google App Engineでランキングやページングを実現する - $koherent->diary

サテライトからの参加だったんだ!行きたかったなあ・・・

このサテライト会場は京都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にご参加下さい(僕もつい先日初参加したばかりです)。

Google App Engineでランキングやページングを実現する - $koherent->diary

screenshot