기술 요약: GraphFlash

문제 정의

그래프 처리 시스템은 복잡한 관계를 가진 대규모 데이터를 분석하는 데 필수적이지만, 기존 프레임워크는 동적 환경에서 상당한 한계에 직면해 있습니다. 전통적인 분산 시스템 (예: Giraph, GraphScope) 은 정적으로 프로비저닝된 클러스터에 의존하여, 워크로드가 돌발적이거나 불규칙할 경우 탄력성 부족, 자원 미활용, 그리고 높은 운영 비용으로 이어집니다.

서버리스 컴퓨팅은 자동 확장 및 세분화된 과금 방식을 제공하지만, 근본적인 아키텍처 불일치로 인해 그래프 처리에 적용되는 데 방해가 되어 왔습니다. 그래프 알고리즘은 본질적으로 상태를 유지하며 반복적이지만, 서버리스 함수는 상태가 없고 수명이 짧으며 일시적인 저장소에 의존합니다. 결과적으로 기존 서버리스 그래프 시스템 (예: Graphless, FaaSGraph) 은 다음과 같은 문제점을 겪습니다:

• 비효율적인 상태 관리: 함수 호출 간에 정점 및 간선 상태를 유지하기 위해 외부 저장소에 대한 과도한 의존.
• 높은 통신 오버헤드: 파티션 간 세분화된 메시지 전달로 인한 상당한 지연 시간 발생, 특히 외부 키 - 값 (KV) 저장소와 상호작용할 때 두드러짐.
• 자원 제약: 콜드 스타트, 함수 내부 메모리 제한, 그리고 멀티코어 병렬성을 효과적으로 활용하지 못함.
• 확장성 문제: 단순한 적응 방식은 종종 서버리스 원칙 (예: 공동 위치 컨테이너 요구) 을 희생하거나 자원 제약 하에서 효율적으로 확장하지 못함.

방법론

GraphFlash 는 서브그래프 중심 실행 모델과 표적 시스템 수준 최적화를 통해 이러한 한계를 극복하도록 설계된 완전한 서버리스 탄력적 그래프 처리 프레임워크입니다.

핵심 아키텍처

• 서브그래프 중심 모델: 정점 중심 접근법과 달리 GraphFlash 는 파티션 (서브그래프) 을 계산 단위로 처리합니다. GRAPE 프로그래밍 모델을 활용하여 두 가지 핵심 API 를 정의합니다: PEval(초기화) 및 IncVal(증분 업데이트).
• MaaS 를 통한 상태 없는 실행: 모든 처리는 상태 없는 함수 내에서 발생합니다. 외부 "메모리 - 서비스 (MaaS)"시스템 (메타데이터용 Dragonfly, 데이터용 MinIO/S3 등) 이 데이터 지속성 및 함수 간 통신을 처리합니다.
• 실행 모드: GraphFlash 는 자원 가용성에 적응하기 위해 두 가지 모드를 지원합니다:
  • 회전 모드 (Rotating Mode): 자원 제약 환경에 설계됨. 단일 워커가 여러 파티션을 순차적으로 처리하며, 매 슈퍼스텝마다 MaaS 에서 데이터를 로드합니다. 유휴 시간을 최소화하기 위해 사전 로드 최적화를 적용합니다.
  • 고정 모드 (Pinned Mode): 충분한 자원을 가진 고성능 시나리오에 설계됨. 각 파티션은 전용 함수에 "고정"되어 반복적인 파티션 로드 및 콜드 스타트 지연을 제거합니다. 워커는 슈퍼스텝 간에 메시지만 가져옵니다.

주요 최적화

서버리스 특유의 병목 현상을 해결하기 위해 GraphFlash 는 세 가지 주요 최적화를 도입합니다:

1. 파티션 인식 키 집계: 각 정점 업데이트를 별도의 키 - 값 작업 (O(V) 복잡도) 으로 처리하는 대신, GraphFlash 는 특정 파티션으로 향하는 업데이트들을 단일 페이로드로 집계합니다. 이로써 워커당 I/O 작업 횟수가 O(V) 에서 O(P)(여기서 P 는 파티션 수) 로 감소하여 MaaS 와의 통신 오버헤드를 크게 줄입니다.
2. 함수 내부 파티션 공동 위치: GraphFlash 는 단일 함수 인스턴스가 멀티스레딩을 통해 여러 파티션을 동시에 처리할 수 있도록 합니다. 이 접근 방식은 다음과 같은 이점을 제공합니다:
   • 경계 정점 데이터를 공유하고 중복 저장을 방지하여 메모리 소비 감소.
   • 파티션 내부 업데이트에 대한 직접 메모리 접근을 가능하게 하여 Bulk Synchronous Parallel (BSP) 장벽까지 외부 동기화를 지연.
   • 함수 수준에서 메시지를 집계; 정점이 여러 공동 위치 파티션에 이웃을 가진 경우, 여러 파티션으로 여러 메시지를 보내는 대신 워커로 단일 메시지를 전송.
3. 슈퍼스텝 인식 활성화: 서버리스 환경에서 세분화된 활성화 확인이 비용이 많이 든다는 점을 인식하여, GraphFlash 는 사용자가 특정 슈퍼스텝 이후에 정점 활동 확인을 활성화할 수 있도록 합니다. 이는 대부분의 정점이 활성화된 알고리즘 초기 단계에서의 불필요한 메시지 전달을 방지합니다.

추가 최적화로는 네트워크 병목 현상을 완화하기 위한 JSON 대체를 위한 이진 직렬화, Zstandard 압축, 그리고 메시지 배칭이 포함됩니다.

주요 기여

1. 완전한 서버리스 프레임워크: GraphFlash 는 탄력적 자원 사용을 가진 상태 없는 서브그래프 중심 처리를 지원하는 실용적인 시스템으로, 성능과 비용을 균형 있게 조절하기 위해 회전 모드와 고정 모드를 도입했습니다.
2. 서버리스 병목 현상 해결: 이 논문은 그래프 워크로드에 대한 서버리스 플랫폼의 근본적인 한계를 식별하고 해결하며, 특히 함수 내부 멀티코어 병렬성을 가능하게 하고 파티션 인식 집계를 통해 통신 오버헤드를 줄입니다.
3. 종합적 평가: 시스템은 Knative 및 AWS Lambda 상에서 다양한 그래프 알고리즘 (BFS, PageRank, CDLP, WCC) 과 데이터셋 (61K 에서 434M 개의 정점까지) 에 걸쳐 평가되었으며, 파티셔닝, 실행 모드, 그리고 동시성의 영향을 체계적으로 분석했습니다.

실험 결과

평가 결과 GraphFlash 는 기존 서버리스 호환 시스템보다 현저히 우수하며, 특정 조건 하에서는 전통적인 분산 프레임워크와 동등한 성능을 보임을 입증했습니다:

• 서버리스 시스템 대비 성능: Graphless 와 비교할 때, GraphFlash 는 실행 시간에서 최대 127 배의 속도 향상 (예: CDLP 알고리즘 기준) 을 달성했으며, 고자원 구성에서는 자원 소비를 최대 98% 감소시켰습니다. 자원 제약 환경 (단일 768MB Lambda 함수) 에서도 Graphless 대비 최대 48 배 속도 향상 및 99.97% 비용 절감을 달성했습니다.
• 전통적 시스템 대비 성능: 대규모 워크로드에서 GraphFlash(고정 모드) 는 GraphScope 및 FaaSGraph 와 같은 고성능 분산 프레임워크와 비교 가능한 실행 시간을 달성하면서도 완전한 서버리스 호환성을 유지합니다.
• 확장성: 시스템은 최대 42 억 3 천만 개의 간선 (G8) 을 가진 데이터셋에 걸쳐 AWS Lambda 에서 견고하게 확장되며, 그래프 크기와 병렬성이 증가함에 따라 안정적인 성능을 유지합니다.
• 비용 효율성: 메모리 사용 최적화 (파티션 공동 위치를 통해) 및 I/O 작업 감소 (키 집계를 통해) 를 통해 GraphFlash 는 서버리스 플랫폼에서의 그래프 처리 비용을 극적으로 낮춥니다.

의의

이 논문은 GraphFlash 가 서버리스 그래프 처리를 실용적이고 고성능으로 만든다고 주장합니다. 원칙적인 시스템 설계와 표적 최적화를 통해 복잡한 상태 유지 그래프 워크로드에서도 서버리스 컴퓨팅의 탄력성과 비용 효율성을 성능을 희생하지 않고 실현할 수 있음을 보여줍니다.

GraphFlash 는 서버리스 인프라의 유연성과 그래프 알고리즘의 엄격한 요구 사항 사이의 간극을 메웁니다. 이는 전통적인 클러스터가 과프로비저닝되는 중소 규모 데이터셋을 위한 동적 및 돌발적 워크로드에 대한 실현 가능한 대안을 제공하며, 대규모 작업에서도 경쟁력을 유지합니다. 이 연구는 상태 관리 및 통신 오버헤드가 아키텍처 혁신을 통해 효과적으로 완화될 수 있음을 입증함으로써, 서버리스가 본질적으로 그래프 처리에 부적합하다는 통념에 도전합니다.