xtimer-02-架构设计

学习核心

• 定时微服务结构设计
  • 实现思路
  • 整体架构
  • 调度流程模块化设计
  • 任务生成模块化设计
  • 存储设计
    • 选型
    • 存储结构设计
  • 服务接口设计
• 定时微服务核心问题
  • 如何解决定时微服务关键问题
  • 幂等性设计原则：如何确保任务不重复执行？

学习资料

todo

• 调度流程模块化设计详情 细节/评论理解
• （概念梳理还有点懵，查看视频或者了解项目代码架构之后再来复盘）

定时微服务结构设计

​ 定时微服务的核心：本质是一个主动轮询的模型，过程中辅以有序表结合分时分桶的方式进行轮询效率的优化

• 其实现核心是基于“主动轮询”+触发机制
• 考虑到轮询效率，基于优化存储结构的思路提升轮询效率
  • 有序表：对于任务的存储采用有序表进行存储，将时间复杂度从O(N)->O(logN)
  • 横向分治：基于时间范围进行分片，以均摊短板效应问题，降低每次轮询的时间复杂度
  • 纵向分治：考虑到并发场景下共享资源问题，xtimer实现一个线程只能消费一个分片的任务。为了提高对并发度的支持，通过进一步分桶将批量任务继续进行拆分，让多个线程进行处理，每个线程消费各个桶的任务（实际是进一步细分分片粒度，让更多的线程加入工作中）

1.实现思路

✨定时器核心：主动轮询

​ 核心：实现定时器最简单粗暴的方式 =》轮询 + 触发

（1）注册定时器：解析并将一系列定时任务平铺直叙地展开，每笔定时任务明确展示执行时间这一指标

（2）节点自轮询：每间隔一个微小的时间范围，对定时任务列表进行全量查询

（3）过滤&触发：以 执行时间点小于等于当前时刻 作为过滤条件，摘出满足执行条件的定时任务进行执行

​ 基于此，一个乞丐版定时器就已经实现了，但显然需要优化的点还有很多，例如这一过程中每次查询都需承担 O(N) 的线性时间复杂度（指遍历所有数据的复杂度）为代价，显然还存在进一步改进的空间

✨存储结构优化：有序表（优化检索的时间复杂度）

​ 核心：基于有序表提升检索效率

​ 对于无序表结构而言，插入记录固然可以达到O(1)的时间复杂度，然而每次查询时需要承担O(N)的线性时间复杂度。

​ 基于木桶效应，存储结构优化的方向是将时间复杂度均摊到每一笔操作当中，从而补齐短板。例如使用红黑树(RBTree) 、跳表(Skip List)这样的数据结构，能以将插入记录的时间复杂度由 **O(1)->O(logN)为代价 =》换取查询时间复杂度由O(N)->O(logN)**的优化

​ 在 xTimer 的实现中，存储介质选型上选择使用 Redis zSet，以定时任务执行时间为 Score 进行有序结构的搭建。当定时任务数量达到一定量级时，zSet底层基于跳表作为有序表的实现，实现流程分析如下：

（1）以 Redis zSet 作为存储介质；

（2）每次添加定时任务时，执行ZAdd 动作，以执行时间的时间戳作为排序的键（Score） 进行有序结构的搭建：

（3）每次查询定时任务时，执行 ZRangeByScore 动作，以当前时刻的时间戳加上一个微小偏移量作 score 的左右边界

于是，木桶的检索短板由 O(N)成功提升到 O(logN)，这是属于时间复杂度模型的优化，接下来还可以通过数据分治的方式对查询的任务数量 N 进行优化

❓扩展问题分析

​ 问题：如何理解查询定时任务要以当前时刻的时间加上一个微小偏移量作 score 的左右边界？

​ 对于定时任务的获取是范围获取，而不是针对某个时间戳（例如1分钟获取一次，在9.01分进行获取的话则需要将9:00->9:01这个时间段的定时任务都检索出来）

​ “每次递增1s”的定时概念是查询频率设定为1秒1次，每次score查询的跨度也是1秒（例如22:37:58 -> 22:37:59）。此处暂时没涉及实现部分，暂定将“微小偏移量”理解为类似此处的“1s”概念

✨存储结构优化：横向分治（分时）

​ 核心：通过时间范围分片，减少查询涉及的任务数量

​ 每次查询时，真正的目标是那部分"即将执行"的定时任务，而另一部分"更晚执行"的任务实际上在本轮查询中是作为干扰项，徒然增大了数据规模却无实质用途。

​ 此处使用到两个比较含糊的用词：“即将执行”和“更晚执行”，因此需要有一个时间范围分片的概念，将整条时间切分为一个又一个边界清晰的时间片。基于此，可以把和当前时刻同属于一个时间片内的任务视为高优先级的“即将执行”的定时任务，而从下一个时间片开始往后的任务都视为低优先级的“更晚执行”的定时任务。在 xTimer 的实现中，选用1分钟作为分片的时间范围，更细致的实现流程如下:

（1）插入每笔定时任务时，根据执行时间推算出所属的分钟级时间范围表达式，例如: 2022-09-17-09:00:00 -> 2022-09-17-09:01:00

（2）以分钟级时间范围表达式为key，将定时任务任务插入到不同 ZSet 中，组成一系列相互隔离的有序表结构

（3）每一次查询过程中、同样根据当前时刻推算出对应分钟级时间范围表达式，并以此为key 查找到对应的有序表进行 ZRange 查询

​ 至此，每一次查询的任务量级就从全量数据N进一步减小到分钟级数据 M，毋庸置疑 M << N

❓扩展问题分析

问题1：选用1分钟作为分片的时间范围，如果此处时间取得太小或太大会带来什么问题呢？

• 此处分片的时间范围并没有一个标准，理解“太小”、“太大”的缺点即可，可以是30s、1min、2min等

• 针对分片规则的考虑

  • 如果时间取得太大，则分片变少，同等任务量情况下每个分片的任务数量就会变多，则可能存在“大key问题”
  • 每个分片都需要配备一个分布式锁，如果此处时间取得太小则分片相应就会变多，需要维护分布式锁带来的性能开销

• 针对存储结构优化，由横向分治和纵向分治共同构建分片规则，一个分片是由**“分钟” + “桶号”**共同决定的，因此要考虑分片规则带来的性能影响

  • 任务拆分过细会导致分片数过多，分片存储本身需要额外占用资源
  • 每个分片都需要配备一个分布式锁，对分布式锁的维护也存在一定的性能开销

问题2：横向分治之后能够优化查询效率吗？如果不进行分片而是每次查询往前搓1分钟的定时任务，这种方式和横向分治的效率一样吗？

​ 从实现上分析两种方式执行的命令都是一样的，其时间复杂度是logN，但N的大小会影响查询实现。

• 基于传统检索方式，在当前时间戳基础上往前推1min，获取这个时间段的任务，此时的N是针对全量任务数，所以其时间复杂度为logN
• 基于横向分治方式，会基于分片规则将任务进行分片，检索定时任务时会根据当前时间戳计算出其所属分片（key），然后根据key定位到其所在分片。分片之后的单片任务量会更少，检索效率也会更高（例如假设任务数是均匀生成的，则此处单片任务量为M，M << N => logM << logN）

​ 可以简单理解为在1w个任务里面找和在1k个任务里面找的效率肯定不同

✨存储结构优化：纵向分治（分桶）

​ 核心：通过定时任务分桶，提高并发度

​ 前面的设计都基于单核的视角出发，对查询和存储模型进行优化，然而生产环境中还需考虑集群模式下的分布式定时器的实现方案，单个节点可以基于线程池实现高并发

​ 为了避免引起多线程介入导致对临界资源的竞态问题，xTimer 在实现上以分片作为最小的资源粒度，每一个分片对应的任务集只会由一个线程负责作轮询。因此在上述横向分治的基础上，需要将时间分片拆解为更细的粒度，即在横向上额外增加一个分桶的维度，从而保证每个时间范围内能有对应于分桶数量的线程并发参加工作。流程分析如下:

（1）插入定时任务时，首先根据执行时间，确定其从属的时间范围；

（2）根据定时任务的唯一标识id，结合服务对最大桶数的设置参数，随机将定时任务划分到一个桶中；（例如task.timerId % maxBucket）

（3）以时间范围和桶号组装形成一个新的key，形成一个二维分片，实现对定时任务有序表的隔离；

（4）后续流程与横向分治相同；

至此，分布式定时器核心方案的轮廓已经呈现，本质上是一个主动轮询的模型，过程中辅以有序表结合分时分桶的方式进行轮询效率的优化

❓扩展问题分析

问题1：并发度概念

​ 此处的并发度的影响因素考虑为以下几部分：分桶、调度器的线程池、触发器的线程池，这几个相关的配置都会影响并发度

问题2：为什么是分布式定时器？

​ 因为 xtimer 的设定是一个独立的定时微服务方案，因此部署需要相应考虑到多机部署的场景，即为一个在分布式环境下的定时器

问题3：如何理解通过定时任务分桶，提高并发度？

​ 为了避免引起多线程介入导致对临界资源的竞态问题，xTimer 在实现上以分片作为最小的资源粒度，每一个分片对应的任务集只会由一个线程负责作轮询。分桶的目的是在横向分治的基础上对一堆任务继续进行拆分，让更多的线程来并发处理任务，提高效率

问题4：分桶的“静态”和“动态”概念

​ 静态分桶：分桶数是固定的，没有做任务数量的判断，可以理解为每1分钟的ZSET数都是相同的

​ 动态分桶：根据任务数量决定分桶数（根据算法策略得到分桶数量（每个桶存多少任务），然后确定分桶个数）

问题5：一个分片内的所有任务只由一个线程处理吗？一个线程怎么处理得过来？

​ 需理解此处的“处理概念”，上述分片分桶场景是针对任务轮询，因此此处的一个线程只负责“取任务”（消费任务），将其丢入线程池，其并不负责执行

2.整体架构

定时任务调度流程

​ 服务架构：3个模块+2个线程池（协程池）

​ xTimer 是一个去中心化体系的定时任务调度框架，根据职责边界，将服务拆分为三个模块：调度器模块(Scheduler module)、触发器模块(Trigger module)、执行器模块(Executor module)，各模块之间存在依赖关系，父模块通过协程池的方式异步启动子模块进行工作

定时任务生成流程

​ 定时任务创建与webServer和migrator 2个模块有关

​ xTimer 提供了 webServer 模块，面向用户提供 api 用于定时器的创建；有两个地方会触发迁移模块的迁移逻辑

• 一个是用户调用激活定时器接口
• 另外一个是migrator会定时执行的脚本

​ 迁移执行逻辑：具体的迁移执行逻辑都是一致的，会根据定时器 cron 表达式批量创建定时任务，用于执行；然后将定时任务提前加载到 redis 中，采用 zset 有序表进行组织，供触发器模块轮询触发

❓问题扩展分析

问题1：项目如何插入定时任务？怎么进行数据预热？

​ 定时任务是根据对应的定时器timer中的cron配置自动生成，会相应涉及MySQL和Redis的操作。

​ 数据预热概念：“预热”指的是将近期要触发的任务（例如2h内）生成出来放在Redis和MySQL（数据冷热分区的设计）。如果超过2h后没有生成的任务则交由定时脚本进行兜底。这个“不断将近期任务生成出来存放在Redis的过程则称为预热”

​

问题2：线程池的命名歧义

​ 针对线程池的命名歧义：结合上述图示分析，原设定两个线程池依次叫调度器线程池、触发器线程池，但结合代码分析来看，在Java中代码实现是schedulerPool为由调度器提交任务，而真正执行任务的是触发器模块的work方法；triggerPool 为由触发器提交任务，但执行的任务是执行器模块的 work 方法，所以这个线程池原来命名的依据是根据所属模块进行命名，但实际上结合具体执行来看应该要依据具体执行任务的模块来进行命名更为合适

​ 即调度器模块是单线程的，触发器模块有一个触发器线程池，执行器模块有一个执行器线程池

​

问题3：单机模式下，一个分片由一个触发器线程负责触发。如果是多机扩容模式下，如何将分片分配给不同的机器的不同触发器线程呢?

​ 多机扩容模式下，扩容机制受限于分片策略（假设只有1个分片，那么最终也只会有1个机器的某个线程抢占到分布式锁，而其他没有抢到锁的机器只能空闲等待）。因此多机扩容模式下，首先要考虑分片策略（保证同一分钟有多个桶，可以提供足够的资源供多机抢占调度），基于这种设计，只要谁抢到分布式锁谁就获得相应分片的触发权，但这种随机竞争的机制可能也会导致不同机器拿到的任务不均等（虽然都是抢占1个分片，但是每个分片的任务数量可能不同），就会出现一些机器负载很大、一些机器负载很小的情况

问题4：任务执行“推拉模式”的考虑

​ 目前xtimer的设定是由机器主动竞争拉取任务，谁抢到分布式锁谁就获得相应分片的触发权，但这种随机竞争的机制可能也会导致不同机器拿到的任务不均等，从而导致出现一些机器负载很大、一些机器负载很小的情况

​ 如果说采用主动分配分片（主动分配任务）的模式（例如在配置文件中直接写好哪台机器负责哪些桶号的分片），但这需考虑接收方的处理性能和状态，否则一旦某台worker出现宕机，那么它被动分配到的那些分片就暂时没办法去处理了（可能需要人工介入）

问题5：“激活”和“去激活”概念？

​ 用户创建定时任务后，这个任务还需要激活后才能执行，如果不激活，即使创建成功、任务到时间了也不会执行。

​ 可以理解为timer定时器就是一个“闹钟”，而“激活”和“去激活”则是“闹钟开关”，timer被“激活”后会根据timer相关的cron配置定时生成相应的任务，然后等待被调度。“去激活”则是指“关闭闹钟”，项目中关闭闹钟是通过修改timer状态实现（不会对已经生成的任务有任何操作），任务在触发执行的时候会检查相应的定时器状态，如果发现timer已关闭则不执行

问题6：迁移逻辑分析

​ 迁移逻辑：是指根据定时 cron 表达式批量创建定时任务，用于执行的逻辑。

​ 举例：以一个定时器timer（周期定时任务：每隔5分钟运行一次）为例，那么迁移的工作就是解析这个定时任务配置的要求，具体生成一个个指定时间点要执行的任务，然后将其保存起来

​ 以单纯MySQL存储为例，假设9点开始，每隔5分钟执行一次operation操作（回调业务逻辑），那么它生成的任务就是：

时间点	任务	执行（回调业务逻辑）
9:05	task1	执行一次operation操作
9:10	task2	执行一次operation操作
9:15	task3	执行一次operation操作
....（以此类推）	taskN	执行一次operation操作

​ 而迁移逻辑则是将这些任务生成、落库，为后续任务执行做预热处理（结合代码分析）

问题7：如果用户执行了任务，停止这个定时任务是不是还得删 mysql 的记录和 redis 的记录?

​ 对于“去激活”操作的处理逻辑，目前xtimer实现“去激活”操作只是修改timer的状态为“关闭”，不会对现有已生成的任务做其他操作（例如删除“无效任务”），而是在任务真正执行的时候进行校验

​ 实际对于“关闭闹钟”这一操作，其会对关联已生成的任务产生影响，需要如何消除这一影响有两种思路（主要是在“无效任务的运行”和“频繁增删任务的消耗”两者间做了取舍）

• 关闭闹钟的同时相应把无效的任务清理掉（但如果闹钟再次开启则需相应再次生成相关的节点任务）
• 对于已经生成的任务不做任何处理，只在最后触发阶段（回调业务方）的时候，会判断timer是否关闭状态，如果校验为关闭状态则不回调，也不会影响业务方

问题8：图示中的定时脚本概念

​ migrator scheduler定时脚本里面存放的是“迁移逻辑”，指的是根据timer设定的cron表达式，提前生成2小时后待执行的任务，等待任务被触发调度（提前预热数据也是基于冷热数据分区的考虑，充分利用冷热特性，将2小时内已被激活的待执行任务按照预期执行时间放入Task中便于后续调度器进行分片分桶）

• 用户调用“创建定时器timer接口”创建的是一个timer（闹钟）
• 而“迁移逻辑”则是去发现用户创建的这些timer，然后根据相应的逻辑自动生成“节点任务”

​ 主要是考虑周期任务的执行，如果是周期任务不可能每次都让用户调用一次接口“创建任务”，而是让用户创建一个“timer”概念，然后xtimer中的迁移模块通过解析这些cron配置去主动生成任务，而用户只需要关注“闹钟的开关状态”即可

3.调度流程模块化设计

​ 调度流程化模块涉及调度器模块、触发器模块、执行器模块

​

调度器模块

（1）实现核心

​ 模块核心：负责二维分片（分时+分桶）的全局统筹分配

​ 分片规则：每一笔定时任务会从属于一个基于时间范围和桶号组成的二维分片，每一个二维分片内会存储一个基于执行时间排好序的有序定时任务集合。

​ 调度器的作用：负责在分布式场景中，将一系列二维分片资源进行统筹分配，最终保证一个分片会由一个单独的触发器角色进行负责，既不能被遗漏，也不能被重复执行

​

xTimer 的实现中，调度器模块核心流程如下：

• （1）基于 time ticker 每隔 1s进行主动轮询，基于当前时刻推算出对应的分钟级时间范围表达式；
• （2）读取配置获得最大桶数的信息，基于时间范围拼接桶号，获得当前需要关心的一系列二维分片的 key；
• （3）尝试抢占对应于每一个二维分片的分布式锁，并将锁的过期时间设置为一个大于1倍分片时间，小于2倍分片时间的值。 例如分片时间范围为1分钟，那这个值N 应该满足(60s<N<120s)，项目里默认设置的是70s；
• （4）抢锁成功，则调度一个触发器进行作业；

（2）关键点分析

问题1：分片规则？

​ 分片 + 桶号决定一个分片，实现上一个分片就是一个独立的ZSET

问题2：如何理解上述步骤（2）中“一系列二维分片的key”

​ 1分钟内，每隔1s就会有1个线程请求一个分片（由“分时+分桶”构建的二维分片key），线程获取到哪个锁就执行哪个分片（如果没有可获取的分片，这个线程会在线程池等待）。一个独立的ZSET由一个线程负责触发，所以一个线程要负责将1分钟内的任务全部触发完（分布式锁和分片一一对应的）

todo 问题3：业务流程梳理？代码实现核心分析

？？？？？？？？？

​ Java 版本，是先取一个线程，再执行第(3)、(4)，以及触发器模块里的第(4)。调度器模块主要是每隔一秒告诉一次触发器模块当前是触发哪一分钟(当前分钟和前一分钟)、哪一个桶号，即哪一个分片。分布式锁的获取、延长过期时间都是属于触发器模块的。

​ 调度器模块每隔一秒，会尝试抢占当前时间对应的分钟范围中每一个二维分片的分布式锁，

​ 比如 15.00-15.01这1分钟内有3个桶（即3个分片），是每隔一秒调度模块就会创建多个线程(来自线程池)，每个线程会去抢占对应分片的分布式锁，哪个线程抢占锁成功则代表拥有了对应分片的触发权（将这个分片的任务交由触发器线程池去处理），没有抢到锁的线程则继续等待。

代码确认：

​ 1.但是大部分时间是抢不到的。整体平均来看，例如1分钟 60 次抢占，只有1次是成功的。

​ 2.这里调度器就是一个线程循环抢占锁，抢到哪个分片的锁就把这个分片当成一个任务交给从触发器线程池执行。

todo

​ 问题：执行器线程池是同步执行任务的，假设执行器线程池总是16个，单个桶的任务有100个，是否在后面的任务延迟就高了？因为执行不过来了（是） 如何理解？？

==扩展问题：线程池数量如何配置？动态调优？==目前线程池就是根据经验值配的，例如 100，没有在这里做调优。如果后续这里成为瓶颈，可以讲线程池参数动态化，做动态调优。动态调优方案学习下这个:JAVA 线程池调优

触发器模块

（1）实现核心

​ 模块核心：按时唤醒二维分片内的定时任务

​ （1）触发器模块承上启下，上承调度器模块，作为调度器的子模块；下接执行器模块，作为执行器的父模块

​ （2）当触发器被调度器启动后，在对应分片的时间范围内，根据策略对分片进行间隔1s的持续轮询

​ （3）将达到执行条件的定时任务取出，不断从协程池中取出对应于任务数量的协程，在协程中启用执行器模块，用于执行定时任务

​ （4）当触发器协程完成任务后，会将该分片对应的分布式锁的过期时间更新为一个大于2倍分片时间范围的值（项目里默认是130s，大于120s）

（2）关键点分析

关键点1：关于分布式锁超时时间（1T<N<2T）和延时时间（N>2T）的解释

​ 这两个时间的设置是与代码中“重复执行上一分钟的分片”的逻辑相配合的。共同作为一个兜底机制，当某一个分片执行失败了，那这种方式可以在下一分钟进行一次重试

​ 为什么要重复执行一下前一分钟的批次? =》基于兜底重试机制，如果某一个分片执行失败了，那这种方式可以在下一分钟进行一次重试

​ 超时时间（1T<N<2T）和延时时间（N>2T）是如何考虑的？：如果分片本身执行失败了，则不会延长分布式锁时间（即70s释放），那"重复执行前一分钟"的逻辑则可以获取到分布式锁重试执行。如果分片本身执行成功了，会延长分布式锁的时间(为大于2倍分片时间，如130s)，这样"重复执行前一分钟"批次这个逻辑也因为获取不到分布式锁而避免重复执行。

关键点2：At least Once

​ 结合上述分析可知，在调度器模块中，只能保证到 at least once 的语义。这是因为实际上没有手段能实现百分之百的分布式事务，即无法保证“（1）触发器完成时间分片作业 +（2）延长分布式锁过期时间”这两个动作整体具有原子性

​ 一种常见的场景是，触发器在分片对应时间范围内轮询时出现宕机，导致一部分任务完成，另遗留少量任务未执行，此时由于触发器不会更新分布式锁的过期时间，导致锁会被其他调度器协程抢占，最终启动新的触发器重复执行分片，从而导致部分任务重复。这个重复问题会留到后续执行器模块进行兜底处理，但至少在调度器和触发器模块的范围内，需要理解目前这样的处理方式只能做到 at least once 而非 exactly once

执行器模块

（1）实现核心

​ 模块核心：真正执行定时任务

​ 流程分析说明：

• （1）执行器由触发器异步启动，一个执行器协程对应于一个定时任务
• （2）执行器首先对定时任务进行幂等去重
• （3）根据消息中的定时器 id，查询到定时器的完整信息
• （4）执行定时任务
• （5）更新 mysql 定时任务执行记录的状态为已执行

（2）关键点分析

问题1：触发器模块已经有了间隔1s的持续轮询，这个轮询是Redis上的实时数据，那么为什么还要每隔1s调度一次？调度器模块是不是可以每隔1分钟调度1次就可以？

​ 理论上是有很多浪费的调度，但也只是拿不到锁就退出了，影响不大。如果一分钟调度一次，则有很多异常情况需要思考处理。例如某一分钟的调度稍有误差，假设 在9:00:00 调度了一次，正常来说下一分钟应该是9:01:00进行调度的，但如果出现误差（在9:00:5999... 时就发生调度了），则可能导致后面 “9:01”这一分钟的任务都调度失败或大量延迟（相当于定时任务在9:00:5999..就触发调度了，而实际本次调度应该要在9:01:00执行，如果通过截取分钟数获取分片数据，那么这次调度的还是“9:00”的分片，因此调度时机如果不准确实际是会影响到后面的调度流程）。所以直接粗暴采用1秒一次，这些问题都不用考虑了。

预期调度分片	预期调度时间	实际调度时间（按分钟调度：异常情况分析）
9:00	9:00:00	9:00:00
9:01	9:01:00	9:00:59.99（调度出现偏差，在这个点触发了，实际调度的还是9:00的分片）
9:02	9:02:00	9:01:59.99（调度恢复正常了，1分钟后再次触发调度，但实际上对比预期9:01分片的调度晚了1分钟左右（59.99s））
9:03	9:03:00	9:02:59.99（以此类推，假设往后调度间隔都正常，后面的分片调度都会比预期调度时间晚1分钟左右）
......	......	......
10:00	10:00:00	9:59:59.99
		10:00:59.99

​ 可以理解为当前分钟的任务分片在第一次轮询的时候就完成了，但为了避免“按分钟调度”的设计下出现上述提到的“误差情况”，因此考虑采用每秒调度一次来缩小这个调度误差范围（将可能存在的分钟级别的延迟缩小到秒级别），虽然可能会出现很多浪费的调度，但实际影响并不大

​ @Schedule定为1分钟，为啥会出现下一次调度提早执行？ =》正常情况是不会出现问题的，但是考虑到定时也是机器在处理，怕没有那么精准，所以留了一点buffer

​ 为什么说浪费？=》分片的规则是按照分钟+分桶的概念进行构建，线程会通过抢占分布式锁来获取指定分片的触发权，抢不到锁的线程则会进入线程池进行等待（所以才会说可能存在很多浪费的调度，因为抢不到锁就退出了）

​ 调度器是一个线程，分时分片（按分钟）+分桶（按桶个数），获取到某分钟的数据，然后每隔1s从上到下遍历“每个桶”，抢占到哪个分片的锁，当前线程就把这个分片当成一个任务交给触发器线程池执行，然后继续尝试获取下一个分片的锁继续执行

4.任务生成模块化设计

migrator 模块

（1）二级存储模型 + 迁移器模块

​ xTimer 中基于 mysql 数据库 + redis 缓存建立二级存储模型，并增设一个迁移器模块(migrator module)根据任务执行时机由近及远进行存储介质之间的迁移同步

（1）一级迁移器模块每间隔一个一级时间步的时长，处理下一个时间步的内容：比如设定一级时间步长为 60 min，当前是 11 点，则迁移器提前开始处理12:00-13:00 这个步长范围内的内容

（2）迁移逻辑：具体工作为全量扫一遍MySQL中的timer表记录，解析出12:00-13:00这个范围内应该执行的定时任务点，在 mysql 执行记录表中添加记录（生成相应节点的任务记录），并在 Redis 中进行批量打点。后续触发器模块在轮询过程中先查询Redis，倘若 Redis 集群出现分片数据丢失，则可以查询 mysql 进行兜底

打点问题

（1）串行打点

串行打点实现方案

​ 串行打点：定时器激活时会首先推算出首次执行的定时任务并存储到Redis zSet 当中，完成首次打点的过程。在这之后，定时器的每一次打点动作会在前一个点的定时任务执行完成后，由执行器模块执行完成。

串行打点存在问题

​ 当前串行打点的方案是比较节省存储资源的，在一定程度上也可以缓解超长过期时间所导致的缓存资源浪费的问题。

​ 然而，在上一个点被触发器模块唤起到执行器模块完成定时任务执行并打好下一个点的过程是需要一定的耗时，假如用户的诉求是创建出一个短间隔高频执行的定时器(例如:1s执行一次)，那么串行打点的方案是无法实现的

（2）批量打点

批量打点实现方案

​ 基于定时器中关于执行时间的定义(cron expr)，推算出一整个批次的执行时间并进行批量打点，这样即可满足短间隔场景的诉求。

批量打点存在问题

（1）基于 cron 表达式推算出来的执行时间点可能漫无边际

​ 解决方案: 因此需要明确批量打点的时间范围边界，将其定义为一级时间步 step1；因此可以每隔一个步长，完成对下一个一级时间步内定时任务的批量打点

（2）用户可能反复对定时器状态进行修改，这样要求频繁对批量的点进行修改，复杂度和工作量都大大提升

​ 解决方案:

​ 首先明确定时器创建后不允许修改定义，只允许作激活和去激活的操作；倘若需要修改定义，可以先删除旧定时器，并重新创建一个新的

​ 其次，遵循只打点不删点的原则。倘若用户将已经完成打点动作的定时器置换为去激活态，同样不删除 zSet 中对应的点，而是留待定时任务被唤起触发后，由执行器协程在查询定时器详细定义时，检查一次状态是否合法，来规避这一问题

​ 最终采用的是批量打点的方式（结合代码实现理解分析，功能实现是简单操作数据库，有些功能点没有全部实现）

（3）方案对比和选型

5.存储设计

存储选型

（1）关系型数据库选型

​ 一般常见的关系型数据库有MySQL、Oracle、SQLServer、TDSQL。关系型数据库普遍具备如下优点:

（1）可靠性强，数据是持久化到磁盘，没有丢失数据的风险

（2）结构规范清晰，每一列数据都有格式和长度规范，一个表中每一行数据的属性都是相同的

（3）支持事务，很多时候多个操作希望要么成功、要么失败，比如扣减库存和记录库存扣减事件这两个操作，不希望出现只有一个成功的情况

​ 软件世界只有平衡、没有银弹，关系型数据也有不足之处，此处说两点核心的、没有歧义的缺点:

（1）关系型数据库性能普遍都不高，和按行存储、维护索引、事务都有关系，可以理解为因为太过规范可靠，所以速度自然快不起来

（2）表结构扩展非常不便，特别上线之后，增减字段都会对线上产生影响

（2）非关系型数据库选型

​ 此处指以键值对形式存储的非关系型数据库，比如Redis、Memcache。这类nosql优点其实就是快，基于内存存储，KV型结构。利用 Redis 自带的 BenchMark做测试，读性能可以10W+，写性能也是7，8W

​ 但这类nosql缺点也很明显，最核心的是可靠性不强，可能会丢失数据，如果数据比较重要那么就不适合用nosql做底层存储

（3）xtimer 选型分析

定时微服务需要存储什么数据？

​ 定时任务（定时器timer）：业务调接口创建的一个定时任务，需求中包含了运行cron表达式，以及任务执行成功后如何回调等信息

​ 单次触发任务（根据定时器timer配置生成的节点任务，对应到每个执行时间节点需要执行的任务记录）：一个cron表达属于周期性任务，例如每天早上9点触发一次。那整个定时任务周期中，触发次数肯定是多次的。 所以需求任务最终会转换成N个单次触发任务进行存储（1-N）

​ 定时任务数据，都是需要是比较精准的，也需要是持久化的，同时也是需要事务的、所以需要比较可靠的数据库。可以进一步对比多种关系型数据库，然后结合业务场景进行择选

选型对比	MySQL	Oracle	SqlServer	TDSQL
运行平台	Linux、Windows	Linux、Windows	Windows	Linux
扩展性	单机	单机	单机	分布式
性能	几千级	几千级	几千级	分布式可扩展
价格	正常	贵	正常	昂贵

​ 对比之下，后端服务跑在linux上比较好，所以不考虑SqlServer；Oracle更多用于工业场景，互联网主流的还是MySQL

​ TDSQL可以看作是腾讯的分布式MySQL，功能和MySQL大部分一样，也完全能支持开发场景，但就是非常贵，一般来说除非有特殊需要，中小团队也不会主动去接入TDSQL。因此最终选择MySQL这个互联网最流行可靠的关系型存储，来做底层数据库

数据处理加速需求

​ 一个定时需求任务整个生命周期中，需要频繁多次的对其进行查询和删除操作。并且基于前面的方案思路，需要对数据进行有序性处理，以及会采取横向纵向等分治策略。所以一来是数据操作频繁，而来数据有灵活的分治需求，所以完全基于关系型数据库没办法满足需求，所以关系型数据库mysql在xtimer的实现中更多是作为核心存储。

​ 除了核心存储，还需要有其他NOSQL存储支持数据的顺序性、横纵向分治等。Redis数据结构比较丰富，相对于Memcache等有天然的优势，并且Redis比Memcache更流行，基本所有后端团队都会应用Redis，所以此处选择Redis

存储结构设计

（1）MySQL 数据存储结构设计

​ t_timer 表中的数据是用户创建的，用户会指定一个cron（周期运行表达式，例如每分钟运行一次），而t_timer_task表中的任务则是根据这个cron生成出来的具体某个时间点的任务表数据

​ 此处的用户概念指的是使用这个框架的业务方（例如某个系统业务）

定时任务表

t_timer 表

字段	类型	说明
timer_id	bigint	主键自增ID
create_time	datetime	创建时间
modify_time	datetime	修改时间
app	varchar(128)	业务方标识（业务方唯一标识）
name	varchar(256)	任务名
status	tinyint	任务状态：‘0新建 1激活 2未激活’
cron	varchar(256)	cron 表达式，用于确定闹钟触发时间
notify_http_param	varchar(8192)	回调上下文

• 核心字段说明
  • notify_http_param：回调上下问题，闹钟时间到点了，就会通过这个回调上下文通知业务“到点该执行业务逻辑了”
  • cron：周期任务的周期表达式设定（系统会通过这个cron配置生成相应执行时间节点的任务数据）
  • status：定时器状态（闹钟状态），定时器初始化为“新建”状态，需由用户手动激活或者关闭

t_timer_task 表

字段	类型	说明
task_id	bigint	主键自增ID
create_time	datetime	创建时间
modify_time	datetime	修改时间
timer_id	bigint	关联的timerId（任务关联的定时器）
app	varchar(128)	业务方标识（业务方唯一标识）
output	varchar(1024)	执行结果输出
status	tinyint	任务状态：‘0待执行 1成功 2失败’
run_timer	bigint	任务开始时间
cost_timer	bigint	误差时间

（2）Redis 数据存储结构设计

单个分片结构：ZSET结构

​ 基于双向分治策略（横向分支：按分钟；纵向分支：按桶）确定分片规则，进而选择合适的存储结构存储分片数据

（1）key：时间+bucket编号（例如2023-10-01 09:02 bucket 01） =》对应分片key概念

（2）value：$timerld $unix时间戳（例如1 1702983567000） =》对应任务列表 （一个分片对应一个ZSET，key作为分片键，value存储多个任务）

（3）score：$unix时间戳（例如1702983567000）

问题：为什么score已经存了时间戳，value还要再存时间戳呢？如果是为了确保任务唯一性的话为什么不直接使用task_id呢？

​ 为了确保任务的唯一性，利用 ZSET 的 value 的唯一性，value 设定为 timerld + 时间戳必须是唯一的，以确保同一个timer在同一个时间点只有一个任务（确保任务的唯一性），即使生成出来也存不进去（数据库层面有幂等性保证，不允许重复插入）

​ 之所以不选用task_id也是考虑到项目引用到MySQL、Redis两级存储，直接生成一个唯一值（timerld+时间戳）可以直接进行两边绑定。而如果依赖于task_id，则Redis上要保存task_id的话就需要先将数据插入MySQL后生成task_id然后再存到Redis上（相当于先去MySQL查一遍了）

扩展问题分析

问题1：事务在xtimer的应用体现在哪些方面？

​ 事务定时项目体现在哪些地方呢？感觉回调成功和修改任务状态需要事务？单纯数据库层面的事务还没发现？

​ =》 这个目前好像确实没用到事务保证，之前设想是批量生成任务的时候做个保证。但是目前有唯一索引之后，没事务也没啥问题。另外设计的时候设想如果需要同时更新 task 和 timer 的时候可能会用到，但目前好想还没有同时更新的场景。但是做方案选型的时候，肯定还是要考虑支持事务的，否则哪天增加新功能，结果因为不支持事务原因切换存储数据库，这会是一个很大的操作成本。

问题2：采用横向纵向分治策略是为什么考虑引入Redis？

​ 请问双向分治策略是需要采用redis 的原因吗？如果只是考虑要双向分治的话，关系型数据库应该也可以实现吧。采用redis的原因是否只有一个：需要对数据进行频繁的操作？（为什么不只用MySQL？）

​ 从理论上分析，如果要实现双向分治也可以单纯使用MySQL来实现，例如数据分块可以为每个块创建一张表（但维护成本较高），或者都落到一张表中通过”指定标识“进行划分（无法做到解耦，数据始终是融合在一起的，没有做到冷热分区）

​ 之所以引入Redis主要基于几方面的考虑：

• 有序性：考虑分时业务场景的数据都是天然有序的，可以根据这一特性进行数据的冷热分区，借助Redis的ZSET存储结构（底层基于跳表实现，检索复杂度从O(n)提升到O(lgo(n))），进一步提升检索效率
• 高精准保证：对比MySQL的检索支持，Redis基于内存操作的高性能特点可以支撑”高频扫描“，而”高频扫描“作为定时任务场景中”高精准“问题的保证
• 支持扩容：Redis支持集群部署架构，可以方便地进行扩容（需注意扩容有效性受限于分片策略，分片:分布式锁是1:1的，因此要有足够的分片提供，才能让更多的线程加入工作，否则其他没有抢到锁的线程（即机器）就会被闲置）

​ 其次考虑到项目技术栈选型的引入成本，MySQL和Redis都是分布式业务场景中比较常用的技术栈，接入成本很低

问题3：项目中已经执行的任务是否要进行清理？例如MySQL中任务表中的数据、Redis中的ZSET？

​ 对于项目中已经执行完成的任务与业务而言已经是”过冷数据“了，因此可以考虑进行清理（这点主要结合实际业务场景进行分析）

• 对于MySQL任务表中的数据：可以进行归档或者清理，释放存储资源
• 对于Redis中的ZSET：没有特意执行删除操作，而是引用Redis的过期机制，待key过期后自动清理
  • 对于过期时间的设定则考虑两方面的影响：一方面是分片策略、一方面是兜底策略
    • 分片策略：分片的有效执行时间（1分钟），起码这1分钟内worker要确保可以处理完拿到的这个”分片（分时+分桶）“
    • 兜底策略：考虑”重试上一分钟“、”最终兜底方案“
      • ”重试上一分钟“：重试上一分钟进行兜底，因此分片过期时间多设置1分钟
      • ”最终兜底方案“：例如基于脚本扫描一些异常情况下还没生成的任务，例如每隔1小时扫描一遍

​ 最终的过期时间设定受限于上述因素的影响，综合得到一个过期时间的设定

问题4：分库分表的设计

​ =》目前xtimer项目设计没有实现分库分表，可以作为一个待优化点进行扩展补充

6.服务接口设计（todo）

​ 接口请求基路径baseUrl：http://127.0.0.1:8081/api

👻获取任务配置列表信息

接口实例

• 请求地址：/xtimer/createTimer

• 接口方法：POST

• 请求参数：JSON

  参数	类型	是否必填	说明
  app	string	是	应用名
  name	string	是	定时器名称
  cron	string	是	cron表达式
  notifyHTTPParam	NotifyHTTPParam	是	http 通知协议参数
  notifyHTTPParam.url	string	是	目标url
  notifyHTTPParam.method	string	是	http方法：GET/POST/DELETE/PATCH
  notifyHTTPParam.header	Map<String,String>	否	http 请求头参数
  notifyHTTPParam.body	string	否	http 请求头体json字符串

• 响应体：（参考响应参数说明）

  字段	类型	备注
  code	int	错误码：0-正常；其他-有错误
  msg	string	错误描述信息
  id	long	定时器唯一id

  {
      "msg": "ok",
      "code": 0,
      "result": {
          "id": ""
      }
  }
  

👻激活定时任务

接口实例

• 请求地址：/xtimer/enableTimer

• 接口方法：GET

• 请求参数：

  参数	类型	是否必填	说明
  id	long	是	定时器唯一id
  app	string	是	所属应用名

• 响应体：

  {
      "msg": "ok",
      "code": 0,
      "result": {
          "id": ""
      }
  }
  

👻删除定时任务

接口实例

• 请求地址：/xtimer/delTimer

• 接口方法：DELETE

• 请求参数：

  参数	类型	是否必填	说明
  id	long	是	定时器唯一id
  app	string	是	所属应用名

• 响应体：

  {
      "msg": "ok",
      "code": 0,
      "result": {
          "id": ""
      }
  }
  

定时微服务核心问题

1.如何解决定时微服务关键问题

👻高精准问题

如何解决高精准问题的?

​ 任务触发时间的误差=扫描间隔时间+任务执行时间

​ 高频扫描(每隔1秒)：通过基于ZSET数据的顺序性设计，以及整体的分治策略设计，使得基于单个分片的单次判断耗时不会太长，同时即便进行短时高频的查询扫描，也不会带来太大的性能开销（因为Redis性能高）。 所以即便每个分片每隔一秒进行定时扫描也不会有问题，任务的触发时间误差是跟扫描间隔直接相关的、例如扫描间隔1秒，那么最差情况单个任务至少误差1秒；

​ 并发执行任务：如果同一时间有大量任务需要执行，如果所有任务都排队执行，那最后执行的任务的误差需要加上前面所有任务执行时间之和，那肯定有问题。本方案中是采用了并发执行任务的方案，让批量任务可以尽可能的并发执行，减少等待时间，提高触发精准度。

👻高负载问题

​ 为了提高系统单位时间处理任务的数量，那必须得提高并发度。

​ 分治策略：将数据分散到不同的分片里面，让不同的线程去跟进分片的处理，提高了并发度。让不同分片内的任务可以并发处理

​ 线程池：单批次任务处理过程中，采用线程池技术，进一步加速了任务的执行速度。同时线程池本身带有线程管理能力，使得任务能够尽可能并发快速执行的同时，又不会带来线程泛滥拖垮系统的问题（对比1个任务一个线程方案，引入线程池后可以让线程池中的一个线程反复执行多个任务）

👻异常任务处理

​ 针对系统中可能出现的异常任务的问题，主要从以下几个方面来考虑解决

• 记录任务执行状态：这个是前提，只有知道任务处于什么状态，才能据此判断一个任务是否异常

  • （a）一个任务状态是"执行失败"；
  • （b）一个任务处于"待执行"状态，同时又超过了预期运行时间一定时长(例如30秒)；

• 定时脚本：单独运行一个定时脚本，每5分钟跑一次。脚本逻辑是扫描mysql数据库，将异常任务检索出来后触发重试执行

• 人工介入：如果一个任务超过预期执行时间，30分钟后还处于失败状态，那就人为介入判断处理（例如定位问题R后，通过维护接口修改任务状态，或者调整任务信息等）

定时脚本：如何实现周期运行的定时脚本

​ 参考xtimer现有的定时脚本运行案例，例如迁移模块的周期运行、调度模块的周期运行，其执行逻辑就是筛选数据库task中符合条件的task，然后丢给executor模块执行。参考@Scheduled相关内容

​ 针对异常任务处理，如果采用通过定时脚本处理的方式，如果任务执行出现异常，由于脚本执行周期是5分钟跑一次，那么就会存在一些定时任务延迟5分钟才执行的情况（例如定时任务第一次执行失败，后面被扫描到重新执行，这中间存在5分钟的时间差）

2.幂等性设计原则：如何确保任务不重复执行

幂等性概念核心

（1）什么是幂等性？

​ 在数学中，幂等函数为f(x)=f(f(x))。举个例子，求绝对值的函数就是幂等函数abs(x)= abs(abs(x))。可以看到这个函数无论执行多少次，结果都是一样的。

​ 在计算机领域，幂等性也是相似的含义:简单来说，即同样的操作无论执行多少次，结果都一样，也就是说只有第一次造成了数据的改变

​ 拿转账举例，同一笔转账请求，即使因为网络波动或者失败重试重发了多次，但最终实际的金额流转只会有一次。

（2）幂等性原则

​ 幂等性是后端设计一个重要原则，因为网络是不可靠的，前置操作也是不可靠的，也就是说一个相同的请求，总有概率会重放到你的服务，这种情况是需要考虑的。一般而言，可以从接口层面来保证幂等性，一个接口可重入的基础，就是它底层操作都是可重入的。

（3）幂等性实现方式

方式1：依托唯一key

​ 依托唯一key：根据唯一key进行可重入校验

​ 底层存储基本都支持唯一Key。比如MySQL（支持定义唯一Key），如果是插入时发现Key已经存在，会有特别的错误信息，通过这个错误信息就可以知道这个操作是否已经执行过，然后根据业务需要进行返回。

​ 举个例子说明，可以在MySQL创建一个表，设置num（编号）为唯一key，然后执行插入操作进行测试（如果插入重复的num则抛出异常）。因此在MySQL中通过唯一key限制，是无法重入插入数据的，且会提示相应的错误。无论是Java还是Go，都会暴露出对应鲜明的错误或封装

# 创建测试表
CREATE TABLE `t_redo_test`
(
    `id`       bigint(20) NOT NULL AUTO_INCREMENT COMMENT '主键id',
    `num`      VARCHAR(128)  COMMENT '编号',
    `status`   int(11)  NOT NULL COMMENT '状态',
    `create_time`         datetime not null DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `modify_time`         datetime not null DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '修改时间',
    PRIMARY KEY (`id`),
    UNIQUE KEY `idx_num`(`num`)
) ENGINE = InnoDB
  DEFAULT CHARSET = utf8mb4
  COMMENT '幂等性重入测试表'
  COLLATE = utf8mb4_unicode_ci;
  
# 插入数据测试
insert into t_redo_test(num,status) values(1001,1); # Affected rows: 1
insert into t_redo_test(num,status) values(1001,2); # 1062 - Duplicate entry '1001' for key 't_redo_test.idx_num'

方式2：依托状态

​ 依托状态：状态更新覆盖，通过状态来进行判断。如果状态已经发生改变，则影响行数为0

​ 结合例子说明：

select * from t_redo_test;
# 1	1001	1	2024-08-15 15:37:40	2024-08-15 15:37:40

​ 更新操作1：基于上述结果，库中已经存在一条num为1001、status为1的数据，对该条数据执行更新操作（将status从1变为9），更新操作成功执行

update t_redo_test set status = 9 where num='1001'; # 更新成功
select * from t_redo_test;
# 1	1001	9	2024-08-15 15:37:40	2024-08-15 15:46:53

​ 更新操作2：将num为1001、status为1的数据的status修改为5，更新无效（因为在更新操作1中status被改成了9，此处修改操作加入限制条件导致最终影响行数为0）。这种思路概念是基于CAS思想，本质上是先通过比较期待值，再决定是否进行后续操作（也可以理解为是乐观锁的一种体现（mysql的version乐观锁思想），但CAS概念更契合）

update t_redo_test set status = 9 where num='1001' and status = 1; # 无效更新，影响行数为0
select * from t_redo_test;
# 1	1001	9	2024-08-15 15:37:40	2024-08-15 15:46:53

方式3：依托额外记录

​ 依托额外记录：有时候表里面没有合适的唯一Key来支撑，也没有状态，但是又想让一个请求不要重复执行，那怎么办？此时可以单独做一个表，理解为请求记录表，即通过记录请求ID来实现不可重复插入。

xtimer 定时微服务的幂等性处理

todo：幂等处理评论问题：重复执行的判断场景分析

幂等去重（避免重复执行）

（1）在执行器模块的视角中，对于二维分片的概念是无感知的，接收到的每一笔定时任务可以通过其定时器id 和执行时间戳全局唯一的确定一个定时任务；

（2）基于定时器id 和执行时间戳检索 mysql 中的定时任务记录表（t_timer_task），准确查询出定时任务是否属于重复执行，若已重复则停止执行；

​ 补充说明：到此为止，兜底措施已经阐述完毕，然而仍然有异常边界情况可能导致这个流程失效。事实上，在分布式场景中，exactly once 的语义永远无法完美触达，只能尝试通过各种手段进行补偿和兜底，尽可能降低出现错误的概率以及发生错误所带来的损失

​ xtimer 的幂等性处理是采用“方式1：依托唯一key”的方式实现