IM专题：分层架构IM系统（13）—时间轮方案实现

在上一篇 IM专题：分层架构IM系统（12）—消息收发逻辑实现文章中，我们分析了 IM 的分层架构中的消息收发逻辑；为了实现消息的 “及时性” 和 “可靠性”，将整个消息收发流程划分为三个阶段：生产消息阶段、推送消息阶段和确认消息阶段。

确认消息阶段，需要完成客户端接收到消息后向服务端回复确认的过程；Logic 推送消息后，等待一段时间（通常15秒），若在 15 秒内没有接收到客户端的 Ack 包，则认定客户端没有收到该消息，客户端处于离线状态。

对每一条推送的消息， Logic 都需要等待 15 秒；如果 15 秒内有 10 万条消息被推送，Logic 需要维护 10 万个等待的流程，每一个流程等待 15 秒；咋一听，在实现的时候，这是一个非常消耗资源的工程，有什么轻量级的实现方案呢？

在上述这样的一个业务场景中，我们通常采用 “时间轮” 轻量级的解决方案，见下图。

在时间轮解决方案中共需要三个数据结构：

第一个结构是一个循环队列，作为不断循环的时间轮；该时间轮的指针，每秒钟向前走一格，走一圈是一个完整的等待客户端回复Ack的超时周期（图中超时时间是 13秒）；
第二个结构是一个消息维度的 key-value 映射 map<msg_id, 时间轮时间刻度>，该 map 的 key 是消息 msg_id，value 是 Logic 推送该条消息时时间轮指针所指向的时间刻度；
第三个结构是一个时间维度的 key-value 映射 map<时间轮时间刻度， msg_id 列表>，该 map 的 key 是时间轮时间刻度，value 是 Logic 在这个时间刻度下推送的所有的消息列表。

很明显，第二个结构和第三个结构是双向映射，可以很方便地根据 msg_id 定位到时间轮时间，也可以根据时间轮时间定位到 msg_id。

时间轮方案的基本处理逻辑描述如下：

当 Logic 推送一条消息到客户端时，需要将消息的msg_id和当前时间刻度分别写入到上述的两个 map 中；在时间指针旋转一周超时之前，如果客户端回复了 Ack，则需要从上述两个 map 中删除msg_id和时间刻度信息；时间指针每指向新的时间刻度时，该时间刻度中所有的消息 msg_id 列表就是超时未回复 Ack 包的，需要做逻辑处理。

这样描述可能比较抽象，我们举一个例子：

假设时间轮指针指向了当前时间刻度 2，在这一秒内，Logic 向三个客户端分别推送了三条消息，msg_id 分别是 101、102 和 103 ，此时需要在第一个 map 中分别写入 <101, 2> ， <102, 2>，<103, 3>，在第二个 map 中写入 <2, [101, 102, 103]>；
三秒后，此时时间轮指针指向了当前时间刻度 5，此时 msg_id = 102 的消息有对应的 Ack 包产生，那么需要先从第一个 map 中删除元素 <102, 2>（同时记录下时间刻度 2，方便后续操作），再从第二个 map 中删除 102 的信息，删除后的map为 <2, [101, 103]>；
九秒后，在时间轮指针指向当前刻度 2 时，此时第二个 map 中，key 是 2 的所有的 msg_id 列表，即 [101, 103]，就是超时未回复 Ack 包的消息列表。

如果将时间轮方案作为一个独立的组件进行实现的话，该组件只需要包括四个方法即可，如下：

//初始化时间轮，准备循环队列、消息维度 Map、时间维度 Map 等三个数据结构
func InitTimeWheel()

//添加新消息，向两个 Map 中写入消息相关数据
func AddNewMsg(msgId uint64）

//删除消息，从两个 Map 中删除消息相关数据
func DelMsg(msgId uint64)

//时间轮任务，循环执行任务：每隔一秒拨动时间指针，对超时消息做回调逻辑处理
func WheelTask()

时间轮方案在具体落地时，有两种实现方式：内存式和 Redis 式。

一、内存式

内存式，即时间轮数据完全保存在 Logic 的本地内存中，见下图。

我们在前面的文章 IM专题：分层架构IM系统（1）— 架构解读中分析过，Logic 是业务逻辑层的计算节点，属于无状态化的服务节点。时间轮直接在 Logic 内存实现后，客户端回复的 Ack 包也必须由 Entry 路由回原 Logic 节点，此时 Logic 成为有状态化的服务节点；而且时间轮数据保存在内存中，在 Logic 节点重启后，数据会丢失，所以对于 “内存式” 时间轮实现方案，服务的可用性是一大问题。

二、 Redis 式

Redis式，即将时间轮数据从本地内存中脱落，保存在中央 Redis 中；这和用户在线数据由中央存储保存的理念是一致的。Redis 式见下图。

时间轮的三个数据结构（循环队列、消息维度Map、时间维度Map）完全由 Redis 实现。

需要注意，虽然 Logic 本地内存中不单独存储数据，但 Logic 仍然不是无状态化节点；因为在时间轮操作中，有一个很特殊的操作：每隔一秒钟，拨动时间轮指针；这步操作只能有一个节点进行，如果四个 Logic 节点都参与拨动时间轮指针，必将导致混乱。

那么由哪一个 Logic 节点参与拨动时间指针的操作呢？

很明显，通过选主进行即可。在当前架构中，通过 Redis 的 Setnx 可以非常方便地选择出专门拨动时间轮指针的 “主Logic” 角色。

时间轮实现方案的 “Redis式” 比 “内存式” 可用性更高，也更趋向于服务节点的无状态化。

最后，总结文中关键：

时间轮方案中共需要三个数据结构：循环队列、消息维度的 Map、时间维度的 Map；
时间轮组件需要包括四个方法：InitTimeWheel()、AddNewMsg(msgId uint64）、 DelMsg(msgId uint64)、WheelTask()；
时间轮方案在落地时有两种方式：内存式和 Redis 式， Redis 式比内存式可用性更高，也更趋向于服务节点的无状态化。

作者：棕生 | 来源：公众号——架构之魂

原文链接：https://mp.weixin.qq.com/s/sa6ceUkNx4f3uQrJtrJieQ