大量ユーザーポイントのランキングアルゴリズムに関する議論

質問

多数のユーザーがいるウェブサイトでは、ユーザーにポイントがあり、使用中にいつでも更新される可能性があります。ここで、ユーザーがログインするたびに現在のスコアランキングを表示するこの Web サイトのアルゴリズムを設計する必要があります。ユーザーの最大数は 2 億人です。ポイントは負でない整数で、100 万未満です。

追記：これはXunleiからのインタビューの質問と言われていますが、質問自体は非常に現実的であるため、この記事ではインタビューの質問の理想的な環境に限定するのではなく、実際のシナリオに応じて検討するつもりです。

ストレージ構造

まず、ユーザー スコア テーブル user_score を使用して、ユーザーのスコア情報を保存します。

テーブル構造:

サンプルデータ:

次のアルゴリズムは、この基本的なテーブル構造に基づいています。

アルゴリズム 1: 単純な SQL クエリ

まず、単純な SQL ステートメントを使用して、ユーザーのポイントよりも大きいポイントを持つユーザーの数を照会することが簡単に考えられます。

ランクとして 1 + count(t2.uid) を選択
user_score t1、user_score t2から
ここで、t1.uid = @uid かつ t2.score > t1.score

ユーザー 4 の場合、次の結果が得られます。

アルゴリズムの特徴

利点: シンプルで、SQL 機能を活用し、複雑なクエリ ロジックを必要とせず、追加のストレージ構造を導入しません。小規模アプリケーションやパフォーマンス要件が低いアプリケーションに適したソリューションです。

デメリット: user_score テーブルを完全にスキャンする必要があります。また、クエリ中にスコアの更新があった場合、テーブルがロックされることも考慮する必要があります。データ規模が大きく、同時実行性が高いアプリケーションでは、パフォーマンスは許容できません。

アルゴリズム2: 均一パーティション設計

多くのアプリケーションでは、キャッシュはパフォーマンスの問題を解決する重要な方法です。Memcached を使用してユーザー ランキングをキャッシュできるかどうかは当然疑問です。しかし、よく考えてみると、ユーザーランキングはグローバルな統計指標であり、ユーザーの個人的な属性ではないため、キャッシュはあまり役に立たないことがわかりました。他のユーザーのポイントの変化は、このユーザーのランキングにすぐに影響を与える可能性があります。しかし、実際のアプリケーションでは、ポイントの変化は実際には特定のルールに従います。通常、ユーザーのポイントは突然増加または減少しません。一般的に、ユーザーは低いパーティションに長時間留まり、ゆっくりと高いパーティションに上昇する必要があります。つまり、ユーザーポイントの分布は一般的にセグメント化されています。さらに、高いパーティションのユーザーのポイントのわずかな変化は、実際には低いセグメントのユーザーのランキングにほとんど影響を与えないことに気付きました。したがって、積分セグメントごとに統計を実行し、パーティション積分テーブル score_range を導入する方法が考えられます。

テーブル構造:

データ例:

[from_score、to_score) の範囲内に count 人のユーザーが存在することを示します。スコアを1000ポイントの間隔に分割すると、1000の間隔が存在します：[0、1000)、[1000、2000)、…、[999000、1000000)。将来的にユーザーのポイントを更新するときは、score_rangeテーブルの間隔値をそれに応じて更新する必要があります。パーティション スコア テーブルを使用してスコア s のユーザーのランキングを照会するには、まずユーザーが属する間隔を決定し、スコア s より高いスコア間隔のカウント値を累積してから、この間隔でのユーザーのランキングを照会します。2 つの値を加算して、ユーザーのランキングを取得します。

一見すると、この方法は間隔集計によってクエリ計算の量を削減するように見えますが、実際にはそうではありません。次の質問は、この範囲内でユーザーのランキングを照会するにはどうすればよいでしょうか?アルゴリズム 1 の SQL に積分条件が追加された場合:

ランクとして 1 + count(t2.uid) を選択
user_score t1、user_score t2から
ここで、t1.uid = @uid かつ t2.score > t1.score かつ t2.score < @to_score

理想的には、t2.score の範囲は 1000 に制限されているため、スコア フィールドにインデックスが付けられている場合、この SQL ステートメントによって、インデックスを通じて user_score テーブルでスキャンされる行数が大幅に削減されることが期待されます。しかし、実際の状況はそうではありません。t2.score の範囲は 1000 以内ですが、この範囲内のユーザー数も 1000 であることを意味するわけではありません。ポイントが同じになる状況もあるからです。 80/20 ルールによれば、低パーティションの上位 20% にユーザーの 80% が集中することがよくあります。つまり、多数の低パーティション ユーザーに対する間隔ランキング クエリのパフォーマンスは、少数の高パーティション ユーザーに対するパフォーマンスよりもはるかに劣ります。したがって、通常の状況では、このパーティション分割方法では大幅なパフォーマンスの向上は得られません。

アルゴリズムの特徴

利点: 積分区間の存在を認識し、事前集計によってクエリのテーブル全体のスキャンを排除します。

欠点: 積分の不均一な分布により、パフォーマンスの改善が不十分になります。

アルゴリズム3: ツリー分割設計

均一パーティション クエリ アルゴリズムの失敗は、ポイントの不均一な分布が原因であるため、80/20 ルールに従って score_range テーブルを不均一な間隔として設計できるかどうかが自然に疑問になります。たとえば、低いポイントをより密に分割し、各間隔に 10 ポイントずつ分割し、徐々に 100 ポイント、1000 ポイント、10,000 ポイントと増やしていきます。もちろん、これは 1 つの方法ですが、やや恣意的で把握しにくいものです。さらに、システム全体の積分分布は使用とともに徐々に変化し、当初のより適切な分割方法が将来の状況には適さなくなる可能性があります。私たちは、積分の不均一性とシステムの積分分布の変化の両方に適応できる分割方法、つまりツリー分割を見つけたいと考えています。

第 1 レベルの間隔として [0, 1,000,000) を取り、第 1 レベルの間隔を 2 つの第 2 レベルの間隔 [0, 500,000)、[500,000, 1,000,000) に分割し、さらに第 2 レベルの間隔を 4 つの第 3 レベルの間隔 [0, 250,000)、[250,000, 500,000)、[500,000, 750,000)、[750,000, 1,000,000) に分割します。最終的には、1,000,000 個の 21 レベルの間隔 [0,1)、[1,2) … [999,999, 1,000,000) が得られます。これは実際に、間隔をバランスのとれたバイナリ ツリー構造に編成します。ルート ノードは第 1 レベルの間隔を表し、各非リーフ ノードには 2 つの子ノードがあり、左の子ノードは低スコア間隔を表し、右の子ノードは高スコア間隔を表します。ツリー パーティション構造は、更新時に不変条件を維持する必要があります。つまり、非リーフ ノードのカウント値は、常にその左側と右側の子ノードのカウント値の合計に等しくなります。

今後、ユーザーのポイントが変化するたびに更新する必要がある間隔の数は、ポイントの変化量に関係します。ポイントの変化が小さいほど、更新される間隔のレベルは低くなります。一般的に、毎回更新する必要がある間隔の数は、ユーザーの積分変数の log(n) レベルです。つまり、ユーザーの積分が一度に *** ずつ変化する場合は、更新間隔の数は 20 レベルになります。このツリー型の分割されたスコア テーブルを使用して、スコア s を持つユーザーのランキングを照会することは、実際には、間隔ツリー上で s の位置を上から下へ、粗いものから細かいものへと段階的に明らかにするプロセスです。たとえば、スコアが 499,000 の場合、累積には初期値 0 のランキング変数を使用します。まず、レベル 1 間隔の左サブツリー [0、500,000) に属しているため、ユーザー ランキングはユーザー カウントの右サブツリー [500,000、1,000,000) にあるはずで、カウント値をユーザー ランキング変数に累積して次のレベル間隔に入ります。次に、レベル 3 間隔 [250,000、500,000) に属しています。これはレベル 2 間隔の右サブツリーであるため、カウントをランキング変数に累積して次のレベル間隔に直接入る必要はありません。また、レベル 4 間隔に属しています...。最終的に、ユーザー スコアをレベル 21 間隔 [499,000、499,001) に正確に配置することで、累積プロセス全体が完了し、ランキングが得られます。

このアルゴリズムの更新とクエリには複数の操作が含まれますが、間隔の from_score と to_score にインデックスを作成すると、これらの操作はすべてキーベースのクエリと更新となり、テーブルスキャンは生成されないため、効率が高くなります。さらに、このアルゴリズムはリレーショナル データ モデルや SQL 操作に依存せず、NoSQL などの他のストレージ方法に簡単に変換できます。キーベースの操作では、キャッシュ メカニズムを簡単に導入して、パフォーマンスをさらに最適化することもできます。さらに、ツリー間隔の数はおよそ 2 億と見積もることができます。各ノードのサイズを考慮すると、全体の構造は数十 M のスペースしか占めません。したがって、メモリ内に区間ツリー構造を完全に構築し、user_score テーブルを通じて O(n) 時間で区間ツリーを初期化し、ランキング クエリと更新操作をメモリ内で実行できます。一般的に、同じアルゴリズムの場合、データベースからメモリ内アルゴリズムへのパフォーマンスの向上は 10^5 以上になることが多く、したがって、このアルゴリズムは非常に高いパフォーマンスを実現できます。

アルゴリズムの特徴

利点: 構造が安定しており、積分分布の影響を受けません。各クエリまたは更新の複雑さは積分最大値の O(log(n)) レベルであり、ユーザー規模に依存せず、大規模に対応できます。SQL に依存せず、NoSQL またはインメモリ データ構造に簡単に変換できます。

デメリット: アルゴリズムが比較的複雑です。

アルゴリズム4: ポイントランキング配列

アルゴリズム 3 はパフォーマンスが高く、積分変更の複雑度は O(log(n)) に達しますが、実装が比較的複雑です。さらに、O(log(n)) の複雑さは、n が非常に大きい場合にのみその利点を発揮します。実際のアプリケーションでは、積分の変化はそれほど大きくないことがよくあります。このとき、O(n) アルゴリズムと比較して明らかな利点がないことが多く、速度が遅くなることもあります。

これを考慮して、ポイントの変化がランキングに及ぼす具体的な影響を注意深く観察すると、ユーザーのポイントが s から s+n に変化しても、ポイントが s 未満または s+n 以上の他のユーザーのランキングは実際には影響を受けないことがわかります。ポイントが [s, s+n) の範囲内にあるユーザーのランキングのみが 1 位下がります。ポイントとランキングの対応を表すために、サイズが 100,000,000 の配列を使用できます。ここで、rank[s] はポイント s に対応するランクを表します。初期化中に、ランク配列は O(n) の複雑さで user_score テーブルから計算できます。ユーザーランキングのクエリと更新はこの配列に基づいています。スコア s に対応するランキングを照会するには、rank[s] を返すだけで、複雑さは O(1) です。ユーザーのスコアが s から s+n に変わると、rank[s] から rank[s+n-1] までの n 要素の値を 1 増やすだけで済みます。複雑さは O(n) です。

アルゴリズムの特徴

利点: スコアランキング配列は間隔ツリーよりも単純で実装が簡単です。ランキングクエリの複雑さは O(1) です。ランキング更新の複雑さは O(n) であり、スコアがあまり変化しない場合には非常に効率的です。

デメリット: n が大きい場合、多数の要素を更新する必要があり、効率はアルゴリズム 3 ほど良くありません。

要約する

上記では、ユーザー ポイントをランク付けするアルゴリズムをいくつか紹介しました。アルゴリズム 1 はシンプルで、理解しやすく実装も容易で、小規模で同時実行性の低いアプリケーションに適しています。アルゴリズム 3 では、より複雑なツリー分割構造が導入されていますが、その O(log(n)) の複雑さは優れたパフォーマンスを発揮し、大規模で同時実行性の高いアプリケーションに適用できます。アルゴリズム 4 では、実装が容易で、ポイントがあまり変化しない場合はアルゴリズム 3 と同等のパフォーマンスを発揮するシンプルなランキング配列を使用します。これは未解決の問題です。他にも優れたアルゴリズムやソリューションがあるはずです。ぜひ議論してください。

オリジナルリンク: http://www.cnblogs.com/weidagang2046/archive/2012/03/01/massive-user-ranking.html

【編集者のおすすめ】

1. Java開発の効率化に役立つ5つのツールを推奨
2. 優れた開発者が備えるべき4つの資質
3. ソフトウェア開発の基本原則 - *** プロジェクト
4. Node.js 開発者を採用するための 6 つのヒント
5. ソフトウェア開発は大工がテーブルを作るようなものだ