Вытеснение

В случае, если отдельные джобы операций выполняются долго, возможна ситуация, в которой операции занимают ресурсов больше, чем положено, и это не позволяет другим операциям запускать свои джобы. В этом случае другие операции страдают (starve). Для решения описанной проблемы в планировщике реализован механизм вытеснения (preemption).

С точки зрения потребления ресурсов (usage share) и положенной доли ресурсов (fair share) каждая операция может находиться в одном из двух состояний (scheduling status):

• normal — операция получает достаточное количество ресурсов;
• below_fair_share — операция получает количество ресурсов меньше положенной ей доли (с учётом сконфигурированного tolerance).

Когда операция долгое время находится в состоянии below_fair_share, она начинает страдать, и для планирования её аллокаций может использоваться механизм вытеснения. С точки зрения страдания операция может находиться в одном из трёх состояний:

• non_starving — для планирования аллокаций операции не требуется применять вытеснение;
• starving — операция страдает, для планирования её аллокаций применяется стандартный механизм вытеснения;
• aggressively_starving — операция страдает, для планирования её аллокаций применяется механизм агрессивного вытеснения.

В любой момент времени аллокации каждой операции делятся на три группы:

• non_preemptible — невытесняемые;
• aggressively_preemptible — вытесняемые только в рамках механизма агрессивного вытеснения;
• preemptible — безусловно вытесняемые.

Данное разделение происходит следующим образом: все аллокации операции упорядочиваются по времени старта последнего джоба; в рамках этого порядка сначала идут невытесняемые аллокации, затем агрессивно вытесняемые, затем безусловно вытесняемые. Разделение на группы происходит с помощью порогов aggressive_preemption_satisfaction_threshold и preemption_satisfaction_threshold, которые задают границу отношения usage share к fair share операции, вычисляемую для префикса рассматриваемых аллокаций.

Устройство механизма вытеснения

Механизм вытеснения является частью планирования аллокаций, то есть решение о вытеснении аллокации принимается при обработке хартбита от ноды, на которой находится данная аллокация.

Вытеснение может происходить по одной из трёх причин:

1. Для запуска аллокации страдающей операции.
2. В ситуации, когда ресурсы, занимаемые аллокациями на ноде, превышают доступные ресурсы ноды.
3. В ситуации, когда нарушен resource_limits операции или одного из родительских пулов операции.

На практике подавляющее большинство вытеснений происходит по первой причине.

Алгоритмически механизм вытеснения устроен следующим образом. Планирование новых аллокаций в рамках обработки хартбита разделено на стадии: стадия обычного (regular) планирования, стадия планирования с вытеснением, стадия планирования с агрессивным вытеснением (также есть ещё ряд других стадий, которые здесь не рассматриваются). Каждая стадия характеризуется подмножеством операций, участвующих в планировании новых аллокаций, и ресурсами, доступными для их запуска:

• На стадии обычного планирования рассматриваются все операции, а доступные ресурсы — это свободные ресурсы на ноде.
• На стадии планирования с вытеснением рассматриваются только страдающие и агрессивно страдающие операции, а доступные ресурсы — это сумма свободных ресурсов на ноде и ресурсов вытесняемых аллокаций на данной ноде.
• На стадии планирования с агрессивным вытеснением рассматриваются только агрессивно страдающие операции, а доступные ресурсы — это сумма свободных ресурсов на ноде и ресурсов вытесняемых и агрессивно вытесняемых аллокаций на данной ноде.

Важно отметить, что для планирования с вытеснением существует конфигурируемый backoff, то есть такая стадия может запускаться не на каждый хартбит от ноды. Также на стадии планирования с вытеснением происходит планирование не более одной аллокации.

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

Агрессивное страдание и вытеснение

Данный механизм необходим для борьбы с фрагментацией и для планирования больших аллокаций.

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

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

Следует отметить, что механизм агрессивного вытеснения имеет и очевидные недостатки: он может приводить к вытеснению аллокаций, которые запущены в рамках положенной доли ресурсов (fair share), что может быть неприемлемо для production-операций, имеющих SLA на время исполнения.

Настройки вытеснения

Основные настройки вытеснения задаются в конфигурации дерева пулов; некоторые параметры могут быть переопределены в опциях пула.

• preemptive_scheduling_backoff — ограничение на частоту планирования аллокаций с вытеснением на одной ноде;
• fair_share_starvation_timeout — после заданного периода времени, если операция недополучает положенные ресурсы, она становится страдающей (starving), и для планирования её аллокаций используется механизм вытеснения;
• fair_share_starvation_tolerance — пороговое значение, определяющее, что операция считается недополучающей ресурсы. Операция считается недополучающей ресурсы (статус below_fair_share), если usage_share < fair_share * tolerance по доминантному ресурсу;
  
• preemption_satisfaction_threshold — пороговое значение, разделяющее аллокации на невытесняемые (а также агрессивно вытесняемые) и вытесняемые. Аллокации, у которых кумулятивный usage_share превосходит fair_share * threshold, считаются вытесняемыми, а все остальные — невытесняемыми (или агрессивно вытесняемыми);
• non_preemptible_resource_usage_threshold — операция не будет участвовать в вытеснении, если её потребление ресурсов меньше данного значения;
• allocation_preemption_timeout — таймаут на вытеснение аллокации. Если джоб в заданной аллокации поддерживает interruption, то, прежде чем джоб будет прерван, ему будет дано указанное время, чтобы успешно завершиться;
• aggressive_preemption_satisfaction_threshold — пороговое значение для разделения аллокаций на невытесняемые и агрессивно вытесняемые (а также просто вытесняемые). Аллокации, у которых кумулятивный usage_share превосходит fair_share * threshold, считаются агрессивно вытесняемыми и просто вытесняемыми. Значение данного порога не должно превышать preemption_satisfaction_threshold.

• enable_aggressive_starvation (false) — включает агрессивное вытеснение для операций в данном пуле и всех его потомках;
• allow_aggressive_preemption (true) — разрешает агрессивное вытеснение аллокаций у всех операций данного пула и его потомков;