[논문 리뷰] Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud

“Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud” 논문을 개인 공부 및 리뷰를 위해 쓴 글입니다.

논문 출처 pdf : GraphLab paper

1. Introduction

• 머신 러닝 및 데이터 마이닝 (MLDM, Machine Learning and Data Mining) 문제의 규모가 증가하면서, 대형 클러스터에서 MLDM 알고리즘을 효율적으로 병렬로 실행할 수 있는 시스템에 대한 필요성이 높아지고 있다.
• 하지만 클라우드를 완전히 활용하는 데 필요한 분산 MLDM 알고리즘을 설계, 구현 및 디버깅하는 것은 MLDM 개발자가 경쟁 상태(race condition), 데드락(deadlock), 분산 상태 및 통신 프로토콜을 해결하는 동시에 수학적으로 복잡한 모델과 알고리즘을 개발해야 하는 이슈가 있다.
• 병렬/분산 시스템 설계의 복잡성을 숨기면서 많은 MLDM 애플리케이션에서 발견되는 비동기(asynchronous), 동적(dynamic), 그래프 병렬 계산을 특별히 대상으로 하는 고급 분산 추상화(abstraction)가 필요하다.
  • 추상화(abstraction) : 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것을 말한다. ¹
• GraphLab 추상화는 공유 메모리 설정에서 위 사항을 직접 대상으로 한다.

2. MLDM Algorithm properties

• Table 1은 대규모 병렬 프레임워크의 요약된 표이다.

Graph Structured Computation

• MLDM의 최근 많은 발전은 데이터 간의 의존성(dependency)을 모델링하는 데 초점을 맞추고 있다.
• 데이터 의존성을 모델링함으로써 노이즈가 많은 데이터에서 더 많은 시그널을 추출할 수 있다.
  • 시그널(signal) : 프로세스끼리 서로 통신할 때 사용한다. ²
• 맵리듀스(MapReduce)는 일반적으로 MLDM 알고리즘에 필요한 의존 계산에 적합하지 않다.

• 따라서, 계산 의존성을 자연스럽게 표현하는 Pregel 및 GraphLab과 같은 그래프 병렬 추상화가 등장했다.
• 이러한 추상화는 계산이 각 버텍스(vertex)에서 실행되는 커널로 정의되는 vertex-centric 모델을 채택한다.
  • 버텍스(vertex) : 정점, 노드(node)와 같은 개념이다. ³
• 프리겔(Pregel)은 버텍스가 메시지를 통해 통신하는 추상화를 전달하는 Bulk Synchronous이다.
• GraphLab은 각 버텍스가 인접한 버텍스와 에지(edge)의 데이터를 읽고 쓸 수 있는 순차적(sequential) 공유 메모리 추상화이다.
  • GraphLab은 사용자가 데이터의 병렬 이동(=메시징)보다는 순차적 계산에 집중할 수 있도록 함으로써 그래프 병렬 알고리즘의 설계와 구현을 단순화한다.

Asynchronous Iterative Computation

• 많은 중요한 MLDM 알고리즘은 큰 파라미터 셋을 반복적으로 업데이트한다.
• 기본 그래프 구조 때문에 (버텍스 또는 에지에서) 파라미터 업데이트는 그래프 인접(adjacency) 구조를 통해 다른 파라미터 값에 의존한다.
• 이전 타임스텝의 파라미터 값을 입력으로 사용하여 모든 파라미터를 동시에(병렬로) 업데이트하는 동기(synchronous) 시스템과 달리, 비동기(asynchronous) 시스템은 가장 최근의 파라미터 값을 입력으로 사용하여 파라미터를 업데이트한다.
• 결과적으로, 비동기 시스템은 많은 MLDM 알고리즘에 상당한 알고리즘 이점을 제공한다.

• 동기 계산은 각 단계의 런타임이 가장 느린 시스템에 의해 결정되기 때문에 값비싼 성능 저하를 초래한다.
• 가장 느린 시스템의 성능 저하는 부하 및 네트워크 불균형, 하드웨어 가변성, 멀티 테넌스(Multi-Tenancy) 등 다양한 요인에 의해 발생할 수 있다.
  • 멀티 테넌스(Multi-Tenancy) : 소프트웨어 애플리케이션의 단일 인스턴스가 여러 클라이언트에게 서비스를 제공하는 아키텍처이다. ⁴
• 이러한 다른 서비스 활용의 불균형은 동기식 계산을 사용할 경우 상당한 성능 저하를 초래할 수 있다.
• 또한 개별 버텍스 커널의 복잡성과 수렴의 변동성(variability)은 그래프가 균일하게 파티션된 경우에도 실행 시간의 추가 변동성을 실행할 수 있다.
• 또한 각 버텍스에 필요한 실제 작업은 문제별 방식(ex. 로컬 수렴 속도)으로 데이터에 의존할 수 있다.

Dynamic Computation

• 많은 MLDM 알고리즘에서 반복 계산은 비대칭적으로 수렴한다.
  • Fig 1(b)를 보면 대부분의 버텍스는 단 한번의 업데이트만 필요했고, 버텍스의 약 3%만이 10개 이상의 업데이트가 필요했다.
• 또한 계산의 우선순위(priority)를 지정하면 수렴을 더욱 가속화할 수 있다. ⁵
• 그리고 초기 계산을 더 까다로운 파라미터에 집중함으로써 잠재적으로 수렴을 감소할 수 있다. (Fig 1(c))

• 프리겔은 일부 버텍스가 각 슈퍼 스텝에서 계산을 건너뛰도록 허용함으로써 제한된 형태의 동적 계산을 지원한다.
• GraphLab은 우선순위 부여뿐만 아니라 인접한 버텍스에서 정보를 적응적으로(adaptively) 끌어내는 기능을 허용한다.

Serializability

• 모든 병렬 실행이 동등한 순차적 실행을 보장함으로써 직렬화(serializability)는 병렬 MLDM 알고리즘의 설계, 구현 및 테스트와 관련된 많은 문제를 제거한다.
• 또한 많은 알고리즘은 직렬화가 보장되면 더 빠르게 수렴되며, 일부는 정확성을 위해 직렬화가 필요하다.
• 연산이 가능한 추상화는 동시성에 의해 도입된 복잡성을 상당 부분 제거하여 MLDM 개발자가 알고리즘과 모델 설계에 집중할 수 있도록 한다.
• GraphLab은 광범위한 일관성 설정을 지원하므로 프로그램이 정확성에 필요한 일관성 수준을 선택할 수 있다.

3. DIST. GraphLab Abstraction

• GraphLab은 데이터 그래프, 업데이트 기능, 동기화 동작의 3가지 주요 부분으로 구성된다.
  • 데이터 그래프(data graph)는 수정 가능한 프로그램 상태를 나타내며, 변경 가능한 사용자 정의 데이터를 저장하고 희소(sparse) 계산 의존성을 인코딩한다.
  • 업데이트 기능(update function)은 계산을 나타내며 scope라는 작은 중첩 컨텍스트에서 데이터를 변환하여 데이터 그래프에서 작동한다.
  • 동기화 동작은 전역 집계(global aggregate)를 동시에 유지한다.

예제 1

• 페이지랭크(PageRank) 알고리즘은 재귀적으로(recursively) 웹페이지 $v$의 랭크를 정의한다.
  • $R(v)=\frac{\alpha}{b}+(1-\alpha)$ $\ \sum_{u\ links\ to\ v}w_{u,v}\times R(\mu)$

3.1 Data Graph

• GraphLab은 프로그램 상태를 데이터 그래프라고 하는 방향성 그래프(directed graph)로 저장한다.
• 데이터 그래프 $G=(V,E,D)$는 사용자 정의 데이터 D를 관리하는 컨테이너이다.
  • 데이터(data) 용어는 모델 파라미터, 알고리즘 상태, 통계 데이터까지 광범위하게 사용된다.
• 사용자는 그래프의 버텍스 ${D_v:v\in V}$와 에지 ${D_{u\to v}:{u,v}\in E}$ 에 임의의 데이터를 연결할 수 있다.
• 데이터 그래프는 변경 가능하지만(mutable) 구조는 정적이며(static) 실행 중에는 변경할 수 있다.

예제 2

• 데이터 그래프는 웹 그래프로부터 직접 얻는데, 각 버텍스는 웹페이지이고, 각 에지는 링크에 해당된다.
• 버텍스 데이터 $D_v$는 $R(v)$에 저장하며 에지 데이터 $D_{u\to v}$는 링크의 방향성 가중치인 $w_{u,v}$에 저장한다.

3.2 Update Functions

• 계산은 업데이트 함수의 형태로 GraphLab로 인코딩된다.
• 업데이트 함수는 버텍스 범위(scope) 내에서 데이터를 수정하고 다른 버텍스에서 업데이트 함수의 향후 실행을 예약하는 상태 무상태(stateless) 프로시저이다.
  • Update : $f(v,S_v)\to (S_v,\Gamma)$
• 업데이트 기능을 실행한 후 $S_v$의 수정된 데이터는 데이터 그래프에 다시 기록된다.
• 버텍스 집합 $u\in \Gamma$은 실행 의미에 따라 업데이트 함수 $f(u,S_u)$를 적용하여 결국 실행된다.
• GraphLab은 사용자 정의 업데이트 기능이 인접한(adjacent) 버텍스 및 에지의 데이터를 읽고 수정할 수 있는 완전한 프리덤을 허용한다.
  • 이것은 사용자 코드를 단순화하고 사용자가 데이터 이동에 대해 추론할 필요를 제거한다.
  • 어떤 버텍스가 $\Gamma$에서 리턴되어 실행될지를 제어함으로써 업데이트 함수는 적응(adaptive) 계산을 효율적으로 표현할 수 있다.

• GraphLab 업데이트 함수는 인접 버텍스가 현재 업데이트를 예약하지 않은 경우에도 인접 버텍스의 데이터에 액세스할 수 있다.
• 하지만 프리겔(Pregel) 업데이트 기능은 메시지에 의해 시작되며 메시지의 데이터에만 액세스할 수 있으므로 표현할 수 있는 내용이 제한된다.
• GraphLab은 pull모델을 자연스럽게 표현하는데, 인접 버텍스는 스케줄링만 담당하고 업데이트 함수는 변경되지 않은 인접 버텍스 값을 직접 읽을 수 있기 때문이다.

예제 3

• 페이지랭크에 대한 업데이트 기능은 인접 버텍스의 현재 랭크의 가중치 합을 계산하고 이를 현재 버텍스의 랭크로 할당한다.
• 현재 버텍스의 값이 미리 정의된 임계값 이상으로 변경되는 경우에만 이웃이 업데이트되도록 예약한다.

3.3 The GraphLab Execution Model

• GraphLab에 대한 입력은 데이터 그래프 $G=(V,E,D)$, 업데이트 기능, 실행할 버텍스 $\Gamma$의 초기 셋으로 구성된다.
• 결과 데이터 그래프와 전역 값은 완료 시 사용자에게 반환된다.
• 보다 효율적인 분산 실행을 가능하게 하기 위해 공유 메모리 GraphLab의 실행 순서 요구 사항을 완화하고 GraphLab 런타임이 버텍스를 실행하는 최상의 순서를 결정할 수 있도록 한다.

3.4 Ensuring Serializability

• GraphLab은 여러 프로세스가 동일한 그래프에서 동일한 루프를 실행하고 다른 버텍스를 동시에 제거 및 실행하여 병렬 실행으로 자동 변환되는 풍부한 순차적(sequential) 모델을 제공한다.
  • 순차적 모델(sequential model)의미를 유지하려면 중복(overlapping) 계산이 동시에 실행되지 않도록 해야 한다.
• GraphLab 런타임은 직렬성(serializable) 실행을 보장한다.
  • 직렬성 실행은 알고리즘에 의해 실행될 때 업데이트 기능의 해당 직렬 일정이 있음을 의미한다.
• 직렬화를 달성하는 간단한 방법은 업데이트 기능을 동시에 실행하는 범위(scope)가 겹치지 않도록 하는 것인데, 이를 완전 일관성(full consistency) 모델이라고 한다.
• 그러나 업데이트 기능을 동시에 실행하는 것은 최소한 2개의 버텍스가 떨어져 있어야 하기 때문에 완전 일관성은 잠재적인 병렬성을 제한한다. (Fig 2(c) 참조)

• 그러나 많은 머신 러닝 알고리즘의 경우 업데이트 기능은 범위 내의 모든 데이터에 대한 전체 읽기/쓰기 액세스 권한을 필요로 하지 않는다.
• 직렬성을 유지하면서 더 큰 병렬성을 제공하기 위해 에지 일관성(edge consistency) 모델을 정의한다.
• 에지 일관성 모델은 각 업데이트 기능이 자신의 버텍스와 인접 에지에 대해 독점적인 읽기-쓰기 액세스 권한을 가지지만 인접 버텍스에 대한 읽기 전용 액세스 권한을 갖도록 한다. (Fig 2(b) 참조)
• 결과적으로 에지 일관성 모델은 범위가 약간 겹치는 업데이트 기능이 병렬로 안전하게 실행되도록 허용하여 병렬성(parallelism)을 증가시킨다. (Fig 2(c) 참조)

3.5 Sync Operation and Global Values

• 많은 MLDM 알고리즘에서 데이터 그래프에 저장된 데이터를 설명하는 전역 통계를 유지 관리해야 한다.
• GraphLab은 프리겔의 집계와 유사하게 동기화 동작은 associative commutative sum이다.
  • $Z=Finalize(\bigoplus_{v\in V}Map(S_v))$
• 프리겔과 달리 GraphLab의 동기화 동작은 전역 값의 업데이트된 추정치를 유지하기 위해 백그라운데엇 계속 실행된다.
• 모든 업데이트 기능은 전역 값에 액세스할 수 있으므로 업데이트 함수와 관련하여 동기화 동작의 직렬성을 보장하는 것은 비용이 많이 들고 일반적으로 모든 계산을 동기화하고 중지해야 한다.

4. Distributed GraphLab Design

• 분산 설계의 개요는 아래 그림과 같다.

• 동적(dynamic) 비동기(asynchronous) 그래프 알고리즘에 공통적으로 임의의 메모리 액세스 패턴때문에 GraphLab은 전체 그래프와 모든 프로그램 상태가 RAM에 상주해야 하는 분산 인메모리 설정에 중점을 둔다.
  • 인메모리(in-memory) 컴퓨팅 : 메모리 내에서 데이터의 저장 뿐 아니라 데이터의 연산까지 수행하는 최첨단 칩 기술이다. ⁶

• 데이터 그래프는 처음 도메인 특정 지식을 사용하거나 분산 그래프 분할 휴리스틱을 사용하여 k 부분으로 오버 파티셔닝된다.
• 아톰(atom)이라 하는 각 부분은 분산 스토리지 시스템(ex. HDFS, Amazon S3)에 별도의 파일로 저장된다.
  • 각 아톰 파일은 AddVertex(5000, vdata) 및 AddEdge(42$\to$314, edata)와 같은 명령을 생성하는 그래프의 간단한 바이너리 압축 저널이다.
• 또한 각 아톰은 파티션 경계에 인접한 버텍스 및 에지 집합인 고스트(ghosts)에 대한 정보를 저장한다.
• k 아톰의 연결 구조와 파일 위치는 아톰 인덱스 파일에 k 버텍스와 아톰 연결을 인코딩하는 에지가 있는 메타 그래프로 저장된다.
• 분산 로딩은 물리적 시스템 수에 대해 메타 그래프의 빠른 로드 밸런싱을 수행하여 수행된다.
• 그런 다음 각 머신은 할당된 각 아톰에서 저널을 재생하여 그래프의 로컬 부분을 구성한다.
• 재생 절차(playback)는 또한 메모리에 있는 로컬 파티션의 고스트를 인스턴스화한다.
  • 고스트(ghost)는 네트워크 전체에서 실제 대응에 대한 캐시로 사용된다.
  • 캐시 일관성(cache consistency)은 변경되지 않거나 일정한 데이터(ex. 에지 가중치)의 전송을 제거하는 간단한 버전 관리 시스템을 사용하여 관리된다.

4.2 Distributed GraphLab Engines

• 분산 GraphLab 엔진은 3.3 섹션에 정의된 실행 모델을 에뮬레이트(emulate)하고 업데이트 기능 및 동기화 작업을 실행하고 예정된 버텍스 $\Gamma$ 셋을 유지하며 적절한 일관성 모델과 관련하여 직렬성을 보장한다.

4.2.1 Chromatic Engine

• 직렬성 병렬 실행을 달성하는 고전적인 기술은 인접한 버텍스가 같은 색(color)을 공유하지 않도록 각 버텍스에 색을 할당하는 것이다.
• 데이터 그래프의 버텍스 색상이 주어지면 다음 색상으로 진행하기 전에 버텍스 셋 $\Gamma$에서 동일한 색상의 모든 버텍스를 동기적으로 실행하여 에지 일관성 모델을 만족시킬 수 있다.
• 단일 색상 내의 모든 버텍스를 업데이트하고 모든 변경 사항을 전달하는 프로세스를 설명하기 위해 BSP 모델의 슈퍼 단계와 유사하게 색상 단계(color-step)라는 용어를 사용한다.
  • 이러면 색상 단계 간에 동기화 작업을 안전하게 실행할 수 있다.

• 크로매직 엔진이 동기식 색상 단계로 작동하는 동안 고스트 버젝스 및 에지에 대한 변경 사항은 변경될 때 비동기식으로 전달된다.
• 결과적으로 크로매틱 엔진은 각 생상 단계 내에서 네트워크 대역폭과 프로세서 시간을 모두 효율적으로 사용한다.

4.2.2 Distributed Locking Engine

• GraphLab은 각 버텍스에 Reader-Writer 락(lock)을 연결하여 분산된 상호 배제(exclusion)를 달성한다.
• 그런 다음 다른 락 프로토콜을 사용하여 다른 일관성 모델을 구현할 수 있다.
• 버텍스 일관성(vertex consistency)은 요청된 각 범위의 중앙 버텍스에 대한 쓰기 락을 획득하여 달성된다.
• 에지 일관성(edge consistency)은 중앙 버텍스에 대한 쓰기 락을 획득하고 인접 버텍스에 대한 읽기 락을 획득하여 달성된다.
• 마지막으로 중앙 버텍스와 모든 인접 버텍스에 대한 쓰기 락을 획득하여 완전한 일관성을 달성한다.

• 데드락은 표준 순서에 따라 순차적으로 락을 획득하여 방지한다.
• 머신 ID 다음에 버텍스 ID(owner(v), v)가 오는 순서를 사용한다.
• 그리고 그래프가 파티셔닝되어 있으므로 각 시스템이 로컬 버텍스에서만 업데이트를 실행하도록 제한한다.
• 고스트 버텍스/에지는 업데이트가 범위의 모든 정보에 직접 메모리에 액세스할 수 있도록 한다.

• 각 시스템의 워커(worker) 스레드는 스케줄러가 비어 있을 때까지 위 알고리즘에 설명된 루프를 평가한다.

Pipelined Locking and Prefetching

• 각 머신은 락이 요청되었지만 충족되지 않은 버텍스 파이프라인을 유지 관리한다.
• 락 획득 및 데이터 동기화를 완료하는 버텍스는 파이프라인을 떠나 워커 스레드에 의해 실행된다.
• 파이프라인 락 엔진 루프의 개요는 아래와 같다.

• 파이프라인 시스템을 구현하기 위해 일반 Reader-Writer 락은 경합 시 파이프라인 스레드를 중지하기 때문에 사용할 수 없다.
• 따라서 콜백을 통해 작동하는 Reader-Writer 락의 non-blocking 변형을 구현했다.
• 락 획득 요청은 요청이 이행되면 호출되는 콜백에 대한 포인터를 제공한다.
• 이러한 콜백은 시스템 간에 락 요청을 순서대로 전달하는 분산 연속 전달 방식으로 연결된다.
• 지연 시간(latency)을 더욱 줄이기 위해 각 시스템이 로컬 락을 완료하는 즉시 락 데이터의 동기화가 수행된다.

4.3 Fault Tolerance

• 분산 체크포인트(checkpoint) 메커니즘을 사용하여 분산 GraphLab 프레임워크에 장애 허용(fault tolerance)을 도입한다.
• 장애가 발생한 경우 시스템은 마지막 체크포인트에서 복구된다.
• GraphLab은 분산 스냅샷(snapshot)을 생성하기 위해 2가지 전략을 평가한다.
  • 하나는 스냅샷이 생성되는 동안 모든 계산이 일시 중단하는 동기 방식이고 다른 하나는 실행을 중단하지 않고 스냅샷을 점진적으로 생성하는 비동기 방식이다.
• 동기식 스냅샷은 업데이트 기능의 실행을 일시 중단하고 모든 통신 채널을 플러시(flush)한 다음 마지막 스냅샷 이후로 수정된 모든 데이터를 저장하여 구성된다.
  • 변경 사항은 분산 파일 시스템의 저널 파일에 기록되고 이전 스냅샷에서 실행을 다시 시작하는 데 사용할 수 있다.
• GraphLab은 Chandy Lamport 스냅샷을 기반으로 완전히 비동기식 대안을 설계했다.

• Alg 5는 업데이트 기능으로 표현되며 다음 조건에서 일관된 스냅샷을 보장한다.
  1. 에지 일관성은 모든 업데이트 기능에 사용된다.
  2. 스케줄은 범위가 락이 해제되기 전에 완료된다.
  3. 스냅샷 업데이트는 다른 업데이트 기능보다 우선시된다.

• 동기 및 비동기 스냅샷은 모두 고정된 간격으로 시작된다.
• 간격 선택은 실패 시 마지막 체크포인트 이후 손실된 계산과 체크포인트 구성 비용의 균형을 맞춰야 한다.
  • $T_{interval}=\sqrt{2T_{checkpoint}T_{MTBF}}$

4.4 System Design

• Fig 5(a)는 GraphLab 시스템의 개요를 보여준다.
• Fig 5(b)는 GraphLab 락 엔진 구현의 개요를 보여준다.
• GraphLab이 클러스터에서 실행되면 GraphLab 프로그램의 인스턴스가 각 시스템에서 실행된다.
• GraphLab 프로세스는 대칭(symmetric)이며 TCP/IP를 통해 비동기 RPC 프로토콜을 사용하여 서로 직접 통신한다.
• 각 프로세스는 로컬 그래프 스토리지 내에서 관리되는 분산 그래프의 파티션을 담당하고 분산 락을 제공한다.
• 캐시는 원격 그래프 데이터에 대한 액세스를 제공하는 데 사용된다.
• 각 프로세스는 프로세스에 할당된 $\Gamma$의 버텍스를 관리하는 스케줄러도 포함되어 있다.
  • 런타임에 각 머신의 로컬 스케줄러는 버텍스를 실행하는 데 필요한 데이터와 락을 수집하는 prefetch 파이프라인에 버텍스를 공급한다.
• 모든 데이터와 락이 획득되면 버텍스는 워커 스레드 풀에 의해 실행된다.
• 버텍스 스케줄링은 로컬 버텍스에 대한 스케줄을 관리하고 원격 버텍스에 대한 스케줄링 요청을 전달하는 각 머신으로 분산된다.
• 마지막으로 분산 합의 알고리즘(distributed consensus algorithm)은 모든 스케줄러가 비어 있는 시기를 결정하는 데 사용된다.
  • 분산 런타임의 대칭 설계로 인해 중앙 집중식 병목 현상이 없다.

References

1. 위키백과 - 추상화(컴퓨터 과학) ↩

2. [리눅스/유닉스] 시그널이란? 시그널(SIGNAL) 종류, 상황, 유사 시그널 차이점 - 양햄찌(jhnyang) ↩

3. [Spark] GraphFrame을 활용한 그래프, 서브그래프, 모티프 by poeun ↩

4. 멀티 테넌시(multi-tenancy) - 솔루션 헌터 ↩

5. Zhang, Yanfeng, et al. “PrIter: A distributed framework for prioritized iterative computations.” Proceedings of the 2nd ACM Symposium on Cloud Computing. 2011. ↩

6. 삼성전자, MRAM 기반 인-메모리 컴퓨팅 세계 최초 구현 ↩