Размещено на http://www.allbest.ru/

Федеральное государственное автономное образовательное учреждение высшего образования

«Национальный исследовательский университет»

«Высшая школа экономики»

Выпускная квалификационная работа

«Информатика и вычислительная техника»

Студент:

Тарасова А.В.

Москва, 2018



Аннотация

Цель работы - разработка системы восстановления задач после сбоев на многопроцессорных вычислительных машинах с интерконнектом Ангара.

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

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

ВКР включает следующие разделы: введение, три главы, заключение, список использованных источников и четыре приложения.

В первой главе рассмотрены основные и альтернативные методы обеспечения отказоустойчивости, проведен их сравнительный анализ. Во второй главе рассмотрены программные реализации трёх выбранных методов, протестирована их эффективность. В третьей главе описана разработка системы тестирования и системы восстановления задач после сбоев на основе самого эффективного инструмента, среди протестированных в главе 2. Заключение содержит основные выводы и рекомендации по дальнейшему развитию работы.

Работа состоит из 66 страниц, включает 6 иллюстраций, 3 таблицы и использует 10 источников.

The goal of the work is the development of the system for restoring tasks after failures on multiprocessor computers with the interconnect of the Angara.

In the course of the work the main basic and alternative methods of fault tolerance are considered, their comparative analysis is carried out. Among the methods considered, three software implementations were selected and tested. Based on the most efficient of them (judging by the time to recover a task), a disaster recovery system was adapted.

The outcomes of the work can be used for development of a system for the tasks recovery and for further research of the ways of increasing the efficiency of computations on multiprocessor computers with the Angara interconnect.

This work includes the following sections: introduction, three chapters, conclusion, list of sources used and four annexes.

In the first chapter, the main and alternative methods for ensuring fault tolerance were examined, their comparative analysis was conducted. In the second chapter, the program implementations of the three selected methods were examined, their efficiency was tested. In the third chapter the testing system and disaster recovery system development are described. The conclusion contains the work outcomes and recommendations for the further development.

The work consists of 66 pages and includes 6 illustrations, 3 tables and uses 10 sources.



Оглавление

Введение

Глава 1. Анализ литературных источников

1.1 Основные методы обеспечения отказоустойчивости

1.2 Альтернативные методы обеспечения отказоустойчивости

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

Глава 2. Исследование методов и построение решения

2.1 Обзор и установка инструментов

2.2 Разработка тестов

2.3 Результаты выполнения тестов и сравнение программных реализаций методов

Глава 3. Описание практической части

3.1 Реализация системы тестирования

3.2 Реализация системы восстановления задач после сбоев

Заключение

Список использованных источников

Приложение



Введение

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

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

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

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

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

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

В число областей применения данной сети входят:

- Высокопроизводительные вычисления (HPC) - на сегодняшний день достаточно важный фактор научно-технического прогресса, который обеспечивает снижение затрат финансов и времени в решении широкого спектра задач;

- Big Data (большие данные). С каждым годом объемы данных растут в геометрической прогрессии. Big Data дает возможность решать комплекс инновационных задач в сферах торговли, медицины, науки;

- Центр обработки данных (ЦОД) обычно создаётся в целях обеспечения бесперебойной автоматизированной работы бизнес-процессов. Центры обработки данных создаются в первую очередь для увеличения производительности компаний, активно использующих в своей деятельности информационные технологии, а также для повышения качества предоставляемых услуг.

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

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

Для достижения этой цели необходимо решение следующих задач:

- Изучение основных понятий отказоустойчивости;

- Изучение методов анализа отказоустойчивых систем;

- Рассмотрение существующих систем восстановления задач после сбоев, описание выявленных проблем в реализации данных систем;

- Описание задач, необходимых для реализации системы восстановления на многопроцессорных вычислительных кластерах с интерконнектом Ангара;

- Реализация выбранной системы восстановления задач после сбоев;

- Тестирование и оптимизация работы программы с интерконнектом Ангара.

Объект исследования - многопроцессорные вычислительные кластеры с интерконнектом Ангара.

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

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

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



Глава 1. Анализ литературных источников

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

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

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

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

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

1.1 Основные методы обеспечения отказоустойчивости

Контрольные точки восстановления процессов на примере библиотеки Berkeley Lab Checkpoint/Restart

В качестве решения для восстановления процессов с использованием контрольных точек рассмотрена библиотека BLCR (Berkeley Lab Checkpoint/Restart) [1], реализованная на уровне ядра операционной системы, которая позволяет сохранять процессы в файл, а в случае отказа восстанавливать процессы из этого файла.

Решение BLCR реализовано при помощи загружаемого модуля ядра Linux версий 2.4.x и 2.6.x для архитектур x86 и x86-64, а также небольшой библиотеки с открытым исходным кодом на языке C.

Возможность проверки и восстановления приложений, другими словами, сохранение всего состояния задания на диск, а затем его восстановление, предоставляет множество полезных функций в кластерной среде:

- График планирования. Возможность создания контрольной точки и перезапуск набора параллельных процессов, которые являются частью одного приложения (график планирования), позволяет использовать как более гибкую систему планирования, так и более высокую общую загрузку системы. Системные администраторы могут запускать различные типы заданий в разное время суток (например, большие, длинные задания запускать в ночное время, а короткие - днём, в интерактивном режиме), просто путем проверки любых заданий, которые все еще выполняются при изменении политики планирования, и дальнейшей их перезагрузкой после того, как политика изменится. Подмножество узлов или даже весь кластер может быть использован для обслуживания системы, не мешая выполнению задания пользователя. Без контрольной точки эти типы действий по планированию должны быть реализованы либо путем простого уничтожения пользовательских приложений, либо путем «истощения очереди», когда новые задания не принимаются определенное время, и система ждет завершения работы пользователей (в течение которых, по определению, система работает не в полной мере). Контрольная точка также позволяет выполнять чрезвычайно большие задания, которые могут долгое время потреблять ресурсы всей системы. Это позволяет избежать блокировки других пользователей, что было бы неприемлемо при длительных периодах времени. Наконец, контрольная точка может обеспечить более высокую общую загрузку системы, позволяя запускать любую конфигурацию доступных процессов, наиболее полно насыщая загрузку процессоров (или других ресурсов), предоставляемых кластером.

- Процесс миграции. Хорошо спроектированная контрольная точка может разрешить перезапуск процессов контрольной точки не только на их исходном узле, но и на других узлах системы (или, возможно, даже на узлах другой системы, которые являются частью вычислительной сети или другой распределенной системы). Такая миграция может позволить продолжить работу, если обнаружен неизбежный сбой одного из его узлов (например, отказ процессора или локального диска). Некоторые частичные сбои также могут быть обработаны. Например, большинство кластеров Linux, которые используют пользовательские высокопроизводительные сети, также предоставляют стандартный интерфейс Ethernet для административного трафика. Если высокопроизводительный сетевой интерфейс узла становится непригодным для использования, все равно можно перенести его процессы на полностью исполняемый узел через интерфейс Ethernet, что позволяет выполнять задание, которое в противном случае было бы прекращено.

- Периодическое резервное копирование. Наконец, контрольная точка может обеспечить повышенный уровень надежности в случае сбоев узлов и / или недетерминированных сбоев приложений (таких, как редко возникающие ошибки синхронизации). Если будут приняты прерывистые контрольные точки, задание можно перезапустить с самой крайней контрольной точки и успешно продолжать, предполагая, что его действия идемпотентны. Некоторая специальная обработка файлов может использоваться системой контрольных точек для «отката» изменений в открытые файлы приложения, что делает многие другие неидентифицированные приложения идемпотентными. Это особенно актуально для научных приложений, которые, как правило, записывают свои выходные файлы в последовательном журнальном режиме: в таких случаях достаточно простого сокращения файлов до их длины на время контрольной точки для отката.

- Приоритеты реализации. BLCR оценивает названные преимущества контрольной точки в порядке убывания важности. График планирования и процесс миграции являются одновременно первоочередными и представляют собой аналогичный уровень сложности. Процесс миграции немного сложнее в том, что эффективная реализация (которая перемещает задание непосредственно по сетевому соединению, а не через промежуточный файл) требует, чтобы доступ к файлу контрольной точки был смежным. Для миграции между неоднородными узлами также требуется поддержка копирования любых разделяемых библиотек и файлов, которые приложение может использовать как часть контрольной точки.

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

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

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

Метод согласованных контрольных точек

Распределенные протоколы контрольных точек используют контрольные точки процессов и очередь сообщений для реализации процедур отката приложений, использующих параллельные вычисления. Цель этого протокола - создание согласованного распределенного моментального снимка распределенной системы. Распределенный снимок представляет собой набор контрольных точек процесса (по одному на процесс) и набор сообщений об операциях (упорядоченный список сообщений для всех связей точка-точка). Каналы связи подразумевают защиту от потерь и упорядоченность сообщений. Сообщения могут посылаться и приниматься до или после момента снятия снимка процесса. Сообщение от процесса А к процессу Б, которое было отправлено после снятия снимка процесса А, но полученное до того, как был снят снимок процесса Б, считается несогласующимся. Для того, чтобы снимок приложения считать согласованным, он не должен содержать несогласующихся сообщений. Используя такой снимок, распределенное приложение будет восстановлено корректно и сможет продолжить вычисления.

Одним из инструментов обеспечения отказоустойчивости при помощи согласованных или координированных контрольных точек является предкомпилятор «Cornell Checkpoint preCompiler».

В работе Корнелльского университета «A System for Automating Application-level Checkpointing of MPI Programs» [2] подчеркивается, что создание контрольной точки на системном уровне позволяет сохранить состояние всей машины и обеспечить стабильность среды, но обычно это требует слишком много накладных расходов.

На практике программисты на этапе разработки приложений пытаются увеличить стабильность работы приложения на уровне самой программы путем написания кода для сохранения значений ключевых программных переменных в критических точках и восстановления всего состояния программы из этих значений. Однако это достаточно сложно реализовать в MPI программах.

В работе представлен протокол координации распределенных контрольных точек, который обрабатывает двухточечные и коллективные конструкции MPI, имея дело с уникальными задачами контрольной точки на уровне приложений. В данном исследовании протоколы реализованы как часть тонкого программного слоя, который находится между прикладной программой и библиотекой MPI, поэтому не требует каких-либо изменений в библиотеке MPI. Этот тонкий слой используется предкомпилятором Cornell Checkpoint precompiler, который автоматически преобразует приложение MPI в эквивалентную отказоустойчивую версию. В работе также представлены экспериментальные результаты, которые показывают, что накладные расходы, введенные протоколами, достаточно малы.

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

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

Система CoCheck

Одной из таких систем является CoCheck, которая обеспечивает отказоустойчивость для приложений MPI. CoCheck предоставляет только функциональные возможности для координации распределенных контрольных точек, полагаясь на систему Condor, чтобы получать контрольные точки на каждом уровне процесса на системном уровне. В отличие от подхода, рассмотренного в основной работе Корнелльского университета, CoCheck интегрирован со своей собственной реализацией MPI и предполагает, что коллективные коммуникации реализованы как сообщения «точка-точка». В этом отношении, способность Cornell Checkpoint preCompiler взаимодействовать с любой реализацией MPI является существенным преимуществом.

Система Manetho

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

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

Кроме того, поскольку система требует, чтобы процесс выполнял создание контрольной точки, когда эти журналы становятся слишком большими, неясно, как использовать этот подход в контексте контрольной точки на уровне приложения. Обратим внимание, что рассматриваемый в работе протокол, как и протокол Chandy-Lamport, также записывает данные сообщений, запись происходит только во время контрольной проверки. Другое отличие состоит в том, что Manetho не был разработан для работы с любым стандартным API-интерфейсом передачи сообщений, и поэтому ему не нужно иметь дело со сложными конструкциями, такими как неблокирующая и коллективная связь, присутствующими в MPI.

Система Egida

Система Egida является другой отказоустойчивой системой для MPI. Как и CoCheck, она обеспечивает создание контрольной точки на системном уровне и реализована непосредственно в слое MPI. Как и Manetho, она основана на ведении журнала сообщений и использует контрольную точку для сброса журналов, когда они становятся слишком большими.

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

CPPC Framework

CPPC ("A compiler-assisted tool for portable checkpointing") является инструментом, очень похожим по принципу работы на “Cornell Checkpoint preCompiler”. Для его работы разработчику также требуется самостоятельно расставить отметки в коде своей программы в критических местах, где может произойти сбой. Эти отметки будут обработаны компилятором и заменены специальным кодом, который будет сохранять состояние процесса в данной точке для последующего восстановления в случае сбоя. Среди преимуществ инструмента его разработчики отмечают [9]:

- Независимость от операционной системы

- Поддержка параллельных приложений независимо от протокола обмена сообщениями

- Небольшой размер файлов контрольных точек

- Портативное восстановление данных

Так как CPPC обладает данными особенностями, считающимися ключевыми для отказоустойчивости гетерогенных крупномасштабных систем, то он подходит и для вычислительных систем на базе интерконнекта Ангара. Для пользователя этот фреймворк представляет собой библиотеку времени выполнения, содержащую в себе подпрограммы управления контрольными точками и компилятор, позволяющий автоматизировать работу с библиотекой.

Метод несогласованных контрольных точек

Следующим изученным литературным источником стала работа «A survey of Rollback-Recovery protocols in message-passing systems» [3], или «Обзор протоколов восстановления в системах передачи сообщений».

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

Проблема восстановления в системах передачи сообщений в настоящее время подвергается обширному исследованию. В данной работе рассматриваются методы восстановления, которые не требуют специальных конструкций языка, и которые подвергаются классификации в две основных категории: нескоординированные и скоординированные методы установки контрольных точек. Категория метода определяется в зависимости от того, когда и как эти контрольные точки были созданы. Восстановление, основанное на контрольной точке, полагается только на состояние системы, отмеченное этой точкой.

Резервное восстановление на основе журнала использует контрольную точку и протоколирование сообщений. В протоколах контрольных точек каждый процесс периодически сохраняет свое состояние на этапе стабильной работы. Протокол должен содержать достаточную информацию для перезапуска процесса. Журналы позволяют протоколу восстановления возвращать состояния, которые не подлежат контролю.

По выводам из данной работы, несогласованная контрольная точка обычно имеет меньшие ограничения и издержки в сравнении согласованной контрольной точкой. Но поскольку она страдает от потенциального эффекта «домино», нескоординированную контрольную точку стоит сочетать с другими методами, чтобы увеличить практическую пользу от ее применения. Для приложений, включающих несколько процессов, выполняемых на скоординированных этапах, скоординированная контрольная точка часто является естественным выбором для упрощения как безотказной работы, так и восстановления операций. Она также может быть объединена с протоколами восстановления на основе журнала для упрощения задачи сбора мусора.

Следующим изученным литературным источником является «ExaScale Computing Study: Technology Challenges in Achieving Exascale Systems» [4], или «Экзафлопное компьютерное обучение: технологические проблемы в достижении экзафлопных систем».

Exascale computing -- термин, обозначающий гипотетические суперкомпьютеры с производительностью порядка одного экзафлопса (exaFLOPS).

В данной работе следует обратить особое внимание на одну из глав: System Resiliency (Системная отказоустойчивость).

Хотя частота отказов какого-либо конкретного компонента может быть относительно небольшой, отказоустойчивость вычислительной системы сильно зависит от количества компонентов, которые она содержит. Это в том числе справедливо для систем класса центров обработки данных (ЦОД) и является предметом изучения данного раздела этого источника.

Как показано на рис. 1, число компонентов в последних суперкомпьютерных системах растет экспоненциально, совокупный годовой темп роста памяти (в 1,28 раза в год) немного превышает темп роста количества сокетов (в 1,22 раза в год).

Рис.1. Рост числа компонентов в суперкомпьютерах

Предполагая продолжение прежнего роста системы, можно спрогнозировать, что система будет состоять из более чем 100 000 процессорных чипов («сокетов») и более 10 миллионов чипов DRAM. В то время как экзафлопная система может потребовать ещё более стремительного масштабирования системы, даже прошлые тенденции масштабирования будут представлять значительные проблемы с отказоустойчивостью.

Метод многоуровневых контрольных точек

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

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

Статья «Optimization of multi-level checkpoint model for large scale HPC applications» [5], или «Оптимизация многоуровневой контрольной модели для широкомасштабных приложений высокопроизводительных вычислений» является одной из самых важных статей данного направления, и описывает метод многоуровневого сохранения контрольных точек.

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

- Как оптимизировать выбор уровней контрольных точек на основе распределений отказов, наблюдаемых в системе;

- Как вычислить оптимальные интервалы контрольных точек для каждого из этих уровней.

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

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

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

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

- Итеративное оптимальное решение превосходит формулу Юнга на 1,92-8%. Прирост производительности отличается от накладных расходов контрольной точки и длины приложения;

- Оптимизация выбора уровней может дополнительно повысить производительность на 10-20% в зависимости от сценария и до 50% на основе 8-уровневой контрольной точки;

- Используя эксперимент, приведенный в данной статье, в кластерной среде с 512 ядрами и 1024 ядрами, можно сделать вывод, что данное решение превосходит другие на 5-10% в целом, что наглядно подтверждает обоснованность решения на практике.

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

Метод репликации

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

1.2 Альтернативные методы обеспечения отказоустойчивости

Методы с использованием модели RMA

Следующий источник, рассмотренный в рамках изучения существующих технических решений, это «Fault Tolerance for Remote Memory Access Programming Models» [6], и в русском эквиваленте: «Отказоустойчивость для моделей программирования удаленного доступа к памяти».

Данная статья посвящена обзору особенного способа обеспечения отказоустойчивости, который основан на удалённом доступе к памяти процессов (RMA).

Удаленный доступ к памяти (RMA) - это новый механизм программирования высокопроизводительных компьютеров и центров обработки данных.

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

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

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

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

Модели RMA-программирования становятся все более популярными и важными, поскольку они позволяют наилучшим образом использовать аппаратные функции, такие, как переключение ОС или передача данных с нулевой копией.

Тем не менее, небольшая работа касается также отказоустойчивости для RMA. В данной работе исследуется полная формальная модель отказоустойчивости для RMA и иллюстрируется пример её использования для проектирования и определения протоколов устойчивости, работающих на плоских и иерархических машинах. Этот протокол будет играть важную роль в создании отказоустойчивого программного обеспечения RMA и его плюсом является возможность легкого расширения для создания, например, стабильного хранилища.

В данном исследовании не используются традиционные менее масштабируемые механизмы, которые часто опираются на дорогостоящие потоки ввода-вывода. Реализация целостного протокола добавляет незначительные накладные расходы для среды выполнения приложений, например, 1-5% для контрольной точки внутри памяти и 8% для полностью прозрачного ведения журнала удаленных доступа к памяти. Вероятностное исследование показывает, что протокол обеспечивает высокую устойчивость.

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

Методы обеспечения отказоустойчивости на уровне конкретных приложений

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

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

опорной платформы. Как можно ожидать, эффективность таких подходов может быть на порядки выше, чем эффективность общих методов; их программирование, однако, становится сложной задачей для конечного пользователя.

Об одном их таких подходов рассказано в статье под названием «Fault Tolerant MPI. Implementation, user's stories, use cases, performance» [7], или в русском варианте «Отказоустойчивость интерфейса передачи сообщений. Реализация, истории пользователей, варианты использования, производительность».

Понятие ULFM, используемое в данной работе по своей сути является расширением интерфейса MPI для обеспечения включения MPI-программы для восстановления коммуникационных возможностей MPI, недоступных при сбоях. Аббревиатура ULFM обозначает понятие User Level Failure Mitigation, в переводе на русский язык обозначающее уменьшение последствий на уровне пользователя.

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

Контракт ULFM разработан рабочей группой MPI Forum Fault Tolerance для поддержки восстановления работы программ MPI после сбоев, повлиявших на выполнение. Ключевым принципом является то, что ни один вызов MPI (точка-точка, collective, RMA, IO, ...) не может бесконечно блокироваться из-за сбоя, он должен либо завершиться успешно, либо вызвать ошибку MPI. Кроме этого, дизайн ориентирован на потребности пользователей и гибкость, API должен позволить создавать различные отказоустойчивые внешние библиотеки.

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

Пример использования простого шаблона связи «мастер-работник», при котором приложение продолжает работу, игнорируя ошибки (рис. 2):



Рис.2. Простой шаблон связи

По выводам данной работы, минимальный набор функций для обеспечения отказоустойчивости следующий:

- Уведомление о сбое;

- Распространение ошибок;

- Восстановление ошибок.

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

По данной работе можно сделать следующие выводы: при реализации отказоустойчивости на уровне пользователя, в контрольную точку входит только то, что явно указано прикладным программистом. При лучшем возможном варианте, только данные, необходимые для восстановления утерянной в результате сбоя информации. Так же на уровне пользователя контролируется частота и момент создания контрольных точек при выполнении программы. То есть накладные расходы могут быть значительно уменьшены, но при этом, потребуется дополнительная работа программиста для реализации отказоустойчивости в приложении. Использование методов организации отказоустойчивости вычислений на системном уровне представляется трудно реализуемым для систем экзафлопсного уровня, поэтому значительное внимание специалистов в этой области уделяется именно методам уровня пользователя.

И последняя работа, рассматриваемая в данном пункте: «Resilient applications using MPI-level constructs» [8], или «Устойчивые приложения с использованием конструкций уровня MPI». Первым, что было рассмотрено в данной работе являются факторы отказоустойчивости в интерфейсах передачи сообщений на сегодняшний день:

- Общее отрицание;

- «После обнаружения ошибки состояние MPI не определено. Реализация MPI может позволить MPI продолжать работу после ошибки, но такой вариант не требуется».

- Две формы управления;

- Коды возврата: все функции MPI возвращают либо MPI_SUCCESS, либо конкретный код ошибки, связанный с обнаруженным классом ошибок (например, MPI_ERR_ARG);

- Обработчики ошибок: обратный вызов автоматически инициируется реализацией MPI перед возвратом из функций MPI.

Данная работа является продолжением предыдущей рассматриваемой работы. Как уже известно из выводов предыдущей работы, минимальный набор функций для обеспечения отказоустойчивости следующий:

- Уведомление о сбое;

- Распространение ошибок;

- Восстановление ошибок.

Теперь перейдем к более подробному объяснению каждого из этих пунктов.

Уведомление о сбое. MPI означает масштабируемые параллельные приложения, было бы необоснованным ожидать полной связи между всеми элементами. Обнаружение отказа и уведомление об этом имеют место только между соседними процессами: только процессы, связанные путем сообщений с неудавшимися процессами, могут обнаружить сбой, но по крайней мере один сосед должен быть проинформирован об отказе.

Распространение ошибок. Подход ULFM предлагает гибкость, позволяющую библиотеке / приложению разрабатывать область отказа, а также ограничивать область отказа только нуждающимися участниками.

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

Стандартом гарантируется, что сообщение о сбое будет распространяться. Некоторые процессы сами обнаруживают отказ (если алгоритм барьера создает связь между ними и мертвым процессом). Другие будут проинформированы либо во время выполнения, либо путем отзыва внутреннего коммуникатора, используемого для коллективов.

Желая предоставить пользователю гибкий интерфейс, авторы ULFM ушли от выбора конкретной техники отказоустойчивости или обязательств восстанавливать приложение целиком после отказа. «Этот интерфейс должен информировать приложение о специальных условиях мешающих передаче сообщений, и предоставлять конструкции определения, которые позволят приложению восстановить MPI-объекты и способность передавать сообщения».

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

Использование спецификации ULFM вызвано естественным стремлением сохранить будущую совместимость с разрабатываемым стандартом MPI 3.1. В данной библиотеке каждому MPI-процессу поставлен в соответствие атрибут, значение которого отражает состояние этого процесса: отказал он или нет. Также в ней реализованы модификации MPI функций обмена. Функции обмена данной библиотеки возвращают исключения согласно спецификации расширения ULFM, непредусмотренные стандартом MPI 3.0 и позволяющие моделировать отказ в нормально функционирующей распределенной вычислительной системе.

Для тестирования и определения эффективности разрабатываемых техник отказоустойчивости необходимо создание соответствующих программных средств. В данной работе представлена библиотека функций моделирования отказов в нормально функционирующих системах, основанная на существующей реализации стандарта MPI 3.0. Она позволяет тестировать различные алгоритмы восстановления вычислений, в том числе, с использованием локальных устройств хранения.

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

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

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

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

Сравнение методов

Для выбора подходящих методов в рамках данной работы необходимо сравнить методы между собой, учитывая их достоинства и недостатки, а также ограничения. Эти свойства перечислены в табл. 1. Технические параметры системы перечислены в приложении А.

Таблица 1 Сравнительная таблица методов обеспечения отказоустойчивости

Метод	Преимущества	Недостатки	Ограничения
Berkeley Lab Checkpoint/Restart	Высокая масштабируемость	Остановка приложения на время создания контрольной точки	Версия ядра linux 2.4.x и 2.6.x для архитектур x86 и x86-64
Согласованные контрольные точки (Cornell Checkpoint preCompiler)	Автоматическая конвертация MPI-программ в отказоустойчивый вариант	Замедление ввода-вывода; Высокие издержки при создании снимков процессов; Не подходит для программ с асинхронными процессами	Подходит только для MPI-программ; Требуется расстановка меток в коде исполняемых программ
Метод	Преимущества	Недостатки	Ограничения
Несогласованные контрольные точки	Низкий расход ресурсов при создании снимков; Синхронизация процессов не требуется	Все процессы будут перезапущены при сбое лишь одного; Необходим сборщик мусора	Не подходит для приложений с частым выводом
Многоуровневые контрольные точки	Низкий расход ресурсов при полном перезапуске процессов	Не гарантируется, что будет достигнуто точное состояние программы на момент сбоя	Имеет смысл для систем с количеством ядер больше 256
Репликация	Полное отсутствие временных издержек на восстановление	Двойная стоимость всех вычислений, половина ресурсов используется неэффективно	Не подходит для больших параллельных платформ
С моделью RMA	Высокая масштабируемость; Высокая производительность по сравнению с методами, основанных на передаче сообщений между процессами	Отсутствуют готовые инструменты для быстрой реализации	Требуется оборудование с поддержкой технологии прямого удаленного доступа к памяти RDMA
Метод	Преимущества	Недостатки	Ограничения
На уровне конкретных приложений	Более эффективное использование ресурсов в сравнении с методами на уровне системы	Реализация полностью зависит от конкретной кластерной среды	Зависят от конкретной платформы

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

Необходимо учитывать требования рассмотренных методов к наличию параллельной файловой системы, так как эти требования могут накладывать дополнительные ограничения на пользовательские приложения. Требования перечислены в табл. 2.

Таблица 2 Требования методов к параллельной файловой системе

Метод	Требуется ли параллельная файловая система?	Свойства использования параллельной файловой системы
Berkeley Lab Checkpoint/Restart	Не требуется, но поддерживается	Для работы с параллельной файловой системой необходима реализация MPI-IO
Согласованные контрольные точки (Cornell Checkpoint preCompiler)	Не требуется, но поддерживается	Для работы с параллельной файловой системой необходима реализация MPI-IO
Метод	Требуется ли параллельная файловая система?	Свойства использования параллельной файловой системы
CPPC Framework	Не требуется, но поддерживается	Требуется HDF5
Несогласованные контрольные точки	Не требуется	Нет
Многоуровневые контрольные точки	Необходима	Необходима единая точка входа. Файловая система может быть монтирована на центральном узле или быть полностью распределена между серверами. Файл может быть дуплицирован на нескольких узлах. В случае сбоя часть файлов может мигрировать на другие узлы. Примеры систем: NFS, AFS, xFS
Репликация	Не требуется	Нет
С моделью RMA	Не требуется, поддерживается	Лучшая производительная при работе в режиме хранения снимков in-memory; При использовании параллельных файловых систем риск сбоев увеличивается
На уровне конкретных приложений	На усмотрение разработчиков приложения	Ограничения на выбор файловой системы отсутствуют

Из табл. 1 можно выяснить, что метод BCLR не подходит для реализации на интерконнекте Ангара как минимум по двум причинам: необходима версия ядра Linux 2.4.x или 2.4.x, а на Десмосе используется ядро версии 3.0, кроме того, в условиях многопользовательского использования кластеров перезагрузка ядра для подключения дополнительного модуля вряд ли будет одобрена владельцами.

Несмотря на то, что инструмент Cornell Checkpoint preCompiler применим только к MPI-программам и имеет недостатки, связанные с дополнительным использованием памяти, простота его использования делает его интересным для дальнейшего исследования, однако в связи с тем, что данная работа была выполнена в 2003 году, на сегодняшней день не сохранилось самой программы, поэтому её невозможно протестировать. Однако CPPC Framework, основанный на тех же принципах, но являющийся разработкой 2012 года, уже не имеет тех недостатков и ограничений, которые имел более старый инструмент. Поэтому он был выбран для тестирования и сравнениях с другими инструментами в рамках данной работы.

Метод несогласованных контрольных точек, как и метод с использованием модели RMA, не подходит по причине очень ограниченного выбора готовых инструментов и, следовательно, высокой стоимость разработки. Метод репликации отвергнут по причине схожей причине, а именно - двойной стоимости всех вычислений.

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

Кроме того, было выполнено сравнение рассмотренных методов (табл. 1), а также рассмотрены требования методов относительно необходимости использования параллельных файловых систем (табл. 2), что позволило определить наиболее подходящие методы в контексте их использования на многопроцессорных вычислительных машинах с интерконнектом Ангара. Этими методами являются: метод согласованных контрольных точек (используя CPPC Framework), метод многоуровневых контрольных точек, метод обеспечения отказоустойчивости на уровне конкретных приложений.

Учитывая особенности данных методов, далее, при помощи тестов предлагается сравнить их производительность и выяснить, какой из них является оптимальным для реализации на интерконнекте Ангара.



Глава 2. Исследование методов и построение решения

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

Обоснованием для реализации набора тестов являются следующие факторы:

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

- При проверке различных инструментов восстановления задач после сбоев требуется набор тестов, учитывающий особенности и ограничения этих инструментов.

...