高效Timer-时间轮算法

发表于 | 分类于

定时器在游戏服务器中使用得非常普遍，它的效率直接影响了服务器的性能。对于服务器程序来说只有理解定时器的原理和细节才能更好的使用定时器，做到心中有数。在前面的文章中已经介绍过一种定时器算法-时间堆，本文介绍另一种定时器算法-时间轮。

一、时间轮(Timing-Wheel)算法原理

1.1 基本思想

我们把时间轮分为5个轮子(slots1~slots5)，slots1 255个区间，其余4个slots分别为64个区间。每个区间都是链表，链表上挂了当前时刻要执行的所有tick。
注册时，根据触发时间，tick落到5个轮子其中一个, 轮子区间最大值分别为：slot1:2^8, slot2:2^14, slot3:2^20, slot4:2^26, slot5:2^32(区间数量和范围可调整)
例如：注册一个30秒的tick, 落到slot1；注册一个3600秒的tick，落到slot2

1.2 转动规则
  1. 可在进程主循环中推动时间轮的转动, 并附带上次执行到本次执行的时间差
  2. 从slots1的区间中依次取到期的tick执行
  3. slots1转一圈（256个区间），则slots2转1/64圈，也就是移1个区间；slots2转一圈（64次）slots3转1/64圈，此类推。若tick执行则从链表中删除，没执行则为tick重定位区间。再比如说slots2的63个区间中，0号区间上的tick是slots1走完一个周期（256次）需要执行的tick, 2号区间是slots1走完2个周期要执行的tick, slots2每移动1个区间会把当前区间的tick重定位到slots1中，以待遍历slots1区间的时候执行；
    同理，slots3移动1次（需要slots2走一圈）并把当前区间的中的tick重定位到slots2各区间,以此类推。

二、核心代码:

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
//nNextTickTime 触发时间(未来某个时间点，比如：18580082，因为精度问题，通常来说不会取unix时间戳；一般取系统启动以来毫秒或纳秒数)
//nTimeLeft 多少久后触发(相对时间, 比如：20毫秒)
//函数的功能是为timer找到对应的槽位(0~4)以及在槽中的索引0~63
void CTickMgr::GetTickPos(uint32 nNextTickTime, uint32 nTimeLeft, uint32 &nSlot, uint32 &nIndex)
{
    //把时间轮分为5个大轮子(0~255, 256~1637, 1638~1048575, 1048576~16777215, 16777216~4294967294)，最小的轮子255个轮位，其余都是63个。
    if(nTimeLeft <  eTeSIZE_256)
    {
        nSlot = 0;
        nIndex = nNextTickTime & eTeMASK_255;
    }
    else if(nTimeLeft < 1 << (eTeSIZE_8+eTeSIZE_6))
    {
        nSlot = 1;
        nIndex = nNextTickTime >> eTeSIZE_8 & eTeMASK_63; //nNextTickTime >> eTeSIZE_8本来是除法(/2^8)，为了效率写成右移
    }
    else if(nTimeLeft < 1 <<(eTeSIZE_8+eTeSIZE_6*2))
    {
        nSlot = 2;
        nIndex = (nNextTickTime >> (eTeSIZE_8 + eTeSIZE_6 )) & eTeMASK_63;
    }
    else if(nTimeLeft < 1 <<(eTeSIZE_8+eTeSIZE_6*3))
    {
        nSlot = 3;
        nIndex = (nNextTickTime >> (eTeSIZE_8 + eTeSIZE_6*2 )) & eTeMASK_63;
    }
    else if(nTimeLeft <  0xFFFFFFFF)
    {
        nSlot = 4;
        nIndex = (nNextTickTime >> (eTeSIZE_8 + eTeSIZE_6*3 )) & eTeMASK_63;
    }
}

//注册一个timer, uInterval后触发
void CTickMgr::RegisterTick(uint32 uInterval, CTick* pTick)
{
    if(false != pTick->IsRegistered())
        return;

    ++m_nTotalTickSize;

    uint32 nIndex=0;
    uint32 nSlot=0;

    TickContext* pContext = PPE_NEW_T(TickContext, MEMCATEGORY_GENERAL, "");
    pContext->m_uInterval = uInterval;
    pContext->m_bTerminate = false;
    //计算timer触发的时间点，m_nTotalCount是进程启动以来经过的总时间
    pContext->m_uNextTickTime = m_nTotalCount + uInterval;
    pContext->m_pTick = pTick;
    pTick->m_pTickContext = pContext;

    GetTickPos(pContext->m_uNextTickTime, uInterval, nSlot, nIndex);
    //把当前timer插入到相应槽位的区间链表中,等待触发
    m_SlotsPointer[nSlot]->m_oSlots[nIndex].push_back(pContext);
}
//重新分到新的槽位
void CTickMgr::MoveRegistedTick(TickContext * pTick)
{ 
    uint32 nIndex=0;
    uint32 nSlot=0;
    uint32 nNextTickTime = pTick->m_uNextTickTime;
    uint32 nInterval = nNextTickTime < m_nTotalCount ? 0 : nNextTickTime - m_nTotalCount;

    GetTickPos(nNextTickTime, nInterval, nSlot, nIndex);
    m_SlotsPointer[nSlot]->m_oSlots[nIndex].push_back(pTick);
}

//把当前轮子中的timer往面前移
void CTickMgr::CascadeTimers(SlotCd& slotcd)
{
    CTickContextSlot& slot = slotcd.m_oSlots[slotcd.m_nIndex];
    while(!slot.empty())
    {
        TickContext* pTickContext = slot.front();
        slot.pop_front();
        MoveRegistedTick(pTickContext);
    }
    slotcd.m_nIndex = (slotcd.m_nIndex + 1)&eTeMASK_63;
}

//此函数用于推动时间轮的转动
//nInterval上次执行PushTickOnce到现在时间差
//PushTickOnce 调用1次可能会有多个timer会被执行
uint32 CTickMgr::PushTickOnce(uint32 nInterval)
{
    uint32 uTotoalTime = 0;
    //检查每一帧是否有timer被执行
    for(uint32 nIndex = 0; nIndex < nInterval; ++nIndex)
    {
        // 检查slot2,slot3,slot4中的timer是否需要往前移(越靠前的表示触发时间离现在越近)
        if(0==m_oSlots1.m_nIndex)
        {
            int n = 1; 
            do {
                CascadeTimers(*m_SlotsPointer[n]); 
            } while (m_SlotsPointer[n]->m_nIndex == 1 && ++n < eTeSIZE_5);
        }

        //永远只取第1个轮子中的timer执行，其它轮子中的timer都会在CascadeTimers中往前移
        CTickContextSlot& slot = m_oSlots1.m_oSlots[m_oSlots1.m_nIndex];
        while(!slot.empty())
        {
            TickContext * pTickContext = slot.front();
            if( pTickContext->m_bTerminate )
            {
                PPE_DELETE_T( pTickContext, TickContext, MEMCATEGORY_GENERAL);
                pTickContext = NULL;
                --m_nTotalTickSize;
            }
            else
            {
                CTick* pTick = pTickContext->m_pTick;
                pTick->OnTick();//执行Timer,本例中的timer会反复触发(也可改成只触发1次)，相当于golang中的ticker
                if(pTickContext->m_bTerminate)
                {
                    PPE_DELETE_T( pTickContext, TickContext, MEMCATEGORY_GENERAL);
                    pTickContext = NULL;
                    --m_nTotalTickSize;
                }
                else
                {
                    RegisterTickAgain(pTickContext); //重新注册,也可设计为只成执行一次，看具体需求
                }
            }
            slot.pop_front();
        }

        ++m_nTotalCount;//时间(帧数)累加
        m_oSlots1.m_nIndex = (m_oSlots1.m_nIndex +1)&eTeMASK_255;
    }
    return uTotoalTime;
}