9.10 Таймеры

time.Sleep, time.After, time.Timer, time.Ticker и даже SetDeadline для сетевого чтения и записи — всё это опирается на одну и ту же инфраструктуру таймеров. Она должна отвечать на вопрос, который выглядит простым, но на деле весьма тонок — вопрос о структурах данных: когда одновременно существуют тысячи таймеров, как эффективно определить «кого нужно разбудить следующим, и когда», не выжигая при этом отдельный поток? Этот раздел начинается с постановки абстрактной задачи, разбирает компромиссы различных решений и приходит к выбору Go и его эволюции.

9.10.1 Задача выбора структуры данных для таймеров

Инфраструктура таймеров должна поддерживать три операции: START (зарегистрировать таймаут), STOP (отменить до истечения) и проверку истечения / EXPIRY (тактовый момент наступил — срабатывает всё просроченное). Сложность в том, что тактовый момент может проверяться тысячи раз в секунду вне зависимости от того, истёк ли хоть какой-то таймер, — значит, стоимость «на каждый такт» должна быть низкой, при этом START и STOP тоже обязаны быть быстрыми. Сравнение сложности нескольких наивных схем — именно отправная точка классической статьи Варгезе и Лака 1987 года:

Схема	START	STOP	Проверка на каждый такт	Извлечение просроченных
Несортированный список	$O(1)$	$O(1)$	$O(n)$ сканирование	$O(n)$
Отсортированный список	$O(n)$	$O(1)$	$O(1)$ взгляд на голову	$O(1)$
Минимальная куча	$O(\log n)$	$O(\log n)$	$O(1)$ взгляд на вершину	$O(\log n)$ каждый

Здесь часто возникает одна неточность: «найти минимум» в куче — это $O(1)$ , но удаление и просеивание вниз при срабатывании каждого просроченного таймера стоит $O(\log n)$ . Поэтому «дешёвая проверка на такт» означает лишь то, что сама проверка дешёва; фактическое извлечение $k$ просроченных таймеров обходится в $O(k \log n)$ . Каждая из трёх наивных схем имеет своё достоинство, однако ни одна не выигрывает одновременно по START, STOP и проверке истечения. Именно для разрешения этого тупика и было придумано колесо таймеров.

9.10.2 Колесо таймеров: пространство в обмен на время

Ответ Варгезе и Лака — колесо таймеров; идея напоминает стрелки часов.

Простое колесо таймеров: кольцевой массив из $N$ слотов, один временной такт на слот, плюс указатель «текущего времени». Регистрация таймера с истечением через $j$ тактов ( $j < N$ ) выполняет вставку за $O(1)$ в слот $(now+j) \bmod N$ ; на каждом такте указатель продвигается на один слот и запускает таймеры из этого слота. START, STOP и обслуживание на каждый такт — всё за $O(1)$ , но только для таймаутов, не превышающих длину колеса $N$ . Это ограничение по диапазону — именно причина существования двух следующих вариантов.
Хешированное колесо таймеров: при большом диапазоне таймаутов они хешируются в меньшее колесо (записи в слоте сортируются по признаку «сколько ещё оборотов осталось»), достигая средней сложности $O(1)$ при равномерном распределении.
Иерархическое колесо таймеров: несколько колёс разной гранулярности, подобно часовой, минутной и секундной стрелкам; длинные таймауты записываются на наиболее грубом колесе, а при истечении каскадируют в более мелкие для точного срабатывания. Охватывает огромный диапазон при ограниченном использовании памяти, ценой накладных расходов на каскадирование при переходе между уровнями.

flowchart LR
    subgraph WHEEL["Простое колесо таймеров (кольцевой массив из N слотов)"]
      direction LR
      S0["Слот 0"] --- S1["Слот 1"] --- S2["Слот 2"] --- S3["..."] --- SN["Слот N-1"]
    end
    PTR["Указатель текущего времени<br/>продвигается на один слот за такт"] --> S2
    INS["Регистрация с истечением через j тактов"] -->|"вставка O(1) в (now+j) mod N"| S3

Колесо таймеров переносит стоимость с «каждой операции» на «размер колеса и каскадирование» — классический обмен пространства на время, который хорошо окупается при сценарии «ограниченный диапазон таймаутов, большинство таймеров отменяются до срабатывания». Go не пошёл этим путём — причина станет ясна в 9.10.8.

9.10.3 Выбор Go: одна 4-арная куча на каждый P

Go выделяет каждому P минимальную кучу, и эта куча является 4-арной (timerHeapN = 4). У 4-арной кучи меньше уровней, чем у двоичной ( $\log_4 n$ ); просеивание на одном уровне требует сравнения 4 дочерних узлов вместо 2, однако меньшее число уровней, как правило, даёт лучшую кэш-эффективность. Это не интуиция, а оптимизация 2013 года, подкреплённая бенчмарком («лучшая производительность при большом числе таймеров»). Куча хранится в массиве; родитель элемента с индексом $i$ находится по индексу $\lfloor (i-1)/4 \rfloor$ , его дочерние узлы — по индексам с $4i+1$ по $4i+4$ .

flowchart LR
    subgraph P1["P1"]
      T1["timers.heap<br/>4-арная минимальная куча (по when)"]
    end
    subgraph P2["P2"]
      T2["timers.heap<br/>4-арная минимальная куча"]
    end
    SCHED["цикл планирования / netpoll / sysmon"] -->|"wakeTime считывает ближайшее время истечения"| T1
    SCHED -->|"check запускает истёкшие таймеры"| T2
    P2 -. "take переносит таймеры при уничтожении P" .-> P1

Набор таймеров каждого P собран в тип timers, навешенный на pp.timers. Если убрать детали блокировки и обнаружения гонок и оставить только поля, значимые для дизайна:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


// timers: набор таймеров конкретного P (эскиз)
type timers struct {
    heap []timerWhen   // 4-арная минимальная куча, отсортированная по when; timerWhen кешируется when, экономя разыменование

    len     atomic.Uint32 // атомарная копия len(heap), для проверки опустошения без блокировки в планировщике
    zombies atomic.Int32  // счётчик таймеров, помеченных удалёнными, но ещё не извлечённых из кучи (ленивое удаление)

    // wakeTime использует эти две нижние границы для вычисления "когда нужно проснуться" — без блокировки и обхода кучи
    minWhenHeap     atomic.Int64 // heap[0].when — ближайшее время истечения в куче
    minWhenModified atomic.Int64 // нижняя граница when для таймеров, сдвинутых раньше (timerModified), но ещё не переставленных в куче
}

Элемент timerWhen в heap хранит when вместе с *timer, чтобы сравнение не требовало разыменования таймера при каждом обращении — небольшая оптимизация для кэш-локальности. Пара атомиков minWhenHeap и minWhenModified — ключевой элемент: они позволяют планировщику одним взглядом считать «ближайшее время истечения» без захвата блокировки таймеров (см. 9.10.5); zombies обслуживает ленивое удаление (см. 9.10.4).

Отдельный таймер представлен типом timer; его состояние упаковано в несколько битов:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// timer: один таймер (эскиз)
type timer struct {
    when   int64  // время истечения (абсолютное значение nanotime)
    period int64  // > 0 означает периодическое срабатывание (Ticker), следующее срабатывание через when+period
    f      func(arg any, seq uintptr, delay int64) // коллбэк при истечении, не должен блокироваться
    arg    any    // аргумент коллбэка: канал или функция в пакете time; иное значение в netpoll

    ts    *timers // timers того P, в котором таймер находится в данный момент
    state uint8   // биты состояния: timerHeaped / timerModified / timerZombie
}

В state всего три бита, однако они кодируют всё отношение таймера к куче: timerHeaped означает, что таймер находится в куче некоторого P; timerModified — что его when изменилось, но позиция в куче ещё не исправлена, отложена до следующей реорганизации; timerZombie — что таймер остановлен, но всё ещё присутствует в куче без удаления. До Go 1.14 для координации конкурентности использовался автомат состояний с десятью возможными значениями; после 1.23 он был упрощён до этих трёх битов плюс единственная блокировка t.mu, при этом снимок состояния astate публикуется атомарно, чтобы быстрый путь мог принимать решения без захвата блокировки (см. 9.10.7).

9.10.4 Регистрация, остановка и ленивое удаление

Регистрация таймера (START) — это просто добавление его в кучу текущего P. time.NewTimer проходит через startTimer в t.maybeAdd рантайма и в конечном счёте вызывает ts.addHeap: добавить в хвост массива, затем siftUp для всплытия на правильную позицию, и обновить minWhenHeap, если таймер оказывается новой вершиной кучи:

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


// добавить таймер в 4-арную кучу текущего P (эскиз)
func (ts *timers) addHeap(t *timer) {
    if netpollInited.Load() == 0 {
        netpollGenericInit() // таймеры полагаются на опросчик сети для пробуждения; убедиться, что он запущен
    }
    t.ts = ts
    ts.heap = append(ts.heap, timerWhen{t, t.when})
    ts.siftUp(len(ts.heap) - 1)        // всплытие O(log n)
    if t == ts.heap[0].timer {
        ts.updateMinWhenHeap()         // стал новым ближайшим, обновить нижнюю границу
    }
}

Сложность остановки (STOP) в том, что таймер может находиться в куче другого P, которым текущая горутина не владеет. Захватывать блокировку и удалять элемент из чужой кучи по одному — дорого и порождает конкуренцию. Подход Go — ленивое удаление: t.stop только устанавливает пометку timerZombie на таймере и увеличивает счётчик zombies в содержащем его timers, оставляя фактическое удаление тому P для завершения при следующей реорганизации его кучи:

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


// остановить таймер: только установить пометку, не удалять немедленно (эскиз)
func (t *timer) stop() bool {
    t.lock()
    if t.state&timerHeaped != 0 {
        t.state |= timerModified
        if t.state&timerZombie == 0 {
            t.state |= timerZombie
            t.ts.zombies.Add(1)   // zombies +1, оставить для очистки cleanHead / adjust
        }
    }
    pending := t.when > 0
    t.when = 0
    t.unlock()
    return pending
}

Зомби-таймеры не накапливаются бесконтрольно. Куча таймеров очищается в двух местах: cleanHead выталкивает зомби с вершины, а adjust попутно удаляет их при реорганизации кучи. Момент запуска очистки выбирается намеренно: только когда речь идёт о куче текущего P и счётчик зомби превышает четверть длины кучи (zombies > len/4), check принудительно запускает очистку. У этого порога есть своя история: в ранних версиях код наподобие context.WithTimeout, часто создающий и отменяющий таймеры, оставлял большое число остановленных таймеров в куче, расходуя память, и порог 1/4 был добавлен именно для устранения этой утечки (подробнее в 9.10.6). Ограничение очистки только локальным P, в свою очередь, призвано избежать захвата блокировки чужого P и снизить конкуренцию.

stateDiagram-v2
    [*] --> Heaped: addHeap (регистрация)
    Heaped --> Zombie: stop (только пометить)
    Heaped --> Modified: modify (изменить when)
    Modified --> Heaped: adjust (переупорядочить)
    Zombie --> [*]: cleanHead / adjust (пакетная очистка)
    Heaped --> [*]: run (сработать при истечении и удалить)

9.10.5 Встроенная проверка истечения: без выделенного потока

Наиболее примечательный момент состоит в том, что проверка истечения не требует выделенного потока; она выполняется попутно. Два связанных между собой вызова обеспечивают это. wakeTime не захватывает блокировку и читает только пару атомарных нижних границ, вычисляя «ближайшее время истечения», — это значение используется для ограничения длительности блокировки в планировщике и опросчике сети (9.9):

1
2
3
4
5
6
7
8
9


// когда следует проснуться в следующий раз; без блокировки, только чтение атомарных нижних границ (эскиз)
func (ts *timers) wakeTime() int64 {
    nextWhen := ts.minWhenModified.Load()
    when := ts.minWhenHeap.Load()
    if when == 0 || (nextWhen != 0 && nextWhen < when) {
        when = nextWhen
    }
    return when   // 0 означает, что таймеров нет
}

check вызывается в цикле планирования (schedule -> findRunnable), при краже задач, в sysmon (9.8) и в ряде других мест. Функция сначала взглядом считывает ближайшее время истечения через wakeTime; если ничего не просрочено и зомби для очистки нет — немедленно возвращается (именно так заканчивается подавляющее большинство вызовов, почти без накладных расходов); только когда что-то просрочено, она захватывает блокировку, вызывает adjust для реорганизации кучи, а затем в цикле запускает run для всех просроченных таймеров:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


// запустить все просроченные таймеры (эскиз)
func (ts *timers) check(now int64, ...) (rnow, pollUntil int64, ran bool) {
    next := ts.wakeTime()
    if next == 0 {
        return now, 0, false   // таймеров нет
    }
    if now == 0 {
        now = nanotime()
    }
    // принудительная очистка только если зомби превышают 1/4 длины кучи и это локальный P
    force := ts == &getg().m.p.ptr().timers && int(ts.zombies.Load()) > int(ts.len.Load())/4
    if now < next && !force {
        return now, next, false   // ничего не просрочено и очистка не нужна: быстрый возврат
    }
    ts.lock()
    if len(ts.heap) > 0 {
        ts.adjust(now, false)             // реорганизовать кучу, попутно очищая зомби
        for len(ts.heap) > 0 {
            if tw := ts.run(now, ...); tw != 0 {  // запустить просроченную вершину кучи
                pollUntil = tw
                break
            }
            ran = true
        }
    }
    ts.unlock()
    return now, pollUntil, ran
}

Таким образом, срабатывание таймеров распределено по существующим точкам пробуждения планировщика, а не монополизирует отдельную горутину. Особенно элегантна одна деталь в краже задач: когда P не имеет работы и переходит в stealWork внутри findRunnable, чтобы украсть горутины у другого P, он попутно вызывает p2.timers.check для P-жертвы, запуская его просроченные таймеры вместо него. Иначе говоря, простаивающий P помогает очистить кучу таймеров другого, распределяя нагрузку по истечению, которую иначе нёс бы занятый P. Когда нет вообще ни одного работающего P, checkTimersNoP в состоянии «без P» просматривает wakeTime всех P и на основании этого определяет, на сколько должен заблокироваться опросчик сети.

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


// фаза кражи задач в findRunnable (минимальный эскиз)
func stealWork(now int64) (gp *g, ..., pollUntil int64, ...) {
    for i := 0; i < stealTries; i++ {
        stealTimersOrRunNextG := i == stealTries-1   // только последний раунд проверяет ещё и таймеры
        for enum := ...; !enum.done(); enum.next() {
            p2 := allp[enum.position()]
            if stealTimersOrRunNextG && timerpMask.read(enum.position()) {
                tnow, w, ran := p2.timers.check(now, nil)  // запустить просроченные таймеры p2
                now = tnow
                if w != 0 && (pollUntil == 0 || w < pollUntil) {
                    pollUntil = w
                }
                _ = ran
            }
            // ... затем попытаться украсть горутины через runqsteal
        }
    }
    return
}

Дедлайны сетевых операций чтения и записи повторно используют ту же инфраструктуру, а не строят отдельную. pollDesc (9.9) встраивает два таймера — для чтения и для записи — вместе с соответствующими дедлайнами и порядковым номером seq:

1
2
3
4
5
6
7
8
9


// pollDesc: один на каждый сетевой fd (поля, относящиеся к дедлайнам, эскиз)
type pollDesc struct {
    rseq uintptr // защищает от ложного срабатывания устаревшего таймера чтения
    rt   timer   // таймер дедлайна чтения
    rd   int64   // дедлайн чтения (будущее значение nanotime, -1 означает уже истёк)
    wseq uintptr // защищает от ложного срабатывания устаревшего таймера записи
    wt   timer   // таймер дедлайна записи
    wd   int64   // дедлайн записи
}

conn.SetDeadline — это по сути перезапись rd / wd и соответствующий modify двух встроенных таймеров; seq используется для идентификации и подавления устаревших срабатываний, ставших недействительными из-за сброса дедлайна. Когда дедлайн наступает, коллбэк таймера пробуждает горутину, заблокированную на данном fd. Одна куча обслуживает как пакет time, так и все дедлайны сетевого ввода-вывода.

9.10.6 История переписываний

Таймер — одна из наиболее переписанных частей рантайма Go; главная нить изменений — «всё глубже интегрируется в планировщик, всё более распределённым становится». Эта история также даёт хороший повод развеять несколько широко распространённых заблуждений.

4-арная куча как таковая была введена ещё в Go 1.2 (2013) как самостоятельная оптимизация производительности; она появилась раньше последующего шардирования и не пришла вместе с ним (распространённое заблуждение).
Go 1.10 заменил единственную глобальную кучу массивом фиксированного размера из 64 бакетов (timersLen = 64), назначаемых по номеру P по модулю. Важно: размер не масштабируется с GOMAXPROCS и это не одна куча на P (ещё одно расхожее недоразумение). Сообщение коммита того времени прямо гласило: масштабирование по GOMAXPROCS потребовало бы динамического перераспределения, а 64 — компромисс между памятью и производительностью.
Только в Go 1.14 таймеры были разделены по-настоящему на кучи per-P, интегрированы в планировщик и опросчик сети, а выделенная горутина timerproc была удалена (серия изменений под руководством Иана Лэнса Тейлора). Поводом послужил конкретный баг производительности: Ticker с периодом 1 мс из-за пробуждений timerproc и конкуренции за глобальную блокировку потреблял 20–25% CPU (issue #27707). В этой же версии было введено ленивое удаление «очищать при превышении 1/4 зомби», чтобы устранить утечку памяти от часто создаваемых и отменяемых таймеров вида context.WithTimeout.
Go 1.23 выполнил ещё один раунд внутренней доработки (Расс Кокс), собрав состояние таймеров per-P в описанный выше тип timers, и устранил давнюю семантическую ловушку: канал таймера стал небуферизованным (ёмкость 0), что гарантирует отсутствие устаревшего значения после возврата из Stop / Reset; незарефиренные Timer / Ticker теперь также могут быть немедленно собраны GC. Старое асинхронное поведение сохранено за флагом GODEBUG=asynctimerchan=1.

flowchart LR
    A["Go 1.2 (2013)<br/>4-арная куча<br/>единственная глобальная куча"]
    A --> B["Go 1.10 (2018)<br/>фиксированный массив из 64 бакетов<br/>не масштабируется по GOMAXPROCS"]
    B --> C["Go 1.14 (2020)<br/>истинно per-P куча<br/>удаление timerproc<br/>ленивое удаление (#27707)"]
    C --> D["Go 1.23 (2024)<br/>собрано в тип timers<br/>небуферизованный канал<br/>немедленно собирается GC"]

При уничтожении P таймеры из его кучи не теряются: они переносятся функцией take на P-преемника. Перенос обходит таймеры кучи по одному, пропуская ставшие зомби или уже недействительные:

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


// при уничтожении P перенести таймеры src в текущий P (эскиз)
func (ts *timers) take(src *timers) {
    if len(src.heap) > 0 {
        for _, tw := range src.heap {
            t := tw.timer
            t.ts = nil
            if t.updateHeap() {   // пропустить зомби / недействительные, иначе переставить
                t.ts = ts
                ts.heap = append(ts.heap, timerWhen{t, t.when})
            }
        }
        src.heap = nil
        src.zombies.Store(0)
        src.len.Store(0)
        ts.siftUpAll()           // перестроить кучу за один проход
    }
}

9.10.7 Как это устроено у других

Реализация таймеров — хорошее окно в тему «как выбор структуры данных меняется вместе со сценарием».

Ядро Linux использует одновременно два механизма. Грубозернистый, применяемый преимущественно для I/O-таймаутов, которые «скорее всего будут отменены», работает на колесе таймеров (kernel/time/timer.c); масштабная переработка Гляйкснера в 2016 году (версия 4.8) просто упразднила каскадирование, используя 8 уровней и битовую карту для нахождения следующего просроченного таймера за $O(1)$ , ценой принятия потери точности в худшем случае около 12,5%, — мотивация в точности та же: «большинство таймаутов отменяются до срабатывания». Высокоточные таймеры идут отдельным путём через hrtimer, сортируя по времени с помощью красно-чёрного дерева (kernel/time/hrtimer.c).
HashedWheelTimer в Netty назван непосредственно в честь работы Варгезе-Лака и является инженерной реализацией хешированного колеса таймеров.
libevent использует двоичную минимальную кучу, nginx — красно-чёрное дерево, а ScheduledThreadPoolExecutor в Java — двоичную минимальную кучу на массиве (DelayedWorkQueue). Erlang/BEAM использует колесо таймеров.

Прослеживается закономерность: системы, в которых доминируют «таймауты, которые будут отменены», и способные принять квантование точности (базовое колесо ядра, Netty), предпочитают $O(1)$ колеса таймеров; сценарии, требующие точности на неограниченном диапазоне (libevent, nginx, Java, Go), — кучу или дерево.

9.10.8 Почему Go выбрал кучу, и сохраняющиеся противоречия

Go выбрал per-P кучу вместо колеса таймеров как инженерный компромисс, а не теоретическое утверждение. Куча сортирует по абсолютному значению int64 времени на неограниченном диапазоне, одинаково обращаясь с микросекундным Sleep и с дедлайном context продолжительностью в час, — без ни ограниченного диапазона колеса, ни его накладных расходов на каскадирование; она проста, и её точность ограничена лишь «частотой проверок»; она может жить рядом с планировщиком, повторно используя существующие точки пробуждения без выделенного потока; наконец, шардирование по P устраняет конкуренцию за блокировку единственного глобального колеса / кучи — именно это доказала эволюция 1.10 → 1.14 и бенчмарк #27707.

Противоречия сохраняются. Слабое место кучи — STOP за $O(\log n)$ , а наивное удаление фрагментирует массив; Go компенсирует это «пометкой зомби плюс периодической очисткой», тогда как $O(1)$ отмены колеса теоретически лучше в высоко-динамичных сценариях наподобие пула соединений, часто устанавливающего и сбрасывающего дедлайны. Помимо этого, компромисс между точностью и накладными расходами (квантование у колеса ядра vs. точность кучи), объединение таймеров для экономии энергии и давление частых Ticker-ов на путь пробуждения — всё это остаётся активными темами в данной области. Выигрыш в производительности никогда не достаётся бесплатно; он всегда сопровождается перераспределением сложности — и именно это снова и снова демонстрирует данная глава.

Дополнительная литература

George Varghese, Anthony Lauck. “Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility.” SOSP 1987; IEEE/ACM Trans. Networking 5(6), 1997. https://doi.org/10.1145/41457.37504
Sokolov Yura. time: make timers heap 4-ary (Go 1.2), 2013. https://golang.org/cl/13094043
Dmitry Vyukov. runtime: make timers faster. Go issue #6239, 2013. https://golang.org/issue/6239 (узкое место масштабируемости единственной глобальной кучи таймеров, мотивация для последующего переноса per-P)
Aliaksandr Valialkin. runtime: improve timers scalability on multi-CPU systems (Go 1.10, 64 бакетов), 2017. https://go-review.googlesource.com/34784
golang/go#27707. time: excessive CPU usage when using Ticker and Sleep (послужил основой для per-P таймеров в 1.14). https://github.com/golang/go/issues/27707
Ian Lance Taylor. runtime: add timers to P (серия изменений per-P таймеров для Go 1.14), 2019. https://go-review.googlesource.com/c/go/+/171828
Go 1.23 Release Notes (небуферизованный канал таймера, немедленная сборка GC). https://go.dev/doc/go1.23 ; реализацию см.: The Go Authors. runtime/time.go (type timers, addHeap, check, take). https://github.com/golang/go/blob/master/src/runtime/time.go
Thomas Gleixner. timers: Switch to a non-cascading wheel (Linux 4.8), 2016. https://git.kernel.org/torvalds/c/500462a9de65 ; LWN: https://lwn.net/Articles/646950/
The Linux Kernel. hrtimers — high-resolution kernel timers. https://www.kernel.org/doc/html/latest/timers/hrtimers.html
Netty. HashedWheelTimer (based on Varghese-Lauck). https://netty.io/4.1/api/io/netty/util/HashedWheelTimer.html