TairZsetを使用して分散リーダーボードを実装する - Tair (Redis® OSS-Compatible)

TairZsetは、Alibaba Cloudによって開発されたデータ構造です。 DOUBLE型のスコアデータを256のディメンションに対してソートできます。社内で開発されたTairベースのクライアントを使用して、コンピューティングタスクを複数のキーに分散できる分散リーダーボード (サブリーダーボードとも呼ばれます) を実装できます。たとえば、10個のキーを指定した場合、データは10個のキーに分散されて計算されます。

背景情報

正確なランキングおよび不正確なランキング (線形補間とも呼ばれる) 方法を使用して、分散リーダーボードを実装できます。

表 1. 分散リーダーボードの実装方法

移動方法

説明

正確なランキング (推奨)

この方法では、コンピューティングのためにデータを複数のキーに分散し、複数のキーで同じメンバーのランクをクエリして、メンバーの合計ランクを取得できます。

たとえば、3つのキーを指定し、3,000のメンバーを含むリーダーボードを作成した場合、Tairはこれらのメンバーを3つのキー (またはサブリーダーボード) に配布します。データ照会中、FindRank(x) コマンドを使用して、3つのキーからxメンバーの3つのランクを取得します。検索されたランクが124、183、および156であると仮定する。この場合、xメンバーの実際のランクは463であり、これは124、183、および156の合計である。

利点: この方法は正確なランクをもたらします。
欠点: 時間の複雑さこの方法は、m * O(log(N)) である。

線形補間 (現在は利用できません)

この方法では、メンバースコアによってメンバーをさまざまな範囲に分類し、メンバー数と各範囲の最高ランクを記録してから、線形補間を使用してスコアが各範囲の最大値と最小値の間にあるメンバーのランクを推定できます。

利点: この方法は、ランク検索において高速であり、O(m) の時間複雑度を有する。
欠点: このメソッドは、実際のランクとは異なる可能性がある推定ランクを取得します。

このトピックでは、正確なランキングを使用して分散リーダーボードを実装する方法について説明します。

説明

このトピックで使用されるTairZsetコマンドの詳細については、「exZset」をご参照ください。

前提条件

Alibaba Cloudによって開発されたTairベースのクライアントが使用されます。詳細については、alibabacloud-tairjedis-sdkをご覧ください。

分散リーダーボードの実装

次の表は、一般的なリーダーボードと分散リーダーボードの基本機能を実装する方法を比較しています。

基本機能	共通リーダーボード		分散リーダーボード
基本機能	実装方法	時間の複雑さ	実装方法	時間の複雑さ
メンバーの挿入	EXZADDコマンドを実行します。	O (ログ (N))	`crc(key) & m`構文を使用して、メンバーを挿入するキーを指定し、EXZADDコマンドを実行してメンバーをキーに挿入します。	O (ログ (N))
メンバーのスコアの更新	EXZINCRBYコマンドを実行します。	O (ログ (N))	`crc(key) & m`構文を使用して、メンバースコアを更新するキーを指定し、EXZINCRBYコマンドを実行してキー内のメンバーのスコアを更新します。	O (ログ (N))
メンバーの削除	EXZREMコマンドを実行します。	O(M * ログ (N))	`crc(key) & m`構文を使用して、メンバーを削除するキーを指定し、EXZREMコマンドを実行してキーからメンバーを削除します。	O (ログ (N))
キー内のメンバー数のクエリ	EXZCARDコマンドを実行します。	O(1)	EXZCARDコマンドを数回実行して、複数のキーのメンバーの数を個別に照会し、その数を追加して合計数を取得します。	O(m) 説明この列では、mはシャードの数を示します。
総ページ数のクエリ	EXZCARDコマンドを実行して、キー内のメンバーの数を照会し、その数を各ページに表示できるエントリの数で割ります。	O(1)	EXZCARDコマンドを数回実行して、複数のキーのメンバー数を個別に照会し、番号を追加して合計番号を取得します。次に、合計数を各ページに表示できるエントリの数で割ります。	O(m)
スコアが特定の範囲内にあるメンバーの総数のクエリ	EXZCOUNTコマンドを実行します。	O (ログ (N))	EXZCOUNTコマンドを数回実行して、複数のキーでスコアが特定の範囲内にあるメンバーの数を個別に照会し、その数を追加して合計数を取得します。	m * O (ログ (N))
スコアが特定の範囲内にあるメンバーの削除	EXZREMRANGEBYSCOREコマンドを実行します。	O (ログ (N)+ M)	EXZREMRANGEBYSCOREコマンドを数回実行して、スコアが特定の範囲内にあるメンバーを複数のキーから個別に削除します。	m * O (ログ (N))
メンバースコアの取得	EXZSCOREコマンドを実行します。	O(1)	`crc(key) & m`構文を使用してメンバースコアを取得するキーを指定し、EXZSCORコマンドを実行してキー内のメンバーのスコアを取得します。	O(1)
メンバーランクの取得	EXZRANKコマンドを実行します。	O (ログ (N))	EXZRANKBYSCOREコマンドを実行して、複数のキーで同じメンバーのランクを個別に取得し、ランクを追加してメンバーの合計ランクを取得します。	m * O (ログ (N))
メンバーのスコアとランクの取得	EXZSCOREコマンドとEXZRANKコマンドを実行します。	O (ログ (N))	`crc(key) & m`構文を使用して、メンバーのスコアとランクを取得するキーを指定し、EXZSCOREコマンドを実行してキー内のメンバーのスコアとランクを取得します。 EXZRANKBYSCOREコマンドを実行して、複数のキーで同じメンバーのランクを個別に取得し、ランクを追加してメンバーの合計ランクを取得します。	m * O (ログ (N))
上位iメンバーの照会	EXZRANGEコマンドを実行します。	O (ログ (N)+ M)	EXZRANGEコマンドを数回実行して、複数のキーから上位iメンバーを個別に取得し、取得したすべてのメンバーの中から上位iメンバーを取得します。	m * O (ログ (N))
リーダーボードの上位iページのクエリ	EXZRANGEコマンドを実行します。	O (ログ (N))	各サブリーダーボードのi番目のページの前に表示されているメンバーを取得し、すべてのサブリーダーボードの取得されたメンバーをランク付けしてから、取得されたすべてのメンバーの上位iページの合計を取得します。	m * O (ログ (N))
有効期限の設定	EXPIREコマンドを実行します。	O(1)	各メンバーの有効期限を指定します。	O(m)
リーダーボードの削除	DELコマンドを実行します。	O(N)	キーからすべてのメンバーを削除します。	m * O(N)

サンプルコード：

public class DistributedLeaderBoradExample {
    private static final int shardKeySize = 10;  // Number of sub-leaderboards.
    private static final int pageSize = 10;      // Number of entries that can be displayed on each page in a leaderboard.
    private static final boolean reverse = true; // In this example, members are ranked in descending order.
    private static final boolean useZeroIndexForRank = false; // In this example, ranks start from 1.

    public static void main(String[] args) {
        JedisPool jedisPool = new JedisPool();
        // Create a distributed leaderboard.
        DistributedLeaderBoard dlb = new DistributedLeaderBoard("distributed_leaderboard", jedisPool,
            shardKeySize, pageSize, reverse, useZeroIndexForRank);

        // Rank the participants by the number of their gold medals. If the number of gold medals is the same, rank the participants by the number of their silver medals. If the number of silver medals is also the same, rank the participants by the number of their bronze medals.
        //                    Gold medal Silver medal Bronze medal
        dlb.addMember("A",     32,  21, 16);
        dlb.addMember("D",     14,  4,  16);
        dlb.addMember("C",     20,  7,  12);
        dlb.addMember("B",     25,  29, 21);
        dlb.addMember("E",     13,  21, 18);
        dlb.addMember("F",     13,  17,  14);

        // Retrieve the rank of Participant A.
        dlb.rankFor("A"); // 1
        System.out.println(dlb.rankFor("A"));

        // Retrieve the top 3 participants.
        dlb.top(3);
        System.out.println(dlb.top(3));
        // [{"member":"A","score":"32#21#16","rank":1},
        // {"member":"B","score":"25#29#21","rank":2},
        // {"member":"C","score":"20#7#12","rank":3}]
    }

下表に、各パラメーターを説明します。

パラメーター	データ型	説明
shardKeySize	int	サブリーダーボードの数。デフォルト値は 10 です。サブリーダーボードの数を動的にスケーリングすることはできません。使用する前に、必要なサブリーダーボードの正確な数を決定する必要があります。
pageSize	int	リーダーボードの各ページに表示できるエントリの数。デフォルト値は 10 です。
リバース	Boolean	有効な値： false: メンバーは昇順でランク付けされます。デフォルト値です。 true: メンバーは降順でランク付けされます。
useZeroIndexForRank	Boolean	有効な値： true: ランクは0から始まります。デフォルト値です。 false: ランクは1から始まります。