【技术应用】java实现排行榜方案

• • 一、前言
  • 二、实现方案
  • • 方案一、通过数据库实现
    • 方案二、通过集合List实现数据排序功能
    • 方案三、通过redis的zset实现
    • 方案四、通过java中的sortedSet集合实现
    • 方案五、通过java的priorityQueue队列实现

一、前言

最近在做一个项目的性能优化，涉及到一个实时数据排行榜功能的性能优化，原方案涉及实时数据排行榜数据是通过实时查询数据实现的，这样实现业务逻辑比较简单，但是在数据量比较多时，sql的order by操作是比较耗费性能；

=我们这里总结几种java实现排行榜的功能，供大家参考。=

二、实现方案

方案一、通过数据库实现

账号浏览量实时更新到数据库中，用户访问人气排行榜时，通过实时查询数据库获取排行榜数据，这也是我们原有的设计方案，性能比较低，在数据量和用户量比较少时，可以考虑；

方案二、通过集合List实现数据排序功能

    List<Integer> list = new ArrayList<>();
    list.add(3);
    list.add(5);
    list.add(1);

    list.sort((o1, o2) -> o2-o1);
    System.out.println(list);

Console：

[5, 3, 1]

这种算法随着数据量越大，时间复杂度越高，同时我们也不可能每次查询一下排行榜数据都做一次排序计算，这种性能也是比较低的；如果通过定时排序实现，又会有数据延迟性能的问题；

我们常见的排序算法有10种，如下：

但是不论是哪种算法通过查询时排序的方式实现排行榜的功能是不可取的，原因同上；

方案三、通过redis的zset实现

redis有序集合和redis集合类似，是不包含 相同字符串的合集。它们的差别是，每个有序集合 的成员都关联着一个评分，这个评分用于把有序集 合中的成员按最低分到最高分排列。

使用有序集合，你可以非常快地（O(log(N))）完成添加，删除和更新元素的操作。 因为元素是在插入时就排好序的，所以很快地通过评分(score)或者 位次(position)获得一个范围的元素。 访问有序集合的中间元素同样也是非常快的，因此你可以使用有序集合作为一个没用重复成员的智能列表。 在这个列表中， 你可以轻易地访问任何你需要的东西: 有序的元素，快速的存在性测试，快速访问集合中间元素！

在项目开发中，redis的zset是常用作排行榜功能的实现方式，但是依赖于redis组件实现，在没有redis的场景下如何实现呐？

方案四、通过java中的sortedSet集合实现

sortedSet集合有redis中zset数据类型一样属性，都是有序集合；
sortedSet实现类我们使用ConcurrentSkipListSet，这个类的命名我们能看出来它实现线程安全的，这很重要，我们实现的场景中涉及到多线程并发操作；

方案流程：

我们这里的样例方案是以抖音直播排行榜为例，各个直播间访客人数是动态变化的，人气排行榜也是动态实时变化的；
账号代表直播间，浏览量代表实时访客数，排行榜就是人气榜单，我们可以取Top N；

方案描述：
1）账号是存在多个的，每个账号的浏览量也是实时变化的，每变化一次就生成一个浏览量消息推送到后台服务；
2）map集合存储账号已在sortedSet集合中存储数据的位置，以便在账号数据更新时，删除老数据，提高删除效率；
3）浏览量的排序发生在存入sortedSet时，所以获取榜单top N时，只需要变量sortedSet集合前N个元素即可，由于ConcurrentSkipListSet是线程安全的，支持多线程新增/删除/查询sortedSet集合中的数据；

代码实现：
1）用户类

import lombok.Data;
import lombok.NoArgsConstructor;

@Data
@NoArgsConstructor
@AllArgsConstructor
public class Account implements Comparable{

    private String username;
    private Integer visitedNumber;


    @Override
    public int compareTo(Object o) {
        Account account = (Account) o;
        return account.getVisitedNumber() - visitedNumber;
    }
}

2）sortedSet、map实现

package com.sk.common;

import com.sk.bean.Account;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListSet;

public class CommonTools {
    public final static SortedSet<Account> skipListSet = new ConcurrentSkipListSet<>();
    public final static Map<String,Account> setMap = new ConcurrentHashMap<>();
}

3）生产者线程

package com.sk.threads02;

import com.sk.bean.Account;
import com.sk.common.CommonTools;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Random;
import java.util.concurrent.TimeUnit;

@Data
@AllArgsConstructor
@NoArgsConstructor
public class ProducerSetThread implements Runnable{

    private String name;

    @Override
    public void run() {
        for (int i = 0; i < 100000; i++) {
            String username = name + i % 10;
            Random random = new Random();
            Integer visitedNumber = random.nextInt(30);
            Account account_old = CommonTools.setMap.get(username);
            Account account_new = new Account(username, visitedNumber);
            if (null != account_old) {
                if (!account_new.equals(account_old)) {
                    CommonTools.skipListSet.add(account_new);
                    CommonTools.setMap.put(username, account_new);
                    CommonTools.skipListSet.remove(account_old);
                }
            } else {
                CommonTools.skipListSet.add(account_new);
                CommonTools.setMap.put(username, account_new);
            }
            try {
                TimeUnit.MILLISECONDS.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

4）消费者线程

package com.sk.threads02;

import com.sk.bean.Account;
import com.sk.common.CommonTools;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Iterator;
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.TimeUnit;

@Data
@AllArgsConstructor
@NoArgsConstructor
public class CustomerSetThread implements Runnable {

    private Integer topN;

    @Override
    public void run() {
        while (true) {
            int topNN = topN;
            int size = CommonTools.skipListSet.size();
            if(size < topNN){
                topNN = size;
            }
            Iterator<Account> iterator = CommonTools.skipListSet.iterator();
            for (int i = 0; i < topNN; i++) {
                System.out.println(i + 1 + "========" + iterator.next());
            }

            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            System.out.println("--------------------------------------------------------");

        }
    }
}

5）初始化类

package com.sk.test;

import com.sk.threads02.CustomerSetThread;
import com.sk.threads02.ProducerSetThread;

public class Test02 {

    public static void main(String[] args) {

        //消费者
        new Thread(new CustomerSetThread(5)).start();
        //生产者A
        new Thread(new ProducerSetThread("张三")).start();
        //生产者B
        new Thread(new ProducerSetThread("李四")).start();
    }

}

6）执行结果

--------------------------------------------------------
1========Account(username=张三1, visitedNumber=26)
2========Account(username=李四2, visitedNumber=24)
3========Account(username=李四6, visitedNumber=20)
4========Account(username=李四3, visitedNumber=17)
5========Account(username=张三2, visitedNumber=16)
--------------------------------------------------------
1========Account(username=李四6, visitedNumber=29)
2========Account(username=李四0, visitedNumber=28)
3========Account(username=张三0, visitedNumber=22)
4========Account(username=李四2, visitedNumber=21)
5========Account(username=李四4, visitedNumber=18)
--------------------------------------------------------

但是，sortedSet集合实现排行榜有一个问题，那就是浏览量visitedNumber不能重复，因为集合sortedSet中数据是不可重复的，排序的属性也是不能重复的；我们知道浏览量是可能存在重复，那这种情况应该怎么办？

方案五、通过java的priorityQueue队列实现

PriorityQueue（优先队列） 采用的是堆排序，实际上是一个堆（不指定Comparator时默认为最小堆）
队列既可以根据元素的自然顺序来排序，也可以根据 Comparator来设置排序规则。队列的头是按指定排序方式的最小元素。如果多个元素都是最小值，则头是其中一个元素。新建对象的时候可以指定一个初始容量，其容量会自动增加。

同样，出于线程安全考虑，我们使用线程安全的实现类：PriorityBlockingQueue

PriorityBlockingQueue是一个无界的基于数组的优先级阻塞队列，数组的默认长度是11，也可以指定数组的长度，且可以无限的扩充，直到资源消耗尽为止，每次出队都返回优先级别最高的或者最低的元素。默认情况下元素采用自然顺序升序排序，当然我们也可以通过构造函数来指定Comparator来对元素进行排序。需要注意的是PriorityBlockingQueue不能保证同优先级元素的顺序。

方案流程：

方案描述：

1）方案流程与方案四项目节点方案描述同上；
2）sortedSet集合修改为了PriorityBlockingQueue优先队列，排序结合中可以存在相同浏览量的元素；
3）客户端访问排行榜时从队列queue中copy一份实时数据，取Top N，并不会影响原queue数据；
4）也可以只保留一个服务数据，定时从元queue中copy数据；
5）主queue队列，可以只存top N的数据，新数据在插入queue之前，先和队列queue中最小值比较，如果小于最小值，则不入队列，反之存入队列，删除最小值；这样能够节省内存空间；（注：流程图中没有体现，供大家参考）；

代码实现：
1）priorityQueue、map实现

package com.sk.common;

import com.sk.bean.Account;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListSet;

public class CommonTools {
    public final static PriorityBlockingQueue<Account> priorityQueue = new PriorityBlockingQueue<>();
    public final static Map<String,Account> setMap = new ConcurrentHashMap<>();
}

2）生产者

package com.sk.threads;

import com.sk.bean.Account;
import com.sk.common.CommonTools;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Random;
import java.util.concurrent.TimeUnit;

@Data
@AllArgsConstructor
@NoArgsConstructor
public class ProducerThread implements Runnable{

    private String name;

    @Override
    public void run() {
        for (int i = 0; i < 100000; i++) {
            String username = name + i % 10;
            Random random = new Random();
            Integer visitedNumber = random.nextInt(30);
            Account account_old = CommonTools.map.get(username);
            Account account_new = new Account(username, visitedNumber);
            if (null != account_old) {
                if (!account_new.equals(account_old)) {
                    CommonTools.priorityQueue.add(account_new);
                    CommonTools.map.put(username, account_new);
                    CommonTools.priorityQueue.remove(account_old);
                }
            } else {
                CommonTools.priorityQueue.add(account_new);
                CommonTools.map.put(username, account_new);
            }
            try {
                TimeUnit.MILLISECONDS.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

3）消费者

package com.sk.threads;

import com.sk.bean.Account;
import com.sk.common.CommonTools;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.TimeUnit;

@Data
@AllArgsConstructor
@NoArgsConstructor
public class CustomerThread implements Runnable {

    private Integer topN;

    @Override
    public void run() {
        while (true) {

            PriorityBlockingQueue<Account> queueTemp = new PriorityBlockingQueue<>();
            queueTemp.addAll(CommonTools.priorityQueue);
            int topNN = topN;
            int queueSize = queueTemp.size();
            if (queueSize < topNN) {
                topNN = queueSize;
            }
            System.out.println("+++++++++++++++++++++++++++++TOP ONE " + queueTemp.peek());
            for (int i = 0; i < topNN; i++) {
                System.out.println(i + 1 + "========" + queueTemp.remove());
            }

            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            System.out.println("--------------------------------------------------------");

        }
    }
}

4）初始化类

package com.sk.test;

import com.sk.threads.CustomerThread;
import com.sk.threads.ProducerThread;

public class Test {

    public static void main(String[] args) {

        //消费者
        new Thread(new CustomerThread(5)).start();

        //生产者A
        new Thread(new ProducerThread("张三")).start();
        //生产者B
        new Thread(new ProducerThread("李四")).start();

    }


}

5）执行结果

+++++++++++++++++++++++++++++TOP ONE Account(username=李四6, visitedNumber=24)
1========Account(username=李四6, visitedNumber=24)
2========Account(username=张三8, visitedNumber=22)
3========Account(username=张三2, visitedNumber=22)
4========Account(username=张三5, visitedNumber=22)
5========Account(username=张三0, visitedNumber=17)
--------------------------------------------------------
+++++++++++++++++++++++++++++TOP ONE Account(username=张三2, visitedNumber=28)
1========Account(username=张三2, visitedNumber=28)
2========Account(username=张三4, visitedNumber=26)
3========Account(username=李四6, visitedNumber=25)
4========Account(username=张三6, visitedNumber=24)
5========Account(username=张三7, visitedNumber=24)
--------------------------------------------------------

=注：如果大家有更好的实现方案，可以在评论区分享==========