Pregel 처리 모델

개요

Pregel(프리글) 이란. 배치 그래프 최적화 방법으로 Bulk Synchronous Parallel. BSP라고도 불린다. 대표적으로 Apache Giraph, Spark GraphX, Filnk Gelly 등의 구현체가 있다.

Pregel 논문

많은 그래프 알고리즘이 한번에 하나의 간선을 순회하는 방식으로 표현된다. 특정 정보를 전파하기 위해 정점 하나와 인접한 정접을 조인하면서 특정 조건(더 이상 간선이 없을 때까지 등)에 도달할 때까지 반복한다. 이런 알고리즘을 이행적 폐쇄(transitive closure)라 한다.

“완료할 때까지 반복”이라는 개념을 맵리듀스로 구현하면 비효율적이다. 맵리듀스는 데이터를 일회성으로 처리하기 때문. 맵리듀스는 항상 전체 데이터셋을 읽어서 완전히 새로운 데이터셋 출력을 생성한다. 이전 반복과 관계없이 그래프의 일부만 처리되었더라도 동일하게 수행한다.

맵리듀스는 개념적으로 매퍼가 특정 리듀서를 호출해 “메세지를 전달”한다. 프리글에서도 유사한 개념으로 한 정점은 다른 정점으로 “메세지를 보낼” 수 있다. 대개 메세지는 간선을 따라 보내진다.

반복할 때마다 개별 정점에서 함수를 호출해 그 정점으로 보내진 모든 메세지를 전달하는데 리듀서를 호출하는 방식과 비슷하다. 차이점은 정점은 반복에서 사용한 메모리 상태를 기억하고 있다는 점. 따라서 정점은 새로 들어오는 메시지만 처리하면 된다. 메세지를 받지 않는 정점은 아무 일도 하지 않는다.

프리글 모델은 액터 모델과 살짝 비슷하다. 각 정점을 액터로 본다면 정점 상태를 제외하고 정점 사이의 메세지는 내결함성과 지속성이 있다. 메세지 통신은 고정된 횟수 안에 처리한다. 다만 프리글은 각 반복에서 이전 반복에서 보내진 모든 메시지를 전달한다. (액터는 이러한 타이밍 보장은 하지 않는다.)

내결함성

정점이 서로 직접 질의하지 않고 메세지로 통신하는 점은 성능 향상에 도움이 된다. 메시지는 일괄 처리가 가능해 통신 중 대기 시간이 발생하지 않기 때문이다. 대기 시간은 반복과 다음 반복 사이에서만 발생한다. 앞선 반복에서 보낸 메세지는 다음 반복에 도착됨을 보장하기 때문에 다음 반복을 시작하기 전 앞선 반복은 반드시 끝나야 하고 메세지는 네트워크 상에 복사되어야 한다.

프리글 구현상 다음 반복에서 메시지는 누락, 중복, 지연되더라도 목적지 정점에서 정확히 한 번만 처리된다. 반복이 끝나는 시점에 모든 정점의 상태를 주기적으로 체크포인팅함으로써 보장된다.

Reference

• 책 “데이터 중심 애플리케이션 설계”
• 논문 “Pregel: A System for Large-Scale Graph Processing”, Grzegorz Malewicz Matthew H. Austern Aart J.C Bik James C. Dehnert Ilan Horn Naty Leiser Grzegorz Czajkowski