阿里面试中遇到的一些架构问题

以你之姓@ 2022-04-24 12:46 244阅读 0赞

Java高级互联网架构 2019-04-23 22:11:05

一位网友之前面试淘点点的时候被问倒得一个问题至今牵挂，工作两年，由于工作环境的限制，没能接触到一些大数据量的并发工作，也没能有机遇参与复杂系统的设计，而学习复杂或高并发系统的唯一途径就是阅读源码，惭愧的是，至今也只阅读了Tomcat的部分源码，于是他在oschina上贴出问题与互联网猿一同分析。

> http://www.oschina.net/question/926166\_2137672

问题描述：让您做一个电商平台，您如何设置一个在买家下订单后的”第60秒“发短信通知卖家发货，您需要考虑的是像淘宝一样的大并发量的订单。

1、具有排序功能的队列

2、Redis+定时器

**思路 1**

原理：第一种思路是延迟队列实现的原理，其就是一个按时间排好序的队列，每次put的时候排序，然后take的时候就计算时间是否过期，如果过期则返回队列第一个元素，否则当前线程阻塞X秒，这个也是JDK 自带 **DelayQueue** 的思路。

**思路 2**

原理：第二种思路（来自java架构沉思录）需要利用**Redis的有序集合Sorted Set，**说到使用 Redis 就不得不考虑Score的设计，因为它直接决定你代码的复杂度，通过精确到秒的时间做Score（去掉毫秒），然后使用线程每一秒扫一次，使用当前时间作为zrangeBysocre命令的Score去查询。

业务场景：按京东一天500万的成交量，一天主要成交时间为8小时，计算得出每秒173个订单，当然实际上订单不能均匀分布在每秒，但我们主要为了论证思想的可行性。

代码实现：这里首先简单的利用Spring Scheduled作为订单的生产者，每一秒制造170个订单，放入Redis，注意Score的生成，为当前时间的后60秒，removeMillis()生成去掉毫秒的时间戳作为Rredis的**Zadd方法**的 Score。

![阿里面试中遇到的一些架构问题][98717071b9604d08b93a2541b1b27e45]

第二步：同样利用Spring Scheduled 一秒钟心跳一次，每次利用当前时间作为Key 从Redis 取数据。

![阿里面试中遇到的一些架构问题][fa174d0297004559b253d16c686cfd17]

经过测试，没有出现漏单的情况，这只是简单的实现，很多地方可以优化，在实际中用也可能会出现很多问题，需要不断完善，此案例只是提供思路，另外我觉得JDK的 DelayQueue 相对于Redis来说没有那么好，因为Queue毕竟每次取一个，如果同一时间的比较多可能不能符合当前这种时间严谨的需求。

以上是原作者的回答。

关于第二种思路我们再补充一下：

**Sorted Set**可以把任务的描述序列化成字符串，放在Sorted Set的value中，然后把任务的执行时间戳作为score，利用Sorted Set天然的排序特性，执行时刻越早的会排在越前面。这样一来，我们只要开一个或多个定时线程，每隔一段时间去查一下这个Sorted Set中score小于或等于当前时间戳的元素（这可以通过**zrangebyscore**命令实现），然后再执行元素对应的任务即可。当然，执行完任务后，还要将元素从Sorted Set中删除，避免任务重复执行。如果是多个线程去轮询这个Sorted Set，还有考虑并发问题，假如说一个任务到期了，也被多个线程拿到了，这个时候必须保证只有一个线程能执行这个任务，这可以通过**zrem命令**来实现，只有删除成功了，才能执行任务，这样就能保证任务不被多个任务重复执行了。

关于这个问题我们再深入思考一下，这两个方案更多是偏单机的，如果在分布式环境下，又该如何实现？

**思路 3**

方案：RabbitMq延迟队列

原理：RabbitMQ本身没有直接支持延迟队列功能，但是我们可以根据其特性Per-Queue Message TTL和 Dead Letter Exchanges实现延时队列。也可以通过改特性设置消息的优先级。

**特性1、Time To Live(TTL)**

> RabbitMQ可以针对Queue设置x-expires 或者 针对Message设置 x-message-ttl，来控制消息的生存时间，如果超时(两者同时设置以最先到期的时间为准)，则消息变为dead letter(死信)RabbitMQ针对队列中的消息过期时间有两种方法可以设置。

*  A: 通过队列属性设置，队列中所有消息都有相同的过期时间。
 *  B: 对消息进行单独设置，每条消息TTL可以不同。

> 如果同时使用，则消息的过期时间以两者之间TTL较小的那个数值为准。消息在队列的生存时间一旦超过设置的TTL值，就成为dead letter

**特性2、Dead Letter Exchanges（DLX）**

> RabbitMQ的Queue可以配置x-dead-letter-exchange 和x-dead-letter-routing-key（可选）两个参数，如果队列内出现了dead letter，则按照这两个参数重新路由转发到指定的队列。

*  x-dead-letter-exchange：出现dead letter之后将dead letter重新发送到指定exchange
 *  x-dead-letter-routing-key：出现dead letter之后将dead letter重新按照指定的routing-key发送

> 队列出现dead letter的情况有：

*  消息或者队列的TTL过期
 *  队列达到最大长度
 *  消息被消费端拒绝（basic.reject or basic.nack）并且requeue=false

综合上述两个特性，设置了TTL规则之后当消息在一个队列中变成死信时，利用DLX特性它能被重新转发到另一个Exchange或者Routing Key，这时候消息就可以重新被消费了。

**实现延迟队列方案1**

延迟任务通过消息的TTL和Dead Letter Exchange来实现。我们需要建立2个队列，一个用于发送消息，一个用于消息过期后的转发目标队列。

![阿里面试中遇到的一些架构问题][5f3effddde7d4f8dade158a69253547b]

生产者输出消息到Queue1，并且这个消息是设置有有效时间的，比如3分钟。消息会在Queue1中等待3分钟，如果没有消费者收掉的话，它就是被转发到Queue2，Queue2有消费者，收到，处理延迟任务。

该方法主要有三步：

第一步：设置TTL产生死信，创建一个队列，队列的消息过期时间为N分钟(这个队列N分钟内没有消费者消费消息则删除，删除后队列内的消息变为死信)

第二步：设置死信的转发规则（如果没有任何规则，则直接丢弃死信）

第三步：配置延时路由规则，需要延时的消息到exchange后先路由到指定的延时队列

**实现延迟队列方案2**

> 在rabbitmq 3.5.7及以上的版本提供了一个插件（rabbitmq-delayed-message-exchange）来实现延迟队列功能。同时插件依赖Erlang/OPT 18.0及以上。

但是rabbitmq像淘宝那样的量每天流转几千亿条消息，双十一大促，是搞不定阿里的问题的。

**思路 4**

方案：时间轮（TimingWheel）& 层级时间轮

原理：该方案的灵感来自于Kafka，JDK的Timer和DelayQueue插入和删除操作的平均时间复杂度为O(nlog(n))，Kafka基于时间轮可以将插入和删除操作的时间复杂度都降为O(1)。Kafka的原理请参照《Rabbitmq实战》作者朱忠华老先生的Kafka解惑之时间轮（TimingWheel）。

时间轮分为单级时间轮和层级时间轮。

时间轮简介：时间轮方案将现实生活中的时钟概念引入到软件设计中，主要思路是定义一个时钟周期（比如时钟的12小时）和步长（比如时钟的一秒走一次），当指针每走一步的时候，会获取当前时钟刻度上挂载的任务并执行:

1.单层时间轮设计：

![阿里面试中遇到的一些架构问题][a0c352b5c1b6462587227d0eb446ac31]

以上图为例，假设一个格子为1秒，整个一圈表示的时间为12秒，此时需要添加5秒后执行的任务，则此时改任务一个放到第（1+5=6）的格子内，如果此时添加13秒后执行任务，此时该任务应该等转完一圈后round为1 放到第二格子中，指针每转动一个一格，获取当前round为0的任务执行，格子上的其他任务round减1

问题： 当时间跨度很大，数量很大时，单层的时间轮造成的round很大，一个格子中链很长，所以衍生出多级时间轮的设计方案

2.多级时间轮设计方案：

![阿里面试中遇到的一些架构问题][95e854a36fc240209dce5965f259be96]

最小轮子走一圈，它的上层轮子走一格

假设图中每层轮子为20个格子，第一层轮子最小时间间隔为1ms，第二层为20ms，第三层为400ms，此时添加5ms后执行的任务，此时应该添加到第一层的第5格子中。如果此时添加445ms后执行的任务，则第一层表示的时间跨度不够，第二层表示的时间跨度也不够，第三层表示的时间跨度足够，该任务应该放到第三层轮子第二格子中，该轮子指针指到第二格子中时，计算离任务启动时间还有多长时间，慢慢将该任务移动到底层轮子上，最终任务到期执行。

关于更多如何在MQ中实现支持任意延迟的消息？建议看一下这篇文章https://www.cnblogs.com/hzmark/p/mq-delay-msg.html，需要说明的是

![阿里面试中遇到的一些架构问题][d6bf7edf73bb43a89ad17c67c6c13572]

阿里云上对业界MQ功能的对比，其中开源产品中只有阿里的RocketMQ支持延迟消息，且是固定的18个Level。固定Level的含义是延迟是特定级别的，比如支持3秒、5秒的Level，那么用户只能发送3秒延迟或者5秒延迟，不能发送8秒延迟的消息。消息队列RocketMQ的阿里云版本（收费版本）才支持到精确到秒级别的延迟消息（没有特定Level的限制）。

对支持任意延迟的需求确实不强，因为:

1.  延迟并不是MQ场景的核心功能，业务单独做一个替代方案的成本不大
2.  业务上一般对延迟的需求都是固定的，比如下单后半小时check是否付款，发货后7天check是否收货

支持任意延迟意味着消息是需要在服务端进行排序的。如何处理排序和消息存储，但是如何更牛逼的进行任意级别的延迟，进行海量的数据落盘呢？我们来看思路5。

**思路 5**

方案：单层文件时间轮

原理：

该图是开源版本RocketMQ支持18个Level的方案简图

![阿里面试中遇到的一些架构问题][744a455114384f8ebaaffa04ddc0a2ab]

结合RocketMQ的做法，但是又不同于它。

我瞎想一下（后面有高手要发系统性的文章，我抛砖引玉），由于大量堆积一定要落盘，另外结合一下rabbit的延时队列+Kafka的TimingWheel，来打造一个支持任意级别的延迟的工具。

第一步，CommitLog需要区分是否是延迟，而非延迟进入正常消费队列。

第二步，延迟的CommitLog剥离出来，按照消息顺序落盘，由于面对海量数据，需要进行落盘和消息备份，这里可以和流式计算Jstorm合作提升效能

第三步，TimeWheel加载延迟时间临近的消息到内存进行处理

**最后，觉得本文还不错的，可以关注小编。**

[98717071b9604d08b93a2541b1b27e45]: /images/20220215/1b86fea93f0e4997a915980002e1e644.png
[fa174d0297004559b253d16c686cfd17]: /images/20220215/e5c1616121a5447f949f0207a9fa8666.png
[5f3effddde7d4f8dade158a69253547b]: http://p1.pstatp.com/large/pgc-image/5f3effddde7d4f8dade158a69253547b
[a0c352b5c1b6462587227d0eb446ac31]: http://p1.pstatp.com/large/pgc-image/a0c352b5c1b6462587227d0eb446ac31
[95e854a36fc240209dce5965f259be96]: http://p1.pstatp.com/large/pgc-image/95e854a36fc240209dce5965f259be96
[d6bf7edf73bb43a89ad17c67c6c13572]: http://p1.pstatp.com/large/pgc-image/d6bf7edf73bb43a89ad17c67c6c13572
[744a455114384f8ebaaffa04ddc0a2ab]: /images/20220215/d090f08d14a8486fb40b2bdfcc1ae845.png