リーダーボードが解決する主な問題はランキングです。そして、17位から32位にはどの選手がいるのか？私の近くには誰がいるのか？最初は、これは単純な概念で、ある種の高速インメモリ・ストアのソートされたセットを使って簡単に解決できるように思えます。最近、顧客のソリューションのために調査している間に、リーダーボードはもっと複雑になり得ることを知りました。この記事では、リーダーボードを実際に構築する方法と、Momentoがリーダーボード開発者にとってより簡単なものであることを示す将来の記事の前触れとして、私が学んだことのいくつかを共有しようと思います。

スコアの変動は、ランク間で一括して変化する

ランキングの1つの課題は、1回のスコアの変更が、大規模な選手のサブセットの順位を変更することを意味することです。DynamoDBのような完全にマテリアライズされたデータベースでは、これは多くのコストのかかる書き込みを意味し、すべての変更を永続化するには時間がかかります。そのため、指定された選手のスコアのランクは、それが要求されたときに決定する方が良さそうです。

スコアの順位を決める

ある選手の順位を見つけるには、一般的に、すべての選手の得点を数字順（通常は降順）にソートして保存する。そして、プレーヤーが見つかるまで得点をスキャンして数える。また、スコアエントリーの総数がわかっている場合は、バイナリサーチを使うこともできます：

1.ソートされたスコアの範囲の真ん中のエントリーを教えてください。はい？これで順位がわかります。いいえ？2.に進んでください。
2.私の選手のスコアが真ん中より高ければ上半分に、私の選手のスコアが真ん中より低ければ下半分になるように範囲を調整してください。範囲を狭めて1に戻ります。

スコア数が多い場合、この方法はスキャンしてカウントする方法よりもはるかに速く順位を求めることに収束することがわかります。得点数が多ければ多いほど、この操作にかかる時間は長くなりますが、それは直線的に増加するのではなく、対数的に増加します。

ここまで説明したリーダーボードの機能があなたの要件に合っていれば、問題は解決です！Momento Cacheのソートセットコレクションを使用してプレーヤーのスコアを保存し、SortedSetGetRankとSortedSetFetchByRank APIを使用してプレーヤーのランキング情報を取得するだけです。ソートされたセットを使ったさまざまな得点アプローチについては、以前のブログで詳しく説明しています。しかし…難点が潜んでいるかもしれません。リーダーボーダーの皆さん、読んでみてください。

序列順位 対 競争順位

ソートされた集合を使用して順位をライブで決定するための上記のテクニックは、ランキングの種類に依存します。ランキングの方法が「順序」である場合にのみ機能します – 今日の Momento Cache のソートされたセットの場合です。以下は序数ランキングの例です。

残念ながら、序列ランキングは多くのリーダーボードシナリオにとって望ましい経験ではありません。上の例では、ChrisとDanielaはともに253点を獲得していますが、ランキングは異なっています。ゲーマーのダニエラは名前をAAAに変えることを考えるかもしれません！競技ランキングでは、クリスとダニエラはともに4位、カークは6位となります。

特定の選手のコンペティションランクはどのようにして決まるのでしょうか？それは複数のステップを踏む必要があります：

1.SortedSetGetScoreで選手のスコアを取得。
2.SortedSetFetchByScore (降順でカウント1)：同じスコアを持つ最初のプレーヤーを検索します。
3.SortedSetGetRank で、同じスコアを持つ最初のプレーヤーの序列を取得します。これは、私たちが実際に興味を持っている選手の順位でもあります。完了！

しかし……大会ランキングや「大会ランクによるトップ10」のような情報で近くにいる選手を見つけるのは、解決するのが難しい問題です。「スコア」は上記の手順で決定された競技ランキングです。

ランキングの定期的な具体化

スコアが1つ変わるだけで、コンペティションの順位が何度も変わる可能性があるため、スコアが変わるたびにコンペティションの順位をソートしたセット全体を作り直す必要があります。これは耐えられません。この要件を大規模に解決するには、競技ランキングの多少の停滞を受け入れる必要がありそうです。定期的に（おそらく10分に1回程度、新しいスコアが出た場合のみ）、競技ランキングのソートセットを再構築します。

基本的なパターンは、ライブスコアのソートセットから全選手とスコアを取得し、各選手の競技順位を決定し、これを競技順位を「スコア」として新しいソートセットに書き込むことです。最初の選手については、その順位が1であることが分かっているので、すぐに順位ソートセットに書き込めば問題ありません。次の選手（それに続く各選手）については、得点ソートセットの直前の選手と得点を比較し、同じ得点であれば同じ順位を再利用しますが、異なる場合は得点ソートセットの選手の順位を順位ソートセットの順位として使用します。アプリケーションのコードが最初にこれをチェックし、競技ランキングの最新ビューを見るために、どのソートセットが正しいかを知るのです。念のため、いくつかの異なるバージョンを残しておくこともできますが、古いビューはしばらくするとTTLの期限切れで削除されてしまいます。

結論

コンペティション・ランキングを作りたい場合、リーダーボードの課題を解決するのは難しいかもしれませんが、コンペティション・ランキングのプレイヤーに対する範囲クエリの一貫性をある程度受け入れることを厭わなければ、それは可能です。この記事で紹介したパターンを使って、Momento Cacheのソートセットでコンペティション・ランキングを作成した方は、ぜひその経験を聞かせてください。次の記事では、Momentoとその最新機能を使って、このソリューションをどのように構築したかを紹介します。それまでは、Momentoがゲーム開発者を支援するために行っていることをチェックしてみてください。それではまた次回！

@pj_naylor までツイートください。また連絡はLinkedIn、メールはsupport@momentohq.comまで。Discordでチャットすることもできます。

ピート・ネイラー

著者

Runs a consulting business called High Bar Solutions. Previously worked as a Solution Architect for Momento and spent 6 years working with DynamoDB at AWS—plus “lots” of years accumulated in old-school environments which are better forgotten these days. Firmly believes that giving software developers the tools to innovate faster will move the world in a positive direction. Always seeking to embed within groups of smart people and act like a sponge. Likes disconnected breaks in the wilderness from time to time. Beware: may talk for hours about distributed systems, correctness and scale in a transactional database context.