대용량 그래프 처리 시스템, Pregel

 

그래프로 정말 다양한 항목들을 나타낼 수 있다.

대중교통 노선 설정, 전염병의 전파 경로, SNS의 사람과 관계를 분석하는 것 등등

 

이런 그래프들을 분석할 때 가장 흔하게 사용되는 것이 최단 경로 탐색이고,

유명한 것은 구글을 현 위치에 있게 한 페이지랭크 알고리즘이 존재한다.

 

이렇게, 다양한 그래프로부터 흥미로운 결과를 도출할 수 있지만, 한가지의 문제가 존재한다.

 

“거대한 그래프”를 다루는 것은 어려운 문제라는 것

아무리 최적의 알고리즘을 선택해도, 소모 비용이 지수적으로 증가한다. 이는 단일 머신일 경우에 한계에 금방 다다른다. 그래서 컴퓨터 하나가 아니라 여러 대의 컴퓨팅 파워를 모으는 방법으로 접근한다. 이를 분산처리 시스템이라고 한다. 그러나 또 다른 문제가 발생한다.

 

1. 분산 처리 시스템에 적용하려면 그에 맞게 알고리즘이나 그래프 표현 방법을 새로 설계해야 함
2. 그로 유명한 MapReduce가 있지만, 그래프용이 아니기에 최적의 성능을 내기에는 부족하고, Map, Reduce 두가지 만으로 또 다른 복잡함을 야기한다.
3. 기존 다른 병렬 그래프 처리 시스템이 존재하지만, 계산 중간에 발생하는 장애에 대해서는 무방비

 

이런 문제들을 해결하기 위해 Pregel 시스템을 제안

프리겔(pregel) 프로그램의 고급 구성은 BSP(Bulk Synchronous Parallel) 모델에서 영감

 

개요

- 프리겔 연산은 슈퍼스텝(superstep)이라 불리는 일련의 반복으로 구성

- superstep동안 프레임워크는 각 정접(vertex)에 대한 사용자 정의 함수를 개념적으로(conceptually) 병렬 호출

- 함수는 싱글 정접 V와 싱글 superstep S에서 동작

 

노드 V는 superstep S 단계에 있다.

S-1 단계에서 보내온 message를 읽고, 내용을 계산하여 자신과 연결된 노드들에게 S+1단계에서 사용할 message를 전송하고 V 자신을 업데이트 한다.

Message 간 순서는 상관없고, superstep S에서 S+1 으로만 통신 발생, 각 노드는 각자 독립적이므로 병렬 처리가 가능하고 구조적으로 비동기 시스템에서 일반적인 교착상태(DeadLock), 데이터 레이스에서 자유롭게 한다.

 

노드는 message 발송 후 정지 상태, 이 상태로 다음 superstep 에 돌입하게 된다면 이 노드는 아무 작업도 하지 않는다. 하지만 수신한 message 내용에 따라 노드가 깨어날 수 있고, 깨어나면 S+1 단계에서 또 작업을 한다.

모든 노드가 정지 상태로, 아무런 message도 오가지 않는 상태가 되면 알고리즘 종료

 

그래프 내 최댓값을 구하는 예제, 

싱글 머신이 아니라 분산 처리 시스템이기 때문에 각 노드의 독립적인 작업으로 분할하여 어떻게 합쳐야할지 재구성 필요

 

 

Pregel은 이와 같은 특성을 지원하기 위해 다음과 같은 API 제공

1. Message 전송은 실패하는 일 없이 항상 목적지에 전달. (중복X), 전송 순서는 처리와 무관
2. Combiner는 message를 통합시켜 트래픽이 과도하게 발생하는 것을 방지 (수행 알고리즘에 따라 통합 방법이 다르기에, 미리 정의된 클래스에 유저가 직접 내부 정의 필요)
3. Aggregator는 매 superstep 단계마다 message를 같이 받아 통계정보 생성 (종료조건 설정 가능)
4. 그래프 알고리즘 수행은 그래프 형태 변화 가능 (다른 형태로 변화시키려는 message들이 있을 때, 우선순위는 Comput 내부에서 유저가 미리 지정)
5. 그래프 파일 포맷에 종속되지 않도록 읽고 쓸 수 있게 Reader/Writer 제공

 

 

출처

• Pretzel : A System for Large-Scale Graph Processing
• https://ingu627.github.io/paper/pregel/
• https://bitnine.tistory.com/76