개인적인 관심사가 machine learning인지라 평소에 주로 map/reduce를 사용한 mahout을 이용해 필요한 알고리즘들을 사용하곤 했다. 요사이 매달리고 있는 matrix factorization문제를 해결 하려고 시도하다가 알게 된 점 들을 몇자 적어본다.
mahout을 너무너무 잘 쓰고는 있지만 몇가지 map/reduce model의 근본적인 문제를 계속 마주치게 되는데, 첫 째로 iterative job처리가 inefficient하다는 것이다.
Iterative job을 map/reduce로 구현 할 때의 문제를 좀더 자세히 들여다보면 아래와 같다.
위 그림에서 눈여겨 볼 inefficient 한 곳은 두 가지 이다.
- 하나의 iteration내에서도 처리해야 할 데이터가 특정 CPU(computing resource)으로 몰려서 partition될 경우 다른 CPU들은 기다리는 lagging이 발생한다. 실제로 사용자 log graph들은 많은 수의 edge를 가지는 몇개의 vertex들을 가지는 경우가 흔하고, 이런 vertex들이 bottle neck 으로 작용한다.
- 매 iteration마다 발생하는 barrier부분에 disk IO와 startup cost가 있다. map only job이 # iteration만큼 hdfs에서 input을 읽고, 결과를 hdfs에 쓰는 overhead가 있다.
이를 그림으로 표현 하면 아래와 같다.
이러한 iterative한 job을 효율적으로 처리하기 위해 나온 것들이 구글의 pregel이고 이와 비슷한 framework로 apache Giraph, Hama가 있다(꼭 iterative job만을 위한건 아님, 뒤에 설명).
이중에서 사용해 본 Giraph로 간략히 설명을 하면(자세한 설명), map only잡을 한번 submit하고, map only job에서 여러벌의 worker와 master를 생성한다. 이 master는 각각의 worker에 partition ownership을 부여하고, vertices를 partitioning한다.
각각의 worker는 자신에게 속한 vertices들에대해 compute를 하고 barrier에서 sync한다(iteration횟수만큼 반복).
map/reduce와 달리 hadoop의 startup penalty를 한번으로 줄이고, 각각의 superstep(iteration)의 결과들을 hdfs가아닌 memory에 들고 있어 다음 superstep에서 훨씬 빠른 access가 가능하다.
둘째로 interdependent computation(graph-parallel algorithm)은 not map-reducible하다.
조금더 일반화 하자면 많은 수의 machine learning algorithm들은 다음과 같은 property를 갖는다.
현재 vertex X3의 computing을 위해서 X3의 neighbor들의 value들이 필요한 경우가 많은데 이는 mapper끼리 통신이 불가능한 map/reduce model에서는 처리 하기 힘들다.
label propagation algorithm(graph-parallel algorithm)을 예로 그 일반적인 특성을 보자.
실제로 belief propagation같은 algorithm은 mahout의 DistributedRowMatrix를 이용하여 matrix로 바꿔서 생각하면 구현 자체는 쉽게 할 수 있다. 하지만 matrix형태로 생각하는 게 intuitive하지도 않고, 위에서 말한 첫번째 이유에 의해서도 map/reduce말고 다른 computing model을 찾게 된다.
여기서 이 포스트의 주인공인 Graphlab이 등장하게 된다.
위에서와 같이 machine learning algorithm을 data-parallel과 graph-parallel로 구분 했을 때 Graphlab은 Graph-parallel algorithm에 특화된 framework이다.
살짝 중간 정리를 하자면, map/reduce가 key, value pair에 map/reduce라는 computation을 정의 하는 framework였다면 Graphlab은 graph상의 vertex node에 gatter, apply, scatter라는 computation을 정의 하는 framework이다.
살짝 중간 정리를 하자면, map/reduce가 key, value pair에 map/reduce라는 computation을 정의 하는 framework였다면 Graphlab은 graph상의 vertex node에 gatter, apply, scatter라는 computation을 정의 하는 framework이다.
이 framework에서는 각각의 vertex는 사용자가 정의 한 vertex-program을 통해 필요한 computing을 하는데 이때 neighbor vertex들의 상태값 뿐만아니라 다른 vertex의 상태 값들도 mpi를 통해 얻어 오는 api가 제공 된다.
다른 말로 위에서 말한 sparse data dependencies는 graph를 통해, local updates는 vertex-program를 통해 만족된다.
이는 사실 위에서 언급한 Pregel(Giraph, Hama)과 거의 흡사하다. 차이점이라면 pregel은 각각의 vertex-program이 message를 통해 interact하고, Graphlab은 각각의 program이 dependencies가 있는 서로의 state를 access할 수 있다는 점이다.
무슨 소리인가? 아래를 보자.
여기서 가장 중요한 점은 asynchronously이다. 위에서 설명 했던 BSP model와의 가장 큰 차이점은 바로 이 asynchronous한 execution이다. Graphlab은 이런 asynchronous update를 scheduling하면서 consistency를 보장해 주는데, 이를 위해 아래와 같이 scope rule이라는 개념을 가진다.
결론적으로 vertex consisitency가 가장 parallel하고, full consistency가 가장 non-parallel하다. 알고리즘 별로 어떤 scope rule이 필요한지 정의하면 framework이 race condition과 deadlock이 발생하지 않도록 보장해준다.
version1(shared memory)에서는 데이터가 커지면 memory도 커져야 했었지만, version 2부터는 distributed version으로 이런 제약이 없어졌고, HDFS를 input/output으로도 사용할 수 있게 되었다. 또 매우 다양한 algorithm들을 toolkit으로 제공하고 있어서 당장 사용해 볼 수 있다는 장점도 있다.
자세한 내용은 http://graphlab.org/에서 꼭 살펴보길 바란다.
http://videolectures.net/nipsworkshops2010_guestrin_kml/는 SELECT lab에서 NIPS2010에 발표한 video이다.
reference:
TODO:
- Graphlab과 mahout을 benchmark 해본 결과 정리
- MPI + Graphlab setup tutorial
- Giraph 자세한 설명 페이지 정리
