Google App Engineのランキング問題

Google App Engineで何かと話題になってたランキング問題。
appengine ja night #8(ajn8)に参加された方ならご存知のように、既にid:koherentさんがSkiplistというアルゴリズムを使って解決しています。
参考：http://d.hatena.ne.jp/koherent/20100425/1272176872


そのほかにも、id:bufferingsさんの実装例もあります。
参考：http://d.hatena.ne.jp/bufferings/20100225/1267121912


id:bufferingsさんのとほぼ同じアイデアを自分でも思いついてたんで、ちょっとslim3使って実装してみました。
http://tetz-lab.appspot.com/ranking/
事前に乱数で10万件の点数データを入れてあります。
って、何を今更な感じなんですが、せっかく思いついて実装までしちゃったので、日記に残しておきます。


ロジックを簡単に説明します。
まず、

  • 点数ごとにその点数を取った人数を格納する領域を用意する。
  • その領域をサイズ16の配列に格納する。点数の下位4ビットが配列へのindexとして使用される。
  • その上位4ビットをindexとして持つ配列に、上記の配列を格納する。この配列では格納された全配列の保持された人数の合計値を保持する。
  • さらに上位4ビット･･･(繰り返し)

というデータ構造を作ります。
69,533点(16進数で10F9D)を例に考えると、下の図みたいな感じの構造です。


ランキングを計算するときには、赤い矢印で示したより高い点数の領域に格納された人数の合計値を計算し、最後に+1すればOKです。
今回の実装では、全Layerの配列をまとめて一つのEntityに保存しているので、getは一回で済みます。
ちなみに、もし配列毎にEntityを分けても、ランキング計算・更新処理ともに一番上Layerには必ずアクセスする必要があるので、分散させることはできません。分散に関しては後述。


ランキング計算にかかる時間は初回は600〜1000ミリ秒程度、2回目以降は70〜120ミリ秒程度でした。
2回目以降が早いのは、多分Datastore側にキャッシュされるからかな？(spin upは計算時間に入れてないから、関係ないはず。)
頻繁にアクセスがある場合には、70〜120ミリ秒で処理できる、ということになりそうです。
更新は120〜200ミリ秒程度かかっています。


この方式のアルゴリズムの速度は、Skiplistと違って点数の件数には影響を受けず、点数の取りうる範囲に影響を受けます。
点数が取りうる値が0〜Xだとすると、アルゴリズムの速度は、
　　O(log 16 (X))
になるんじゃないかと思います(多分)。

Skiplistと比べると…

このデータ構造はSkiplistと比べて、汎用性がありません。
扱うのが整数値の点数なら問題ないですが、例えばこれが小数値だと途端に難しくなります。
特に文字列を扱うのは多分無理でしょう。
Skiplistなら任意ソート条件が扱えるんですが、こちらは使用できる条件がかなり限定されます。


まあでも、その限定された条件なら高速に動作しますし、速度がデータ件数に依存しないって特長もあるんで、使いどころはそれなりにあるんじゃないかとは思います。

ランキング計算以外も実現できる？

id:koherentさんがajn8向けに作成されたスライドを見ながら、同じことができるか考えてみました。
http://www.slideshare.net/koher/skiplists20100604

  • P.36　リストの要素数･･･一番上の階層の保持する人数。O(1)で計算可能。
  • P.37　要素番号による検索･･･要するに「○位の人は何点」。ランキング計算同様、O(log 16 (X))で計算可能。
  • P.39　総和・平均･･･同様に、配列と一緒に格納された要素の総和を保持すれば可能。一番上のLayerから取得すれば良いので、O(1)でOK。
  • P.40　範囲に対する集約･･･同様に実現可能。
  • P.41　最大・最小・中央値･･･要素数番目・0番目・要素数/2番目の検索として実現可能。全部O(log 16 (X))。
  • P.42　キー値以外の集約･･･これも同様に配列と一緒に保持すれば可能。
  • P.43　キー値以外の最大・最小･･･これも同様にやれば多分可能そうですね。

という訳で、集計関係はほぼ同じ事が実現できそうです。

その他、Pagingは一応無理すれば条件付きで実現できそうなんですが･･･これに関しては無理やりな感じが否めないので、割愛します。

分散への考察その１−分散カウンタ方式

スケールするカウンタの実装として、「分散カウンタ」というのが知られています。
appengineでは更新処理に比べてgetがとても早いので、カウンタ用のEntityを複数個用意して、
　・更新はランダムに選んだどれか一つに対して実施
　・カウンタの値は全部parallel getして合計値を計算
とすることで、高速かつスケールするカウンタが実現できる、というものです。


上にも書きましたが、この実装ではEntity1個でやっているので、この考え方がほとんどそのまま使えます。
実際に実装したのがこちらです。
http://tetz-lab.appspot.com/ranking/?type=sharding


id:bluerabbitさんの、
http://d.hatena.ne.jp/bluerabbit/20091226/1261756546
を参考にさせていただきました。ありがとうございました。m(__)m


ランキング計算にかかる時間は初回は800〜1300ミリ秒程度と少々遅いものの、2回目以降は70〜200ミリ秒程度とそれ程変わらない速度が出ています。parallel getって早いんですね。
更新はEntity一つの場合とほとんど変わらない値が出てました。

分散への考察その２−Entity分割方式

全点数を一つのインスタンスに格納するのではなく、適当な点数の範囲毎にインスタンスを分けて分散させるアイデアです。
今回試しに実装したものは0〜10万点の範囲で作成していますが、これを4096点毎に25個のインスタンスに分けて実装したのが↓です。
http://tetz-lab.appspot.com/ranking/?trn=gtx&type=divided


ランキング計算にかかる時間は初回は600〜900ミリ秒程度、2回目以降は70〜150ミリ秒程度でした。更新は80〜150ミリ秒程度。Entityが小さくなった分、若干更新が早いみたいです。


しかしこの方式だと特定の点数に負荷が集中するとスケールしないので、Entityへの負荷が高まってきたらそのEntityを分散カウンタ方式で分割する、といった対処も考えた方がよさそうです。