Apache Giraph – From installation to Example execution

By | Y2016Y2016-8M-D

아파치 하둡 기반의 다양한 플랫폼 중에서 오늘은 Apache Giraph 를 알아보고,  예제인 SimpleShortestPathsComputation 을 실행해 보려고 한다.

먼저 Giraph 에 대한 소개를 보자(http://giraph.apache.org/)

Welcome to Apache Giraph!
Apache Giraph is an iterative graph processing system built for high scalability. For example, it is currently used at Facebook to analyze the social graph formed by users and their connections. Giraph originated as the open-source counterpart to Pregel, the graph processing architecture developed at Google and described in a 2010 paper. Both systems are inspired by the Bulk Synchronous Parallel model of distributed computation introduced by Leslie Valiant. Giraph adds several features beyond the basic Pregel model, including master computation, sharded aggregators, edge-oriented input, out-of-core computation, and more. With a steady development cycle and a growing community of users worldwide, Giraph is a natural choice for unleashing the potential of structured datasets at a massive scale.

Apache Giraph 는 고확장성의 반복 그래프 (작업) 처리 시스템이다. 예를 들면, 이 Giraph는 현재 페이스북에서 사용자와 사용자의 연결 망이 이루는  social graph 를 분석하기 위해 현재 사용되고 있다. Giraph 는 Google 이 2010년에 개발 및 기술한  graph 처리 아키텍쳐인  Pregel에 대항하는 오픈소스에 기원을 두고 있다. 이 두 시스템(Pregel & Giraph) 은 Leslie Valiant 가 소개한 분산 컴퓨팅의 BSP(Bulk Synchronous Parallel model) 에서 영감을 받아 탄생하였다. Giraph 는 주 연산(master computation), 공유 집합체(shared aggregation), 가장자리-중심의 입력(edge-oriented input), 중심 밖 연산(out-of-core computation) 외에 다른 특징들을 포함하는 기본 Pregel model 이상의 여러 특징들이 추가된다. 지속적인 개발 사이클과 전 세계적으로 성장하는 커뮤니티 사용자 수와 함께, Giraph는 막대한 규모의 구조화 된 잠재적 데이터 집합을 풀어주기 위한 자연적인 선택이다.

The input to a Giraph computation is a graph composed of vertices and directed edges, see Figure 1. For example vertices can represent people, and edges friend requests. Each vertex stores a value, so does each edge. The input, thus, not only determines the graph topology, but also the initial values of vertices and edges.

Giraph 연산을 위한 graph 모델은 꼭지점(vertext) 와 방향성 있는 가장자리(edge) 로 이루어지며, 이 각각의 vertex, edge는 값을 저장하고 있다. graph 연산을 위한 입력 값을 보면 graph topology 뿐만 아니라, 각 vertext 와 edge 의 초기 값을 지정하게 된다.

그림 1: Giraph에서 단일 소스 최단 경로 알고리즘의 실행에 대한 일러스트. 입력은 3개의 꼭지점(검은색)과 두 개의 가장자리(초록색)으로 된 체인 그래프로 되어 있다. 알고리즘은 가장 왼쪽의 꼭지점으로 부터의 거리를 계산한다. 꼭지점들의 최초 값은 0, ∞ 그리고 ∞ (최 상위 열). 상위 경계의 거리는 메시지(파란색)으로 보내지며, 꼭지점 값들을 업데이트 하게 된다(연속적인 열들이 내려가게 된다). 이는 세 번의 superstep 을 거쳐 지속된다(붉은 색 선으로 구분됨) – cited from Apache Giraph introduction

Hadoop 기반의 graph 처리에 대한 단점 및 이를 극복하기 위한 BSP 의 도입은  Cloudera Blog 에 게시되어 있는  의 [How-to: Write and Run Apache Giraph Jobs on Apache Hadoop]  에 잘 나와 있다.

graph 처리를 위해  Map-Reduce Algorithm 을 사용할 경우, 위키피디아 페이지 간의 링크 전체의 집합과 같이 대단히 큰 Graph 처리를 하는 경우에는 데이터를 mapper 개체로 변환하여 Reducer 가 중간 결과들을 취합하여 처리하게 된다. 이때, 한 Map-Reduce 잡(Job) 이 하나의 super-step 을 처리하게 되고,  그 다음 super-step이 이전 step 의 임시 결과 까지 합친 전체 graph 구조를 하둡 파일시스템 에서 불러와서 결국 다시 저장하게 된다. 이 과정에서 전체 graph 를 불러오는 과정이 굉장히 큰 비용을 발생 시키게 된다. 물론 shuffle-sort 단계로 보내지는 임시 데이터를 처리하기 위해서도 각 노드의 worker 는 로컬 저장소를 요구하게 된다.

반면, BSP 를 이용한 경우에는 알고리즘은 graph 에 처음에 단 한번만 접근하면 되며, worker node간에는 run-time 시 만의 메시지를 주고받는 것으로 가정하며, 다만 fault-tolerant;장애 극복 작업을 위해, 중간 단계에 때때로 graph 를 저장하지만, 매 super-step 마다 실시하지는 않는다.”(아마 그래서 zookeeper 를 이용하게 되는 것으로 생각된다)

그렇다면, BSP(Bulk Synchronous Parallel model) 는 무엇인가?

위의 Girph 소개에 있는 Wekipedia 의 Graph 항목을 참고하자.

The Bulk Synchronous Parallel (BSP) abstract computer is a bridging model for designing parallel algorithms. It serves a purpose similar to the Parallel Random Access Machine (PRAM) model. BSP differs from PRAM by not taking communication and synchronization for granted. An important part of analyzing a BSP algorithm rests on quantifying the synchronization and communication needed.

bsp_abstract_model

그림2 : 1989년에 제안된 Leslie Valiant 의 BSP 추상 모델(http://www.staff.science.uu.nl/~bisse101/Book/PSC/psc1_2.pdf)

BSP 추상 컴퓨터는 평행 알고리즘을 위한 브릿지 모델이다. 이는 평행 임의 접근 머신(PRAM) 모델과 유사한 목적을 가진다. BSP 는 PRAM 과는 (작업)승낙을 위한 동기화와 통신을 하지 않는 다는 점에서 차이가 난다. BSP 알고리즘을 분석하는데 있어 중요한 점은 동기화와 통신을 정량화 여부가 필수적인가 하는 점이다.

위키피디아의 BSP 항목을 참고하면 BSP 는 다음과 같은 요소로 이루어져 있다.

  1. components capable of processing and/or local memory transactions (i.e., processors),
    로컬 메모리 트랜잭션과/또는 처리할 수 있는 능력의 (즉, processor 들)
  2. a network that routes messages between pairs of such components,
    이와 같은 경로에 따라 전달되는 메시지
  3. and a hardware facility that allows for the synchronization of all or a subset of components.
    요소의 전체 또는 부분집합의 동기화를 허용하는 하드웨어 설비

그림 3. BSP structure and superstep

BSP 는 주로 세 번째 특성에 의존하며, 모든 연산은 global superstep 에서 이루어진다.

superstep 은 다음과 같이 이루어진다고 한다.

  • 로컬 연산을 수행하는 동시연산 (Concurrent computation): 프로세스들은 로컬 프로세서의 고속 메모리로 로컬 저장된 값 만을 연산한다. 이 연산은  각 프로세스 간에 비 동기적으로 이루어지며, 통신을 통해 겹쳐진다.
  • 통신(Communication): 프로세스들은 원격 데이터 저장소의 사용 가능성을 용이하게 하기 위해 데이터를 서로 주고 받는다.
  • 장벽 동기화(Barrier synchronisation): 한 프로세스가 이 지점(장벽;the barrier)에 도달하면, 다른 모든 프로세스들이 이 장벽에 도달 할 때까지 이 프로세스는 대기한다.

위의 그림 1에서 보게 되면Giraph 를 이용한 단일 소스 최소 경로 알고리즘에 대해 기술하고 있다.

  • 최 상위 열에서 3개의 vertex 의 초기 값이 0, ∞ 그리고 ∞ 이다. Edge는 1, 3 이다.
  • 최 상위 열에서 BSP 알고리즘을 수행한다. 그리고 각각의 프로세스는 최종적으로 Barrier 에 도달하여, 이 때 첫번째 superstep 이 완료된다.(첫 번째 빨간줄)
  • 산출 된 값을 Message 값으로 전달하여  두 번째 vertex 값으로 update 한다.
  • 다시 프로세스를 진행하여 두 번째 superstep 이 완료되고, 결과 값을 message 로 세 번째 vertex 를 update 한다.

일단, 이론적으로 깊이 있는 부분은 차차 확인해 볼 생각이며 우선은 설치를 해보려 한다.

테스트 환경 – Virtual Hadoop Cluster

64-bit 환경의 4GB of RAM allocated virtual machine 을 Virtual Box 를 이용하여 다음과 같이 구성하였다.

  • HDFS: Namenode+9 data nodes
  • YARN: Resourcemanager+9  nodemanager nodes
    (Test 를 위해서는 standalone host 에서 pseudo mode 에서도 무방하다)

Software/Hardware Specifications:

  • Hardware:
    • Dual-core 2.5 GHz CPU (64-bit architecture)
    • 4GB RAM (6GB would be much better)
    • 50GB hard drive space
    • 100 Mbps NIC
  • CentOS 7.2(64-bit)
  • Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
  • Apache Hadoop 2.7.2
  • Apache Giraph 1.1.0
  • Hadoop Owner Account: hadoop:hadoop

Hadoop Cluster Setup

Hadoop 설치는 Cloudera CDH 버전을 사용하거나, Apache Hadoop 에서 다운로드 받은 설치 파일로 설치할 수 있다.

Maven Compile / Build

Giraph Building / Testing 은 다음을 참고한다: http://giraph.apache.org/build.html

이 때, Hadoop 2 (YARN Framework) 상에서 Giraph 를 운용하기 위해서는 반드시 Giraph 1.1 버전을 사용하여야 한다는 점을 유의하자.

  • Deploy
  1. giraph 소스가 위치할 폴더로 이동
  2. git(https://github.com/apache/giraph)에서 giraph 소스 다운로드
  3. 다운받은 소스를 계정으로 owner permission 을 가져온다.
  4. maven 빌드

    • maven install 을 해보면 dependancy error 가 계속 발생한다. 옵션에 주의하자
    • 자신의 시스템에 설치된 하둡 버전에 대해 Dependancy  옵션을 준다: -Dhadoop.version=2.x.x
    • Test 생략 후, build 한다. Test Skip Option 을 주지 않으면 giraph-core / giraph-kibble 또는 giraph example 에서 compile error 가 계속 발생한다: -DskipTests clean install
    • 계속 compile 이 실패하면 ~/.m2 directory 아래의 repository 및 git 에서 download 한 소스를 모두 지우고 다시 실행해 본다.
    • munge plugin 을 위해 maven 3 이상이 설치되어 있어야 하며, OSX에서는 Xcode와 연동되어 있어야 한다.
  5. 모든 Project build 가 완료되면
  6. Giraph Root 로 이동한다.
  7. bash profile(~/.bash_profile) 또는 /etc/profile.d/custom.sh 에 Giraph 환경 변수를 추가한다.
    예)
  • Test
  1. 이 예제는 giraph 를 namenode 에 설치하여 실행하는 것으로 가정한다.
  2. 입력 데이터를 준비한다.(http://giraph.apache.org/quick_start.html )
    • First, create an example graph under /tmp/tiny_graph.txt with the follwing:

      Save and close the file. Each line above has the format [source_id,source_value,[[dest_id, edge_value],...]]. In this graph, there are 5 nodes and 12 directed edges. Copy the input file to HDFS:

  3. 다음을 실행한다.(아마 오류가 날 것이다)
    • Simple Shortest Path Example 실행
    • 여기서 발생하는 오류는 Giraph Example 쪽의 source_ id 가 1로 하드 코딩 되어 있기 때문이며, 여기를 참고하여(http://stackoverflow.com/questions/27545664/giraph-tutorial-shortestpath-example-job-failing) SimpleShortestPathsComputation.java 의 해당 내용을 수정 후, 다시 maven bulid 한다.
      예제를 위한 SimpleShortestPathComputation 의 Source 파일의 위치는 다음과 같다.
      $GIRPH_HOME/giraph-examples/src/main/java/org/apache/giraph/examples/ 폴더 내의 SimpleShortestPathsComputation.java 를 수정한다.
  4. maven 빌드를 다시 수행한다.
  5. 빌드가 완료되면 다음과 같이 예제를 실행한다.
      • 이 때, YARN 서버가 별도의 위치에 있으면,-ca mapred.job.tracker=resourcemanager 과 같이 옵션을 별도로 지정할 수 있다.
      • Zookeeper 서버가 별도로 존재하면-ca giraph.zkList=zookeeper:2081 과 같이 별도 지정이 가능하다.

  • Troubleshooting
    • Exception in thread “main” org.apache.hadoop.mapred.FileAlreadyExistsException: Output directory hdfs://namenode:9000/user/hadoop/output/shortestpaths already exists:
      이 경우는 이미 출력 파일이 존재하는 경우이므로, 다음 명령으로 출력 결과를 삭제하고 다시 실행한다.


Apache Giraph –

How-to: Write and Run Apache Giraph Jobs on Apache Hadoop – http://giraph.apache.org/

http://blog.cloudera.com/blog/2014/02/how-to-write-and-run-giraph-jobs-on-hadoop/

BSP Model –

http://www.staff.science.uu.nl/~bisse101/Book/PSC/psc1_2.pdf

1,849 total views, 1 views today

댓글 남기기