STLGT: A Scalable Trace-Based Linear Graph Transformer for Tail Latency Prediction in Microservices

"STLGT: A Scalable Trace-Based Linear Graph Transformer for Tail Latency Prediction in Microservices" 논문의 상세 기술 요약은 다음과 같습니다.

1. 문제 정의

본 논문은 클라우드 네이티브 마이크로서비스 시스템에서 **선제적 자동 확장 (proactive auto-scaling)**의 핵심적인 과제를 다룹니다. 구체적으로는 다단계 p95 꼬리 지연 시간 예측 (종단 간 응답 시간의 95 백분위수 예측) 에 초점을 맞춥니다.

식별된 주요 과제:

• 제한된 전역 의존성 모델링 (C1): 기존 예측 모델들은 종종 장거리 호출 의존성을 무시하거나 지역적 이웃만 포착합니다. 깊은 마이크로서비스 호출 체인에서는 오류가 누적되어 잘못된 확장 결정과 서비스 수준 목표 (SLO) 위반을 초래합니다.
• 불충분한 버스트 인식 시간적 모델링 (C2): 많은 모델들은 작업 부하의 정상성 (stationarity) 이나 주기성을 가정합니다. 따라서 생산 환경에서 흔히 발생하는 비주기적이고 버스트가 많은 트래픽 패턴 (예: 예정된 시험이나 플래시 세일) 을 포착하는 데 어려움을 겪습니다.
• 낮은 확장성과 충실도 (C3): 그래프 신경망 (GNN) 과 전역 어텐션 메커니즘 (표준 Transformer 등) 은 서비스 노드 수에 대해 이차적인 계산 복잡도 ($O(N^2)$) 를 incur 합니다. 이는 수천 개의 서비스나 복잡한 추적 (trace) 그래프를 가진 대규모 시스템에서는 실행 불가능하게 만듭니다. 또한 많은 모델들이 API 이질성을 지나치게 단순화합니다.

2. 방법론: STLGT

저자들은 분산 추적을 **스팬 그래프 (span graphs)**로 인코딩하는 API 별 예측기인 **STLGT(Scalable Trace-based Linear Graph Transformer)**를 제안합니다. 아키텍처는 세 가지 주요 구성 요소로 이루어져 있습니다.

A. 데이터 표현: API 유도 스팬 그래프

정적 전역 호출 그래프를 사용하는 대신, STLGT 는 각 예측 윈도우마다 동적이고 API 특정적인 **스팬 그래프 ($G_A$)**를 구성합니다.

• 노드: 분산 추적에서 추출된 호출자 - 피호출자 쌍 $(p, s)$로 정의된 실행 단계를 나타냅니다. 이를 통해 모델은 다른 부모에 의해 호출되는 동일한 서비스를 구별할 수 있습니다.
• 엣지: 추적 내의 호출 의존성 (부모 - 자식 관계) 을 나타냅니다.
• 특징:
  • 노드 특징: 서비스 수준 지표 (CPU, 메모리, 네트워크 I/O) 와 스팬별 시간적 특징 (정규화된 시작/종료 시간, 지속 시간) 을 결합합니다.
  • 컨텍스트 벡터: API 수준 작업 부하 (처리량, p50/p90/p99 지연 시간, 실패율) 를 요약하는 추적 공통 벡터입니다.

B. 공간 인코더: 구조 인식 선형 그래프 Transformer

이차 복잡도 없이 전역 의존성을 포착하기 위해, STLGT 는 표준 softmax 어텐션을 선형 그래프 Transformer로 대체합니다:

• 선형 어텐션: SGFormer 에서 영감을 받은 선형 믹싱 연산자를 사용하여 $O(N^2)$ 대신 $O(N)$ 시간에 전역 표현을 계산합니다. $N \times N$ 어텐션 행렬을 구체화하지 않고 값의 전역 요약 ($\bar{K}^\top \bar{V}$) 을 계산하여 모든 노드에 분배함으로써 이를 달성합니다.
• 구조 인식 사전 믹싱 (Structure-Aware Pre-mixing): 한 번의 희소 전파 단계를 통해 스팬 그래프의 희소 토폴로지를 전역 믹싱에 주입합니다. 이는 모델이 선형 복잡도를 유지하면서 실제 호출 구조를 존중하도록 보장합니다.
• 지역 전파: 경량 그래프 합성곱 신경망 (GCN) 브랜치가 지역 이웃 의존성을 포착합니다.
• 퓨전: 전역 및 지역 표현은 잔여 연결을 갖춘 피드포워드 네트워크를 통해 융합됩니다.

C. 시간 디코더: 분리된 시공간 모델링

비정상적이고 버스트가 많은 작업 부하를 처리하기 위해 값비싼 결합된 시공간 어텐션 없이:

• 분리: 모델은 전역 의존성 인코딩 (공간) 을 시간적 역동성 모델링 (시간) 과 분리합니다.
• TimesBlock: 시간 디코더는 TimesNet 아키텍처를 활용합니다. FFT 를 통해 주파수 영역에서 지배적인 주기를 식별하고 2D 컨볼루션을 사용하여 주기별 표현을 집계합니다. 이를 통해 모델은 주기적 패턴 (예: 일일 주기) 과 비주기적 버스트를 동시에 포착할 수 있습니다.
• 리드아웃 (Readout): 노드 표현은 어텐션 풀링을 통해 집계되고, 시간 디코더에 입력되기 전에 추적 공통 컨텍스트 벡터와 융합됩니다.

3. 주요 기여

1. 추적 기반 스팬 그래프 추상화: 분산 추적에서 직접 유도된 경량 API 특정 그래프 표현을 도입합니다. 이는 예측 인스턴스당 특징 - 그래프 크기를 제한하고 API 이질성을 처리함으로써 확장성 문제를 해결합니다.
2. 구조 인식 선형 그래프 Transformer: 표준 GNN/Transformer 의 병목 현상을 극복하면서 전역 의존성 전파를 포착하는 선형 추론 시간 ($O(|E|d + Nd^2)$) 을 달성하는 새로운 인코더를 설계합니다.
3. 분리된 시공간 모델링: 결합된 어텐션 메커니즘의 높은 계산 비용을 피하고 버스트가 많은 트래픽을 효과적으로 모델링하기 위해 의존성 인코딩과 시간적 역동성을 분리하는 프레임워크를 제안합니다.

4. 실험 결과

저자들은 STLGT 를 세 가지 데이터셋에서 평가했습니다:

• DeathStarBench (DSB): 오픈소스 마이크로서비스 벤치마크 (호텔 예약, 소셜 네트워크).
• Alibaba Production Traces: 2 만 개 이상의 서비스를 포함한 대규모 실제 세계 추적.
• Edu Platform: 예정된 시험과 같은 일정 기반 트래픽 버스트를 가진 개인화된 교육 시스템.

주요 발견:

• 정확도: STLGT 는 PERT-GNN, FastPERT, GBDT 와 같은 최신 베이스라인을 능가했습니다.
  • 데이터셋 전반에 걸쳐 PERT-GNN 대비 평균 MAPE 8.5% 개선을 달성했습니다.
  • Edu Platform 에서 PERT-GNN 대비 MAPE 를 8.3% 감소시켜 시험으로 인한 트래픽 버스트를 더 잘 처리함을 입증했습니다.
• 확장성 및 효율성:
  • 추론 속도: 그래프 크기 $N=32$에서 STLGT 는 CPU 기준 PERT-GNN 보다 최대 12 배 빠릅니다.
  • 확장성: $N$이 1 에서 32 로 증가할 때 PERT-GNN 의 지연 시간은 49.7 배 증가한 반면, STLGT 의 지연 시간은 CPU 에서 3.8 배만 증가했습니다. 이는 선형 확장 이점을 확인시켜 줍니다.
• 절대 연구 (Ablation Studies):
  • 구조 인식 사전 믹싱이나 GCN 브랜치를 제거하면 성능이 크게 저하되어, 전역 및 지역 의존성 모델링의 필요성을 입증했습니다.
  • TimesNet 디코더를 선형 헤드로 교체하면 성능이 저하되어, 버스트가 많은 환경에서 복잡한 시간적 모델링의 필요성을 강조했습니다.

5. 중요성 및 영향

• 선제적 SLO 관리: 꼬리 지연 시간 (p95) 을 정확하게 사전에 예측함으로써, STLGT 는 SLO 위반이 발생한 후 대응하는 대신 위반 발생 전에 자원을 프로비저닝할 수 있게 합니다.
• 생산 환경용 확장성: 선형 복잡도 설계는 기존 그래프 모델이 실시간 제어 루프에 너무 느려서 실행 불가능한 대규모 마이크로서비스 클러스터에서 모델을 실행 가능하게 만듭니다.
• 교육 분야 적용성: Edu Platform 에 대한 성공적인 적용은 예정된 시험과 같이 매우 예측 가능하지만 강렬한 트래픽 버스트가 발생하는 분야에서 모델의 유용성을 입증합니다. 이러한 환경에서는 반응형 확장이 지연 시간 급증을 방지하는 데 종종 실패합니다.
• 일반화 가능성: API 별 스팬 그래프를 사용하는 접근 방식은 모델 복잡도의 조합적 폭발 없이 API 수에 따라 시스템이 확장되도록 하여, 현대 클라우드 네이티브 아키텍처에 대한 견고한 솔루션을 제공합니다.