일반 컴퓨터 1대로 대용량 그래프 데이터를 처리하는 그래프 엔진
일반 컴퓨터 1대로 대용량 그래프 데이터를 처리하는 그래프 엔진
  • 한욱신 / 창공 교수
  • 승인 2013.10.16 11:36
  • 댓글 0
이 기사를 공유합니다

학술 - 터보그래프
최근 들어 트위터, 페이스북 등 소셜 네트워크 서비스(SNS)의 사용이 증가하면서, 대용량의 그래프 데이터를 효율적으로 처리하는 연구가 주목을 받고 있다. 그래프는 노드(node)와 에지(edge)로 구성되는 자료 구조로서, 소셜 네트워크 서비스뿐만 아니라 화합물, 단백질 구조 등과 같은 다양한 종류의 데이터를 표현하기 위해 사용되고 있다. 예를 들면, 소셜 네트워크에서는 사람이 노드에 대응되고 에지는 사람들 사이에 친구 관계가 있음을 나타낸다. 생명공학에서의 예를 들면, 단백질이 노드에 대응되고 단백질 사이의 상호작용이 에지로 표현된다. 또 하나의 예는, 인터넷에서 웹 페이지가 하나의 노드에 대응되고, 웹 페이지 내에 있는 링크가 하나의 에지가 될 수 있다. 이처럼, 현재 인간 사회에서 다루는 모든 복잡한 데이터들은 이런 그래프로 표현할 수 있다.
터보그래프는 그래프로 표현되는 데이터들에 대한 연산을 지원하기 위해 개발한 고성능의 그래프 엔진이다. 사용자는 터보그래프를 사용하여 여러 가지 다양한 응용들을 구현할 수 있다.

SNS의 검색 원리 및 고성능 컴퓨터의 활용
소셜 네트워크 서비스가 제공하는 주요한 기능들은 그래프에 대한 연산으로 처리될 수 있다. 이러한 기능 중 대표적으로 하나로 친구의 친구를 소개해 주는 기능이 있는데, 이는 그래프 연구 쪽에서 나의 친구의 친구가 나의 친구가 되는 삼각형 구조로 표현할 수 있다. 최근에는 사용자의 공개된 취미나 성향까지 비슷한 친구를 소개해 주는 기능이 소셜 네트워크 서비스로 추가되고 있다.
그런데 페이스북과 같은 소셜 네트워크 서비스는 사용자의 수가 매우 많아서, 이러한 기능들을 많은 사람에 대해 효율적으로 처리하기 위해 수백 대의 컴퓨터 혹은 서버를 고속 네트워크로 연결한 클러스터라는 장비를 사용하여 병렬로 기능들을 처리하고 있다. 클러스터 기반의 고성능 컴퓨터는 고가의 네트워크 장치를 설치하고 클러스터를 유지해야 하므로 비용이 매우 크게 들게 된다. 이에 반해 터보그래프는 SSD(Solid State Drive)와 멀티 코어 CPU(Center Process Unit)가 장착된 일반적인 컴퓨터 1대만을 사용하여 이러한 연산을 처리할 수 있어, 비용을 크게 절감할 수 있다.
[그림 1]은 터보그래프의 아키텍처를 나타낸다. 터보그래프는 빠른 그래프 저장과 액세스를 보장하기 위해 고속의 버퍼 관리자를 장착한 그래프 저장 엔진을 탑재하고 있다. 이는 이미 읽힌 그래프 일부를 메모리상에서 유지하고 있어, 사용자에게 빠른 그래프 검색을 제공하게 된다. 그리고 그래프 연산의 속도를 향상하기 위해서 엔진 수준의 그래프 프리미티브를 제공하고 있다. 이를 위해 병렬 넓이 우선 탐색을 기본 엔진 연산자로 제공한다. 특히 최근에는 핀-슬라이드라는 새로운 계산 모델을 제공하여 행렬과 벡터의 곱을 빠르게 계산할 수 있도록 확장되고 있다.
그리고 벡터의 크기가 메모리에 저장할 수 없는 규모로 커질 수 있기 때문에 이를 효과적으로 처리하는 방법을 제공하고 있다. 이렇게 함으로써 아무리 큰 그래프 데이터에 대한 처리도 터보그래프 내에서 효과적으로 지원될 수 있도록 설계가 되어 있다.

일반 컴퓨터 1대로 고성능 컴퓨터보다 더 빠르게 그래프 데이터를 처리하는 터보그래프
터보그래프는 주위에서 흔히 볼 수 있는 일반적인 컴퓨터에 장착된 고속 병렬 장치들의 능력을 100% 활용함으로써, 수십~수백 대의 컴퓨터를 이용하여 대용량의 그래프 데이터를 처리하는 클러스터 기반의 고성능 컴퓨터보다 더 빠르게 그래프 데이터를 처리한다. 터보그래프에서 활용하는 SSD는 우리나라의 삼성, 하이닉스에서 개발하고 있는 고속의 저장 매체로, 최근에 나오는 노트북에는 다 탑재되어 있다. CPU 하나에 여러 개의 계산 장치, 즉 코어를 장착하는 멀티 코어 CPU 역시 일반적인 데스크톱 PC나 노트북에서 널리 사용되고 있는 CPU 타입이다. 이는 터보그래프를 활용하면 고가의 시스템인 클러스터를 사용하는 비용이 일반적으로 누구나 구매할 수 있는 일반 컴퓨터 1대 수준으로 절감된다는 것을 의미한다.
더불어 응용에 따라 다소 차이가 있으나, 터보그래프는 성능 측면에서도 기존 시스템에 비해 수십에서 최대 수천 배에 이르는 성능 향상을 이루어냈다. 이는 SSD에서 제공하는 병렬 데이터 접근 기능과 멀티 코어에서 제공하는 병렬 데이터 계산 기능 두 가지를 쉼 없이 100% 동작하도록 알고리즘을 설계하고 구현함으로써 현실화되었다. 터보그래프에 대한 연구 결과는 데이터마이닝 분야의 최우수 국제 학술대회인 ‘KDD(Knowledge Discovery and Data Mining) 2013’에 발표되었는데, 트위터 사용자의 공개된 데이터를 활용하여 실험한 결과, 분 단위로 실험 결과를 보고할 수 있었다.
터보그래프의 성능 측면의 우수성을 입증하는 다른 예로 페이지랭크(PageRank) 연산을 처리하는 성능을 들 수 있다. 구글 사에서 사용하고 있는 기술인 페이지랭크는 그래프에서 각 노드의 중요도를 계산하는 계산량이 많은 기법이다. 최근 발표된 논문을 보면 트위터 데이터에 대해 100대의 컴퓨터를 사용하여 13분 만에 페이지랭크를 계산하는 반면, 터보그래프는 일반 컴퓨터 1대만을 사용하여 3.7분 만에 페이지랭크 값을 계산하여, 최근 발표된 논문의 결과보다 약 4배 빠른 성능을 보였다.
[그림 2]는 트위터 데이터에 대해 그래프 연산의 종류별로 터보그래프와 현재까지 단일 PC 상에서 제일 빠르다고 알려진 GraphChi의 성능 비교 결과이다. 참고로, GraphChi는 카네기멜론대에서 개발하여 작년 운영체제 분야의 최상위 학회인 OSDI(Operating Systems Design and Implementation)에 발표한 기법이다. 그래프 일부만을 액세스하는 타겟 질의에 대해서는 터보그래프가 수천에서 만 배 이상까지도 우수한 성능을 보였으며, 그래프를 모두 액세스하는 글로벌 질의에 대해서도 수십에서 수백 배의 우수한 성능을 보임을 알 수 있다.

터보그래프의 활용
터보그래프는 그래프로 표현될 수 있는 데이터를 다루는 모든 영역에서 활용할 수 있다. 구체적으로 마케팅 분야에서 널리 활용되고 있는 시스템으로서 △사람들에게 영화, 음악, 책 등 콘텐츠 이용을 제안하는 추천 시스템 △웹 페이지의 검색 결과를 중요도에 따라 순서대로 출력하기 위해, 웹 페이지의 중요도를 계산하여 순위에 활용하는 웹 검색 시스템 △생명 공학에서 단백질 간의 상호작용 관계를 활용하여 질병을 분석하는 시스템 △뇌 과학에서 뇌의 특정 부분과 다른 부분들 간의 발현 현상을 살펴보는 시스템 등 우리 생활에서 직접적으로 혹은 간접적으로 영향을 주는 많은 실용적인 시스템에서 활용할 수 있다.
단기적인 계획으로는 10월 말에 실리콘 밸리의 구글, IBM, HP Labs, 오라클 등의 세계적인 IT 회사들을 방문하여 터보그래프의 우수성을 홍보할 계획이다. 또한, 재정적 지원이나 우수 연구원 유치 등의 노력을 통해 터보그래프의 기술적 향상과 상용화를 위해 노력할 예정이다.