Конкурентный планировщик ресурсов на Go: архитектура и реализация

Проблема: тысячи запросов к ограниченному пулу ресурсов

Представьте LLM-шлюз со 100 API-ключами. Каждый ключ имеет свои лимиты, приоритет, здоровье и состояние. На шлюз одновременно приходит тысячи запросов. Как выбрать лучший ресурс для каждого запроса, не заблокировав всю систему? В этой статье мы разберем архитектуру конкурентного планировщика ресурсов (CRS) на Go, которая решает эту задачу эффективно.

Наивный подход: глобальный мьютекс

Самое простое решение — защитить весь пул ресурсов одним мьютексом:

type Scheduler struct {
    mu        sync.Mutex
    resources []*Resource
}

func (s *Scheduler) Acquire() *Resource {
    s.mu.Lock()
    defer s.mu.Unlock()
    // сканируем все ресурсы, ищем лучший
    return best
}

При 10 ресурсах и 2 горутинах это работает. Но при 10 000 ресурсах и 5 000 конкурентных запросов все упирается в одну блокировку. Глобальный мьютекс превращается в узкое место: горутины выстраиваются в очередь, планировщик фактически работает последовательно.

Почему глобальный мьютекс — это проблема

1. Конкуренция за блокировку: только одна горутина может работать с пулом одновременно.
2. Линейное сканирование: поиск лучшего ресурса в массиве — O(N) на каждое получение.
3. Поддержание приоритетов: при изменении приоритетов нужно постоянно пересортировывать.
4. Переходы состояний: ресурсы перемещаются между ACTIVE, INACTIVE, REMOVED — все это требует синхронизации.
5. Наблюдаемость: метрики и колбэки не должны блокировать горячий путь.

Ключевая идея CRS: шардирование вместо глобальной блокировки

Вместо одного глобального мьютекса CRS разбивает ресурсы на независимые шарды, каждый со своей кучей и своим мьютексом. Это позволяет разным горутинам работать с разными шардами параллельно, снижая конкуренцию.

Архитектура CRS

Система состоит из нескольких слоев: стратегии получения, карты поиска, хранилища неактивных ресурсов и диспетчера событий. Рассмотрим каждый компонент.

Шардированные кучи приоритетов

Каждый шард содержит кучу приоритетов. Например, шард 1 может содержать элементы с приоритетами 10, 20, 30, а шард 2 — с приоритетами 5, 15, 25. У каждого шарда свой мьютекс, поэтому операции над разными шардами не блокируют друг друга.

Карта поиска O(1)

Куча эффективно отвечает на вопрос «какой ресурс лучший?», но не на вопрос «где находится ресурс X?». Для этого CRS поддерживает отдельную карту, которая по ключу (например, имени ресурса) возвращает узел в куче. Карта защищена отдельным RWMutex и позволяет выполнять операции Get, Update, Remove за O(1).

Приоритет и получение — разные задачи

Приоритет ресурса не определяет, какой шард проверять первым. CRS разделяет стратегию получения (какой шард выбрать) и порядок приоритетов (какой ресурс внутри шарда лучший). Это позволяет подключать разные стратегии маршрутизации без изменения кучи.

Стратегии получения ресурсов

CRS предоставляет несколько стратегий: Round Robin, Weighted, Adaptive и Consistent Hashing для affinity-маршрутизации.

Round Robin

Самая простая стратегия: запросы по очереди направляются к шардам. Request 1 → Shard 1, Request 2 → Shard 2 и так далее. Предсказуемо и просто. Подходит, когда шарды однородны.

Weighted Acquire

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

Adaptive Acquire

Адаптивная стратегия отслеживает время ответа или загрузку каждого шарда и динамически перенаправляет запросы на менее загруженные. Это полезно при неравномерной нагрузке.

Affinity Routing

Использует консистентное хеширование, чтобы запросы с одинаковым ключом попадали на один и тот же шард. Это важно для кэширования или поддержания сессий.

Жизненный цикл ресурса

Ресурсы могут находиться в состояниях ACTIVE, INACTIVE и REMOVED. Переходы между состояниями атомарны и синхронизированы. Неактивные ресурсы хранятся отдельно, чтобы не замедлять поиск в активных кучах.

Пакетные операции и обновления

CRS поддерживает пакетное добавление и удаление ресурсов. Обновление приоритета выполняется без разрушения порядка кучи: ресурс удаляется, обновляется и вставляется заново. Это гарантирует согласованность.

Кулдауны и асинхронные события

После использования ресурс может уйти в кулдаун. CRS обрабатывает это асинхронно, не блокируя основные операции. События (например, изменение состояния) отправляются в диспетчер, который может обновлять метрики или запускать кулдаун.

Наблюдаемость и интеграция с Prometheus

CRS собирает метрики: количество активных ресурсов, время ожидания, количество ошибок. Данные экспортируются в Prometheus для мониторинга.

Модель конкурентности

Основная идея — минимизировать общие блокировки. Каждый шард имеет свой мьютекс, карта поиска — RWMutex, а события обрабатываются отдельно. Это позволяет масштабироваться до тысяч конкурентных запросов.

Сложность алгоритмов

Получение ресурса в худшем случае O(log N) для кучи + O(1) для карты. Вставка и удаление также O(log N). Пакетные операции выполняются за O(N log N).

Тестирование библиотеки

CRS тщательно протестирован с помощью детектора гонок и нагрузочных тестов: 10 000 конкурентных воркеров, тесты на пиковые нагрузки, отказы и кулдауны. Это подтверждает корректность и производительность.

Пример: LLM-шлюз

Ниже приведен минимальный пример использования CRS для шлюза с API-ключами:

// Создаем планировщик с 4 шардами
sched := crs.NewScheduler(crs.Config{
    ShardCount: 4,
    AcquireStrategy: crs.RoundRobin,
})

// Добавляем ресурсы (API-ключи)
sched.Add(&crs.Resource{
    ID: "key-1",
    Priority: 10,
})
sched.Add(&crs.Resource{
    ID: "key-2",
    Priority: 5,
})

// Получаем лучший ресурс
res := sched.Acquire()
if res != nil {
    defer sched.Release(res.ID)
    // используем ключ
}

Почему CRS доменно-независим?

Планировщик не знает, что такое ресурс. Он знает только: «У меня есть ресурсы, мне нужно безопасно их поддерживать, расставлять приоритеты и возвращать подходящий конкурентному вызывающему». Это позволяет использовать CRS для API-ключей, пулов соединений, GPU-воркеров и многого другого.

Принципы проектирования

• Минимизация блокировок: шардирование вместо глобального мьютекса.
• Разделение ответственности: стратегия получения отделена от приоритетной кучи.
• Асинхронные события: не блокируют горячий путь.
• Наблюдаемость: метрики и колбэки не влияют на производительность.

Уроки, извлеченные при разработке

Главный урок: не пытайтесь решить все одной блокировкой. Разделяйте задачи и используйте специализированные структуры данных. Также важно тестировать под нагрузкой с детектором гонок.

Когда не стоит использовать CRS

Если у вас всего несколько ресурсов и низкая конкурентность, CRS может быть избыточен. Простой мьютекс будет проще и быстрее.

Будущие направления

Планируется добавить поддержку приоритетов с динамическим изменением, более сложные адаптивные стратегии и интеграцию с OpenTelemetry.

Итоги

CRS — это мощный инструмент для управления пулами ресурсов под высокой нагрузкой. Он сочетает в себе эффективные структуры данных, гибкие стратегии и надежную конкурентность. Попробуйте его в своем следующем проекте!