TL;DR: Fa quatre anys vaig deixar Google amb una idea per a una nova eina de monitorització de servidors. La idea era combinar funcions normalment aïllades en un sol servei i anàlisi de registres, recollida de mètriques, i quadres de comandament. Un dels principis és que el servei ha de ser de veritat ràpid, proporcionant als devops una experiència fàcil, interactiva i agradable. Això requereix processar conjunts de dades de diversos gigabytes en fraccions de segon i mantenir-se dins del pressupost. Les eines de gestió de registres existents solen ser lentes i complicades, de manera que ens vam enfrontar a un bon repte: dissenyar de manera intel·ligent una eina per oferir als usuaris una nova experiència.
Aquest article descriu com a Scalyr vam resoldre aquest problema aplicant mètodes de la vella escola, un enfocament de força bruta, eliminant capes innecessàries i evitant estructures de dades complexes. Podeu aplicar aquestes lliçons als vostres propis problemes d'enginyeria.
Poder de la vella escola
L'anàlisi del registre sol començar amb una cerca: trobar tots els missatges que coincideixen amb un patró determinat. A Scalyr, es tracta de desenes o centenars de gigabytes de registres de molts servidors. Els enfocaments moderns, per regla general, impliquen la construcció d'alguna estructura de dades complexa optimitzada per a la cerca. Sens dubte, ho he vist a Google, on són força bons en aquest tipus de coses. Però vam optar per un enfocament molt més cru: l'exploració lineal de registres. I va funcionar: proporcionem una interfície de cerca que és ordres de magnitud més ràpid que els nostres competidors (vegeu l'animació al final).
La idea clau va ser que els processadors moderns són realment molt ràpids en operacions senzilles i senzilles. Això és fàcil de perdre's en sistemes complexos i multicapa que depenen de la velocitat d'E/S i les operacions de xarxa, i aquests sistemes són molt comuns avui dia. Així que vam desenvolupar un disseny que minimitza les capes i l'excés de deixalles. Amb diversos processadors i servidors en paral·lel, la velocitat de cerca arriba a 1 TB per segon.
Punts clau d'aquest article:
- La cerca de força bruta és un enfocament viable per resoldre problemes a gran escala del món real.
- La força bruta és una tècnica de disseny, no una solució lliure de treball. Com qualsevol tècnica, s'adapta millor a alguns problemes que a altres, i es pot implementar malament o bé.
- La força bruta és especialment bona per aconseguir-ho estable productivitat.
- L'ús efectiu de la força bruta requereix optimitzar el codi i aplicar recursos suficients en el moment adequat. És adequat si els vostres servidors estan sota una gran càrrega de no usuaris i les operacions dels usuaris segueixen sent una prioritat.
- El rendiment depèn del disseny de tot el sistema, no només de l'algoritme de bucle intern.
(Aquest article descriu la cerca de dades a la memòria. En la majoria dels casos, quan un usuari realitza una cerca de registre, els servidors de Scalyr ja l'han guardat a la memòria cau. El següent article tractarà sobre la cerca de registres sense memòria cau. S'apliquen els mateixos principis: codi eficient, força bruta amb grans recursos computacionals).
Mètode de força bruta
Tradicionalment, es cerca un conjunt de dades gran mitjançant un índex de paraules clau. Quan s'aplica als registres del servidor, això significa cercar cada paraula única del registre. Per a cada paraula, heu de fer una llista de totes les inclusions. Això fa que sigui fàcil trobar tots els missatges amb aquesta paraula, per exemple "error", "firefox" o "transaction_16851951"; només cal que mireu l'índex.
Vaig utilitzar aquest enfocament a Google i va funcionar bé. Però a Scalyr cerquem els registres byte per byte.
Per què? Des d'un punt de vista algorítmic abstracte, els índexs de paraules clau són molt més eficients que les cerques de força bruta. Tanmateix, no venem algorismes, venem rendiment. I el rendiment no és només sobre algorismes, sinó també sobre enginyeria de sistemes. Hem de considerar-ho tot: volum de dades, tipus de cerca, maquinari disponible i context de programari. Vam decidir que per al nostre problema particular, alguna cosa com "grep" era més adequat que un índex.
Els índexs són excel·lents, però tenen limitacions. Una paraula és fàcil de trobar. Però cercar missatges amb diverses paraules, com ara "googlebot" i "404", és molt més difícil. Cercar una frase com "excepció no capturada" requereix un índex més complicat que enregistri no només tots els missatges amb aquesta paraula, sinó també la ubicació específica de la paraula.
La veritable dificultat ve quan no busques paraules. Suposem que voleu veure quant trànsit prové dels robots. El primer pensament és buscar la paraula "bot" als registres. Així és com trobareu alguns bots: Googlebot, Bingbot i molts altres. Però aquí "bot" no és una paraula, sinó una part d'ella. Si cerquem "bot" a l'índex, no trobarem cap entrada amb la paraula "Googlebot". Si comproveu totes les paraules de l'índex i després escanegeu l'índex per trobar les paraules clau trobades, la cerca s'alentirà molt. Com a resultat, alguns programes de registre no permeten cerques de paraules parcials o (en el millor dels casos) permeten una sintaxi especial amb un rendiment inferior. Volem evitar això.
Un altre problema és la puntuació. Vols trobar totes les peticions de 50.168.29.7? Què passa amb els registres de depuració que contenen [error]? Els índexs solen saltar la puntuació.
Finalment, als enginyers els encanten les eines potents i, de vegades, un problema només es pot resoldre amb una expressió regular. L'índex de paraules clau no és gaire adequat per a això.
A més, els índexs complex. Cada missatge s'ha d'afegir a diverses llistes de paraules clau. Aquestes llistes s'han de mantenir en un format de cerca fàcil en tot moment. Les consultes amb frases, fragments de paraules o expressions regulars s'han de traduir en operacions de diverses llistes i els resultats s'han d'escanejar i combinar per produir un conjunt de resultats. En el context d'un servei multi-inquilí a gran escala, aquesta complexitat crea problemes de rendiment que no són visibles en analitzar els algorismes.
Els índexs de paraules clau també ocupen molt d'espai i l'emmagatzematge és un cost important en un sistema de gestió de registres.
D'altra banda, cada cerca pot consumir molta potència de càlcul. Els nostres usuaris agraeixen les cerques d'alta velocitat per a consultes úniques, però aquestes consultes es fan relativament poques vegades. Per a consultes de cerca típiques, per exemple, per a un tauler, utilitzem tècniques especials (les descriurem a l'article següent). Altres sol·licituds són prou poc freqüents que rarament haureu de processar-ne més d'una alhora. Però això no vol dir que els nostres servidors no estiguin ocupats: estan ocupats amb la feina de rebre, analitzar i comprimir nous missatges, avaluar alertes, comprimir dades antigues, etc. Així, tenim una oferta força important de processadors que es poden utilitzar per executar consultes.
La força bruta funciona si teniu un problema brut (i molta força)
La força bruta funciona millor en problemes simples amb bucles interns petits. Sovint podeu optimitzar el bucle intern perquè funcioni a velocitats molt altes. Si el codi és complex, és molt més difícil optimitzar-lo.
El nostre codi de cerca originalment tenia un bucle interior força gran. Emmagatzemem missatges en pàgines a 4K; cada pàgina conté alguns missatges (en UTF-8) i metadades per a cada missatge. Les metadades són una estructura que codifica la longitud del valor, l'identificador intern del missatge i altres camps. El cicle de cerca tenia aquest aspecte:
Aquesta és una versió simplificada del codi real. Però fins i tot aquí, són visibles diverses ubicacions d'objectes, còpies de dades i trucades de funcions. La JVM és bastant bona per optimitzar les trucades de funcions i assignar objectes efímers, de manera que aquest codi va funcionar millor del que ens mereixíem. Durant les proves, els clients el van utilitzar amb força èxit. Però finalment ho vam portar al següent nivell.
(Potser us pregunteu per què emmagatzemem missatges en aquest format amb pàgines de 4K, text i metadades, en lloc de treballar amb registres directament. Hi ha moltes raons, que es redueixen al fet que internament el motor Scalyr s'assembla més a una base de dades distribuïda que a una base de dades distribuïda). sistema de fitxers. La cerca de text sovint es combina amb filtres d'estil DBMS als marges després de l'anàlisi de registres. Podem cercar simultàniament molts milers de registres alhora, i els fitxers de text simples no són adequats per a la nostra gestió de dades transaccionals, replicades i distribuïdes).
Inicialment, semblava que aquest codi no era gaire adequat per a l'optimització de força bruta. "Treball real" a String.indexOf() ni tan sols dominava el perfil de la CPU. És a dir, l'optimització d'aquest mètode per si sola no comportaria un efecte significatiu.
Succeeix que emmagatzemem metadades al principi de cada pàgina i el text de tots els missatges en UTF-8 s'empaqueta a l'altre extrem. Aprofitant això, vam reescriure el bucle per cercar tota la pàgina alhora:
Aquesta versió funciona directament a la vista raw byte[] i cerca tots els missatges alhora a tota la pàgina 4K.
Això és molt més fàcil d'optimitzar per al mètode de força bruta. El bucle de cerca intern es crida simultàniament per a tota la pàgina 4K, i no per separat a cada publicació. No hi ha còpia de dades, ni assignació d'objectes. I les operacions de metadades més complexes només es criden quan el resultat és positiu, i no en tots els missatges. D'aquesta manera hem eliminat un munt de despeses generals i la resta de la càrrega es concentra en un petit bucle de cerca intern, que és molt adequat per a una optimització addicional.
Es basa el nostre algorisme de cerca real . És similar a l'algorisme de Boyer-Moore, saltant aproximadament la longitud de la cadena de cerca a cada pas. La diferència principal és que comprova dos bytes alhora per minimitzar les coincidències falses.
La nostra implementació requereix crear una taula de cerca de 64K per a cada cerca, però això no és res en comparació amb els gigabytes de dades que estem cercant. El bucle interior processa diversos gigabytes per segon en un sol nucli. A la pràctica, el rendiment estable és d'uns 1,25 GB per segon a cada nucli i hi ha marge per millorar. És possible eliminar part de la sobrecàrrega fora del bucle intern, i tenim previst experimentar amb un bucle intern en C en lloc de Java.
Fem servir la força
Hem comentat que la cerca de registres es pot implementar "aproximadament", però quant "poder" tenim? Molt.
1 nucli: Quan s'utilitza correctament, un únic nucli d'un processador modern és força potent per si mateix.
8 nuclis: Actualment estem funcionant amb servidors SSD hi1.4xlarge i i2.4xlarge d'Amazon, cadascun amb 8 nuclis (16 fils). Com s'ha esmentat anteriorment, aquests nuclis solen estar ocupats amb operacions de fons. Quan l'usuari realitza una cerca, les operacions en segon pla es suspenen, alliberant els 8 nuclis per a la cerca. La cerca normalment es completa en una fracció de segon, després de la qual es reprèn el treball en segon pla (el programa d'acceleració assegura que l'allau de consultes de cerca no interfereixi amb el treball en segon pla important).
16 nuclis: per fiabilitat, organitzem els servidors en grups mestres/esclaus. Cada mestre té un servidor SSD i un servidor EBS sota les seves ordres. Si el servidor principal falla, el servidor SSD ocupa immediatament el seu lloc. Gairebé tot el temps, mestre i esclau funcionen bé, de manera que cada bloc de dades es pot cercar en dos servidors diferents (el servidor esclau EBS té un processador feble, per la qual cosa no ho tenim en compte). Repartim la tasca entre ells, de manera que tenim un total de 16 nuclis disponibles.
Molts nuclis: En un futur proper, distribuirem dades entre servidors de manera que tots participin en el processament de totes les sol·licituds no trivials. Cada nucli funcionarà. [Nota: vam implementar el pla i vam augmentar la velocitat de cerca a 1 TB/s, vegeu la nota al final de l'article].
La senzillesa garanteix la fiabilitat
Un altre avantatge del mètode de força bruta és el seu rendiment força consistent. Normalment, la cerca no és molt sensible als detalls del problema i al conjunt de dades (suposo que per això s'anomena "grosera").
L'índex de paraules clau de vegades produeix resultats increïblement ràpids, i altres vegades no. Suposem que teniu 50 GB de registres en què el terme "client_5987235982" apareix exactament tres vegades. Una cerca d'aquest terme compta amb tres ubicacions directament des de l'índex i es completarà a l'instant. Però les cerques de comodins complexes poden escanejar milers de paraules clau i trigar molt de temps.
D'altra banda, les cerques de força bruta funcionen més o menys a la mateixa velocitat per a qualsevol consulta. Cercar paraules llargues és millor, però fins i tot cercar un sol caràcter és bastant ràpid.
La simplicitat del mètode de força bruta fa que el seu rendiment s'aproximi al seu màxim teòric. Hi ha menys opcions per a sobrecàrregues de disc inesperades, contenció de bloqueig, persecució de punters i milers d'altres motius per fallar. Acabo de mirar les sol·licituds fetes pels usuaris de Scalyr la setmana passada al nostre servidor més ocupat. Hi havia 14 peticions. Exactament vuit d'ells van trigar més d'un segon; 000% completat en 99 mil·lisegons (si no heu utilitzat eines d'anàlisi de registres, confieu en mi: és ràpid).
El rendiment estable i fiable és important per facilitar l'ús del servei. Si es retarda periòdicament, els usuaris el percebran com a poc fiable i es mostraran reticents a utilitzar-lo.
Cerca de registre en acció
Aquí teniu una animació curta que mostra la cerca de Scalyr en acció. Tenim un compte de demostració on importem tots els esdeveniments a tots els dipòsits públics de Github. En aquesta demostració, examino les dades d'una setmana: aproximadament 600 MB de registres en brut.
El vídeo es va gravar en directe, sense preparació especial, al meu escriptori (a uns 5000 quilòmetres del servidor). El rendiment que veuràs es deu en gran part , així com un backend ràpid i fiable. Sempre que hi ha una pausa sense un indicador de "càrrega", sóc jo la pausa perquè pugueu llegir el que estic a punt de prémer.
en conclusió
Quan es processen grans quantitats de dades, és important triar un bon algorisme, però "bo" no vol dir "fantàstic". Penseu en com funcionarà el vostre codi a la pràctica. L'anàlisi teòrica dels algorismes deixa de banda alguns factors que poden ser de gran importància en el món real. Els algorismes més senzills són més fàcils d'optimitzar i més estables en situacions de punta.
Penseu també en el context en què s'executarà el codi. En el nostre cas, necessitem servidors prou potents per gestionar tasques en segon pla. Els usuaris inicien cerques amb relativa poca freqüència, de manera que podem agafar en préstec tot un grup de servidors durant el curt període necessari per completar cada cerca.
Mitjançant un mètode de força bruta, vam implementar una cerca ràpida, fiable i flexible en un conjunt de registres. Esperem que aquestes idees siguin útils per als vostres projectes.
Edita: El títol i el text han canviat de "Cerca a 20 GB per segon" a "Cerca a 1 TB per segon" per reflectir els augments de rendiment dels darrers anys. Aquest augment de la velocitat es deu principalment als canvis en el tipus i el nombre de servidors EC2 que estem instal·lant avui per atendre la nostra base de clients creixent. Aviat hi haurà canvis que donaran un altre impuls espectacular a l'eficiència operativa, i no podem esperar per compartir-los.
Font: www.habr.com