README
¶
from
https://github.com/RussellLuo/timingwheel
使用场景
延迟一段时间后执行任务；C1000k的场景，每个连接一个Timer，小顶堆的结构查找删除时间复杂度O(logn)，效率会比较低；采用时间轮实现的 Timer,创建和删除的时间复杂度为 O(1); 效仿kafka Purgatory 的实现，层级时间轮(Hierarchical Timing Wheels); 主要场景：
- 长链接心跳检测，聊天，推送
- 客户端发起 HTTP 请求后，如果在指定时间内没有收到服务器的响应，则自动断开连接
对比
Go 1.14 对time.Timer进行优化，在go1.15 的测试：
go test -bench=. -run=none -benchmem -memprofile=mem.pprof -cpuprofile=cpu.pprof -blockprofile=block.pprof
goos: darwin
goarch: amd64
pkg: github.com/weedge/lib/timingwheel
BenchmarkTimingWheel_StartStop/N-1m-8 4408240 238 ns/op 84 B/op 2 allocs/op
BenchmarkTimingWheel_StartStop/N-5m-8 4696995 261 ns/op 104 B/op 2 allocs/op
BenchmarkTimingWheel_StartStop/N-10m-8 2271856 467 ns/op 82 B/op 1 allocs/op
BenchmarkStandardTimer_StartStop/N-1m-8 6194773 204 ns/op 83 B/op 1 allocs/op
BenchmarkStandardTimer_StartStop/N-5m-8 6753042 219 ns/op 80 B/op 1 allocs/op
BenchmarkStandardTimer_StartStop/N-10m-8 1000000 51426 ns/op 3859 B/op 9 allocs/op
#最后一个操作慢有gc导致
#第二次运行结果，使用go1.15
BenchmarkTimingWheel_StartStop/N-1m-8 4488100 237 ns/op 84 B/op 2 allocs/op
BenchmarkTimingWheel_StartStop/N-5m-8 4677676 263 ns/op 103 B/op 2 allocs/op
BenchmarkTimingWheel_StartStop/N-10m-8 4872208 518 ns/op 54 B/op 1 allocs/op
BenchmarkStandardTimer_StartStop/N-1m-8 6061422 200 ns/op 81 B/op 1 allocs/op
BenchmarkStandardTimer_StartStop/N-5m-8 6735716 193 ns/op 83 B/op 1 allocs/op
BenchmarkStandardTimer_StartStop/N-10m-8 4947601 259 ns/op 85 B/op 1 allocs/op
go tool pprof -http=":8080" cpu.pprof
Serving web UI on http://localhost:8080
#可以通过火焰图查看cpu占用时间, 内存(allocs已分配的空间和对象数目，heap正在使用的空间和对象数目)，阻塞等情况；整体timingwheel 耗时相对少些;
总结： time.Timer 经过优化之后，性能有所提升，但是整体小顶堆结构的添加删除操作O(logn)比双向循环链表O(1)的效率要低
reference
- 层级时间轮的 Golang 实现
- Apache Kafka, Purgatory, and Hierarchical Timing Wheels
- 完全兼容golang定时器的高性能时间轮实现(go-timewheel)
- golang netty timewheel
- golang timer(计时器)
- 第 74 期 time.Timer 源码分析 (Go 1.14)
- 论golang Timer Reset方法使用的正确姿势
- George Varghese , Anthony Lauck, Hashed and hierarchical timing wheels: efficient data structures for implementing a timer facility, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.824-834, Dec. 1997
Documentation
¶
Overview ¶
Example (ScheduleTimer) ¶
package main
import (
"fmt"
"time"
)
type EveryScheduler struct {
Interval time.Duration
}
func (s *EveryScheduler) Next(prev time.Time) time.Time {
return prev.Add(s.Interval)
}
func main() {
tw := NewTimingWheel(time.Millisecond, 20)
tw.Start()
defer tw.Stop()
exitC := make(chan time.Time)
t := tw.ScheduleFunc(&EveryScheduler{3 * time.Second}, func() {
fmt.Println("The timer fires")
exitC <- time.Now().UTC()
})
<-exitC
<-exitC
// We need to stop the timer since it will be restarted again and again.
for !t.Stop() {
}
}
Output: The timer fires The timer fires
Example (StartTimer) ¶
tw := NewTimingWheel(time.Millisecond, 20)
tw.Start()
defer tw.Stop()
exitC := make(chan time.Time)
tw.AfterFunc(time.Second, func() {
fmt.Println("The timer fires")
exitC <- time.Now().UTC()
})
<-exitC
Output: The timer fires
Example (StopTimer) ¶
tw := NewTimingWheel(time.Millisecond, 20)
tw.Start()
defer tw.Stop()
t := tw.AfterFunc(time.Second, func() {
fmt.Println("The timer fires")
})
<-time.After(900 * time.Millisecond)
// Stop the timer before it fires
t.Stop()
Output:
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Scheduler ¶
type Scheduler interface {
// Next returns the next execution time after the given (previous) time.
// It will return a zero time if no next time is scheduled.
//
// All times must be UTC.
Next(time.Time) time.Time
}
Scheduler determines the execution plan of a task.
type Timer ¶
type Timer struct {
// contains filtered or unexported fields
}
Timer represents a single event. When the Timer expires, the given task will be executed.
func (*Timer) Stop ¶
Stop prevents the Timer from firing. It returns true if the call stops the timer, false if the timer has already expired or been stopped.
If the timer t has already expired and the t.task has been started in its own goroutine; Stop does not wait for t.task to complete before returning. If the caller needs to know whether t.task is completed, it must coordinate with t.task explicitly.
type TimingWheel ¶
type TimingWheel struct {
// contains filtered or unexported fields
}
TimingWheel is an implementation of Hierarchical Timing Wheels.
func NewTimingWheel ¶
func NewTimingWheel(tick time.Duration, wheelSize int64) *TimingWheel
NewTimingWheel creates an instance of TimingWheel with the given tick and wheelSize.
func (*TimingWheel) AfterFunc ¶
func (tw *TimingWheel) AfterFunc(d time.Duration, f func()) *Timer
AfterFunc waits for the duration to elapse and then calls f in its own goroutine. It returns a Timer that can be used to cancel the call using its Stop method.
func (*TimingWheel) ScheduleFunc ¶
func (tw *TimingWheel) ScheduleFunc(s Scheduler, f func()) (t *Timer)
ScheduleFunc calls f (in its own goroutine) according to the execution plan scheduled by s. It returns a Timer that can be used to cancel the call using its Stop method.
If the caller want to terminate the execution plan halfway, it must stop the timer and ensure that the timer is stopped actually, since in the current implementation, there is a gap between the expiring and the restarting of the timer. The wait time for ensuring is short since the gap is very small.
Internally, ScheduleFunc will ask the first execution time (by calling s.Next()) initially, and create a timer if the execution time is non-zero. Afterwards, it will ask the next execution time each time f is about to be executed, and f will be called at the next execution time if the time is non-zero.
func (*TimingWheel) Stop ¶
func (tw *TimingWheel) Stop()
Stop stops the current timing wheel.
If there is any timer's task being running in its own goroutine, Stop does not wait for the task to complete before returning. If the caller needs to know whether the task is completed, it must coordinate with the task explicitly.
Source Files