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

1. Definizione del Problema

Il paper affronta la sfida critica del provisioning automatico proattivo (proactive auto-scaling) nei sistemi di microservizi cloud-native. Nello specifico, si concentra sulla previsione della latenza di coda p95 multi-step (previsione del 95° percentile dei tempi di risposta end-to-end).

Sfide Chiave Identificate:

• Modellazione Limitata delle Dipendenze Globali (C1): I predittori esistenti spesso ignorano le dipendenze di invocazione a lungo raggio o catturano solo i vicinati locali. Nelle catene di chiamata dei microservizi profonde, gli errori si accumulano, portando a decisioni di scaling errate e violazioni degli Obiettivi di Livello di Servizio (SLO).
• Modellazione Temporale Insufficiente Consapevole dei Burst (C2): Molti modelli assumono la stazionarietà o la periodicità del carico di lavoro. Faticano a catturare pattern di traffico non periodici e a scoppio (bursty) comuni in produzione (ad esempio, esami programmati o vendite lampo).
• Scalabilità e Fedeltà Scarse (C3): Le Reti Neurali su Grafo (GNN) e i meccanismi di attenzione globale (come i Transformer standard) comportano una complessità computazionale quadratica ($O(N^2)$) rispetto al numero di nodi di servizio. Ciò li rende non fattibili per sistemi su larga scala con migliaia di servizi o grafi di traccia complessi. Inoltre, molti modelli semplificano eccessivamente l'eterogeneità delle API.

2. Metodologia: STLGT

Gli autori propongono STLGT (Scalable Trace-based Linear Graph Transformer), un predittore per API che codifica le tracce distribuite come grafi di span. L'architettura è composta da tre componenti principali:

A. Rappresentazione dei Dati: Grafi di Span Indotti dalle API

Invece di utilizzare un grafo di chiamata globale statico, STLGT costruisce un Grafo di Span ($G_A$) dinamico e specifico per ogni API per ogni finestra di previsione.

• Nodi: Rappresentano le fasi di esecuzione definite dalle coppie chiamante-chiamato $(p, s)$ estratte dalle tracce distribuite. Ciò permette al modello di distinguere tra lo stesso servizio chiamato da genitori diversi.
• Archi: Rappresentano le dipendenze di invocazione (relazioni genitore-figlio nella traccia).
• Caratteristiche:
  • Caratteristiche del Nodo: Combinano metriche a livello di servizio (CPU, memoria, I/O di rete) con caratteristiche temporali specifiche dello span (tempi di inizio/fine normalizzati, durata).
  • Vettore di Contesto: Un vettore comune alla traccia che riassume il carico di lavoro a livello di API (throughput, latenze p50/p90/p99, tassi di errore).

B. Encoder Spaziale: Transformer su Grafo Lineare Consapevole della Struttura

Per catturare le dipendenze globali senza complessità quadratica, STLGT sostituisce l'attenzione softmax standard con un Transformer su Grafo Lineare:

• Attenzione Lineare: Utilizza un operatore di miscelazione lineare (ispirato a SGFormer) per calcolare rappresentazioni globali in tempo $O(N)$ invece di $O(N^2)$. Evita la materializzazione della matrice di attenzione $N \times N$ calcolando un riepilogo globale dei valori ($\bar{K}^\top \bar{V}$) e distribuendolo a tutti i nodi.
• Pre-miscelazione Consapevole della Struttura: Inietta la topologia sparsa del grafo di span nella miscelazione globale tramite un passaggio di propagazione sparsa singola. Ciò garantisce che il modello rispetti la struttura di invocazione effettiva mantenendo la complessità lineare.
• Propagazione Locale: Un ramo leggero di Rete Neurale su Grafo Convoluzionale (GCN) cattura le dipendenze del vicinato locale.
• Fusione: Le rappresentazioni globali e locali vengono fuse tramite una rete feed-forward con connessioni residue.

C. Decoder Temporale: Modellazione Spazio-Temporale Disaccoppiata

Per gestire carichi di lavoro non stazionari e a scoppio senza costose attenzioni spazio-temporali accoppiate:

• Disaccoppiamento: Il modello separa la codifica delle dipendenze globali (Spaziale) dalla modellazione delle dinamiche temporali (Temporale).
• TimesBlock: Il decoder temporale utilizza l'architettura TimesNet. Identifica i periodi dominanti nel dominio della frequenza (tramite FFT) e aggrega le rappresentazioni per periodo utilizzando convoluzioni 2D. Ciò permette al modello di catturare simultaneamente pattern periodici (ad esempio, cicli giornalieri) e burst aperiodici.
• Readout: Le rappresentazioni dei nodi vengono aggregate tramite pooling basato sull'attenzione e fuse con il vettore di contesto comune alla traccia prima di essere inviate al decoder temporale.

3. Contributi Chiave

1. Astrazione del Grafo di Span Basata su Tracce: Introduce una rappresentazione grafica leggera e specifica per API derivata direttamente dalle tracce distribuite. Ciò risolve il problema della scalabilità limitando la dimensione del grafo delle caratteristiche per istanza di previsione e gestendo l'eterogeneità delle API.
2. Transformer su Grafo Lineare Consapevole della Struttura: Progetta un encoder innovativo che raggiunge un tempo di inferenza lineare ($O(|E|d + Nd^2)$) rispetto alla dimensione del grafo, catturando al contempo la propagazione delle dipendenze globali, superando il collo di bottiglia delle GNN/Transformer standard.
3. Modellazione Spazio-Temporale Disaccoppiata: Propone un framework che disaccoppia la codifica delle dipendenze dalle dinamiche temporali, evitando l'alto costo computazionale dei meccanismi di attenzione accoppiati e modellando efficacemente il traffico a scoppio.

4. Risultati Sperimentali

Gli autori hanno valutato STLGT su tre dataset:

• DeathStarBench (DSB): Benchmark open-source di microservizi (Hotel Reservation, Social Network).
• Tracce di Produzione Alibaba: Tracce reali su larga scala con oltre 20.000 servizi.
• Piattaforma Edu: Un sistema educativo personalizzato con picchi di traffico guidati da programmi (ad esempio, esami online).

Risultati Chiave:

• Accuratezza: STLGT ha superato i baseline all'avanguardia (PERT-GNN, FastPERT, GBDT).
  • Ha raggiunto un miglioramento medio dell'8,5% in MAPE rispetto a PERT-GNN su tutti i dataset.
  • Sulla Piattaforma Edu, ha ridotto il MAPE dell'8,3% rispetto a PERT-GNN, dimostrando una gestione superiore dei picchi di traffico indotti dagli esami.
• Scalabilità ed Efficienza:
  • Velocità di Inferenza: A una dimensione del grafo di $N=32$, STLGT è stato fino a 12 volte più veloce su CPU rispetto a PERT-GNN.
  • Scalabilità: Mentre la latenza di PERT-GNN è cresciuta di 49,7 volte quando $N$ è aumentato da 1 a 32, la latenza di STLGT è cresciuta solo di 3,8 volte su CPU. Ciò conferma il vantaggio della scalabilità lineare.
• Studi di Ablazione:
  • Rimuovere la pre-miscelazione consapevole della struttura o il ramo GCN ha degradato significativamente le prestazioni, dimostrando la necessità di una modellazione sia globale che locale delle dipendenze.
  • Sostituire il decoder TimesNet con un head lineare ha danneggiato le prestazioni, evidenziando la necessità di una modellazione temporale complessa in ambienti a scoppio.

5. Significato e Impatto

• Gestione Proattiva degli SLO: Prevedendo accuratamente in anticipo la latenza di coda (p95), STLGT permette ai sistemi di provisionare le risorse prima che si verifichino violazioni degli SLO, invece di reagire a cose fatte.
• Scalabilità per la Produzione: La progettazione a complessità lineare rende il modello fattibile per cluster di microservizi su larga scala, dove i modelli grafici tradizionali sarebbero troppo lenti per i loop di controllo in tempo reale.
• Applicabilità nel Settore Educativo: La riuscita applicazione alla Piattaforma Edu dimostra l'utilità del modello in domini con picchi di traffico altamente prevedibili ma intensi (esami programmati), dove lo scaling reattivo spesso fallisce nel prevenire picchi di latenza.
• Generalizzabilità: L'approccio di utilizzare grafi di span per API permette al sistema di scalare con il numero di API senza un'esplosione combinatoria nella complessità del modello, rendendolo una soluzione robusta per le moderne architetture cloud-native.