TL;DR: Acum patru ani am părăsit Google cu o idee pentru un nou instrument de monitorizare a serverului. Ideea a fost de a combina funcții de obicei izolate într-un singur serviciu și analiza jurnalelor, colectarea de valori, și tablouri de bord. Unul dintre principii este că serviciul trebuie să fie cu adevărat rapid, oferind devoților o experiență ușoară, interactivă și plăcută. Acest lucru necesită procesarea seturi de date de mai mulți gigaocteți în fracțiuni de secundă, respectând bugetul. Instrumentele existente de gestionare a jurnalelor sunt adesea lente și neplăcute, așa că ne-am confruntat cu o provocare bună: proiectarea inteligentă a unui instrument pentru a oferi utilizatorilor o nouă experiență.
Acest articol descrie modul în care noi cei de la Scalyr am rezolvat această problemă prin aplicarea metodelor de școală veche, o abordare cu forță brută, eliminând straturi inutile și evitând structurile complexe de date. Puteți aplica aceste lecții propriilor probleme de inginerie.
Puterea de la vechea școală
Analiza jurnalului începe de obicei cu o căutare: găsiți toate mesajele care corespund unui anumit model. În Scalyr, acestea sunt zeci sau sute de gigaocteți de jurnale de la multe servere. Abordările moderne, de regulă, implică construirea unei structuri complexe de date optimizate pentru căutare. Cu siguranță am văzut asta pe Google, unde sunt destul de buni la astfel de lucruri. Dar ne-am hotărât pe o abordare mult mai crudă: scanarea liniară a jurnalelor. Și a funcționat - oferim o interfață de căutare care este mult mai rapidă decât concurenții noștri (vezi animația de la sfârșit).
Perspectiva cheie a fost că procesoarele moderne sunt într-adevăr foarte rapide la operațiuni simple și directe. Acest lucru este ușor de ratat în sistemele complexe, cu mai multe straturi, care se bazează pe viteza I/O și operațiunile de rețea, iar astfel de sisteme sunt foarte comune în prezent. Așa că am dezvoltat un design care minimizează straturile și excesul de resturi. Cu mai multe procesoare și servere în paralel, viteza de căutare ajunge la 1 TB pe secundă.
Principalele concluzii din acest articol:
- Căutarea cu forță brută este o abordare viabilă pentru rezolvarea problemelor la scară largă din lumea reală.
- Forța brută este o tehnică de proiectare, nu o soluție fără muncă. Ca orice tehnică, este mai potrivită unor probleme decât altora și poate fi implementată prost sau bine.
- Forța brută este deosebit de bună pentru realizarea grajd performanţă.
- Utilizarea eficientă a forței brute necesită optimizarea codului și aplicarea resurselor suficiente la momentul potrivit. Este potrivit dacă serverele dvs. sunt supuse unei sarcini grele de non-utilizatori și operațiunile utilizatorului rămân o prioritate.
- Performanța depinde de proiectarea întregului sistem, nu doar de algoritmul buclei interioare.
(Acest articol descrie căutarea datelor în memorie. În cele mai multe cazuri, atunci când un utilizator efectuează o căutare în jurnal, serverele Scalyr au stocat-o deja în cache. Următorul articol va discuta despre căutarea jurnalelor necachete. Se aplică aceleași principii: cod eficient, forță brută cu resurse de calcul mari).
Metoda forței brute
În mod tradițional, un set mare de date este căutat folosind un index de cuvinte cheie. Când se aplică jurnalelor de server, aceasta înseamnă căutarea fiecărui cuvânt unic din jurnal. Pentru fiecare cuvânt, trebuie să faceți o listă cu toate incluziunile. Acest lucru facilitează găsirea tuturor mesajelor cu acest cuvânt, de exemplu „eroare”, „firefox” sau „transaction_16851951” - trebuie doar să căutați în index.
Am folosit această abordare la Google și a funcționat bine. Dar în Scalyr căutăm jurnalele octet cu octet.
De ce? Din punct de vedere algoritmic abstract, indexurile de cuvinte cheie sunt mult mai eficiente decât căutările cu forță brută. Cu toate acestea, nu vindem algoritmi, vindem performanță. Iar performanța nu este doar despre algoritmi, ci și despre ingineria sistemelor. Trebuie să luăm în considerare totul: volumul de date, tipul de căutare, contextul hardware și software disponibil. Am decis că pentru problema noastră particulară, ceva de genul „grep” era mai potrivit decât un index.
Indicii sunt grozavi, dar au limitări. Un cuvânt este ușor de găsit. Dar căutarea mesajelor cu mai multe cuvinte, cum ar fi „googlebot” și „404”, este mult mai dificilă. Căutarea unei expresii precum „excepție neprinsă” necesită un index mai greoi care înregistrează nu numai toate mesajele cu acel cuvânt, ci și locația specifică a cuvântului.
Adevărata dificultate vine atunci când nu cauți cuvinte. Să presupunem că doriți să vedeți cât trafic vine de la roboți. Primul gând este să căutați în jurnale cuvântul „bot”. Așa vei găsi niște roboți: Googlebot, Bingbot și mulți alții. Dar aici „bot” nu este un cuvânt, ci o parte din el. Dacă căutăm „bot” în index, nu vom găsi nicio postare cu cuvântul „Googlebot”. Dacă verificați fiecare cuvânt din index și apoi scanați indexul pentru cuvintele cheie găsite, căutarea va încetini foarte mult. Ca urmare, unele programe de jurnal nu permit căutări de cuvinte parțiale sau (în cel mai bun caz) permit o sintaxă specială cu performanțe mai scăzute. Vrem să evităm acest lucru.
O altă problemă este punctuația. Doriți să găsiți toate solicitările de la 50.168.29.7? Ce zici de jurnalele de depanare care conțin [error]? Indicele omit de obicei semnele de punctuație.
În cele din urmă, inginerii iubesc instrumentele puternice și, uneori, o problemă poate fi rezolvată doar cu o expresie obișnuită. Indexul de cuvinte cheie nu este foarte potrivit pentru asta.
În plus, indicii complex. Fiecare mesaj trebuie adăugat la mai multe liste de cuvinte cheie. Aceste liste trebuie păstrate într-un format ușor de căutat în orice moment. Interogările cu fraze, fragmente de cuvinte sau expresii regulate trebuie traduse în operații cu mai multe liste, iar rezultatele scanate și combinate pentru a produce un set de rezultate. În contextul unui serviciu pe scară largă, cu mai mulți locatari, această complexitate creează probleme de performanță care nu sunt vizibile atunci când se analizează algoritmii.
Indicii de cuvinte cheie ocupă, de asemenea, mult spațiu, iar stocarea este un cost major într-un sistem de gestionare a jurnalelor.
Pe de altă parte, fiecare căutare poate consuma multă putere de calcul. Utilizatorii noștri apreciază căutările de mare viteză pentru interogări unice, dar astfel de interogări sunt făcute relativ rar. Pentru interogări de căutare tipice, de exemplu, pentru un tablou de bord, folosim tehnici speciale (le vom descrie în articolul următor). Alte solicitări sunt suficient de rare încât rareori trebuie să procesați mai multe deodată. Dar asta nu înseamnă că serverele noastre nu sunt ocupate: sunt ocupate cu munca de primire, analiză și comprimare a mesajelor noi, evaluarea alertelor, comprimarea datelor vechi și așa mai departe. Astfel, avem o sursă destul de semnificativă de procesoare care pot fi folosite pentru a executa interogări.
Forța brută funcționează dacă aveți o problemă brută (și multă forță)
Forța brută funcționează cel mai bine în problemele simple cu bucle interne mici. Adesea puteți optimiza bucla internă pentru a rula la viteze foarte mari. Dacă codul este complex, este mult mai dificil de optimizat.
Codul nostru de căutare avea inițial o buclă interioară destul de mare. Stocam mesajele pe pagini la 4K; fiecare pagină conține câteva mesaje (în UTF-8) și metadate pentru fiecare mesaj. Metadatele este o structură care codifică lungimea valorii, ID-ul mesajului intern și alte câmpuri. Ciclul de căutare a arătat astfel:
Aceasta este o versiune simplificată a codului real. Dar chiar și aici, sunt vizibile mai multe plasări de obiecte, copii de date și apeluri de funcții. JVM-ul este destul de bun la optimizarea apelurilor de funcții și la alocarea de obiecte efemere, așa că acest cod a funcționat mai bine decât am meritat. În timpul testării, clienții l-au folosit cu succes. Dar până la urmă am trecut la următorul nivel.
(V-ați putea întreba de ce stocăm mesajele în acest format cu pagini 4K, text și metadate, în loc să lucrăm direct cu jurnalele. Există multe motive, care se rezumă la faptul că, în interior, motorul Scalyr este mai mult ca o bază de date distribuită decât cu o bază de date distribuită. sistem de fișiere. Căutarea text este adesea combinată cu filtre în stil DBMS în margini după analizarea jurnalelor. Putem căuta simultan multe mii de jurnale deodată, iar fișierele text simple nu sunt potrivite pentru gestionarea datelor noastre tranzacționale, replicate și distribuite).
Inițial, părea că un astfel de cod nu era foarte potrivit pentru optimizarea forței brute. „Munca adevărată” în String.indexOf() nici măcar nu a dominat profilul CPU. Adică, optimizarea acestei metode singură nu ar aduce un efect semnificativ.
Se întâmplă că stocăm metadate la începutul fiecărei pagini, iar textul tuturor mesajelor din UTF-8 este împachetat la celălalt capăt. Profitând de acest lucru, am rescris bucla pentru a căuta simultan întreaga pagină:
Această versiune funcționează direct pe vizualizare raw byte[] și caută toate mesajele simultan pe întreaga pagină 4K.
Acest lucru este mult mai ușor de optimizat pentru metoda forței brute. Bucla internă de căutare este apelată simultan pentru întreaga pagină 4K, mai degrabă decât separat pe fiecare postare. Nu există copiere a datelor, nici alocare de obiecte. Și operațiunile de metadate mai complexe sunt apelate numai atunci când rezultatul este pozitiv și nu pe fiecare mesaj. În acest fel, am eliminat o tonă de supraîncărcare, iar restul încărcăturii este concentrată într-o buclă de căutare internă mică, care este potrivită pentru optimizarea ulterioară.
Algoritmul nostru real de căutare se bazează pe . Este similar cu algoritmul Boyer-Moore, sărind aproximativ lungimea șirului de căutare la fiecare pas. Principala diferență este că verifică doi octeți la un moment dat pentru a minimiza potrivirile false.
Implementarea noastră necesită crearea unui tabel de căutare de 64K pentru fiecare căutare, dar asta nu este nimic în comparație cu gigaocteții de date prin care căutăm. Bucla interioară procesează câțiva gigaocteți pe secundă pe un singur nucleu. În practică, performanța stabilă este de aproximativ 1,25 GB pe secundă pe fiecare nucleu și există loc de îmbunătățire. Este posibil să eliminăm o parte din supraîncărcarea din afara buclei interioare și intenționăm să experimentăm cu o buclă interioară în C în loc de Java.
Folosim forta
Am discutat că căutarea în jurnal poate fi implementată „aproximativ”, dar câtă „putere” avem? Destul de mult.
1 miez: Când este utilizat corect, un singur nucleu al unui procesor modern este destul de puternic în sine.
8 miezuri: În prezent rulăm pe servere SSD Amazon hi1.4xlarge și i2.4xlarge, fiecare cu 8 nuclee (16 fire). După cum am menționat mai sus, aceste nuclee sunt de obicei ocupate cu operațiuni de fundal. Când utilizatorul efectuează o căutare, operațiunile de fundal sunt suspendate, eliberând toate cele 8 nuclee pentru căutare. Căutarea se finalizează de obicei într-o fracțiune de secundă, după care se reia activitatea de fundal (programul de limitare asigură că barajul de interogări de căutare nu interferează cu munca de fundal importantă).
16 miezuri: pentru fiabilitate, organizăm serverele în grupuri master/slave. Fiecare master are un SSD și un server EBS sub comanda lui. Dacă serverul principal se blochează, serverul SSD îi ia imediat locul. Aproape tot timpul, master și slave funcționează bine, astfel încât fiecare bloc de date poate fi căutat pe două servere diferite (serverul slave EBS are un procesor slab, așa că nu îl luăm în considerare). Împărțim sarcina între ei, astfel încât să avem un total de 16 nuclee disponibile.
Multe miezuri: În viitorul apropiat, vom distribui datele pe servere în așa fel încât toți să participe la procesarea fiecărei cereri non-triviale. Fiecare nucleu va funcționa. [Notă: am implementat planul și am crescut viteza de căutare la 1 TB/s, vezi nota de la sfârșitul articolului].
Simplitatea asigură fiabilitatea
Un alt avantaj al metodei forței brute este performanța sa destul de consistentă. În mod obișnuit, căutarea nu este foarte sensibilă la detaliile problemei și setul de date (presupun că de aceea se numește „agreat”).
Indexul de cuvinte cheie produce uneori rezultate incredibil de rapide, iar alteori nu. Să presupunem că aveți 50 GB de jurnale în care termenul „client_5987235982” apare de exact trei ori. O căutare pentru acest termen numără trei locații direct din index și se va finaliza instantaneu. Dar căutările complexe cu caractere metalice pot scana mii de cuvinte cheie și pot dura mult timp.
Pe de altă parte, căutările cu forță brută funcționează mai mult sau mai puțin cu aceeași viteză pentru orice interogare. Căutarea cuvintelor lungi este mai bună, dar chiar și căutarea unui singur caracter este destul de rapidă.
Simplitatea metodei forței brute înseamnă că performanța sa este aproape de maximul său teoretic. Există mai puține opțiuni pentru supraîncărcarea neașteptată a discului, disputa de blocare, urmărirea indicatorului și mii de alte motive pentru eșec. Tocmai m-am uitat la solicitările făcute de utilizatorii Scalyr săptămâna trecută pe cel mai aglomerat server al nostru. Au fost 14 de cereri. Exact opt dintre ei au durat mai mult de o secundă; 000% finalizat în 99 milisecunde (dacă nu ați folosit instrumente de analiză a jurnalelor, credeți-mă: E rapid).
Performanța stabilă și fiabilă este importantă pentru ușurința în utilizare a serviciului. Dacă întârzie periodic, utilizatorii îl vor percepe ca fiind nesigur și vor fi reticenți în a-l folosi.
Căutarea în jurnal în acțiune
Iată o scurtă animație care arată căutarea Scalyr în acțiune. Avem un cont demonstrativ în care importăm fiecare eveniment din fiecare depozit public Github. În această demonstrație, examinez datele pentru o săptămână: aproximativ 600 MB de jurnale brute.
Videoclipul a fost înregistrat live, fără pregătire specială, pe desktopul meu (la vreo 5000 de kilometri de server). Performanța pe care o veți vedea se datorează în mare parte , precum și un backend rapid și de încredere. Ori de câte ori există o pauză fără un indicator de „încărcare”, eu fac pauză, astfel încât să puteți citi ceea ce sunt pe cale să apăs.
în concluzie
Când procesați cantități mari de date, este important să alegeți un algoritm bun, dar „bun” nu înseamnă „fantezist”. Gândiți-vă la modul în care va funcționa codul dvs. în practică. Analiza teoretică a algoritmilor omite câțiva factori care pot fi de mare importanță în lumea reală. Algoritmii mai simpli sunt mai ușor de optimizat și mai stabili în situații marginale.
Gândiți-vă și la contextul în care va fi executat codul. În cazul nostru, avem nevoie de servere suficient de puternice pentru a gestiona sarcinile de fundal. Utilizatorii inițiază căutări relativ rar, astfel încât putem împrumuta un întreg grup de servere pentru perioada scurtă necesară pentru a finaliza fiecare căutare.
Folosind o metodă de forță brută, am implementat o căutare rapidă, fiabilă și flexibilă într-un set de jurnale. Sperăm că aceste idei sunt utile pentru proiectele dumneavoastră.
Editați | ×: Titlul și textul s-au schimbat de la „Căutare la 20 GB pe secundă” la „Căutare la 1 TB pe secundă” pentru a reflecta creșterile de performanță din ultimii ani. Această creștere a vitezei se datorează în primul rând modificărilor tipului și numărului de servere EC2 pe care le instalăm astăzi pentru a servi baza noastră de clienți sporită. În curând urmează modificări care vor oferi un alt impuls dramatic al eficienței operaționale și abia așteptăm să le împărtășim.
Sursa: www.habr.com