这个排队系统设计碉堡了

各位好，我是南哥。

我在网上看到某厂最后一道面试题：如何设计一个排队系统？

关于系统设计的问题，大家还是要多多思考，可能这道题考的不是针对架构师的职位，而是关于你的业务设计能力。如果单单只会用开源软件的API，那似乎我们的竞争力还可以再强些。学习设计东西、创作东西，把我们设计的产品给别人用，那竞争力一下子提了上来。

15岁的初中生开源了 AI 一站式 B/C 端解决方案，该产品在上个月被以几百万的价格收购了。这值得我们思考，程序创造力、设计能力在未来会变得越来越重要。

⭐⭐⭐收录在《Java学习/进阶/面试指南》：

1.1 数据结构

排队的一个特点是一个元素排在另一个元素的后面，形成条状的队列。List结构、LinkedList链表结构都可以满足排队的业务需求，但如果这是一道算法题，我们要考虑的是性能因素。

排队并不是每个人都老老实实排队，现实会有多种情况发生，例如有人退号，那属于这个人的元素要从队列中删除；特殊情况安排有人插队，那插入位置的后面那批元素都要往后挪一挪。结合这个情况用LinkedList链表结构会更加合适，相比于List，LinkedList的性能优势就是增、删的效率更优。

但我们这里做的是一个业务系统，采用LinkedList这个结构也可以，不过要接受修改、维护起来困难，后面接手程序的人难以理解。大家都知道，在实际开发我们更常用List，而不是LinkedList。

List数据结构我更倾向于把它放在Redis里，有以下好处。

（1）数据存储与应用程序拆分。放在应用程序内存里，如果程序崩溃，那整条队列数据都会丢失。

（2）性能更优。相比于数据库存储，Redis处理数据的性能更加优秀，结合排队队列排完则销毁的特点，甚至可以不存储到数据库。可以补充排队记录到数据库里。

简单用Redis命令模拟下List结构排队的处理。

# 入队列（将用户 ID 添加到队列末尾）
127.0.0.1:6379> RPUSH queue:large user1
127.0.0.1:6379> RPUSH queue:large user2

# 出队列（将队列的第一个元素出队）
127.0.0.1:6379> LPOP queue:large

# 退号（从队列中删除指定用户 ID）
127.0.0.1:6379> LREM queue:large 1 user2

# 插队（将用户 ID 插入到指定位置，假设在 user1 之前插入 user3）
127.0.0.1:6379> LINSERT queue:large BEFORE user1 user3

1.2 业务功能

先给大家看看，南哥用过的费大厨的排队系统，它是在公众号里进行排队。

我们可以看到自己现在的排队进度。

同时每过 10 号，公众号会进行推送通知；如果 10 号以内，每过 1 号会微信公众号通知用户实时排队进度。最后每过 1 号就通知挺人性化，安抚用户排队的焦急情绪。

总结下来，我们梳理下功能点。虽然上面看起来是简简单单的查看、通知，背后可能隐藏许多要实现的功能。

1.3 后台端

（1）排队开始

后台管理员创建排队活动，后端在Redis创建List类型的数据结构，分别创建大桌、中桌、小桌三条队列，同时设置没有过期时间。

// 创建排队接口
@Service
public class QueueManagementServiceImpl {

    @Autowired
    private RedisTemplate<String, String> redisTemplate;

    // queueType为桌型
    public void createQueue(String queueType) {
        String queueKey = "queue:" + queueType;
        redisTemplate.delete(queueKey); // 删除队列，保证队列重新初始化
    }
}

（2）排队操作

前面顾客用餐完成后，后台管理员点击下一号，在Redis的表现为把第一个元素从List中踢出，次数排队的总人数也减 1。

// 排队操作
@Service
public class QueueManagementServiceImpl {

    @Autowired
    private RedisTemplate<String, String> redisTemplate;

    /**
     * 将队列中的第一个用户出队
     */
    public void dequeueNextUser(String queueType) {
        String queueKey = "queue:" + queueType;
        String userId = redisTemplate.opsForList().leftPop(queueKey);
    }
}

1.4 用户端

（1）点击排队

用户点击排队，把用户标识添加到Redis队列中。

// 用户排队
@Service
public class QueueServiceImpl {

    @Autowired
    private RedisTemplate<String, String> redisTemplate;

    public void enterQueue(String queueType, String userId) {
        String queueKey = "queue:" + queueType;
        redisTemplate.opsForList().rightPush(queueKey, userId);
        log.info("用户 " + userId + " 已加入 " + queueType + " 队列");
    }
}

（2）排队进度

用户可以查看三条队列的总人数情况，直接从Redis三条队列中查询队列个数。此页面不需要实时刷新，当然可以用WebSocket实时刷新或者长轮询，但具备了后面的用户通知功能，这个不实现也不影响用户体验。

而用户的个人排队进度，则计算用户所在队列前面的元素个数。

// 查询排队进度
@Service
public class QueueServiceImpl {

    @Autowired
    private RedisTemplate<String, String> redisTemplate;

    public long getUserPositionInQueue(String queueType, String userId) {
        String queueKey = "queue:" + queueType;
        List<String> queue = redisTemplate.opsForList().range(queueKey, 0, -1);
        if (queue != null) {
            return queue.indexOf(userId);
        }
        return -1;
    }
}

（3）用户通知

当某一个顾客用餐完成后，后台管理员点击下一号。此时后续的后端逻辑应该包括用户通知。

从三个队列里取出当前用户进度是 10 的倍数的元素，微信公众号通知该用户现在是排到第几桌了。

从三个队列里取出排名前 10 的元素，微信公众号通知该用户现在的进度。

// 用户通知
@Service
public class NotificationServiceImpl {

    @Autowired
    private RedisTemplate<String, String> redisTemplate;

 private void notifyUsers(String queueType) {
        String queueKey = "queue:" + queueType;
        // 获取当前队列中的所有用户
        List<String> queueList = jedis.lrange(queueKey, 0, -1);

        // 通知排在10的倍数的用户
        for (int i = 0; i < queueList.size(); i++) {
            if ((i + 1) % 10 == 0) {
                String userId = queueList.get(i);
                sendNotification(userId, "您的排队进度是第 " + (i + 1) + " 位，请稍作准备！");
            }
        }

        // 通知前10位用户
        int notifyLimit = Math.min(10, queueList.size()); // 避免队列小于10时出错
        for (int i = 0; i < notifyLimit; i++) {
            String userId = queueList.get(i);
            sendNotification(userId, "您已经在前 10 位，准备好就餐！");
        }
    }
}

这段逻辑应该移动到前面后台端的排队操作。

1.5 存在问题

上面的业务情况，实际上排队人员不会太多，一般会比较稳定。但如果每一条队列人数激增的情况下，可以预见到会有问题了。

对于Redis的List结构，我们需要查询某一个元素的排名情况，最坏情况下需要遍历整条队列，时间复杂度是O(n)，而查询用户排名进度这个功能又是经常使用到。

对于上面情况，我们可以选择Redis另一种数据结构：Zset。有序集合类型Zset可以在O(lgn)的时间复杂度判断某元素的排名情况，使用ZRANK命令即可。

# zadd命令添加元素
127.0.0.1:6379> zadd 100run:ranking 13 mike
(integer) 1
127.0.0.1:6379> zadd 100run:ranking 12 jake
(integer) 1
127.0.0.1:6379> zadd 100run:ranking 16 tom
(integer) 1

# zrank命令查看排名
127.0.0.1:6379> zrank 100run:ranking jake
(integer) 0
127.0.0.1:6379> zrank 100run:ranking tom
(integer) 2

# zscore判断元素是否存在
127.0.0.1:6379> zscore 100run:ranking jake
"12"

我是南哥，南就南在Get到你的点赞点赞点赞。

创作不易，不妨点赞、收藏、关注支持一下，各位的支持就是我创作的最大动力❤️