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

  • 6 мин

Для обеспечения отказоустойчивости в случае сбоев GraphLab предлагает использовать назначение распределенных контрольных точек и обеспечивает два механизма назначения распределенных контрольных точек: синхронный и асинхронный. Для захвата распределенной контрольной точки синхронный механизм полностью приостанавливает выполнение функций обновления на компьютерах кластера. Таким образом, механизм сбрасывает все передаваемые сообщения связи (вызванные обработчиками внутренним образом) и принимает локальную контрольную точку (моментальный снимок) всех измененных данных на каждом компьютере с момента последней захваченной контрольной точки. Захваченные локальные контрольные точки в совокупности образуют распределенную контрольную точку, которая затем сохраняется в файлах2 на уровне базового хранилища механизма (например, HDFS). В случае сбоя компьютера или обработчика эту распределенную контрольную точку можно использовать для возобновления выполнения.

Хотя назначение синхронных контрольных точек выполняется довольно просто, оно существенно снижает эффективность, так как подразумевает полную приостановку выполнения GraphLab для захвата распределенной контрольной точки. Чтобы устранить этот недостаток, асинхронный механизм определяет на каждом компьютере кластера функцию обновления назначения контрольных точек, которая выполняется для каждой вершины, собирая моментальные снимки, охватывающие период со времени последнего сохраненного снимка. На каждом компьютере функции обновления назначения контрольных точек выполняются так, как показано в алгоритме 2. Они имеют приоритет над обычными функциями обновления (используемыми пользовательскими программами GraphLab) и соответствуют модели согласованности ребер. Следовательно, если область вершины $v$ заблокирована, как того требует модель согласованности ребер, она остается заблокированной до тех пор, пока алгоритм 2 не завершит работу в вершине $v$, прежде чем перейти к другой вершине. Этот асинхронный механизм построен на стратегии назначения контрольных точек Ченди-Лампорта1 и обеспечивает согласованные распределенные контрольные точки. Наконец, как синхронные, так и асинхронные механизмы назначения контрольных точек запускаются GraphLab через фиксированные промежутки времени, которые вычисляются, как описано в статье "Приближение первого порядка к оптимальному интервалу контрольных точек" Юнга2.

На этом мы заканчиваем обсуждение отказоустойчивости в GraphLab. В этом механизме используются модели с параллелизмом графов, с общей памятью, а также асинхронные и одноранговые модели. Он поддерживает три уровня согласованности, которые балансируют плюсы и минусы параллелизма и согласованности, предоставляя пользователям возможность выбирать между полной согласованностью, согласованностью ребер и согласованностью вершин тот уровень, который соответствует требованиям их приложений. Кроме того, он обеспечивает сериализуемость (необходимую для многих алгоритмов машинного обучения и интеллектуального анализа данных (MLDM)) в отношении соответствующей модели согласованности. GraphLab также предлагает два типа асинхронных механизмов, Chromatic и Locking. Механизм Chromatic выполняет вершины частично асинхронно, а механизм Locking выполняет вершины полностью асинхронно. Механизм Chromatic использует раскраску графиков и предлагает концепцию цветовых шагов, которая аналогична концепции супершагов в модели параллельных вычислений. В сущности, GraphLab с механизмом Chromatic и моделью согласованности ребер может имитировать Pregel. Наконец, для достижения отказоустойчивости GraphLab предлагает использовать синхронные и асинхронные распределенные контрольные точки.

Алгоритм 2

Захват контрольной точки в вершине $v$

  • If $v$ контрольная точка уже установлена then

    • Quit

  • Save $D_{v}$ //сохранить каждую вершину

  • foreach$u \in N[v]$do //цикл по соседним вершинам

    • if $u$ контрольная точка не установлена then
      • Сохранить данные на ребре $D_{(u \leftrightarrow v)}$
      • Запланировать $u$ для захвата контрольной точки

  • Пометить $v$ как имеющую контрольную точку


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

Ссылки

  1. K. M. Chandy and L. Lamport (1985). Distributed Snapshots: Determining Global States of Distributed Systems ACM Trans. Comput. Syst., 3(1):63–75
  2. J. W. Young (1974). A First Order Approximation to the Optimum Checkpoint Interval Communications ACM, 17:530–531

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

1.

Какие механизмы назначения распределенных контрольных точек используются в GraphLab?

2.

В чем заключается основное различие между синхронным и асинхронным механизмами назначения контрольных точек в GraphLab?