Pregel-A System for Large-Scale Graph Processing(2010)

pregel.pptx

0.58MB

그래프 프로세싱 하는 것에 대한 문제점으로는 다음과 같이 두 개가 있다.

1.Poor locality of memory access

 - Distributed memory requires that the edges and vertices of a graph be partitioned among processors.

2.Very little work per vertex

이는 그래프가 메모리에 접근하는 것이 좋지 않으며, vertex당 처리하는 양이 적다는 것을 뜻한다.(?)

 

그래서 이를 해결하기 위한 해결책이 다음과 같이 4가지가 있다.

1.Crafting a custom distributed infrastructure
⇒ typically requiring a substantial implementation effort

2.Relying on an existing distributed computing platform
⇒ this can lead to suboptimal performance and usability issues.

3.Using a single-computer graph algorithm library
⇒ limiting the scale of problems

4.Using an existing parallel graph system
⇒ do not address fault tolerance or other issues that are important for very large-scale distributed systems.

 

화살표에 써 있는 것과 같이 확실한 해결책이라고 할 수 없다.

그래서 Pregel이라는 알고리즘이 나왔다.

여기서 Pregel이란, 

•distributed programming framework

•scalable and fault-tolerant platform with an API

•sufficiently flexible to express arbitrary graph algorithms

이다. 다시 말해 분산 프로그래밍 프레임워크로, 확장성과 내고장성이 뛰어난 API이며 어떤 그래프 알고리즘에도 적용가능한 유연하다.

 

Pregel의 개략도는 다음과 같다.

Input과 Output은 그래프형태이며, superstep으로 반복하고 각 단계는 함수로 구성되어 있으며 메세지로 주고받는다.

 

Pregel은 vertex와 edge로 구성되어 있다.

vertex는 문자열 고유 식별자와 사용자 정의 값으로 이루어져 있고, 

edge는 source vertex, target vertex, user defined value로 구성되어 있으며, 사용자 정의 값은 수정이 가능하다.

또한 edge는 first class가 아니기 때문에 계산과정에는 포함되지 않는다.

 

superstep 0에서는 모든 vertex를 활동상태로 바꾼다. 이 때 모든 vertex가 활동상태가 되면 계산에 참여하게 된다.

계산이 끝나면 vertex는 스스로 중단한다.(inactive 상태로 바꾼다.)

모든 vertex가 inactive상태가 되고 더이상 주고받을 메세지가 없을 때 알고리즘은 종료된다.

 

(maximum value를 전달하는 Pregel 예시)

 

Pregel library는 그래프를 파티션으로 나누어 관리하며, 각 파티션은 vertex와 그 vertex의 outgoing edge로 이루어져 있다.

파티션은 오로지 vertexID에만 의존하며 이는 vertex가 어느 파티션에 위치하는지 알 수 있음을 뜻한다.

기본 파티셔닝 함수는 hash(ID) mod N(파티션 개수)이며 사용자가 변경 가능하다.

 

Pregel 프로그램은 몇 가지 단계로 이루어진다.

첫 번째, 사용자 프로그램의 많은 복사본이 클러스터에서 실행될 때 복사본 중 하나를 마스터로 지정한다.

두 번째, 마스터는 파티션의 개수를 결정하고 워커머신에게 하나 이상의 파티션을 할당한다.

세 번째, 마스터는 각각의 워커에게 사용자의 입력값을 할당한다. 이 때 워커는 모든 vertex를 로드하고 활동상태로 표시한다.

네 번째, 마스터는 각각의 워커에게 superstep을 수행하라고 지시한다. 

  각각의 워커들은 활동상태의 vertex를 통해 계산을 수행하고 반복한다.

  메세지는 비동기로 전달되지만, superstep이 끝나기 전에 전달이 완료된다.

  이 단계는 vertex가 활동상태이거나 메세지를 전달받는 한 계속된다.

다섯 번째, 모든 계산이 중단된 후에, 마스터는 각각의 워커들에게 그래프를 저장하라고 지시할 수 있다.

Pregel architecture의 그림을 보면 다음과 같다.

먼저 job을 전달받으면 마스터는 워커들에게 일을 전달한다.

워커들은 전달받게 되면 파티션된 그래프를 로딩한다.

후에 superstep을 수행하고 워커들의 동기화가 다 끝나면 그 결과를 저장한다.

 

Pregel의 내고장성은 checkpoint를 통해 달성된다.

마스터는 주기적으로 워커들에게 현재 상태를 저장하라고 지시하는데 저장되는 값에는 vertex value와 edge value 그리고 수신메세지가 포함된다.

워커들의 고장은 마스터가 주기적으로 보내는 ping메세지에 의해 판별되는데, 워커가 마스터가 보낸 ping메세지를 되돌려보내지 못한다면 마스터는 워커 프로세스를 실패처리한다.

하지만 네트워크 문제 등 다른 문제로 인해 되돌려보내지 못하는 경우도 발생하기 때문에, 한 번의 과정으로 실패처리를 하지 않고, 지정한 횟수를 넘어가면 실패처리한다.

이렇게 하나의 워커가 실패하게 되면 그 과정을 잃기 때문에 마스터는 다시 회복과정을 거치게 된다.

마스터는 먼저 현재 수행가능한 워커들에게 그래프 파티션을 재할당한다.

그리고 가장 최신의 checkpoint를 사용하여 파티션 상태를 다시 재로드한다.

 

워커들은 메모리 위에서 그래프를 유지하게 되며, 계산이 끝난 후 메세지를 보내야 될 때, 메세지를 보낼 vertex가 있는 곳이 원격 컴퓨터인지 로컬 컴퓨터인지를 판별한다. 

만약 원격 컴퓨터라면 메세지를 보내기 위해서 버퍼링을 수행하며, 로컬컴퓨터라면 바로 배치가 가능하기 때문에 최적화가 가능하다.

마스터는 워커들의 활동을 조정하는 책임이 있다. 그래서 현재 이용가능한 워커들의 목록을 유지하는데, 목록에 저장되어 있는 값은 다음과 같다.

1. 워커들의 고유식별자

2. 주소 정보(ip)

3. 그래프에서 할당된 부분

 

또한 마스터는 정보를 보여주기 위해 HTTP 서버를 실행한다.

 

이 논문에서는 single-source shortest paths에 대한 세 가지 실험을 하였다.

300개의 멀티코어 컴퓨터를 클러스터하여 사용하였으며, 이진트리와 로그정규랜덤그래프를 사용하여 런타임을 보고하였다.

(측정시간에는 클러스터 초기화한 시간, 그래프 생성시간, 결과확인 시간은 포함되지 않았다.)

 

먼저 워커들의 수가 pregel scales에 미치는 영향을 알아보았다.

여기서 10억개의 vertex를 사용하였으며, 워커는 50개에서 800개까지 사용하였다.

다음 그래프를 보면 50개의 워커에서는 174초가 걸렸으며, 800개의 워커에서는 17.3초가 걸렸다.

이는 워커의 수가 16배 증가했을 때 약 10배 정도 빨라짐을 확인하였다.

여기서 워커의 수가 증가함에 따라 비례하게 빨라지지 않는 이유는 워커의 수가 늘어남에 따라 전달해야 하는 메세지의 수도 늘어나기 때문에 전달 시간이 늘어남을 이유로 들 수 있다.

 

다음은 graph size가 미치는 영향이다. 여기서 10억개에서 500억개의 vertex를 사용하였으며, 워커는 800개로 고정하여 테스트하였다.

다음 그래프를 보면 graph size가 증가함에 따라 런타임도 선형적으로 증가함을 알 수 있다.

로그 형태가 아닌 선형적으로 증가한다는 것은 좋은 알고리즘이란 것을 보여준다.

 

다음은 로그정규랜덤그래프를 통한 실험 결과이다. 

여기서 이진트리가 아닌 로그정규랜덤그래프를 사용한 이유는 이진트리가 모든 실제상황에 대해서 설명할 수 없기 때문이다. 그래서 outgoing edge의 수가 로그정규분포를 따라 생성하였으며, 여기서 사용한 그래프는 평균이 4이고 표준편차가 1.3인 그래프이다.

1000만개에서 10억개의 vertex를 사용하여 테스트 하였으며, 워커의 수는 800개로 고정하였다.

결과는 다음 그래프와 같이 나왔으며, 가장 큰 그래프에서 shortest path를 찾는 시간은 10분이 조금 넘게 걸렸다.

 

Pregel은 성능과 확장성, 내고장성이 이미 10억개의 vertex를 통해 충분히 만족함을 확인하였으며 그들은 이 프로그래밍 인터페이스가 추가진화에 탄력적으로 사용할 수 있을 만큼 충분히 추상적이고 유연하다고 말한다.