TL;DR: Prije četiri godine napustio sam Google s idejom za novi alat za nadzor poslužitelja. Ideja je bila kombinirati obično izolirane funkcije u jednu uslugu i analiza dnevnika, prikupljanje metrika, i nadzorne ploče. Jedno od načela je da usluga mora biti istinska brzo, pružajući devops-u jednostavno, interaktivno i ugodno iskustvo. To zahtijeva obradu skupova podataka od više gigabajta u djeliću sekunde, a da ostane unutar proračuna. Postojeći alati za upravljanje zapisnicima često su spori i nezgrapni, pa smo se suočili s dobrim izazovom: pametnim dizajnom alata koji će korisnicima pružiti novo iskustvo.
Ovaj članak opisuje kako smo mi u Scalyr-u riješili ovaj problem primjenom metoda stare škole, brute force pristupa, eliminacijom nepotrebnih slojeva i izbjegavanjem složenih struktura podataka. Ove lekcije možete primijeniti na vlastite inženjerske probleme.
Moć stare škole
Analiza dnevnika obično počinje pretraživanjem: pronađite sve poruke koje odgovaraju određenom uzorku. U Scalyru su to deseci ili stotine gigabajta zapisa s mnogih poslužitelja. Suvremeni pristupi u pravilu uključuju konstrukciju neke složene podatkovne strukture optimizirane za pretraživanje. Sigurno sam ovo vidio na Googleu, gdje su prilično dobri u ovakvim stvarima. Ali odlučili smo se za mnogo grublji pristup: linearno skeniranje trupaca. I uspjelo je - nudimo sučelje koje se može pretraživati i koje je nekoliko redova veličine brže od naših konkurenata (pogledajte animaciju na kraju).
Ključni uvid bio je da su moderni procesori doista vrlo brzi u jednostavnim, jasnim operacijama. To je lako propustiti u složenim, višeslojnim sustavima koji se oslanjaju na I/O brzinu i mrežne operacije, a takvi su sustavi danas vrlo česti. Stoga smo razvili dizajn koji minimalizira slojeve i višak otpadaka. Uz paralelno više procesora i poslužitelja, brzina pretraživanja doseže 1 TB u sekundi.
Ključni zaključci iz ovog članka:
- Brute-force pretraživanje je održiv pristup za rješavanje stvarnih problema velikih razmjera.
- Brute force je tehnika dizajna, a ne rješenje bez rada. Kao i svaka tehnika, ona je prikladnija za neke probleme nego za druge i može se implementirati loše ili dobro.
- Gruba sila je posebno dobra za postizanje stabilan produktivnost.
- Učinkovito korištenje grube sile zahtijeva optimiziranje koda i primjenu dovoljnih resursa u pravo vrijeme. Prikladan je ako su vaši poslužitelji pod velikim ne-korisničkim opterećenjem i korisničke operacije ostaju prioritet.
- Performanse ovise o dizajnu cijelog sustava, a ne samo o algoritmu unutarnje petlje.
(Ovaj članak opisuje traženje podataka u memoriji. U većini slučajeva, kada korisnik izvrši pretraživanje dnevnika, Scalyr poslužitelji su to već spremili u predmemoriju. Sljedeći članak raspravljat će o traženju nepredmemoriranih zapisa. Primjenjuju se isti principi: učinkovit kod, gruba sila s velikim računalnim resursima).
Metoda grube sile
Tradicionalno se veliki skup podataka pretražuje pomoću indeksa ključnih riječi. Kada se primijeni na zapisnike poslužitelja, to znači traženje svake jedinstvene riječi u zapisniku. Za svaku riječ morate napraviti popis svih uključenja. To olakšava pronalaženje svih poruka s ovom riječi, na primjer 'greška', 'firefox' ili "transakcija_16851951" - samo pogledajte u indeksu.
Koristio sam ovaj pristup u Googleu i dobro je funkcionirao. Ali u Scalyr-u pretražujemo zapisnike bajt po bajt.
Zašto? S apstraktne algoritamske točke gledišta, indeksi ključnih riječi puno su učinkovitiji od grubih pretraživanja. Međutim, mi ne prodajemo algoritme, mi prodajemo performanse. A performanse se ne odnose samo na algoritme, već i na inženjering sustava. Moramo uzeti u obzir sve: količinu podataka, vrstu pretraživanja, dostupni hardverski i softverski kontekst. Odlučili smo da je za naš određeni problem nešto poput 'grep' prikladnije od indeksa.
Indeksi su izvrsni, 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", puno je teže. Pretraživanje izraza kao što je 'neuhvaćena iznimka' zahtijeva glomazniji indeks koji bilježi ne samo sve poruke s tom riječi, već i određenu lokaciju riječi.
Prava poteškoća dolazi kada ne tražite riječi. Recimo da želite vidjeti koliko prometa dolazi od botova. Prva pomisao je pretražiti zapise 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 nijedan post s riječju 'Googlebot'. Ako provjerite svaku riječ u indeksu i zatim skenirate indeks u potrazi za pronađenim ključnim riječima, pretraživanje će se znatno usporiti. Kao rezultat toga, neki programi zapisnika ne dopuštaju pretraživanje po dijelovima riječi ili (u najboljem slučaju) dopuštaju posebnu sintaksu s nižom izvedbom. Ovo želimo izbjeći.
Drugi problem je interpunkcija. Želite li pronaći sve zahtjeve od 50.168.29.7? Što je s zapisnicima za otklanjanje pogrešaka koji sadrže [error]? Indeksi obično preskaču interpunkcijske znakove.
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š prikladan za to.
Osim toga, indeksi kompleks. Svaku poruku potrebno je dodati na nekoliko popisa ključnih riječi. Ove popise treba uvijek čuvati u lako pretraživom formatu. Upiti s izrazima, fragmentima riječi ili regularnim izrazima moraju se prevesti u operacije s više popisa, a rezultati skenirati i kombinirati kako bi se proizveo skup rezultata. U kontekstu velike usluge s više korisnika, ova složenost stvara probleme s izvedbom koji nisu vidljivi prilikom analize algoritama.
Indeksi ključnih riječi također zauzimaju puno prostora, a pohranjivanje je veliki trošak u sustavu upravljanja zapisima.
S druge strane, svaka pretraga može potrošiti puno računalne snage. Naši korisnici cijene brza pretraživanja za jedinstvene upite, ali takvi se upiti postavljaju relativno rijetko. Za tipične upite za pretraživanje, na primjer, za nadzornu 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 odjednom. Ali to ne znači da naši poslužitelji nisu zauzeti: oni su zauzeti poslom primanja, analiziranja i sažimanja novih poruka, evaluacije upozorenja, sažimanja starih podataka i tako dalje. Dakle, imamo prilično značajnu ponudu procesora koji se mogu koristiti za izvršavanje upita.
Gruba sila radi ako imate grub problem (i puno sile)
Brute force najbolje radi na jednostavnim problemima s malim unutarnjim petljama. Često možete optimizirati unutarnju petlju za rad pri vrlo velikim brzinama. Ako je kod složen, puno ga je teže optimizirati.
Naš kôd za pretraživanje izvorno je imao prilično veliku unutarnju petlju. Poruke pohranjujemo na stranice u 4K; svaka stranica sadrži neke poruke (u UTF-8) i metapodatke za svaku poruku. Metapodaci su struktura koja kodira duljinu vrijednosti, interni ID poruke i druga polja. Ciklus pretraživanja je izgledao ovako:
Ovo je pojednostavljena verzija stvarnog koda. Ali čak i ovdje vidljivi su višestruki smještaji objekata, kopije podataka i pozivi funkcija. JVM je prilično dobar u optimiziranju poziva funkcija i dodjeljivanju prolaznih objekata, tako da je ovaj kod radio bolje nego što smo zaslužili. Tijekom testiranja kupci su ga prilično uspješno koristili. Ali na kraju smo to podigli na višu razinu.
(Možda ćete pitati zašto pohranjujemo poruke u ovom formatu s 4K stranicama, tekstom i metapodacima, umjesto da izravno radimo s zapisima. Mnogo je razloga, koji se svode na činjenicu da je interno Scalyr motor više poput distribuirane baze podataka nego datotečni sustav. Pretraživanje teksta često se kombinira s filtrima u stilu DBMS-a na marginama nakon parsiranja dnevnika. Možemo istovremeno pretraživati više tisuća dnevnika odjednom, a jednostavne tekstualne datoteke nisu prikladne za naše transakcijsko, replicirano, distribuirano upravljanje podacima).
U početku se činilo da takav kod nije baš prikladan za brute force optimizaciju. "Pravi posao" u String.indexOf() nije čak ni dominirao CPU profilom. Odnosno, sama optimizacija ove metode ne bi donijela značajan učinak.
Događa se da metapodatke spremamo na početak svake stranice, a tekst svih poruka u UTF-8 pakiramo na drugom kraju. Iskoristivši ovo, prepravili smo petlju da pretraži cijelu stranicu odjednom:
Ova verzija radi izravno na prikazu raw byte[] i pretražuje sve poruke odjednom na cijeloj 4K stranici.
Ovo je puno lakše optimizirati za metodu grube sile. Interna petlja pretraživanja poziva se istovremeno za cijelu 4K stranicu, a ne zasebno za svaku objavu. Nema kopiranja podataka, nema dodjele objekata. A složenije operacije metapodataka pozivaju se samo kada je rezultat pozitivan, a ne na svakoj poruci. Na ovaj smo način eliminirali gomilu dodatnih troškova, a ostatak tereta koncentriran je u maloj unutarnjoj petlji pretraživanja, koja je vrlo prikladna za daljnju optimizaciju.
Naš stvarni algoritam pretraživanja temelji se na . Sličan je Boyer-Moore algoritmu, preskače približno duljinu niza za pretraživanje u svakom koraku. Glavna razlika je u tome što provjerava dva bajta istovremeno kako bi se smanjila lažna podudaranja.
Naša implementacija zahtijeva izradu tablice pretraživanja od 64K za svako pretraživanje, ali to je ništa u usporedbi s gigabajtima podataka koje pretražujemo. Unutarnja petlja obrađuje nekoliko gigabajta u sekundi na jednoj jezgri. U praksi, stabilne performanse su oko 1,25 GB po sekundi na svakoj jezgri, a ima prostora za poboljšanje. Moguće je eliminirati neke dodatne troškove izvan unutarnje petlje, a planiramo eksperimentirati s unutarnjom petljom u C-u umjesto Jave.
Koristimo silu
Raspravljali smo o tome da se pretraživanje dnevnika može implementirati "ugrubo", ali koliko "moći" imamo? Podosta.
1 jadro: Kada se pravilno koristi, jedna jezgra modernog procesora prilično je moćna sama po sebi.
8 jezgri: Trenutno radimo na Amazon hi1.4xlarge i i2.4xlarge SSD poslužiteljima, svaki s 8 jezgri (16 niti). Kao što je gore spomenuto, te su jezgre obično zauzete pozadinskim operacijama. Kada korisnik izvrši pretragu, pozadinske operacije se obustavljaju, oslobađajući svih 8 jezgri za pretragu. Pretraživanje obično završi u djeliću sekunde, nakon čega se rad u pozadini nastavlja (program za prigušivanje osigurava da niz upita za pretraživanje ne ometa važan rad u pozadini).
16 jezgri: radi pouzdanosti, organiziramo poslužitelje u grupe master/slave. Svaki master ima jedan SSD i jedan EBS server pod svojim zapovjedništvom. Ako se glavni poslužitelj sruši, SSD poslužitelj odmah zauzima njegovo mjesto. Gotovo cijelo vrijeme master i slave rade dobro, tako da je svaki blok podataka pretraživ na dva različita poslužitelja (podređeni EBS poslužitelj ima slab procesor, pa ga ne uzimamo u obzir). Podijelimo zadatak između njih, tako da imamo ukupno 16 jezgri na raspolaganju.
Mnogo jezgri: U bliskoj budućnosti ćemo distribuirati podatke po serverima na takav način da svi sudjeluju u obradi svakog netrivijalnog zahtjeva. Svaka jezgra će raditi. [Bilješka: implementirali smo plan i povećali brzinu pretraživanja na 1 TB/s, vidi bilješku na kraju članka].
Jednostavnost osigurava pouzdanost
Još jedna prednost metode brute force je njezina prilično dosljedna izvedba. Tipično, pretraživanje nije jako osjetljivo na detalje problema i skupa podataka (valjda se zato zove "grubo").
Indeks ključnih riječi ponekad daje nevjerojatno brze rezultate, a ponekad ne. Recimo da imate 50 GB zapisa u kojima se izraz 'customer_5987235982' pojavljuje točno tri puta. Pretraživanje ovog pojma broji tri lokacije izravno iz indeksa i završit će trenutno. Ali složena pretraživanja sa zamjenskim znakovima mogu skenirati tisuće ključnih riječi i potrajati dugo.
S druge strane, gruba pretraživanja izvode se manje-više istom brzinom za bilo koji upit. Pretraživanje dugih riječi je bolje, ali čak je i pretraživanje jednog znaka prilično brzo.
Jednostavnost metode grube sile znači da je njezina izvedba blizu teoretskog maksimuma. Postoji manje opcija za neočekivana preopterećenja diska, sukob zaključavanja, jurnjava pokazivača i tisuće drugih razloga za neuspjeh. Upravo sam pogledao zahtjeve koje su prošli tjedan uputili korisnici Scalira na našem najprometnijem poslužitelju. Bilo je 14 zahtjeva. Za točno osam njih trebalo je više od jedne sekunde; 000% dovršeno unutar 99 milisekundi (ako niste koristili alate za analizu dnevnika, vjerujte mi: brzo je).
Stabilna, pouzdana izvedba važna je za jednostavno korištenje usluge. Ako povremeno kasni, korisnici će ga smatrati nepouzdanim i oklijevati ga koristiti.
Pretraga dnevnika u akciji
Evo kratke animacije koja prikazuje Scalyr pretragu na djelu. Imamo demo račun na koji uvozimo svaki događaj u svakom javnom Github repozitoriju. U ovoj demonstraciji ispitujem podatke za tjedan dana: otprilike 600 MB neobrađenih zapisa.
Video je snimljen uživo, bez posebne pripreme, na mom desktopu (oko 5000 kilometara od servera). Izvedba koju ćete vidjeti uvelike je rezultat , kao i brz i pouzdan backend. Kad god postoji pauza bez indikatora 'učitavanja', ja pauziram kako biste mogli pročitati što ću pritisnuti.
U zaključku
Kada se obrađuju velike količine podataka, važno je odabrati dobar algoritam, ali "dobar" ne znači "fancy". Razmislite o tome kako će vaš kod funkcionirati u praksi. Teorijska analiza algoritama izostavlja neke čimbenike koji mogu biti od velike važnosti u stvarnom svijetu. Jednostavnije algoritme lakše je optimizirati i stabilniji su u rubnim situacijama.
Također razmislite o kontekstu u kojem će se kôd izvršiti. U našem slučaju, potrebni su nam dovoljno snažni poslužitelji za upravljanje pozadinskim zadacima. Korisnici relativno rijetko pokreću pretraživanja, tako da možemo posuditi cijelu grupu poslužitelja za kratko vrijeme potrebno za dovršenje svake pretrage.
Koristeći metodu grube sile, implementirali smo brzo, pouzdano, fleksibilno pretraživanje niza zapisa. Nadamo se da će ove ideje biti korisne za vaše projekte.
Uredi: Naslov i tekst promijenjeni su iz "Pretraga pri 20 GB u sekundi" u "Pretraga u 1 TB u sekundi" kako bi se odrazilo povećanje performansi u posljednjih nekoliko godina. Ovo povećanje brzine prvenstveno je posljedica promjena u vrsti i broju EC2 poslužitelja koje danas postavljamo kako bismo opsluživali našu povećanu bazu korisnika. Uskoro dolaze promjene koje će pružiti još jedan dramatičan poticaj u operativnoj učinkovitosti i jedva čekamo da ih podijelimo.
Izvor: www.habr.com