TL;DR: Quattro anni fa ho lasciato Google con l'idea di uno strumento nuovo per il monitoraggio dei server. L'idea era di unire in un unico servizio funzioni solitamente isolate e analisi dei log, raccolta di metriche, e dashboard. Uno dei principi è che il servizio deve essere davvero veloce, offrendo ai devops un lavoro semplice, interattivo e piacevole. Questo richiede la gestione di set di dati da diversi gigabyte in frazioni di secondo, senza superare il budget. Gli strumenti esistenti per gestire i log sono spesso lenti e ingombranti, quindi abbiamo affrontato una bella sfida: progettare uno strumento in modo da offrire agli utenti nuove esperienze di lavoro.
In questo articolo descriviamo come noi di Scalyr abbiamo risolto questo problema applicando metodi della vecchia scuola, un approccio di forza bruta, eliminando strati superflui e evitando strutture dati complesse. Queste lezioni possono essere applicate ai tuoi problemi ingegneristici.
La forza della vecchia scuola
L'analisi dei log in genere inizia con la ricerca: trovare tutti i messaggi corrispondenti a un certo modello. In Scalyr questo significa decine o centinaia di gigabyte di log provenienti da molti server. Gli approcci moderni tendono a prevedere la costruzione di una certa struttura dati complessa, ottimizzata per la ricerca. Certamente ho visto qualcosa del genere in Google, dove sono piuttosto bravi in queste cose. Ma noi abbiamo optato per un approccio molto più semplice: la scansione lineare dei log. E ha funzionato: garantiamo un'interfaccia con una ricerca di ordini di grandezza più rapida rispetto ai concorrenti (vedi l'animazione alla fine).
La chiave è che i processori moderni sono davvero molto veloci in operazioni semplici e dirette. Questo è facile da trascurare in sistemi complessi e multilivello, che dipendono dalla velocità di I/O e dalle operazioni di rete, e tali sistemi sono molto comuni oggigiorno. Pertanto, abbiamo sviluppato un design che minimizza il numero di strati e di spazzatura superflua. Con più processori e server in parallelo, la velocità di ricerca raggiunge 1 TB al secondo.
Le principali conclusioni di questo articolo:
- La ricerca di tipo brute-force è un approccio praticabile per risolvere problemi reali e su larga scala.
- La forza bruta è una tecnica di progettazione, non un modo per liberarsi dal lavoro. Come ogni tecnica, è più adatta a determinati problemi piuttosto che ad altri e può essere implementata in modo efficace o inefficace.
- La forza bruta è particolarmente efficace per raggiungere una prestazione .
- Un utilizzo efficace della forza bruta richiede l'ottimizzazione del codice e l'applicazione tempestiva di risorse adeguate. Essa è adatta se i tuoi server sono sotto carico pesante, non legato agli utenti, mentre le operazioni degli utenti rimangono una priorità.
- La prestazione dipende dal design dell'intero sistema, e non solo dall'algoritmo del ciclo interno.
(In questo articolo si descrive la ricerca di 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. Nel prossimo articolo parleremo della ricerca nei log non memorizzati nella cache. Si applicano gli stessi principi: codice efficiente, metodo della forza bruta con grandi risorse computazionali).
Metodo della forza bruta
Tradizionalmente, la ricerca in un grande set di dati si svolge tramite l'indice delle parole chiave. Per i log del server, ciò significa cercare ogni parola unica nel registro. Per ogni parola, è necessario compilare un elenco di tutte le occorrenze. Questo consente di trovare facilmente tutti i messaggi contenenti quella parola, ad esempio 'errore', 'firefox' o 'transaction_16851951' - basta consultare l'indice.
Ho utilizzato questo approccio in Google, e ha funzionato bene. Ma in Scalyr cerchiamo nei log byte per byte.
Perché? Da un punto di vista algoritmico astratto, gli indici delle parole chiave sono molto più efficienti della ricerca bruta. Tuttavia, noi non vendiamo algoritmi, vendiamo prestazioni. E la prestazione non riguarda solo gli algoritmi, ma anche l'ingegneria sistemica. Dobbiamo considerare tutto: l'ammontare dei dati, il tipo di ricerca, l'hardware disponibile e il contesto software. Abbiamo deciso che, per il nostro problema specifico, un'opzione come 'grep' è più adatta rispetto all'indice.
Gli indici sono ottimi, ma hanno delle limitazioni. Trovare una parola è facile. Ma cercare messaggi con più parole, come 'googlebot' e '404', è già molto più complesso. Trovare una frase come 'eccezione non catturata' richiede un indice più ingombrante, che registra non solo tutti i messaggi con quella parola, ma anche la posizione specifica della parola.
La vera difficoltà sorge quando cerchi non parole. Supponiamo che tu voglia vedere quanto traffico arriva dai bot. La prima idea è cercare nei log con la parola 'bot'. Così troverai alcuni bot: Googlebot, Bingbot e molti altri. Ma qui 'bot' non è una parola, ma parte di essa. Se cerchiamo 'bot' nell'indice, non troveremo messaggi con la parola 'Googlebot'. Se controlliamo ogni parola nell'indice e poi scandagliamo l'indice per le parole chiave trovate, la ricerca rallenterà notevolmente. Di conseguenza, alcuni programmi per la gestione dei log non consentono la ricerca per porzioni di parola o (nel migliore dei casi) consentono di usare una sintassi speciale con prestazioni inferiori. Vogliamo evitare questo.
Un altro problema è la punteggiatura. Vuoi trovare tutte le query da 50.168.29.7? Что насчёт отладки логов, содержащих [error]? Индексы обычно пропускают пунктуацию.
Infine, gli ingegneri amano gli strumenti potenti, e a volte il problema può essere risolto solo con un'espressione regolare. L'indice delle parole chiave non è molto adatto a questo.
Inoltre, gli indici sono complessi. Ogni messaggio deve essere aggiunto a più elenchi di parole chiave. Questi elenchi devono essere mantenuti costantemente in un formato facilmente ricercabile. Le query con frasi, frammenti di parole o espressioni regolari devono essere tradotte in operazioni con più elenchi, e i risultati devono essere scansionati e combinati per ottenere un insieme risultante. Nel contesto di un servizio multi-utente su larga scala, tale complessità crea problemi di prestazioni che non sono evidenti nell'analisi degli algoritmi.
Gli indici delle parole chiave occupano anche molto spazio, e lo storage è la principale voce di spesa nei sistemi di gestione dei log.
D'altra parte, ogni ricerca può richiedere molta potenza computazionale. I nostri utenti apprezzano ricerche ad alta velocità su query uniche, ma tali query vengono effettuate relativamente raramente. Per le query di ricerca tipiche, ad esempio per il pannello di monitoraggio, utilizziamo tecniche speciali (le descriveremo nel prossimo articolo). Altre query sono piuttosto rare, quindi raramente dobbiamo elaborarne più di una alla volta. Ma questo non significa che i nostri server non siano occupati: sono impegnati a ricevere, analizzare e comprimere nuovi messaggi, valutare le notifiche, comprimere dati obsoleti e così via. Pertanto, abbiamo un notevole surplus di processori che possono essere utilizzati per elaborare le richieste.
La forza bruta funziona se hai un problema semplice (e molta forza).
La forza bruta funziona meglio su compiti semplici con piccoli cicli interni. Spesso puoi ottimizzare il ciclo interno per funzionare a velocità molto elevate. Se il codice è complesso, è molto più difficile ottimizzarlo.
Inizialmente, il nostro codice di ricerca aveva un ciclo interno piuttosto grande. Memorizziamo i messaggi in pagine da 4K; ogni pagina contiene alcuni messaggi (in UTF-8) e metadati per ciascun messaggio. I metadati sono una struttura in cui sono codificate la lunghezza del valore, l'ID interno del messaggio e altri campi. Il ciclo di ricerca era strutturato in questo modo:
Questa è una versione semplificata rispetto al codice reale. Ma anche qui si notano diverse allocazioni di oggetti, copie di dati e chiamate di funzione. La JVM ottimizza piuttosto bene le chiamate a funzione e gestisce gli oggetti effimeri, quindi questo codice funzionava meglio di quanto meritassimo. Durante i test, i clienti lo utilizzavano con successo. Ma alla fine abbiamo fatto un salto di qualità.
(Puoi chiederti perché conserviamo i messaggi in questo formato con pagine da 4K, testo e metadati, e non lavoriamo direttamente con i log. Ci sono molte ragioni che si riducono al fatto che internamente il motore Scalyr assomiglia di più a un database distribuito che a un file system. La ricerca testuale è spesso combinata con filtri in stile DBMS sui campi dopo il parsing dei log. Possiamo cercare contemporaneamente tra migliaia di log, e file di testo semplici non sono adatti per la nostra gestione dei dati transazionale, replicata e distribuita).
Inizialmente sembrava che questo codice non fosse molto adatto per l'ottimizzazione tramite il metodo di forza bruta. "Il vero lavoro" in String.indexOf() non dominava nemmeno nel profilo della CPU. Cioè, l'ottimizzazione solo di questo metodo non avrebbe portato a effetti significativi.
È successo che conserviamo i metadati all'inizio di ogni pagina, mentre il testo di tutti i messaggi è impacchettato in UTF-8 all'altra estremità. Approfittando di questo, abbiamo riscritto il ciclo per cercare contemporaneamente nell'intera pagina:
Questa versione funziona direttamente sulla rappresentazione raw byte[] ed esegue la ricerca di tutti i messaggi contemporaneamente su tutta la pagina 4K.
È molto più facile ottimizzare per il metodo di forza bruta. Il ciclo di ricerca interno viene chiamato simultaneamente per l'intera pagina 4K, e non separatamente per ciascun messaggio. Non ci sono né copie di dati né allocazioni di oggetti. E operazioni più complesse sui metadati vengono chiamate solo in caso di esito positivo, e non per ogni messaggio. In questo modo, abbiamo eliminato un sacco di overhead, e il carico rimanente è concentrato in un piccolo ciclo di ricerca interno, che si presta bene a ulteriori ottimizzazioni.
Il nostro algoritmo di ricerca effettivo si basa su . Assomiglia all'algoritmo di Boyer-Moore, con uno skip di circa la lunghezza della stringa di ricerca a ogni passo. La principale differenza è che controlla due byte alla volta, per minimizzare i falsi positivi.
La nostra implementazione richiede la creazione di una tabella di ricerca di 64K per ogni ricerca, ma è poca cosa rispetto ai gigabyte di dati nei quali cerchiamo. Il ciclo interno elabora diversi gigabyte al secondo su un core. Nella pratica, la performance stabile è di circa 1,25 GB al secondo per ogni core, e c'è potenziale di miglioramento. Alcuni sovraccarichi al di fuori del ciclo interno possono essere eliminati, e abbiamo in programma di sperimentare con il ciclo interno in C invece che in Java.
Applichiamo la potenza
Abbiamo discusso che la ricerca nei log può essere realizzata "brutalmente", ma quanta "potenza" abbiamo? Non poco.
1 core: se usato correttamente, un core di un processore moderno è piuttosto potente di per sé.
8 core: attualmente stiamo lavorando su server Amazon hi1.4xlarge e i2.4xlarge SSD, ognuno con 8 core (16 thread). Come accennato, di solito questi core sono occupati in operazioni di sfondo. Quando un utente esegue una ricerca, le operazioni di sfondo vengono sospese, liberando tutti i 8 core per la ricerca. La ricerca di solito si completa in una frazione di secondo, dopodiché il lavoro di sfondo riprende (un programma-regolatore garantisce che un'ondata di richieste di ricerca non interferisca con il lavoro di sfondo importante).
16 core: per affidabilità, organizziamo i server in gruppi master/slave. Ogni master ha sotto di sé un server SSD e uno EBS. Se il server principale cade, il server SSD prende immediatamente il suo posto. Quasi sempre il master e lo slave funzionano normalmente, quindi ogni blocco di dati è disponibile per la ricerca su due server diversi (il server slave EBS ha un processore debole, quindi non lo consideriamo). Dividiamo il compito tra di loro, così abbiamo a disposizione un totale di 16 core.
Molti core: nel prossimo futuro distribuirà i dati tra i server in modo che tutti partecipino all'elaborazione di ogni richiesta non triviale. Ogni core sarà in funzione. [Nota: abbiamo realizzato un piano e aumentato la velocità di ricerca a 1 TB/s, vedere nota alla fine dell'articolo.].
La semplicità garantisce l'affidabilità
Un ulteriore vantaggio del metodo brute force è la performance piuttosto stabile. In generale, la ricerca non è molto sensibile ai dettagli del compito e del set di dati (penso che sia per questo che lo chiamano "brutale").
L'indice delle parole chiave talvolta restituisce risultati incredibilmente rapidi, mentre altre volte no. Supponiamo che tu abbia 50 GB di log, in cui il termine 'customer_5987235982' appare esattamente tre volte. La ricerca per questo termine calcola direttamente dall'indice tre posizioni e si conclude immediatamente. Ma una ricerca complessa con caratteri jolly può esaminare migliaia di parole chiave e richiedere molto tempo.
D'altro canto, la ricerca a forza bruta per qualsiasi query viene eseguita a una velocità più o meno uniforme. La ricerca di parole lunghe è migliore, ma anche la ricerca di un solo carattere avviene piuttosto rapidamente.
La semplicità del metodo a forza bruta significa che la sua prestazione è vicina al massimo teorico. Qui ci sono meno possibilità di sovraccarico imprevisto dei dischi, conflitti di blocco, inseguitore di puntatore e mille altre cause di malfunzionamenti. Ho appena esaminato le richieste effettuate dagli utenti di Scalyr la settimana scorsa sul nostro server più carico. Ci sono state 14.000 richieste. Esattamente otto di esse hanno impiegato più di un secondo; il 99% è stato completato entro 111 millisecondi (se non hai utilizzato strumenti di analisi dei log, credimi: è veloce).
Un'esperienza stabile e affidabile è importante per l'usabilità del servizio. Se si blocca occasionalmente, gli utenti lo percepiranno come inaffidabile e saranno riluttanti a utilizzarlo.
Ricerca nei log in azione
Ecco una piccola animazione che mostra Scalyr in azione. Abbiamo un account demo, dove importiamo ogni evento in ogni repository pubblico di Github. In questa dimostrazione, esamino i dati di una settimana: circa 600 MB di log grezzi.
Il video è stato registrato in diretta, senza preparazione speciale, sul mio desktop (circa 5000 chilometri dal server). La prestazione che vedrai è in gran parte dovuta , così come a un backend veloce e affidabile. Ogni volta che c'è una pausa senza indicatore 'loading', è perché mi fermo per darti il tempo di leggere ciò che sto per fare.
In conclusione
Quando si trattano grandi volumi di dati, è fondamentale scegliere un buon algoritmo, ma "buono" non significa "complicato". Pensate a come il vostro codice funzionerà nella pratica. Nell'analisi teorica degli algoritmi mancano alcuni fattori che possono avere un grande impatto nel mondo reale. Algoritmi più semplici sono più facili da ottimizzare e sono più stabili in situazioni critiche.
Considerate anche il contesto in cui verrà eseguito il codice. Nel nostro caso sono necessari server abbastanza potenti per gestire i compiti in background. Gli utenti avviano le ricerche relativamente raramente, quindi possiamo noleggiare un intero gruppo di server per il breve periodo necessario a svolgere ogni ricerca.
Con un approccio di forza bruta abbiamo implementato una ricerca veloce, affidabile e flessibile su un insieme di log. Speriamo che queste idee siano utili per i vostri progetti.
Modifica: il titolo e il testo sono stati aggiornati da "Ricerca a una velocità di 20 GB al secondo" a "Ricerca a una velocità di 1 TB al secondo", per riflettere l'aumento delle prestazioni negli ultimi anni. Questo incremento di velocità è principalmente dovuto al cambiamento del tipo e della quantità di server EC2 che oggi stiamo utilizzando per servire una clientela in crescita. Presto ci saranno cambiamenti che garantiranno un altro drastico miglioramento dell'efficienza, e non vediamo l'ora di poterlo annunciare.
Fonte: habr.com
