Background

Recently, my codebase was scattered with random use of Go timers to perform dynamic tasks. Most tasks needed to be performed at random times in the future triggered from user inputs. Initially, my code had few random timer logic sprinkled over few files. As the codebase started to become larger I encountered "code-smell" problem. The idea of a hardcoded timers became unmanageable after certain point in time.

I mean you could still create a Higher Order Function to achieve the same task, but the problem was I still had to call cleanup functions manually after every use which was dangerous. Because, if I forgot to make the correct calls at the end, it would lead to unsolicited memory leaks. In addition, there is additional performance benefit that I will highlight below.

Wheel Of Timer was Born

1. Introduction: What is a Wheel of Timer?

Checkout the full library here

At the heart, a "Wheel of Timer" is like a highly efficient data structure helping to manage a large number of timers. Imagine it like a clock face. Each slot on the clock represents a specific time interval. When you want to set a timer, you place your task in the corresponding slot on the wheel. A "hand" or pointer moves around the wheel at a fixed interval, and when it lands on a slot, all the tasks in that slot are considered "expired" and ready to be processed (plucked).

This approach is significantly more performant than creating and managing individual timer instances, especially when dealing with thousands or even millions of timers. The key benefit is that adding, removing, and checking for expired timers can be done in constant time, O(1), making it a very scalable solution.

Having a generic based solution concocts an easy-to-use implementation of this concept which can inject value of any data type without the need for the inefficient interface in Go which takes up more memory.

2. Getting Started: A Quick Example

Before diving into the details, let's look at a simple example of how to use the library. The following code snippet demonstrates creating a timer wheel, adding a few tasks, and then retrieving them as they expire.

package main

import (
	"fmt"
	"time"
	"wot" // This is package that does the heavy lifting
)

func main() {
	// 1. Create a new thread-safe timer wheel.
	// Ticks every 100 milliseconds and has a max timeout of 10 seconds.
	tw := wot.NewLockingWoT[string](100*time.Millisecond, 10*time.Second)

	// 2. Add tasks with different timeouts.
	tw.Add("Task 1 after 1 sec", 1*time.Second)
	tw.Add("Task 2 after 2 sec", 2*time.Second)
	// This task's timeout will be capped at the wheel's max duration.
	tw.Add("Task 3 after 10 sec", 55*time.Second)

	fmt.Println("Timer wheel started. Waiting for tasks to expire...")

	// 3. Main loop to check for and process expired tasks.
	for {
		// Spin the wheel to move forward into the future time or the current time.
		tw.Spin(time.Now())

		// Retrieve all expired tasks.
		for {
			item, ok := tw.Pluck()
			if !ok {
				// No more expired items at this moment.
				break
			}
			fmt.Printf("Expired: %v\n", item)
		}

		// A short sleep to prevent a busy loop.
		time.Sleep(50 * time.Millisecond)
	}
}

3. Core Components

Our library consists of two main types for creating a timer wheel:

• WoT[T any]: The fundamental, non-thread-safe implementation of the timer wheel. You should use this if you are managing access to it from a single goroutine.

• LockingWoT[T any]: A thread-safe wrapper around WoT. This is the recommended choice for most use cases, as it protects against race conditions when timers are added or checked from multiple goroutines.

Both WoT and LockingWoT are generic, meaning they can hold any type of data T as the timer item. This could be a simple string, a struct, or even a function to be executed.

4. How to Use the Library

Using the Wheel of Timer library involves three main steps:

Step 1: Initialization

First, you need to create a new timer wheel. You'll use either NewWoT or NewLockingWoT for this.

// For a thread-safe wheel (recommended)
tw := wot.NewLockingWoT[string](tickDuration, wheelDuration)

// For a non-thread-safe wheel
tw := wot.NewWoT[string](tickDuration, wheelDuration)

Parameters:

• tickDuration (time.Duration): This is the smallest interval of time the wheel can measure, much like the tick of a clock's second hand. All timeouts will be rounded up to the nearest tickDuration.

• wheelDuration (time.Duration): This is the maximum timeout that the wheel can handle. Any timeout longer than this will be capped at wheelDuration.

Step 2: Adding Timers

To add a new timer, use the Add method.

tw.Add(item, timeout)

Parameters:

• item (T): The data you want to associate with the timer. The type T is determined when you initialize the wheel.

• timeout (time.Duration): The duration after which this item should expire.

Step 3: Checking for and Retrieving Expired Items

The timer wheel doesn't actively "push" expired items to you. Instead, you need to periodically check for them. This is done in a two-step process:

1. Spin(time.Now()): This method moves the wheel's internal "hand" to the current time. As the hand moves, it collects all the items from the slots it passes over. These items are then marked as expired. You should call this regularly in your application's main loop.

2. Pluck(): After calling Spin, you can use Pluck to retrieve the expired items one by one.

// In your main loop
tw.Spin(time.Now())

for {
    item, ok := tw.Pluck()
    if !ok {
        // No more expired items
        break
    }
    // Process the expired item
    fmt.Println("Expired:", item)
}

Pluck() Return Values:

• item (T): The expired item.

• ok (bool): Will be true if an expired item was returned, and false if there are no more expired items to pluck at this moment.

5. Understanding the Source Code (The one you find in the gist above)

For those interested in the implementation details:

• WoT[T any]: This struct contains the core logic.

  • wheel: A slice of *TimeoutList[T], where each element represents a "slot" on the wheel.

  • tickDuration: The resolution of the timer.

  • wheelDuration: The maximum timeout.

  • present: An integer representing the current position of the "hand" on the wheel.

  • expired: A list of items that have expired and are ready to be plucked.

• LockingWoT[T any]: This struct embeds a sync.Mutex and a pointer to a WoT instance, ensuring that all operations (Add, Pluck, Spin) are thread-safe.

• TimeoutItem[T any] and TimeoutList[T any]: These are used to implement a linked list of items within each slot of the wheel and in the expired list.

The findWheel function is responsible for calculating the correct slot on the wheel for a given timeout. The Spin function is the heart of the expiration logic, pushing the wheel and moving items from the wheel slots to the expired list. The Pluck function simply removes and returns the first item from the expired list. An internal cache for TimeoutItem objects is used to reduce memory allocations.

6. In a nutshell, these are the things you do to make use of the library

1. Initialize: Create a LockingWoT with a specific tick resolution and a maximum timeout duration.

2. Add Tasks: Use the Add(item, timeout) method to place any type of data onto the wheel to be retrieved later.

3. Check for Expirations: In a loop, call Spin(time.Now()) to move the wheel into the current time and then Pluck() to retrieve all tasks that have expired.