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

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

세상에 그래프로 나타낼 수 있는 항목들이 많이 있습니다. 전통적으로는  대도시 대중교통의 노선 설정, 전염병의 전파경로, 논문표절탐지 등이 있으며 요새는 SNS의 사람과 관계를 분석하는 것이 아주 인기가 높습니다. 이런 그래프들을 분석할 때 가장 흔하게 사용하는 것이 최단 경로 탐색이고 또 유명한 것으로 구글을 현 위치에 있게 한 페이지랭크 알고리즘도 있습니다..  그 밖에도 여러가지 그래프로부터 흥미로운 결과를 도출할 수 있지만 문제가 한 가지 있습니다.

거대한 그래프를 다루는 것은 어려운 문제입니다. 최적의 알고리즘을 선택해도 소모 비용이 지수적으로 증가하는 것이 보통입니다. 결국 단일 머신에서의 한계에 금새 다다르게 됩니다. 계산과정을 모두 메모리에 적재하고 수행해도 한세월인데 메모리도 부족하여 디스크와 스왑하기 시작하면 살아생전에 결론을 보기가 불가능합니다. 그러므로 컴퓨터 하나가 아니라 여러 대의 Computing power를 모으는 방법으로 접근합니다. 이를 분산처리 시스템이라고 합니다. 다만 힘을 모으면 금새 잘 될 것 같았지만 또 다른 문제들이 발생하기 시작합니다.

1. 분산처리 시스템에 적용하려면 그에 맞게 알고리즘이나 그래프 표현 방법을 새로 설계해야합니다.

2. 이 분야의 대스타 MapReduce 가 있습니다만 그래프용으로 만들어진 물건은 아닙니다. 최적의 성능을 내기엔 부족하고 Map과 Reduce 두가지 만으로 그래프 알고리즘을 모두 표현하는건 또 다른 복잡함을 야기합니다.

3. 기존의 다른 병렬 그래프처리 시스템이 있긴 합니다만, 계산 중간에 발생하는 장애에 대해서는 무척 무방비합니다.

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

개요는 다음과 같습니다.

노드 V는 superstep S 단계에 있습니다. S-1 단계에서 보내온 message 를 읽고 나름의 내용을 계산해서 자신과 연결된 노드들에게 S+1단계에서 사용할 mesage를 전송하고 V 자신을 업데이트합니다. message간에 순서는 상관없고, superstep S 에서 S+1 으로만 통신이 발생합니다. 각 노드는 각자 독립적이므로 병렬 처리가 가능하고 구조적으로 Dead lock이 발생할 수 없습니다.

노드는 message 발송 후에 정지 상태에 접어들고 이 상태로 다음 superstep에 돌입하게 된다면 이 노드는 아무 작업도 하지 않게 됩니다. 하지만 수신한 message 내용에 따라 노드가 깨어날 수 있고. 깨어나면 S+1 단계에서 또 작업을 하게 됩니다. 모든 노드가 정지 상태에 접어들어 아무런 message도 오가지 않는 상태가 되면 알고리즘이 종료된 것이며 원하던 결과를 얻을 수 있습니다.

그래프 내의 최대값을 구하는 예제입니다. 싱글 머신이라면 쭉 돌아가며 비교하겠지만 분산 처리 시스템이니까 각 노드의 독립적인 작업으로 분할하여 어떻게 합쳐야할지 잘 재구성해봐야 합니다.

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

1. Message 전송은 실패하는 일 없이 항상 목적지에 전해집니다. 중복되거나 하지도 않습니다. 전송받은 순서는 처리와 무관합니다.

2. Combiner는 message를 통합시켜 트래픽이 과도하게 발생하는 것을 방지합니다. 수행하는 알고리즘에 따라 통합 방법은 달라질 수 밖에 없으므로 미리 정의된 클래스가 주어지고 유저가 직접 내부를 정의해주어야합니다.

3. Aggregator는 매 superstep 단계마다 message를 같이 받아서 통계정보를 생성해냅니다. 그냥 보여줄 수도 있고, 알고리즘의 종료조건으로 사용할 수도 있습니다.

4. 그래프 알고리즘의 수행은 그래프의 형태를 변화시키기도 합니다. 서로 다른 형태로 변화시키려는 message들이 있을 때 무엇을 선택할지는 Comput() 내부에서 미리 유저가 정의해주어야 합니다.

5. 그래프 파일 포맷에 종속되지 않도록 다 읽고 쓸 수 있게 Reader / Writer 를 제공합니다.

이와 같은 아이디어들을 기반으로 해서 벌써 많은 그래프 분석 시스템들이 돌아가고 있습니다. 논문에서 처럼 Hadoop 을 기저로 삼기도 하고 새로 나온 Spark를 가지고 만들기도 합니다. 다음에는 실제 구현된 Pregel에 대해서 이야기 해보는 것도 좋겠습니다.

이 내용은 Pregel : A system for Large-Scale Graph Processing을 참고하여 작성하였습니다.

Pregel에 관해 더 구체적인 내용이 궁금하시다면 원문을 참조해주세요.

Posted by Bitnine(비트나인)