아침놀 Blog

Daybreakin Things

7 Entries : Results for 수업

PageRank 구현하기

Posted
Filed under 만들어내기

이번 학기에 듣는 문수복 교수님의 분산처리특강 프로젝트로 그 유명한 PageRank를 구현하였다. (혹시나 모르시는 분들을 위해 살짝 덧붙이면 Google 검색 엔진의 기초가 되는 웹페이지 중요도 판단 알고리즘이다) Google의 창업자 세르게이 브린과 래리 페이지가 썼던 PageRank 논문을 바탕으로 크기가 수백~수천만 단위인 sparse 행렬과 벡터의 곱셈을 계산하기 위해 matrix 계산 방식을 바꾼 power method를 활용하여 Hadoop 기반 MapReduce 방식으로 구현하였다.

특히 이번 수업에서는 여름방학부터 9월까지 NexR에서 인턴하면서 개발한 CCI:U Open CourseLabs (오픈소스 프로젝트도 참조) 및 KAIST 클라우드 컴퓨팅 테스트베드를 활용하여 작년에 했던 같은 수업보다 좀더 넉넉한 환경에서 쓸 수 있었다. 학과 자체에서도 가상화 클러스터를 만든 게 있어서 40코어 / RAM 32GB * 5 정도를 사용하고 여기에 CCI:U 클러스터는 48코어 / RAM 2GB * 48 규모로 함께 사용하였다.

PageRank에 대해 간단히 설명하면, 이전까지의 웹 검색은 키워드를 입력하면 그 키워드와 웹문서들을 분석하여 연관성이 높은 것을 뽑아주는 것이 기본 아이디어였지만 PageRank는 웹문서들 사이의 연결 관계를 주목했다는 점이다. 웹을 이루는 네트워크의 구조 자체를 랭킹에 포함시킨 것은 혁신적인 발상이었다. 원래 개념은 어떤 페이지에서 다른 페이지로 나가는 링크를 이용해 그 링크된 문서들의 PageRank 값을 그 각각이 가진 링크의 개수로 나눈 것을 모두 더한 것이 자신의 PageRank가 되는 것이다. 정의를 잘 살펴보면 상호 의존적인 정의이기 때문에 바로 값을 구할 수는 없다는 것을 알 수 있는데, 처음에 임의로 값을 초기화하고 몇 가지 조건을 더 고려하여 이 계산을 계속 반복해서 돌리면 어떤 값에 수렴하게 할 수 있고 그 결과가 PageRank 순위가 되는 것이다. 수학적으로는 연결 관계를 정의하는 거대한 행렬(행과 열의 개수가 인덱싱한 문서의 개수와 같은...)과 그 행렬과 곱해질 크기의 벡터를 이용하여 위 내용을 수식으로 표현할 수 있고, 이 거대한 행렬을 효과적으로 분산처리하기 위해 power method(링크된 글의 맨 끝 식이 실제로 사용한 것)라는 것을 이용한다.

NexR에서 인턴하면서 이런저런 실습을 하기도 했었고 MapReduce에 어느 정도 익숙하였기 때문에 처음 예상으로는 한 5일이면 되겠다 싶었는데, 웬걸 열흘이 넘게 걸려버렸다. 대상 데이터는 위키백과에서 XML 형식으로 제공되는 dump였는데 총 20GB 분량을 200여개의 파일로 나누어 놓은 것이었다. 알고리즘 구현은 4일 만에 끝났지만 최적화와 디버깅에만 3일이 넘게 걸렸고, 프로젝트 듀가 있던 주말에는 CCI:U 클러스터의 각 노드가 로그 파일로 인해 디스크가 꽉 차는 문제가 발생하여 이를 해결하느라 과제 진행을 못하기도 했다. PageRank 특성 상 어느 정도 수렴할 때까지 계속 반복(iteraion)해야 하는데 처음 짠 버전은 한 번 도는 데 6시간(!)이 넘게 걸렸지만 온갖 최적화와 삽질 끝에 완성한 최종 버전은 불과 2분밖에 걸리지 않았다. (좀 심하게 어이없는 버그가 하나 있었다. 돌아갔던 게 더 신기하달까 싶은...-_-) 허나 거기서 끝난 게 아니라 실제 검색엔진처럼 웹 상에서 키워드 입력하면 결과를 볼 수 있게 만들어야 하는데 결과로 나온 PageRank 벡터 및 문서 ID와 제목의 mapping 등을 DB에 올리는 과정에서 워낙 큰 용량으로 인해 몇 시간씩 돌렸던 것이 중간에 깨지고 버그로 중단되는 등 추가로 하루를 더 소요하였다.

참고로 위키백과의 각종 meta page와 redirection page들을 제외하고 총 3백만개가 약간 넘는 양의 문서에 대한 link graph와 PageRank를 계산하였다. 첨부한 파일은 처리한 데이터를 바탕으로 상위 100개의 페이지들을 모아본 것으로, 주로 나라·지명·년도가 많은 링크가 걸리고 있음을 확인할 수 있다. (좀 예전 데이터를 바탕으로 했기 때문에 현재의 위키백과하고는 다소 다를 수 있음) 원래는 iteration을 적어도 20~30회 이상은 돌려야 하지만 시간 부족 관계로 10번만 돌렸기 때문에 좀 부정확할 수도 있다.

상위 100개 보기

중간에 missing title이라고 된 것은 Redis라는 key-value storage를 검색엔진 구현에 사용하다가 너무 많은 데이터(대략 레코드 수 560만개?)가 들어가니 32bit 메모리 영역을 초과하여 더 이상 들어가지 못해 발생한 것이다. 문제는 이 프로젝트 때문에 지난 주와 이번 주 내내 거의 아무것도 못하고 밤샘하다가 수업을 5차례나 째는(...) 로드가 걸렸다는 것. 작곡 2번, 로보틱스 2번, 분산처리 1번...; ㅠ_ㅠ

PageRank 논문을 보면 1999년 당시 사용한 페이지 수가 7천5백만개였으니 내가 해본 데이터 크기가 대략 이것의 4% 크기인데, 그때와 지금의 컴퓨터 성능 차이를 생각해보면 Google이 얼마나 대단한지 알 수 있다. 3백만개의 원소를 가지는 벡터 2개 정도는 대충 1GB 메모리에 다 올려놓고 계산해버릴 수 있지만 저 정도 되면 논문에서 이야기한 것처럼 여러 pass에 걸쳐 계산하도록 만들어야 할 것이다.

어쨌든 이번 프로젝트를 통해 대용량 데이터를 다루는 작업이 얼마나 어려운지--조금만 실수해도 몇시간 분량의 작업을 날려먹으니--뼈저리게 깨달을 수 있었고, 또한 어떤 점들을 조심해서 짜야 하는지, Hadoop 사용·설정 노하우 등을 얻을 수 있었다. 3명이서 팀으로 하는 기말프로젝트 proposal로는 GPU 가속을 이용한 행렬 연산과 MapReduce programming model의 결합에 관한 아이디어를 발표했는데 이건 또 얼마나 삽질을 하게 될런지 모르겠다. ㅠ_ㅠ

덧: 교수님이 왤케 자꾸 밤새면서 작업하냐고 물으시길래 '연속적으로 집중할 수 있는 시간'을 확보하기 위한 거라고 말씀드렸다. 학생들끼리 같이 무얼 해보려고 해도 보통 낮에는 시간이 안 맞는 경우가 많아 밤에 뭘 하는 경우가 많다보니 낮엔 각자 다른 일을 하고 밤에 모여있는 것이 습관화되어 어쩔 수 없이 생활리듬도 그렇게 바뀌어가는 듯하다. 하는 일을 줄이면 괜찮을 텐데 새로운 일을 추가하지 않아도 이미 있는 일들만으로도 충분히 빡센 것도 문제인 듯.