TL; DR: Quattru anni fà, aghju lasciatu Google cù una idea per un novu strumentu di monitoraghju di u servitore. L'idea era di cumminà funzioni generalmente isolate in un serviziu è analisi di log, raccolta di metriche, è dashboards. Unu di i principii hè chì u serviziu deve esse veramente prestu, chì furnisce i devops cun una sperienza faciule, interattiva è piacevule. Questu richiede l'elaborazione di seti di dati multi-gigabyte in frazioni di secondu mentre stà in u budget. L'arnesi di gestione di log esistenti sò spessu lenti è goffi, cusì ci eramu affruntatu una bona sfida: cuncepimentu intelligente di un strumentu per dà l'utilizatori una nova sperienza.
Questu articulu descrive cumu noi in Scalyr risolve stu prublema applicà i metudi di a scola antica, un approcciu di forza bruta, eliminendu strati inutili è evitendu strutture di dati cumplessi. Pudete applicà queste lezioni à i vostri prublemi di ingegneria.
Old School Power
L'analisi di u logu principia di solitu cù una ricerca: truvate tutti i missaghji chì currispondenu à un certu mudellu. In Scalyr, questi sò decine o centinaie di gigabytes di logs da parechji servitori. L'avvicinamenti muderni, in regula, implicanu a custruzzione di una struttura di dati cumplessa ottimizzata per a ricerca. Aghju certamente vistu questu nantu à Google, induve sò abbastanza bè in stu tipu di cose. Ma avemu stabilitu un approcciu assai più crudu: scanning lineare di logs. È hà travagliatu - furnimu una interfaccia di ricerca chì hè ordini di grandezza più veloce di i nostri cuncurrenti (vede l'animazione à a fine).
L'intruduzione chjave era chì i prucessori muderni sò veramente assai veloci in operazioni simplici è dirette. Questu hè faciule da mancà in sistemi cumplessi, multi-layer chì si basanu in a velocità di I / O è l'operazioni di rete, è tali sistemi sò assai cumuni oghje. Cusì avemu sviluppatu un disignu chì minimizza i strati è i detriti eccessivi. Cù parechji processori è servitori in parallelu, a velocità di ricerca righjunghji 1 TB per seconda.
Cunsiglii chjave da questu articulu:
- A ricerca di forza bruta hè un approcciu viable per risolve i prublemi di u mondu reale, à grande scala.
- A forza bruta hè una tecnica di disignu, micca una soluzione senza travagliu. Cum'è ogni tecnica, hè megliu adattatu à certi prublemi cà altri, è pò esse implementatu pocu o bè.
- A forza bruta hè soprattuttu bona per ottene stabile produttività.
- L'usu efficace di a forza bruta richiede l'ottimisazione di u codice è l'applicazione di risorse sufficienti à u mumentu propiu. Hè adattatu se i vostri servitori sò sottu una pesante carica non-utilizatori è l'operazioni di l'utilizatori restanu una priorità.
- U rendiment dipende da u disignu di tuttu u sistema, micca solu l'algoritmu di u ciclu internu.
(Stu articulu descrive a ricerca di dati in memoria. In a maiò parte di i casi, quandu un utilizatore realiza una ricerca di log, i servitori Scalyr anu digià cached it. U prossimu articulu discuterà a ricerca di logs uncached. I stessi principii s'applicanu: codice efficiente, forza bruta. cù grandi risorse computazionali).
Metudu di forza bruta
Tradizionalmente, un grande settore di dati hè cercatu cù un indice di keyword. Quandu hè appiicata à i logs di u servitore, questu significa cercà ogni parolla unica in u logu. Per ogni parolla, avete bisognu di fà una lista di tutte l'inclusioni. Questu facilita à truvà tutti i missaghji cù sta parolla, per esempiu "error", "firefox" o "transaction_16851951" - basta à circà in l'indici.
Aghju utilizatu stu approcciu in Google è hà travagliatu bè. Ma in Scalyr cerchemu i logs byte per byte.
Perchè? Da un puntu di vista algoritmicu astrattu, l'indici di keyword sò assai più efficaci cà e ricerche di forza bruta. Tuttavia, ùn vendemu micca algoritmi, vendemu performance. È u rendiment ùn hè micca solu di l'algoritmi, ma ancu di l'ingegneria di sistemi. Avemu da cunsiderà tuttu: volume di dati, tipu di ricerca, hardware dispunibule è u cuntestu di u software. Avemu decisu chì per u nostru prublema particulare, qualcosa cum'è "grep" era più adattatu cà un indice.
L'indici sò grandi, ma anu limitazioni. Una parolla hè faciule di truvà. Ma a ricerca di missaghji cù parechje parolle, cum'è "googlebot" è "404", hè assai più difficiule. A ricerca di una frasa cum'è "eccezzioni micca catturata" richiede un indice più ingombrante chì registra micca solu tutti i missaghji cù quella parola, ma ancu u locu specificu di a parolla.
A vera difficultà vene quandu ùn cercate micca parolle. Diciamu chì vulete vede quantu trafficu vene da i bots. U primu pensamentu hè di circà i logs per a parolla "bot". Eccu cumu truverete alcuni bots: Googlebot, Bingbot è assai altri. Ma quì "bot" ùn hè micca una parolla, ma una parte di questu. Se cerchemu "bot" in l'indici, ùn truvemu micca posti cù a parolla "Googlebot". Se verificate ogni parolla in l'indici è poi scansà l'indici per e parolle chjave truvate, a ricerca rallenta assai. In u risultatu, certi prugrammi di logu ùn permettenu micca e ricerche in parte di parole o (in u megliu) permettenu sintassi speciale cù un rendimentu più bassu. Vulemu evitari questu.
Un altru prublema hè a puntuazione. Vulete truvà tutte e dumande da 50.168.29.7? Chì ci hè di debugging logs chì cuntenenu [error]? L'abbonamenti generalmente saltanu a puntuazione.
Infine, l'ingegneri amanu strumenti putenti, è qualchì volta un prublema pò esse solu solu cù una espressione regulare. L'indici di keyword ùn hè micca assai adattatu per questu.
Inoltre, l'indici cumplessu. Ogni missaghju deve esse aghjuntu à parechji listi di keyword. Queste listi deve esse guardatu in un furmatu facilmente cercabile in ogni mumentu. E dumande cù frasi, frammenti di parolle, o espressioni rigulari devenu esse tradutte in operazioni multi-liste, è i risultati scannati è cumminati per pruduce un set di risultati. In u cuntestu di un serviziu à grande scala, multi-tenant, sta cumplessità crea prublemi di rendiment chì ùn sò micca visibili quandu analizà l'algoritmi.
L'indici di keyword occupanu ancu assai spaziu, è u almacenamentu hè un costu maiò in un sistema di gestione di log.
Per d 'altra banda, ogni ricerca pò cunsumà assai putenza di computing. I nostri utilizatori apprezzanu e ricerche à alta velocità per e dumande uniche, ma tali dumande sò fatte relativamente raramente. Per e dumande di ricerca tipiche, per esempiu, per un dashboard, usemu tecniche speciali (avemu descritti in u prossimu articulu). L'altri dumande sò abbastanza raru chì raramente avete da processà più di una à una volta. Ma questu ùn significa micca chì i nostri servitori ùn sò micca occupati: sò occupati cù u travagliu di riceve, analizà è cumpressione novi messagi, valutà alerti, cumpressione di dati vechji, etc. Cusì, avemu un fornimentu abbastanza significativu di processori chì ponu esse aduprati per eseguisce dumande.
A forza bruta funziona sè avete un prublema brute (è assai forza)
A forza bruta funziona megliu nantu à prublemi simplici cù picculi cicli interni. Spessu pudete ottimisà u ciclu internu per corre à velocità assai elevate. Se u codice hè cumplessu, hè assai più difficiule di ottimisimu.
U nostru codice di ricerca hà inizialmente un ciclu internu abbastanza grande. Guardemu i missaghji nantu à e pagine à 4K; ogni pagina cuntene qualchi messagi (in UTF-8) è metadata per ogni messagiu. Metadata hè una struttura chì codifica a durata di u valore, l'ID di missaghju internu è altri campi. U ciculu di ricerca pareva cusì:
Questa hè una versione simplificata di u codice propiu. Ma ancu quì, parechje piazzamenti d'ughjettu, copie di dati è chjama di funzione sò visibili. A JVM hè abbastanza bona per ottimisà e chjama di funzioni è allocate l'uggetti effimeri, cusì stu codice hà travagliatu megliu di ciò chì ci meritavamu. Durante a prova, i clienti anu utilizatu abbastanza bè. Ma à a fine l'avemu purtatu à u prossimu livellu.
(Pudete dumandà perchè avemu guardatu i missaghji in stu formatu cù pagine 4K, testu è metadati, invece di travaglià cù logs direttamente. Ci sò parechje ragioni, chì sboccanu à u fattu chì internamente u mutore Scalyr hè più cum'è una basa di dati distribuita chè un sistema di schedari. A ricerca di testu hè spessu cumminata cù filtri in stile DBMS in i marghjini dopu l'analisi di log. Pudemu simultaneamente cercà parechji millaie di logs à una volta, è i schedarii di testu simplici ùn sò micca adattati per a nostra gestione di dati transazionale, replicati è distribuiti).
In principiu, pareva chì tali codice ùn era micca assai adattatu per l'optimizazione di forza bruta. "Travagliu veru" in String.indexOf() ùn hà mancu duminatu u prufilu CPU. Questu hè, l'ottimisazione di stu metudu solu ùn porta micca un effettu significativu.
Succede chì avemu guardatu metadata à u principiu di ogni pagina, è u testu di tutti i missaghji in UTF-8 hè imballatu à l'altru finale. Approfittendu di questu, avemu riscritto u ciclu per circà tutta a pagina in una volta:
Sta versione travaglia direttamente nantu à a vista raw byte[] è cerca tutti i missaghji in una volta in tutta a pagina 4K.
Questu hè assai più faciule d'ottimisà per u metudu di forza bruta. U ciclu di ricerca internu hè chjamatu simultaneamente per tutta a pagina 4K, piuttostu cà separatamente in ogni postu. Ùn ci hè micca copia di dati, nè allocazione di oggetti. E operazioni di metadati più cumplessi sò chjamati solu quandu u risultatu hè pusitivu, è micca nantu à ogni missaghju. In questu modu, avemu eliminatu una tonna di sopra, è u restu di a carica hè cuncentrata in un picculu ciclu di ricerca internu, chì hè adattatu per più ottimisazione.
U nostru algoritmu di ricerca attuale hè basatu annantu . Hè simile à l'algoritmu Boyer-Moore, saltendu apprussimatamente a lunghezza di a stringa di ricerca à ogni passu. A diferenza principale hè chì cuntrolla dui byte à u tempu per minimizzà i falsi partiti.
A nostra implementazione richiede a creazione di una tabella di ricerca di 64K per ogni ricerca, ma ùn hè nunda in paragunà à i gigabyte di dati chì avemu cercatu. U ciclu internu processa parechji gigabyte per seconda nantu à un core unicu. In pratica, u rendiment stabile hè di circa 1,25 GB per seconda in ogni core, è ci hè spaziu per migliurà. Hè pussibule eliminà una parte di l'overhead fora di u ciclu internu, è avemu pensatu à sperimentà un ciclu internu in C invece di Java.
Avemu aduprà a forza
Avemu discututu chì a ricerca di log pò esse implementata "approssimativamente", ma quantu "putere" avemu? Assai assai.
1 core: Quandu s'utilice currettamente, un core unicu di un processore mudernu hè abbastanza putente in u so propiu dirittu.
8 core: Avemu attualmente in esecuzione nantu à i servitori SSD Amazon hi1.4xlarge è i2.4xlarge, ognunu cù 8 core (16 fili). Cumu l'esitatu sopra, sti nuclei sò generalmente occupati cù operazioni di fondo. Quandu l'utilizatore esegue una ricerca, l'operazioni di fondo sò sospese, liberendu tutti i 8 core per a ricerca. A ricerca di solitu compie in una frazione di secunna, dopu chì u travagliu di fondo ripiglià (u prugramma di throttling assicura chì a barrage di e dumande di ricerca ùn interferiscenu micca cù u travagliu di fondo impurtante).
16 core: per affidabilità, urganizemu i servitori in gruppi master/slave. Ogni maestru hà un SSD è un servitore EBS sottu u so cumandamentu. Se u servitore principalu crash, u servitore SSD piglia immediatamente u so postu. Quasi tuttu u tempu, maestru è schiavu travaglianu bè, perchè ogni bloccu di dati hè cercatu nantu à dui servitori diffirenti (u servitore slave EBS hà un processatore debule, cusì ùn avemu micca cunsideratu). Dividemu u compitu trà elli, in modu chì avemu un totale di 16 core disponibile.
Parechji core: In un futuru vicinu, sparghjemu dati à traversu i servitori in tale manera chì tutti participanu à u processu di ogni dumanda micca triviale. Ogni core hà da travaglià. [Nota: avemu implementatu u pianu è hà aumentatu a veloce di ricerca à 1 TB / s, vede a nota à a fine di l'articulu].
A simplicità assicura affidabilità
Un altru vantaghju di u metudu di forza bruta hè a so prestazione abbastanza consistente. Di genere, a ricerca ùn hè micca assai sensibile à i dettagli di u prublema è a data set (supponu chì hè per quessa chì hè chjamatu "grossu").
L'indici di parole chjave qualchì volta pruduce risultati incredibbilmente veloci, è altre volte ùn hè micca. Diciamu chì avete 50 GB di logs in quale u terminu "customer_5987235982" appare esattamente trè volte. Una ricerca per stu termu cunta trè lochi direttamente da l'indici è compie istantaneamente. Ma e ricerche cumplessu di wildcard ponu scansà migliaia di parole chjave è piglianu assai tempu.
Per d 'altra banda, e ricerche di forza bruta facenu più o menu a stessa velocità per ogni dumanda. A ricerca di parolle longu hè megliu, ma ancu a ricerca di un caratteru unicu hè abbastanza veloce.
A simplicità di u metudu di forza bruta significa chì a so prestazione hè vicinu à u so massimu teoricu. Ci hè menu opzioni per i sovraccarichi di discu inaspettati, a disputa di serratura, a caccia di puntatori, è millaie d'altri motivi di fallimentu. Aghju vistu solu e richieste fatte da l'utilizatori di Scalyr a settimana passata nantu à u nostru servitore più occupatu. Ci era 14 000 dumande. Esattamente ottu di elli hà pigliatu più di una seconda; 99% cumpletu in 111 millisecondi (se ùn avete micca utilizatu strumenti di analisi di log, fiducia in mè: hè prestu).
A prestazione stabile è affidabile hè impurtante per a facilità di usu di u serviziu. S'ellu si ritarda periodicamente, l'utilizatori a perciveranu cum'è inaffidabile è esse riluttanti à aduprà.
Ricerca di log in azione
Eccu una breve animazione chì mostra a ricerca di Scalyr in azione. Avemu un contu demo induve impurtamu ogni avvenimentu in ogni repositoriu publicu Github. In questa demo, esaminà u valore di una settimana di dati: circa 600 MB di logs crudi.
U video hè statu arregistratu in diretta, senza preparazione speciale, nantu à u mo scrittore (circa 5000 chilometri da u servitore). U rendiment chì vedete hè largamente dovutu , è ancu un backend veloce è affidabile. Ogni volta chì ci hè una pausa senza un indicatore di 'caricamentu', sò mè in pausa per pudè leghje ciò chì aghju da appughjà.
In cunclusioni
Quandu si tratta di grande quantità di dati, hè impurtante di sceglie un bonu algoritmu, ma "bonu" ùn significa micca "fantasia". Pensate à cumu u vostru codice hà da travaglià in pratica. L'analisi teorica di l'algoritmi lascia fora certi fatturi chì ponu esse di grande impurtanza in u mondu reale. L'algoritmi più simplici sò più faciuli d'ottimisà è più stabili in situazioni di punta.
Pensate ancu à u cuntestu in quale u codice serà eseguitu. In u nostru casu, avemu bisognu di servitori abbastanza putenti per gestisce e attività di fondo. L'utilizatori inizianu e ricerche relativamente raramenti, cusì pudemu piglià in prestito un gruppu sanu di servitori per u cortu periodu necessariu per compie ogni ricerca.
Utilizendu un metudu di forza bruta, avemu implementatu una ricerca rapida, affidabile è flessibile in un settore di logs. Speremu chì queste idee sò utili per i vostri prughjetti.
Edit: U tìtulu è u testu sò cambiati da "Ricerca à 20 GB per seconda" à "Ricerca à 1 TB per seconda" per riflette l'aumentu di rendiment in l'ultimi anni. Stu aumentu di a velocità hè principalmente dovutu à i cambiamenti in u tipu è u numeru di servitori EC2 chì mettemu oghje per serve a nostra basa di clienti aumentata. Ci sò cambiamenti chì venenu prestu chì furnisceranu un altru impulsu drammaticu in l'efficienza operativa, è ùn pudemu aspittà di sparte.
Source: www.habr.com