Fair Scheduler¶

Fair Scheduler — это планировщик ресурсов для распределённых вычислительных систем, в первую очередь для кластеров Hadoop, реализующий алгоритм справедливого распределения вычислительных мощностей (честного разделения ресурсов) между несколькими пользователями, группами или приложениями. Основная цель Fair Scheduler — гарантировать, что все активные задания (jobs) в системе получают равную долю ресурсов кластера (процессорного времени, памяти, дискового ввода-вывода) в течение длительного периода времени, независимо от их размера, приоритета или времени запуска. Этот подход отличается от традиционного планировщика FIFO (First In, First Out), где задания выполняются строго в порядке очереди, что может приводить к длительному ожиданию для коротких задач, запущенных после больших.

¶История и происхождение

Fair Scheduler был разработан в 2009 году инженерами компании Facebook (организация Meta признана экстремистской и запрещена в РФ) для решения проблемы неэффективного использования ресурсов в кластерах Hadoop. В ранних версиях Hadoop использовался планировщик FIFO, который при запуске одного большого задания блокировал все ресурсы кластера, заставляя мелкие задания ждать его завершения. Это было неприемлемо для компаний, где одновременно работали сотни пользователей с разными по размеру задачами.

Первая реализация Fair Scheduler была представлена как часть проекта Apache Hadoop в версии 0.20.0. В 2011 году планировщик был включён в состав дистрибутива Apache Hadoop 1.0.0. Позднее, с появлением Hadoop YARN (Yet Another Resource Negotiator) в версии 2.0, Fair Scheduler был переработан и стал одним из трёх стандартных планировщиков (наряду с Capacity Scheduler и FIFO Scheduler). В настоящее время Fair Scheduler поддерживается в рамках проекта Apache Hadoop и активно используется в различных корпоративных средах.

¶Основные принципы работы

¶Справедливое распределение (Fairness)

Основной принцип Fair Scheduler заключается в том, что каждое задание (или пул заданий) получает равную долю ресурсов кластера. Если в системе работает N заданий, каждое из них получает примерно 1/N от общего объёма ресурсов. Если задание не может использовать свою долю (например, из-за отсутствия данных), она перераспределяется между другими заданиями.

¶Минимальные и максимальные гарантии

Fair Scheduler позволяет администраторам задавать минимальные и максимальные гарантии ресурсов для отдельных пользователей, групп или приложений. Минимальная гарантия (minimum share) — это объём ресурсов, который задание должно получить в любом случае, даже если для этого придётся отнять ресурсы у других заданий. Максимальная гарантия (maximum share) — это верхняя граница ресурсов, которую задание не может превысить, даже если кластер простаивает.

¶Приоритеты и веса

Каждому заданию или пулу может быть назначен вес (weight). Задания с большим весом получают пропорционально больше ресурсов. Например, если задание A имеет вес 2, а задание B — вес 1, то задание A получит в два раза больше ресурсов, чем задание B, при прочих равных условиях.

¶Вытеснение (Preemption)

Для обеспечения справедливости в реальном времени Fair Scheduler поддерживает механизм вытеснения. Если задание не получает свою минимальную гарантию, планировщик может принудительно остановить (вытеснить) другие задания, которые занимают больше ресурсов, чем им положено. Вытеснение может быть как мягким (запрос на освобождение ресурсов), так и жёстким (принудительное завершение контейнеров). Этот механизм позволяет быстро восстанавливать справедливость, но может приводить к потере прогресса вытесненных заданий.

¶Архитектура и компоненты

¶Пул (Pool)

Пул — это логическая группа заданий, объединённых по какому-либо признаку (например, по пользователю, группе, проекту). Каждому пулу могут быть назначены свои минимальные и максимальные гарантии, веса и правила планирования. Пул может быть вложенным (иерархическим), что позволяет создавать сложные структуры управления ресурсами.

¶Очередь (Queue)

В терминологии Fair Scheduler очередь — это синоним пула. Каждое задание помещается в определённую очередь, из которой оно выбирается на выполнение. Очереди могут быть настроены на использование различных алгоритмов планирования (например, FIFO, Fair или DRF — Dominant Resource Fairness).

¶Планировщик (Scheduler)

Основной компонент Fair Scheduler — это планировщик, который принимает решения о том, какие задания и в каком объёме получат ресурсы. Планировщик работает в цикле: каждые несколько секунд он пересчитывает доли ресурсов для каждого задания, учитывая текущую загрузку кластера, минимальные гарантии, веса и политики вытеснения.

¶Конфигурация

Fair Scheduler настраивается через XML-файл (обычно fair-scheduler.xml), в котором определяются пулы, их параметры, правила вытеснения и другие настройки. Также возможно динамическое изменение конфигурации без перезапуска кластера.

¶Применение

¶Кластеры Hadoop

Основная область применения Fair Scheduler — это кластеры Hadoop, работающие под управлением YARN. Он используется в компаниях, где одновременно работают сотни или тысячи пользователей, запускающих задания MapReduce, Spark, Hive, Pig, Tez и других фреймворков. Fair Scheduler позволяет эффективно утилизировать ресурсы кластера, предотвращая «голодание» мелких заданий.

¶Другие распределённые системы

Хотя Fair Scheduler был разработан для Hadoop, его принципы справедливого распределения ресурсов могут быть применены и в других распределённых системах, где требуется управление вычислительными мощностями. Например, аналогичные алгоритмы используются в некоторых планировщиках для Apache Spark, Apache Flink и других систем потоковой обработки данных.

¶Облачные вычисления

В облачных средах (например, в Amazon EMR, Google Cloud Dataproc, Azure HDInsight) Fair Scheduler часто используется по умолчанию для распределения ресурсов между несколькими заданиями, запущенными в одном кластере. Это позволяет пользователям платить только за фактически использованные ресурсы, а не за зарезервированные.

¶Преимущества и недостатки

¶Преимущества

• Справедливость: Гарантирует, что все пользователи и задания получают равную долю ресурсов в долгосрочной перспективе.
• Гибкость: Поддерживает настройку минимальных и максимальных гарантий, весов, вытеснения и иерархических пулов.
• Устойчивость к «голоданию»: Мелкие задания не блокируются большими, что улучшает время отклика для интерактивных запросов.
• Динамическое перераспределение: Ресурсы автоматически перераспределяются между заданиями по мере их завершения или запуска новых.

¶Недостатки

• Сложность настройки: Для эффективной работы требуется тщательная настройка параметров (минимальные гарантии, веса, политики вытеснения), что может быть сложно для администраторов.
• Накладные расходы на вытеснение: Механизм вытеснения может приводить к потере прогресса вытесненных заданий и дополнительной нагрузке на кластер.
• Неоптимальность для однородных нагрузок: Если все задания имеют одинаковые требования и размеры, Fair Scheduler может работать неэффективнее, чем простой FIFO-планировщик.
• Зависимость от точности оценки: Для корректной работы планировщик должен знать точные требования заданий к ресурсам, что не всегда возможно.

¶Сравнение с другими планировщиками

¶FIFO Scheduler

FIFO Scheduler — самый простой планировщик, который выполняет задания в порядке их поступления. Он не требует настройки и хорошо работает для небольших кластеров с однородными нагрузками. Однако в многопользовательских средах FIFO приводит к «голоданию» мелких заданий.

¶Capacity Scheduler

Capacity Scheduler, разработанный Yahoo, также является популярным планировщиком для Hadoop YARN. В отличие от Fair Scheduler, он ориентирован на гарантированные доли ресурсов для отдельных очередей (организационных подразделений), а не на справедливое распределение между заданиями. Capacity Scheduler проще в настройке для фиксированных структур, но менее гибок в динамическом перераспределении.

¶Dominant Resource Fairness (DRF)

DRF — это алгоритм, который расширяет идею справедливости на многомерные ресурсы (CPU, память, сеть). Он гарантирует, что каждое задание получает равную долю своего доминирующего ресурса (того, который требуется в наибольшей пропорции). Fair Scheduler в версии для YARN поддерживает DRF как один из режимов планирования.

¶Интересные факты

• Fair Scheduler был разработан в Facebook (организация Meta признана экстремистской и запрещена в РФ) для обслуживания кластера Hadoop, который в 2009 году состоял из нескольких тысяч узлов.
• В 2010 году Facebook (организация Meta признана экстремистской и запрещена в РФ) передала код Fair Scheduler в проект Apache Hadoop, что сделало его доступным для всего сообщества.
• Fair Scheduler поддерживает динамическое создание пулов на основе имени пользователя, группы или имени приложения, что упрощает администрирование.
• В некоторых реализациях Fair Scheduler используется алгоритм «честного разделения» (fair sharing), который гарантирует, что каждое задание получает ресурсы, пропорциональные его весу, даже если некоторые задания не могут использовать свою долю.

¶Источники

• Apache Hadoop Documentation: Fair Scheduler Guide
• Zaharia, M. et al. (2010). "Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling". Proceedings of the 5th European Conference on Computer Systems (EuroSys).
• Facebook (продукт Meta, признанной экстремистской и запрещённой в РФ) Engineering Blog (2009). "Under the Hood: Scheduling MapReduce jobs more efficiently with Fair Scheduler".
• Apache Hadoop Wiki: Fair Scheduler Configuration