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

2022-09-20 9 분 소요

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

논문 출처 pdf : pregel paper

1. Introduction

자주 적용되는 그래프 알고리즘에는 최단 경로 계산, 다양한 종류의 클러스터링, 페이지 순위 테마의 변형들이 있다.
대규모 그래프(large graph)를 효과적으로 처리하는 데는 어려움이 있다.
- 그래프 알고리즘들은 종종 메모리 액세스의 빈약한 지역성(locality), 정점(vertex)당 매우 적은 처리량(work), 실행 과정에서 병렬화의 정도가 변하는 것들이 있다.
- 많은 머신들의 분포는 지역성 문제를 악화시키고, 계산(computation) 중에 머신이 고장날 확률을 높인다.

대규모 그래프를 처리하기 위해 알고리즘을 구현하는 것은 다음 중 하나를 선택하는 것을 의미한다.

맞춤형 분산 인프라를 만드는 것은 일반적으로 새로운 알고리즘 또는 그래프 표현마다 반복되어야 하는 상당한 구현(implementation) 노력이 필요하다.
그래프 처리에 적합하지 않은 (예를 들어 맵리듀스같은) 기존 분산 컴퓨팅 플랫폼에 의존하는 경우
- 이러한 기능은 일반적으로 메시지 전달(message passing) 모델에 더 잘 맞는 그래프 알고리즘에는 적합하지 않다.
기존 병렬 그래프 시스템(BGL, CGM 그래프)을 사용하는 경우. 하지만 이는 장애 허용(fault tolerance) 또는 대규모 분산 시스템에서는 다루지 않는다.

위 옵션들은 모두 대규모 그래프 처리 목적에 맞지 않는다.
저자들은 대규모 그래프의 분산 처리를 해결하기 위해, 확장 가능하고(scalable) 장애 허용(fault tolerance) 플랫폼인 Pregel을 구축했다.

프리겔(Pregel) 프로그램의 고급 구성은 BSP(Bulk Synchronous Parallel) 모델에서 영감을 받았다.

이미지출처 ¹

프리겔 연산은 슈퍼스텝(superstep)이라고 불리는 일련의 반복으로 구성된다.
슈퍼스텝동안 프레임워크는 각 정점(vertex)에 대한 사용자 정의 함수를 개념적으로(conceptually) 병렬로 호출한다.
함수는 싱글 정점 $V$와 싱글 슈퍼스텝 $S$에서 동작을 지정한다.
슈퍼스텝 $S-1$에서 $V$로 전송된 메시지를 읽고, 슈퍼스텝 $S+1$에서 수신될 다른 정점으로 메시지를 전송하며, $V$의 상태와 해당 발신 에지를 수정할 수 있다.
정점 중심 접근법은 유저가 각 항목을 독립적으로 처리하면서 로컬 작업에 집중하고 시스템이 이러한 작업을 구성하여 계산을 대규모 데이터 셋으로 끌어올린다는 점에서 맵리듀스(Mapreduce)를 연상시킨다.
이 모델의 공시성(synchronicity)은 알고리즘을 구현할 때 프로그램 의미론에 대한 추론을 용이하게 하며, 프리겔이 본질적으로 비동기 시스템에서 일반적인 교착 상태(deadlock) 및 데이터 레이스(race)에서 자유롭도록 한다.

이미지출처 ²

2. Model of computation

프리겔 계산에 대한 입력(input)은 각 정점이 문자열 정점 id(식별자)에 의해 고유하게 식별되는 방향 그래프(directed graph)이다.
각 정점(vertex)은 수정 가능한 사용자 정의 값과 연결된다.
방향 에지(directed edge)는 소스 정점과 연관되며, 각 에지는 수정 가능한 사용자 정의 값과 목적지 정점 id로 구성된다.
일반적인 프리겔 계산은 그래프를 초기화할 때 입력과 알고리즘이 종료될 때까지 전역 동기화 포인트(global synchronization point)로 분리된 일련의 슈퍼스텝과 출력으로 구성된다.
각 슈퍼스텝 내에서 정점은 병렬로 계산되며, 각 정점은 주어진 알고리즘의 논리를 표현하는 동일한 사용자 정의 함수를 실행한다.
정점(vertex)은 상태(state)나 나가는(outgoing) 에지의 상태를 수정하거나, 이전 슈퍼스텝에서 보낸 메시지를 수신하거나, 다른 정점으로 메시지를 전송하거나, 그래프의 토폴로지(topology)을 변형시킬 수 있다.
- 토폴로지(topology) : 컴퓨터 네트워크의 요소들(링크, 노드 등)을 물리적으로 연결해 놓은 것 또는 그 연결 방식을 말한다. ³
에지(edge)는 일급 객체(first-class citizen)가 아니기 때문에, 이 모델에서 계산 과정에는 없다.

알고리즘 종료는 모든 정점이 vote to halt 일 때이다.
슈퍼스텝 0에서, 모든 정점은 active 상태이다.
정점은 스스로 계산을 중단하고 비활성화된다.
프리겔의 출력(output)은 정점에 의해 명시적으로 출력되는 값의 집합이다.

그래프 마이닝 알고리즘은 단순히 그래프에서 마이닝된 집계 통계를 출력할 수 있다.
이러한 개념을 Fig 2에서 보여주고 있다.
각 정점이 값을 포함하는 강하게 연결된 그래프가 주어지면, 가장 큰 값을 모든 정점으로 전파한다.
각 슈퍼스텝에서, 메시지로부터 더 큰 값을 학습한 정점은 그것을 모든 이웃에게 보낸다.
슈퍼스텝에서 더 이상 정점이 바뀌지 않으면 알고리즘은 종료된다.

3. THE C++ API

프리겔 프로그램을 작성하려면 미리 정해진 Vertex 클래스를 하위 클래스(subclass)해야 한다. (Fig 3)

// 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();
}

template 인수는 정점, 에지 및 메시지와 관련된 3가지 값 유형을 정의한다.
- 각 정점(vertex)에는 규정된 유형의 값이 있다.
사용자는 모든 슈퍼스텝의 각 active 정점에서 실행되는 가상 Compute() 메서드를 재정의(override)한다.
미리 정의된 Vertex 메서드를 사용하면 Compute()이 현재 정점과 에지에 대한 정보를 쿼리하고 다른 정점으로 메시지를 보낼 수 있다.
Compute()는 GetValue()를 통해 정점과 관련된 값을 검사하거나, MutableValue()를 통해 수정할 수 있다.
GetOutEdgeIterator()에서 제공하는 방법을 사용하여 Out-Edge 값을 검사 및 수정할 수 있다.

이미지출처 ²

정점과 에지와 관련된 값은 슈퍼스텝에서 유지되는 유일한 정점 단위 상태이다.
프레임워크에서 관리하는 그래프 상태를 정점 또는 에지당 싱글 값으로 제한하면 메인 계산 주기, 그래프 분포 및 장애 복구가 단순해진다.

3.1 Message Passing

정점들은 메시지 값과 목적지 정점의 이름으로 구성된 메시지를 전송함으로써 서로 직접 통신한다(communicate).
- 메시지 값의 유형은 사용자 Vertex 클래스의 template 매개 변수로 지정한다.
슈퍼스텝 $S$에서 정점 $V$로 전송된 모든 메시지는 슈퍼스텝 $S+1$에서 $V$의 Compute() 메서드가 호출될 때 이터레이터(iterator)를 통해 사용할 수 있다.
- 이터레이터(iterator)에 메시지 순서가 보장되지는 않지만 메시지가 전달되고 중복되지 않도록 보장한다.

그러나 dest_vertex는 $V$의 이웃이 필요없을 수 있다.
- 정점은 일찍 메시지를 받은 이웃이 아닌 id를 배우거나, 정점 id를 암묵적으로 알 수 있다.

3.2 Combiners

메시지를 보내는 것은, 특히 다른 머신에 있는 정점에, 약간의 오버헤드를 발생시킨다.
사용자의 도움을 받아 이를 줄일 수 있는 경우도 있다.
예를 들어 시스템은 정점 $V$를 위한 여러 메시지를 합계(sum)를 포함하는 싱글 메시지로 결합하여(combine) 전송 및 버퍼링해야 하는 메시지의 수를 줄일 수 있다.
이 최적화를 활성화하기 위해 사용자는 컴바이너 클래스를 subclass하여 가상 Combine() 메서드를 재정의한다.

3.3 Aggregators

프리겔 애그리게이터(aggregator)는 글로벌 통신(communication), 모니터링 및 데이터를 위한 메커니즘이다.
각 정점은 슈퍼스텝 $S$에서 애그리게이터에 값을 제공할 수 있으며, 시스템은 이러한 값을 reduction 연산자를 사용하여 결합(combine)하고, 결과 값은 슈퍼스텝 $S+1$에서 모든 정점에 사용할 수 있게 된다.
프리겔은 min, max, sum 연산자와 같은 다수의 미리 정의된 애그리게이터를 포함한다.
애그리게이터는 통계(statistic)에도 사용된다.

또한 애그리게이터는 전역 조정(coordination)에도 사용될 수 있다.
- 예를 들어, Compute()의 한 branch는 애그리게이터가 모든 정점이 어떤 조건을 만족한다고 결정할 때까지 슈퍼스텝에 대해 실행될 수 있으며, 다른 branch는 종료될 때까지 실행될 수 있다.

3.4 Topology Mutations

일부 그래프 알고리즘은 그래프의 토폴로지를 변경해야 한다.
- 예를 들어 클러스터링(clustering) 알고리즘은 각 클러스터를 싱글 정점으로 대체할 수 있다.
사용자의 Compute() 기능이 메시지를 보낼 수 있는 것처럼 정점이나 에지를 추가하거나 제거하는 요청도 할 수 있다.
이 과정에서 여러 정점들은 동일한 슈퍼스텝에서 충돌할 수 있다.

따라서 결정론(determinism)을 달성하기 위해 부분 순서(partial ordering)와 핸들러(handler)라는 2가지 메커니즘을 사용한다.
- 결정론(determinism) : 다른 시점에 다른 노드에서 동일한 작업을 수행해도 동일한 결과를 생성해야 한다. ⁴
메시지와 마찬가지로, 뮤테이션(mutation)은 요청(request)이 발행된 후 슈퍼스텝에서 효과적이다.
그 안에서 정점을 제거하면 암묵적으로 모든 바깥쪽(out) 에지가 제거되기 때문에, 정점 제거 전에 에지 제거가 먼저 수행된다.
덧셈은 에지 덧셈 전에 정점 덧셈과 함께 제거가 되며, 모든 뮤테이션은 Compute() 호출에 선행한다.

부분 순서 : 에지 제거 -> 정점 제거 -> 정점 덧셈 -> 에지 덧셈

이 부분 순서(partial ordering)는 대부분의 충돌에 대해 결정론적 결과를 산출한다.
- 나머지 충돌은 사용자 정의 핸들러(handler)로 해결된다.

같은 슈퍼스텝에서 같은 정점을 만들기 위한 요청이 여러 개 있는 경우, 기본적으로 시스템은 임의로 하나를 선택하지만, 특별한 요구가 있는 사용자는 Vertex 하위클래스에서 적절한 핸들러(handler) 메서드를 정의하여 더 나은 충돌 해결 정책을 지정할 수 있다.
여러 정점 제거 요청 또는 여러 에지 추가 또는 제거 요청에 의해 발생한 충돌을 해결하기 위해 동일한 핸들러 메커니즘이 사용된다.

조정(coordination) 메커니즘은 lazy하다.
- 글로벌 뮤테이션은 적용되는 시점까지 조정이 필요하지 않다.
이러한 설계 선택은 스트림 처리(stream processing) 처리를 용이하게 한다.

3.5 Input and output

그래프에는 텍스트 파일, 관계형 데이터베이스의 정점 집합 또는 빅테이블의 행과 같이 가능한 파일 형식이 많이 있다.
파일 형식의 특정 선택이 강요되는 것을 피하기 위해 프리겔은 입력 파일을 그래프로 해석하는 태스크를 그래프 계산 작업에서 분리한다.
- Reader와 Writer 하위클래스를 활용할 수 있다.
마찬가지로 임의의 형식으로 생성될 수 있고 주어진 애플리케이션에 가장 적합한 형태로 저장될 수 있다.

4. Implementation

각 클러스터는 랙(rack) 내 대역폭이 높은 랙으로 구성된 수천 대의 범용 PC로 구성된다.
클러스터는 상호 연결되어 있지만 지리적으로 분산되어 있다.
애플리케이션은 리소스 할당을 최적화하기 위해 잡을 스케줄링하는 클러스터 관리 시스템에서 실행되며, 때로는 인스턴스를 죽이거나 다른 시스템으로 이동한다.

4.1 Basic architecture

프리겔 라이브러리는 그래프를 파티션으로 나누는데, 파티션은 정점 집합과 모든 정점의 나가는(outgoing) 에지로 구성되어 있다.
정점을 파티션에 할당하는 것은 정점 ID에만 의존하는데, 이는 정점이 다른 머신에 의해 소유되거나 정점이 아직 존재하지 않더라도 어떤 파티션에 속하는지 알 수 있음을 의미한다.
기본 파티셔닝 함수는 hash(ID) mod N(number of partition)이다.

이미지출처 ⁵

장애가 없는 경우, 프리겔 실행은 다음 과정과 같다.

사용자 프로그램의 많은 복제본이 시스템 클러스터에서 실행되기 시작한다.
- 이 복제본 중 하나가 마스터(master) 역할을 한다. 그래프의 어떤 부분도 할당되지 않았지만 워커(worker) 활동(activity)을 조정하는 역할을 한다.
- 워커는 클러스터 관리 시스템의 네임 서비스를 사용하여 마스터의 위치를 검색하고 등록(registration) 메시지를 마스터에게 보낸다.
마스터는 그래프에 포함할 파티션 수를 결정하고, 각 워커에 하나 이상의 파티션을 할당한다.
- 넘버는 사용자에 의해 제어될 수 있다.
- 워커당 파티션이 2개 이상 있으면 파티션 간의 병렬화(parallelism)와 로드 밸런싱(load balancing)이 개선되며 일반적으로 성능이 향상된다.
- 각 워커는 그래프의 섹션 상태를 유지하고, 정점에서 사용자의 Compute() 메서드를 실행하고, 다른 워커와 주고받는 메시지를 관리할 책임이 있다.
- 각 워커에게는 모든 워커에 대한 전체 할당 세트가 부여된다.
마스터는 사용자 입력의 일부를 각 워커에게 할당한다.
- 입력은 레코드 집합으로 처리되며, 각 레코드 집합에는 임의의 수의 정점과 에지가 포함된다.
마스터는 각 워커에게 슈퍼스텝을 수행하도록 지시한다.
- 워커는 각 파티션에 대해 하나의 스레드를 사용하여 활성 정점을 순환한다(loop).
- 워커는 각 활성 정점에 대해 Compute() 메서드를 호출하여 이전 슈퍼스텝에서 보낸 메시지를 전달한다.
- 메시지는 계산(computation)과 통신(communication) 및 배치(batching)의 중첩(overlapping)을 가능하게 하기 위해 비동기적으로 전송되지만, 슈퍼스텝이 끝나기 전에 전달된다.
- 워커가 완료되면 마스터에 응답하여 다음 슈퍼스텝에서 활성화될 정점의 수를 마스터에 알린다.
- 이 단계는 정점이 활성 상태이거나 메시지가 전송 중인 동안 반복된다.
계산이 중단된 후 마스터는 각 워커에게 그래프의 해당 부분을 저장하도록 지시한다.

4.2 Fault tolerance

장애 허용(fault tolerance)은 체크포인트(checkpoint)를 통해 달성된다.
슈퍼스텝이 시작될 때 마스터는 워커에게 정점값, 에지 값 및 수신 메시지를 포함한 파티션의 상태를 영구 저장소에 저장하도록 지시한다.
- 워커 장애는 마스터가 워커에게 정기적으로 발행하는 핑(ping) 메시지를 보냄으로써 감지한다.
- 지정된 간격동안 워커가 핑 메시지를 수신하지 않으면 워커 프로세스가 종료된다.
마스터가 워커로부터 회신을 받지 못할 경우, 마스터는 해당 워커 프로세스를 실패(fail)로 표시한다.
하나 이상의 워커가 실패하면 해당 워커에게 할당된 파티션의 현재 상태가 손실된다.
따라서 마스터는 그래프 파티션을 현재 사용 가능한 워커 집합에 다시 할당하고, 워커는 슈퍼스텝 $S$의 시작 시 가장 최근에 사용 가능한 체크포인트에서 파티션 상태를 다시 로드한다.
- 이때, MTTF(mean time to failure) 모델을 기반으로 체크포인트 빈도를 선택하여 체크포인트 비용과 예상 복구 비용의 균형을 맞춘다.

기본 체크포인트 외에도 워커는 그래프 로드(load) 및 슈퍼스텝 중에 할당된 파티션에서 보내는 메시지를 기록한다.
그런 다음 복구(recovery)는 체크포인트에서 복구된 손실된 파티션으로 제한된다.(confine)
시스템은 정상 파티션에서 기록된 메시지와 복구 파티션에서 다시 계산된 메시지를 사용하여 누락된 슈퍼스텝을 $S0$까지 재계산한다.
- 이 접근 방식은 손실된 파티션만 재계산하여 복구 중에 컴퓨팅 리소스를 절약하고 각 작업자가 복구하는 파티션 수가 줄어들기 때문에 복구 대기 시간을 단축할 수 있다.
- 보내는 메시지를 저장하면 오버헤드가 증가하지만 일반적인 시스템은 I/O가 병목 현상이 되지 않도록 적절한 디스크 대역폭을 갖는다.
제한된(confined) 복구는 원래 실행에서 저장된 메시지와 복구에서 새 메시지를 혼합하여 발생하는 불일치를 방지하기 위해 사용자 알고리즘이 결정론적(determinism)이어야 한다.

4.3 Worker implementation

워커 머신은 메모리에 있는 그래프 부분의 상태를 유지한다.
- 개념적으로 이것은 정점 ID부터 각 정점의 상태, 나가는 에지의 목록, 들어오는 메시지들을 포함하는 큐, 정점이 활성인지 지정하는 플래그까지의 맵(map)으로 생각할 수 있다.
워커가 슈퍼스텝을 수행할 때 모든 정점을 루프하고 Compute()를 호출하여 현재 값을 전달하고, 수신 메시지에 이터레이터를 전달하며, 송신 에지에 이터레이터를 전달한다.

Compute() 메서드가 다른 정점으로 메시지 전송을 요청하면 워커 프로세스는 먼저 목적지 정점이 원격 워커 머신에 의해 소유되는지 아니면 보낸 사람을 소유하는 동일한 워커에 의해 소유되는지 여부를 결정한다.
- 원격일 경우, 메시지가 목적지 워커에 전달하기 위해 버퍼링된다.

4.4 Master implementation

마스터는 주로 워커의 활동을 조정하는 역할을 한다.
각 워커는 등록 시 고유 id가 할당된다.
마스터는 워커의 고유 id, 주소 지정 정보 및 할당된 그래프 부분을 포함하여 현재 살아있는(alive) 것으로 알려진 모든 워커의 목록을 유지한다.
마스터의 데이터 구조의 크기는 정점이나 에지의 수가 아니라 파티션 수에 비례하므로, 싱글 마스터가 대규모 그래프에 대한 계산을 조정할 수 있다.
입력, 출력, 계산, 체크포인트에서 저장 및 재개(resume)를 포함한 대부분의 마스터 작업(operation)은 장벽(barrier)에서 종료된다.
장벽 동기화가 성공하면 마스터는 다음 단계로 진행한다.
마스터는 또한 그래프의 전체 크기, 진출차수(out-degree) ⁶ 의 분포에 대한 히스토그램, 활성 정점의 수, 최근 슈퍼스텝의 타이밍(timing)과 메시지 트래픽, 모든 사용자 정의 애그리게이터의 값과 같은 계산 진행률과 그래프 상태에 대한 통계를 유지한다.
사용자 모니터링을 사용 기능으로 설정하기 위해 마스터는 이 정보를 표시하는 HTTP 서버를 실행한다.

4.5 Aggregators

이미지출처 ⁷

애그리게이터(aggregator)는 사용자가 제공하는 값(value) 집합에 집계(aggregation) 함수를 적용하여 싱글 전역 값을 계산한다.
각 워커는 타입 이름 및 인스턴스 이름으로 식별되는 애그리게이터 인스턴스 컬렉션을 유지 관리한다.
워커가 그래프의 어떤 파티션에 대해 슈퍼스텝을 실행할 때 워커는 애그리게이터 인스턴스에 제공된 모든 값을 싱글 로컬 값, 즉 파티션에 있는 워커의 모든 정점에 걸쳐 부분적으로 리듀스되는 애그리게이터로 결합한다.
슈퍼스텝이 끝날 때 워커는 트리를 형성하여 부분적으로 리듀스된 애그리게이터를 전역 값으로 리듀스하고 마스터에게 전달한다.
마스터는 다음 슈퍼스텝이 시작될 때 모든 워커에게 전역 값을 보낸다.

Pregel 전체 프로세스 ⁸

5. Applications

이번 내용은 실제 문제를 해결하기 위해 프리겔 사용자가 개발한 단순한 버전인 Page Rank, Shortest Paths, Bipartite Matching, Semi-Clustering 알고리즘 예시를 제시한다.

5.1 PageRank

// Figure 4. PageRank implemented in Pregel.

// PageRankVertext 클래스는 Vertex에서 상속된다.
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();
        }
      }
  };

5.2 Shortest Paths

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() = mindst;
        OutEdgeIterator iter = GetOutEdgeIterator();
        for (; !iter.Done(); iter.Next())
          SendMessageTo(iter.Target(),
                        mindist + iter.GetValue());
      }
      VoteToHalt();
    }
  }

단일 소스 최단 경로(SSSP, single-source shortest paths) 알고리즘에서 각 정점과 관련된 값이 INF로 초기화된다고 가정한다.
각 슈퍼스텝에서 각 정점은 먼저 이웃으로부터의 메시지로 소스 정점에서 업데이트된 최소 거리를 수신한다.
이러한 업데이트의 최소값이 정점과 현재 연결된 값보다 작으면 이 정점은 값을 업데이트하고, 새로 발견된 최소 거리에 추가된 각 나가는(outgoing) 에지의 가중치로 구성된 잠재적 업데이트를 이웃에게 보낸다.
이러한 이웃들은 차례로 값을 업데이트하고 메시지를 보내 그래프를 통해 업데이트의 물결을 일으킨다.
알고리즘은 더 이상 업데이트가 없을 때 종료되며, 그 후 각 정점과 관련된 값은 소스 정점에서 해당 정점까지의 최소 거리를 나타낸다.

6. Experiments

저자들은 300개의 멀티코어 PC 클러스터 상에서 SSSP 구현을 통해 다양한 실험을 했다.
그들은 모든 에지의 가중치가 암시적으로 1로 설정된 다양한 그래프 크기를 사용하여 이진 트리(scaling 특성을 보기 위해)와 로그 정규 랜덤 그래프(보다 현실적인 설정에서 성능을 보기 위해)에 대한 런타임(runtime)을 보고한다.
모든 실험은 비교적 짧은 시간에 실행될 수 있기 때문에 실패 확률이 낮았고 체크포인트를 사용할 수 없었다.

Fig 7은 워커 태스크에 따라 프리겔이 어떻게 확장되는지를 나타내는 것으로, 프리겔 워커의 수가 50에서 800까지 다양할 때 10억개의 정점을 가진 이진 트리의 최단 경로 런타임을 보여준다.

Fig 8은 그래프 크기에 따라 프리겔이 어떻게 확장되는지 보여주기 위한 것으로, 크기가 10억에서 500억 개의 정점까지 다양한 이진 트리에 대한 최단 경로 런타임을 제시한다.

저자들은 또한 진출차수의 로그 정규 분포를 사용하는 랜덤 그래프를 사용하여 실험을 했다.
- $p(d)=\frac{1}{\sqrt{2\pi}\sigma d}e^{-(ln d-\mu)^2/2\sigma^2}$
  - $\mu = 4$
  - $\sigma = 1.3$
  - mean outdegree = $127.1$
이러한 분포는 웹 그래프 또는 소셜 네트워크와 같은 많은 실제 대규모 그래프와 유사하며, 대부분의 정점은 상대적으로 작은 정도(degree)를 가지지만 일부 이상치(outlier)는 훨씬 크다.

Fig 9는 크기가 1,000만 개에서 10억 개의 정점까지 다양한 그래프의 최단 경로 런타임을 보여준다.
가장 큰 그래프의 최단 경로를 실행하는 데 10분이 조금 넘게 걸렸다.

References

KakaoTalk Twitter Facebook LinkedIn

poeun 🔅

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

1. Introduction

2. Model of computation

3. THE C++ API

3.1 Message Passing

3.2 Combiners

3.3 Aggregators

3.4 Topology Mutations

3.5 Input and output

4. Implementation

4.1 Basic architecture

4.2 Fault tolerance

4.3 Worker implementation

4.4 Master implementation

4.5 Aggregators

5. Applications

5.1 PageRank

5.2 Shortest Paths

6. Experiments

References

공유하기

댓글남기기

참고

MySQL 문법 및 예제 정리 - LIKE, REGEXP, REGEXP_LIKE

MySQL 문법 및 예제 정리 - PRECEDING, FOLLOWING, CURRENT ROW

MySQL 문법 및 예제 정리 - 날짜, WITH

MySQL 문법 및 예제 정리 - IF, IFNULL, CASE, COALESCE