ingu627 🔅

Circuit rhythms, neural visions: the art of artificial intelligence 64.6 x 65

개인 저장공간입니다.
Since 2021.10

3 분 소요

image

“Pregel: A System for Large-Scale Graph Processing” 논문을 개인 공부 및 리뷰를 위해 쓴 글입니다.

논문 출처 pdf : pregel paper




Pregel: 대규모 그래프를 쉽게 처리하는 구글의 똑똑한 시스템

  • Pregel은 구글이 만든 시스템으로, 웹 페이지 연결이나 소셜 네트워크처럼 엄청나게 큰 그래프 데이터를 효율적으로 분석하고 처리한다.
    • 마치 거미줄처럼 복잡하게 연결된 데이터를 다루는 데 최적화되어 있다.
    • 이 시스템의 강점은 크기가 커져도 잘 확장되고, 중간에 문제가 생겨도 잘 견디는 ‘장애 허용’ 기능이다.
    • 논문 내용을 바탕으로, 복잡한 부분은 비유와 예시를 들어 쉽게 풀어 설명하겠다.
    • Pregel의 아이디어는 요즘 AI 프레임워크인 LangGraph에도 영향을 주고 있다.


왜 Pregel이 필요했을까? (Introduction)

  • 큰 그래프를 다루는 건 쉽지 않다.
  • 그래프 알고리즘으로는 ‘최단 경로 찾기(예: 지도 앱의 길 안내)’, ‘클러스터링(비슷한 그룹 짓기)’, ‘페이지 랭크(웹 페이지 중요도 계산)’ 등이 있다.
  • 문제점:
    • 메모리 접근이 불규칙해서 느리고,
    • 각 ‘정점(노드)’에서 할 일이 적으며,
    • 병렬 처리 양이 들쑥날쑥하다.
  • 여러 컴퓨터에 데이터를 나누면, 데이터가 ‘지역성(가까운 곳에 모여 있음)’이 떨어져 더 느려지고, 컴퓨터 하나가 고장 나면 전체가 멈출 위험이 크다.


  • 기존 방법의 단점:
    • 직접 분산 시스템을 만들자니 매번 새로 짜야 해서 번거롭다.
    • MapReduce처럼 기존 도구를 쓰자니, 그래프에 맞지 않아(메시지 주고받기가 어색하다).
    • 다른 병렬 시스템은 고장 나면 대처가 약하다.


  • 그래서 구글이 Pregel을 만들었다.
    • 확장성과 장애 허용을 최우선으로 한 플랫폼이다.
    • BSP(Bulk Synchronous Parallel) 모델에서 아이디어를 얻었다.
    • BSP는 ‘모두 함께 계산하고, 끝나면 박자 맞춰 다음으로’ 가는 방식이다.
    • 비유: 합창단이 한 소절씩 동시에 부르고, 각 소절 끝에서 “준비됐어?” 하고 확인하는 거다.


  • 프리겔(Pregel) 프로그램의 고급 구성은 BSP(Bulk Synchronous Parallel) 모델에서 영감을 받았다.
  • Pregel은 ‘슈퍼스텝(superstep)’이라는 반복 단계로 계산한다.
  • 각 단계에서 모든 정점이 동시에 일하고, 메시지를 주고받는다.
  • 이 방식은 MapReduce처럼 각 부분을 독립적으로 처리하지만, 그래프 연결을 활용해 더 자연스럽다.

  • 동기화 덕분에 프로그램이 엉키거나(교착 상태) 데이터가 충돌(레이스)할 위험이 적다.


    이미지출처 1



이미지출처 2



Pregel은 어떻게 계산하나? (Model of Computation)

  • 입력과 기본 흐름
    • 입력: 방향 그래프(화살표가 있는 연결).
    • 정점(vertex): 고유 ID(이름표)와 값(예: 웹 페이지 점수).
    • 에지(edge): 소스에서 타겟으로의 연결, 값(예: 연결 강도).
  • 계산 과정: 그래프를 초기화한 후, 슈퍼스텝을 반복한다.
    • 각 슈퍼스텝은 ‘전역 동기화’로 구분된다(모두 끝날 때까지 기다림).
    • 모든 정점이 병렬로 같은 함수를 실행한다.
  • 정점이 하는 일:
    • 자신의 상태나 나가는 에지 수정.
    • 이전 단계 메시지 받기.
    • 다른 정점으로 메시지 보내기.
    • 그래프 구조(토폴로지) 변경(정점/에지 추가/제거).
  • 토폴로지: 연결 방식, 마치 지도의 도로망처럼.
  • 에지는 계산 주체가 아니라, 그냥 ‘길’ 역할만 한다.


image

  • 종료와 출력
    • 종료: 모든 정점이 “이제 그만 하자(vote to halt)” 투표하면 끝.
      • 시작할 때 모든 정점 ‘활성(active)’.
      • 정점은 일 끝나면 비활성화 투표.
      • 새 메시지 오면 자동 활성화.
      • 출력: 정점 값 모음(예: 각 도시까지의 최단 거리).
      • 또는 통계만 출력(그래프 마이닝).

image

  • 예시: 그래프에서 최대값을 모든 정점에 퍼뜨리기.
    • 각 정점이 “내 최대값은 이거야” 메시지를 이웃에게 보낸다.
    • 더 큰 값 받으면 업데이트하고 다시 보낸다.
    • 더 이상 변화 없을 때 끝.
  • 비유: 마을 사람들(정점)이 “들어본 소문 중 제일 큰 숫자”를 이웃에게 전하고, 더 큰 거 들으면 업데이트하는 거다. 결국 모두가 최대값을 알게 된다.



Pregel 프로그래밍: C++ API (THE C++ API)

  • Pregel 프로그램은 Vertex 클래스를 상속받아 만든다.
    • 템플릿으로 값 타입 정의(정점, 에지, 메시지).
    • 핵심 함수: Compute() - 각 슈퍼스텝에서 active 정점에서 실행.
// Figure 3: The Vertex API foundations

template <typename VertexValue,
          typename EdgeValue,
          typename MessageValue>
class Vertex {
  public:
    virtual void Compute(MessageIterator* msgs) = 0;

    const string& vertex_id() const;
    int64 superstep() const;

    const VertexValue& GetValue();
    VertexValue* MutableValue();
    OutEdgeIterator GetOutEdgeIterator();

    void SendMessageTo(const string& dest_vertex,
                       const MessageValue& message);
    void VoteToHalt();
}
  • Compute(): 메시지 읽고, 상태 바꾸고, 메시지 보냄.
  • 상태: 정점/에지 값만 슈퍼스텝 간 유지(단순화 위해).

image
이미지출처 2


  • 메시지 주고받기(Message Passing)
    • SendMessageTo(): 값 + 타겟 ID로 메시지 보냄.
    • 다음 슈퍼스텝에서 Iterator로 받음(순서 무관, 전달 보장).
    • 타겟은 꼭 이웃 아니어도 OK.
    • 비유: 우편물 보내기, 주소만 알면 된다.
  • 메시지 합치기(Combiners)
    • 여러 메시지를 하나로 묶어 네트워크 부하 줄임.
    • 예: 숫자 메시지 합쳐 합계로.
    • 사용자 Combine() 함수 정의.
  • 글로벌 값 계산(Aggregators)
    • 모든 정점이 값 주면, 합/최대 등으로 하나로 만듦.
    • 다음 슈퍼스텝에서 공유.
    • 통계나 전체 조정 용도.
    • 예: “모두 조건 만족?” 확인해 알고리즘 분기.
  • 그래프 구조 바꾸기(Topology Mutations)
    • Compute()에서 정점/에지 추가/제거 요청.
    • 충돌 시: 순서 규칙(에지 지우기 먼저, 정점 추가 나중).
    • 나머지: 사용자 핸들러.
    • 결정론: 같은 입력이면 항상 같은 결과.
    • 변경은 다음 슈퍼스텝 적용.
  • 입출력(Input and Output)
    • 다양한 파일(텍스트, DB) 지원 위해 Reader/Writer 사용.
    • 계산과 분리해 유연.



Pregel 안에서 어떻게 돌아가나? (Implementation)

image
이미지출처 3


  • 기본 구조(Basic Architecture)
    • 클러스터: 수천 PC, 분산.
    • 마스터: 워커 지휘(파티션 나누기).
    • 워커: 그래프 조각(파티션) 처리, Compute() 실행, 메시지 주고받기.
    • 파티션: 정점 + 나가는 에지, 해시로 나눔.
  • 실행 순서:
    1. 프로그램 여러 개 띄우고 마스터 정함.
    2. 파티션 나누기.
    3. 입력 데이터 나눠줌.
    4. 슈퍼스텝 반복(Compute() 호출, 메시지 비동기 보내기).
    5. 출력 저장.
  • 고장 나도 OK(Fault Tolerance)
    • 체크포인트: 슈퍼스텝 시작 시 상태 백업.
    • 고장 감지: 마스터가 핑(안부 확인) 보냄.
    • 복구: 최근 백업 로드, 재배치.
    • 제한 복구: 고장 난 부분만 다시 계산, 메시지 기록 활용.
    • 결정론 필요(불일치 방지).
  • 워커 세부(Worker Implementation)
    • 메모리에 그래프 저장(정점 맵, 에지 리스트, 메시지 큐).
    • 슈퍼스텝: active 정점 돌며 Compute().
    • 메시지: 로컬은 바로, 원격은 버퍼.
  • 마스터 세부(Master Implementation)
    • 워커 목록 관리.
    • 장벽: 모두 끝날 때까지 기다림.
    • 통계 추적(그래프 크기, 활성 정점).
    • HTTP로 모니터링.
  • 애그리게이터 세부(Aggregators)
    • 워커에서 부분 계산 → 트리로 모아서 전체 값 → 마스터가 나눠줌.


  • Pregel 전체 프로세스 4



실제로 써보자: 예시 알고리즘 (Applications)

  • 페이지 랭크(PageRank)
    • 웹 페이지 중요도 계산.
    • 각 페이지가 랭크를 이웃에게 나누어 줌.
    • 30번 반복 후 끝.
class PageRankVertex : public Vertex<double, void, double> {
    virtual void Compute(MessageIterator* msgs) {
        // 메시지 합산해 새 랭크 계산
        // 이웃에게 나누어 보내기
    }
};


  • 최단 경로(Shortest Paths)
    • 한 시작점에서 모든 곳까지 최단 거리.
    • 거리 업데이트하며 퍼뜨림
class ShortestPathVertex : public Vertex<int, int, int> {
    void Compute(MessageIterator* msgs) {
        // 최소 거리 갱신
        // 이웃에게 새 거리 보내기
    }
};


마무리

  • Pregel은 큰 그래프를 다루는 데 혁신적이다.
  • 메시지 전달과 동기화로 복잡한 계산을 쉽게 한다.
  • 고장 나도 튼튼하고, 크기 커져도 잘 버틴다.
  • 이 개념은 요즘 AI 도구에도 쓰인다.
  • 그래프 처리에 관심 있으면 Pregel부터 공부해보자!



References

  1. Bulk Synchronous Parallel and Pregel - Large-scale graph processing ↩

  2. Gao, Jianliang, et al. “PRS: Parallel relaxation simulation for massive graphs.” The Computer Journal 59.6 (2016): 848-860. ↩ ↩2

  3. Hassan, Mohamad Al Hajj, and Mostafa Bamha. Handling limits of high degree vertices in graph processing using MapReduce and Pregel. Diss. Université Orléans, INSA Centre Val de Loire, LIFO EA 4022, France, 2017. ↩

  4. How does Google Pregel work? by nuric ↩

댓글남기기

참고