使用epoll超时实现定时器的时间轮同步偏差问题咨询

问题根源 #

你遇到的核心问题是epoll超时设置与时间轮槽位更新不同步：当当前时间临近槽位切换点时，直接设置epoll超时为下一个事件的间隔，会导致休眠结束后跳过中间槽位，遗漏本该触发的定时器事件。

修复方案 #

不需要放弃时间轮，只需调整epoll超时的计算逻辑，确保每次休眠不会跳过时间轮的槽位切换点：

1. 计算epoll超时的最小阈值

每次设置epoll超时前，同时计算两个时间差：

• 从当前时间到下一个时间轮槽位切换点的时间差
• 从当前时间到时间轮中最早到期事件的时间差
  取两者的最小值作为epoll的超时时间。

比如你的例子：
当前时间1.99999999999秒，槽位大小1秒，下一个槽位切换点是2秒（仅差0.00000000001秒），而最早到期事件是5秒后（差4秒）。此时epoll超时应设为0.00000000001秒（近似为0），而不是4秒。这样epoll会立即唤醒，遍历时间轮槽位，不会错过5秒到期的事件。

2. 处理时间轮的跨轮遍历

每次epoll唤醒后，先更新当前时间，然后检查时间轮的当前指针是否落后于实际时间。如果是，循环遍历从当前指针到实际时间对应槽位之间的所有槽位，处理其中的定时器事件，最后更新时间轮的当前指针。

比如当前时间跳到6秒，时间轮当前指针停在1秒，就需要遍历2、3、4、5、6这几个槽位，处理所有到期的事件。

代码示例（C语言）

#include <stdint.h>
#include <sys/epoll.h>

// 获取当前单调时间（纳秒）
static uint64_t get_current_ns() {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1000000000ULL + ts.tv_nsec;
}

// 时间轮配置
#define SLOT_SIZE_NS 1000000000ULL // 每个槽位1秒
#define TIME_WHEEL_SLOTS 60        // 时间轮总槽位数

// 处理指定槽位的定时器事件（需自行实现）
void process_timer_slot(uint64_t slot_idx);
// 获取时间轮中最早到期的事件时间（需自行实现）
uint64_t get_earliest_timer_time();

int main() {
    int epfd = epoll_create1(0);
    uint64_t time_wheel_current_slot = 0; // 时间轮当前指针（对应槽位的起始时间）

    while (1) {
        uint64_t now = get_current_ns();
        uint64_t current_slot_idx = now / SLOT_SIZE_NS;

        // 遍历所有落后的槽位，处理到期事件
        while (time_wheel_current_slot <= current_slot_idx) {
            uint64_t slot_idx = time_wheel_current_slot % TIME_WHEEL_SLOTS;
            process_timer_slot(slot_idx);
            time_wheel_current_slot++;
        }

        // 计算到下一个槽位切换点的时间
        uint64_t next_slot_time = (current_slot_idx + 1) * SLOT_SIZE_NS;
        uint64_t time_to_next_slot = next_slot_time - now;

        // 计算到最早到期事件的时间
        uint64_t earliest_event_time = get_earliest_timer_time();
        uint64_t time_to_earliest_event = earliest_event_time > now ? earliest_event_time - now : 0;

        // 取最小超时时间，转换为毫秒（适配epoll_wait的参数）
        int timeout = (int)(time_to_next_slot < time_to_earliest_event ? time_to_next_slot : time_to_earliest_event) / 1000000ULL;
        if (timeout < 0) timeout = 0;

        struct epoll_event events[10];
        int n = epoll_wait(epfd, events, 10, timeout);
        // 处理epoll IO事件...
    }
}

时间轮vs二叉堆的取舍 #

• 时间轮：适合大量定时器场景，插入、删除、触发都是O(1)复杂度，解决同步问题后性能优势明显。
• 二叉堆：实现简单，无需处理槽位同步，但插入删除是O(logN)，如果定时器数量在万级以下，性能损耗几乎可以忽略。

如果你的场景中定时器数量较多，优先优化时间轮的同步逻辑；如果数量少，二叉堆的实现成本更低。

内容的提问来源于stack exchange，提问作者Callum Thomson