ELIMINISANJE ZASTOJA ZBOG PROMAŠAJA KEŠA U TRAVERSIRANJU MREŽE U REALNOM VREMENU

Zamena objektno-teškog traversiranja grafa data layout-om prilagođenim kešu i zasnovanim na CSR-u

Evropska platforma za distribuciju energije iz obnovljivih izvora

Performance Engineering Data-Oriented Design Cache Efficiency Real-Time Systems Graph Traversal Latency Engineering

Java Compressed Sparse Row Primitive Arrays

IZVRŠNI SAŽETAK

PROBLEM

Sistem za obilazak mreže obnovljivih izvora energije u realnom vremenu obrađivao je graf sa približno 20.000 pametnih brojila i čvorova mreže, sa 180.000–250.000 grana i protokom od približno 350.000–500.000 događaja u sekundi. Repna latencija prelazila je budžet za obradu: p99 latencija obilaska bila je iznad 500 ms, a najgora latencija dostizala je približno 1,2 sekunde. Analiza je identifikovala memorijske zastoje kao značajno ograničenje. Neregularan obilazak grafa izazivao je cache miss događaje, dok je reprezentacija grafa zauzimala približno 2,8 GB heap memorije.

REŠENJE

Reprezentacija grafa redizajnirana je korišćenjem kompaktnih nizova u CSR stilu: int[] offsetArray, int[] edgeArray i long[] metricsArray. Time su strukture objekata sa mnogo referenci zamenjene kontinuiranim nizovima primitivnih tipova, čime su smanjeni memorijski otisak i troškovi pristupa podacima tokom obilaska. Kritična putanja dizajnirana je tako da ne alocira memoriju, uz ograničavanje računskog rada na definisani budžet. Promena je bila usmerena na memorijski pristup i raspored podataka, a ne samo na dodavanje računarskih resursa.

KLJUČNI ARHITEKTONSKI POMAK

OD strukture grafa sa mnogo referenci, memorijski zastoji i nepredvidiva latencija obilaska

→

KA kompaktni nizovi primitivnih tipova, bolja lokalnost memorije i ograničen obilazak bez alokacija

ZAKLJUČAK

Izmereni rezultati obuhvatili su smanjenje p99 latencije obilaska sa 620+ ms na 18 ms, smanjenje najgore latencije sa 1.200+ ms na manje od 480 ms, smanjenje udela memorijskih zastoja sa 62% na 9% i smanjenje memorijskog otiska grafa sa 2,8 GB na 450 MB. Kritična putanja nije vršila alokacije, a tokom testiranog opterećenja nisu zabeležena prekoračenja granice za obradu. Interna granica iznosila je približno 470 ms; rezultati opisuju testirano opterećenje i ne predstavljaju garanciju hard real-time ponašanja.

ARHITEKTONSKA ANALIZA

KONTEKST I POSLOVNI UTICAJ

Platforma obavlja traversiranje elektroenergetske mreže u realnom vremenu kroz približno 20.000 pametnih brojila, trafostanica i drugih čvorova mreže.

Dominantan problem nije bila samo računarska složenost traversiranja grafa. Fizička reprezentacija podataka izazivala je značajne zastoje procesora tokom pristupa memoriji, što je doprinosilo prekoračenjima vremenskih granica pri visokoj aktivnosti telemetrije.

OSNOVNI UZROK I FORENZIČKA ANALIZA

Profilisanje je pokazalo da je ponašanje pristupa memoriji predstavljalo dominantno ograničenje performansi, a ne asimptotska složenost algoritma za traversiranje grafa.

Originalna Java implementacija predstavljala je graf pomoću objektno-teške kolekcije objekata Node i Relationship. Traversiranje je zato zahtevalo ponavljano praćenje lanaca referenci (pointer chasing) kroz JVM heap, umesto pristupa kompaktnim, kontinualnim primitivnim podacima.

ORIGINALNI OBJEKTNO-TEŠKI GRAF

+----------------------+
| Mrežni graf          |
+----------+-----------+
           |
           v
+----------------------+
| Node objekti         |
+----------+-----------+
           |
           v
+----------------------+
| Relationship objekti |
+----------+-----------+
           |
           v
+----------------------+
| Pointer Chasing      |
| kroz JVM heap        |
+----------+-----------+
           |
           v
+----------------------+
| Zastoji pri pristupu |
| memoriji             |
+----------+-----------+
           |
           v
+----------------------+
| Produženo trajanje   |
| traversiranja        |
+----------------------+

Graf je bio upravljiv sa stanovišta algoritamske složenosti, ali je njegova fizička reprezentacija nametala značajan trošak izvršavanju.

ARHITEKTONSKI UVID I EVOLUCIJA

Rezultati profilisanja promenili su cilj optimizacije. Umesto optimizovanja traversiranja uz zadržavanje originalne objektne reprezentacije, redizajn je usmeren na fizički raspored i način pristupa podacima u JVM-u i procesoru.

Nova arhitektura razdvojila je dva različita tipa opterećenja: česta ažuriranja metrika i relativno retke strukturne izmene topologije grafa. Svaki tip opterećenja dobio je reprezentaciju i strategiju ažuriranja prilagođenu svojim zahtevima.

DATA-ORIENTED RASPORED MEMORIJE

Objektno-teška reprezentacija grafa zamenjena je reprezentacijom Compressed Sparse Row (CSR). Povezanost grafa predstavljena je pomoću dva primitivna niza:

int[] offsetArray int[] edgeArray

Za dati čvor, niz offsetArray određuje kontinualni opseg njegovih izlaznih veza: start = offsetArray[nodeId] end = offsetArray[nodeId + 1] Odgovarajući opseg u nizu edgeArray sadrži identifikatore susednih čvorova. Traversiranje zato koristi indeksiranje nizova i sekvencijalan pristup primitivnim podacima, umesto praćenja lanaca Java objektnih referenci.

Često korišćene vrednosti metrika čuvaju se odvojeno u primitivnom nizu long[] metricsArray. Taj niz služi za pristup metrikama i nije deo CSR strukture povezanosti koju definišu nizovi offsetArray i edgeArray.

CSR reprezentacija poboljšava prostornu lokalnost podataka i omogućava predvidljiviji obrazac pristupa memorijskoj hijerarhiji procesora i hardverskom prefetchingu. To ne znači da svako susedstvo staje u jednu cache liniju.

Dinamičke izmene topologije obrađuju se odvojeno od ažuriranja metrika. Strukturna izmena asinhrono gradi novi CSR snapshot. Nizovi topologije ne menjaju se nakon objavljivanja, pa traversiranje može da nastavi rad koristeći postojeći snapshot dok se priprema njegova sledeća verzija.

Kada je novi snapshot spreman, objavljuje se atomskom zamenom reference putem AtomicReference. Svako traversiranje zadržava lokalnu referencu na snapshot sa kojim je započelo, tako da topologija koju čita ostaje strukturno stabilna tokom celog traversiranja.

Prethodni snapshot postaje podoban za garbage collection kada više ne postoje aktivne reference ka njemu. Time se izbegava potreba da niti za traversiranje čekaju rekonstrukciju topologije na mestu.

Često promenljive metrike ažuriraju se na mestu pomoću atomskih primitiva, umesto da se topologija ponovo gradi pri svakom telemetrijskom ažuriranju. Pojedinačna atomska ažuriranja ne znače da sve metrike predstavljaju jedan transakciono konzistentan trenutak u vremenu. Arhitektura čuva strukturnu konzistentnost topologije, dok se telemetrijske vrednosti kontinuirano menjaju.

Radno stanje traversiranja premešteno je u unapred alocirane primitivne bafere. Privremene kolekcije, iteratori i drugi pomoćni objekti koji bi se alocirali pri svakom izvršavanju uklonjeni su iz merene hot-path putanje.

Rezultat merenja alokacije odnosi se isključivo na aplikacionu alokaciju tokom traversiranja. To ne znači da JVM ili čitava aplikacija nisu vršili alokacije; kvantifikovani rezultat prikazan je zasebno u rezultatima merenja.

BUDŽETI I GRANICE LATENCIJE

Putanja traversiranja procenjivana je u odnosu na eksplicitne pragove latencije, kako bi se izmereno vreme izvršavanja moglo uporediti sa zahtevom za end-to-end latenciju.

Interni prag od 470 ms bio je cilj latencije, a ne aktivni timeout niti mehanizam koji prekida traversiranje kada se prag dostigne. Zato nije garantovao da će svako traversiranje biti završeno u roku od 470 ms. Činjenica da je maksimalna posmatrana latencija bila ispod 480 ms ne dokazuje da je interni prag uvek bio ispoštovan.

Tokom validacije nisu uočena prekoračenja spoljašnje end-to-end granice od 500 ms. Java na operativnom sistemu opšte namene ne pruža garancije hard real-time izvršavanja; merenja opisuju testirano opterećenje, a ne determinističko najgore vreme izvršavanja.

PRAGOVI LATENCIJE

Cilj normalne latencije
         |
         v
       <50 ms
         |
         v
Interni prag latencije
         |
         v
      ~470 ms
         |
         |  Nominalna razlika od 30 ms
         v
Spoljašnji end-to-end cilj
         |
         v
       500 ms

KLJUČNE INŽENJERSKE ODLUKE

ARHITEKTONSKI ISHOD

Redizajn je uskladio fizičku reprezentaciju podataka grafa sa zahtevima traversiranja. Strukturne izmene topologije više nisu zahtevale rekonstrukciju grafa na mestu dok se on koristi, a česta ažuriranja metrika ostala su nezavisna od zamene topologije.

Nova arhitektura uspostavila je efikasniju izvršnu putanju zajedničkim rešavanjem problema pristupa memoriji, izolacije ažuriranja i upravljanja radnim stanjem traversiranja, umesto oslanjanja samo na izmene algoritma.

KVANTIFIKOVANI REZULTATI

P99 LATENCIJA TRAVERSIRANJA

PRE 620+ ms

POSLE 18 ms

Smanjenje od 97%+

MAKSIMALNA POSMATRANA LATENCIJA TRAVERSIRANJA

PRE 1200+ ms

POSLE < 480 ms

Maksimalna posmatrana latencija tokom validacije

IZMERENI CIKLUSI ZASTOJA ZBOG MEMORIJE

PRE 62%

POSLE 9%

Smanjenje od približno 85%

MEMORIJSKI FOOTPRINT GRAFA

PRE 2,8 GB

POSLE 450 MB

Smanjenje od približno 84%

ALOKACIJA NA HOT-PATH-U

PRE Alokacije pri svakom traversiranju

POSLE 0 B izmereno

Nulta izmerena aplikaciona alokacija na validiranoj putanji

PREKORAČENJA SPOLJAŠNJE GRANICE LATENCIJE

PRE Ponavljajuća

POSLE 0 uočeno tokom validacije

Tokom validacije nisu uočena prekoračenja

Merenja latencije pokazuju značajno poboljšanje i u ponašanju repa distribucije latencije i u maksimalnom posmatranom trajanju traversiranja. Tokom end-to-end validacije nisu zabeležena prekoračenja spoljašnje granice latencije. Ovo su rezultati za testirano opterećenje, a ne garancija hard real-time izvršavanja.

Hardverska merenja pokazuju da je redizajn značajno smanjio udeo izmerenih CPU ciklusa povezanih sa zastojima zbog memorije. To potvrđuje da je optimizacija adresirala ponašanje pristupa memoriji identifikovano profilisanjem, umesto da samo premesti posao na drugi deo sistema.

Smanjeni memorijski footprint grafa i izmerena aplikaciona alokacija u skladu su sa prelaskom sa objektno-teške reprezentacije na kompaktne primitivne podatke i unapred alocirano radno stanje traversiranja.

Merenja zastoja zbog memorije obavljena su tokom izolovanog traversiranja u stabilnom režimu rada pod punim opterećenjem, bez šuma od alokacija i GC pauza u merenoj putanji izvršavanja. Rezultati su zato usmereni na ponašanje pristupa memoriji tokom samog traversiranja.

Zamena objektno-teškog grafa kompaktnom CSR reprezentacijom značajno je smanjila latenciju traversiranja, zastoje zbog memorije i memorijski footprint grafa. Rezultat je bila data-oriented izvršna putanja čije su se izmerene performanse mnogo više približile zahtevima aplikacije za end-to-end latenciju. Izmereni rezultati validacije nisu garancija hard real-time izvršavanja niti determinističke gornje granice latencije.

INŽENJERSKI DOPRINOS

SWARCS je vodio analizu performansi i arhitektonski redizajn putanje traversiranja elektroenergetske mreže, od identifikovanja dominantnog ograničenja izvršavanja do validacije implementacije prema zahtevima za latencijom. Angažovanje je obuhvatilo forenzičku analizu performansi, reprezentaciju grafa, konkurentne promene topologije, izolaciju ažuriranja metrika i analizu alokacija na hot-path putanji.

ODGOVORNOSTI

Sprovedena analiza performansi pomoću alata Linux perf i async-profiler
Identifikovani zastoji zbog pristupa memoriji kao dominantno ograničenje traversiranja grafa
Objektno-teški graf zamenjen kompaktnom Compressed Sparse Row reprezentacijom
Implementirano traversiranje topologije pomoću kontinualnih primitivnih nizova
Razdvojene strukturne izmene topologije od čestih ažuriranja metrika
Uvedeni nepromenljivi CSR snapshot-i i atomska zamena reference
Smanjen memorijski footprint grafa sa približno 2,8 GB na 450 MB
Uklonjena izmerena aplikaciona alokacija sa hot-path putanje traversiranja
Performanse traversiranja procenjene prema normalnim i internim pragovima latencije
Redizajnirano traversiranje validirano pri opterećenju do približno 500.000 telemetrijskih događaja u sekundi i približno 20.000 čvorova mreže

KLJUČNA PORUKA

PROJEKTUJTE RASPORED PODATAKA PREMA NAČINU NA KOJI IM CPU STVARNO PRISTUPA.

DATA-ORIENTED RASPORED MEMORIJE

CACHE-FRIENDLY REPREZENTACIJA GRAFA

NEPROMENLJIVI TOPOLOŠKI SNAPSHOT-I

HOT-PATH SA MALOM ALOKACIJOM

MERENJE PONAŠANJA PRISTUPA MEMORIJI

EKSPLICITNI PRAGOVI LATENCIJE

Algoritamska složenost samo je jedan deo performansi u realnim sistemima. Fizička reprezentacija podataka određuje koliko indirekcije, memorijskog saobraćaja, alokacija i pristupa udaljenim lokacijama izvršna putanja zahteva. Inženjering performansi zato mora da posmatra raspored podataka, ponašanje pristupa memoriji, alokacije i konkurentnost kao međusobno povezane osobine izvršne putanje. PERFORMANSE SU SVOJSTVO CELE IZVRŠNE PUTANJE. Princip koji se može primeniti i u drugim sistemima jeste da se prvo izmeri stvarno usko grlo, a zatim usklade reprezentacija podataka i model ažuriranja sa opterećenjem. Rezultat treba validirati prema eksplicitnim operativnim zahtevima, bez mešanja izmerenih performansi sa garancijom determinističkog vremena izvršavanja.

NAZAD NA STUDIJE SLUČAJA