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

1. Probleemdefinitie

Het paper adresseert de kritieke uitdaging van proactieve auto-scaling in cloud-native microservice-systemen. Specifiek richt het zich op multi-step p95 tail-latency prediction (het voorspellen van het 95e percentiel van end-to-end responstijden).

Gesignaleerde Kernuitdagingen:

• Beperkte Global Dependency Modeling (C1): Bestaande predictors negeren vaak langere oproepafhankelijkheden of vangen slechts lokale buurten. In diepe microservice-call chains accumuleren fouten, wat leidt tot verkeerde schaalbeslissingen en Service Level Objective (SLO)-schendingen.
• Onvoldoende Burst-Aware Temporal Modeling (C2): Veel modellen veronderstellen werklast-stationariteit of periodiciteit. Ze worstelen met het vangen van niet-periodieke, bursty verkeerspatronen die in productie voorkomen (bijvoorbeeld geplande examens of flash sales).
• Slechte Schaalbaarheid en Faithfulness (C3): Graph Neural Networks (GNNs) en globale attention-mechanismen (zoals standaard Transformers) leiden tot kwadratische computationele complexiteit ($O(N^2)$) ten opzichte van het aantal servicenodes. Dit maakt ze onhaalbaar voor grootschalige systemen met duizenden services of complexe trace-graafstructuren. Bovendien vereenvoudigen veel modellen API-heterogeniteit te sterk.

2. Methodologie: STLGT

De auteurs stellen STLGT (Scalable Trace-based Linear Graph Transformer) voor, een per-API predictor die gedistribueerde traces codeert als span graphs. De architectuur bestaat uit drie hoofdcomponenten:

A. Data Representatie: API-Induced Span Graphs

In plaats van een statische globale call graph te gebruiken, construeert STLGT een dynamische, API-specifieke Span Graph ($G_A$) voor elk voorspellingsvenster.

• Nodes: Vertegenwoordigen uitvoeringsstadia gedefinieerd door caller-callee paren $(p, s)$, ontleend aan gedistribueerde traces. Dit stelt het model in staat om onderscheid te maken tussen dezelfde service die door verschillende ouders wordt aangeroepen.
• Edges: Vertegenwoordigen oproepafhankelijkheden (ouder-kind relaties in de trace).
• Features:
  • Node Features: Combineren service-level metrics (CPU, geheugen, netwerk I/O) met span-specifieke temporale features (genormaliseerde start/eindtijden, duur).
  • Context Vector: Een trace-gemeenschappelijke vector die de API-niveau werklast samenvat (throughput, p50/p90/p99 latencies, failure rates).

B. Spatial Encoder: Structure-Aware Linear Graph Transformer

Om globale afhankelijkheden te vangen zonder kwadratische complexiteit, vervangt STLGT standaard softmax attention door een Linear Graph Transformer:

• Linear Attention: Gebruikt een lineaire mixing operator (geïnspireerd door SGFormer) om globale representaties te berekenen in $O(N)$ tijd in plaats van $O(N^2)$. Het vermijdt het materialiseren van de $N \times N$ attention matrix door een globale samenvatting van waarden ($\bar{K}^\top \bar{V}$) te berekenen en deze naar alle nodes te distribueren.
• Structure-Aware Pre-mixing: Injecteert de schaarse topologie van de span graph in de globale mixing via een eenmalige schaarse propagatiestap. Dit zorgt ervoor dat het model de daadwerkelijke oproepstructuur respecteert terwijl het de lineaire complexiteit behoudt.
• Local Propagation: Een lichtgewicht Graph Convolutional Network (GCN) tak vangt lokale buurafhankelijkheden.
• Fusion: Globale en lokale representaties worden gefuseerd via een feed-forward netwerk met residual connections.

C. Temporal Decoder: Decoupled Spatiotemporal Modeling

Om te handelen met niet-stationaire en bursty werklasten zonder dure gekoppelde spatiotemporale attention:

• Decoupling: Het model scheidt globale afhankelijkheidscodering (Spatieel) van temporele dynamiekmodelling (Temporeel).
• TimesBlock: De temporele decoder maakt gebruik van de TimesNet architectuur. Het identificeert dominante perioden in het frequentiedomein (via FFT) en aggregeert periodieke representaties met 2D convoluties. Dit stelt het model in staat om zowel periodieke patronen (bijvoorbeeld dagelijkse cycli) als aperiodieke bursts gelijktijdig te vangen.
• Readout: Node representaties worden geaggregeerd via attention pooling en gefuseerd met de trace-gemeenschappelijke context vector voordat ze worden ingevoerd in de temporele decoder.

3. Kernbijdragen

1. Trace-Based Span Graph Abstraction: Introduceert een lichtgewicht, API-specifieke graafrepresentatie die direct is afgeleid van gedistribueerde traces. Dit lost het schaalbaarheidsprobleem op door de feature-graafgrootte per voorspellingsinstantie te begrenzen en API-heterogeniteit te hanteren.
2. Structure-Aware Linear Graph Transformer: Ontwerpt een novel encoder die lineaire inferentietijd ($O(|E|d + Nd^2)$) bereikt ten opzichte van de graafgrootte, terwijl het globale afhankelijkheidspropagatie vangt, waardoor de bottleneck van standaard GNNs/Transformers wordt overwonnen.
3. Decoupled Spatiotemporal Modeling: Stelt een kader voor dat afhankelijkheidscodering ontkoppelt van temporele dynamiek, waardoor de hoge computationele kosten van gekoppelde attention-mechanismen worden vermeden en bursty verkeer effectief wordt gemodelleerd.

4. Experimentele Resultaten

De auteurs evalueerden STLGT op drie datasets:

• DeathStarBench (DSB): Open-source microservice benchmarks (Hotel Reservation, Social Network).
• Alibaba Production Traces: Grootschalige real-world traces met 20k+ services.
• Edu Platform: Een gepersonaliseerd onderwijssysteem met schema-gedreven verkeerspieken (bijvoorbeeld online examens).

Kernbevindingen:

• Nauwkeurigheid: STLGT presteerde beter dan state-of-the-art baselines (PERT-GNN, FastPERT, GBDT).
  • Bereikte een gemiddelde verbetering van 8,5% in MAPE ten opzichte van PERT-GNN over de datasets.
  • Op het Edu Platform verlaagde het de MAPE met 8,3% vergeleken met PERT-GNN, wat een superieure hantering van door examens veroorzaakte verkeerspieken aantoont.
• Schaalbaarheid & Efficiëntie:
  • Inferentie Snelheid: Bij een graafgrootte van $N=32$ was STLGT tot 12× sneller op CPU dan PERT-GNN.
  • Schaalbaarheid: Terwijl de latency van PERT-GNN met 49,7× toenam toen $N$ van 1 naar 32 groeide, nam de latency van STLGT op CPU slechts met 3,8× toe. Dit bevestigt het voordeel van lineaire schaling.
• Ablation Studies:
  • Het verwijderen van de structure-aware pre-mixing of de GCN-tak degradeerde de prestaties aanzienlijk, wat de noodzaak bewijst van zowel globale als lokale afhankelijkheidsmodelling.
  • Het vervangen van de TimesNet decoder door een lineaire kop schaadde de prestaties, wat de behoefte aan complexe temporele modellering in bursty omgevingen benadrukt.

5. Betekenis en Impact

• Proactief SLO-beheer: Door tail latency (p95) nauwkeurig vooraf te voorspellen, stelt STLGT systemen in staat resources te provisioneren voordat SLO-schendingen optreden, in plaats van reactief te handelen nadat het feit.
• Schaalbaarheid voor Productie: Het ontwerp met lineaire complexiteit maakt het model levensvatbaar voor grootschalige microservice-clusters waar traditionele graafmodellen te traag zouden zijn voor real-time controlelussen.
• Toepasbaarheid in de Onderwijssector: De succesvolle toepassing op het Edu Platform demonstreert de bruikbaarheid van het model in domeinen met zeer voorspelbare maar intense verkeerspieken (geplande examens), waar reactieve schaling vaak faalt om latency-spieken te voorkomen.
• Generaliseerbaarheid: De aanpak van het gebruik van per-API span graphs stelt het systeem in staat mee te schalen met het aantal APIs zonder een combinatorische explosie in modelcomplexiteit, waardoor het een robuuste oplossing is voor moderne cloud-native architecturen.