이번에 더 배울 것
Malewicz 외(2010)의 Pregel은 계산을 슈퍼스텝(superstep)의 반복으로 나눕니다. 각 슈퍼스텝에서 모든 정점이 같은 사용자 함수를 개념상 병렬로 실행합니다. 함수는 이전 슈퍼스텝에서 받은 메시지를 읽고, 자기 값을 갱신하고, 다음 슈퍼스텝에 도착할 메시지를 이웃에게 보냅니다. 그래프 전체가 아니라 정점 하나의 입장에서 프로그램을 쓰기 때문에 정점 중심(vertex-centric) 계산이라고 부릅니다.
정점은 할 일이 없으면 멈춤에 투표(vote to halt)하고, 새 메시지를 받으면 다시 깨어납니다. 모든 정점이 멈춰 있고 전달 중인 메시지가 없으면 계산이 끝납니다. PageRank는 슈퍼스텝마다 ‘점수/진출 차수’를 이웃에 보내고 받은 합으로 점수를 갱신하며, 연결 요소는 가장 작은 번호를 이웃에 퍼뜨리는 방식으로 계산합니다.
분할(DAY 47)이 여기서 비용이 됩니다. 다른 서버에 있는 이웃에게 보내는 메시지는 네트워크를 지나므로 엣지 컷이 크면 슈퍼스텝마다 통신이 늘어납니다. 같은 정점으로 가는 메시지를 미리 하나로 합치는 결합기(combiner)로 줄일 수 있습니다. 다만 Stonebraker와 Pavlo(2024)가 지적하듯 통신 비용 때문에 분산 실행이 한 대 실행보다 늘 빠르지는 않으므로, 데이터 규모를 먼저 확인합니다.
작은 예제로 따라가기
A–B–C와 D–E 두 덩어리에서 초기값을 A=1, B=2, C=3, D=4, E=5로 두고, 슈퍼스텝 0에서 모든 정점이 자기 값을 이웃에 보냅니다.
슈퍼스텝 1에서 B는 {1, 3}을 받아 1로, C는 {2}를 받아 2로, E는 {4}를 받아 4로 바뀌고, 바뀐 정점만 다시 보냅니다.
슈퍼스텝 2에서 C가 1을 받아 1이 되고, 슈퍼스텝 3에서는 바뀌는 정점이 없어 모두 멈춥니다. 결과는 {A, B, C}=1, {D, E}=4입니다.
메시지가 서버를 넘을 때
동아리 네트워크(엣지 11개)에서 모든 정점이 이웃에게 메시지를 하나씩 보내는 슈퍼스텝 0에, 서버를 넘는 메시지가 몇 개일지 각 분할마다 먼저 예상하세요.
무방향 엣지 하나마다 양쪽으로 메시지가 하나씩 가므로, 잘린 엣지 1개가 서버 간 메시지 2개를 만듭니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.