查看: 93|回复: 0

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

发表于 2018-9-11 15:13:06
一位网友之前面试淘点点的时候被问倒得一个问题至今牵挂,工作两年,由于工作环境的限制,没能接触到一些大数据量的并发工作,也没能有机遇参与复杂系统的设计,而学习复杂或高并发系统的唯一途径就是阅读源码,惭愧的是,至今也只阅读了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。




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




经过测试,没有出现漏单的情况,这只是简单的实现,很多地方可以优化,在实际中用也可能会出现很多问题,需要不断完善,此案例只是提供思路,另外我觉得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个队列,一个用于发送消息,一个用于消息过期后的转发目标队列。




生产者输出消息到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.单层时间轮设计:




以上图为例,假设一个格子为1秒,整个一圈表示的时间为12秒,此时需要添加5秒后执行的任务,则此时改任务一个放到第(1+5=6)的格子内,如果此时添加13秒后执行任务,此时该任务应该等转完一圈后round为1 放到第二格子中,指针每转动一个一格,获取当前round为0的任务执行,格子上的其他任务round减1
问题: 当时间跨度很大,数量很大时,单层的时间轮造成的round很大,一个格子中链很长,所以衍生出多级时间轮的设计方案
2.多级时间轮设计方案:




最小轮子走一圈,它的上层轮子走一格
假设图中每层轮子为20个格子,第一层轮子最小时间间隔为1ms,第二层为20ms,第三层为400ms,此时添加5ms后执行的任务,此时应该添加到第一层的第5格子中。如果此时添加445ms后执行的任务,则第一层表示的时间跨度不够,第二层表示的时间跨度也不够,第三层表示的时间跨度足够,该任务应该放到第三层轮子第二格子中,该轮子指针指到第二格子中时,计算离任务启动时间还有多长时间,慢慢将该任务移动到底层轮子上,最终任务到期执行。
关于更多如何在MQ中实现支持任意延迟的消息?建议看一下这篇文章https://www.cnblogs.com/hzmark/p/mq-delay-msg.html,需要说明的是




阿里云上对业界MQ功能的对比,其中开源产品中只有阿里的RocketMQ支持延迟消息,且是固定的18个Level。固定Level的含义是延迟是特定级别的,比如支持3秒、5秒的Level,那么用户只能发送3秒延迟或者5秒延迟,不能发送8秒延迟的消息。消息队列RocketMQ的阿里云版本(收费版本)才支持到精确到秒级别的延迟消息(没有特定Level的限制)。
对支持任意延迟的需求确实不强,因为:
延迟并不是MQ场景的核心功能,业务单独做一个替代方案的成本不大
业务上一般对延迟的需求都是固定的,比如下单后半小时check是否付款,发货后7天check是否收货
支持任意延迟意味着消息是需要在服务端进行排序的。如何处理排序和消息存储,但是如何更牛逼的进行任意级别的延迟,进行海量的数据落盘呢?我们来看思路5。
思路 5
方案:单层文件时间轮
原理:
该图是开源版本RocketMQ支持18个Level的方案简图




结合RocketMQ的做法,但是又不同于它。
我瞎想一下(后面有高手要发系统性的文章,我抛砖引玉),由于大量堆积一定要落盘,另外结合一下rabbit的延时队列+Kafka的TimingWheel,来打造一个支持任意级别的延迟的工具。
第一步,CommitLog需要区分是否是延迟,而非延迟进入正常消费队列。
第二步,延迟的CommitLog剥离出来,按照消息顺序落盘,由于面对海量数据,需要进行落盘和消息备份,这里可以和流式计算Jstorm合作提升效能
第三步,TimeWheel加载延迟时间临近的消息到内存进行处理
欢迎工作一到五年的java工程师朋友们加入Java架构开发:744677563
群内提供免费的Java架构学习资料(里面有高可用、高并发、高性能及分布式、Jvm性能调优、Spring源码,MyBatis,Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多个知识点的架构资料)合理利用自己每一分每一秒的时间来学习提升自己,不要再用"没有时间“来掩饰自己思想上的懒惰!趁年轻,使劲拼,给未来的自己一个交代!



回复

使用道具 举报