"1조개 규모 그래프 알고리즘도 PC에서 개발"

[아이뉴스24 최상국 기자] KAIST 전산학부 김민수 교수 연구팀은 그래프 데이터에 기반한 서비스 알고리즘 개발시 대규모 컴퓨팅 자원이 없어도 한 대의 PC만으로 알고리즘을 시험할 수 있는 기술을 개발했다고 23일 발표했다.

연구팀이 선보인 기술은 '그래프 프로세싱 시뮬레이션'이라는 개념이다. 이 기술은 그래프 데이터를 실제로 메모리에 저장하지 않고도 마치 데이터가 저장돼 있는 것처럼 알고리즘을 실행할 수 있게 해 준다. 1조 개 간선(edge)의 초대규모 그래프를 PC 한 대로 처리할 수 있는 'T-GPS(Trillion-scale Graph Processing Simulation)' 기술이다.

그래프 데이터란 일종의 '관계'를 나타내는 데이터를 말한다. A라는 데이터와 B라는 데이터가 있다면 A와 B 사이의 관계를 나타내는 데이터도 존재한다. 그래프 DB에서는 이를 정점(vertex)과 간선(edge)이라는 개념으로 표현한다. SNS의 친구관계, 좋아요한 페이지, 시청한 유튜브 영상 등이 모두 그래프 데이터다. 내가 정점(vetex)이라면 내가 SNS에서 활동한 내용은 간선(edge)이라 할 수 있다. 구글이 검색결과 페이지를 '중요도' 순으로 정렬해 보여주는 '페이지랭크'가 대표적인 그래프 알고리즘이다.

따라서 그래프 데이터는 서비스 규모에 따라 어마어마하게 크고 수시로 변한다. 그래프 데이터를 활용해 친구를 추천하고 개별 취향에 맞게 컨텐츠를 구성해 보여주는 등의 서비스를 하기 위해서는 이를 처리할 알고리즘을 개발하고 실제 환경에서 테스트해야 하지만, 실제 데이터를 활용하기 위해서는 방대한 규모의 컴퓨터 클러스터가 필요하다.

KAIST 연구팀이 개발한 'T-GPS'는 그래프 데이터를 실제로 디스크에 저장하지 않고도 마치 그래프 데이터가 저장돼 있는 것처럼 알고리즘을 계산할 수 있다. 계산 결과도 실제 저장된 그래프에 대한 알고리즘 계산과 완전히 동일하다는 장점이 있다.

그래프 알고리즘은 그래프 처리 엔진 상에서 개발되고 실행된다. 이는 산업적으로 널리 사용되는 SQL 질의를 데이터베이스 관리 시스템(DBMS) 엔진 상에서 개발하고 실행하는 것과 유사한 방식이다. 그래프 데이터상에서 그래프 알고리즘이 계산을 위해 접근하는 그래프 데이터의 정점 및 간선들을 실시간 및 임시(on-the-fly) 방식으로 생성, 결과적으로 실제 저장된 그래프에 대한 알고리즘 실행과 완전히 똑같은 결과를 낼 수 있는 것이다.

연구팀은 T-GPS 기술을 기존의 방법과 성능을 비교한 결과, 기존 방법은 11대의 컴퓨터로 구성된 클러스터에서 10억 개 간선 규모의 그래프를 계산할 수 있었던 반면, T-GPS 기술은 1대의 컴퓨터에서 1조 개 간선 규모의 그래프를 계산할 수 있어 컴퓨터 자원 대비 1만배 더 큰 규모의 데이터를 처리를 할 수 있으며 알고리즘 계산 시간도 최대 43배 더 빠름을 확인했다고 밝혔다.

연구팀은 대규모 컴퓨팅 자원을 보유하지 못한 중소 벤처 기업들이 그래프 데이터 기반의 서비스를 개발할 때, 저비용으로 빠르게 서비스를 개발할 수 있도록 도와줄 것으로 기대하고 있다.

특히 서비스에 사용되는 그래프 데이터가 매우 커질 때 현재의 알고리즘이 어떤 성능상의 문제를 가질지, 어떤 다른 알고리즘을 사용해야 그 문제를 해결할 수 있을지 미리 알기 어렵지만 T-GPS 기술을 사용하면, 초기 서비스에서 확보된 매우 소규모의 그래프 데이터와 서비스 중인 알고리즘을 입력으로 넣어주고 시뮬레이션 함으로써, 서비스 운영에 따른 그래프 데이터가 증가할 때 현재 알고리즘이 어떤 성능을 낼지 PC 1대만으로도 매우 쉽게 정확히 계산할 수 있다고 설명했다.

이 연구는 한국연구재단 선도연구센터사업 및 중견연구자 지원사업, 과기정통부 IITP SW스타랩 사업의 지원을 받아 수행됐다. 김 교수의 제자이자 캐나다 워털루 대학에 박사후 연구원으로 재직 중인 박힘찬 박사가 제1저자로, 김 교수가 교신저자로 참여했으며 지난 22일 그리스 차니아에서 온라인으로 열린 데이터베이스 분야 최고 국제학술대회 중 하나인 IEEE ICDE에서 발표됐다. (논문명 : Trillion-scale Graph Processing Simulation based on Top-Down Graph Upscaling)