TL;DR: Prije četiri godine napustio sam Google s idejom za novi alat za praćenje servera. Ideja je bila kombinirati obično izolirane funkcije u jednu uslugu i analiza dnevnika, prikupljanje metrike, i kontrolne table. Jedan od principa je da usluga mora biti istinita brzo, pružajući devops jednostavno, interaktivno i ugodno iskustvo. Ovo zahteva obradu višegigabajtnih skupova podataka u delićima sekunde, a da pritom ostane u okviru budžeta. Postojeći alati za upravljanje dnevnikom su često spori i nezgrapni, pa smo se suočili s dobrim izazovom: pametno dizajniranje alata kako bi korisnicima pružili novo iskustvo.
Ovaj članak opisuje kako smo mi u Scalyru riješili ovaj problem primjenom starih školskih metoda, grubog pristupa, eliminacijom nepotrebnih slojeva i izbjegavanjem složenih struktura podataka. Ove lekcije možete primijeniti na vlastite inženjerske probleme.
Old School Power
Analiza dnevnika obično počinje pretragom: pronađite sve poruke koje odgovaraju određenom obrascu. U Scalyru su to desetine ili stotine gigabajta dnevnika sa mnogih servera. Savremeni pristupi, po pravilu, podrazumevaju izgradnju neke složene strukture podataka optimizovane za pretragu. Ovo sam sigurno vidio na Guglu, gdje su prilično dobri u ovakvim stvarima. Ali odlučili smo se na mnogo grublji pristup: linearno skeniranje dnevnika. I uspjelo je – nudimo sučelje za pretraživanje koje je za redove veličine brže od naših konkurenata (pogledajte animaciju na kraju).
Ključni uvid je bio da su moderni procesori zaista veoma brzi u jednostavnim, jednostavnim operacijama. Ovo je lako propustiti u složenim, višeslojnim sistemima koji se oslanjaju na I/O brzinu i mrežne operacije, a takvi sistemi su danas vrlo česti. Stoga smo razvili dizajn koji minimizira slojeve i višak otpada. Sa više procesora i servera paralelno, brzina pretraživanja dostiže 1 TB u sekundi.
Ključni zaključci iz ovog članka:
- Brute force pretraga je održiv pristup za rješavanje problema velikih razmjera u stvarnom svijetu.
- Brute force je tehnika dizajna, a ne rješenje bez posla. Kao i svaka tehnika, ona je bolje prilagođena nekim problemima od drugih i može se loše ili dobro implementirati.
- Bruta sila je posebno dobra za postizanje stabilan produktivnost.
- Efikasna upotreba grube sile zahteva optimizaciju koda i primenu dovoljnih resursa u pravo vreme. Pogodan je ako su vaši serveri pod velikim opterećenjem koje nisu korisnici, a korisničke operacije ostaju prioritet.
- Performanse zavise od dizajna čitavog sistema, a ne samo od algoritma unutrašnje petlje.
(Ovaj članak opisuje traženje podataka u memoriji. U većini slučajeva, kada korisnik izvrši pretragu dnevnika, Scalyr serveri su ga već keširali. Sljedeći članak će raspravljati o traženju nekeširanih dnevnika. Primjenjuju se isti principi: efikasan kod, brute force sa velikim računskim resursima).
Metoda grube sile
Tradicionalno, veliki skup podataka se pretražuje pomoću indeksa ključnih riječi. Kada se primjenjuje na zapisnike servera, to znači traženje svake jedinstvene riječi u dnevniku. Za svaku riječ morate napraviti listu svih uključenja. Ovo olakšava pronalaženje svih poruka sa ovom riječju, na primjer 'error', 'firefox' ili "transaction_16851951" - samo pogledajte u indeksu.
Koristio sam ovaj pristup u Google-u i dobro je funkcionisao. Ali u Scalyru pretražujemo dnevnike bajt po bajt.
Zašto? Sa apstraktne algoritamske tačke gledišta, indeksi ključnih reči su mnogo efikasniji od pretraživanja grubom silom. Međutim, mi ne prodajemo algoritme, mi prodajemo performanse. A performanse se ne odnose samo na algoritme, već i na sistemski inženjering. Moramo uzeti u obzir sve: količinu podataka, vrstu pretrage, raspoloživi hardverski i softverski kontekst. Odlučili smo da je za naš konkretni problem nešto poput 'grep' bolje prikladnije od indeksa.
Indeksi su odlični, ali imaju ograničenja. Jednu riječ je lako pronaći. Ali traženje poruka s više riječi, kao što su 'googlebot' i '404', mnogo je teže. Pretraživanje fraze kao što je 'neuhvaćeni izuzetak' zahtijeva glomazniji indeks koji ne bilježi samo sve poruke s tom riječi, već i specifičnu lokaciju riječi.
Prava poteškoća dolazi kada ne tražite riječi. Recimo da želite vidjeti koliki promet dolazi od botova. Prva pomisao je da pretražite dnevnike za riječ 'bot'. Ovako ćete pronaći neke botove: Googlebot, Bingbot i mnoge druge. Ali ovdje 'bot' nije riječ, već dio toga. Ako tražimo 'bot' u indeksu, nećemo pronaći postove sa riječju 'Googlebot'. Ako provjerite svaku riječ u indeksu, a zatim skenirate indeks u potrazi za pronađenim ključnim riječima, pretraga će se jako usporiti. Kao rezultat toga, neki programi dnevnika ne dozvoljavaju pretraživanje djelomičnim riječima ili (u najboljem slučaju) dozvoljavaju posebnu sintaksu sa nižim performansama. Ovo želimo izbjeći.
Drugi problem je interpunkcija. Želite li pronaći sve zahtjeve od 50.168.29.7? Šta je sa evidencijama za otklanjanje grešaka koje sadrže [error]? Podskripti obično preskaču interpunkciju.
Konačno, inženjeri vole moćne alate, a ponekad se problem može riješiti samo regularnim izrazom. Indeks ključnih riječi nije baš pogodan za ovo.
Osim toga, indeksi kompleks. Svaku poruku treba dodati na nekoliko lista ključnih riječi. Ove liste treba stalno čuvati u lako pretraživom formatu. Upiti s frazama, fragmentima riječi ili regularnim izrazima moraju biti prevedeni u operacije s više lista, a rezultati skenirani i kombinirani da bi se proizveo skup rezultata. U kontekstu opsežne usluge sa više zakupaca, ova složenost stvara probleme s performansama koji nisu vidljivi prilikom analize algoritama.
Indeksi ključnih riječi također zauzimaju puno prostora, a skladištenje je veliki trošak u sistemu upravljanja dnevnikom.
S druge strane, svako pretraživanje može potrošiti mnogo računarske snage. Naši korisnici cijene brzu pretragu jedinstvenih upita, ali se takvi upiti postavljaju relativno rijetko. Za tipične upite za pretraživanje, na primjer, za kontrolnu ploču, koristimo posebne tehnike (opisat ćemo ih u sljedećem članku). Ostali zahtjevi su dovoljno rijetki da rijetko morate obraditi više od jednog istovremeno. Ali to ne znači da naši serveri nisu zauzeti: oni su zauzeti poslom primanja, analize i kompresije novih poruka, procjenom upozorenja, komprimiranjem starih podataka itd. Dakle, imamo prilično značajnu ponudu procesora koji se mogu koristiti za izvršavanje upita.
Brute force radi ako imate grubi problem (i mnogo sile)
Brute force najbolje radi na jednostavnim problemima s malim unutrašnjim petljama. Često možete optimizirati internu petlju za rad pri vrlo velikim brzinama. Ako je kod složen, mnogo ga je teže optimizirati.
Naš kod za pretragu je prvobitno imao prilično veliku unutrašnju petlju. Poruke pohranjujemo na stranicama u 4K; svaka stranica sadrži neke poruke (u UTF-8) i metapodatke za svaku poruku. Metapodaci su struktura koja kodira dužinu vrijednosti, interni ID poruke i druga polja. Ciklus pretrage je izgledao ovako:
Ovo je pojednostavljena verzija stvarnog koda. Ali čak i ovdje, višestruki smještaji objekata, kopije podataka i pozivi funkcija su vidljivi. JVM je prilično dobar u optimizaciji poziva funkcija i dodjeli efemernih objekata, tako da je ovaj kod radio bolje nego što smo zaslužili. Tokom testiranja, kupci su ga prilično uspješno koristili. Ali na kraju smo to podigli na viši nivo.
(Možete se zapitati zašto pohranjujemo poruke u ovom formatu sa 4K stranicama, tekstom i metapodacima, umjesto da radimo direktno sa zapisnicima. Postoji mnogo razloga koji se svode na činjenicu da interno Scalyr engine više liči na distribuiranu bazu podataka nego na sistem datoteka. Pretraživanje teksta se često kombinuje sa filterima u DBMS stilu na marginama nakon raščlanjivanja dnevnika. Možemo istovremeno pretraživati više hiljada dnevnika odjednom, a jednostavne tekstualne datoteke nisu pogodne za naše transakcijsko, replicirano, distribuirano upravljanje podacima).
U početku se činilo da takav kod nije baš pogodan za brute force optimizaciju. "Pravi posao" u String.indexOf() nije čak ni dominirao CPU profilom. Odnosno, samo optimizacija ove metode ne bi donijela značajan učinak.
Događa se da metapodatke pohranjujemo na početku svake stranice, a tekst svih poruka u UTF-8 je pakiran na drugom kraju. Koristeći ovo, prepisali smo petlju da pretražimo cijelu stranicu odjednom:
Ova verzija radi direktno na prikazu raw byte[] i pretražuje sve poruke odjednom na cijeloj 4K stranici.
Ovo je mnogo lakše optimizirati za metodu grube sile. Interna petlja pretraživanja poziva se istovremeno za cijelu 4K stranicu, a ne zasebno za svaki post. Nema kopiranja podataka, nema alokacije objekata. A složenije operacije metapodataka pozivaju se samo kada je rezultat pozitivan, a ne na svakoj poruci. Na ovaj način smo eliminisali gomilu troškova, a ostatak opterećenja je koncentrisan u maloj internoj petlji pretraživanja, koja je veoma pogodna za dalju optimizaciju.
Naš stvarni algoritam pretraživanja je zasnovan na . Sličan je Boyer-Moore algoritmu, preskačući približno dužinu niza pretraživanja u svakom koraku. Glavna razlika je u tome što provjerava dva bajta u isto vrijeme kako bi minimizirala lažna podudaranja.
Naša implementacija zahtijeva kreiranje 64K tabele za pretraživanje za svaku pretragu, ali to nije ništa u poređenju sa gigabajtima podataka koje pretražujemo. Unutrašnja petlja obrađuje nekoliko gigabajta u sekundi na jednoj jezgri. U praksi, stabilne performanse su oko 1,25 GB po sekundi na svakom jezgru i ima prostora za poboljšanje. Moguće je eliminisati dio nadmetanja izvan unutrašnje petlje, a planiramo eksperimentirati sa unutrašnjom petljom u C umjesto u Javi.
Koristimo silu
Razgovarali smo o tome da se pretraživanje dnevnika može implementirati "grubo", ali koliko "snage" imamo? Prilično.
1 jezgro: Kada se pravilno koristi, jedna jezgra modernog procesora je sama po sebi prilično moćna.
8 jezgara: Trenutno radimo na Amazon hi1.4xlarge i i2.4xlarge SSD serverima, svaki sa 8 jezgara (16 niti). Kao što je gore spomenuto, ove jezgre su obično zauzete pozadinskim operacijama. Kada korisnik izvrši pretragu, pozadinske operacije se suspenduju, oslobađajući svih 8 jezgri za pretragu. Pretraživanje se obično završava u djeliću sekunde, nakon čega se nastavlja rad u pozadini (program za prigušivanje osigurava da gomila upita za pretraživanje ne ometa važan rad u pozadini).
16 jezgara: radi pouzdanosti, organiziramo servere u master/slave grupe. Svaki master ima jedan SSD i jedan EBS server pod svojom komandom. Ako se glavni server sruši, SSD server odmah zauzima njegovo mjesto. Gotovo cijelo vrijeme, master i slave rade dobro, tako da se svaki blok podataka može pretraživati na dva različita servera (EBS slave server ima slab procesor, pa ga ne uzimamo u obzir). Zadatak podijelimo između njih, tako da imamo na raspolaganju ukupno 16 jezgri.
Mnogo jezgara: U bliskoj budućnosti ćemo distribuirati podatke po serverima na način da svi oni učestvuju u obradi svakog netrivijalnog zahtjeva. Svako jezgro će raditi. [Bilješka: implementirali smo plan i povećali brzinu pretraživanja na 1 TB/s, vidi napomenu na kraju članka].
Jednostavnost osigurava pouzdanost
Još jedna prednost metode grube sile je njena prilično konzistentna izvedba. Tipično, pretraga nije previše osjetljiva na detalje problema i skupa podataka (valjda se zato i zove "grubo").
Indeks ključnih riječi ponekad daje nevjerovatno brze rezultate, a drugi put ne. Recimo da imate 50 GB dnevnika u kojima se termin 'customer_5987235982' pojavljuje tačno tri puta. Pretraživanje ovog pojma broji tri lokacije direktno iz indeksa i završit će se odmah. Ali složena pretraživanja džoker znakova mogu skenirati hiljade ključnih riječi i potrajati dugo.
S druge strane, brute force pretrage rade manje-više istom brzinom za bilo koji upit. Pretraživanje dugih riječi je bolje, ali čak i traženje jednog znaka je prilično brzo.
Jednostavnost metode grube sile znači da je njen učinak blizu svog teoretskog maksimuma. Manje je opcija za neočekivana preopterećenja diska, svađe oko zaključavanja, jurenje pokazivača i hiljade drugih razloga za neuspjeh. Upravo sam pogledao zahtjeve korisnika Scalyra prošle sedmice na našem najprometnijem serveru. Bilo je 14 zahtjeva. Za tačno osam njih trebalo je više od jedne sekunde; 000% završeno u roku od 99 milisekundi (ako niste koristili alate za analizu dnevnika, vjerujte mi: brzo je).
Stabilna, pouzdana izvedba je važna za jednostavno korištenje usluge. Ako povremeno zaostaje, korisnici će ga smatrati nepouzdanim i nerado ga koriste.
Log pretraga u akciji
Evo kratke animacije koja prikazuje Scalyr pretragu u akciji. Imamo demo nalog na koji uvozimo svaki događaj u svako javno Github spremište. U ovom demo-u ispitujem sedmičnu vrijednost podataka: otprilike 600 MB neobrađenih dnevnika.
Video je snimljen uživo, bez posebne pripreme, na mom desktopu (oko 5000 kilometara od servera). Performanse koje ćete vidjeti uglavnom su zaslužne za to , kao i brz i pouzdan backend. Kad god postoji pauza bez indikatora 'učitavanja', ja pauziram da biste mogli pročitati šta ću pritisnuti.
U zaključku
Prilikom obrade velikih količina podataka važno je odabrati dobar algoritam, ali „dobar“ ne znači „fensi“. Razmislite o tome kako će vaš kod funkcionirati u praksi. Teorijska analiza algoritama izostavlja neke faktore koji mogu biti od velike važnosti u stvarnom svijetu. Jednostavnije algoritme je lakše optimizirati i stabilniji su u rubnim situacijama.
Također razmislite o kontekstu u kojem će se kod izvršiti. U našem slučaju, potrebni su nam dovoljno moćni serveri za upravljanje pozadinskim zadacima. Korisnici relativno rijetko pokreću pretrage, tako da možemo posuditi cijelu grupu servera na kratak period potreban da se završi svako pretraživanje.
Koristeći metodu grube sile, implementirali smo brzu, pouzdanu, fleksibilnu pretragu u nizu dnevnika. Nadamo se da su ove ideje korisne za vaše projekte.
Pravka: Naslov i tekst su se promijenili iz "Traži pri 20 GB u sekundi" u "Traži pri 1 TB u sekundi" kako bi odražavali povećanje performansi u posljednjih nekoliko godina. Ovo povećanje brzine je prvenstveno zbog promjena u tipu i broju EC2 servera koje danas postavljamo da opslužuju našu povećanu bazu korisnika. Uskoro dolaze promjene koje će pružiti još jedno dramatično povećanje operativne efikasnosti i jedva čekamo da ih podijelimo.
izvor: www.habr.com