Highload-задачи

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

Под нагрузкой простые решения перестают работать. Один мьютекс на всю карту становится очередью, в которой стоят все запросы. Популярный ключ пропадает из кэша, и сотня одновременных запросов разом идёт в базу. Неограниченный поток вызовов упирается в лимит внешнего API. Блок про приёмы, которыми с этим справляются: ограничение частоты, объединение одинаковых запросов, шардирование и ограниченный параллельный обход.

Общее в задачах — работа под явными ограничениями: не больше N запросов в секунду, не больше M вызовов одновременно, как можно меньше блокировок на горячем пути.

Что понадобится

• Token bucket (неблокирующий Allow: есть жетон — пропускаем) и leaky bucket (блокирующий Acquire: выдаём разрешения равномерно).
• Singleflight: одновременные запросы с одним ключом выполняются один раз.
• Шардирование карты: несколько частей со своими мьютексами, номер части по хешу ключа.
• Семафор на буферизованном канале и защита от повторного посещения вершины.

Задачи

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

Что прочитать

Понятия для всех пяти задач — с числовыми примерами — собраны в разделе «Перед задачами блоков 5 и 7» главы «Паттерны». Там же семафор и шардирование.

• sync/atomic — счётчики на горячем пути и конкуренция за ячейку.
• sync: примитивы — RWMutex для шардов, sync.Map.

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