Highload-задачи

О чём этот блок

Когда нагрузка растёт, наивные решения перестают работать: один мьютекс на всю map превращается в узкое место, протухший популярный ключ роняет БД сотней одновременных запросов, неограниченный поток вызовов кладёт внешний API. Этот блок — про инженерные приёмы, которыми защищают highload-сервисы: rate limiting, дедупликация запросов, шардирование под контеншен и ограниченный параллельный обход.

Сквозная идея — управление давлением и контеншеном. Вы учитесь не просто «делать конкурентно», а делать это под конкретными ограничениями: не больше N запросов в секунду, не больше M одновременных вызовов, минимум блокировок на горячем пути.

Что вы научитесь делать

• Реализовывать rate limiting двумя способами: неблокирующий token bucket (есть токен — пропускаем) и блокирующий leaky bucket (сглаживаем всплески).
• Подавлять дублирующиеся вызовы (singleflight) и защищаться от cache stampede.
• Снижать контеншен через шардирование map на независимые сегменты со своими мьютексами.
• Параллельно обходить граф с ограничением одновременных вызовов (семафор) и защитой от циклов.
• Держать горячий путь быстрым и по возможности без аллокаций.

Карта задач

• 16 · Token Bucket Rate Limiter — неблокирующий Allow(); восполнение токенов во времени; быстрый горячий путь без аллокаций.
• 17 · Leaky Bucket (сглаживание всплесков) — блокирующий Acquire(); после выдачи одного разрешения начинается новый интервал; выравнивание темпа.
• 18 · Singleflight — подавление дублей: дорогая fn для ключа выполняется один раз, результат раздаётся всем ожидающим; защита от cache stampede.
• 19 · Concurrent Map с шардированием — 32 шарда со своими RWMutex; номер шарда по хешу (FNV); снижение контеншена при равномерном распределении ключей.
• 20 · Параллельный обход графа (BFS) — обход в ширину до глубины 3; семафор на 10 одновременных вызовов; visited против циклов; сборка результата без гонок.

Связанные главы учебника

• sync/atomic — атомарные счётчики токенов, contention на горячем пути.
• sync: примитивы — RWMutex для шардов, семафор на буферизированном канале.
• Паттерны конкурентности — semaphore, bounded parallelism, fan-out при обходе графа.

// Идиома блока: семафор на буферизированном канале ограничивает параллелизм.
sem := make(chan struct{}, 10)
sem <- struct{}{}        // занять слот (блокирует на 11-м)
go func() {
    defer func() { <-sem }() // освободить слот
    // ... ограниченная работа
}()