App Engine上で順位・平均・中央値等を計算するライブラリを作る

先日のエントリー「Google App Engineでランキングやページングを実現する」にたくさんのブックマークをいただきありがとうございます。まさかここまで盛り上がると思っていなかったので驚いています。

前のエントリーでSkip ListではなくB-treeによる実装について書きましたが、色々と検討した結果Skip Listでライブラリを実装しようと思います。ライブラリはGoogle App Engine for Java (GAE/J) 用で、次の機能を実装したいと思います。

  • ソートキー(得点など)から順位計算
  • ソートキーから値を取得
  • 順位から値を取得
  • ソートキーで範囲検索(inclusive、exclusive設定可)
  • 順位で範囲検索(inclusive、exclusive設定可)
  • 範囲(全体も可)に対して次の項目を計算
    • 個数
    • 合計値
    • 平均値
    • 中央値
    • 最小値
    • 最大値

ディスカッション

前回のSkip Listの実装は試験的なものだったので、実用を考えると色々と検討しなければなりません。これまでに @kazunori_279さん、@kibayosさん、@itawasaさんらを中心に、どのようにSkip Listを実装すべきかについて議論してきたのでまとめておきます(きれいに切り分けられているわけではないですが一応議題別にまとめてます)。

以下、単にノードと書いた場合Skip Listのノードを指しているものとします(Datastoreのノードの場合はそのように明記します)。また、log_Mは底がMの対数関数を表すものとします。

ノードのブロック化について
  1. 1ノード1エンティティで実装すると、log_2(N)回程度のDatastoreアクセスが発生する。N=100万なら20回。Datastoreは1回1回のアクセスが遅いので辛い。Skip Listは連結リストのように順々にたどっていくので並列getもできない。
  2. B-treeのようにM分木的な実装ができればlog_M(N)にでき、M=1024程度にしておけば2〜4回程度のDatastoreアクセスで目的のノードまでたどり着ける。
  3. B-treeだとLock-freeにならないからSkip Listのノードをうまくブロック化した方がいいんじゃないか。
  4. Skip Listのノードをブロック化する場合、同一階層の横につながったノードをブロックにすることになる。
最上位階層への更新の集中について
  1. Skip Listに順位などの付加情報を加える場合、更新時に必ず最上位階層まで更新が波及する。ブロック化されていると最上位階層を表す特定のエンティティに更新が集中する。
  2. しかも、DatastoreでCAS的な動作を再現しようとすると、トランザクションでget→putとなり重い。
  3. トランザクションを使うので並列putもできない。更新対象に成り得るノードを同一のエンティティグループにするとSkip Listの大部分を同一のエンティティグループにすることになってしまう。
  4. putはスケールしなくても、getだけはスケールするというのでよいのでは?
  5. LogCounterのような仕組みで最上位階層に対する更新対象エンティティを分散して高速化できないか。
スケーリングについて
  1. Skip Listだと開始ノードが決まっているので、getでも特定エンティティ(つまり、Datastoreの特定のノード)にアクセスが集中する。スケールしないのでは?
  2. Skip Graphだと開始ノードを分散できる。でも、Skip GraphはSkip Listを多重にしたようなものなので、順位等の付加情報をつけると更新時にその「多重」分をすべて更新しなければならなくなる。
  3. 特定エンティティにアクセスが集中した場合にスケールしないのは普通のDatastoreでも同じでは?
  4. 特定のキーではなく、ランキング(大抵は一つのkind相当)へのすべてのアクセスが特定エンティティに集中するのが問題。MemcacheをかませばMemcacheの限界までは捌けるか。
不整合について
  1. 通常のSkip Listは更新中に参照しても不整合が起こらないが(追加時は下位階層から、削除時は上位階層から順番に操作すれば全体の構造としては常に正しい)、順位等の付加情報があると上位階層と下位階層で一時的な不整合が起こる(101個のデータが格納されているのに上位階層ではサイズが100だったり)。
  2. 一時的な不整合は事実上問題ないかもしれないが、30秒ルール等で処理が打ち切られた場合は問題になる。
イテレーションについて
  1. ブロック化されたノードの結合が起こった場合、イテレーション時にブロックが消失してしまい途中からたどれなくなる可能性がある(イテレーション中のブロック内の更新は無視で良い?)。
  2. 削除は物理削除ではなく論理削除にして、cronでVACUUM的な処理で不要なエンティティを削除するという方法で対処できないか。
ブロックの分割・結合について
  1. ノードをブロック化した場合、ノードを分割したり結合したりする際に同時に上位階層のポインタの付け替えが必要になるが、これをアトミックに行うことができない。
  2. ノードをたどっている途中でこれが起こると、下位階層に進んだときに、そのブロックの中に対象のノードが存在しないケースが起こりうる。
  3. 存在しない場合は、次のブロックをたどるなどで対処できる?結合・分割の手順とからめて要検討(必ず左と結合とか)。

今後の議論についてはTwitter上の#gae_rankerで行いたいと思います。良いアイディアをお持ちの方は教えていただけると助かります。議論は適宜、ブログやTogetter等でまとめていきます。

appengine ja night #8での発表

Skip Listの実装についてappengine ja night #8にて発表させていただくことになりました。ご興味のある方はご参加下さい…と言いたいところですが、毎回のことながらappengine ja nightは大人気ですでにキャンセル待ちが68名です…。Ustreamで中継も行われるようなのでそちらをどうぞ。