How is the Go timer scheduled?

This article breaks down the Go timer. Timers are an important part of both business and infrastructure development, which shows how important they are.

Whether we initialise a timer with NewTimer, timer.After, or timer.AfterFun, the timer is eventually added to a global timer heap, which is managed by Go runtime.

The global timer heap has also undergone three major upgrades.

Before Go 1.9, all timers were maintained by a globally unique quad fork heap, with fierce competition between goroutines.
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 saw a quantum leap in timer performance, but with it came the most complex and difficult to sort out data structure in Go. In this article, we won’t go into every detail, but we’ll take a general look at how the Go timer works.

1. Usage Scenarios

Go timers are frequently encountered in our code.

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

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

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 The quadruple heap principle

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

A quadruple heap is really a quadtree, how does the Go timer maintain a quadruple heap?

When Go runtime schedules a timer, the timer with an earlier trigger time has to reduce the number of queries and be triggered as soon as possible. So the trigger time of the parent node of a quadtree is necessarily less than that of the child nodes.
In order to take into account the speed of insertion, deletion and rearrangement of quadtrees, the four sibling nodes are not required to be ordered by their trigger time.

Here is a simple demonstration of the insertion and deletion of a timer using two moving pictures

insert timer into heap

Remove timer from the heap

2.2 How is a timer dispatched?

Call NewTimer, timer.After, timer.AfterFunc to produce a timer, adding it to the heap of the corresponding P.
Stop, timer.Reset is called 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.

2.3 How is a timer added to the timer heap?

There are several ways to add timers to the scheduler.

After initializing a timer with NewTimer, time.After, timer.AfterFunc, the timer in question is placed on the timer heap of the corresponding p.
the 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 has reached the time it needs 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, removes the timers that are valid on the timers of the p that is no longer in use (states are: timerWaiting, timerModifiedEarlier, timerModifiedLater). timerModifiedLater) are rejoined to a new timer of p

2.4 How is the timer manipulated during Reset?

The purpose of a 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 are added to the timer heap by resetting the trigger time
a timer waiting to be triggered, where only its trigger time and status (timerModifiedEarlier or timerModifiedLater) are modified in the Reset function. The timer with this modified state is also re-added to the timer heap, but is triggered by GMP and executed by checkTimers calling adjusttimers or runtimer.

2.5 How is the timer manipulated when it stops?

Stop is used to stop the timer from being triggered, i.e. to remove it from the timer heap. However, timer.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 the timer are two dodeltimer, dodeltimer0.

2.6 How is the timer actually executed?

The real executor of a timer is the GMP. GMP calls timer.runtimer() with runtime.checkTimers each dispatch cycle. timer.runtimer checks all timers on the timer heap for that p 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’s a ticker, when it’s triggered, it will calculate the next time to be triggered and add the timer to the timer heap again.

3. The wrong use of the timer

It is true that timers are a common tool in our development, but they are also one of the most likely causes of memory leaks and CPU spikes.

However, a closer look reveals 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 doesn’t actively shut down C when it stops.

3.1 Incorrectly creating many timers, resulting in wasted resources

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

The reason for the problem is simple: timer.After is a call to timer.

For 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 cycles checkTimers and inserts new timers into the timer heap.

Note that not only does time.After generate timers, but NewTimer and time.

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.

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

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

3.2 Program blocking, causing memory or goroutine leaks

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

As you can see from the code above, the program will only output when the timer times out “done”, the principle is simple: the program blocks on <-timer1. When the timer is triggered, the callback function time.sendTime will send a current time to timer1. C so that the program can continue to execute.

However, special care should be taken when using timer.

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

    println("done")
}

The program will remain deadlocked. Because timer1.Stop does not close channel C, the program stays blocked on timer1.

This is an oversimplified example. Imagine if <- timer1.C was blocking on a child goroutine and the stop method of timer was called, then the child goroutine could be blocked forever, causing a goroutine leak and a memory leak.

The correct way to use Stop is.

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")
}

Table of Contents