HashedWheelTimer

为什么我们需要Timer?

经常写网络层代码的人肯定不会对定时器(Timer)陌生,因为有很多应用场景会需要用到定时器或者与之相似的东西,比如：

• delay一段时间再执行某个方法
• 等待某个事件直到超过一定的时间上限
• 以一定的间隔循环执行某些方法

而在 .net中(广义的 .net包括 .net framework, .net core, .net standard, xamarin等),一共有四种定时器（Timer）类型,分别是:

• System.Windows.Forms.Timer(.NET Framework only):windows窗体程序使用的定时器,只能在单线程中使用

• System.Web.UI.Timer(.NET Framework only):ASP.NET使用的定时器

• System.Threading.Timer:可以在指定的时间间隔执行方法,也可通过传入时间参数控制其行为,但是此类无法继承并且传入的方法一旦确定就无法修改,几乎所有的控制权都由 .net runtime掌控

• System.Timers.Timer:主要用于在程序中生成定时的事件,不是所有的 .net版本都支持

考虑到适用性,一般在 .net core中使用的都是System.Threading.Timer

.net的Timer存在的一些问题

一般来说,我们会这么使用System.Threading.Timer

var timer = new Timer((object)=>{
    //do something
}),null, 1000, 250);.
timer.Change(0, 500);

上面代码先是new了一个System.Threading.Timer的实例,在构造这个实例的时候,需要传入你希望执行的回调函数,执行回调的所需要的存储的状态(如果不需要则传入null即可),第一次执行回调的delay的时间,以及之后每次执行回调的时间间隔(如果这个值设置为Timeout.Infinite则不会重复执行回调).但是实际使用的时候会发现,如果够早了大量的Timer的话,会导致函数执行回调的时间精度有显著地下降.同时Timer本身还存在一个问题,就是回调函数的执行时间会有一些误差,因为Timer的实现依赖底层的操作系统.在Windows上,一般这个误差是在15ms左右,详细信息可以查看MSDN上的文档.

浏览System.Threading.Timer的实现,不难发现问题的原因.因为在当前版本的.net的实现里面,new一个Timer对象的时候,实际上做的事情相当于是把传进来的回调插入到一个在线程池中工作的队列中,而唤醒这个回调函数的时候则需要去这个队列里面查找时间到了的回调函数,随着Timer数量的增加,队列的长度也会明显的增加,这时候再插入或者唤醒就会有显著的开销.

HashWheelTimer

这时候就轮到我们的HashWheelTimer登场了,考虑一下,什么样的数据结构插入的时间复杂度最低?不难发现是HashTable,因为其插入的时间复杂度是o(1),那么接下来就要考虑一下如何将这个特点应用到Timer的查找中.如果我们对时间精度要求不是非常的高(一般大部分应用需要的时间精度都不会小于1ms),那么我们可以构建这样一张HashTable,这张表中每个槽位表示一个最小时间精度的间隔比如10ms,槽位用于存放回调函数.这样在这张表里第一个槽位存放的就是10ms后需要执行的回调函数,第二个槽位里面存放的就是20ms后要执行的回调函数,以此类推…

进一步分析,可以将原来的HashTable改为一个ring buffer,这样就可以循环使用,不过这样也限制了最大delay的时间(虽然实际使用中我们很少会去delay很长一段时间再去执行某个操作).同时我们需要保留有一个指向当前槽位的记录,这样这个定时器的工作流程可以概括为:每次await一定的时间(最小时间精度),然后将指向当前槽位的索引记录+1,取出这个槽位里的回调函数,依次执行,最后再继续await直到下一次循环开始.

不过需要注意的一点是,既然在 .net core中,await Task.Delay()这一行为本身是会产生一些误差的,那么长时间执行以后难免会有较大的累积误差.如何解决这个累积误差也很简单,引入一个执行次数的计数,暂且称之为execCount和我们HashWheelTimer的执行总时间.每次循环开始时用执行总时间除以最小时间精度得到值和execCount相比较,如果大于说明执行的次数不够,则这次循环执行完回调函数后不再等待,直接进行下一次循环,这样就可以从总体上避免累积误差的产生.

Task.Run(async () =>
    {
        //初始化总执行时间和执行次数计数
        sw.Start();
        var execCount = 0;
        //HashWheelTimer主循环
        while (true)
        {
            if (( sw.ElapsedMilliseconds / tickDuration ) > execCount)
            {
                //执行delay的回调函数
                doCallBack();
                execCount++;
            }
            else
            {
                //await一个最小时间精度
                await Task.Delay(tickDuration);
            }
        }
    });

总结

经过上述步骤,我们就可以得到一个初步可用的HashWheelTimer,它拥有o(1)时间复杂度的插入操作,同时也避免了累积误差的出现.
但同时它也有两个缺点:

• 1.受限于最小时间精度
• 2.最大delay时间有上限

所以,是否使用它还是得结合项目的实际情况去看.

PS:在.net core 2.1中,我看到Timer已经引入一些优化(虽然并没有解决根本性的问题),比如根据Environment.ProcessorCount来决定Timer工作队列的数量,每次会把新构造的TimerCallBack分配到不同的队列中等等,也许在不久的未来,我们甚至可以看到标准库中引入HashWheelTimer.