Kinly

Kinly's 记录

模块：时间轮定时器

发表于 更新于 分类于
时间轮定时器简要描述

代码

https://github.com/kinly/timer_wheel

基础数据结构

1
2
3
4
uint64_t       _index;           // guid（时间戳）
event_type     _type;            // 业务：事件类型
uint32_t       _repeat;          // 业务：重复次数
timer_callback _caller;          // 回调: std::function

时间轮

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
union timer_clock
{
    time64_t time;
    struct
    {
        uint32_t m5 : 10;     // 分桶：5
        uint32_t m4 : 8;      // 分桶：4
        uint32_t m3 : 6;      // 分桶：3
        uint32_t m2 : 6;      // 分桶：2
        uint32_t m1 : 6;      // 分桶：1
        uint32_t m0 : 6;      // 分桶：0
    };
};
桶名 最大容纳 桶起始位置
m5 1024 0x000
m4 256 0x400
m3 64 0x500
m2 64 0x540
m1 64 0x580
m0 64 0x5C0

自内向外依次是m5、m4、m3、m2、m1、m0
认为m5是最小的桶，m0是最大的桶

manager

1
2
3
std::vector<std::list<time64_t> > _wheelVec;               // 管理每一层，容器可以再考量下
std::unordered_map<time64_t, timer_event> _timeSeq2Evt;    // 管理触发时候的callback
time64_t _timeSeconds;                                     // 时间轮精度下的当前时间戳

operator

当前有两个时间戳，一个是数据成员 _timeSeconds，另一个是insert的事件下次要触发的时间戳 deadline，将这两个时间转化为timer_clock类型，确定事件在时间轮里面的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
if( t1.m0 != t2.m0 )
{
    _wheelVec[0x5c0 + t1.m0].push_back(_handle);
}
else if( t1.m1 != t2.m1 )
{
    _wheelVec[0x580 + t1.m1].push_back(_handle);
}
else if( t1.m2 != t2.m2 )
{
    _wheelVec[0x540 + t1.m2].push_back(_handle);
}
else if( t1.m3 != t2.m3 )
{
    _wheelVec[0x500 + t1.m3].push_back(_handle);
}
else if( t1.m4 != t2.m4 )
{
    _wheelVec[0x400 + t1.m4].push_back(_handle);
}
else
{
    _wheelVec[t1.m5].push_back(_handle);
}

_handle是一个唯一索引，也就是 _timeSeq2Evt 的 key
接下来是执行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
timer_clock now; // ... 赋值当前时间戳（以时间轮的精度)

while( _timeSeconds <= now.time )
{
	timer_clock ts = { tickcount_ };

	if( ts.m5 )
	{
		_clock_step_list( time_wheel_[ts.m5] );
	}
	else if( ts.m4 )
	{
		_clock_step_list( _wheelVec[ts.m4 + 0x400] );
	}
	else if( ts.m3 )
	{
		_clock_step_list( _wheelVec[ts.m3 + 0x500] );
	}
	else if( ts.m2 )
	{
		_clock_step_list( _wheelVec[ts.m2 + 0x540] );
	}
	else if( ts.m1 )
	{
		_clock_step_list( _wheelVec[ts.m1 + 0x580] );
	}
	else if( ts.m0 )
	{
		_clock_step_list( _wheelVec[ts.m0 + 0x5c0] );
	}

	_timeSeconds += 1;
}
return true;

_clock_step_list的入参是一个list的引用（后面需要clear这个list），这个函数需要做的就是检查时间，如果时间 <= _timeSeconds 就调用 _caller 执行，否则，重新insert_clock（这个操作其实就是把外层的事件move到内层去），遍历完整个list，做一个clear

其他

存在的问题是如果测试期间修改服务器时间，定时器会循环很多次处理事件，可能引起网络的超时断链，cpu跑满等问题，可以考虑增加一个判断，如果循环超过2000次break一次，其他的等下次主循环跑到了再执行。

2023.更新

  • 实际实现的定时器性能还可以，20W数据 + 10ms period + 单线程，误差基本在3ms以内 （因为是单线程的关系，测试的回调只是算了下和应当触发时间的误差）
  • 为了简化活动一般配置成绝对时间开启、周期开启的情况，引入 https://github.com/mariusbancila/croncpp，抽象 event_interface，对间隔时间方式、计划任务方式兼容
  • 这里有点遗留问题：因为分桶量级的关系，这里认为最小时间单位是毫秒（ms），计划任务里就有一段硬编码的时间转换，虽然是满足绝大多数游戏开发的需要，但是对于延迟要求特别严格的场景也是一种限制
  • 解决办法是写个明确的 seconds 换算 tick 的函数
  • 另外：这个模块里 std::string 相关的位置可以换成 std::string_view，都是只读的场景
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    struct event_interface {
    	timer_handle _handle = handle_gen::invalid_handle;  // 句柄
    	time64_t _next = 0;                                 // 下次执行时间
    	time64_t _period = 0;                               // 间隔时间
    	uint64_t _round = 1;                                // 执行轮次（剩余）
    	timer_callback _callback = nullptr;                 // 回调
    	timer_stopped_callback _stopped_callback = nullptr; // 停止回调

    	std::string _remark{ };                             // debug remark

    	explicit event_interface(time64_t nxt, time64_t period, uint64_t round, timer_callback&& cb, timer_stopped_callback&& stopped_cb)
    		: _next(nxt)
    		, _period(period)
    		, _round(round)
    		, _callback(std::forward<timer_callback>(cb))
    		, _stopped_callback(std::forward<timer_stopped_callback>(stopped_cb)) {
    		_handle = handle_gen::instance().get();
    		if (_period == 0)
    			_round = 1;
    	}
    	virtual ~event_interface() {
    		if (_handle == handle_gen::invalid_handle)
    			return;
    		handle_gen::instance().put(_handle);
    	}

    	virtual time64_t next() = 0;                         // next trigger time
    };

    template<uint64_t precision_tt = 10>
    struct event_custom : public event_interface {
    	static constexpr time64_t _precision = precision_tt;

    	explicit event_custom(time64_t nxt, time64_t period, uint64_t round, timer_callback&& cb, timer_stopped_callback&& stopped_cb)
    		: event_interface(nxt, period, round, std::forward<timer_callback>(cb), std::forward<timer_stopped_callback>(stopped_cb)) {

    	}

    	~event_custom() {

    	}

    	virtual time64_t next() {
    		event_interface::_next = (tick() + _period) / _precision;
    		return _next;
    	}

    	static std::shared_ptr<event_interface> create(time64_t nxt, time64_t period, uint64_t round, timer_callback&& cb, timer_stopped_callback&& stopped_cb) {
    		std::shared_ptr<event_custom> result = std::make_shared<event_custom>(nxt, period, round,
    			std::forward<timer_callback>(cb), std::forward<timer_stopped_callback>(stopped_cb));
    		return result;
    	}
    };

    template<uint64_t precision_tt = 10>
    struct event_crontab : public event_interface {
    	static constexpr time64_t _precision = precision_tt;

    	cron::cronexpr _cronexpr;    // cronexpr

    	explicit event_crontab(timer_callback&& cb, timer_stopped_callback&& stopped_cb)
    		: event_interface(tick() / _precision, -1, -1, std::forward<timer_callback>(cb), std::forward<timer_stopped_callback>(stopped_cb)) {

    	}

    	~event_crontab() {

    	}

    	virtual time64_t next() {
    		auto last = event_interface::_next * _precision / 1000;
    		event_interface::_next = cron::cron_next(_cronexpr, last) * 1000 / _precision;
    		return event_interface::_next;
    	}

    	static std::shared_ptr<event_interface> create(const std::string& cron_str, timer_callback&& cb, timer_stopped_callback&& stopped_cb) {
    		try {
    			std::shared_ptr<event_crontab> result = std::make_shared<event_crontab>(std::forward<timer_callback>(cb), std::forward<timer_stopped_callback>(stopped_cb));
    			result->_cronexpr = cron::make_cron(cron_str);
    			result->next();
    			return result;
    		} catch (cron::bad_cronexpr const& ex) {
    			// todo: log
    			return nullptr;
    		}
    	}

    	static std::shared_ptr<event_interface> create(std::string&& cron_str, timer_callback&& cb, timer_stopped_callback&& stopped_cb) {
    		try {
    			std::shared_ptr<event_crontab> result = std::make_shared<event_crontab>(std::forward<timer_callback>(cb), std::forward<timer_stopped_callback>(stopped_cb));
    			result->_cronexpr = cron::make_cron(cron_str);
    			result->next();
    			return result;
    		} catch (cron::bad_cronexpr const& ex) {
    			// todo: log
    			return nullptr;
    		}
    	}
    };
------ 本文结束 ------
------ 版权声明：转载请注明出处 ------