정현석

개인 저장공간입니다.
Since 2021.10

7 분 소요

image

“PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs”(OSDI 2012) 논문을 개인 공부 및 리뷰를 위해 정리한 글이다.

대규모 소셜 네트워크나 웹 그래프와 같은 실제 자연 그래프(Natural Graphs)는 소수의 고차수(high-degree) 정점이 전체 연결을 지배하는 멱법칙(Power-law) 차수 분포를 갖는다. 기존의 Pregel이나 GraphLab 같은 그래프 병렬 시스템은 정점을 개별 머신에 고정하고 간선을 자르는 엣지 컷(Edge-Cut) 방식에 의존했기 때문에, 극심한 작업 불균형과 막대한 통신·스토리지 오버헤드라는 근본적인 병목에 직면했다. PowerGraph는 버텍스 프로그램을 Gather-Apply-Scatter(GAS) 단계로 인수분해(factoring)하고, 정점을 여러 머신에 분할하는 버텍스 컷(Vertex-Cut)을 도입하여 고차수 정점의 계산과 통신을 간선 단위로 분산해 이 병목을 완화한다.

논문 출처 pdf : PowerGraph paper

1. Introduction

그래프 병렬 추상화는 각 정점이 작은 이웃만을 갖는다는 가정하에 설계되었으나, 실제 자연 그래프는 이러한 가정을 완전히 무너뜨린다.

  • 그래프 병렬 추상화의 기본 전제: 전통적인 그래프 병렬 추상화(abstraction)는 각 버텍스가 비교적 작은 이웃을 갖는다는 점에 의존하여 병렬성을 극대화하고, 효과적인 파티셔닝을 통해 머신 간 통신을 최소화한다.
  • 자연 그래프의 멱법칙(Power-law) 특성: 그러나 소셜 네트워크 및 웹과 같은 실제 현상에서 기인하는 자연 그래프에는 일반적으로 멱법칙(power law) 차수(degree) 분포가 나타난다.
    • 이는 소수의 버텍스 서브셋(subset)이 그래프 전체 연결의 대다수를 차지함을 의미한다.
    • 이러한 극단적인 차수 편향 때문에 멱법칙 그래프는 기존 방식으로 파티셔닝하기 극히 어렵고 분산 환경에서 효율적으로 표현하기 어렵다.
  • PowerGraph의 핵심 접근법: PowerGraph는 멱법칙 그래프 계산의 병목을 해결하기 위해 버텍스 프로그램의 내부 구조를 활용하여, 버텍스 단위 대신 에지에 걸쳐 계산을 명시적으로 분해(factoring)한다.

정점에 집중되던 부하를 에지 단위로 분산시킨다. 결과적으로 PowerGraph는 정점 단위 제어보다 넓은 병렬 처리 폭을 제공하고 네트워크 통신 및 저장 비용을 줄이는 접근 방식을 제시한다.

2. Graph-Parallel Abstractions

그래프 병렬 계산 프레임워크는 대규모 그래프 구조와 그 위에서 실행되는 사용자 로직을 추상화하여 분산 환경의 복잡성을 감춘다.

  • 그래프 병렬 추상화의 정의: 그래프 병렬 추상화는 희소(sparse) 그래프 $G={V,E}$와 각 버텍스 $v\in V$에서 병렬로 실행되며 인접 이웃 인스턴스 $Q(u)$와 상호작용하는 버텍스 프로그램 $Q$로 구성된다.

2.1 Characterization

다양한 그래프 계산 프레임워크의 동작 방식은 정점 중심의 3단계 실행 모델인 GAS로 일반화하여 비교할 수 있다.

  • GAS 모델의 개념: GAS 모델은 버텍스 프로그램의 세 가지 개념적 실행 단계인 Gather, Apply, Scatter를 나타낸다.
  • 수집(Gather) 단계: 인접 버텍스 및 에지에 대한 정보는 $Q(u)$가 실행되는 버텍스 $u$의 이웃에 대한 합계를 통해 수집된다.
    • $\sum \leftarrow\bigoplus_{v\in Nbr[u]}g(D_u,D_{(u,v)},D_v)$
  • 적용(Apply) 단계: 수집 결과값 $\sum$은 중심(central) 버텍스 값을 업데이트하는 데 사용된다.
    • $D_u^{new}\leftarrow a(D_u,\sum)$
  • 분산(Scatter) 단계: 중심 버텍스의 갱신된 값을 사용하여 인접한 에지의 데이터를 업데이트한다.
    • $(D_{(u,v)})\leftarrow s(D_u^{new},D_{(u,v)},D_v)$

기존 프레임워크들은 이 세 단계를 구현하는 방식에서 서로 다른 트레이드오프를 취한다.

  • Pregel의 접근: Pregel 추상화에서 Gather 단계는 메시지 컴바이너(combiner)를 사용하여 구현되고, Apply 및 Scatter 단계는 버텍스 프로그램 내부에서 표현된다.
  • GraphLab의 접근: GraphLab은 전체 이웃 상태를 버텍스 프로그램에 직접 노출하여 사용자가 프로그램 내에서 Gather 및 Apply 단계를 자유롭게 정의할 수 있도록 지원한다.
  • 통신 동기화 방식: GraphLab 추상화는 버텍스 또는 에지 데이터에 대한 변경 사항이 인접한 버텍스에 자동으로 반영되도록 구성되어, Gather/Scatter 단계의 통신 측면을 암시적으로 정의한다.

3. Challenges of Natural Graphs

실제 세계의 그래프 데이터가 갖는 극단적인 비대칭성은 기존 그래프 병렬 프레임워크의 성능을 심각하게 저하시킨다.

  • 희소성 구조와 차수 편향: 그래프의 희소성(sparsity) 구조는 효율적인 분산 그래프 병렬 계산에 고유한 문제를 제기한다. 특히 자연 그래프의 대표적 특징은 심하게 왜곡된(skewed) 멱법칙 차수 분포이다.
  • 고차수 정점의 존재: 대다수 버텍스에는 이웃이 비교적 적지만, 극소수의 정점은 수백만 개 이상의 이웃을 갖는다. (예: 소셜 네트워크의 유명인 계정)
  • 멱법칙 수학적 정의: 멱법칙 차수 분포에서 버텍스가 차수 $d$를 가질 확률은 다음과 같이 역제곱 법칙을 따른다.
    • $P(d)\propto d^{-\alpha}$

Fig 1은 트위터 팔로워 네트워크의 인/아웃 차수(degree) 분포를 시각화한 결과로, 뚜렷한 선형 멱법칙 특성을 보여준다.

image

이러한 차수 불균형은 분산 시스템의 전반적인 영역에서 심각한 병목을 초래한다.

  • 작업 불균형(Work Balance): 멱법칙 차수 분포는 버텍스를 대칭적으로 처리하는 기존 그래프 병렬 추상화에서 극심한 연산 부하 불균형을 초래한다. 단 하나의 고차수 정점을 처리하는 머신이 전체 작업의 완료 시간을 지연시키는 스트래글러(straggler)가 된다.
  • 파티셔닝(Partitioning): 자연 그래프는 컷 에지를 최소화하는 전통적 파티셔닝 기법이 통하지 않아, GraphLab과 Pregel 모두 지역성(locality)이 취약한 단순 해시 기반(임의) 분할에 의존해야 한다.
  • 통신(Communication): 편향된 차수 분포는 통신의 심각한 비대칭성으로 이어져, 고차수 정점을 호스팅하는 노드의 네트워크 대역폭 병목을 유발한다.
  • 스토리지(Storage): 그래프 병렬 추상화는 각 버텍스에 대한 인접 에지 정보를 로컬에 보관해야 하므로, 각 버텍스는 해당 차수에 선형적으로 비례하는 메모리를 소비한다.

소수의 슈퍼스타 정점이 분산 클러스터 전체를 마비시키는 구조다.

4. PowerGraph Abstraction

PowerGraph는 정점 단위로 묶여 있던 연산을 에지 단위로 쪼개어 고차수 정점의 계산 병목을 원천적으로 제거한다.

  • GAS 분해와 버텍스 프로그램 팩토링: PowerGraph는 멱법칙 그래프의 계산 병목을 해결하기 위해 GAS 분해를 직접 활용하여 에지에 걸쳐 버텍스 프로그램을 팩토링(factoring, 인수분해)함으로써 차수 의존성을 완전히 제거한다.
  • 하이브리드 실행 엔진 지원: PowerGraph는 고도로 병렬화된 대량 동기식 Pregel 계산 모델(BSP)과 계산 효율적인 비동기식 GraphLab 계산 모델을 모두 지원하여 알고리즘 특성에 맞게 선택할 수 있다.

4.1 GAS Vertex-Programs

버텍스 프로그램을 잘 정의된 인터페이스 함수들로 세분화함으로써, 단일 정점의 계산을 여러 머신에 분산할 수 있는 이론적 기반이 마련된다.

image

  • GASVertexProgram 인터페이스: PowerGraph 추상화의 계산은 GASVertexProgram 인터페이스를 구현하는 stateless 버텍스 프로그램으로 인코딩되며, gather, sum, apply, scatter 기능을 명시적으로 모델링한다. (Fig 2)
  • 엔진의 단계적 호출: 각 기능은 Alg 1의 의미론에 따라 PowerGraph 실행 엔진에 의해 단계별로 호출된다.
  • 계산의 데이터 이동: 버텍스 프로그램을 세분화하여 팩토링함으로써 실행 엔진은 단일 버텍스 프로그램을 여러 머신에 안전하게 분산 배포하고, 무거운 데이터 대신 가벼운 계산을 데이터가 위치한 머신으로 이동시킬 수 있다.

GAS의 각 단계는 다음과 같이 정밀하게 동작한다.

  • Gather 단계의 Map-Reduce 동작: Gather 단계에서 gather 및 sum 함수는 버텍스 이웃 정보를 집계하기 위한 맵(map) 및 리듀스(reduce) 연산으로 기능한다.
    • gather 함수는 $u$에 인접한 에지들에서 병렬로 호출된다.
    • 처리할 에지 셋은 none, in, out, all 중 하나로 지정되는 gather nbrs에 의해 결정된다.
    • gather 함수는 인접 버텍스와 에지 데이터를 전달받아 임시 어큐뮬레이터(accumulator)를 반환한다.
    • 반환된 결과들은 가환(commutative) 및 결합(associative) 속성을 갖는 sum 연산을 통해 병렬 집계된다.
    • 최종 집계 결과 $a_u$는 Apply 단계로 전달되고 PowerGraph 엔진에 의해 캐싱된다.
  • Apply 단계의 상태 갱신: Gather 단계가 완료되면 Apply 함수는 최종 어큐뮬레이터를 사용하여 새로운 버텍스 값 $D_u$를 계산하고 이를 데이터 그래프에 원자적(atomically)으로 갱신한다.
  • Scatter 단계의 에지 갱신 및 신호 전파: Scatter 단계 동안 scatter 함수는 $u$에 인접한 에지들에서 병렬로 호출되어 데이터 그래프에 기록될 새 에지 값 $D_{(u,v)}$를 생성한다.
    • scatter 함수는 인접 버텍스에 대해 캐시된 어큐뮬레이터 $a_v$를 동적으로 업데이트하는 데 사용되는 선택적(optional) 값 $\Delta a$를 반환할 수 있다.

단일 정점의 계산이 에지 단위의 가벼운 맵-리듀스로 분해된다. Fig 3은 PowerGraph 추상화를 활용하여 대표적인 그래프 알고리즘인 PageRank, Greedy Graph Coloring, Single Source Shortest Path(SSSP)를 구현한 모습을 보여준다.

image

4.2 Delta Caching

반복 계산 알고리즘에서는 변경된 차이값만을 반영함으로써 중복 연산을 줄일 수 있다.

  • 어큐뮬레이터 캐시 유지: PowerGraph 엔진은 각 버텍스에 대해 이전 Gather 단계에서 계산된 최종 어큐뮬레이터 $a_u$를 메모리에 캐시로 유지한다.
  • 증분 델타($\Delta a$) 반영: Scatter 함수는 sum 함수를 사용하여 이웃 버텍스 $v$의 캐시된 어큐뮬레이터 $a_v$에 원자적으로 가산되는 증분 값 $\Delta a$를 선택적으로 반환할 수 있다.
  • 캐시 무효화 및 완전 재계산: 만약 $\Delta a$가 반환되지 않으면 해당 이웃의 캐시된 $a_v$는 무효화(cleared)되며, 이후 버텍스 $v$에서 버텍스 프로그램이 다시 실행될 때 전체 이웃에 대한 완전한 Gather 단계가 강제된다.

델타 캐싱을 통해 수렴에 가까워진 그래프에서는 이웃 재탐색 횟수를 줄일 수 있다.

5. Distributed Graph Placement

계산 추상화의 분해 못지않게 중요한 과제는 대규모 그래프 데이터를 클러스터 노드들에 어떻게 배치할 것인가이다.

  • 데이터 그래프 배치의 중요성: PowerGraph 추상화는 계산 상태를 저장하고 버텍스 프로그램 간 상호작용을 처리하기 위해 분산 데이터 그래프에 의존한다. 데이터 그래프의 배치 구조는 클러스터 간 네트워크 통신을 최소화하고 작업 균형을 유지하는 핵심 결정 요인이다.
  • 전통적 Balanced p-way Edge-Cut의 한계: $p$개 머신 클러스터에 그래프를 배치하는 기존 표준 기법은 균형 잡힌 $p$-way 엣지 컷(balanced p-way edge-cut)을 구성하는 것이다.
    • 이 방식에서는 버텍스를 머신들에 균등하게 분배하고, 머신 경계를 가로지르는 컷 에지(cut edge)의 수를 최소화하는 것을 목표로 한다.
    • 그러나 멱법칙 그래프에서는 소수의 고차수 정점 때문에 에지 컷 알고리즘이 전혀 힘을 쓰지 못한다.
    • 결국 GraphLab과 Pregel 모두 멱법칙 그래프 앞에서는 지역성을 포기한 단순 무작위 해시 버텍스 배치에 의존할 수밖에 없었다.

image

  • 엣지 컷의 스토리지 및 통신 오버헤드: 컷팅된 모든 에지는 복제본으로 인해 심각한 스토리지 및 네트워크 오버헤드를 발생시킨다.
    • 분산 프레임워크들은 인접 정보의 로컬 복사본과 함께 버텍스 및 에지 데이터의 고스트(ghost, 로컬 복사본)를 유지해야 하기 때문이다.
    • 예를 들어 Fig 4(a)에서 보듯 4개 버텍스로 구성된 간단한 그래프의 3방향 에지 컷만으로도 5개의 고스트 버텍스가 생성되고 모든 에지 데이터가 복제된다.
    • 컷 에지와 연관된 버텍스 및 에지 데이터의 모든 변경 사항은 네트워크를 통해 실시간으로 동기화되어야 하므로 통신 병목이 폭증한다.

엣지를 자르는 순간 정점 복제와 네트워크 동기화 비용이 함께 증가한다.

5.1 Balanced p-way Vertex-Cut

PowerGraph는 엣지를 자르는 대신 정점을 쪼개는 버텍스 컷(Vertex-Cut)으로 발상을 완전히 전환한다.

image

  • 버텍스 프로그램의 분산 실행: 버텍스 프로그램을 에지를 따라 팩토링함으로써 PowerGraph 추상화에서는 단일 버텍스 프로그램이 여러 머신에 걸쳐 분산 실행될 수 있다.
  • 고차수 정점 분할 예시: Fig 5에서 단일 고차수 버텍스 프로그램은 두 머신으로 분할되어 Gather 및 Scatter 단계가 각 머신에서 병렬로 실행되고, 어큐뮬레이터와 버텍스 데이터만이 네트워크를 통해 교환된다.
  • 버텍스 컷의 핵심 이점:
    • 에지 중복 없는 저장: 각 머신은 자신에게 할당된 에지 정보만을 정확히 한 번 저장하므로 에지 데이터의 중복 복제가 발생하지 않으며, 에지 변경 사항을 네트워크로 전송할 필요도 없다.
    • 작업 균형 달성: 방대한 양의 에지를 머신들에 균등하게 분배함으로써 고차수 정점으로 인한 연산 쏠림을 원천 방지한다.
    • 통신 오버헤드 억제: 버텍스 데이터의 변경 사항만 해당 버텍스가 걸쳐 있는 머신들에 동기화되므로, 스토리지 및 네트워크 오버헤드는 정점이 분할된 머신 수에만 비례한다.

수학적으로 Balanced p-way 버텍스 컷은 각 에지 $e\in E$를 머신 $A(e)\in {1,…,p}$에 할당함으로써 정점의 복제 계수를 최소화하는 것을 목표로 공식화된다.

  • 마스터-미러 복제 모델:
    • 여러 머신에 복제된 각 버텍스 $v$에 대해 복제본 중 하나가 무작위로 마스터(Master)로 지정되어 버텍스 데이터의 기준 버전을 관리한다.
    • 나머지 복제본들은 미러(Mirror)가 되어 버텍스 데이터의 로컬 읽기 전용 캐시를 유지한다. (Fig 4(b))
    • Fig 4(b)에서 보듯 동일한 그래프에 대해 3방향 버텍스 컷을 적용하면 단 2개의 미러 정점만이 생성된다.
    • Apply 단계 등에서 발생하는 버텍스 데이터 변경 사항은 먼저 마스터에 기록된 후 모든 미러로 즉시 브로드캐스트된다.
  • 침투 이론(Percolation Theory)과 버텍스 컷의 정당성:
    • 물리학의 침투 이론(Percolation theory)에 따르면 멱법칙 그래프는 구조적으로 버텍스 컷에 유리한 특성을 갖는다.
    • 직관적으로 극소수의 초고차수 버텍스를 절단(분할)하는 것만으로도 거대한 그래프 네트워크를 손쉽게 독립된 조각들로 분리해낼 수 있다.
    • 에지 균등 분배 제약조건 덕분에 초고차수 정점이 존재하더라도 머신 간 부하가 거의 균등하게 분배된다.
  • 무작위 에지 배치의 장점: 버텍스 컷을 구성하는 가장 단순한 방법은 에지를 머신에 균등하게 무작위 할당(Random/Hash Edge Placement)하는 것이다. 이 방식은 데이터 병렬 처리가 가능하며, 대규모 그래프에서도 부하가 고르게 분배될 뿐 아니라 스트리밍 환경에도 손쉽게 적용할 수 있다.

정점을 쪼개자 비로소 자연 그래프의 고질적인 부하 불균형이 풀렸다.

6. 핵심 요약 및 시사점

PowerGraph는 멱법칙 그래프 처리에 내재된 구조적 한계를 버텍스 컷으로 우회한 대표적인 분산 그래프 시스템이다.

  • GAS 분해 모델 확립: Gather-Apply-Scatter 인터페이스를 통해 정점 연산을 에지 단위로 팩토링하여, 고차수 정점이라도 다수의 머신에 연산을 분산할 수 있는 추상화를 정립했다.
  • Edge-Cut에서 Vertex-Cut으로의 패러다임 전환: 전통적인 정점 고정-엣지 절단 방식 대신 엣지 고정-정점 분할(Vertex-Cut)을 채택함으로써, 멱법칙 그래프의 통신 병목과 스토리지 복제 낭비를 크게 줄였다.
  • 마스터-미러 복제 아키텍처: 정점 복제본을 마스터와 읽기 전용 미러로 이원화하여 분산 상태 동기화의 일관성을 효율적으로 유지했다.
  • 동기식과 비동기식의 통합 지원: Pregel의 대량 동기식(BSP) 모델과 GraphLab의 비동기식 모델을 단일 엔진에서 포괄하여 다양한 그래프 알고리즘에 대한 유연한 최적화를 실현했다.

6.1 한계와 트레이드오프

PowerGraph의 이점은 다음 전제 위에서 성립하므로, 도입 전에 워크로드가 이 조건을 만족하는지 따져야 한다.

  • GAS 인수분해의 전제: 버텍스 프로그램이 이웃별 지역 계산과 가환(commutative)·결합(associative) 집계로 표현 가능해야 한다. 이 형태로 쪼갤 수 없는 알고리즘은 GAS 인터페이스에 그대로 얹기 어렵다.
  • 정점 복제 비용: 버텍스 컷은 에지 복제를 없애는 대신 고차수 정점의 버텍스 데이터를 여러 머신에 복제하고 마스터-미러 동기화 메시지를 발생시킨다. 통신 비용이 사라지는 것이 아니라 에지 단위에서 정점 단위로 옮겨간다.
  • 델타 캐싱의 조건부 이득: Scatter가 $\Delta a$를 반환하지 않으면 캐시가 무효화되어 전체 Gather가 강제되므로, 증분값을 정의할 수 있는 알고리즘에서만 이득이 난다.
  • 차수 분포 의존성: 버텍스 컷의 이점은 차수 분포가 극단적으로 치우친 자연 그래프를 전제로 한다. 차수가 고르게 분포한 그래프에서는 엣지 컷 대비 이점이 줄어들 수 있다.
  • 평가 조건: 논문의 성능 수치는 저자들이 구성한 클러스터와 특정 데이터셋(트위터 팔로워 그래프 등)에서의 저자 실측이다. 다른 하드웨어·워크로드로 일반화하려면 별도 검증이 필요하다.

References

  • Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., & Guestrin, C. (2012). PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12) (pp. 17-30). https://www.usenix.org/conference/osdi12/technical-sessions/presentation/gonzalez

댓글남기기

참고