TL;DR: Quattro anni fa ho lasciato Google con l'idea di uno strumento innovativo per il monitoraggio dei server. L'idea era quella di combinare in un unico servizio funzioni normalmente isolate e analisi dei log, raccolta di metriche, e dashboard. Uno dei principi è che il servizio deve essere realmente veloce, offrendo ai devops un'esperienza di lavoro facile, interattiva e piacevole. Questo richiede l'elaborazione di set di dati di diverse gigabyte in frazioni di secondo, senza superare il budget. Gli strumenti esistenti per la gestione dei log sono spesso lenti e ingombranti, quindi ci siamo imbattuti in una bella sfida: progettare uno strumento in modo intelligente per offrire agli utenti una nuova esperienza di lavoro.
In questo articolo descriviamo come in Scalyr abbiamo affrontato questa sfida, applicando metodi classici, un approccio di forza bruta, eliminando strati superflui e evitando strutture dati complesse. Queste lezioni possono essere applicate alle vostre stesse sfide ingegneristiche.
La forza della vecchia scuola
L'analisi dei log inizia solitamente con la ricerca: trovare tutti i messaggi che corrispondono a un certo modello. In Scalyr, si tratta di decine o centinaia di gigabyte di log provenienti da molti server. Gli approcci moderni tendono a costruire una complessa struttura dati ottimizzata per la ricerca. Certo, ho visto questo in Google, dove sono piuttosto bravi in queste cose. Ma abbiamo optato per un approccio molto più semplice: la scansione lineare dei log. E ha funzionato: offriamo un'interfaccia con una ricerca notevolmente più veloce rispetto ai concorrenti (guarda l'animazione alla fine).
La chiave della nostra intuizione è stata che i moderni processori sono veramente molto veloci nelle operazioni semplici e dirette. È facile perderlo di vista in sistemi complessi e multilivello che dipendono dalla velocità delle operazioni I/O e di rete, sistematiche oggi molto comuni. Abbiamo quindi progettato un design che minimizza il numero di strati e la spazzatura inutile. Con più processori e server in parallelo, la velocità di ricerca raggiunge 1 TB al secondo.
Principali conclusioni di questo articolo:
- La ricerca esaustiva è un approccio perfettamente valido per affrontare problemi reali e su larga scala.
- La forza bruta è una tecnica di progettazione, non è un modo per evitare il lavoro. Come ogni tecnica, è più adatta per alcuni problemi rispetto ad altri e può essere implementata in modo scadente o adeguato.
- La forza bruta è particolarmente efficace per raggiungere in fase stabile) è le prestazioni.
- Un utilizzo efficace della forza bruta richiede ottimizzazione del codice e l'applicazione tempestiva di risorse sufficienti. È indicata se i tuoi server sono sotto un carico elevato, non legato agli utenti, mentre le operazioni degli utenti rimangono una priorità.
- Le prestazioni dipendono dal design dell'intero sistema e non solo dall'algoritmo del ciclo interno.
(Questo articolo 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. Nell'articolo successivo discuteremo della ricerca nei log non memorizzati nella cache. Si applicano gli stessi principi: codice efficace, metodo di forza bruta con grandi risorse computazionali).
Metodo di forza bruta
Tradizionalmente, la ricerca in un grande insieme di dati viene effettuata tramite un indice di parole chiave. Pertinente ai log dei server, ciò significa cercare ogni parola unica nel registro. Per ogni parola è necessario creare un elenco di tutte le occorrenze. Questo permette di trovare facilmente tutti i messaggi contenenti quella parola, come ‘error’, ‘firefox’ o «transaction_16851951» — basta guardare nell'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 di parole chiave sono molto più efficienti della ricerca grezza. Tuttavia, noi non vendiamo algoritmi, vendiamo prestazioni. E le prestazioni non riguardano solo gli algoritmi, ma anche l'ingegneria di sistema. Dobbiamo considerare tutto: la quantità di 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 a un indice.
Gli indici sono utili, ma hanno delle limitazioni. Trovare una singola parola è facile. Tuttavia, la ricerca di messaggi con più parole, come 'googlebot' e '404', è molto più difficile. La ricerca di frasi come 'uncaught exception' richiede un indice più complesso, che registra non solo tutti i messaggi contenenti quella parola, ma anche la posizione specifica della parola.
La vera difficoltà si presenta quando non stai cercando parole. Supponiamo che tu voglia vedere quanti visitatori provengono dai bot. La prima idea è cercare nei log la parola 'bot'. In questo modo troverai alcuni bot: Googlebot, Bingbot e molti altri. Ma qui 'bot' non è una parola intera, ma un suo frammento. Jika cercate 'bot' nell'indice, non troverete messaggi contenenti la parola 'Googlebot'. Se controlliamo ogni parola nell'indice e poi scansioniamo l'indice per le chiavi trovate, la ricerca rallenterà notevolmente. Di conseguenza, alcuni programmi di analisi dei log non consentono la ricerca per frammenti di parole o, nella migliore delle ipotesi, consentono un uso di una sintassi speciale con prestazioni inferiori. Vogliamo evitare tutto ciò.
Un altro problema è la punteggiatura. Vuoi trovare tutte le richieste da 50.168.29.7? Что насчёт отладки логов, содержащих [error]? Индексы обычно пропускают пунктуацию.
Infine, agli ingegneri piacciono gli strumenti potenti, e a volte un problema può essere risolto solo con un'espressione regolare. L'indice delle parole chiave non è molto adatto a questo scopo.
Inoltre, gli indici sono complessi. Ogni messaggio deve essere aggiunto a più elenchi di parole chiave. È necessario mantenere questi elenchi sempre in un formato facilmente ricercabile. Le query con frasi, frammenti di parole o espressioni regolari devono essere tradotte in operazioni su più elenchi, e i risultati devono essere scansionati e uniti per ottenere l'insieme finale. Nel contesto di un servizio multiutente su larga scala, questa 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 è un costo principale nei sistemi di gestione dei log.
D'altra parte, ogni ricerca può richiedere molta potenza di calcolo. I nostri utenti apprezzano le ricerche ad alta velocità per richieste uniche, anche se tali richieste vengono effettuate relativamente raramente. Per le ricerche tipiche, come ad esempio per il pannello di monitoraggio, utilizziamo tecniche speciali (di cui parleremo nel prossimo articolo). Altre richieste sono abbastanza rare, quindi di solito non si trattano più di una alla volta. Ma questo non significa che i nostri server non siano occupati: sono impegnati nell'accettazione, analisi e compressione di nuovi messaggi, valutazione delle notifiche, compressione dei dati più vecchi e così via. Pertanto, disponiamo di una notevole riserva di processori che possono essere utilizzati per eseguire le richieste.
La forza bruta funziona se hai un problema drastico (e molta potenza).
La forza bruta funziona meglio con compiti semplici e piccoli cicli interni. Spesso puoi ottimizzare il ciclo interno per funzionare a velocità molto elevate. Se il codice è complesso, diventa molto più difficile ottimizzarlo.
Inizialmente, il nostro codice per la ricerca conteneva un ciclo interno piuttosto ampio. Conserviamo i messaggi su pagine da 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 interno del messaggio e altri campi. Il ciclo di ricerca appariva così:
Questa è una versione semplificata rispetto al codice effettivo. Ma anche qui si notano diverse allocazioni di oggetti, copie di dati e chiamate a funzioni. La JVM ottimizza piuttosto bene le chiamate a funzioni e gestisce gli oggetti effimeri, quindi questo codice ha funzionato meglio di quanto ci aspettassimo. Durante i test, i clienti lo hanno utilizzato con successo. Ma alla fine siamo passati a un nuovo livello.
(Puoi chiederti perché memorizziamo i messaggi in questo formato con pagine da 4K, testo e metadati, anziché 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 testuale è spesso combinata con filtri in stile DBMS sui campi dopo il parsing dei log. Possiamo cercare simultaneamente in migliaia di log e i semplici file di testo non si adattano alla nostra gestione dati transazionale, replicata e distribuita).
Inizialmente, sembrava che questo codice non fosse molto adatto all'ottimizzazione tramite il metodo della forza bruta. "Il vero lavoro" in String.indexOf() non dominava nemmeno nel profilo CPU. Quindi, ottimizzare solo questo metodo non avrebbe portato a un effetto significativo.
Per caso, memorizziamo i metadati all'inizio di ogni pagina e il testo di tutti i messaggi in UTF-8 è compresso all'altra estremità. Approfittando di questo, abbiamo riscritto il ciclo per cercare su tutta la pagina:
Questa versione funziona direttamente sulla rappresentazione raw byte[] e ricerca tutti i messaggi contemporaneamente su tutta la pagina 4K.
È molto più semplice ottimizzare per il metodo di forza bruta. Il ciclo di ricerca interno viene chiamato simultaneamente per l'intera pagina 4K, anziché separatamente per ciascun messaggio. Non ci sono operazioni di copia dei dati o allocazione di oggetti. Inoltre, operazioni più complesse sui metadati vengono invocate solo in caso di esito positivo, e non per ogni messaggio. In questo modo, abbiamo eliminato un sacco di overhead e il resto del carico è concentrato in un piccolo ciclo di ricerca interno, che è ben adatto per ulteriori ottimizzazioni.
Il nostro algoritmo di ricerca effettivo si basa su . È simile all'algoritmo di Boyer-Moore con uno skip approssimativo della lunghezza della stringa di ricerca ad ogni passo. La principale differenza è che verifica due byte alla volta, per minimizzare le corrispondenze false.
La nostra implementazione richiede la creazione di una tabella di ricerca da 64K per ogni ricerca, ma è poca cosa rispetto ai gigabyte di dati in cui operiamo. Il ciclo interno gestisce diversi gigabyte al secondo su un solo core. In pratica, le prestazioni stabili si aggirano attorno a 1,25 GB al secondo per core, e c'è potenziale per miglioramenti. È possibile ridurre alcune sovraccarichi al di fuori del ciclo interno, 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 implementata in modo "grezzo", ma quanta "potenza" abbiamo veramente? Non poca.
1 core: se utilizzato correttamente, un core moderno di un processore è abbastanza potente da solo.
8 core: attualmente operiamo su server Amazon hi1.4xlarge e i2.4xlarge SSD, ciascuno con 8 core (16 thread). Come accennato in precedenza, di solito questi core sono occupati da operazioni in background. Quando un utente effettua una ricerca, le operazioni in background vengono sospese, liberando tutti e 8 i core per la ricerca. La ricerca di solito si completa in un attimo, dopo di che il lavoro in background riprende (il programma di regolazione garantisce che un'ondata di richieste di ricerca non interferisca con il lavoro importante in background).
16 core: per garantire affidabilità, organizziamo i server in gruppi master/slave. Ogni master ha sotto di sé un server SSD e uno EBS. Se il server principale si guasta, il server SSD prende immediatamente il suo posto. Quasi sempre master e slave funzionano correttamente, quindi ogni blocco di dati è accessibile per la ricerca su due server diversi (il server EBS subordinato ha un processore debole, quindi non lo consideriamo). Distribuiamo il compito tra loro, in modo che abbiamo un totale di 16 core disponibili.
Molti core: nel prossimo futuro distribuirà i dati sui server in modo tale che tutti partecipino all'elaborazione di ogni richiesta non triviale. Funzionerà ogni core. [Примечание: abbiamo implementato il piano e aumentato la velocità di ricerca a 1 TB/s, vedi nota alla fine dell'articolo].
La semplicità garantisce l'affidabilità
Un ulteriore vantaggio del metodo di brute force è una prestazione piuttosto stabile. In generale, la ricerca non è troppo sensibile ai dettagli del compito e del set di dati (penso che sia per questo che si chiama ‘brute’).
L'indice delle parole chiave a volte fornisce risultati incredibilmente rapidi, mentre in altri casi no. Supponiamo di avere 50 GB di log, in cui il termine ‘customer_5987235982’ appare esattamente tre volte. La ricerca di questo termine considera direttamente dall'indice tre posizioni e si completa istantaneamente. Ma una ricerca complessa con caratteri jolly può scandagliare migliaia di parole chiave e richiedere molto tempo.
D'altra parte, la ricerca con metodo di forza bruta per qualsiasi richiesta viene eseguita a una velocità più o meno costante. La ricerca di parole lunghe è migliore, ma anche la ricerca di un singolo carattere avviene abbastanza rapidamente.
La semplicità del metodo di forza bruta significa che le sue prestazioni si avvicinano al massimo teorico. Qui ci sono meno possibilità di sovraccarico imprevisto dei dischi, conflitti per blocchi, inseguimenti di puntatori e migliaia di altre ragioni per guasti. Ho appena esaminato le richieste fatte dagli utenti di Scalyr la scorsa settimana sul nostro server più carico. Ci sono state 14.000 richieste. Solo otto di esse hanno impiegato più di un secondo; il 99% è stato eseguito in meno di 111 millisecondi (se non hai utilizzato strumenti di analisi dei log, credimi: è veloce).
Prestazioni stabili e affidabili sono importanti per la facilità d'uso del servizio. Se rallenta 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 da ogni repository pubblico di Github. In questa dimostrazione esploro i dati di una settimana: circa 600 MB di log grezzi.
Il video è stato registrato in diretta, senza preparazione speciale, dal mio desktop (circa 5000 chilometri dal server). Le prestazioni che vedrete sono in gran parte dovute , così come a un backend rapido e affidabile. Ogni volta che c'è una pausa senza l'indicatore 'loading', è perché mi sono fermato per darvi il tempo di leggere cosa sto per cliccare.
In conclusione
Quando si elaborano grandi volumi di dati, è fondamentale scegliere un buon algoritmo, ma 'buono' non significa 'stravagante'. Pensate a come il vostro codice funzionerà nella pratica. Alcuni fattori possono essere trascurati nell'analisi teorica degli algoritmi, ma possono avere un grande impatto nel mondo reale. Algoritmi più semplici sono più facili da ottimizzare e più stabili in situazioni limite.
Considera anche il contesto in cui verrà eseguito il codice. Nel nostro caso, servono server abbastanza potenti per gestire i compiti in background. Gli utenti avviano raramente le ricerche, quindi possiamo prendere in prestito un intero gruppo di server per il breve periodo necessario a completare 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 possano essere utili per i vostri progetti.
Modifica: 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à è principalmente dovuto al cambiamento nel tipo e nel numero di server EC2 che oggi utilizziamo per servire una clientela in crescita. Sono in arrivo ulteriori modifiche che garantiranno un altro notevole incremento dell'efficienza, e non vediamo l'ora di avere l'opportunità di parlarne.
Fonte: habr.com
