Kyle's Notebook

可靠的分布式计时器(译)

Word count: 2.4kReading time: 8 min
2021/08/10

原文链接:https://0x709394.me/How-To%20Design%20A%20Reliable%20Distributed%20Timer

在最近的几个月,作者一直在维护一个遗留的、用于处理一些重要的支付业务(10 亿个/天,峰值 2 万个/秒)的分布式计时器。尽管这是一段古老且充满黑魔法的代码,但也能看出设计者深厚的洞察力、设计之巧妙,因此作者把设计思路总结为下文。

不包含实际代码,也许只有数值和图解,毕竟一图胜千言。

可靠的分布式计时器

算法描述

实现计时器的算法有红黑树、最小堆和时间轮等,其中最有效、最常用的算法是时间轮,因此备受关注。

基于时间轮的计时器建模,分为两个内部操作:

  • 单位计数:类似时钟的每个“滴答”。 如果设置计时器的粒度是 T 个时间单位(比如 1s),则每 T 个时间单位就会发生一次单位计数。这会检查是否存在未完成、已过期的计时器,是则把它删除并调用过期处理。

  • 到期处理:调用用户提供的回调函数(或其他用户请求操作,取决于模型设计)。

简单时间轮

即维护一个大的定时轮,其中有 8 个槽位,每个槽位挂载即将到期的任务。假设每个槽位表示 1s,则当前槽位就是 slot1,如果要添加一个需要 2s 后触发的任务,则这个任务就会被插入到 slot3 中。

img

单位计数的时间复杂度为 O(1)。但由于只有 8 个槽位,无法添加一个 20s 后启动的任务。如果有大周期的定时任务,则必须维护有大量槽位的时间轮,这需要指数级的内存。

哈希时间轮

在以上设计中,如果计时器周期较大,则会消耗大量资源。经过改进后,可以使用散列代替每个时间单位使用一个槽位的做法。构造一个固定槽位数的环形缓冲区(比如 8 个)。 如果当前槽位为 0,要存储 3s 后的任务,可以插入 slot3;如果想要存储 9s 后的任务,则可以插入 slot1(9 % 8 = 1)。

img

单位计数的时间复杂度为 O(1) - O(n),这是一种以时间换空间的权衡策略。

分层时间轮

以上两种做法具有时间或空间效率上的缺点。Varghese 和 Lauck 在 1987 年曾发表过一篇论文,介绍了 分层计时轮(Hierarchical Timing Wheels),为了更好地理解它,可以参考旧水表:第一级轮(秒轮)旋转一圈,触发第二级(分轮)打一个槽,第三级(时轮)同理。 因此要表示一天(60*60*24s)则需要 60+60+24 个槽位;要表示一个月,则只需要一个有 30 个槽位的四级轮(月轮)。

img

单位计数的时间复杂度为 O(1) - O(n)。

单位计数

介绍完时间轮算法,回到设计可靠的分布式计时器的话题,其中决定如何存储计时器任务至关重要。需要权衡实现复杂度和时间、空间,因此选择散列时间轮算法。

插入任务

使用 TableKV 实现散列时间轮算法:假设有 10m 个桶,当前时间为 2021:08:05 11:17:33 +08=(UNIX 时间戳:1628176653)。有一个任务将在 10s 后触发(``start_time = 1628176653 + 10,或 start_time = 1628176653 + 10 + 100000000即 100000010s 后),这些任务都将存储到桶start_time % 1006060030` 中。

img

取出任务

随着时间到了 2021:08:05 11:17:43 +08(UNIX 时间戳:1628176663),需要通过计算桶号来从槽位中取出任务:current_timestamp(1628176663) % 100000000 = 2817663 定位桶号,在桶 28176663 中找到满足 start_time <= current_timestamp 的任务,即为所有预期的到期任务。

img

全局时钟与锁

当在到达当前时间时获取所有到期任务,如果服务在分布式系统上运行,通常会有多个主机(物理机或 docker),在其机器上有多个 current_time。不能保证多台主机的所有时钟都由同一个网络时间服务器同步,则所有时钟可能会略有不同。

img

为了得到正确的时间,需要维护一个单调的全局时钟(也有其它方法处理时间和顺序)。 由于只关心 Unix 时间戳,可以维护一个由 Unix 时间戳表示的全局系统时钟。所有机器每秒请求全局时钟以获取当前时间,再获取到期得任务。

但又有新的问题:如果所有机器都可以获取到期任务,将会导致这些任务被处理多次。因此还需要一个互斥锁来保证只有一台机器可以获取到期任务。可以使用乐观锁策略实现全局时钟和互斥锁。

img

步骤如下:

  • 所有机器获取带版本的全局时间戳(tA)。

  • 所有机器都增加时间戳(tB)和更新版本(乐观锁,只有一台机器会成功)。

  • 获得互斥锁的机器被授权去取 tA 的过期任务,其他没有获得互斥锁的机器被挂起等待 1s。

  • 基于 tB 循环回到步骤 1。

可以将不断获取锁和获取到期数据的功能封装在一个 scheduler 组件中。

过期处理

用于调用用户提供的回调函数或其他用户请求的操作。在分布式计算中,通过 RPC 执行一个过程调用是很常见的,比如在计时器任务到期时发起一个 RPC 请求,从计时器服务到回调服务。因此在触发计时器任务时,调用者需要把参数和服务信息提供给计时器。

可以将服务元信息和参数数据打包并序列化为二进制数据,发送给计时器。 当从插槽中拉出数据时,定时器可以重构 Request/Response/Client 类型并设置为自定义数据,然后直接执行即可。

img

如果需要触发的过期任务很多、要尽可能多地处理,可以创建线程池、进程池、协程池来并发执行 RPC。

服务解耦

如果回调函数包含大量操作(100ms+),即使已经有线程/进程/协程池来处理定时器任务也难免会宕,导致吞吐量下降。

img

使用消息队列可显着简化解耦服务编码,同时提高性能、可靠性和可扩展性。

通常将消息队列与发布/订阅的消息传递设计模式结合,计时器可将任务数据发布为消息,并订阅相同主题的消息,使用消息队列作为缓冲区。在订阅者中 RPC 客户端执行回调请求。

img

此时计时器的状态机如下:

img

有了消息队列,就能实现缓冲、重试或批量工作,并为工作负载削峰。

高可用问题

错过到期任务

调度进程被关闭、崩溃或其他未知问题可能会导致任务错过到期。定位遗漏的任务并重新执行是一项重要的工作。由于使用全局 current_timestamp 获取到期任务,可以用另一个调度程序来使用 delay10mintimestamp 来获取错过的到期任务。

img

为了在任务集合中找到错过的到期任务,需要设置一个范围(延迟 10min - 当前时间),并在批量地 cross 桶查找。找到错过的任务后,计时器再将它们作为消息发布到消息队列。一些开源分布式定时器项目(如 Quartz)提供了处理丢失任务的指令:Misfire。

如果 NoSQL 组件不支持 find-cross-buckets 功能,还可以逐个查找范围内的所有桶。

回调执行错误

由于分布式系统是无共享系统,其通过消息在网络中进行通信(异步或同步),由于网络不可靠,调用用户提供的回调时如果网络暂时中断或回调服务暂时关闭,RPC 请求可能会失败。

可利用重试处理暂时性错误(暂时出现、可能很快消失)。通过允许系统重复发送请求直到得到明确的响应来帮助实现弹性。利用消息队列可获得免费的重试能力,同时计时器也可以处理用户请求重试。

img

总结

综上所述,计时器的整体架构如下:

  • 添加附带指定元信息和任务信息的计时器任务。

  • 通过散列时间轮算法将任务插入到桶中(状态设置为 pending)。

  • 时间同步调度器尝试获取锁并获取全局当前时间。

  • 取锁调度器获取预期的到期任务数据。

  • 使用线程池将任务数据作为消息发布到消息队列,将任务状态设置为 delivered。

  • 消息订阅者从消息队列拉取消息。

  • 向回调服务发送 RPC 请求,并设置任务状态为 success 或 fail。

  • 如有必要则执行重试。

img

参考

CATALOG
  1. 1. 可靠的分布式计时器
    1. 1.1. 算法描述
      1. 1.1.1. 简单时间轮
      2. 1.1.2. 哈希时间轮
      3. 1.1.3. 分层时间轮
    2. 1.2. 单位计数
      1. 1.2.1. 插入任务
      2. 1.2.2. 取出任务
    3. 1.3. 全局时钟与锁
    4. 1.4. 过期处理
    5. 1.5. 服务解耦
    6. 1.6. 高可用问题
      1. 1.6.1. 错过到期任务
      2. 1.6.2. 回调执行错误
    7. 1.7. 总结
    8. 1.8. 参考