TL;DR: Pred štirimi leti sem zapustil Google z idejo za novo orodje za nadzor strežnikov. Ideja je bila združiti običajno izolirane funkcije v eno storitev in analiza dnevnika, zbiranje meritev, in nadzorne plošče. Eno od načel je, da mora biti storitev resnična hitro, ki zagotavlja devops enostavno, interaktivno in prijetno izkušnjo. To zahteva obdelavo večgigabajtnih naborov podatkov v delčkih sekunde, pri čemer ostajate znotraj proračuna. Obstoječa orodja za upravljanje dnevnikov so pogosto počasna in okorna, zato smo se soočili z dobrim izzivom: pametnim oblikovanjem orodja, ki bo uporabnikom omogočilo novo izkušnjo.
Ta članek opisuje, kako smo pri Scalyr rešili to težavo z uporabo starih šolskih metod, pristopa surove sile, odpravljanja nepotrebnih plasti in izogibanja kompleksnim podatkovnim strukturam. Te lekcije lahko uporabite pri svojih inženirskih težavah.
Moč stare šole
Analiza dnevnika se običajno začne z iskanjem: poiščite vsa sporočila, ki se ujemajo z določenim vzorcem. V Scalyrju so to desetine ali stotine gigabajtov dnevnikov iz številnih strežnikov. Sodobni pristopi praviloma vključujejo konstrukcijo neke kompleksne podatkovne strukture, optimizirane za iskanje. To sem zagotovo videl na Googlu, kjer so zelo dobri v teh stvareh. Vendar smo se odločili za veliko bolj grob pristop: linearno skeniranje dnevnikov. In delovalo je – nudimo vmesnik, po katerem je mogoče iskati, ki je veliko hitrejši od naših konkurentov (glejte animacijo na koncu).
Ključni vpogled je bil, da so sodobni procesorji res zelo hitri pri preprostih in enostavnih operacijah. To je zlahka spregledati v zapletenih večplastnih sistemih, ki so odvisni od hitrosti V/I in omrežnih operacij, in takšni sistemi so danes zelo pogosti. Zato smo razvili dizajn, ki zmanjšuje plasti in odvečne smeti. Z več procesorji in vzporednimi strežniki hitrost iskanja doseže 1 TB na sekundo.
Ključni zaključki tega članka:
- Iskanje s surovo silo je izvedljiv pristop za reševanje obsežnih problemov v realnem svetu.
- Surova sila je tehnika načrtovanja in ne rešitev brez dela. Kot vsaka tehnika je tudi ta bolj primerna za nekatere težave kot za druge in jo je mogoče izvajati slabo ali dobro.
- Surova sila je še posebej dobra za doseganje stabilno produktivnost.
- Učinkovita uporaba grobe sile zahteva optimizacijo kode in uporabo zadostnih virov ob pravem času. Primeren je, če so vaši strežniki pod veliko neuporabniško obremenitvijo in uporabniške operacije ostajajo prednostna naloga.
- Zmogljivost je odvisna od zasnove celotnega sistema, ne le od algoritma notranje zanke.
(Ta članek opisuje iskanje podatkov v pomnilniku. V večini primerov, ko uporabnik izvede iskanje po dnevniku, so ga strežniki Scalyr že predpomnili. Naslednji članek bo razpravljal o iskanju nepredpomnjenih dnevnikov. Veljajo enaka načela: učinkovita koda, groba sila z velikimi računalniškimi viri).
Metoda surove sile
Običajno se velik nabor podatkov išče z uporabo indeksa ključnih besed. Ko se uporablja za dnevnike strežnika, to pomeni iskanje vsake edinstvene besede v dnevniku. Za vsako besedo morate narediti seznam vseh vključkov. To olajša iskanje vseh sporočil s to besedo, na primer »napaka«, »firefox« ali »transakcija_16851951« – samo poglejte v kazalo.
Ta pristop sem uporabil pri Googlu in dobro je deloval. Toda v Scalyrju iščemo dnevnike bajt za bajtom.
Zakaj? Z abstraktnega algoritemskega vidika so indeksi ključnih besed veliko bolj učinkoviti kot iskanja na silo. Vendar ne prodajamo algoritmov, prodajamo zmogljivost. Zmogljivost pa ni le algoritm, ampak tudi sistemski inženiring. Upoštevati moramo vse: količino podatkov, vrsto iskanja, razpoložljivo strojno in programsko opremo. Odločili smo se, da je za naš problem nekaj, kot je "grep", primernejše od indeksa.
Indeksi so odlični, vendar imajo omejitve. Eno besedo je enostavno najti. Toda iskanje sporočil z več besedami, kot sta »googlebot« in »404«, je veliko težje. Iskanje besedne zveze, kot je 'neulovljena izjema', zahteva bolj okoren indeks, ki beleži ne samo vsa sporočila s to besedo, ampak tudi specifično lokacijo besede.
Prava težava nastopi, ko ne iščete besed. Recimo, da želite videti, koliko prometa prihaja od botov. Prva misel je iskanje v dnevnikih za besedo 'bot'. Tako boste našli nekaj robotov: Googlebot, Bingbot in mnoge druge. Toda tukaj 'bot' ni beseda, ampak del nje. Če v indeksu iščemo 'bot', ne bomo našli nobene objave z besedo 'Googlebot'. Če preverite vsako besedo v kazalu in nato pregledate kazalo za najdene ključne besede, se bo iskanje močno upočasnilo. Zaradi tega nekateri programi za dnevnike ne dovoljujejo iskanja po delnih besedah ali (v najboljšem primeru) dovoljujejo posebno sintakso z nižjo zmogljivostjo. Temu se želimo izogniti.
Druga težava so ločila. Ali želite najti vse zahteve od 50.168.29.7? Kaj pa dnevniki odpravljanja napak, ki vsebujejo [error]? Indeksi običajno preskočijo ločila.
Končno, inženirji obožujejo zmogljiva orodja in včasih je težavo mogoče rešiti le z regularnim izrazom. Indeks ključnih besed za to ni preveč primeren.
Poleg tega indeksi kompleksen. Vsako sporočilo je treba dodati na več seznamov ključnih besed. Te sezname je treba vedno hraniti v obliki, ki omogoča preprosto iskanje. Poizvedbe s frazami, fragmenti besed ali regularnimi izrazi je treba prevesti v operacije z več seznami, rezultate pa pregledati in združiti, da se ustvari niz rezultatov. V kontekstu obsežne storitve z več najemniki ta kompleksnost ustvarja težave z zmogljivostjo, ki niso vidne pri analizi algoritmov.
Indeksi ključnih besed prav tako zavzamejo veliko prostora, shranjevanje pa je velik strošek v sistemu za upravljanje dnevnikov.
Po drugi strani pa lahko vsako iskanje porabi veliko računalniške moči. Naši uporabniki cenijo hitra iskanja edinstvenih poizvedb, vendar so takšne poizvedbe razmeroma redke. Za tipične iskalne poizvedbe, na primer za nadzorno ploščo, uporabljamo posebne tehnike (opisali jih bomo v naslednjem članku). Druge zahteve so dovolj redke, da vam je le redko treba obdelati več kot eno naenkrat. Vendar to ne pomeni, da naši strežniki niso zasedeni: zasedeni so s sprejemanjem, analiziranjem in stiskanjem novih sporočil, ocenjevanjem opozoril, stiskanjem starih podatkov itd. Tako imamo precejšnjo ponudbo procesorjev, ki jih je mogoče uporabiti za izvajanje poizvedb.
Surova sila deluje, če imate grobo težavo (in veliko sile)
Surova sila najbolje deluje pri preprostih težavah z majhnimi notranjimi zankami. Pogosto lahko notranjo zanko optimizirate za delovanje pri zelo visokih hitrostih. Če je koda kompleksna, jo je veliko težje optimizirati.
Naša iskalna koda je prvotno imela precej veliko notranjo zanko. Sporočila na straneh shranjujemo pri 4K; vsaka stran vsebuje nekaj sporočil (v UTF-8) in metapodatke za vsako sporočilo. Metapodatki so struktura, ki kodira dolžino vrednosti, notranji ID sporočila in druga polja. Cikel iskanja je izgledal takole:
To je poenostavljena različica dejanske kode. Toda tudi tukaj je vidnih več postavitev objektov, kopij podatkov in klicev funkcij. JVM je precej dober pri optimizaciji klicev funkcij in dodeljevanju kratkotrajnih objektov, zato je ta koda delovala bolje, kot smo si zaslužili. Med testiranjem so ga kupci precej uspešno uporabljali. Toda sčasoma smo ga popeljali na višjo raven.
(Morda se boste vprašali, zakaj shranjujemo sporočila v tem formatu s 4K stranmi, besedilom in metapodatki, namesto da delamo neposredno z dnevniki. Obstaja veliko razlogov, ki se nanašajo na dejstvo, da je motor Scalyr v notranjosti bolj podoben porazdeljeni bazi podatkov kot datotečni sistem. Besedilno iskanje je pogosto kombinirano s filtri v slogu DBMS na robovih po razčlenjevanju dnevnika. Istočasno lahko iščemo več tisoč dnevnikov hkrati in preproste besedilne datoteke niso primerne za naše transakcijsko, podvojeno, porazdeljeno upravljanje podatkov).
Sprva se je zdelo, da takšna koda ni preveč primerna za brute force optimizacijo. "Pravo delo" v String.indexOf() sploh ni prevladoval v profilu CPU. To pomeni, da samo optimizacija te metode ne bi prinesla bistvenega učinka.
Tako se zgodi, da metapodatke shranimo na začetku vsake strani, besedilo vseh sporočil v UTF-8 pa je zapakirano na drugem koncu. Izkoristili smo to in smo preoblikovali zanko za iskanje po celotni strani hkrati:
Ta različica deluje neposredno na pogled raw byte[] in išče vsa sporočila hkrati po celotni strani 4K.
To je veliko lažje optimizirati za metodo surove sile. Notranja iskalna zanka se kliče hkrati za celotno stran 4K in ne za vsako objavo posebej. Ni kopiranja podatkov, ni dodeljevanja objektov. In bolj zapletene metapodatkovne operacije se kličejo le, ko je rezultat pozitiven, in ne za vsako sporočilo. Na ta način smo odpravili ogromno dodatnih stroškov, preostanek obremenitve pa je skoncentriran v majhni notranji iskalni zanki, ki je zelo primerna za nadaljnjo optimizacijo.
Naš dejanski iskalni algoritem temelji na . Podoben je algoritmu Boyer-Moore, ki preskoči približno dolžino iskalnega niza v vsakem koraku. Glavna razlika je v tem, da preverja dva bajta hkrati, da zmanjša lažna ujemanja.
Naša izvedba zahteva ustvarjanje 64 K iskalne tabele za vsako iskanje, vendar to ni nič v primerjavi z gigabajti podatkov, po katerih iščemo. Notranja zanka obdeluje več gigabajtov na sekundo v enem jedru. V praksi je stabilna zmogljivost okoli 1,25 GB na sekundo za vsako jedro in obstaja prostor za izboljšave. Možno je odpraviti nekaj režijskih stroškov zunaj notranje zanke in nameravamo eksperimentirati z notranjo zanko v C namesto Jave.
Uporabljamo silo
Razpravljali smo o tem, da je iskanje po dnevnikih mogoče izvesti "približno", toda koliko "moči" imamo? Kar precej.
1 jedro: Ob pravilni uporabi je eno jedro sodobnega procesorja samo po sebi precej zmogljivo.
8 jeder: Trenutno delujemo na strežnikih Amazon hi1.4xlarge in i2.4xlarge SSD, vsak z 8 jedri (16 niti). Kot je navedeno zgoraj, so ta jedra običajno zaposlena z operacijami v ozadju. Ko uporabnik izvede iskanje, se operacije v ozadju prekinejo, kar sprosti vseh 8 jeder za iskanje. Iskanje se običajno zaključi v delčku sekunde, nato pa se delo v ozadju nadaljuje (program za dušenje zagotavlja, da val iskalnih poizvedb ne moti pomembnega dela v ozadju).
16 jeder: zaradi zanesljivosti organiziramo strežnike v skupine master/slave. Vsak master ima pod svojim poveljstvom en SSD in en EBS strežnik. Če se glavni strežnik zruši, SSD strežnik takoj prevzame njegovo mesto. Skoraj ves čas glavni in podrejeni delujeta dobro, tako da je po vsakem podatkovnem bloku mogoče iskati na dveh različnih strežnikih (podrejeni strežnik EBS ima šibak procesor, zato ga ne upoštevamo). Mednje razdelimo nalogo, tako da imamo na voljo skupno 16 jeder.
Veliko jeder: V bližnji prihodnosti bomo podatke porazdelili po strežnikih tako, da bodo vsi sodelovali pri obdelavi vsake netrivialne zahteve. Vsako jedro bo delovalo. [Opomba: uresničili smo načrt in povečali hitrost iskanja na 1 TB/s, glej opombo na koncu članka].
Enostavnost zagotavlja zanesljivost
Druga prednost metode surove sile je njena dokaj dosledna učinkovitost. Običajno iskanje ni zelo občutljivo na podrobnosti težave in nabora podatkov (verjetno se zato imenuje "grobo").
Indeks ključnih besed včasih daje neverjetno hitre rezultate, drugič pa ne. Recimo, da imate 50 GB dnevnikov, v katerih se izraz 'customer_5987235982' pojavi natanko trikrat. Iskanje tega izraza šteje tri lokacije neposredno iz indeksa in se zaključi takoj. Toda zapletena iskanja z nadomestnimi znaki lahko pregledajo na tisoče ključnih besed in trajajo dolgo.
Po drugi strani pa iskanja na silo izvajajo bolj ali manj enako hitro za vsako poizvedbo. Iskanje po dolgih besedah je boljše, vendar je tudi iskanje po enem znaku precej hitro.
Preprostost metode surove sile pomeni, da je njena učinkovitost blizu teoretičnega maksimuma. Manj je možnosti za nepričakovane preobremenitve diska, spor za zaklepanje, lovljenje kazalca in na tisoče drugih razlogov za neuspeh. Pravkar sem pogledal zahteve, ki so jih prejšnji teden vložili uporabniki Scalyrja na našem najbolj obremenjenem strežniku. Bilo je 14 prošenj. Točno osem jih je trajalo več kot eno sekundo; 000 % končano v 99 milisekundah (če še niste uporabljali orodij za analizo dnevnika, verjemite mi: hitro je).
Stabilno in zanesljivo delovanje je pomembno za preprosto uporabo storitve. Če občasno zaostaja, ga bodo uporabniki razumeli kot nezanesljivega in ga neradi uporabljajo.
Iskanje dnevnika v akciji
Tukaj je kratka animacija, ki prikazuje Scalyr iskanje v akciji. Imamo demo račun, kamor uvozimo vsak dogodek v vsako javno skladišče Github. V tej predstavitvi pregledam podatke za en teden: približno 600 MB neobdelanih dnevnikov.
Video je bil posnet v živo, brez posebne priprave, na mojem namizju (približno 5000 kilometrov od strežnika). Učinkovitost, ki jo boste videli, je v veliki meri posledica , kot tudi hitro in zanesljivo zaledje. Kadarkoli pride do premora brez indikatorja 'nalaganja', se ustavim jaz, da lahko preberete, kaj bom pritisnil.
Na koncu
Pri obdelavi velikih količin podatkov je pomembno izbrati dober algoritem, vendar "dober" ne pomeni "fancy". Razmislite, kako bo vaša koda delovala v praksi. Teoretična analiza algoritmov izpusti nekatere dejavnike, ki so lahko zelo pomembni v resničnem svetu. Enostavnejše algoritme je lažje optimizirati in so bolj stabilni v robnih situacijah.
Razmislite tudi o kontekstu, v katerem se bo koda izvajala. V našem primeru potrebujemo dovolj zmogljive strežnike za upravljanje opravil v ozadju. Uporabniki relativno redko sprožijo iskanje, zato si lahko izposodimo celotno skupino strežnikov za kratko obdobje, ki je potrebno za dokončanje vsakega iskanja.
Z uporabo metode surove sile smo izvedli hitro, zanesljivo in prilagodljivo iskanje po nizu dnevnikov. Upamo, da bodo te ideje koristne za vaše projekte.
Pravka: Naslov in besedilo sta se spremenila iz »Iskanje pri 20 GB na sekundo« v »Iskanje pri 1 TB na sekundo«, da odražata povečanje zmogljivosti v zadnjih nekaj letih. To povečanje hitrosti je predvsem posledica sprememb v vrsti in številu strežnikov EC2, ki jih danes postavljamo, da bi služili naši povečani bazi strank. Kmalu prihajajo spremembe, ki bodo zagotovile nov dramatičen dvig operativne učinkovitosti, in komaj čakamo, da jih delimo.
Vir: www.habr.com