[빅데이터] 논문 리뷰 An Experimental Comparison of Pregel-like Graph Processing Systems

Abstract

구글 프레겔의 등장은 대규모 그래프 데이터 처리 분야에 큰 관심을 불러일으켰고, 지난 2년 동안 등장한 Apache Giraph, GPS, Mizan, GraphLab과 같은 Pregel 유사 시스템 개발에 영감을 주었습니다. Pregel과 같은 시스템이 어떻게 작동하는지 이해하기 위해 그래프와 알고리즘에 구애받지 않는 최적화를 고려하고 여러 메트릭을 사용하여 Giraph, GPS, Mizan 및 GraphLab을 동일한 기준에서 실험적으로 비교하는 연구를 수행합니다. 시스템은 최대 128개의 Amazon EC2 시스템에서 4가지 다른 알고리즘(PageRank, 단일 소스 최단 경로, 약하게 연결된 구성 요소 및 분산 최소 스패닝 트리)과 비교됩니다. Giraph 및 GraphLab에 있는 시스템 최적화를 통해 잘 수행할 수 있음을 알았습니다. 우리의 평가는 또한 Giraph 0.1 이후 Giraph 1.0.0의 상당한 개선을 보여주고 모든 시스템에 대한 개선 영역을 식별합니다.

Intro

소셜 네트워킹 및 과학적 계산 기술의 발전과 대중화로 그래프 데이터는 유비쿼터스되었습니다. 비즈니스 인텔리전스, 분석, 데이터 마이닝 및 온라인 머신 러닝을 포함하여 실제 응용 프로그램을 위한 그래프 데이터를 처리해야 하는 흥미로운 문제가 점점 더 많아지고 있습니다. 예를 들어, Google의 PageRank 알고리즘은 1조 개 이상의 인덱싱된 웹페이지에 대해 영향력 있는 정점을 결정해야 합니다[4]. 소셜 그래프의 경우 Facebook은 인기도 또는 개인화된 순위를 계산하고, 공유 연결을 확인하고, 커뮤니티를 찾고, 9억 명 이상의 활성 사용자에 대한 광고 전파를 수행해야 합니다[6]. 통신 및 도로 네트워크에서 각각 최대 흐름을 결정하고 운송 경로를 지정하려면 큰 그래프를 처리해야 합니다[26]. 최근 과학자들은 생물학 그래프를 활용하여 단백질 상호 작용을 이해하고 병리학 그래프를 활용하여 이상을 식별하고 있습니다[30].

전통적으로 그래프 데이터를 처리하는 것은 자연 그래프의 불규칙한 특성 때문에 계산적으로 어려운 것으로 간주됩니다. BSP(Bulk Synchronous Parallel) 모델[37]은 더 많은 작업자로 확장되는 병렬 처리 알고리즘을 설계하는 수단을 제공합니다. Google의 Pregel[29]은 그래프 데이터를 처리하는 알고리즘을 작성하기 위한 기본 API를 제공하는 BSP 구현입니다. Pregel은 여전히 개선의 여지가 많은 단순한 모델이며, 여러 다른 그래프 처리 프레임워크의 출현으로 이어집니다. 대표적인 것으로 Apache Hama[2], Apache Giraph[1], Catch Wind(CatchW)[34], GPS[32], GraphLab[28](현재 PowerGraph[18]을 통합), Mizan[23]이 있습니다. .

이러한 시스템의 상대적인 성능 특성은 불분명합니다. 각각이 성능 결과를 보고하지만 쉽게 비교할 수는 없습니다. 이 백서에서 우리는 기본 제공 및 선택적 시스템 최적화, 시스템 고유의 최적화 및 사용된 그래프 또는 알고리즘에 대한 불가지론적 최적화 모두에 기인하는 다양한 시스템의 동작을 노출하는 데 중점을 두어 이 문제를 해결합니다. 따라서 이 연구는 서로 다른 시스템의 고유한 기능을 노출합니다.

이러한 시스템은 인프라가 다양하기 때문에 Pregel의 정점 중심 접근 방식을 사용하는 시스템인 오픈 소스 Pregel과 유사한 시스템으로 연구 범위를 좁힙니다. 따라서 그래프에 최적화되거나 특화되지 않은 일반화된 BSP 프레임워크인 Hama와 오픈 소스가 아니며 요청 시 해당 코드를 사용할 수 없었기 때문에 CatchW는 제외됩니다. 또한 그래프 데이터베이스 시스템은 그래프 데이터를 지속적으로 관리하는 것이 목표이므로 그래프 데이터베이스 시스템은 제외하고 그래프 처리 프레임워크는 대용량 그래프의 메모리 내 일괄 처리를 처리합니다[12].

따라서 Giraph, GPS, GraphLab 및 Mizan을 비교합니다. 처음 세 가지는 모두 연구 및 산업계가 현재 사용하고 구축하고 있는 인기 있는 시스템입니다. 예를 들어, Giraph는 GPS의 몇 가지 최적화 기능을 통합했으며 빠르게 성장하는 사용자 기반을 보유하고 있으며 Facebook에서는 1조 개의 모서리가 있는 그래프로 확장했습니다[10]. Mizan은 이러한 시스템의 경쟁자로 떠올랐습니다. 최근성과 유사한 그래프 처리 목표를 감안할 때 Mizan이 Giraph, GPS 및 GraphLab과 동일한 설정에서 어떻게 수행되는지 이해하는 것도 중요합니다.

우리의 주요 목표와 기여는 (i) 4개의 오픈 소스 Pregel 유사 시스템(Giraph, GPS, Mizan 및 GraphLab)을 체계적이고 공정하게 비교하여 내장 및 선택적 시스템 최적화가 성능에 미치는 영향을 연구하는 것입니다. (ii) 실행 시간, 메모리 사용량 및 네트워크 트래픽을 실제 데이터 세트 및 다양한 알고리즘과 함께 메트릭으로 사용하여 각 시스템의 성능을 설명하고 (iii) 다음과 관련하여 각 시스템의 장단점에 대한 논의 시스템 설계자와 사용자에게 이러한 시스템의 사용 및 개발을 촉진할 수 있는 정보를 제공하기 위한 그래프 데이터 처리.

우리는 Pregellike 시스템에 대한 두 가지 기존 실험 연구[16, 19]를 알고 있지만 둘 다 데이터 세트 크기와 사용된 기계 수 측면에서 규모가 부족합니다. 또한 [16]은 알고리즘 다양성이 좋지 않고 하나의 실험 메트릭만 고려하는 반면 [19]는 알고리즘, 데이터 세트 및 기계의 모든 조합에 대한 포괄적인 실험 결과가 부족합니다. 마지막으로 두 연구 모두 GPS 및 Mizan과 같이 우리가 포함하는 일부 시스템을 고려하지 않습니다.

이 논문은 다음과 같이 구성되어 있습니다. 섹션 2에서는 BSP와 Pregel에 대한 배경 지식을 제공합니다. 섹션 3에서는 테스트하는 시스템을 설명하고 섹션 4에서는 워크로드로 사용하는 네 가지 알고리즘을 설명합니다. 섹션 5에서 데이터 세트 및 메트릭을 포함한 평가 방법론을 자세히 설명하고 섹션 6에서 결과를 분석합니다. 섹션 8에서 마무리하기 전에 섹션 7에서 각 시스템에 대한 경험을 강조합니다.

Background

BSP(Bulk Synchronous Parallel)는 확장성을 위해 여러 작업자에 걸쳐 작업을 병렬화하는 문제를 해결하기 위해 개발된 MPI(메시지 전달 인터페이스)가 있는 병렬 프로그래밍 모델입니다[37]. 분산 공유 메모리와 달리 MPI를 사용하면 메시지 일괄 처리가 가능하므로 MPI는 본질적으로 교착 상태 및 경쟁 조건이 없기 때문에 대기 시간이 긴 원격 읽기를 보장하고 과도한 잠금을 방지합니다. BSP는 본질적으로 각 정점이 각 상태에서 활성 또는 비활성일 수 있는 정점 상태 머신입니다. 계산은 수퍼스텝 장벽에서 발생하는 작업자 간의 동기화와 함께 일련의 수퍼스텝으로 구성됩니다(그림 1). 이 동기식 접근 방식의 고유한 한계는 작업자가 낙오자 문제에 직면할 수 있다는 것입니다. 여기서 빠른 작업자는 느린 작업자를 기다려야 합니다. 그러나 BSP는 행렬 계산, 기계 학습 및 그래프 처리 문제에 대해 거의 완전한 범위를 제공합니다.

Pregel [29]은 최초의 BSP 구현 중 하나입니다. 기본 통신 세부 정보를 추상화하면서 그래프 알고리즘 프로그래밍을 위해 특별히 네이티브 API를 제공합니다. Pregel이 사용하는 기본적인 컴퓨팅 패러다임은 "정점처럼 생각하기"로 특징지을 수 있습니다. 그래프 계산은 각 정점이 계산해야 하는 항목으로 지정됩니다. 에지는 한 정점에서 다른 정점으로 계산 결과를 전송하기 위한 통신 채널이며 계산에 참여하지 않습니다. 계산은 슈퍼스텝으로 나뉩니다. 각 슈퍼스텝에서 정점은 사용자 정의 기능을 실행하고 이웃(또는 알려진 ID를 가진 다른 정점)에 메시지를 보내거나 받을 수 있으며 상태를 활성에서 비활성으로 변경할 수 있습니다. 수퍼스텝은 동기화 장벽으로 끝나며(그림 1), 한 수퍼스텝에서 보낸 메시지가 다음 수퍼스텝 시작 시 전달되도록 합니다. 정점은 모든 수퍼스텝에서 중지하도록 투표할 수 있으며 메시지를 수신하면 깨어납니다. 모든 정점이 비활성화되고 더 이상 메시지가 전송되지 않으면 Pregel이 종료됩니다.

통신 오버헤드를 피하기 위해 Pregel은 데이터를 보존합니다. 로컬에 저장된 데이터에 대해 계산이 수행되도록 보장하여 로컬리티. 입력 그래프는 프로그램 시작 시 한 번 로드되고 모든 계산은 메모리 내에서 실행됩니다. 결과적으로 Pregel은 메모리에 맞는 그래프만 지원합니다.

Pregel은 마스터/작업자 모델을 사용합니다. 한 기계는 마스터 역할을 하고 다른 기계는 작업자가 됩니다. 마스터는 입력 그래프를 하위 그래프로 분할하고 각 분할을 작업자에게 할당합니다. 마스터는 슈퍼스텝 장벽에서 동기화를 조정하고 작업자에게 체크포인트(내결함성 수단)를 수행하도록 지시하는 책임이 있습니다. 각 작업자는 그래프의 해당 부분에 있는 정점에서 compute() 함수를 독립적으로 호출합니다. 또한 작업자는 다른 작업자의 정점에서 메시지를 수신하기 위해 메시지 대기열을 유지 관리합니다. 또한 사용자 정의 결합기를 사용하여 (발신자 또는 수신자에서) 메시지를 결합하여 성능을 향상시킬 수 있습니다. 글로벌 조정을 위해 애그리게이터를 사용할 수 있습니다. 각 정점은 한 수퍼스텝에서 집계기에 값을 제공하고 다음 수퍼스텝에서 전체적으로 감소된 값을 얻을 수 있습니다[29].

Systems Tested

Giraph

Apache Giraph[1]는 독점 Pregel에 대한 오픈 소스 대안입니다. Giraph는 Hadoop에서 작업자를 맵 전용 작업으로 실행하고 데이터 입력 및 출력에 HDFS를 사용합니다. Giraph는 또한 조정, 체크포인트 및 장애 복구 체계를 위해 Apache ZooKeeper를 사용합니다. Facebook [10]을 포함한 대규모 개발자 및 사용자 기반 때문에 Giraph 1.0.0을 선택합니다. Giraph 1.0.0도 Giraph 0.1 이후 여러 최적화를 거쳤습니다. 여기에는 마스터에서 병목 현상을 방지하는 샤딩된 수집기(sharded aggregator)와 버텍스, 에지 및 메시지를 바이트 배열로 직렬화하여 상당한 메모리 절약 및 Java 가비지 수집 오버헤드 감소가 포함됩니다[10].

Giraph는 정점 인접 목록에 대해 다양한 데이터 구조를 지원합니다. 기본적으로 바이트 배열은 공간 효율적이기 때문에 사용되며 결과에서 볼 수 있듯이 입력 로드 시간이 빨라집니다. 그러나 바이트 배열 가장자리는 가장자리가 제거될 때마다 모든 가장자리가 역직렬화되기 때문에 정점 또는 가장자리의 추가 또는 제거와 같은 그래프 변형에는 비효율적입니다. 반면에 해시 맵 가장자리는 메모리에는 덜 효율적이지만 돌연변이에는 매우 효율적입니다.

워크로드 중 하나인 DMST(Distributed Minimum Spanning Tree)가 그래프 변형을 수행하므로 바이트 배열과 해시 맵 에지를 모두 사용하여 Giraph를 테스트합니다. 마지막으로 체크포인트는 다른 시스템에서 수행하지 않으므로 비활성화됩니다.

GPS

GPS는 Stanford InfoLab의 또 다른 오픈 소스 Pregel 구현입니다[32]. GPS는 Giraph 0.1보다 12배 더 빠른 것으로 보고되었지만 결과에서 알 수 있듯이 Giraph 1.0.0이 일부 GPS 최적화를 채택했기 때문에 이 격차가 부분적으로 좁혀졌습니다[32].

GPS는 비교적 완전한 기능을 갖춘 실험 시스템이기 때문에 포함합니다. 많은 그래프 알고리즘이 구현되어 시스템의 정확성에 대한 확신을 제공합니다. GPS는 또한 여러 Java 객체를 할당하는 비용을 줄이기 위해 단일 표준 정점 및 메시지 객체와 같은 많은 내장 시스템 최적화 기능을 제공합니다[32]. 정점별 메시지 버퍼가 아닌 작업자별 사용(네트워크 사용량 향상) 및 스레드 동기화 감소와 같은 기타 최적화는 모두 성능 향상에 도움이 됩니다[31].

GPS는 모든 이웃에 동일한 메시지를 보내는 알고리즘에 대한 선택적 성능 최적화인 LALP(Large Adjacency List Partitioning)를 제공합니다[32]. LALP는 다른 작업자에 걸쳐 고차 정점의 인접 목록을 분할하여 작동합니다. PageRank, WCC(Weakly Connected Components) 및 단위 가장자리 가중치가 있는 단일 소스 최단 경로(SSSP)(섹션 4)와 같은 알고리즘에 유용하지만 DMST와 같은 알고리즘이나 애그리게이터가 관련된 경우에는 작동하지 않습니다. LALP는 또한 최적 값이 입력 그래프와 작업자 수에 따라 달라지는 임계값 매개변수를 필요로 합니다[32]. 그래프, 알고리즘 및 작업자의 모든 조합에 대해 이 매개변수를 조정하는 것은 비현실적이므로 전체적으로 잘 작동하도록 실험적으로 결정한 값 100을 선택합니다.

GPS는 또한 선택적 동적 마이그레이션 체계를 제공합니다. 대부분의 시스템에서 그래프 분할은 계산 전에 수행되지만 계산 중에는 수행되지 않습니다. 동적 마이그레이션은 작업 부하 균형과 네트워크 사용량을 개선하기 위해 작업자 간의 정점을 마이그레이션하여 계산 중에 그래프를 다시 분할합니다. 특히 GPS의 방식은 각 정점이 보낸 데이터의 양에 따라 작업자 간에 정점을 교환합니다. 이 체계는 정점 ID의 레이블을 다시 지정하고 표시되는 인접 목록을 업데이트하여 마이그레이션된 정점을 찾습니다. 즉, 지정된 정점 ID로 직접 메시지를 보내는 DMST와 같은 알고리즘에서는 작동하지 않습니다. 이 방식은 네트워크 I/O를 줄이지만 항상 계산 시간을 향상시키는 것은 아닙니다[32]. 이러한 결과를 독립적으로 확인하기 위해 동적 마이그레이션을 실험합니다.

마지막으로 GPS는 여러 알고리즘별 최적화를 제공하며 그 중 다수는 입력 그래프에 따라 조정 가능한 매개변수를 사용합니다. 이러한 최적화는 특정 그래프와 알고리즘에 의존할 뿐만 아니라 시스템 간의 성능 격차를 줄여 내장된 시스템 최적화로 인해 차이를 관찰하기 더 어렵게 만들 수도 있습니다. 따라서 알고리즘별 최적화를 사용하지 않습니다.

선택적 최적화 없이 LALP만 사용하고 동적 마이그레이션만 사용하여 GPS를 실행합니다.

Mizan

Mizan은 KAUST가 IBM Research와 공동으로 개발한 오픈 소스 프로젝트입니다[23]. GPS와 유사하게 Mizan은 동적 마이그레이션이 사용되지 않는 정적 모드에서 실행할 때 Giraph 0.1보다 2배 더 빠른 것으로 보고되었습니다[23]. 우리의 연구는 동일한 모드에서 Mizan과 Giraph의 최신 버전을 고려합니다.

Giraph, GPS 및 GraphLab과 동일한 그래프 데이터 처리 목표를 가지고 있기 때문에 Mizan을 포함합니다. Mizan에는 구현된 알고리즘이 거의 없으므로 시스템의 성능과 정확성을 모두 테스트할 수 있는 좋은 기회를 제공합니다. 실제로 알고리즘을 구현하는 과정에서 잘못된 집계 값 및 메시지 수신 시 깨어나지 않는 정지 작업자와 같은 시스템의 여러 버그를 식별하고 수정할 수 있었습니다.

Mizan은 또한 GPS보다 더 복잡한 선택적 동적 마이그레이션 체계를 제공하지만 Mizan은 이 체계가 활성화된 상태에서 올바르게 작동하지 않습니다[22]. 따라서 정적 모드에서 기본 구성으로 Mizan을 실행합니다. 다른 시스템과 달리 Mizan은 알고리즘 실행과 별도로 그래프를 분할하며 이는 섹션 6.4에서 논의하는 문제입니다.

GraphLab

GraphLab은 CMU[28]에서 시작하여 현재 GraphLab Inc.에서 지원하는 오픈 소스 프로젝트입니다. 우리는 분산 계산을 지원하고 PowerGraph[18]의 기능 및 개선 사항을 통합하는 최신 버전의 GraphLab 2.2[3]를 사용합니다. 그래프 분석 작업에 대한 인기와 성숙도 때문에 GraphLab을 포함합니다.

GraphLab은 이전 시스템과 달리 BSP 모델과 유사하지만 근본적으로 다른 GAS 분해(Gather, Apply, Scatter)를 사용합니다. GAS 모델에서 정점은 수집 단계에서 이웃에 대한 정보를 축적하고 적용 단계에서 누적된 값을 적용하며 인접 정점과 가장자리를 업데이트하고 분산 단계에서 인접 정점을 활성화합니다. 특히 정점은 이웃으로부터 명시적으로 메시지를 받을 필요 없이 이웃 데이터를 직접 가져올 수 있습니다(Gather를 통해). 대조적으로, BSP 모델의 정점은 이웃이 푸시하는 메시지를 통해서만 이웃의 값을 학습할 수 있습니다. GAS 모델은 또한 통신 장벽 없이 완전히 비동기식 실행을 가능하게 합니다.

또 다른 주요 차이점은 GraphLab이 가장자리 절단 대신 정점 절단을 사용하여 그래프를 분할한다는 것입니다. 결과적으로 각 가장자리는 고유한 시스템에 할당되고 정점은 원격 시스템의 캐시에 복제됩니다. 정점 절단을 통해 여러 시스템에 걸쳐 높은 차수의 정점을 분할할 수 있기 때문에 이것은 PowerGraph에서 통합된 기능으로, 편향된 차수 분포가 있는 그래프에 대해 더 균형 잡힌 작업 부하를 생성합니다[18]. 대조적으로 Giraph, GPS 및 Mizan은 모두 가장자리 절단을 수행하고 정점을 복제하지 않습니다.

마지막으로 Giraph, GPS, Mizan과 달리 GraphLab은 그래프 변이를 완벽하게 지원하지 않습니다. 모서리 추가는 지원하지만 정점이나 모서리 제거는 지원하지 않습니다.

GraphLab은 동기 및 비동기의 두 가지 실행 모드를 제공합니다. BSP와 마찬가지로 동기 모드는 통신 장벽을 사용합니다. 그러나 GAS 모델을 따르기 때문에 동기 모드도 적응적입니다. 수렴된 정점은 이웃이 Gather를 통해 마지막 값을 가져올 수 있으므로 더 이상 계산에 참여할 필요가 없습니다. 이렇게 하면 CPU 및 네트워크 리소스가 낭비되는 것을 방지할 수 있습니다. 대조적으로, 수렴된 정점은 BSP에서 활성 상태를 유지하여 마지막 값을 포함하는 이웃 메시지를 보내야 합니다. 비동기 모드 또는 [28]의 분산 잠금 엔진은 완전히 비동기적이며 통신 장벽이나 수퍼스텝에 대한 개념이 없습니다. 충돌을 피하고 직렬성(일부 순차적 실행과 동등함)을 유지하기 위해 분산 잠금을 사용합니다. 비동기 모드를 추가 비교 포인트로 사용합니다. 따라서 동기 및 비동기 모드로 GraphLab을 테스트합니다.

Algorithms

우리는 랜덤 워크, 순차 순회, 병렬 순회 및 그래프 돌연변이의 네 가지 범주의 그래프 알고리즘을 고려합니다(표 2) [35].

랜덤 워크 알고리즘은 랜덤 워크 모델을 기반으로 모든 정점에 대해 계산을 수행합니다. 순차 탐색 알고리즘은 그래프 구조를 업데이트하거나 변경하지 않고 일부 최적화 기준에 따라 그래프에서 하나 이상의 경로를 찾습니다. 이러한 알고리즘은 일반적으로 하나의 소스 정점에서 시작하여 수퍼스텝 i에서 소스로부터 거리 i에 있는 정점을 처리합니다. 순차 순회와 달리 병렬 순회 알고리즘은 모든 정점을 한 번에 고려하는 것으로 시작합니다. 여러 정점이 공통 정보를 얻을 때까지 각 수퍼스텝에 참여합니다. 마지막으로, 그래프 돌연변이는 계산 중에 그래프 구조를 변경하는 알고리즘을 포함합니다.

실험을 위해 각 범주에서 하나의 대표적인 알고리즘을 선택합니다. 랜덤 워크의 경우 PageRank, 순차 탐색의 경우 SSSP, 병렬 탐색의 경우 WCC, 그래프 돌연변이의 경우 DMST입니다. 표 2는 이러한 알고리즘이 CPU, 메모리 및 네트워크 리소스를 얼마나 많이 활용하는지 요약합니다. 다음으로 각 알고리즘에 대해 설명합니다. 추가 기술 세부 사항은 섹션 5.3에서 찾을 수 있습니다.

PageRank

PageRank는 Google에서 웹페이지 순위를 매기는 데 사용하는 알고리즘으로, 더 중요한 웹사이트가 다른 웹사이트로부터 더 많은 링크를 받을 가능성이 높다는 아이디어를 기반으로 합니다. [29]에서 사용된 것과 동일한 값인 0.85 감쇠 계수와 함께 PageRank를 사용합니다. 이 요소는 사용자가 탐색 중인 웹 페이지(정점)가 주어지면 현재 페이지의 나가는 링크(외부 가장자리)에서 임의의 웹 페이지로 이동할 가능성이 85%이고 다음으로 이동할 가능성이 15%임을 의미합니다. 전체 웹에서 선택한 임의의 웹페이지(입력 그래프).

특히 모든 정점은 1.0 값으로 시작합니다. 각 슈퍼스텝에서 정점 u는 값을 p = 0.15 + 0.85x로 업데이트합니다. 여기서 x는 내부 가장자리에서 수신된 값의 합이고 외부 가장자리를 따라 p/deg+(u)를 보냅니다. 여기서 deg+(u) 는 당신의 outdegree입니다. 이것은 기대값을 제공합니다. 정점의 수로 나누면 확률 값이 나옵니다.

많은 시스템에서 제공되는 인기 있는 알고리즘인 PageRank를 포함합니다. PageRank의 단순성은 핵심 시스템 구성 요소 및 성능에 대한 간단한 테스트를 제공합니다. 계산 전반에 걸쳐 모든 정점이 활성 상태를 유지하므로 슈퍼스텝에서도 통신이 안정적입니다.

한 슈퍼스텝에서 모든 정점이 연산에 참여하여 방대한 양의 메시지를 생성하므로 네트워크 트래픽 병목 현상이 발생할 수 있다.

SSSP

단일 소스 최단 경로(SSSP)는 주어진 소스 정점과 연결된 구성 요소의 다른 모든 정점 사이의 최단 경로를 찾습니다. 무방향 그래프의 경로는 인접한 꼭짓점의 시퀀스이며 구성 간선 가중치의 합이 최소화되는 경우 가장 짧습니다. 우리는 Bellman-Ford 알고리즘[13]의 병렬 변형을 사용합니다. 이 알고리즘은 소스 정점의 거리를 0으로 설정하고 다른 모든 정점의 거리를 ∞로 설정하는 것으로 시작합니다. 소스 정점만 첫 번째 수퍼스텝에서 활성화됩니다. 각 활성 정점 u는 모든 이웃 v에게 현재 최소 거리에 에지의 가중치(u, v)를 더한 값을 보냅니다. 다음 수퍼스텝에서는 메시지를 수신하는 정점이 활성화되고 각 활성 정점은 수신된 거리의 최소값을 취합니다. 더 작은 거리가 발견되면 정점은 발견을 이웃으로 전파합니다. SSSP가 수행하는 슈퍼스텝의 수는 그래프의 최장 최단 경로에 의해 제한됩니다. 순회 알고리즘이기 때문에 SSSP의 네트워크 사용량은 가변적입니다. 즉, 통신량이 증가하고 최고점에 도달한 다음 슈퍼스텝이 증가함에 따라 감소합니다. 따라서 SSSP는 시스템이 동적으로 변화하는 통신을 얼마나 잘 처리하는지 테스트하는 가장 간단한 알고리즘입니다. 특히 PageRank와 달리 정점은 항상 정지에 투표하고 수신된 메시지에 의해서만 깨어납니다. 시스템 병목 현상은 초기 단계에서 통신이 작고 점차 증가하기 때문에 식별하기 더 쉽습니다.

WCC

Weakly Connected Components(WCC)는 그래프의 최대 약한 연결 구성 요소를 찾는 알고리즘입니다. 모서리 방향을 무시할 때 모든 정점 쌍이 서로 연결할 수 있으면 구성 요소가 약하게 연결된 것입니다. WCC는 HCC 알고리즘을 사용하여 구현됩니다[20]. 모든 정점은 처음에 활성화됩니다. 각 정점은 구성 요소 ID를 정점 ID로 설정하여 자체 구성 요소로 시작합니다. 정점이 더 작은 구성 요소 ID를 받으면 수신된 ID로 정점 값을 업데이트하고 해당 ID를 이웃에 전파합니다. SSSP와 마찬가지로 WCC는 그래프의 최장 최단 경로와 동일한 수의 슈퍼스텝을 취합니다. 병렬 순회 알고리즘인 WCC는 입력 그래프를 변경하지 않고 네트워크 부하가 더 큰 경우 SSSP의 결과를 확증하는 데 도움이 됩니다. 또한 SSSP와 달리 모든 정점은 초기에 활성화되며 PageRank와 달리 정점이 다른 정점보다 먼저 중지될 수 있습니다. 그 결과 수퍼스텝이 증가함에 따라 단조롭게 감소하는 네트워크 통신이 발생하여 다른 별개의 통신 패턴에서 시스템 성능을 관찰할 수 있습니다.

DMST

DMST(분산 최소 신장 트리)는 무방향 가중치 그래프의 최소 신장 트리(MST)를 찾습니다. 이 트리는 모든 간선 가중치가 고유한 경우 고유합니다. 병렬 Boruvka 알고리즘을 사용합니다[11, 33]. 입력 그래프는 방향이 없어야 하지만 연결될 필요는 없습니다. 연결되지 않은 그래프의 경우 DMST는 MST의 합집합인 최소 스패닝 포레스트를 출력합니다. 이 알고리즘은 복잡성 때문에 흥미롭습니다. 예를 들어, Giraph의 구현은 SSSP의 경우 100라인에 비해 약 1300라인의 코드입니다. 이 알고리즘에는 사용자 지정 정점, 가장자리 및 메시지 데이터 유형이 필요하며 세 가지 유형의 메시지를 보냅니다.

알고리즘은 4단계로 진행됩니다. 첫 번째 단계에서 각 정점은 최소 가중치를 찾습니다. 두 번째 단계에서 정점은 질문 및 답변 메시지를 사용하여 하위 정점이 속하는 그래프의 연결된 구성 요소를 나타내는 상위 정점을 결정하여 포인터 점프 알고리즘[11]을 수행합니다. 이 단계는 수퍼스텝의 불확실한 수에 대해 반복될 수 있으므로 합산 집계기를 사용하여 동기화됩니다. 세 번째 단계에서 정점은 가장자리 청소를 수행합니다. 정점은 먼저 동일한 슈퍼 정점을 가진 이웃에 대한 외부 가장자리를 제거합니다. 그런 다음 가장자리의 대상 정점의 초 정점을 가리키도록 나머지 각 외부 가장자리를 수정합니다. 마지막으로 네 번째 단계에서 정점은 인접 목록을 수퍼 정점으로 보내고 최소 가중치에 따라 병합합니다. Non-supervertices는 정지에 투표하고 supervertices는 정규 정점으로 첫 번째 단계로 돌아갑니다. 그래프는 연결되지 않은 정점만 남으면 알고리즘이 종료되면서 점점 작아집니다.

DMST는 CPU 집약적이며 훨씬 덜 예측 가능한 메시지 패턴을 실행합니다. 의사 소통은 세 번째 및 네 번째 단계에서 최고조에 달하지만 첫 번째 및 두 번째 단계에서는 작게 유지됩니다. 이 피크는 활성 상태로 남아 있는 정점이 적기 때문에 시간이 지남에 따라 감소합니다. 두 번째 단계가 여러 번 반복되기 때문에 언제 이러한 피크가 발생할지 예측하기 어렵습니다. 또한 슈퍼버텍스로 에지를 보내는 것은 다대일 통신으로 슈퍼버텍스를 병목 현상으로 만들 수 있습니다. DMST는 집계 및 그래프 돌연변이를 광범위하게 사용하기 때문에 좋은 시스템 스트레스 테스트이기도 합니다. 둘 다 다른 알고리즘에 의해 테스트되지 않은 Pregel과 같은 시스템의 중요한 구성 요소입니다.