浅论时间轮

基于时间轮的定时器

定时器的实现多采用最小堆,其创建和删除复杂度为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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前奏 https://tech.meituan.com/2016/11/04/nio.html 综述 netty通...
    jiangmo阅读 11,188评论 0 13
  • Spring Cloud为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理,服务发现,断路器,智...
    卡卡罗2017阅读 135,463评论 19 139
  • Android 自定义View的各种姿势1 Activity的显示之ViewRootImpl详解 Activity...
    passiontim阅读 175,631评论 25 709
  • 最美的时候就是你在,无论风雨,只要你在,我便心安。 无论何时都忘不掉,你的容颜。你总说,小二啊!你慢慢长大了,以后...
    小二_Forever阅读 1,352评论 0 0
  • 如今肉夹馍 蛋饼油条都要走小资轻奢风 蛋炒饭也紧跟时代脚步 举起手说 我们家“煮”公会打仗更都会炒饭! #土豪三丁...
    桂花糕Quincy阅读 1,371评论 0 0