TL;DR: Quattro anni fa ho lasciato Google con l'idea di un nuovo strumento di monitoraggio dei server. L'idea era quella di combinare funzioni solitamente isolate in un unico servizio e analisi dei log, raccolta di metriche, e dashboard. Uno dei principi è che il servizio deve essere veritiero veloce, fornendo ai devops un'esperienza facile, interattiva e divertente. Ciò richiede l'elaborazione di set di dati multi-gigabyte in frazioni di secondo rispettando il budget. Gli strumenti di gestione dei log esistenti sono spesso lenti e goffi, quindi ci siamo trovati di fronte a una bella sfida: progettare in modo intelligente uno strumento per offrire agli utenti una nuova esperienza.
Questo articolo descrive come noi di Scalyr abbiamo risolto questo problema applicando metodi della vecchia scuola, un approccio di forza bruta, eliminando livelli non necessari ed evitando strutture dati complesse. Puoi applicare queste lezioni ai tuoi problemi di ingegneria.
Potere della vecchia scuola
L'analisi del registro di solito inizia con una ricerca: trova tutti i messaggi che corrispondono a un determinato modello. In Scalyr si tratta di decine o centinaia di gigabyte di log provenienti da molti server. Gli approcci moderni, di norma, implicano la costruzione di una struttura di dati complessa ottimizzata per la ricerca. L'ho sicuramente visto su Google, dove sono piuttosto bravi in questo genere di cose. Ma abbiamo optato per un approccio molto più rozzo: la scansione lineare dei log. E ha funzionato: forniamo un'interfaccia ricercabile che è molto più veloce dei nostri concorrenti (vedi l'animazione alla fine).
L’intuizione chiave è stata che i processori moderni sono davvero molto veloci nelle operazioni semplici e dirette. È facile non notare questo aspetto nei sistemi complessi e multistrato che fanno affidamento sulla velocità di I/O e sulle operazioni di rete e tali sistemi sono molto comuni oggi. Quindi abbiamo sviluppato un design che riduce al minimo gli strati e i detriti in eccesso. Con più processori e server in parallelo, la velocità di ricerca raggiunge 1 TB al secondo.
Punti chiave di questo articolo:
- La ricerca con forza bruta è un approccio praticabile per risolvere problemi reali su larga scala.
- La forza bruta è una tecnica di progettazione, non una soluzione priva di lavoro. Come ogni tecnica, è più adatta ad alcuni problemi rispetto ad altri e può essere implementata bene o male.
- La forza bruta è particolarmente utile per ottenere risultati stabile produttività.
- L'uso efficace della forza bruta richiede l'ottimizzazione del codice e l'applicazione di risorse sufficienti al momento giusto. È adatto se i tuoi server sono sottoposti a un carico pesante da parte di non utenti e le operazioni degli utenti rimangono una priorità.
- Le prestazioni dipendono dalla progettazione dell'intero sistema, non solo dall'algoritmo del ciclo interno.
(Questo articolo descrive la ricerca dei dati in memoria. Nella maggior parte dei casi, quando un utente esegue una ricerca nei log, i server Scalyr li hanno già memorizzati nella cache. Il prossimo articolo discuterà della ricerca di log non memorizzati nella cache. Si applicano gli stessi principi: codice efficiente, forza bruta con grandi risorse computazionali).
Metodo della forza bruta
Tradizionalmente, la ricerca in un set di dati di grandi dimensioni viene eseguita utilizzando un indice di parole chiave. Quando applicato ai log del server, questo significa cercare ogni parola univoca nel log. Per ogni parola è necessario creare un elenco di tutte le inclusioni. Ciò semplifica la ricerca di tutti i messaggi con questa parola, ad esempio "errore", "firefox" o "transaction_16851951": basta guardare nell'indice.
Ho utilizzato questo approccio in Google e ha funzionato bene. Ma in Scalyr cerchiamo i log byte per byte.
Perché? Da un punto di vista algoritmico astratto, gli indici di parole chiave sono molto più efficienti delle ricerche di forza bruta. Tuttavia, non vendiamo algoritmi, vendiamo prestazioni. E le prestazioni non riguardano solo gli algoritmi, ma anche l’ingegneria dei sistemi. Dobbiamo considerare tutto: volume di dati, tipologia di ricerca, contesto hardware e software disponibile. Abbiamo deciso che per il nostro problema particolare qualcosa come "grep" era più adatto di un indice.
Gli indici sono ottimi, ma hanno dei limiti. Una parola è facile da trovare. Ma cercare messaggi con più parole, come "googlebot" e "404", è molto più difficile. La ricerca di una frase come "eccezione non rilevata" richiede un indice più complicato che registri non solo tutti i messaggi con quella parola, ma anche la posizione specifica della parola.
La vera difficoltà arriva quando non cerchi le parole. Supponiamo che tu voglia vedere quanto traffico proviene dai bot. Il primo pensiero è cercare nei log la parola "bot". Ecco come troverai alcuni bot: Googlebot, Bingbot e molti altri. Ma qui "bot" non è una parola, ma una parte di essa. Se cerchiamo "bot" nell'indice, non troveremo nessun post con la parola "Googlebot". Se controlli ogni parola nell'indice e poi esegui la scansione dell'indice per le parole chiave trovate, la ricerca rallenterà notevolmente. Di conseguenza, alcuni programmi di registro non consentono la ricerca di parti di parole o (nella migliore delle ipotesi) consentono una sintassi speciale con prestazioni inferiori. Vogliamo evitare questo.
Un altro problema è la punteggiatura. Vuoi trovare tutte le richieste da 50.168.29.7? Che dire del debug dei log contenenti [error]? Gli abbonati di solito saltano la punteggiatura.
Infine, gli ingegneri amano gli strumenti potenti e talvolta un problema può essere risolto solo con un'espressione regolare. L'indice delle parole chiave non è molto adatto a questo.
Inoltre, gli indici complesso. Ogni messaggio deve essere aggiunto a diversi elenchi di parole chiave. Questi elenchi dovrebbero essere mantenuti in un formato facilmente consultabile in ogni momento. Le query con frasi, frammenti di parole o espressioni regolari devono essere tradotte in operazioni multi-elenco e i risultati scansionati e combinati per produrre un set di risultati. Nel contesto di un servizio multi-tenant su larga scala, questa complessità crea problemi di prestazioni che non sono visibili quando si analizzano gli algoritmi.
Anche gli indici delle parole chiave occupano molto spazio e l'archiviazione rappresenta un costo importante in un sistema di gestione dei log.
D'altra parte, ogni ricerca può consumare molta potenza di calcolo. I nostri utenti apprezzano le ricerche ad alta velocità per query uniche, ma tali query vengono effettuate relativamente raramente. Per le query di ricerca tipiche, ad esempio per una dashboard, utilizziamo tecniche speciali (le descriveremo nel prossimo articolo). Altre richieste sono abbastanza rare da dover raramente elaborarne più di una alla volta. Ma questo non significa che i nostri server non siano occupati: sono impegnati nel lavoro di ricezione, analisi e compressione di nuovi messaggi, valutazione degli avvisi, compressione di vecchi dati e così via. Pertanto, disponiamo di una fornitura abbastanza significativa di processori che possono essere utilizzati per eseguire query.
La forza bruta funziona se hai un problema bruto (e molta forza)
La forza bruta funziona meglio su problemi semplici con piccoli circuiti interni. Spesso è possibile ottimizzare il circuito interno affinché funzioni a velocità molto elevate. Se il codice è complesso, è molto più difficile ottimizzarlo.
Il nostro codice di ricerca originariamente aveva un ciclo interno abbastanza grande. Archiviamo i messaggi su pagine a 4K; ogni pagina contiene alcuni messaggi (in UTF-8) e metadati per ciascun messaggio. I metadati sono una struttura che codifica la lunghezza del valore, l'ID del messaggio interno e altri campi. Il ciclo di ricerca era simile al seguente:
Questa è una versione semplificata del codice vero e proprio. Ma anche qui sono visibili più posizionamenti di oggetti, copie di dati e chiamate di funzioni. La JVM è abbastanza brava nell'ottimizzare le chiamate di funzioni e nell'allocare oggetti effimeri, quindi questo codice ha funzionato meglio di quanto meritassimo. Durante i test, i clienti lo hanno utilizzato con successo. Ma alla fine siamo passati al livello successivo.
(Potresti chiederti perché archiviamo i messaggi in questo formato con pagine da 4K, testo e metadati, invece di lavorare direttamente con i log. Ci sono molte ragioni, che si riducono al fatto che internamente il motore Scalyr è più simile a un database distribuito che a un file system. La ricerca di testo è spesso combinata con filtri in stile DBMS ai margini dopo l'analisi dei log. Possiamo cercare simultaneamente molte migliaia di log contemporaneamente e i semplici file di testo non sono adatti alla nostra gestione dei dati transazionali, replicati e distribuiti).
Inizialmente sembrava che tale codice non fosse molto adatto all'ottimizzazione della forza bruta. "Lavoro vero" in String.indexOf() non ha nemmeno dominato il profilo della CPU. Cioè, l’ottimizzazione di questo metodo da sola non porterebbe un effetto significativo.
Accade così che memorizziamo i metadati all'inizio di ogni pagina e che il testo di tutti i messaggi in UTF-8 sia compresso all'altra estremità. Approfittando di ciò, abbiamo riscritto il ciclo per cercare nell'intera pagina contemporaneamente:
Questa versione funziona direttamente sulla vista raw byte[] e cerca tutti i messaggi contemporaneamente nell'intera pagina 4K.
Questo è molto più semplice da ottimizzare per il metodo della forza bruta. Il ciclo di ricerca interno viene chiamato simultaneamente per l'intera pagina 4K, anziché separatamente per ciascun post. Non è prevista la copia dei dati, né l'allocazione degli oggetti. E le operazioni sui metadati più complesse vengono chiamate solo quando il risultato è positivo e non su ogni messaggio. In questo modo abbiamo eliminato un sacco di spese generali e il resto del carico è concentrato in un piccolo ciclo di ricerca interno, che ben si adatta a un'ulteriore ottimizzazione.
Il nostro attuale algoritmo di ricerca si basa su . È simile all'algoritmo Boyer-Moore, salta approssimativamente la lunghezza della stringa di ricerca ad ogni passaggio. La differenza principale è che controlla due byte alla volta per ridurre al minimo le false corrispondenze.
La nostra implementazione richiede la creazione di una tabella di ricerca da 64 KB per ogni ricerca, ma non è niente in confronto ai gigabyte di dati in cui cerchiamo. Il ciclo interno elabora diversi gigabyte al secondo su un singolo core. In pratica, le prestazioni stabili sono di circa 1,25 GB al secondo su ciascun core, e c'è spazio per miglioramenti. È possibile eliminare parte del sovraccarico al di fuori del ciclo interno e prevediamo di sperimentare un ciclo interno in C anziché in Java.
Usiamo la forza
Abbiamo discusso del fatto che la ricerca nei log può essere implementata "approssimativamente", ma quanta "potenza" abbiamo? Parecchio.
1 anni: Se utilizzato correttamente, un singolo core di un processore moderno è piuttosto potente di per sé.
8 core: Attualmente utilizziamo server SSD Amazon hi1.4xlarge e i2.4xlarge, ciascuno con 8 core (16 thread). Come accennato in precedenza, questi core sono solitamente impegnati in operazioni in background. Quando l'utente esegue una ricerca, le operazioni in background vengono sospese, liberando tutti gli 8 core per la ricerca. La ricerca di solito viene completata in una frazione di secondo, dopodiché riprende il lavoro in background (il programma di limitazione garantisce che la raffica di query di ricerca non interferisca con importanti lavori in background).
16 core: per affidabilità, organizziamo i server in gruppi master/slave. Ogni master ha un SSD e un server EBS sotto il suo comando. Se il server principale si blocca, il server SSD prende immediatamente il suo posto. Quasi sempre, master e slave funzionano bene, quindi ogni blocco di dati è ricercabile su due server diversi (il server slave EBS ha un processore debole, quindi non lo consideriamo). Dividiamo il compito tra loro, in modo da avere a disposizione un totale di 16 core.
Molti nuclei: Nel prossimo futuro distribuiremo i dati tra i server in modo tale che tutti partecipino all'elaborazione di ogni richiesta non banale. Ogni core funzionerà. [Nota: abbiamo implementato il piano e aumentato la velocità di ricerca a 1 TB/s, vedi nota a fine articolo].
La semplicità garantisce affidabilità
Un altro vantaggio del metodo della forza bruta è la sua prestazione abbastanza costante. In genere, la ricerca non è molto sensibile ai dettagli del problema e al set di dati (immagino sia per questo che viene chiamata "grossolana").
L'indice delle parole chiave a volte produce risultati incredibilmente rapidi, altre volte no. Supponiamo che tu abbia 50 GB di log in cui il termine "cliente_5987235982" appare esattamente tre volte. Una ricerca per questo termine conta tre posizioni direttamente dall'indice e verrà completata immediatamente. Ma le ricerche complesse con caratteri jolly possono scansionare migliaia di parole chiave e richiedere molto tempo.
D'altra parte, le ricerche di forza bruta vengono eseguite più o meno alla stessa velocità per qualsiasi query. La ricerca di parole lunghe è migliore, ma anche la ricerca di un singolo carattere è abbastanza veloce.
La semplicità del metodo della forza bruta fa sì che le sue prestazioni siano vicine al massimo teorico. Sono disponibili meno opzioni per sovraccarichi imprevisti del disco, conflitti di blocco, caccia al puntatore e migliaia di altri motivi di errore. Ho appena esaminato le richieste avanzate dagli utenti Scalyr la settimana scorsa sul nostro server più trafficato. Le richieste sono state 14. Esattamente otto di essi hanno impiegato più di un secondo; Completato al 000% entro 99 millisecondi (se non hai utilizzato strumenti di analisi dei log, fidati di me: è veloce).
Prestazioni stabili e affidabili sono importanti per la facilità d'uso del servizio. Se rallenta periodicamente, gli utenti lo percepiranno come inaffidabile e saranno riluttanti a usarlo.
Ricerca dei registri in azione
Ecco una breve animazione che mostra la ricerca di Scalyr in azione. Abbiamo un account demo in cui importiamo ogni evento in ogni repository Github pubblico. In questa demo esamino i dati di una settimana: circa 600 MB di log non elaborati.
Il video è stato registrato in diretta, senza particolare preparazione, sul mio desktop (a circa 5000 chilometri dal server). Le prestazioni che vedrai sono in gran parte dovute a , nonché un backend veloce e affidabile. Ogni volta che c'è una pausa senza un indicatore di "caricamento", sono io che faccio una pausa in modo che tu possa leggere ciò che sto per premere.
insomma
Quando si elaborano grandi quantità di dati, è importante scegliere un buon algoritmo, ma “buono” non significa “stravagante”. Pensa a come funzionerà il tuo codice nella pratica. L’analisi teorica degli algoritmi tralascia alcuni fattori che possono essere di grande importanza nel mondo reale. Gli algoritmi più semplici sono più facili da ottimizzare e più stabili in situazioni limite.
Pensa anche al contesto in cui verrà eseguito il codice. Nel nostro caso, abbiamo bisogno di server sufficientemente potenti per gestire le attività in background. Gli utenti avviano le ricerche relativamente di rado, quindi possiamo prendere in prestito un intero gruppo di server per il breve periodo necessario a completare ogni ricerca.
Utilizzando un metodo di forza bruta, abbiamo implementato una ricerca veloce, affidabile e flessibile in una serie di registri. Speriamo che queste idee siano utili per i vostri progetti.
Tipo: Il titolo e il testo sono cambiati da "Ricerca a 20 GB al secondo" a "Ricerca a 1 TB al secondo" per riflettere l'aumento delle prestazioni negli ultimi anni. Questo aumento di velocità è dovuto principalmente ai cambiamenti nel tipo e nel numero di server EC2 che stiamo installando oggi per servire la nostra crescente base di clienti. Sono in arrivo cambiamenti che forniranno un ulteriore notevole incremento dell'efficienza operativa e non vediamo l'ora di condividerli.
Fonte: habr.com