대규모 그래프 처리 기술은 비즈니스 및 인공지능(AI, 예: 벡터 데이터베이스 인덱싱) 분야에서 점점 더 중요해지고 있다. GFlux는 SSD와 GPU를 활용하여 한 대의 컴퓨터에서 조 단위 규모의 그래프 처리를 가능하게 하며, 삼각형 개수 세기와 같은 복잡한 분석 연산을 지원한다.

최근 대규모의 그래프 데이터를 처리하는 기술의 중요성이 비즈니스 및 AI 분야에서 증가하고 있다. 비즈니스 분야에서는 팔란티어와 같이 기업의 데이터를 그래프로 모델링하여 운영 및 의사결정을 지능화하는 사례들이 증가하고 있고, AI 분야에서는 LLM의 환각 현상을 줄이기 위해 사용하는 벡터DB가 높은 recall을 위해 그래프 구조의 색인을 널리 사용하고 있다. 대규모 그래프 데이터를 처리하기 위해 데이터를 분할하여 여러 컴퓨터들의 메모리 적재하여 네트워크 통신을 통해 처리하는 방법을 주로 사용하지만, 그래프 규모가 커질 수록 컴퓨터 구입 비용과 네트워크 통신 비용이 급격히 증가하는 단점이 있다.

GFlux는 한 대의 컴퓨터에서 그래프 데이터를 모두 SSD에 저장하고 GPU로 그래프 연산(태스크)을 수행함으로써, 상기 비용 문제들을 근본적으로 해결한 프레임워크 기술이다. GFlux는 데이터 저장 계층, 태스크 실행 계층, 태스크 스케줄링 계층으로 구성되어 있으며, 조 단위 규모의 그래프도 효율적으로 처리하기 위해 각 계층에서 기술적 혁신이 적용되어 있다.

데이터 저장 계층에서는 그래프를 High-density hierarchical Graph Format (HGF) 라는 새로운 포맷으로 저장한다. HGF는 그래프를 출발 정점과 도착 정점의 2차원 공간으로 간주한 후, 이를 논리적으로 2²⁴ x 2²⁴ 크기의 블록으로 구성된 그리드(grid)로 분할하고, 그래프의 왜도(skewness)를 고려하여 각 블록을 물리적으로 특정 크기(예: 3GB) 이하의 샤드(shard)로 분할하는 2단계 분할 방식을 적용한다. 이 방식은 각 블록 내 정점 ID를 기존의 최대 8바이트 대신 3바이트 주소체계로 표현할 수 있게 하여 데이터 압축 효과를 제공한다. 또한, GPU에서 3바이트 주소가 유발하는 메모리 정렬 문제를 해결하기 위해, GFlux는 Flip24라는 새로운 3바이트 주소체계를 제안한다.

태스크 실행 계층에서는 PageRank, 삼각형 개수 세기와 같은 그래프 연산을 GPU에서 효율적으로 실행할 수 있도록, 이를 GTask라는 단위 작업으로 정의한다. GTask는 연산을 실행하는 GPU 커널 함수, 입력 샤드, 각 샤드에 포함된 정점들의 입력 및 출력 속성, 그리고 태스크 실행 중 생성되는 중간 데이터로 구성된다. 예를 들어, 삼각형 개수 세기 연산은 서로 연결된 세 개의 정점으로 구성된 삼각형 형태의 관계를 모두 찾아 개수를 세는 작업으로, 데이터 분석 및 인공지능에서 널리 활용된다. 이 연산에 대한 GTask는 세 개의 샤드 (S_v, S_p, S_h) 트리플을 입력으로 받아, 해당 트리플 내의 모든 삼각형을 GPU 커널 함수를 통해 빠르게 구한다. 이 과정에서 입력 샤드와 중간 데이터를 메인 메모리와 GPU 메모리 간에 효율적으로 관리하고 전송하기 위해, GFlux는 새로운 메모리 관리자 기술을 제안한다.

태스크 스케줄링 계층에서는 대규모 그래프에 대해 주어진 연산을 효율적으로 수행하기 위해 GTask를 스케줄링하고 최적화한다. 예를 들어, PageRank 연산의 경우 블록 그리드를 컬럼 방향으로 접근하여 PageRank 값을 집계(aggregation)하는 것이 효율적인 것으로 알려져 있으므로, 컬럼 단위로 GTask를 스케줄링한다. 반면, 삼각형 개수 세기 연산에서는 가능한 모든 샤드 트리플을 탐색하되, 삼각형이 존재하지 않는 트리플은 사전에 제외하고, SSD 접근 횟수를 최소화할 수 있도록 샤드 트리플의 순서를 조정하는 ‘3-홉’이라는 새로운 방식으로 스케줄링한다. 특히, 제안하는 최적화 기법은 삼각형이 존재하지 않는 트리플을 스케줄링 대상에서 완전히 제외할 수 있음을 이론적으로 증명한다.

GFlux는 1조 간선 규모의 그래프를 HGF 포맷으로 약 4.6TB 크기로 압축 저장할 수 있으며, 이는 기존 표준인 CSR 포맷에서 동일한 그래프가 9TB인 것과 비교해 절반 수준으로 공간을 절약한다. 또한, GFlux는 1조 간선 규모의 그래프에 대한 PageRank 연산을 약 1,300초 만에 완료했으며, 약 700억 간선 규모의 그래프의 삼각형 개수 세기 연산을 1,184초 만에 처리하는데 성공했다. 이는 단일 컴퓨터에서 삼각형 개수 세기 연산을 성공적으로 수행한 사례 중 현재까지 알려진 최대 규모의 그래프이다. 특히 기존 최고 성능 기록은 고속 네트워크로 연결된 CPU 서버 25대를 사용하여 약 2,000초가 걸린 반면, GFlux는 단일 머신에서 이보다 약 두 배 빠른 속도를 달성했다.