浅论时间轮

基于时间轮的定时器

定时器的实现多采用最小堆，其创建和删除复杂度为O(logN),tick的复杂度为O(1);在极端高性能场景（如timer数量巨大）下有待优化；

下面介绍基于多级时间轮的定时器，他能做到创建和删除复杂度为O(1)，tick复杂度也为O(1),非常适合高性能的场景。

基于时间轮的超时连接剔除

连接超时踢除，在长连接服务中非常重要。有以下几个方案：

1）全局Timer：全局定时器中轮询当前的每个连接，此方案的复杂度为O(N),当连接数较大时不适合。

2）为每个连接设置一个one-short timer，在超时时断开连接，但是连接收到数据时需要频繁的更新Timer，为timer的管理增加了难度。

这里提出一个更简单的时间轮方案。

参考文献

https://www.ibm.com/developerworks/cn/linux/l-cn-timers/index.html

https://www.zhihu.com/question/38427301

https://github.com/ichenq/timerqueue-benchmark