Отказоустойчивость

  • 14 мин

Цель MapReduce состоит в разделении заданий на задачи для эффективного использования параллелизма задач и, следовательно, более быстрого выполнения заданий. Хотя этот подход весьма эффективен, на практике он имеет свои недостатки. Например, если всего одна задача выполняется медленно или завершается сбоем, все задание завершается гораздо медленнее. На практике задачи Hadoop MapReduce завершаются сбоем и замедляются из-за снижения производительности оборудования, неправильной настройки программного обеспечения, неоднородности и (или) расположения данных, а также по многим другим причинам. Обрабатывать неправильные и медленные задачи в облаке непросто. В частности, если объем данных, передаваемых через систему ввода-вывода, аналогичен объему, который обрабатывался Hadoop, вероятность повреждения фрагментов данных возрастает. Более того, если задачи и узлы измеряются тысячами и выше (обычно для Hadoop), вероятность сбоя увеличивается.

Hadoop MapReduce применяет два механизма для обеспечения отказоустойчивости, избыточности данных и устойчивости задач. Избыточность данных применяется на уровне хранилища. В частности, HDFS сохраняет блоки HDFS, поддерживая несколько реплик на блок (по умолчанию — три реплики) на физически отдельных компьютерах. Очевидно, что благодаря этому MapReduce может легко допускать поврежденные блоки и неисправные узлы. В случае утери блока из-за сбоя оборудования или программного обеспечения можно всегда найти и прочитать другую реплику на другом узле таким образом, что в заданиях не возникнет заминок. Система HDFS рассчитывает контрольные суммы с помощью циклической проверки избыточности (CRC-32) для всех данных, записанных в нее, и по умолчанию проверяет контрольные суммы при считывании данных из нее2. При обнаружении ошибки в блоке или отказе узла HDFS прозрачно восстанавливает коэффициент репликации 3, заданный по умолчанию.

Несмотря на то, что все блоки HDFS набора данных задания могут не содержать ошибок, задачи в задании по-прежнему могут выполняться медленно или просто завершаться сбоем. Очевидно, что задержка или сбой задачи могут привести к замедлению или сбою всего задания. Чтобы избежать таких последствий и обеспечить устойчивость, Hadoop MapReduce позволяет выполнять репликацию задач и отслеживать задачи для обнаружения и обработки неисправностей и проблем. Для обнаружения медленных или неисправных задач Hadoop MapReduce использует пакеты пульса. JobTracker (JT) запускает поток со сроком годности, который проверяет пульс каждого TaskTracker (TT) и определяет, являются задачи TT активными или нерабочими. Если этот поток не получает пакеты пульса, подтверждающие работоспособность задачи, в течение 10 минут (по умолчанию), задача считается неработающей. В противном случае задача помечается как активная.

Активные задачи могут выполняться медленно (в Hadoop это называется "отстающие") или с нормальной скоростью. Для измерения скорости JT оценивает ход выполнения задачи по шкале от 0 до 1. Показатели для map и reduce вычисляются по-разному. Для задачи map показатель хода выполнения зависит от того, какая часть входного блока HDFS уже считана. Для задачи reduce учитывается показатель хода выполнения. В Hadoop MapReduce предполагается, что каждый шаг свертки (перетасовывание, слияние и сортировка, а также свертка) занимает одну треть задачи reduce, и для каждого шага показатель рассчитывается на основе доли уже обработанных данных. Например, задача reduce на середине шага перетасовывания будет иметь показатель хода выполнения $\frac{1}{3} \times \frac{1}{2} = \frac{1}{6}$. А задача reduce на середине этапа слияния и сортировки будет иметь показатель хода выполнения $\frac{1}{3} + (\frac{1}{2} \times \frac{1}{3}) = \frac{1}{2}$. Наконец, задача reduce на середине этапа свертки будет иметь показатель хода выполнения $\frac{1}{3} + \frac{1}{3} + (\frac{1}{3} \times \frac{1}{2}) = \frac{5}{6}$.

При обнаружении слишком медленной задачи JT одновременно запускает соответствующую резервную (спекулятивную) задачу. Hadoop позволяет выполнять одну спекулятивную задачу на исходную медленную, и они состязаются друг с другом. Когда одна версия выполняется, вторая завершается. В Hadoop MapReduce такая тактика устойчивости задач называется спекулятивным выполнением и активируется по умолчанию, хотя ее можно включать или отключать независимо для задач map и reduce на уровне кластера или для каждого задания.

Hadoop MapReduce вычисляет средний показатель хода выполнения для всех задач в каждой категории задач (например, все задачи map). В рамках одной категории задача с оценкой менее 80 % от среднего значения (пороговая разность хода выполнения 20 %) помечается как отстающая. Если все исходные задачи map и reduce уже запланированы9, JT запускает эквивалентную спекулятивную задачу. Все отстающие задачи считаются одинаково медленными, а связи между ними разрываются расположением данных. Точнее, если слот map освобождается в определенном TT и обнаруживается две отстающих задачи map, то для спекулятивного выполнения будет выбрана задача, использующая блок HDFS в этом TT. Если обеим отстающим задачам требуются блоки HDFS, хранящиеся в TT, можно случайным образом выбрать одну из них. Неработающие задачи всегда получают наивысший приоритет, а спекулятивные — самый низкий. В частности, когда JT получает пакет пульса TT, включающий запрос задачи map или reduce, JT отвечает в следующем порядке:

  1. Задача, которая компенсирует неработающие или остановленные задачи.
  2. Исходная, но еще не запланированная задача.
  3. Спекулятивная задача.

Подход к устойчивости задач Hadoop MapReduce хорошо работает в однородных средах, но совсем не эффективен в разнородных по нескольким причинам1, 3:

  • Неоднородность может вызывать состязание за ресурсы в виртуализованных облаках, в которых перегрузка может быть только временной. В таких случаях JT может запустить слишком много спекулятивных задач для исходных, которые в какой-то момент будут считаться медленными, но вскоре после этого восстановят нормальную скорость. Спекулятивные задачи отнимают ресурсы у исходных, и чрезмерное спекулятивное выполнение может замедлять работу всего кластера, особенно если сеть перегружена большим количеством ненужного перетасовывания трафика.
  • Hadoop MapReduce также запускает задачи в TT, не учитывая, как их текущие нагрузки и скорости сравнимы с TT, где размещаются исходные задачи. Потенциально JT может запланировать спекулятивную задачу на медленном ТТ, и она будет выполняться еще медленнее, чем исходная задача.
  • Так как планировщик Hadoop использует расположение данных для разрыва связей между отстающими задачами map, можно выбрать неверную отстающую задачу для спекуляции. Если JT обнаруживает две отстающих задачи $S_{1}$ и $S_{2}$, и у $S_{1}$ показатель 70 % от среднего, а у $S_{2}$ — 20 %, при этом TT, где размещен входной блок $S_{1}$, становится неактивным, спекулятивная задача для $S_{1}$ буде создана раньше, чем для $S_{2}$.
  • Пороговая разница хода выполнения 20 % означает, что задача с оценкой свыше 80 % от среднего никогда не будет обрабатываться спекулятивно, несмотря на потребность или потенциальное увеличение эффективности.
  • Наконец, Hadoop MapReduce делит показатель этапа свертки поровну для трех составляющих шагов. Такой компромисс нереалистичен в типичном задании MapReduce, в котором шаг перетасовывания обычно выполняется медленнее всего, так как в нем все пары взаимодействуют по сети. В действительности вполне вероятно, что после шага перетасовывания задание MapReduce быстро завершит шаг слияния и сортировки и шаг свертки. Поэтому вскоре после того, как первые несколько задач reduce завершат перетасовывание, их показатель хода выполнения поднимется с $\frac{1}{3}$ до $1$. Это значительно увеличит общий средний показатель и может снизить точность спекулятивного выполнения. На самом деле, как только будет выполнено 30 % задачи reduce, средний показатель будет $0,3 \times 1 + 0,7 \times \frac{1}{3} = 53%$. Поэтому все задачи reduce, которые все еще находятся на шаге перетасовывания, будут на 20 % отставать от среднего показателя. В результате для произвольного набора ложных отстающих задач будет запущено спекулятивное выполнение, которое быстро заполнит слоты reduce и может перегрузить облачную сеть ненужным трафиком.

Очевидно, что стандартный подход со спекулятивным выполнением в Hadoop MapReduce имеет серьезные недостатки. Поэтому Facebook отключает спекулятивное выполнение для задач reduce1. Yahoo! также отключает спекулятивное выполнение для всех задач, но только для определенных заданий1. Чтобы устранить проблему, Захария и соавторы1 предлагают жадную стратегию, именуемую "самое больше приблизительное время до завершения" (longest approximate time to end, или LATE), которая подразумевает спекулятивное выполнение только для тех задач, чье завершение ожидается позднее всего. Стратегия LATE позволяет спекулятивным задачам оптимальным образом обходить исходные, и это должно сократить общее время выполнения задания. Однако проблема заключается в выявлении подходящих задач. Для этого LATE предлагает вычислять скорость выполнения каждой задачи как $\frac{score}{T}$, где $T$ — это время, которое задача уже выполняется, а затем предсказать время до завершения задачи как $\frac{(1 - ход выполнения\ показатель)}{ход выполнения\ скорость}$. Кроме того, LATE рекомендует планировать спекулятивные задачи только на быстрых TT (выше определенного порогового значения). Чтобы учитывать тот факт, что спекулятивное выполнение потребляет ресурсы, LATE указывает ограничение на количество спекулятивных задач, которые можно запустить одновременно. Наконец, LATE не учитывает расположение данных при планировании спекулятивных задач map, предполагая, что большинство исходных задач map по-прежнему выполняются с локальными входными блоками HDFS и завершаются успешно. Результаты экспериментов показывают, что LATE может улучшить время отклика Hadoop вдвое в разнородных облачных средах.

9 Каждая исходная задача должна выполняться, по крайней мере, 1 минуту (по умолчанию), прежде чем будет вычисляться показатель хода ее выполнения. Затем JT определяет, следует ли планировать соответствующую спекулятивную задачу.

Ссылки

  1. M. Zaharia, A. Konwinski, A. Joseph, R. Katz, and I. Stoica (2008). Improving MapReduce Performance in Heterogeneous Environments OSDI
  2. T. White (2011). Hadoop: The Definitive Guide 2nd Edition O'Reilly
  3. Z. Guo and G. Fox (2012). Improving MapReduce Performance in Heterogeneous Network Environments and Resource Utilization In Proceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing

Проверьте свои знания

1.

Как обрабатывается избыточность данных в Hadoop MapReduce?

2.

Как выполняется репликация задач в Hadoop MapReduce?

3.

Ниже приведен список некоторых предположений, что Hadoop неявно делает в спекулятивном выполнении:

  • А. Планирование спекулятивной задачи с помощью TT, предоставляющего бездействующий слот, не влечет за собой расходы.
  • B. TT выполняет задачи с приблизительно одинаковой скоростью.
  • C. Задачи в задании выполняются с постоянной скоростью.
  • D. В задаче reduce шаги перетасовывания, слияния и сортировки, а также свертки занимают одинаковое время (т. е. каждый этап занимает треть от общего времени выполнения задачи reduce).
  • Д. Задача с медленным прогрессом, вероятно, является отстающей, так как задачи обычно завершаются примерно в одно и то же время.
Какое из предположений с наибольшей вероятностью может навредить разнородным облакам, но не однородным?

4.

Ниже приведены три предположения, что Hadoop неявно делает в спекулятивном выполнении:

  • А. TaskTracker выполняют задачи с приблизительно одинаковой скоростью.
  • B. В задаче reduce шаги перетасовывания, слияния и сортировки, а также свертки занимают одинаковое время (т. е. каждый этап занимает треть от общего времени выполнения задачи reduce).
  • C. Задача с медленным прогрессом, вероятно, является отстающей, так как задачи обычно завершаются примерно в одно и то же время.
Представим кластер Hadoop C с очень ограниченной пропускной способностью сети и задание Hadoop J с очень высокой скоростью перетасовывания. Какое из приведенных выше допущений, скорее всего, приведет к нарушению работы J в C?