达达-京东到家作为优秀的实时配送物流平台，实现了多渠道的订单配送，包括外卖平台的餐饮订单、新零售的生鲜订单、高价知名商家的优质订单等待。为了提高平台的用户粘性，我们需要兼顾商家和骑士各自的愿景：商家希望订单能够准时送达，骑士希望能够高效抢单。那么适时增加订单定制的曝光率是时达物流平台的核心竞争力之一。本文将从零开始讲述订单配送系统的系统演进，以及方案设计和关键点，为大家解决相关业务场景提供案例参考。订单分发结构的演变在公司发展初期，我们的外卖订单是在商家下单后直接出现在抢单池中的。3公里范围内的骑士可以看到订单并从订单卡中获取送货地址和送货时限。关键信息。这种暴力的展示方式，很容易导致骑士选择对自己有利的订单进行投放，导致部分订单超时后无法投放。这样的模式在一定程度上导致了商家的流失，同时也浪费了骑士的配送时间。从上面的场景可以看出，我们的系统中缺少订单核心调度器。一种解决方案是为区域订单选择一个订单调度员，调度员会根据骑士的接单情况、交货时间、订单挤压等实时情况进行订单调度。这种模式看似可行，但人工成本太高，而且更依赖个人经验。核心问题出来了：个人经验的总结是什么？骑士正在交付的订单数量是否已经饱和？骑士的分娩习惯是什么？某个阶段的订单是否在途中？预计时间……明确了核心问题的答案后，我们的系统订单调度就成为可能了。基于以上原则，订单分发方式可以逐步从抢单池中的订单展示演化为系统派单。我们会记录商家的出单行为、小骑士的配送日志和运行轨迹等信息，并通过数据挖掘和数据分析，获取小骑士的画像、小骑士的预计发货时间、小骑士的预计到达时间等基本信息。骑士到达商店。;利用遗传算法规划最优投递路线……经过以上一系列算法，我们会在骑士池中匹配出最合适的骑士，然后使用长连接（Netty）不断通知骑士。随着达达业务的不断迭代，订单分发逐渐孵化出基于大商户的门店模式：基于商户维持固定数量的专属骑士，只有在配送能力达到时才会将订单发送至抢单池是不够的。一般情况下，使用dispatch方式通知骑士。订单派送模型订单派送可以简单地认为是一种信息流的推荐。在订单进入抢单池之前，我们会先根据各个城市的调度情况对订单进行N次调度。一般的表达形式如下：比如有一个订单需要推送。在推送过程中，假设一直没有骑士接受订单，那么每N秒推荐一次这个订单，然后进入抢单池。从订单派送的流程周期可以看出，派送模型中充斥着大量的延迟任务。只要能够派单，整个系统50%的功能点都可以轻松解决。先来了解一下经典的延迟方案：1.数据库轮询通过一个线程定时扫描数据库，获取需要派发的订单信息。优点：开发简单，结合quartz满足分布式扫描缺点：对数据库服务器压力大，不利于项目后续开发2.JDK的延迟队列——DelayQueueDelayQueue是Delayed元素的无界阻塞队列，从中元素可以仅在延迟期满时提取。队列中对象的顺序按过期时间排序。优点：开发简单，效率高，任务触发时间延迟小缺点：服务器重启后，数据会丢失。为满足高可用场景，需要二次开发hook线程；对停机时间的担忧；如果数据量急剧增加，也会导致OOM发生3.定时轮——TimingWheel定时轮的结构原理很简单。是一个循环队列，用于存放定时任务。底层通过数组实现，数组中的每个元素可以存储一个定时任务列表。列表中的每一项代表一个事件操作单元，当时间指针指向对应的时间网格时，列表中的所有任务都会被执行。时间轮由多个时间格组成，每个时间格代表当前实践理论的跨度，用tickMs表示；时间轮的数量是固定的，用wheelSize表示；整个时间轮的跨度用interval表示，那么指针转一圈的时间为：interval=tickMs*wheelSize如果tickMs=1ms，wheelSize=20，那么可以计算出此时的时间为20ms作为一个轮转周期，时间指针（currentTime）指向wheelSize=0的数据槽，此时在wheelSize=5的时间网格中插入一个延迟5ms的任务。随着时间的推移，指针currentTime继续向前移动。5ms后，到达时间格5时，时间格5需要对应的任务执行相应的应有操作。如果此时有一个定时为180ms的任务怎么办？直观的想法是直接扩大wheelSize？这样会导致wheelSize随着业务的发展不断扩大，从而导致时间轮占用大量的内存空间，导致效率低下，于是衍生出分层时间轮的数据结构。180ms的任务会升级到秒级时间轮，最后插入到秒级时间轮#8时间格对应的TimerTaskList中。如果此时有另一个任务计时为600ms，那么显然二级时间轮不能满足条件，于是升级为三级时间轮，最后插入到第三级时间轮TimerTaskList。注意，过期时间在[400ms,800ms]区间的多个任务（如446ms、455ms、473ms定时任务）会被放置在三级时间轮的时间格#1中，时间格#1对应于TimerTaskList的超时时间为400ms。随着时间轮的转动，当TimerTaskList到期时，原本预定450ms的任务还剩50ms，无法进行该任务的到期操作。会有一个时间轮的降级操作，会将剩余时间为50ms的定时任务重新提交给下一级时间轮，所以任务放在第二级时间轮中，过期时间为[40ms,60ms)在时间网格中。又过了40ms，此时又触发了任务，但是还剩10ms，不能立即执行应有的操作。所以需要再次降级。这个任务会以第一层时间轮的到期时间[10ms,11ms]加入到时间网格中，再过10ms后，这个任务就会真正到期，最后执行相应的周期操作。优点：效率高，可靠性高（Netty，Kafka，Akka都用），容易开发缺点：数据保存在内存中，需要实现持久化方案才能实现高可用订单调度的实现结合了以上三者方案最终决定使用redis作为数据存储，使用timingWhell作为时间驱动。这样就可以将定时任务的存储和时间推送解耦，依赖于Redis的AOF机制，不用太担心订单数据的丢失。Kafka选择了多层时间轮设计，以处理数千个延迟任务。我们从业务角度和开发难度上做了权衡，只选择设计单层时间轮来满足要求。1、时间网格与缓存的映射维护假设当前时间currentTime为11:49:50，订单的dispatchTime为11:49:57，则在时间网格#7中设置一个sentinel节点时间轮（作为是否有数据存储在redis中的依据）用于表示时间段是否会被时间事件触发，并将此数据放入缓存（key=dispatchTime+ip）。7秒后，触发该时间段的数据。数据会从redis中获取，相应的业务逻辑会异步执行。最后，为了防止因为重启等一些操作导致数据丢失，哨兵节点的维护也会在缓存中维护一份数据，重启时再次读取。2、缓存的key统一加上IP标识。它附加到自己的系统。通过将IP标识统一添加到缓存的key中，可以保证每个服务器消费自己的数据，从而防止分布式环境下的并发问题，也可以减少遍历整个链表带来的问题。时间损失（时间复杂度为O(N)）3.使用异步线程处理时间网格中对应的数据。使用异步线程是考虑到如果前面的节点出现异常或者超时，会延迟下一秒的操作，如果使用异常，可以提高调度的即时性。我们在设计系统的时候，系统的完善和业务的满意度是相互关联的。单从上面的设计来看，会存在一些问题。比如使用IP作为缓存key，如果集群发生变化，会导致数据无法被消费；使用线程池进行异步处理时，也有可能不会消耗到数据。这些不会被消费的数据会进入抢单池。从调度场景的需求来看，这些场景是可以接受的。当然，我们的系统会有脚本定期筛选，那些进入抢单池的订单会重新派单。为什么不用ScheduledThreadPoolExecutor定时轮询redis呢？即使这样可以满足业务需求，获取定时触发的任务，但是空查询不仅会增加服务的CPU，还会增加redis的QPS，可能导致redis的慢查询会大幅增加。结语我们在完成一个功能的时候，往往需要一些可视化的数据来判断业务开发的正确与否。所以我们在开发的时候，也记录了一些骑士团和骑士团的互动。从日报数据可以看出，90%以上的订单都是通过派单发出，并被骑士接受的。订单分发模式是提高订单曝光率的有效技术手段。我们一直在结合大数据、人工智能等技术手段，更好地做订单配送，提供更多元化的功能，让达达成为更一流的配送平台。作者：季炳坤，Java工程师，负责订单分发、订单权限、合并订单等相关工作。【本文来自专栏作者张凯涛微信公众号（凯涛的博客）公众号id：kaitao-1234567】点此查看作者更多好文
