How to Detect Inactive Uber Drivers Without Third‑Party Tools: Go Time‑Wheel Solution

Scenario Description

Assume 1,000,000 Uber drivers, each driver client reports data every 10 minutes; if no report is received within 10 minutes, the server marks the driver offline and stops assigning orders. How can this be implemented without third‑party components?

Using a Timer

Maintain a Map<uid, last_time> to record the latest report time for each driver.

Update the map in real time when a driver reports.

Start a timer that periodically scans the map; if now - last_time > 30s, treat the driver as timed out.

var (
    userMap sync.Map
    timeout = 10 * time.Minute
)
func checkTimeout() {
    now := time.Now().Unix()
    userMap.Range(func(key, value any) bool {
        uid := key.(string)
        lastTime := value.(int64)
        if now-lastTime > int64(timeout) {
            fmt.Printf("User %s timed out. Last reported at %d
", uid, lastTime)
            userMap.Delete(uid)
        }
        return true
    })
}

Drawback: Inefficient because it requires periodic full‑map scans, leading to high time complexity.

Using Goroutine Management

Another approach assigns a dedicated goroutine to each driver to manage its heartbeat timeout.

timer := time.NewTimer(timeout * time.Second)
for {
    select {
    case <-heartbeat:
        if !timer.Stop() {
            <-timer.C
        }
        timer.Reset(timeout * time.Second)
    case <-timer.C:
        fmt.Printf("Driver %s timed out.
", uid)
        break
    }
}
userMap.Delete(uid)

Drawback: No polling, but each goroutine consumes stack memory; with millions of drivers memory usage becomes prohibitive, and timer creation/deletion costs O(log n).

Timing Wheel Algorithm

The timing wheel, introduced by George Varghese and Tony Lauck, uses a fixed‑size array where each slot represents a time interval. Core logic:

Each slot holds a slice of tasks expiring in that interval and a Map<uid, slot> to locate a driver’s slot.

A periodic timer advances the wheel by one position, processing all tasks in the current slot.

Implementation example: set interval = 1s, slots = 600; when a driver reports, insert its record into position‑1 slot.

package main
import (
    "log"
    "sync"
    "time"
)

type Driver struct {
    uid      string
    expireAt int64
}

type TimeWheel struct {
    drivers   map[string]*Driver
    slots     [][]*Driver
    position  int
    mu        sync.Mutex
    ticker    *time.Ticker
    stop      chan struct{}
    interval  int
    slotCount int
    timeoutSecs int
}

func NewTimeWheel(interval, slotCount, timeoutSecs int) *TimeWheel {
    tw := &TimeWheel{
        interval:   interval,
        slotCount:  slotCount,
        timeoutSecs: timeoutSecs,
        drivers:    make(map[string]*Driver),
        slots:      make([][]*Driver, slotCount),
        position:   0,
        ticker:    time.NewTicker(time.Duration(interval) * time.Second),
        stop:      make(chan struct{}),
    }
    for i := 0; i < slotCount; i++ {
        tw.slots[i] = make([]*Driver, 0)
    }
    go tw.run()
    return tw
}

func (tw *TimeWheel) Add(uid string) {
    tw.mu.Lock()
    defer tw.mu.Unlock()
    expireAt := time.Now().Unix() + int64(tw.timeoutSecs)
    driver := &Driver{uid: uid, expireAt: expireAt}
    tw.drivers[uid] = driver
    slot := tw.GetSlot(-1)
    tw.slots[slot] = append(tw.slots[slot], driver)
    log.Printf("time:%d,Driver %s added to slot %d
", time.Now().Unix(), uid, slot)
}

func (tw *TimeWheel) GetSlot(index int) int {
    return (tw.position + index + tw.slotCount) % tw.slotCount
}

func (tw *TimeWheel) run() {
    for {
        select {
        case <-tw.ticker.C:
            log.Printf("tick, position:%d
", tw.position)
            tw.mu.Lock()
            expired := tw.slots[tw.position]
            tw.slots[tw.position] = make([]*Driver, 0)
            tw.position = (tw.position + 1) % tw.slotCount
            tw.mu.Unlock()
            for _, driver := range expired {
                if time.Now().Unix() >= driver.expireAt {
                    tw.mu.Lock()
                    delete(tw.drivers, driver.uid)
                    tw.mu.Unlock()
                    log.Printf("Driver %s timeout
", driver.uid)
                }
            }
        case <-tw.stop:
            return
        }
    }
}

func (tw *TimeWheel) Stop() {
    close(tw.stop)
    tw.ticker.Stop()
}

Advantages

Adding a task is O(1) by appending to the appropriate slot.

Memory usage is bounded by the fixed number of slots.

Well‑suited for handling massive numbers of timed tasks.

Disadvantages

Precision limited by the chosen interval.

If tasks are unevenly distributed, deleting a task may degrade to O(n).

Timing wheels excel in scenarios requiring fast bulk insertion, modest timing precision, and relatively uniform task distribution.

Timing Wheel Optimizations

Simple Timing Wheel

Maintain an array whose length equals the maximum expiration interval; each index stores tasks expiring at that offset. Adding a task and advancing the clock are both O(1).

Start a task: compute its expiration offset and place it in the corresponding array cell (O(1)).

Clock tick: execute all tasks in the current cell (O(1)).

Hash‑Based Timing Wheel

When the maximum expiration interval is huge, a plain array wastes memory. Instead, hash the expiration value into a fixed‑size array (wheel size W, typically a power of two). Each bucket may hold multiple tasks sorted by absolute expiration, forming a linked list within the slot.

Drawback: With a single wheel, processing a bucket can be O(n) if many tasks land in the same slot.

Hierarchical Timing Wheel

Multiple wheels of increasing granularity solve the above issue. Each level has a fixed size n; the first level’s unit is u, the second level’s unit is n·u, and so on. Upper‑level wheels are created on demand. Tasks overflow from higher to lower wheels as time progresses, similar to Kafka’s Purgatory implementation.

Summary

The table below compares the algorithms (omitted for brevity). In practice, a hierarchical timing wheel offers low memory overhead, O(1) insertion, and logarithmic deletion, making it ideal for large‑scale, long‑lived task scheduling such as in Kafka or Netty.