お使いのブラウザは最新版ではありません。最新のブラウザでご覧ください。

CNET Japan ブログ

ランキングのつくりかた

2011/01/12 00:00
  • このエントリーをはてなブックマークに追加

遅ればせながら、あけましておめでとうございます。

先週には、ベイエリアの友人たちがやっているEchofonPostUpに買収されるなど、幸先のよい新年のスタートとなりました。

さて、最近ホットなマーケットといえばソーシャルゲームですが、ゲームといえばリーダーボード。ハイスコアのランキングで友人や見知らぬ人たちと競うのは、ビデオゲームが誕生した1970年代から欠かせない要素でした。

ところが、インターネット経由で100万人規模のプレイヤーがつながるようになってきた現在、その全体をランキングづけするのは、技術的にも大きなチャレンジとなってきました。

今回は、そのリーダーボードのつくりかたについて、ぼくらの作っているソーシャルゲーム・プラットフォームであるPankiaの運用で得られた知見を共有したいと思います。

自分の順位を知る方法

リーダーボードの基本的な考え方はシンプルで、それはつまり「ユーザが持っている最高得点を記録しておき」「それをキーとしてソートを実行する」というものです。したがって、まずは

(user_id, value)

というテーブルを用意しておき(ここでは最高得点だけを記録するので、user_idはユニークです)、このvalueにインデックスを張っておくことで、ランキング上位10人を取り出すには

SELECT * FROM scores ORDER BY value DESC LIMIT 10

とすればよいことになります。このクエリーは、ソート済みのインデックスを上から順番にたどって10件取り出すだけなので、ユーザ数が100万人になろうが1億人になろうが、ほとんど性能が劣化することがありません。

問題は、「自分の順位を知りたい」や「全体のプレイヤー数を知りたい」という要求とともに発生します。

全体のプレイヤー数については、MyISAMなら

SELECT count(*) FROM scores

を実行すればメモリ上のメタデータから瞬時に得られますが、InnoDBなどのMVCCをサポートしたデータベース(更新頻度が高いテーブルなら普通はこちらを使うと思います)の多くではテーブルのフルスキャンが発生してしまいます。

また、自分の順位を得るためには、「自分より上位のプレイヤーの数を数える」という戦略をつかえば、

SELECT count(*) + 1 AS rank FROM scores WHERE value > #{my_score}

というクエリーで得ることができるのですが、これもプレイヤー人口が増えてくると、たとえば99万位のプレイヤーが自分の順位を知るためには、99万件をスキャンする必要があり、とても重い処理になってしまいます。

これを回避するひとつの方法はcapped rankingを採用することで、たとえば「9999位以下の場合、ランク外としてしまう」というような割り切りで、スキャンする件数を1万件以内に抑えようという考え方です。こうすれば、プレイ人口が1億人になっても、上位1万人がメモリ上に乗り切るようにサイジングを行えばよいことになります。

具体的には、先のクエリーを

SELECT count(*) + 1 AS rank FROM (SELECT 1 FROM scores WHERE value > #{my_score} LIMIT 9999) as t

のように書き換えて、10000がかえってきたらランク外として扱う、ということです。

この方法はそれなりにうまく動くし、多くのサービスで採用されている方式でもあるのですが、やはり、もっと下位のユーザであっても自分の順位を知りたいということはあるでしょうし、1万位以内に入らないと自分の上達度合いがわからないというのはプレイのインセンティブを削ぐことにもなりかねません。それに、いずれにしても総プレイ人口をこのテーブルから知ることはやはり困難なままです。

出現頻度表を使った圧縮アルゴリズム

この問題に対して、何かいい方法はないものだろうかと考えていたところ、ふと気がついたことがありました。

Pankiaはプラットフォームなので多数のゲームが同居しており、またゲームごとに複数のリーダーボードを作れるので、全体としてはかなりの数のリーダーボードが存在します。

これらのデータを注意深くみてみると、その多くが、べき分布対数正規分布などに近い偏りを持っていることがわかりました。たとえば「累積プレイ回数」でランキングするようなリーダーボードでは、当然ながら全ユーザが「1」というスコア値からはじまるので、もっともユーザが集中するのが「1」というスコアで、だんだん減っていき、上位になればなるほど出現確率が下がっていく分布になります。また、スコアの値は内部的には64bit整数値で保存していますが、実際には32bitをこえるようなスコアは、ほんの数百件程度しかありませんでした。

ご存知のように、B木ベースのインデックスはキーが均等にばらけているときに最大のパフォーマンスを発揮します。つまり、インデックスの貼られているカラムがユニークであるときを最高とし(これを「カーディナリティが高い」といいます)、重複が増えれば増えるほど性能が劣化し、「男/女」や「true/false」のように2値しかとらないカラムが最悪となります。(このようなカーディナリティの低いカラムには、インデックスを張らないか、更新性能が問われないバッチ分析系のデータベースであればビットマップインデックスを使うのが基本となります)

これがなぜかというと、B木の構造をよく考えればわかると思うのですが、B木はその名のとおり深さをバランスさせようとするアルゴリズムなので、たとえば先の「累積プレイ回数」の例でいえば本来なら値が「1」のところだけがどんどん深くなるべきところ、これを一定の深さに均そうとするため、更新処理時にノードの張り替えが高い頻度で発生します。そして、せっかくコストをかけて深さを一定にしたにもかかわらず、値が「1」である範囲があまりにも広いので、結果的にはリーフノードを水平にスキャンしていく範囲も広くなり、ツリー構造の恩恵が受けられず、取得する件数が増えるにつれてインデックスとデータを行ったり来たりするランダムアクセスのコストが支配的になってきます。

ここで言ってるB木の問題を視覚化するには、高さ調整ヒストグラムをイメージしてもらうとわかりやすいと思います。オラクルなどの商用データベースでは、こういったツールが整備されているのですが、オープンソース系のデータベースでは、各種アルゴリズムとデータ構造を熟知したエンジニアの職人芸に頼る部分が大きいでしょう。

現象に偏りがあるときには、そこに圧縮や最適化の可能性がある、と考えるのがコンピュータ・サイエンスの常道です。

この「偏りがある」という情報を、なんとかうまく使えないか考えていたところ、ふと、「逆に、スコア値のほうをキーにして、同点ユーザの人数を保管するような別テーブルを作ってみたらどうなるだろう?」と思いつきました。いわゆる出現頻度表を使った圧縮アルゴリズムに近い着想です。

このテーブルを仮にcards(カーディナリティズの略)と呼ぶことにすると、つまり、あるユーザがハイスコアを更新するときには、scoresのレコードを更新するとともに、cardsでは自分が旧スコアで属していたレコードの同点ユーザ数を-1し(ゼロになれば削除)、新スコアで所属することになるレコードを+1し(レコードがなければ作成、INSERT ON DUPLICATE KEY UPDATE構文を使うのもよいでしょう)、これら全体をトランザクション化して扱うということです。

cardsテーブルの定義はこうです。score_valueにユニークインデックスを張ります。

(score_value, users_count)

そして、実際に順位を取得するには、このテーブルに対して以下のようなクエリーを発行します。

SELECT SUM(users_count) + 1 AS rank FROM cards WHERE score_value > #{my_score}

こうすることにより、更新時のコストは上がるが、たとえば「1」というスコアのユーザが最も多いなら、「1」というキーには何万人ものユーザが集中することになるので、それを1レコードとして保持できることの圧縮効果は高いと考えられます。そして、こちらのテーブルはスコアがキーとなる=ユニークになるので、B木インデックスの効果も最大化されるはずです。

というわけで、実際に約100万人が登録されているリーダーボードをいくつか対象にピックアップし、実験を行ってみました。その結果は以下のようなものでした。

scores -> cards
1,055,200 -> 754
1,095,749 -> 2,507
1,129,720 -> 7,010
1,167,610 -> 102,554
(単位:レコード件数)

どうでしょう。最も効果の高いリーダーボードでは、それまでの1/1000倍以下にまで減りました。最も効果の薄かったリーダーボードでも、約1/10という圧縮性能を示しました。

圧縮後でも10万件となってくると微妙な数字ではありますが、1万件程度なら、キャップなしでフルスキャンさせるのも全然アリの水準です。

この運用をはじめて2ヶ月ほどの実績としては、もっと規模が大きく、cardsのほうでも20万件近くになっているリーダーボードがあるのですが、それでもキャップなしで運用を続けてきて、自分の順位を知るためのクエリーに2秒以上かかることは一度もありませんでした。

一応、念のためにキャップありの運用をしたければ、

SELECT count(*) as found_rows, IFNULL(SUM(users_count), 0) + 1 AS rank FROM
(SELECT users_count FROM cards WHERE score_value > #{my_score} LIMIT 10000) as t

というような方法で、取得する行数を制限することも可能です。この場合、1万行=1万位とはならないので、found_rows=10000だった場合には、実際に計算して得られたrankをもとに有効桁数を算出し、9,999位、99,999位、999,999位といった感じでダイナミックにランキング上限をフォールバックしていくのもよいでしょう。

そして、懸念していた肝心のデータサイズ+インデックスサイズはというと、cardsはscoresの7-8%程度しかありませんでした。cardsのアプローチは、ユーザ数が増えれば増えるほど効果が出てくるものなので、逆に言うと、プレイ人数が少ないリーダーボードでは、ほとんど同点ユーザがいなくなり、単純に2つのテーブルでデータサイズが2倍になります。それを補って余りある効果が、規模の大きいリーダーボードに出ているということでしょう。このアプローチの効果は、今後ユーザ数が1000万人、1億人と増えるにつれて、より高くなっていくでしょう。Pankiaはピーク時には毎秒8,000クエリーをこえるデータベースアクセスがあるシステムなので、導入には不安もあったのですが、10%の容量増とスコア投稿時のコストを少し上乗せするだけでこれだけの効果が出たというのは、我ながらうまくいったなと思います。

基礎はアルゴリズムとデータ構造

さて、ここまでは極端に単純化したリーダーボードのモデルを使って説明してきましたが、実際にはスコアのテーブルには複数のリーダーボードが同居していたり、また期間別(オールタイム、月毎、週毎、日毎など)、地理別(国、州、市など)、ソーシャルグラフドメイン(友人内ランキング、友人の友人内ランキングなど)など、アイデア次第で様々なスコープで集計したいというニーズがありうるでしょう。また、スコアの絶対値ではなく前回プレイ時からの増分値(前回最後に遊んだ日からどれだけスコアが増えたか)で競うというのも、どのタイミングで参加したユーザであっても達成感が得られるのでよい方法かもしれません。こういったさまざまな要件にどう対処していくかという場面では、基礎的な問題設定能力が試されることになるでしょう。

昨今データベースの世界ではShardingなどの水平分散がトレンドですが、やはりコンピュータの世界で普遍的な基礎といえば「アルゴリズムとデータ構造」でしょう。水平分散のアプローチでは性能を10倍にするためには10倍のマシンが必要で、1000倍にするには1000倍のマシンが必要です。個人的な見解でいえば、これをもって「スケーラブル」と呼ぶのは、どちらかというと恥ずかしいことで、むしろ「ナイーブ」と呼びたいところです。今回の事例のように、10%のペナルティで100倍1000倍のパフォーマンスを出せてこそ、コンピュータ・サイエンスの真骨頂でしょう。

たとえば、スコアの値は内部的には64bit整数値で保持しているという話がありましたが、これも空間効率的にはかなり改善の余地があります。べき分布や対数正規分布のように、小さいほうの値の出現頻度が高い場合には、varchar(可変長文字列)ならぬvarint(可変長整数)も有効なはずです。データベースシステムでCPUがボトルネックになることはまずないので、アラインメントが崩れることのペナルティを考慮に入れても、ストレージ上でのサイズやメモリ上での表現がコンパクトになることの効果の方が大きいでしょう。

仮に、値のバイト数を表現するのに1バイト、実際の値を可変長バイトで表現するとすれば、256未満の数字は1+1=2バイトで表現できることになり、64ビット=8バイトをパディングして使う場合に比べて4倍の圧縮率になります。また64ビットをこえる突出した数字の表現も可能になり、データベース設計の初期にカラムをintにするかbigintにするかで迷うこともなくなるという別のメリットもあります。べき分布や対数正規分布が現実世界で幅広くみられる現象である以上、varintをサポートしたストレージエンジンがそろそろ登場してもよい頃ではなかろうか?という気がします。

それから、今回はMySQLなどの汎用RDBを使うことを前提に書いてきましたが、実はRedisを使えばランキング問題はいきなり解決するという裏技もあります。Redisはsorted-set型のデータをサポートしており、まさに今回のようにスコアとユーザのペアをスコアで順序づけしておくような使い方にピッタリです。これを使えば、全体の件数を取る(ZCARD)のも自分のランキングを取る(ZRANK/ZREVRANK)のも一瞬です。Redisは全データがオンメモリでないと性能が出ないので、富豪向けのソリューションではありますが、前回のポスト英語で書きなおしたところ、作者とコメント欄も含めてこのようなやりとりがあり、その議論が功を奏してか、最近ではもっぱらmmapベースのdiskstoreの開発がホットになっているようです。これが完成すれば、全てをオンメモリとする前提のサイジングを行う必要もなくなり、非常に簡単にリーダーボードを実装できるようになる可能性もあります。(同時に中途半端な役割だったVirtual Memory (VM)の機能は廃止するという意向のようです)

このように、リーダーボードひとつ作るにも、様々なアプローチが考えられるので、チャレンジしがいのある分野ではないでしょうか。

あるいは、リーダーボードをつくることがコアコンピタンスではないのなら、そこはノウハウの蓄積されているPankiaのようなクラウドサービスを使ってアウトソースし、自社は面白いゲームを作ることに集中するという方法もいいでしょう。(宣伝!)

というわけで、たまには宣伝オチも許してくださいませ。

それでは今年もよろしくお願いします!

Summer Time Love / m-flo loves 日之内エミ & Ryohei

※このエントリは CNET Japan ブロガーにより投稿されたものです。朝日インタラクティブ および CNET Japan 編集部の見解・意向を示すものではありません。
運営事務局に問題を報告

最新ブログエントリー