调度系统揭秘（下）：调度算法与架构设计

一、调度算法

在调度系统中，调度算法常见是以下两种：

1. 广度优先
2. 深度优先

1.1、广度优先:

广度优先搜索算法按照任务之间的依赖关系进行逐级遍历，先执行所有直接前置任务，再执行所有直接后继任务，以此类推，直到所有的任务都被遍历和执行完成。其特点如下：

1. 执行顺序合理：广度优先搜索保证所有任务都会按照其执行顺序被执行，从而能够保证任务之间的依赖关系得到满足。
2. 适合处理大量的任务：由于广度优先搜索采用逐层遍历的方式，因此能够高效地处理大量的任务，提高作业的执行效率。
3. 消耗较多的资源：由于需要保存每个任务的前置和后继关系，因此广度优先搜索可能会占用较多的内存和计算资源。
4. 不适合处理复杂的依赖关系：当任务之间存在复杂的依赖关系时，使用广度优先搜索可能会导致调度效率降低

示例：

1. 这里的广度优先是指先优先将下一梯队任务放置在任务队列中，而并非指B、C任务必须全部执行完毕后才可以运行D、E、F，如果B先运行结束可以直接调度D任务。
2. 由于B、C任务的执行时间各不相同又互不关联，例如B任务执行3秒，C任务执行30秒，此时如果阻塞B的下游任务意义不大
3. 由于J 依赖G、H；正确的执行应该是G、H都执行完毕后再执行J，否则会执行两次J任务；故此处应加一层业务判断：先执行完毕的任务应先判断下游任务是否还依赖其他上游，若其他上游任务没有运行完毕则不触发下游任务，由其他上游任务运行成功后再触发J（此处建议使用责任链模式，在判断是否需要调度下游任务时只有通过责任链中的各种规则后方可调度）

广度优先适用于按照“层次”优先级依次调度任务，批量数据处理等；例如BI中表的依赖关系：上图中的D表依赖B表数据，只有当B表数据更新后才可触发J任务

1.2、深度优先

深度优先搜索算法按照某一个任务开始，一直往下执行该任务的后继任务，直到该任务的所有后继任务都被执行完毕，然后再回溯到该任务的前置任务再依次执行其后继任务，以此类推，直到所有的任务都被遍历和执行完成。其特点如下：

1. 消耗较少的资源：由于深度优先搜索只需要保存当前调度路径上的部分信息，因此相对于广度优先搜索来说，它消耗的内存和计算资源较少。
2. 不保证任务的执行顺序：深度优先搜索不保证任务按照其执行顺序被执行，可能会导致任务之间的依赖关系得不到满足。

示例：

1. 关于H、G节点是否要触发两次任务J需要根据业务需求而定，可以通过增加一层业务判断从而只调用一次任务J
2. 当B分支全部执行完毕后会回溯到A节点从而触发C分支的全部任务

深度优先搜索适合处理任务之间的依赖关系比较复杂、数量较多的作业，或者不要求保证任务按照其执行顺序被执行的场景。

1.3、总结

广度优先搜索（BFS）

广度优先搜索按照任务之间的依赖关系逐级遍历，先执行所有直接前置任务，再执行所有直接后继任务。其特点如下：

1. 执行顺序合理：保证所有任务按照其执行顺序执行，满足任务之间的依赖关系。
2. 适合处理大量任务：采用逐层遍历方式，高效处理大量任务，提高作业执行效率。
3. 消耗较多资源：需要保存每个任务的前置和后继关系，占用较多内存和计算资源。
4. 不适合处理复杂依赖关系：复杂依赖关系可能导致调度效率降低。

广度优先适用于按“层次”优先级依次调度任务，适合批量数据处理等场景。例如在BI系统中，表的依赖关系决定了数据更新触发的顺序。

深度优先搜索（DFS）

深度优先搜索从某个任务开始，一直执行其后继任务，直到该任务的所有后继任务都执行完毕，再回溯到前置任务，依次类推，直到所有任务遍历和执行完成。其特点如下：

1. 消耗较少资源：只需保存当前调度路径上的部分信息，相对于BFS，内存和计算资源消耗较少。
2. 不保证任务执行顺序：可能导致任务依赖关系得不到满足，任务执行顺序无法保证。

深度优先适合处理任务依赖关系复杂、数量较多的作业，或不要求任务按执行顺序执行的场景。

综述

广度优先搜索适用于任务之间依赖关系简单、需要按顺序执行的场景，适合批量数据处理。深度优先搜索适用于任务依赖关系复杂、数量较多，或不要求按顺序执行的场景。在实际应用中，选择合适的调度算法需要根据任务的具体特点和需求综合考虑。

二、架构设计

调度系统在服务架构设计上一般分为以下两种：

1. Master/Slave架构
2. Leader架构

2.1、Master/Slave架构

Master/Slave架构是一种常见的调度系统架构，其中主节点（Master）负责任务的调度和监控，从节点（Slave）负责任务的执行。以下是常见的Master/Slave架构设计：

1. manager节点负责任务分配、元数据管理、worker宕机重试以及对外提供接口能力等，而worker节点主要负责任务执行
2. manager节点和worker节点都可以布置多活，通过nacos对外提供服务和负载均衡
3. manager、worker服务均不保留元数据信息，元数据存储在数据库中，只有manager服务可以操作元数据
4. manager通过redis队列向下分发待执行任务，worker节点抢占redis队列中的任务并执行，该设计实现任务分配的均衡，确保每个Worker节点的任务负载均衡，同时通过Redis队列下发任务可以提高系统的可扩展性，轻松地扩展到多个Worker节点，从而提高系统的可扩展性和吞吐量，最后该设计可以实现任务的异步执行。
5. manager与worker节点可以进行通讯，实现worker心跳及任务执行状态更新等操作，从而保证任务的可靠性

优劣分析：

优点：

1. 可扩展性好：Master/Slave架构可以轻松地扩展到多个从节点，以满足系统的可扩展性需求。
2. 高可用性：Master/Slave架构可以实现多活从而保证高可用性。
3. 任务调度和监控功能强大：Master节点负责任务的调度和监控，可以实现更加灵活的任务调度和监控功能。
4. 任务分配均衡：Master/Slave架构可以实现任务分配均衡，确保每个从节点的任务负载均衡。

缺点：

1. 通信延迟：Master/Slave架构中，从节点需要不断地向主节点汇报任务执行情况，这可能会导致通信延迟问题。
2. 系统复杂度：Master/Slave架构中，需要管理和维护多个从节点，这可能会增加系统的复杂度和维护成本。
3. 部署复杂：Master/Slave架构中，若要实现最低级别的高可靠、高可用性，最少需要4个服务，即：双master、双slave

2.2、Leader架构

下图中的Leader架构和传统Leader架构有所不同，传统Leader架构中Leader节点只负责任务的调度和监控，Follower节点负责执行；而下图架构中无论是Leader节点还是Follower节点都可以进行任务调度和任务执行，唯一区别在于Leader节点多了一项节点存活监听功能，负责将宕机节点的任务从新调度。

1. Leader选举可以通过抢占redis锁竞选，竞选失败的节点成为follower并且会轮询抢占，直到leader节点宕机后再参与竞选
2. Leader节点和Follower节点都可以进行任务分配和执行，两种服务皆不保留元数据，元数据存储至数据库中
3. Leader、Follower节点都可对外提供接口能力，通过Nacos实现服务发现和负载均衡
4. Leader节点相较于Follower节点多了一项节点监听功能，所有节点都会注册到redis-节点注册列表，并会心跳更新各自节点的时间戳，leader节点定时轮询访问节点注册列表，当发现某个节点更新时间超过阈值便认定该节点宕机，通过访问数据库将其正在运行中的任务重新分配到redis任务队列中重试
5. 在数据库任务实例表中应有负责运行该任务服务唯一ID的标识字段，用于节点宕机后Leader可以根据节点注册列表中的服务ID与任务实例表中的服务标识字段进行匹配，将其未运行成功的任务再次调度，实现高可靠性

优劣分析：

优点：

1. 可扩展性好：Leader架构可以轻松地扩展到多个从节点，以满足系统的可扩展性需求。
2. 部署简单：若要实现最低级别的高可靠、高可用性，之需要2个服务即可实现。

缺点：

1. 监控开销：Leader架构中，leader节点需要定期轮询节点注册列表，从节点需要定期汇报心跳，增加网络和系统计算开销
2. 性能瓶颈：Leader架构中，由于每个节点都负责任务分配及任务执行，对单个服务可能存在压力过大、性能等问题。

2.3、总结

Master/Slave架构和Leader架构各有优缺点。在选择调度系统架构时，需要根据具体的应用场景和需求综合考虑。如果系统需要强大的任务调度和监控功能，以及高可用性和可扩展性，可以选择Master/Slave架构；如果系统需要更简化的部署和动态的任务调度，可以选择Leader架构。