Odporność na uszkodzenia

  • 6 min

W celu zapewnienia odporności na uszkodzenia GraphLab sugeruje zastosowanie rozproszonego tworzenia punktów kontrolnych i zaleca dwa mechanizmy rozproszonego tworzenia punktów kontrolnych: synchroniczny i asynchroniczny. W celu przechwycenia rozproszonego punktu kontrolnego, mechanizm synchroniczny wstrzymuje całe wykonanie funkcji aktualizacji na maszynach w klastrze. Dzięki temu mechanizm opróżnia wszystkie przesyłane komunikaty (wywołane wewnętrznie przez aparaty) i przechwytuje lokalny punkt kontrolny (migawkę) wszystkich zmienionych danych na każdej maszynie od ostatniego przechwyconego punktu kontrolnego. Przechwycone lokalne punkty kontrolne tworzą zbiorczo rozproszony punkt kontrolny, który następnie jest przechowywany w plikach2 w podstawowej warstwie magazynowania aparatu (np. HDFS). W przypadku awarii maszyny/aparatu można użyć rozproszonego punktu kontrolnego do ponownego uruchomienia wykonania.

Mimo że synchroniczne tworzenie punktów kontrolnych jest proste, powoduje poważną nieefektywność związaną z zawieszeniem całego wykonania narzędzia GraphLab w celu przechwycenia rozproszonego punktu kontrolnego. Aby wyeliminować tę wadę, mechanizm asynchroniczny określa ma każdej maszynie w klastrze funkcję aktualizacji punktów kontrolnych, która jest wykonywana w każdym wierzchołku, zbierając migawki z okresu od ostatniej zapisanej migawki. Na każdej maszynie funkcje aktualizacji punktów kontrolnych są wykonywane, jak pokazano w Algorytmie 2. Mają one wyższy priorytet niż zwykłe funkcje aktualizacji (używane przez programy użytkownika w oprogramowaniu GraphLab) i są zgodne z modelem spójności krawędziowej. W związku z tym, gdy zakres wierzchołka $v $ jest zablokowany, zgodnie z wymaganiami modelu spójności krawędzi, pozostaje w tym stanie zakończenia wykonywania algorytmu 2 w $v $ przed przejściem do kolejnego wierzchołka. Ten mechanizm asynchroniczny jest oparty na strategii tworzenia punktów kontrolnych Chandy’ego-Lamporta1 i gwarantuje spójność rozproszonych punktów kontrolnych. Wreszcie, mechanizmy synchronicznego i asynchronicznego tworzenia punktów kontrolnych są wyzwalane przez GraphLab w ustalonych odstępach czasu, obliczonych zgodnie z opracowaniem „A First Order Approximation to the Optimum Checkpoint Interval” (Przybliżenie pierwszego rzędu optymalnego interwału punktów kontrolnych) Younga2

Na odporności na uszkodzenia kończymy omówienie narzędzia GraphLab. W tym aparacie stosowane są modele grafów równoległych, pamięci współdzielonej, asynchroniczne i równorzędne. Obsługuje on trzy poziomy spójności, które poświęcają równoległość na rzecz spójności, umożliwiając użytkownikom wybór poziomu odpowiadającego potrzebom aplikacji — pełnej spójności, spójności krawędzi i spójności wierzchołków. Zwiększa to możliwość serializacji (co jest wymagane w przypadku wielu algorytmów uczenia maszynowego i wyszukiwania danych (MLDM)) w odniesieniu do odpowiedniego modelu spójności. GraphLab sugeruje również zastosowanie dwóch typów aparatów asynchronicznych — chromatycznego i blokującego. Aparat chromatyczny wykonuje wierzchołki częściowo asynchronicznie, a aparat blokujący wykonuje wierzchołki w pełni asynchronicznie. Aparat chromatyczny używa kolorowania grafów i promuje koncepcję kroków oznaczonych kolorami, która jest analogiczna do koncepcji kroku nadrzędnego w zbiorczym, równoległym modelu synchronicznym. Zasadniczo, narzędzie GraphLab z aparatem chromatycznym i modelem spójności krawędziowej może naśladować model Pregel. Na koniec w celu uzyskania odporności na uszkodzenia GraphLab sugeruje użycie synchronicznego i asynchronicznego rozproszonego tworzenia punktów kontrolnych.

Algorytm 2

Przechwytywanie punktu kontrolnego w wierzchołku $v $

  • Jeśli dla wierzchołka $v$ utworzono już punkt kontrolny, to

    • zakończ.

  • Save $D_{v}$ //zapisz każdy wierzchołek

  • foreach$u \in N[v]$do //loop over neighbors

    • jeśli dla wierzchołka $u$ nie utworzono punktu kontrolnego to
      • Zapisz dane na krawędzi $D_{(u \leftrightarrow v)}$
      • Zaplanuj przechwytywanie punktu kontrolnego dla wierzchołka $u$

  • Oznacz wierzchołek $v$ jako mający punkt kontrolny


2 Rozproszony punkt kontrolny obejmuje wszystkie lokalne punkty kontrolne przechwycone na każdej maszynie w klastrze. Każdy lokalny punkt kontrolny może być przechowywany w pliku, a wszystkie pliki odpowiadające lokalnym punktom kontrolnym można skojarzyć ze sobą (w metadanych), aby wskazać, że wszystkie należą do tego samego rozproszonego punktu kontrolnego.

Odwołania

  1. K. M. Chandy i L. Lamport (1985). Migawki rozproszone: określanie globalnych stanów systemów rozproszonych ACM Trans. Comput. Syst., 3(1):63–75
  2. J. W. Young (1974). Przybliżenie pierwszego porządku do optymalnego interwału punktów kontrolnych ACM, 17:530–531

Sprawdź swoją wiedzę

1.

Jakie mechanizmy rozproszonego tworzenia punktów kontrolnych są używane w narzędziu GraphLab?

2.

Jaka jest główna różnica między synchronicznym i asynchronicznym mechanizmem tworzenia punktów kontrolnych w narzędziu GraphLab?