LHGstore: An In-Memory Learned Graph Storage for Fast Updates and Analytics

본 논문은 현대 멀티코어 CPU 환경에서 빈번한 업데이트와 저지연 분석을 동시에 효율적으로 처리하기 위해, 정점의 차수에 따라 경량 배열과 학습된 색인을 적응적으로 적용하는 새로운 인메모리 그래프 저장소 LHGstore 를 제안하고, 이를 통해 기존 최첨단 시스템 대비 5.9~28.2 배의 처리량 향상을 입증합니다.

핵심

🏙️ 비유: 거대한 도시의 주소록과 우편 배달 시스템

컴퓨터가 데이터를 처리할 때, 그래프는 마치 수백만 명의 사람이 살고 있는 거대한 도시와 같습니다.

• 사람 (Vertex): 도시의 각 주민.
• 친구 관계 (Edge): 주민들 사이의 연결.

기존의 시스템들은 이 도시를 관리하는 데 두 가지 큰 고민이 있었습니다.

1. 새 친구를 사귀거나 관계를 끊는 것 (업데이트): 매우 빨라야 합니다.
2. 특정 사람의 친구 목록을 훑어보는 것 (분석): 매우 빠르게 찾아야 합니다.

❌ 기존 시스템의 문제점: "모두에게 똑같은 규칙"

기존 시스템은 모든 주민에게 똑같은 주소록 방식을 적용했습니다.

• 친구가 적은 사람 (저차수): 친구 목록을 종이에 쭉 적어두면 되는데, 검색할 때 다 읽어야 해서 느립니다.
• 친구가 엄청난 사람 (고차수): 친구가 수만 명인데, 이들을 한 장의 종이에 쭉 적어두면?
  • 새 친구 추가 시: 종이를 중간에 끼워 넣으려면 뒤에 있는 친구들 모두를 한 칸씩 밀어야 합니다 (엄청난 시간 소요).
  • 검색 시: 친구 목록을 처음부터 끝까지 다 봐야 합니다.

이처럼 "친구 수가 많은 사람"과 "적은 사람"을 똑같이 대우하는 방식이 비효율적이었던 것입니다.

---

✅ LHGstore 의 해결책: "지능형 맞춤형 주소록"

이 논문이 제안한 LHGstore는 **"사람의 친구 수 (차수) 에 따라 주소록 방식을 다르게 쓴다"**는 똑똑한 전략을 사용합니다. 마치 도시 관리자가 주민의 특성에 따라 우편 배달 방식을 바꾸는 것과 같습니다.

1. 두 단계의 지능형 구조 (Hierarchical Design)

이 시스템은 크게 두 단계로 나뉩니다.

• 1 단계 (주민 찾기): "A 씨의 친구 목록이 어디에 있나?"를 빠르게 찾습니다.
• 2 단계 (친구 목록 관리): A 씨의 친구 목록을 어떻게 저장할지 결정합니다.

2. 친구 수에 따른 맞춤형 전략 (Degree-Aware)

🟢 친구가 적은 사람 (저차수) → "단순한 메모장"

• 상황: 친구가 10 명 미만인 경우.
• 방식: 순서대로 나열된 간단한 메모장 (배열) 을 사용합니다.
• 이유: 친구가 적어서 검색할 때 다 봐도 금방 끝납니다. 그리고 메모장이라서 새로운 친구를 추가할 때 복잡한 계산이 필요 없어 매우 빠릅니다.
• 비유: 친구가 적은 사람은 편지를 손으로 직접 적어주면 되니까, 우체국 시스템을 쓸 필요가 없습니다.

🔴 친구가 엄청난 사람 (고차수) → "AI 우체부"

• 상황: 친구가 수만 명인 유명인 (인플루언서, 대기업 등) 인 경우.
• 방식: **학습된 인덱스 (Learned Index)**라는 AI 기술을 사용합니다.
• 원리: AI 가 "친구 B 는 대략 300 번 페이지에 있을 거야"라고 예측합니다. 그래서 처음부터 끝까지 다 볼 필요 없이, 예측된 곳으로 바로 가서 확인합니다.
• 이유: 친구가 너무 많아서 다 보면 시간이 걸리지만, AI 가 예측하면 순간적으로 찾을 수 있습니다. 또한, 새로운 친구를 추가할 때도 전체를 밀어낼 필요 없이 예측된 자리에 살짝 끼워 넣으면 됩니다.
• 비유: 친구가 많은 유명인은 AI 비서가 "친구 C 는 300 번 페이지 5 줄에 있어요"라고 바로 알려주니까, 검색이 매우 빠릅니다.

---

🚀 LHGstore 가 가져온 혁신

이 방식 덕분에 LHGstore 는 기존 시스템보다 5.9 배에서 28.2 배까지 더 빠른 속도를 보여줍니다.

• 업데이트 속도: 친구를 새로 사귀거나 끊을 때, AI 가 예측해서 바로 처리하므로 시스템이 멈추지 않습니다.
• 분석 속도: 친구 목록을 훑을 때, 친구가 적은 사람은 순서대로 빠르게, 친구가 많은 사람은 AI 가 가리키는 곳으로 바로 가서 빠르게 처리합니다.

💡 한 줄 요약

"친구가 적은 사람은 간단한 메모장으로, 친구가 많은 사람은 AI 비서로 관리해 주니, 도시 전체의 우편 배달 (데이터 처리) 속도가 비약적으로 빨라졌다!"

이 기술은 금융 사기 탐지, SNS 추천 시스템, 실시간 교통 정보 등 데이터가 끊임없이 변하고 분석도 빨라야 하는 모든 분야에 큰 도움을 줄 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

현대 사회의 소셜 네트워크, 추천 시스템, 사기 탐지 등 다양한 응용 분야는 동적 그래프 (Dynamic Graphs) 를 기반으로 합니다. 이러한 그래프는 빈번한 업데이트 (간선 삽입/삭제) 가 발생하면서도, 동시에 실시간 분석 (BFS, SSSP 등) 을 요구합니다. 기존 인메모리 그래프 저장 시스템은 다음 두 가지 요구사항을 동시에 충족하는 데 한계가 있습니다.

• 업데이트 효율성 (R1): 고처리량 (High-throughput) 업데이트를 위해서는 데이터 이동이 적고 불연속적인 메모리 레이아웃이 유리합니다.
• 탐색 국소성 (R2): 고성능 분석을 위해서는 CPU 캐시 국소성 (Locality) 을 극대화하기 위해 연속적인 메모리 레이아웃이 필요합니다.

기존 시스템 (CSR, B+Tree, LSM-Tree 기반 등) 은 이 두 가지 상충되는 요구사항 (Trade-off) 을 해결하지 못했습니다. 또한, 기존 Learned Index (학습된 인덱스) 를 그래프에 직접 적용할 경우, 고차수 (High-degree) 정점의 경우 예측된 위치가 겹쳐 선형 검색이나 대량 이동이 발생하여 $O(deg(u))$ 의 비용이 발생한다는 한계가 있었습니다.

2. 제안 방법론: LHGstore (Methodology)

저자들은 LHGstore를 제안했습니다. 이는 정점의 차수 (Degree) 를 인식하는 계층적 학습된 그래프 저장 (Degree-aware Learned Hierarchical Graph Storage) 구조입니다.

핵심 설계 원리

1. 2 단계 계층 구조 (Two-level Hierarchy):

   • 1 단계 (Vertex Index): 정점 ID 를 키로 사용하여 해당 정점의 엣지 정보를 가리키는 인덱스를 관리합니다.
   • 2 단계 (Edge Index): 각 정점의 이웃 (간선) 을 관리하는 인덱스입니다.
   • 이 구조를 통해 정점 탐색과 이웃 접근을 분리하여, 학습된 인덱스의 예측 능력을 활용하면서도 정렬된 레이아웃을 유지합니다.

2. 차수 인식형 하이브리드 레이아웃 (Degree-aware Hybrid Layout):

   • 실제 그래프는 소수의 고차수 정점과 다수의 저차수 정점으로 이루어진 편향된 분포 (Skewed Distribution) 를 보입니다. LHGstore 는 정점의 차수에 따라 저장 구조를 동적으로 선택합니다.
   • 저차수 정점 (Degree $\le T$): 정렬되지 않은 배열 (Unsorted Array) 을 사용합니다.
     • 이유: 오버헤드가 적고, 분석 시 순차적 스캔 (Sequential Scan) 에 유리하여 캐시 국소성을 극대화합니다.
   • 고차수 정점 (Degree $> T$): 학습된 인덱스 (Learned Index) 를 사용합니다.
     • 이유: 업데이트 시 데이터 이동 (Shift) 을 최소화하고, 예측 기반 접근으로 $O(1)$ 에 가까운 탐색/삽입 성능을 보장합니다.
     • 구현: 고차수 정점의 경우, 이웃 ID 를 키로, 정점 ID 를 값으로 하는 변환 테이블 (Translation Table) 을 사용하여 학습 모델이 동일한 키를 예측하는 문제를 해결합니다.

3. 동적 전환 (Dynamic Transition):

   • 정점의 차수가 임계값 $T$ 를 넘거나 아래로 떨어질 때, 저장 구조를 자동으로 전환하거나 유지합니다 (삭제 시에는 효율성을 위해 학습 인덱스를 배열로 즉시 전환하지 않음).

3. 주요 기여 (Key Contributions)

1. 새로운 관점: 인메모리 동적 그래프 저장소로서 학습된 인덱스 (Learned Index) 를 최초로 도입하여 업데이트 효율성과 탐색 국소성 간의 트레이드오프를 해결했습니다.
2. 간단하지만 효과적인 솔루션: 정점과 이웃 접근을 분리하고, 정점 차수에 따라 다른 인접 리스트 레이아웃을 할당하는 LHGstore를 설계했습니다. 이는 실제 그래프의 편향된 차수 분포를 활용하여 데이터 이동을 최소화하고 국소성을 극대화합니다.
3. 광범위한 실험 검증: 합성 및 실세계 그래프 데이터셋을 사용하여 다양한 워크로드 (쓰기 전용, 읽기/쓰기 혼합, 읽기 전용) 와 5 가지 그래프 분석 알고리즘 (BFS, PageRank, LCC, WCC, SSSP) 에 대한 성능을 입증했습니다.

4. 실험 결과 (Results)

저자들은 Teseo, Sortledton, LiveGraph, Aspen, LSGraph, LGstore 등 기존 최첨단 (SOTA) 시스템과 비교 실험을 수행했습니다.

• 업데이트 처리량 (Throughput):
  • LHGstore 는 모든 워크로드에서 기존 시스템 대비 5.9 배에서 28.2 배 높은 처리량을 달성했습니다.
  • 특히 고차수 정점에서의 선형 검색을 학습된 인덱스로 대체함으로써, 업데이트 시 발생하는 오버헤드를 획기적으로 줄였습니다.
• 분석 성능 (Analytics Performance):
  • 순차적 접근 (BFS, WCC, SSSP): 저차수 정점의 연속적 배열 레이아웃 덕분에 캐시 국소성이 유지되어 기존 시스템 대비 2.6 배에서 13.9 배 빠른 성능을 보였습니다.
  • 무작위 접근 (LCC): 학습된 인덱스를 통해 선형 검색을 피함으로써 LGstore 대비 2.4 배에서 30.6 배 빠른 성능을 기록했습니다.
• 메모리 사용량:
  • 추가 메타데이터 (포인터 등) 로 인한 오버헤드가 존재하지만, LiveGraph 의 로그나 Aspen 의 버전 관리 구조에 비해 메모리 효율성이 우수하거나 경쟁력 있는 수준을 유지했습니다.
• 임계값 ($T$) 의 영향:
  • 실험 결과, $T \approx 60$ 일 때 업데이트 처리량과 분석 성능 모두 최적의 균형을 이루는 것으로 확인되었습니다.

5. 의의 및 결론 (Significance)

LHGstore 는 학습된 인덱스와 하이브리드 데이터 레이아웃을 결합하여, 인메모리 동적 그래프 시스템이 겪어온 "업데이트 vs 분석"이라는 근본적인 딜레마를 성공적으로 해결했습니다.

• 기술적 혁신: 단순한 인덱스 구조를 넘어, 그래프 데이터의 통계적 특성 (차수 분포) 을 학습 모델과 결합하여 최적의 저장 전략을 자동화했습니다.
• 실용성: 현대의 다중 코어 CPU 환경에서 캐시 국소성과 병렬 처리를 동시에 고려하여, 실시간 그래프 분석이 필요한 금융 사기 탐지, 소셜 네트워크 분석 등 다양한 분야에서 높은 성능을 제공할 것으로 기대됩니다.

결론적으로, LHGstore 는 동적 그래프 관리의 새로운 패러다임을 제시하며, 기존 시스템 대비 압도적인 성능 개선을 입증했습니다.