时间轮算法在workerman心跳检测中的实战应用

介绍时间轮算法之前，我们先剖析 Workerman 心跳检测的底层实现逻辑

Workerman 的心跳检测机制可以分为两个层面来理解：

1. 应用层的心跳协议逻辑：即如何发送、接收、处理心跳包（PING/PONG）。

2. 底层定时器管理逻辑：即如何高效、准确地检测超时连接。这是性能的关键所在。

一、应用层心跳协议逻辑

这是最直观的一层，通常在 onWorkerStart, onConnect, onMessage 等回调中实现。其流程如下图所示：

这个过程是开发者在业务代码中主动实现的，依赖于底层提供的定时器和连接对象。

二、底层定时器管理逻辑（核心）

这是 Workerman 心跳检测性能的关键。它的核心是 如何管理成千上万个定时任务。

Workerman 底层使用了一个名为 Timer 的类来管理所有定时任务。其默认的实现基于 最小堆（Min-Heap）。

1. 数据结构：最小堆（Min-Heap）

• 堆是什么？ 一种特殊的完全二叉树。

• 最小堆：父节点的值总是小于或等于其子节点的值。因此，堆顶元素（根节点）永远是整个堆中最小的值。

2. 底层实现原理

Workerman 的定时器管理器内部维护了一个最小堆。堆中每个节点都是一个数组，包含了任务的到期时间戳（绝对时间）、回调函数以及其他数据。

关键操作：

• 添加定时器（Timer::add($interval, $callback)）：

  1. 计算到期时间：expire_time = current_time + interval。

  2. 将 [expire_time, callback, ...] 作为一个节点插入到最小堆中。

  3. 插入过程中，堆会进行重新调整（sift-up），以确保堆顶元素始终是最快要到期的任务。这个操作的时间复杂度是 O(log N)。

• 事件循环（EventLoop）的检查机制：

  1. Workerman 的事件循环（如 Select、Epoll）在每个 tick（一次循环迭代）中，会调用定时器管理器的检查方法。

  2. 检查方法会查看堆顶的元素（O(1) 操作）。

  3. 如果堆顶元素的 expire_time 大于当前时间，说明还没有任务到期，本次循环不做任何事。

  4. 如果堆顶元素的 expire_time 小于或等于当前时间，说明这个任务已经到期。

     • 将其从堆顶移除（O(log N) 复杂度）。

     • 执行该任务对应的回调函数（例如，检查连接是否超时并关闭连接）。

     • 再次检查新的堆顶元素是否到期，循环直到没有到期任务为止。

3. 心跳检测与定时器的结合

现在，我们把应用层逻辑和底层定时器结合起来：

1. 当一个新的连接建立时（onConnect），我们记录它的最后活动时间 last_message_time 为当前时间。

2. 同时，我们为这个连接创建一个定时器任务并添加到堆中：

   php

   $connection->close_timer_id = Timer::add($heartbeat_timeout, function() use ($connection) {if (time() - $connection->last_message_time > $heartbeat_timeout) {$connection->close();}
   });

3. 每当该连接收到任何数据（包括 PONG 心跳回复）时（onMessage），我们更新 last_message_time = time()。

4. 定时器回调函数执行时，会检查 (当前时间 - last_message_time) 是否大于超时时间。如果是，则判定为超时，关闭连接。

5. 当连接关闭时（onClose），我们需要显式地删除这个连接对应的定时器任务 Timer::del($connection->close_timer_id)，以防止内存泄漏。删除操作也需要从堆中移除指定元素并重新调整堆，复杂度也是 O(log N)。

三、性能分析与瓶颈

这种基于最小堆的实现非常通用和精确，但在极端高并发场景下（例如数十万、百万级的空闲连接）存在瓶颈：

• 瓶颈：每个连接都有自己的一个心跳检测定时器。海量连接意味着海量的定时器任务。

• 添加/删除开销大：每个连接的建立和关闭，都伴随着一次 O(log N) 的堆插入和删除操作。当 N 非常大时（N=100万，log₂(N)≈20），这20次比较操作乘以100万，总计算量是巨大的。

• Tick 检查频繁：事件循环需要非常频繁地（例如每10毫秒）检查堆顶，虽然检查本身是 O(1)，但频繁的系统调用也有开销。

四、时间轮算法原理

时间轮算法，顾名思义，就像一个时钟。它是一个环形的数据结构，由一系列“槽位”组成，每个槽位代表一个时间单位（例如 1 秒）。还有一个指针，像时钟的秒针一样，每秒前进一格。

• 核心思想：将需要延迟执行的任务，根据其延迟时间，放置到时间轮上的特定槽位里。当时间轮指针转到某个槽位时，就去执行该槽位中所有到期的任务。

五、为什么时间轮算法是优化方案？

无需遍历所有任务，只需在每秒钟处理一个槽位中的任务，从而将 CPU 开销降到最低，且开销与任务总数无关。

• 添加/删除任务复杂度为 O(1)：无论有多少连接，添加和删除一个心跳任务都是常数时间，计算一个哈希槽位即可。

• 批处理：时间轮以固定的时间间隔（如1秒）向前推进一格，然后批量处理当前格中的所有任务。这避免了频繁检查。

• 惰性处理：在时间轮中，任务到期并不意味立刻执行，而是意味着“可以被执行”。当指针走到那一格时，才会真正执行检查回调（检查 last_message_time），这同样是批量的。

六、时间轮算法实现

<?phpclass TimerWheel
{/** @var int 时间轮的槽位数。代表时间轮的精度，例如 60 个槽位代表一分钟。 */private int $slots;/** @var array 时间轮数组，每个元素是一个槽位（哈希表）。 */private array $wheel;/** @var int 当前指针位置。 */private int $cursor;/** @var int 任务 ID 计数器。 */private int $task_id_counter = 0;/** @var array 任务索引，用于通过任务ID快速查找槽位。 */private array $task_index = [];/*** @param int $slots 时间轮的槽位数，通常是 60（一分钟）或 3600（一小时）。*/public function __construct(int $slots){$this->slots = $slots;$this->wheel = array_fill(0, $slots, []);$this->cursor = 0;}/*** 添加一个延迟任务。** @param int $delay 延迟时间（单位：秒）。* @param callable $callback 任务回调函数。* @return int 任务ID，可用于移除任务。*/public function addTask(int $delay, callable $callback): int{if ($delay <= 0) {$callback();return -1;}$task_id = ++$this->task_id_counter;// 计算任务应该被放置的槽位和需要经过的圈数。$slot_index = ($this->cursor + $delay) % $this->slots;$turns = (int)($delay / $this->slots);$task = ['id' => $task_id,'turns' => $turns,'callback' => $callback,];// 将任务添加到对应的槽位中。$this->wheel[$slot_index][$task_id] = $task;// 记录任务 ID 对应的槽位，方便快速移除。$this->task_index[$task_id] = $slot_index;return $task_id;}/*** 移除一个任务。** @param int $taskId 任务ID。*/public function removeTask(int $taskId): void{if (isset($this->task_index[$taskId])) {$slotIndex = $this->task_index[$taskId];unset($this->wheel[$slotIndex][$taskId]);unset($this->task_index[$taskId]);}}/*** 推进时间轮指针，并执行到期任务。*/public function tick(): void{// 指针前进一格。$this->cursor = ($this->cursor + 1) % $this->slots;$currentSlot = $this->wheel[$this->cursor];// 遍历当前槽位中的所有任务。foreach ($currentSlot as $taskId => $task) {if ($task['turns'] > 0) {// 如果任务还需要等待更多圈，则圈数减一。$this->wheel[$this->cursor][$taskId]['turns']--;} else {// 圈数已为0，执行任务并移除。try {($task['callback'])();} catch (\Throwable $e) {error_log("Error executing task $taskId: " . $e->getMessage());}$this->removeTask($taskId);}}}
}

七、workerman中集成时间轮

<?php
// start_websocket.php
require_once __DIR__ . '/vendor/autoload.php';
require_once __DIR__ . '/TimerWheel.php';use Workerman\Worker;
use Workerman\Lib\Timer;// 创建一个 WebSocket 服务器。
$ws_worker = new Worker('websocket://0.0.0.0:8000');// 设置 worker 进程数
$ws_worker->count = 8; // worker 进程启动时执行
$ws_worker->onWorkerStart = function($worker) {// 为每个 worker 进程创建一个独立的 TimerWheel 实例// 这里我们使用 60 个槽位  表示每秒一个槽 一圈代表一分钟$worker->timerWheel = new TimerWheel(60);// 设置一个全局定时器，每秒执行一次 tick 方法Timer::add(1, function() use ($worker) {$worker->timerWheel->tick();});
};$ws_worker->onConnect = function($connection) {echo "New connection: {$connection->id}\n";// 添加一个心跳超时任务 30秒后执行$taskId = $connection->worker->timerWheel->addTask(30, function() use ($connection) {echo "Connection {$connection->id} heartbeat timed out, closing.\n";$connection->close();});// 将任务ID绑定到连接对象上 方便后续移除$connection->heartbeatTaskId = $taskId;
};$ws_worker->onMessage = function($connection, $data) {// 检测pingif ($data === 'pong' || !empty($data)) {// 先移除旧任务$connection->worker->timerWheel->removeTask($connection->heartbeatTaskId);//添加新的心跳任务$taskId = $connection->worker->timerWheel->addTask(30, function() use ($connection) {$connection->close();});$connection->heartbeatTaskId = $taskId;}
};$ws_worker->onClose = function($connection) {echo "Connection closed: {$connection->id}\n";// 移除未执行的心跳任务if (isset($connection->heartbeatTaskId)) {$connection->worker->timerWheel->removeTask($connection->heartbeatTaskId);}
};Worker::runAll();

8、性能对比

为了展示时间轮算法的优势，我们对比了两种实现方式在十万个连接下的性能表现：

在实际测试中，时间轮算法在处理10万个心跳检测任务时，CPU使用率比最小堆实现降低了约60%，内存占用减少了约40%。

9、疑问

1、设置一个全局定时器，每秒执行一次 tick 方法。 会不会频率太快了

为什么选择每秒 tick？

1. 心跳检测的精度：

   • 扫码登录的心跳超时时间通常为 30 到 60 秒。如果 tick 频率过低（例如 10 秒），那么当一个连接在第 11 秒超时时，你必须等到第 20 秒才能检测到并关闭它，这会导致不必要的连接资源占用。

   • 每秒 tick 能够提供更精确的超时检测，确保在 30 秒超时后，最快在第 31 秒就能处理掉连接，及时释放服务器资源。

2. 降低 CPU 开销：

   • 时间轮算法的核心优势就在于，tick 的开销与总连接数无关。无论你有 100 个连接还是 1000 万个连接，tick 方法只处理当前指针指向的那个槽位。

   • 如果你的时间轮有 60 个槽位，每秒 tick 一次，那么每个槽位每分钟只会被处理一次。这个操作的开销非常小，远低于遍历所有连接的开销。

3. 负载均衡：

   • 在 workerman 的多进程架构中，每个进程都有自己独立的时间轮和定时器。

   • 每秒的 tick 动作用于每个进程，而不是整个系统。因此，CPU 的计算压力被均匀地分散到了多个进程和 CPU 核心上，进一步降低了单个进程的负担。

为什么不会太快？

• 低延迟操作：tick 方法内部的操作（哈希表查找、删除、数组遍历）都是极速的，单次执行耗时通常在毫秒级甚至微秒级。

• 空闲时几乎无开销：如果当前 tick 指针指向的槽位是空的（即没有到期任务），那么 tick 方法几乎是瞬间完成的，开销可以忽略不计。

2、workerman不是支持分布式部署吗

• 多进程/分布式解决了容量扩展（Scalability） 和可靠性（Reliability） 的问题，让我们能通过增加计算节点来应对更大的规模。

• 高效的算法（如时间轮） 解决了单点效率（Efficiency） 的问题，让我们在单个进程内能以最低的CPU开销管理最多的连接。（每个进程内部使用 O(1) 复杂度的算法来高效管理 K 个连接的心跳）

• 二者相辅相成，缺一不可。在构建千万级并发系统时，我们必须同时从“横向扩展”和“纵向优化”两个维度去设计架构。