This article breaks down the content of Go timers. Timers are an important part of business development and infrastructure development, so you can see how important they are.

AfterFun to initialize a timer, the timer will eventually be added to a global timer heap, which is managed by Go runtime.

The global timer heap has undergone three major upgrades.

  • Before Go 1.9, all timers were maintained by a globally unique quadruple fork heap, with fierce competition between concurrent processes.
  • Go 1.10 - 1.13, all timers are maintained globally using 64 quad fork heaps, without essentially solving the pre-1.9 problem
  • After Go 1.14, each P maintains a separate quad fork heap.

Go 1.14 onwards has seen a quantum leap in timer performance, but along with that, timers have become the most complex and difficult data structures to sort out in Go. In this article, we won’t analyze every detail, but we’ll get a general idea of how the Go timer works.

1. Usage Scenarios

Go timer is often encountered in our code.

Scenario 1: Time-out prevention for RPC calls (the following code excerpt from dubbogo)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func (c *Client) Request(request *remoting.Request, timeout time.Duration, response *remoting.PendingResponse) error {
    _, session, err := c.selectSession(c.addr)
    // .. 省略
    if totalLen, sendLen, err = c.transfer(session, request, timeout); err != nil {
        if sendLen != 0 && totalLen != sendLen {
          // .. 省略
        }
        return perrors.WithStack(err)
    }

    // .. 省略
    select {
    case <-getty.GetTimeWheel().After(timeout):
        return perrors.WithStack(errClientReadTimeout)
    case <-response.Done:
        err = response.Err
    }
    return perrors.WithStack(err)
}

Scenario 2: Timeout Handling for Context

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func main() {
    ctx, cancel := context.WithTimeout(context.Background(), 1*time.Second)
    defer cancel()
    go doSomething()
    
    select {
    case <-ctx.Done():
        fmt.Println("main", ctx.Err())
    }
}

2. Illustrated source code

2.1 Principle of the quadruple heap

The timer’s global heap is a quadtree heap, especially since Go 1.14 each P maintains a quadtree heap, reducing concurrency problems between Goroutines and improving timer performance.

A quadtree is actually a quadtree, how does the Go timer maintain a quadtree?

  • When Go runtime schedules a timer, the timer with an earlier trigger time has to reduce its query count and be triggered as soon as possible. So the trigger time of the parent node of a quadtree is necessarily smaller than that of the child nodes.
  • As the name implies, the quadtree has at most four child nodes, and in order to take into account the speed of quadtree insertion, deletion and rearrangement, so the four sibling nodes are not required to be sorted by trigger time.

Here is a simple demonstration of timer insertion and deletion using two animated images.

Insert timer into heap.

Insert timer into heap

Remove timer from the heap.

Remove timer from the heap

2.2 How is the timer scheduled?

  • Call NewTimer, timer.After, timer.AfterFunc to produce timer, add it to the heap of the corresponding P.
  • Stop, timer.Reset to change the state of the corresponding timer.
  • GMP will call checkTimers during the scheduling cycle to iterate through the elements on the timer heap of the P and perform the real operation according to the state of the corresponding timer.

How is the timer scheduled

2.3 How is a timer added to the timer heap?

There are several ways to add timers to the scheduler.

  • After the timer is initialized with NewTimer, time.After, timer.
  • timer has been marked as timerRemoved, timer.Reset(d) is called, and the timer is added back to the timer heap of p
  • timer.Reset(d) is called before the timer is ready to be executed, the timer is detected by the GMP scheduler, removed from the timer heap, and then readded to the timer heap.
  • STW, the runtime releases the resources of the p that is no longer in use. p.destroy()->timer.moveTimers, the timers that are valid on the timers of the p that is no longer in use (states are: timerWaiting, timerModifiedEarlier, timer timerModifiedLater) are rejoined to a new timer of p.

2.4 How is the timer manipulated during Reset?

The purpose of Reset is to add the timer back to the timer heap and wait for it to be triggered again. However, there are two cases.

  • timers marked as timerRemoved, which have been removed from the timer heap, but will be added to the timer heap with a reset trigger time
  • timer waiting to be triggered, where only its trigger time and status (timerModifiedEarlier or timerModifiedLater) are modified in the Reset function. The timer whose state has been modified will also be added back to the timer heap, but triggered by the GMP and executed by checkTimers calling adjusttimers or runtimer.

How is the timer manipulated during Reset

2.5 How is the timer manipulated when stopped?

Stop is used to stop the timer from being triggered, i.e. to remove it from the timer heap. Stop does not actually delete the timer from p’s timer heap, it just changes the timer’s state to timerDeleted and waits for the GMP-triggered adjusttimers or runtimer to execute.

The functions that actually delete timers are two dodeltimer, dodeltimer0.

How is the timer manipulated when stopped

2.6 How is the timer actually executed?

The real executor of a timer is GMP. GMP calls timer.runtimer() with runtime.checkTimers during each scheduling cycle. timer.runtimer checks all timers on that p’s timer heap to see if they can be triggered.

If the timer can be triggered, a callback function sendTime will send a current time to the timer’s channel C, telling us that the timer has been triggered.

If it is a ticker, after it is triggered, it will calculate the next time to be triggered and add the timer to the timer heap again.

How is the timer actually executed

3. The pitfalls of timer usage

It’s true that timer is one of the more common tools we use in development, but timer is also one of the most likely culprits of memory leaks and CPU spikes.

However, a careful analysis shows that there are only two aspects that can cause problems.

  • Creating a lot of timers by mistake, resulting in wasted resources.
  • The program blocks because it does not actively close C when it stops.

3.1 Creating a lot of timers by mistake, resulting in wasted resources

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func main() {
    for {
        // xxx 一些操作
        timeout := time.After(30 * time.Second)
        select {
        case <- someDone:
            // do something
        case <-timeout:
            return
        }
    }
}

The above code is the most common way of writing timer exceptions, and it is also the most easy to ignore.

After the underlying timer is a call to timer. NewTimer, after NewTimer generates a timer, it will put the timer into the global timer heap.

NewTimer will create tens of thousands of timers and put them into the timer heap, causing the machine memory to skyrocket and causing CPU exceptions as the GMP cycle checkTimers and inserting new timers will traverse the timer heap like crazy.

AfterFunc also generates timers to be added to the timer, which should also be prevented from being called in a loop.

Solution: Use time.Reset to reset the timer and reuse the timer.

We already know that time.Reset resets the timer’s trigger time and then adds the timer back to the timer heap, waiting to be called by the trigger.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func main() {
    timer := time.NewTimer(time.Second * 5)    
    for {
        t.Reset(time.Second * 5)

        select {
        case <- someDone:
            // do something
        case <-timer.C:
            return
        }
    }
}

3.2 Program blocks, causing memory or goroutine leaks

1
2
3
4
5

func main() {
    timer1 := time.NewTimer(2 * time.Second)
    <-timer1.C
    println("done")
}

The above code can be seen, only when the timer timeout “done” will output, the principle is very simple: the program blocks on <-timer1. C, and the program can continue to execute.

However, special care should be taken when using timer. For example.

1
2
3
4
5
6
7
8
9

func main() {
    timer1 := time.NewTimer(2 * time.Second)
    go func() {
        timer1.Stop()
    }()
    <-timer1.C

    println("done")
}

Stop does not close channel C and keeps the program blocking on timer1.

If <- timer1.C was blocking in a subcoordinator and the timer was called with the Stop method, then the subcoordinator could be blocked forever, causing a goroutine leak and memory leak.

The correct way to use Stop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func main() {
    timer1 := time.NewTimer(2 * time.Second)
    go func() {
        if !timer1.Stop() {
            <-timer1.C
        }
    }()

    select {
    case <-timer1.C:
        fmt.Println("expired")
    default:
    }
    println("done")
}