[논문 리뷰] Pregel: A System for Large-Scale Graph Processing

2022-09-21 7 분 소요

“Pregel: A System for Large-Scale Graph Processing” 논문을 개인 공부 및 리뷰를 위해 쓴 글입니다. 논문 출처 pdf : pregel paper

대규모 그래프 처리는 불규칙한 메모리 접근 패턴과 동적 통신 구조로 인해 기존 MapReduce 프레임워크로는 비효율성을 극복하기 어려웠다. 구글의 Pregel은 “정점 중심(Think Like a Vertex)”의 순수 메시지 전달 모델과 동기식 단계 모델을 결합하여 수십억 개 정점을 갖는 초대형 그래프를 수천 대의 범용 클러스터에서 안정적으로 병렬 처리할 수 있는 분산 컴퓨팅 패러다임을 확립했다.

Pregel: 대규모 그래프를 쉽게 처리하는 구글의 똑똑한 시스템

Pregel은 웹 페이지 링크 그래프나 대규모 소셜 네트워크와 같이 극도로 복잡하게 얽힌 그래프 데이터를 분산 클러스터 환경에서 효율적으로 처리하기 위해 구글이 제안한 전용 그래프 처리 시스템이다.

극대화된 확장성과 장애 허용성: 수천 대의 상용 머신으로 구성된 클러스터에서 데이터 규모가 선형적으로 증가해도 안정적인 수평 확장을 지원하며, 머신 장애 시에도 연산을 지속할 수 있는 결함 감내 체계를 갖추었다.
거미줄형 복잡 데이터의 최적화: 임의의 포인터 추적이 잦은 그래프 알고리즘의 특성을 메모리 기반 분산 데이터 모델로 해결한다.
현대 프레임워크로의 계승: Pregel이 정립한 반복형 메시지 전달 및 단계적 동기화 개념은 아파치 지라프(Apache Giraph) 등 오픈소스 그래프 처리 시스템으로 이어졌고, 스스로 Pregel에서 영감을 받았다고 밝힌 LangGraph 같은 현대 에이전트 오케스트레이션 프레임워크에서도 다시 등장한다.¹

정점 관점에서 생각하면 수십억 개의 노드도 독립적인 연산 단위로 분할된다.

왜 Pregel이 필요했을까? (Introduction)

그래프 알고리즘은 최단 경로 탐색, 군집화(Clustering), 페이지랭크(PageRank) 등 다양한 핵심 도메인에서 널리 활용되지만, 기존 범용 분산 프레임워크 위에서는 구조적인 병목에 부딪힌다.

비규칙적 메모리 접근: 포인터를 따라 그래프를 순회하는 패턴 때문에 캐시 지역성(Locality)이 극도로 낮아진다.
정점당 낮은 연산 밀도: 개별 정점 단위에서 처리할 연산량은 매우 적은 반면, 정점 간 통신 오버헤드가 상대적으로 크다.
불규칙한 병렬 처리 부하: 탐색 깊이나 차수(Degree) 분포에 따라 실행 런타임의 병렬 작업량이 들쑥날쑥하게 변한다.
단일 장애 취약성: 분산 머신 수백, 수천 대로 확장할수록 파티션 간 네트워크 트래픽이 폭증하고 개별 머신 결함이 전체 분산 작업 중단으로 직결된다.

기존 대안들 역시 명확한 한계를 지니고 있었다.

자체 커스텀 분산 시스템 구축: 알고리즘마다 분산 메시징, 동기화, 장애 복구를 매번 바닥부터 구현해야 하므로 구현 부담이 크다.
MapReduce 활용: 반복 그래프 알고리즘 수행 시 각 스테이지마다 그래프 전체 상태를 HDFS/GFS에 기록하고 다시 읽어야 하므로, 불필요한 직렬화/역직렬화와 I/O 오버헤드로 인해 심각하게 비효율적이다.
기타 병렬 프레임워크: 메시지 전달이나 락(Lock) 기반 동기화는 데드락이나 경쟁 상태(Race Condition)를 유발하기 쉽고, 클러스터 규모 결함 감내(Fault Tolerance) 지원이 취약하다.

Pregel은 이 문제를 해결하기 위해 BSP(Bulk Synchronous Parallel) 모델을 채택했다. BSP 모델에서는 모든 프로세서가 일련의 반복 단계인 슈퍼스텝(Superstep)을 수행하며, 각 슈퍼스텝은 로컬 계산, 메시지 교환, 그리고 전역 장벽(Barrier) 동기화의 3단계로 엄격히 통제된다. 합창단이 한 소절씩 동시에 부르고 소절 끝의 전역 장벽에서 다음 박자를 맞추는 구조와 같다.

동기식 장벽 덕분에 복잡한 락 없이도 데드락 없는 병렬성을 보장한다.

이미지출처 ²

이미지출처 ³

Pregel은 어떻게 계산하나? (Model of Computation)

Pregel의 기본 연산 단위는 정점(Vertex)이며, 계산은 일련의 전역 슈퍼스텝을 거쳐 반복 수행된다.

입력 데이터 구조: 기본 모델은 방향 그래프(Directed Graph)이다. 각 정점은 고유한 식별자(ID)와 수정 가능한 정점 값을 가지며, 에지(Edge)는 소스 정점에서 타겟 정점으로의 방향 정보와 에지 값을 보유한다. 에지는 계산의 독립 주체가 아니라 메시지를 라우팅하는 통로 역할을 수행한다.
슈퍼스텝 기반 계산 주기:
- 각 슈퍼스텝 $S$에서 모든 활성 정점은 동일한 사용자 정의 함수를 병렬로 실행한다.
- 정점은 이전 슈퍼스텝 $S-1$에서 전송된 메시지들을 수신한다.
- 수신된 메시지를 바탕으로 로컬 상태 및 나가는 에지의 값을 갱신한다.
- 나가는 에지를 따라(또는 알려진 타겟 ID로 직접) 슈퍼스텝 $S+1$에서 전달될 메시지를 전송한다.
- 필요한 경우 정점 및 에지를 추가하거나 삭제하는 그래프 토폴로지 변경을 요청한다.⁴

알고리즘 종료 조건:
- 슈퍼스텝 0에서 모든 정점은 활성(Active) 상태로 시작한다.
- 정점은 할 작업을 마치면 스스로 비활성(Inactive) 상태로 전환하는 종료 투표(VoteToHalt)를 선언한다.
- 비활성 상태인 정점이라도 다른 정점으로부터 새로운 메시지를 수신하면 다음 슈퍼스텝에서 즉시 다시 활성 상태로 전환된다.
- 클러스터 내의 모든 정점이 비활성 상태이고 전달 중인 메시지가 없는 시점에 전체 계산이 자동으로 종료된다.
- 결과 출력은 각 정점의 최종 상태 값이거나, 집계기를 통해 생성된 전역 요약 통계값이다.

대표적인 예시로 그래프 내의 전역 최댓값을 찾는 문제를 들 수 있다. 각 정점은 자신이 알고 있는 최댓값을 이웃 정점들에게 브로드캐스트하고, 수신된 메시지 중 더 큰 값이 존재하면 자신의 값을 갱신한 뒤 다시 전파한다. 더 이상 값의 갱신이 발생하지 않아 모든 정점이 종료 투표를 마치면 모든 정점이 전역 최댓값으로 수렴하게 된다.

모든 정점이 침묵에 투표하는 순간, 전역 분산 연산이 수렴을 마친다.

Pregel 프로그래밍: C++ API (THE C++ API)

Pregel의 프로그래밍 인터페이스는 C++ 템플릿 기반의 정점 클래스를 상속받아 사용자 로직을 구현하는 방식으로 설계되었다.

사용자는 Vertex 기본 클래스를 상속받아 3개의 템플릿 인자(정점 값 타입, 에지 값 타입, 메시지 값 타입)를 지정하고, 순수 가상 함수인 Compute() 메서드를 오버라이드한다.

// Figure 3: The Vertex API foundations

template <typename VertexValue,
          typename EdgeValue,
          typename MessageValue>
class Vertex {
  public:
    virtual void Compute(MessageIterator* msgs) = 0;

    const string& vertex_id() const;
    int64 superstep() const;

    const VertexValue& GetValue();
    VertexValue* MutableValue();
    OutEdgeIterator GetOutEdgeIterator();

    void SendMessageTo(const string& dest_vertex,
                       const MessageValue& message);
    void VoteToHalt();
}

정점의 라이프사이클은 각 슈퍼스텝에서 호출되는 Compute() 함수를 중심으로 회전하며, 슈퍼스텝 간 상태 유지는 오직 정점 값과 에지 값에 의해서만 보장된다.

이미지출처 ³

메시지 전달(Message Passing):
- SendMessageTo()를 통해 목적지 정점 ID와 메시지 값을 지정하여 전송한다.
- 송신된 메시지는 다음 슈퍼스텝에서 MessageIterator를 통해 순서와 무관하게 완전히 전달된다.
- 목적지 정점이 인접 이웃일 필요는 없으며, ID만 알고 있다면 그래프 전역의 임의 정점으로 전송할 수 있다.
메시지 결합(Combiners):
- 다수의 정점이 단일 타겟 정점으로 메시지를 보낼 때 네트워크 대역폭과 메모리를 절약하기 위해 메시지를 사전 압축한다.
- 사용자가 결합적(Associative)이고 가환적(Commutative)인 Combine() 함수를 정의하면 워커 노드 로컬에서 메시지들을 미리 병합해 전송량과 버퍼 크기를 줄인다. 논문은 단일 출처 최단 경로(SSSP)에 결합기를 적용해 메시지 트래픽이 4배 이상 줄었다고 보고한다.⁵
전역 집계기(Aggregators):
- 각 정점이 제공한 값들을 전역 수준에서 축약(합산, 최댓값, 최솟값 등)하여 다음 슈퍼스텝의 모든 정점이 참조할 수 있도록 공유한다.
- 전역 루프 제어, 잔차(Residual) 오차 감시, 전체 활성 정점 수 집계 등 알고리즘 제어용으로 활용된다.
그래프 위상 변경(Topology Mutations):
- Compute() 실행 중에 정점이나 에지의 동적 추가/제거를 요청할 수 있다.
- 동일 슈퍼스텝 내 요청 간 충돌을 방지하기 위해 엄격한 정규 순서(에지 삭제 $\rightarrow$ 정점 삭제 $\rightarrow$ 정점 추가 $\rightarrow$ 에지 추가)로 처리하며, 사용자 정의 충돌 해결 핸들러를 통해 결정론적(Deterministic) 결과를 보장한다.⁶
입출력 분리(Input and Output):
- 정점 연산 로직과 입출력 포맷을 분리하기 위해 Reader 및 Writer 추상화를 제공한다.
- 텍스트 파일, Bigtable 뷰, 관계형 DB 등 다양한 데이터 소스로부터 그래프를 병렬 로드하고 저장할 수 있다.

로컬 결합기와 전역 집계기는 분산 통신 병목을 선제적으로 억제하는 핵심 방어선이다.

Pregel 안에서 어떻게 돌아가나? (Implementation)

Pregel의 내부 런타임 아키텍처는 단일 마스터와 수천 대의 워커 머신 간의 정교한 역할 분담으로 구축되어 있다.⁷

이미지출처 ⁸

클러스터 아키텍처와 역할 분담:
- 마스터 노드(Master): 워커들의 멤버십과 상태를 모니터링하고, 그래프 파티션 할당을 총괄하며, 슈퍼스텝의 전역 장벽 동기화를 통제한다.
- 워커 노드(Worker): 할당받은 그래프 파티션을 메모리에 유지하면서 각 정점의 Compute()를 병렬 구동하고, 타 워커들과 직접 비동기 통신을 수행한다.
- 파티셔닝(Partitioning): 기본적으로 정점 ID의 해시 함수(hash(ID) mod N)를 통해 정점들과 나가는 에지를 균등하게 파티션 단위로 분할한다.
전체 실행 라이프사이클:
1. 클러스터 프로세스들이 실행되고 네임 서비스를 통해 마스터 선출이 이루어진다.
2. 마스터가 그래프 크기에 맞추어 파티션 수를 결정하고 워커들에게 파티션을 할당한다.
3. 워커들이 외부 저장소로부터 입력 스플릿을 읽어 정점을 생성하고 적절한 소유 워커로 재배치한다.
4. 마스터의 신호에 맞춰 슈퍼스텝 루프를 반복하며, 각 워커는 활성 정점을 순회하고 메시지를 버퍼링하여 비동기로 전송한다.
5. 모든 정점이 비활성화되고 메시지가 없으면 연산을 종료하고 최종 상태를 디스크에 기록한다.
결함 감내 체계(Fault Tolerance):
- 체크포인팅(Checkpointing): 슈퍼스텝 시작 시 마스터의 지시에 따라 정점 상태, 에지 상태, 전송 메시지를 분산 파일 시스템(GFS)에 주기적으로 저장한다.
- 하트비트 기반 장애 감지: 마스터가 정기적인 핑(Ping) 메시지로 워커 상태를 점검하며, 응답이 없는 워커는 고장 처리된다.
- 전역 롤백 복구: 장애 발생 시 마스터가 잔여 워커들에게 파티션을 재할당하고 가장 최근의 정상 체크포인트 슈퍼스텝으로 롤백하여 연산을 재개한다.
- 제한 복구(Confined Recovery): 나가는 메시지 로그를 활용해 장애가 발생한 파티션만 선별적으로 재연산하여 복구 오버헤드를 줄인다.
워커 및 마스터 세부 구현:
- 워커는 정점 맵, 에지 배열, 수신 메시지 큐, 발신 메시지 버퍼를 순수 메모리 상에서 최적화하여 관리한다.
- 동일 머신 내부 정점 간 메시지는 네트워크 스택을 타지 않고 메모리 큐로 직접 라우팅된다.
- 집계기(Aggregator)는 워커 로컬 집계 후 트리 구조로 부분 집계값을 축약해 마스터로 모은다.

체크포인트 롤백과 메모리 기반 분산 큐잉이 거대 클러스터의 연속성을 담보한다.

Pregel 전체 프로세스 파이프라인 ⁹

실제로 써보자: 예시 알고리즘 (Applications)

정점 중심 추상화는 복잡한 대표 그래프 알고리즘들을 직관적인 수십 줄의 코드로 간결하게 표현해 준다.

페이지랭크(PageRank):
- 각 웹 페이지 정점은 현재 자신의 랭크 값을 나가는 에지의 개수($outdegree$)¹⁰로 나누어 모든 이웃 정점으로 전송한다.
- 슈퍼스텝 1 이상에서는 수신된 랭크 메시지들을 합산하여 댐핑 팩터($0.15 / \text{num_vertices} + 0.85 \times \text{sum}$)를 적용한 새 랭크를 계산한다.
- 통상적으로 수렴 기준치에 도달하거나 사전 지정된 반복 횟수(예: 30회)에 도달하면 투표 후 종료한다.

class PageRankVertex : public Vertex<double, void, double> {
public:
  virtual void Compute(MessageIterator* msgs) {
    if (superstep() >= 1) {
      double sum = 0;
      for (; !msgs->Done(); msgs->Next())
        sum += msgs->Value();
      *MutableValue() = 0.15 / NumVertices() + 0.85 * sum;
    }

    if (superstep() < 30) {
      const int64 n = GetOutEdgeIterator().size();
      SendMessageToAllNeighbors(GetValue() / n);
    } else {
      VoteToHalt();
    }
  }
};

단일 출발지 최단 경로(Single-Source Shortest Path, SSSP):
- 시작 정점은 거리 값을 0으로 초기화하고, 나머지 모든 정점은 무한대($\infty$)로 설정한다.
- 정점은 수신한 메시지 중 최소 거리 값으로 자신의 상태를 갱신하고, 값이 감소했을 때만 해당 거리와 에지 가중치의 합을 인접 정점들로 전파한다.
- 더 이상 최단 거리가 갱신되지 않는 정점들은 자연스럽게 비활성화되어 연산이 종료된다.

class ShortestPathVertex : public Vertex<int, int, int> {
  void Compute(MessageIterator* msgs) {
    int mindist = IsSource(vertex_id()) ? 0 : INF;
    for (; !msgs->Done(); msgs->Next())
      mindist = min(mindist, msgs->Value());

    if (mindist < GetValue()) {
      *MutableValue() = mindist;
      OutEdgeIterator iter = GetOutEdgeIterator();
      for (; !iter.Done(); iter.Next())
        SendMessageTo(iter.Target(), mindist + iter.GetValue());
    }
    VoteToHalt();
  }
};

수학적 수렴 과정이 곧 개별 정점의 종료 투표 루프로 자연스럽게 치환된다.

한계와 트레이드오프 (Limitations and Tradeoffs)

Pregel의 설계 전제와 논문이 직접 밝힌 제약은 다음과 같다.⁵

동기식 장벽의 전제: 슈퍼스텝 사이의 동기화 지연을 감추려면 정점 수가 머신 수보다 훨씬 많은 병렬 여유(Parallel Slack)가 확보되어야 하며, 논문도 이 전제 아래에서만 비동기 시스템과 견줄 만한 성능을 기대할 수 있다고 밝힌다.
기본 파티셔닝의 한계: 기본 hash(ID) mod N 파티셔닝은 그래프의 지역성을 반영하지 못한다. 논문의 실험도 기본 파티셔닝을 사용했고, 토폴로지를 고려한 파티셔닝 함수가 더 나은 성능을 낸다고 명시한다.
복구 비용과 체크포인트 주기: 장애가 나면 가장 최근 체크포인트로 롤백하고 누락된 슈퍼스텝을 재계산해야 하므로, 체크포인트 저장 비용과 복구 비용을 평균 고장 시간(MTTF) 모델로 절충해야 한다. 파티션 단위 선택 복구(Confined Recovery)는 논문 시점에 개발 중이었고 결정론적 알고리즘을 요구한다.
결합기와 집계기의 조건: 결합기는 교환·결합 법칙을 만족하는 연산에만 쓸 수 있고 기본 활성화되지 않으며, 어떤 메시지가 어떤 조합으로 결합되는지에 대한 보장이 없다.
실험 조건: 논문은 300대의 멀티코어 상용 PC에서 단순한 병렬 SSSP를 측정했다. 10억 정점 이진 트리에서 워커를 50대에서 800대로 늘리면 174초에서 17.3초로 줄었고(약 10배), 그래프가 10억 정점에서 500억 정점으로 커지면 17.3초에서 702초로 늘었다. 평균 outdegree 127.1의 로그노말 랜덤 그래프(최대 10억 정점, 1,270억 에지)는 10분 남짓 걸렸다. 이 수치들은 체크포인팅을 끄고 기본 해시 파티셔닝과 최적화되지 않은 알고리즘으로 측정한 값이며, 논문 스스로 최상의 런타임으로 해석해서는 안 된다고 밝힌다.

핵심 요약 및 시사점

정점 중심의 직관적 프로그래밍 패러다임: 개발자는 복잡한 분산 스케줄링이나 레이스 컨디션을 신경 쓰지 않고 “개별 정점 하나의 관점”에서 연산 로직만 작성하면 되며, 분산 처리의 세부는 프레임워크가 담당한다.
BSP 기반의 동기화와 높은 확장성: 슈퍼스텝 단위의 전역 장벽 동기화를 적용해 데드락 위험을 원천 제거하고, 메모리 기반 로컬 처리와 결합기(Combiner)를 통해 네트워크 병목을 최소화했다.
투명한 결함 감내 체계: 수천 대의 상용 서버 클러스터 환경을 전제로 설계되어, 체크포인팅과 롤백 복구를 런타임 차원에서 자동 처리함으로써 대규모 분산 파이프라인의 신뢰성을 확보했다.
현대 분산 시스템 및 AI 프레임워크로의 영향: Pregel의 디자인은 아파치 지라프(Giraph), 그래프X(GraphX) 등 오픈소스 생태계로 이어졌으며, 순환형 단계 전파 구조는 스스로 Pregel에서 영감을 받았다고 밝힌 LangGraph 같은 멀티 에이전트 오케스트레이션 프레임워크에서도 다시 등장한다.¹

대규모 연결 데이터의 잠재력은 정점 중심의 분산 추상화 위에서 비로소 현실화되었다.

References

KakaoTalk Twitter Facebook LinkedIn

[논문 리뷰] Pregel: A System for Large-Scale Graph Processing

Pregel: 대규모 그래프를 쉽게 처리하는 구글의 똑똑한 시스템

왜 Pregel이 필요했을까? (Introduction)

Pregel은 어떻게 계산하나? (Model of Computation)

Pregel 프로그래밍: C++ API (THE C++ API)

Pregel 안에서 어떻게 돌아가나? (Implementation)

실제로 써보자: 예시 알고리즘 (Applications)

한계와 트레이드오프 (Limitations and Tradeoffs)

핵심 요약 및 시사점

References

공유하기

댓글남기기

참고

엔터프라이즈 AI 플랫폼 설계 (1): 프라이빗 인프라 격리와 초거대 분산 서빙 토폴로지

엔터프라이즈 AI 플랫폼 설계 (2): 무중단 장애 격리와 프로덕션 운영화(LLMOps)

엔터프라이즈 바이브 코딩의 이면: MCP 컨텍스트 폭발 제어와 멀티 에이전트 거버넌스

Claude Code 소스맵 유출 완전 해부: 왜 프로덕션 에이전트는 상태 그래프 대신 결정론적 하네스(query.ts)를 택했는가