如何實(shí)現(xiàn)一個定時器？看這一篇就夠了
“本文主要介紹定時器作用，實(shí)現(xiàn)定時器數(shù)據(jù)結(jié)構(gòu)選取，并詳細(xì)介紹了跳表，紅黑樹，時間輪實(shí)現(xiàn)定時器的思路和方法。
”
定時器作用
定時器在各種場景都需要用到，比如游戲的Buff實(shí)現(xiàn)，Redis中的過期任務(wù)，Linux中的定時任務(wù)等等。顧名思義，定時器的主要用途是執(zhí)行定時任務(wù)。
定時器數(shù)據(jù)結(jié)構(gòu)選取
定時器數(shù)據(jù)結(jié)構(gòu)要求：
需要快速找到到期任務(wù)，因此，應(yīng)該具有有序性； 其過期執(zhí)行、插入(添加定時任務(wù))和刪除(取消定時任務(wù))的頻率比較高，三種操作效率必須保證
以下為各數(shù)據(jù)結(jié)構(gòu)時間復(fù)雜度表現(xiàn)
有序鏈表：插入O(n)，刪除O(1)，過期expire執(zhí)行O(1)
最小堆：插入O(logn)，刪除O(logn)，過期expire執(zhí)行O(1)
紅黑樹：插入O(logn)，刪除O(logn)，過期expire執(zhí)行O(logn)
哈希表+鏈表（時間輪）：插入O(1)，刪除O(1)，過期expire平均執(zhí)行O(1)（最壞為O(n)）
不同開源框架定時器實(shí)現(xiàn)方式不一，如，libuv采用最小堆來實(shí)現(xiàn)，nginx采用紅黑樹實(shí)現(xiàn)，linux內(nèi)核和skynet采用時間輪算法實(shí)現(xiàn)等等。
定時器接口封裝
作為定時器，需要封裝以下4類接口給用戶使用：
創(chuàng)建定時器： init_timer添加定時任務(wù)： add_timer取消定時任務(wù)： cancel_timer執(zhí)行到期任務(wù)： expire_timer
其中執(zhí)行到期任務(wù)有兩種工作方式：
輪詢: 每隔一個時間片去查找哪些任務(wù)到期 睡眠/喚醒：不停查找deadline最近任務(wù)，到期執(zhí)行，否則sleep；sleep期間，任務(wù)有改變，線程會被喚醒
接下來將介紹分別用跳表、紅黑樹、時間輪來實(shí)現(xiàn)定時器。
跳表實(shí)現(xiàn)定時器
跳表簡介
跳表是一種動態(tài)的數(shù)據(jù)結(jié)構(gòu)，采用空間換時間的思想，在有序鏈表基礎(chǔ)上加入多級索引，通過索引進(jìn)行二分快速查找，支持快速刪除、插入和查找操作（平均時間復(fù)雜度為O(logN)，最壞為O(N)），效率可與平衡樹媲美，實(shí)現(xiàn)比其簡單。
下面通過一張圖來簡單說明跳表操作。跳表的最底層即為基本的有序鏈表，存儲所有的數(shù)據(jù)，可理解為數(shù)據(jù)層；往上則為索引層，理想狀態(tài)下，上一層為下一層節(jié)點(diǎn)數(shù)的一半。比如，要查找下圖的數(shù)據(jù)為11的節(jié)點(diǎn)，從begin''出發(fā)，向右走，如果下一個節(jié)點(diǎn)大于11則往下走，直到找到目標(biāo)節(jié)點(diǎn)。可見，跳表要比原始鏈表少比較一些節(jié)點(diǎn)，但前提是需要花更多空間存儲索引節(jié)點(diǎn)。
跳表實(shí)現(xiàn)定時器
跳表查找，插入，刪除(任意節(jié)點(diǎn)、頭節(jié)點(diǎn))的時間復(fù)雜度大概率趨向于
O(logn)過期任務(wù)查找，只需要跟第一個節(jié)點(diǎn)比較，因其第一個節(jié)點(diǎn)即為最小節(jié)點(diǎn)
學(xué)會吸取開源框架中優(yōu)秀數(shù)據(jù)結(jié)構(gòu)和代碼思想，直接采用redis中跳表結(jié)構(gòu)的實(shí)現(xiàn)，取出所需部分，用于實(shí)現(xiàn)定時器。如下：
跳表數(shù)據(jù)結(jié)構(gòu)
跳表節(jié)點(diǎn)與跳表結(jié)構(gòu)
/*skiplist.h*/
#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPPLIST 0.25
typedef struct zskiplistNode zskiplistNode;
typedef void (*handler_pt) (zskiplistNode * node);
// 跳表節(jié)點(diǎn)
struct zskiplistNode {
unsigned long score; /*用于排序的值*/
handler_pt handler; /*處理函數(shù)*/
struct zskiplistLevel {
struct zskiplistNode **forward;
}level[];
};
// 跳表結(jié)構(gòu)
typedef struct zskiplist {
struct zskiplistNode * header;
int length;
int level; /*跳表層數(shù)*/
}zskiplist;
跳表接口申明
具體接口實(shí)現(xiàn)細(xì)節(jié)請移步redis源碼。
/*skiplist.h*/
/*創(chuàng)建跳表，初始化*/
zskiplist *zslCreate(void);
/*刪除跳，表釋放資源*/
void zslFree(zskiplist *zsl);
/*插入節(jié)點(diǎn)*/
zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt func);
/*刪除頭節(jié)點(diǎn)*/
void zsklDeleteHead(zskiplist *zsl);
/*刪除任意節(jié)點(diǎn)*/
void zslDelete(zskiplist *zsl, zskplistNode *zn);
/*打印，調(diào)試*/
void zslPrint(zskiplist *zsl);
定時器接口實(shí)現(xiàn)
主要介紹四個接口實(shí)現(xiàn)：初始化定時器，添加定時任務(wù)，刪除/取消定時任務(wù)，處理定時任務(wù)
// test_user.c 封裝給用戶使用的接口
static uint32_t
current_time() {
uint32_t t;
struct timespec ti;
clock_getttime(CLOCK_MONOTONIC, &ti);
t = (uint32_t)ti.tv_sec * 1000;
t += ti.tv_sec / 1000000;
}
zskiplist *init_timer() {
// 初始化定時器
return zslCreate();
}
zskiplistNode *add_timer(zskiplist *zsl, uint32_t msec, handler_pt func) {
// 添加定時任務(wù)
msec += current_time();
return zslInsert(zsl, msec, func);
}
void cancel_timer(zskiplist *zsl, zskiplistNode *zn) {
// 刪除/取消定時任務(wù)
zslDelete(zsl, zn);
}
void expire_timer(zskiplist *zsl){
// 處理定時任務(wù)
zskiplistNode *x;
uint32_t now = current_time();
for (;;) {
x = zslMin(zsl); // 最近節(jié)點(diǎn)
if (!x) break;
if (x->score > now) break; // 時間未到
x->handler(x); // 執(zhí)行相關(guān)定時任務(wù)
zslDeleteHead(zsl); // 執(zhí)行完刪除
}
}
紅黑樹實(shí)現(xiàn)定時器
紅黑樹
紅黑樹是一種自平衡的二叉查找樹，即，插入和刪除操作如果破壞樹的平衡時，需要重新調(diào)整達(dá)到平衡狀態(tài)。因此，是一種比較難的數(shù)據(jù)結(jié)構(gòu)。
紅黑樹五條性質(zhì)
每個節(jié)點(diǎn)要么是紅色，要么是黑色 根節(jié)點(diǎn)是黑色 每個葉子結(jié)點(diǎn)是黑色 每個紅節(jié)點(diǎn)的兩個子節(jié)點(diǎn)一定是黑色 任意一節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)的路徑都含相同數(shù)目的黑結(jié)點(diǎn)
弄懂紅黑樹如何調(diào)整樹的平衡，保證滿足這5條性質(zhì)，是比較麻煩，需要耐心的去推導(dǎo)一遍，此處不展開。
紅黑樹實(shí)現(xiàn)定時器
AVL 樹平衡要求太高，維護(hù)平衡操作過多，較復(fù)雜；紅黑樹只需維護(hù)一個黑高度，效率較高
紅黑樹查找，刪除，添加時間復(fù)雜度為：O(log(n))
吸取開源框架中優(yōu)秀數(shù)據(jù)結(jié)構(gòu)和代碼思想，選用nginx中的紅黑樹結(jié)構(gòu)
紅黑樹數(shù)據(jù)結(jié)構(gòu)
紅黑樹節(jié)點(diǎn)與紅黑樹
// rbtree.h 紅黑樹數(shù)據(jù)結(jié)構(gòu)以及相關(guān)接口，具體接口實(shí)現(xiàn)同上
#ifndef _NGX_RBTREE_H_INCLUDE_
#define _NGX_RBTREE_H_INCLUDE_
typedef unsigned int ngx_rbtree_key_t;
typedef unsigned int ngx_uint_t;
typedef int ngx_rbtree_key_int_t;
// 紅黑樹節(jié)點(diǎn)
typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;
struct ngx_rbtree_node_s {
ngx_rbtree_key_t key;
ngx_rbtree_node_t *left;
ngx_rbtree_node_t *right;
ngx_rbtree_node_t *parent;
u_char color; // 節(jié)點(diǎn)顏色
u_char data; // 節(jié)點(diǎn)數(shù)據(jù)
};
// 插入函數(shù)指針
typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
// 紅黑樹
typedef struct ngx_rbtree_s ngx_rbtree_t;
struct ngx_rbtree_s {
ngx_rbtree_node_t *root;
ngx_rbtree_node_t *sentinel;
ngx_rbtree_insert_pt insert;
};
紅黑樹接口聲明
// 紅黑樹初始化
#define ngx_rbtree_init(tree, s, i) \
ngx_rbtree_sentinel_init(s); \
(tree)->root = s; \
(tree)->sentinel = s; \
(tree)->insert = i;
// 插入操作
void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
// 刪除操作
void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
// 插入value
void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel);
// 插入timer
void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel);
// 獲取下一個節(jié)點(diǎn)
ngx_rbtree_node_t *ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
#define ngx_rbt_red(node) ((node)->color = 1)
#define ngx_rbt_black(node) ((node)->color = 0)
#define ngx_rbt_is_red(node) ((node)->color)
#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)
#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)
// 找到最小值，一直往左走即可
static inline ngx_rbtree_node_t *
ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
while (node->left != sentinel){
node = node->left;
}
return node;
}
定時器接口實(shí)現(xiàn)
// test_user.c 封裝給用戶使用的接口
ngx_rbtree_t timer;
static ngx_rbtree_node_t sentinel;
typedef struct timer_entry_s timer_entry_t;
typedef void (*timer_handler_pt)(timer_entry_t *ev);
struct timer_entry_s {
ngx_rbtree_node_t timer;
timer_handler_pt handler;
};
// 初始化
int init_timer() {
ngx_rbtree_init(&timer, &sentinel, ngx_rbtree_insert_timer_value);
return 0;
}
// 添加定時任務(wù)
void add_timer(timer_entry_t *te, uint32_t msec) {
msec += current_time();
te->timer.key = msec;
ngx_rbtree_insert(&timer, &te->timer);
}
// 取消定時
void cancel_timer(timer_entry_t *te) {
ngx_rbtree_delete(&timer, &te->timer);
}
// 執(zhí)行到期任務(wù)
void expire_timer() {
timer_entry_t *te;
ngx_rbtree_node_t *sentinel, *root, *node;
sentinel = timer.sentinel;
uint32_t now = current_time();
for(;;){
root = timer.root;
if (root == sentinel) break;
if (node->key > now) break;
te = (timer_entry_t *) ((char *) node - offsetof(timer_entry_t, timer));
te->handler(te);
ngx_rbtree_delete(&timer, &te->timer);
free(te);
}
}
以上，為紅黑樹和跳表實(shí)現(xiàn)的定時器，多線程環(huán)境下加鎖粒度比較大，高并發(fā)場景下效率不高，而時間輪適合高并發(fā)場景，如下。
時間輪實(shí)現(xiàn)定時器
時間輪
可以用于高效的執(zhí)行大量定時任務(wù)，如下為分層時間輪示意圖：
時間輪可參考時鐘進(jìn)行理解，秒針(Seconds wheel)轉(zhuǎn)一圈，則分針(Minutes wheel)走一格，分針(Minutes wheel)轉(zhuǎn)一圈，則時針(Hours wheel)走一格。隨著，時間的流逝，任務(wù)不斷從上層流下下一層，最終到達(dá)秒針輪上，當(dāng)秒針走到時執(zhí)行。
如上所示，時間輪大小為8格，秒針1s轉(zhuǎn)動一格，其每一格所指向的鏈表保存著待執(zhí)行任務(wù)。比如，如果當(dāng)前指針指向1，要添加一個3s后執(zhí)行的任務(wù)，由于1+3=4，即在第4格的鏈表中添加一個任務(wù)節(jié)點(diǎn)即可。如果要添加一個10s后執(zhí)行的任務(wù)，10+1=11，超過了秒針輪范圍，因此需要對8取模11 % 8 = 3，即，會把這個任務(wù)放到分針輪上3對應(yīng)的鏈表上，之后再從分針輪把任務(wù)丟到秒針輪上進(jìn)行處理。也即，**秒針輪(Seconds wheel)**即保存著最近將要執(zhí)行的任務(wù)，隨著時間的流逝，任務(wù)會慢慢的從上層流到秒針輪中進(jìn)行執(zhí)行。
優(yōu)點(diǎn)：加鎖粒度較小，只需要加一個格子即可，一個格子對應(yīng)一串鏈表；適合高并發(fā)場景
缺點(diǎn)：不好刪除
如何解決時間輪定時任務(wù)刪除？
通過引用計數(shù)來解決 交由業(yè)務(wù)層處理，將刪除標(biāo)記設(shè)為 true, 在函數(shù)回調(diào)中根據(jù)這個標(biāo)記判斷是否需要處理
這里介紹兩種定時器實(shí)現(xiàn)方案，一種是簡單實(shí)現(xiàn)方案，另一種是skynet較為復(fù)雜的實(shí)現(xiàn)。
時間輪實(shí)現(xiàn)定時器
簡單時間輪實(shí)現(xiàn)方案
功能場景：由心跳包進(jìn)行超時連接檢測，10s未收到則斷開連接
一般做法：map<fd, *connect>每秒輪詢這個結(jié)構(gòu)，檢測所有連接是否超時，收到心跳包，記錄時間戳
缺點(diǎn)：效率很差，每次需要檢測所有連接，時間復(fù)雜度為O(n)
優(yōu)化：分治大法，只需檢測快過期的連接， 采用hash數(shù)組+鏈表形式，數(shù)組大小設(shè)置成16 ：[0] + [1] + [2] + ... + [15] ，相同過期時間的放入一個數(shù)組，因此，每次只需檢測最近過期的數(shù)組即可，不需要遍歷所有。
數(shù)據(jù)結(jié)構(gòu)定義
以下為定時器節(jié)點(diǎn)，增加引用計數(shù)ref， 只有當(dāng)ref為0時刪除連接。
class CTimerNode {
public:
CTimerNode(int fd) : id(fd), ref(0) {}
void Offline() {this->ref = 0};
bool tryKill() {
if (this->ref == 0) return true;
DecRef();
if (this->ref == 0){
return true;
}
return false;
}
void IncRef() {this->ref++;}
protected:
void DecRef() {this->ref--;}
private:
int ref;
int id;
}
// 時間輪數(shù)組大小16, (x對16取余)==(x&1111) 落到0-15之間,即落到對應(yīng)的數(shù)組
const int TW_SIZE = 16;
const in EXPIRE = 10; // 過期間隔
const int TW_MASK = TW_SIZE - 1; // 掩碼, 用于對16取余
static size_t iReadTick = 0; // 滴答時鐘
typedef list<CTimerNode*> TimeList; // 數(shù)組每一個槽位對應(yīng)一個list
typedef TimeList::iterator TimeListIter;
typedef vector<TimeList> TimeWheel; // 時間輪
定時器接口
// 添加定時
void AddTimeOut(TimerWheel &tw, CTimerNode *p) {
if (p) {
p->IncRef();
// 找到iRealTick對應(yīng)數(shù)組的idx(槽位)
TimeList &le = tw[(iRealTick+EXPIRE) & TW_MASK];
le.push_back(p); // 把時間節(jié)點(diǎn)加入list中
}
}
// 延時調(diào)用
void AddTimeOutDelay(TimeWheel &tw, CTimerNode *p, size_t delay) {
if (p) {
p->IncRef();
TimeList &le = tw[(iRealTick + EXPIRE + delay) & TW_MASK];
le.push_back(p);
}
}
// 時間輪移動
void TimerShift(TimeWheel &tw) {
size_t tick = iRealTick;
iRealTick++;
TimeList &le = tw[tick & TW_MASK];
TimeListIter iter = le.begin();
for (; iter != le.end(); iter++) {
CTimerNode *p = *iter;
if (p && p->trySkill()){
delete p;
}
}
le.clear();
}
Skynet定時器實(shí)現(xiàn)方案
skynet中定時器數(shù)據(jù)結(jié)構(gòu)
采用時間輪方式，hash表+鏈表實(shí)現(xiàn)，
struct timer_node { //時間節(jié)點(diǎn)
struct timer_node *next;
uint32_t expire; //到期滴答數(shù)
};
struct link_list { // 鏈表
struct timer_node head;
struct timer_node *tail;
};
struct timer {
struct link_list near[256]; // 即將到來的定時器
struct link_list t[4][64]; // 相對較遙遠(yuǎn)的定時器
struct spinlock lock;
uint32_t time; // 記錄當(dāng)前滴答數(shù)
uint64_t starttime;
uint64_t current;
uint64_t current_point;
};
其中time為32位無符號整數(shù)， 記錄時間片對應(yīng)數(shù)組near[256] ，表示即將到來的定時任務(wù)， t[4][64]，表示較為遙遠(yuǎn)的定時任務(wù)。
定時器執(zhí)行流程
| t[3] | t[2] | t[1] | t[0] | near |
|---|---|---|---|---|
| 26-32位 | 20-26位 | 14-20位 | 8-14位 | 0-8位 |
[2^(8+6x3),2^(8+6x4)-1] | [2^(8+6x2),2^(8+6x3)-1] | [2^(8+6),2^(8+6x2)-1] | [2^8,2^(8+6) -1] | [0,2^8-1] |
首先檢查節(jié)點(diǎn)的 expire與time的高24位是否相等，相等則將該節(jié)點(diǎn)添加到expire低8位值對應(yīng)數(shù)組near的元素的鏈表中，不相等則進(jìn)行下一步檢查 expire與time的高18位是否相等，相等則將該節(jié)點(diǎn)添加到expire低第9位到第14位對應(yīng)的6位二進(jìn)制值對應(yīng)數(shù)組t[0]的元素的鏈表中，否則進(jìn)行下一步檢查 expire與time的高12位是否相等，相等則將該節(jié)點(diǎn)添加到expire低第15位到第20位對應(yīng)的6位二進(jìn)制值對應(yīng)數(shù)組t[1]的元素的鏈表中，如果不相等則進(jìn)行下一步檢查 expire與time的高6位是否相等，相等則將該節(jié)點(diǎn)添加到expire低第21位到第26位對應(yīng)的6位二進(jìn)制值對應(yīng)數(shù)組t[2]的元素的鏈表中，如果不相等則進(jìn)行下一步將該節(jié)點(diǎn)添加到 expire低第27位到第32位對應(yīng)的6位二進(jìn)制值對應(yīng)數(shù)組t[3]的元素的鏈表中
以下為具體實(shí)現(xiàn)，僅貼出主要接口，具體細(xì)節(jié)請參考skynet源代碼。
定時器初始化
// skynet_start.c
// skynet 啟動入口
void
skynet_start(struct skynet_config * config) {
...
skynet_timer_init();
...
}
// skynet_timer.c
void
skynet_timer_init(void) {
// 創(chuàng)建全局timer結(jié)構(gòu) TI
TI = timer_create_timer();
uint32_t current = 0;
systime(&TI->starttime, ¤t);
TI->current = current;
TI->current_point = gettime();
}
添加定時器
通過skynet_server.c中的cmd_timeout調(diào)用skynet_timeout添加新的定時器
// TI為全局的定時器指針
static struct timer * TI = NULL;
int skynet_timeout(uint32_t handle, int time, int session) {
...
struct timer_event event;
event.handle = handle; // callback
eveng.session = session;
// 添加新的定時器節(jié)點(diǎn)
timer_add(TI, &event, sizeof(event), time);
return session;
}
// 添加新的定時器節(jié)點(diǎn)
static void timer_add(struct timer *T, void 8arg, size_t sz, int time) {
// 給timer_node指針分配空間，還需要分配timer_node + timer_event大小的空間，
// 之后通過node + 1可獲得timer_event數(shù)據(jù)
struct timer_node *node = (struct timer_node *)skynet_malloc(sizeof(*node)+sz);
memcpy(node+1,arg,sz);
SPIN_LOCK(T);
node->expire=time+T->time;
add_node(T, node);
SPIN_UNLOCK(T);
}
// 添加到定時器鏈表里，如果定時器的到期滴答數(shù)跟當(dāng)前比較近(<2^8)，表示即將觸發(fā)定時器添加到T->near數(shù)組里
// 否則根據(jù)差值大小添加到對應(yīng)的T->T[i]中
static void add_node(struct timer *T, struct timer_node *node) {
...
}
驅(qū)動方式
skynet啟動時，會創(chuàng)建一個線程專門跑定時器，每幀(0.0025s)調(diào)用skynet_updatetime()
// skynet_start.c
static void *
thread_timer(void *p) {
struct monitor * m = p;
skynet_initthread(THREAD_TIMER);
for (;;) {
skynet_updatetime(); // 調(diào)用timer_update
skynet_socket_updatetime();
CHECK_ABORT
wakeup(m,m->count-1);
usleep(2500); // 2500微秒 = 0.0025s
if (SIG) {
signal_hup();
SIG = 0;
}
}
...
}
每個定時器設(shè)置一個到期滴答數(shù)，與當(dāng)前系統(tǒng)的滴答數(shù)(啟動時為0，1滴答1滴答往后跳，1滴答==0.01s ) 比較得到差值interval;
如果interval比較小(0 <= interval <= 2^8-1)，表示定時器即將到來，保存在第一部分前2^8個定時器鏈表中；否則找到屬于第二部分對用的層級中。
// skynet_timer.c
void
skynet_updatetime(void) {
...
uint32_t diff = (uint32_t)(cp - TI->current_point);
TI->current_point = cp;
TI->current += diff;
// diff單位為0.01s
for (i = 0; i < diff; i++){
timer_update(TI);
}
}
static void
timer_update(struct timer *T) {
SPIN_LOCK(T);
timer_execute(T); // 檢查T->near是否位空，有就處理到期定時器
timer_shift(T); // 時間片time++，移動高24位的鏈表
timer_execute(T);
SPIN_UNLOCK(T);
}
// 每幀從T->near中觸發(fā)到期得定時器
static inline void
timer_execute(struct timer *T) {
...
}
// 遍歷處理定時器鏈表中所有的定時器
static inline void
dispatch_list(struct timer_node *current) {
...
}
// 將高24位對應(yīng)的4個6位的數(shù)組中的各個元素的鏈表往低位移
static void
timer_shift(struct timer *T) {
...
}
// 將level層的idx位置的定時器鏈表從當(dāng)前位置刪除，并重新add_node
static void move_list(struct timer *T, int level, int idx) {
}
最小堆實(shí)現(xiàn)定時器
最小堆實(shí)現(xiàn)例子：boost.asio采用二叉樹，go采用四叉樹， libuv
具體實(shí)現(xiàn)略。
總結(jié)
本文主要介紹定時器作用，實(shí)現(xiàn)定時器數(shù)據(jù)結(jié)構(gòu)選取，并詳細(xì)介紹了跳表，紅黑樹，時間輪實(shí)現(xiàn)定時器的思路和方法。
參考
跳表介紹
https://baijiahao.baidu.com/s?id=1633338040568845450&wfr=spider&for=pc
Skynet GitHub
https://github.com/cloudwu/skynet
skynet源碼剖析
https://zhongyiqun.gitbooks.io/skynet/content/18-skynetding-shi-qi-yuan-li.html