TL;DR: Vier jaar gelede het ek Google verlaat met 'n idee vir 'n nuwe bedienermoniteringsinstrument. Die idee was om gewoonlik geïsoleerde funksies in een diens te kombineer en log analise, metrieke versameling, en dashboards. Een van die beginsels is dat die diens waarlik moet wees vinnig, wat devops 'n maklike, interaktiewe, aangename ervaring bied. Dit vereis die verwerking van multi-gigagrepe-datastelle in breukdele van 'n sekonde terwyl dit binne die begroting bly. Bestaande logbestuurnutsmiddels is dikwels stadig en lomp, so ons het voor 'n goeie uitdaging te staan gekom: slim ontwerp van 'n hulpmiddel om gebruikers 'n nuwe ervaring te gee.
Hierdie artikel beskryf hoe ons by Scalyr hierdie probleem opgelos het deur ou skoolmetodes, 'n brute force-benadering toe te pas, onnodige lae uit te skakel en komplekse datastrukture te vermy. Jy kan hierdie lesse op jou eie ingenieursprobleme toepas.
Old School Power
Loganalise begin gewoonlik met 'n soektog: vind alle boodskappe wat by 'n sekere patroon pas. In Scalyr is dit tiene of honderde gigagrepe logs van baie bedieners. Moderne benaderings behels as 'n reël die konstruksie van 'n komplekse datastruktuur wat vir soektog geoptimaliseer is. Ek het dit beslis op Google gesien, waar hulle redelik goed is in hierdie soort ding. Maar ons het besluit op 'n baie growwer benadering: lineêre skandering van logs. En dit het gewerk - ons bied 'n soekbare koppelvlak wat ordes van grootte vinniger is as ons mededingers (sien animasie aan die einde).
Die sleutelinsig was dat moderne verwerkers inderdaad baie vinnig is met eenvoudige, reguit bewerkings. Dit is maklik om dit te mis in komplekse meerlaagstelsels wat staatmaak op I/O-spoed en netwerkbedrywighede, en sulke stelsels is vandag baie algemeen. Ons het dus 'n ontwerp ontwikkel wat lae en oortollige rommel tot die minimum beperk. Met verskeie verwerkers en bedieners in parallel, bereik die soekspoed 1 TB per sekonde.
Sleutel wegneemetes uit hierdie artikel:
- Brute-force-soektog is 'n lewensvatbare benadering om werklike, grootskaalse probleme op te los.
- Brute force is 'n ontwerptegniek, nie 'n werkvrye oplossing nie. Soos enige tegniek, is dit beter geskik vir sommige probleme as ander, en kan dit swak of goed geïmplementeer word.
- Brute krag is veral goed om te bereik stabiel produktiwiteit.
- Effektiewe gebruik van brute krag vereis die optimalisering van kode en die toepassing van voldoende hulpbronne op die regte tyd. Dit is geskik as u bedieners onder swaar nie-gebruikerslading is en gebruikersbedrywighede 'n prioriteit bly.
- Werkverrigting hang af van die ontwerp van die hele stelsel, nie net die binnelusalgoritme nie.
(Hierdie artikel beskryf die soektog na data in die geheue. In die meeste gevalle, wanneer 'n gebruiker 'n logsoektog doen, het die Scalyr-bedieners dit reeds in die kas gekas. Die volgende artikel sal die soektog na ongekaslogboeke bespreek. Dieselfde beginsels geld: doeltreffende kode, brute force met groot rekenaarhulpbronne).
Brute krag metode
Tradisioneel word 'n groot datastel deursoek deur 'n sleutelwoordindeks te gebruik. Wanneer dit op bedienerlogboeke toegepas word, beteken dit dat u na elke unieke woord in die log moet soek. Vir elke woord moet jy 'n lys van alle insluitings maak. Dit maak dit maklik om alle boodskappe met hierdie woord te vind, byvoorbeeld 'fout', 'firefox' of "transaction_16851951" - kyk net in die indeks.
Ek het hierdie benadering by Google gebruik en dit het goed gewerk. Maar in Scalyr soek ons die logs greep vir greep.
Hoekom? Vanuit 'n abstrakte algoritmiese oogpunt is sleutelwoordindekse baie doeltreffender as brute force-soektogte. Ons verkoop egter nie algoritmes nie, ons verkoop prestasie. En prestasie gaan nie net oor algoritmes nie, maar ook oor stelselingenieurswese. Ons moet alles in ag neem: volume data, tipe soektog, beskikbare hardeware en sagteware konteks. Ons het besluit dat iets soos 'grep' vir ons spesifieke probleem beter geskik is as 'n indeks.
Indekse is wonderlik, maar hulle het beperkings. Een woord is maklik om te vind. Maar soek na boodskappe met veelvuldige woorde, soos 'googlebot' en '404', is baie moeiliker. Om na 'n frase soos 'onbevange uitsondering' te soek, vereis 'n meer omslagtige indeks wat nie net alle boodskappe met daardie woord aanteken nie, maar ook die spesifieke ligging van die woord.
Die werklike moeilikheid kom wanneer jy nie na woorde soek nie. Kom ons sê jy wil sien hoeveel verkeer van bots af kom. Die eerste gedagte is om die logs vir die woord 'bot' te soek. Dit is hoe jy sommige bots sal vind: Googlebot, Bingbot en vele ander. Maar hier is 'bot' nie 'n woord nie, maar 'n deel daarvan. As ons vir 'bot' in die indeks soek, sal ons geen plasings met die woord 'Googlebot' vind nie. As jy elke woord in die indeks nagaan en dan die indeks skandeer vir die sleutelwoorde wat gevind is, sal die soektog baie vertraag. Gevolglik laat sommige logprogramme nie deelwoordsoektogte toe nie of laat (op sy beste) spesiale sintaksis met laer werkverrigting toe. Ons wil dit vermy.
Nog 'n probleem is leestekens. Wil jy al die versoeke van vind 50.168.29.7? Wat van ontfouting logs wat bevat [error]? Onderskrifte slaan gewoonlik leestekens oor.
Ten slotte, ingenieurs hou van kragtige gereedskap, en soms kan 'n probleem slegs met 'n gereelde uitdrukking opgelos word. Die sleutelwoordindeks is nie baie geskik hiervoor nie.
Daarbenewens het die indekse kompleks. Elke boodskap moet by verskeie sleutelwoordlyste gevoeg word. Hierdie lyste moet te alle tye in 'n maklik soekbare formaat gehou word. Navrae met frases, woordfragmente of gereelde uitdrukkings moet in multi-lys bewerkings vertaal word, en die resultate geskandeer en gekombineer word om 'n resultaatstel te produseer. In die konteks van 'n grootskaalse, multi-huurder diens, hierdie kompleksiteit skep prestasie kwessies wat nie sigbaar is wanneer die ontleding van die algoritmes.
Sleutelwoordindekse neem ook baie spasie op, en berging is 'n groot koste in 'n logbestuurstelsel.
Aan die ander kant kan elke soektog baie rekenaarkrag verbruik. Ons gebruikers waardeer hoëspoedsoektogte vir unieke navrae, maar sulke navrae word relatief selde gedoen. Vir tipiese soeknavrae, byvoorbeeld vir 'n dashboard, gebruik ons spesiale tegnieke (ons sal dit in die volgende artikel beskryf). Ander versoeke is selde genoeg dat jy selde meer as een op 'n slag hoef te verwerk. Maar dit beteken nie dat ons bedieners nie besig is nie: hulle is besig met die werk om nuwe boodskappe te ontvang, te ontleed en saam te komprimeer, waarskuwings te evalueer, ou data saam te komprimeer, ensovoorts. Ons het dus 'n redelike groot voorraad verwerkers wat gebruik kan word om navrae uit te voer.
Brute krag werk as jy 'n brute probleem het (en baie geweld)
Brute force werk die beste op eenvoudige probleme met klein interne lusse. Dikwels kan jy die interne lus optimaliseer om teen baie hoë spoed te hardloop. As die kode kompleks is, is dit baie moeiliker om dit te optimaliseer.
Ons soekkode het oorspronklik 'n redelik groot binnelus gehad. Ons stoor boodskappe op bladsye by 4K; elke bladsy bevat 'n paar boodskappe (in UTF-8) en metadata vir elke boodskap. Metadata is 'n struktuur wat die lengte van die waarde, interne boodskap-ID en ander velde enkodeer. Die soeksiklus het so gelyk:
Dit is 'n vereenvoudigde weergawe van die werklike kode. Maar selfs hier is veelvuldige voorwerpplasings, datakopieë en funksie-oproepe sigbaar. Die JVM is redelik goed om funksie-oproepe te optimaliseer en kortstondige voorwerpe toe te ken, so hierdie kode het beter gewerk as wat ons verdien het. Tydens toetsing het klante dit redelik suksesvol gebruik. Maar uiteindelik het ons dit na die volgende vlak geneem.
(Jy kan vra hoekom ons boodskappe in hierdie formaat met 4K-bladsye, teks en metadata stoor, eerder as om direk met logs te werk. Daar is baie redes wat daarop neerkom dat die Scalyr-enjin intern meer soos 'n verspreide databasis is as 'n lêerstelsel. Tekssoektog word dikwels gekombineer met DBMS-styl filters in die kantlyne na log ontleding. Ons kan gelyktydig baie duisende logs op een slag deursoek, en eenvoudige tekslêers is nie geskik vir ons transaksionele, gerepliseerde, verspreide databestuur nie).
Aanvanklik het dit gelyk asof sulke kode nie baie geskik was vir brute force-optimalisering nie. "Regte werk" in String.indexOf() het nie eers die SVE-profiel oorheers nie. Dit wil sê, die optimalisering van hierdie metode alleen sal nie 'n beduidende effek hê nie.
Dit gebeur so dat ons metadata aan die begin van elke bladsy stoor, en die teks van alle boodskappe in UTF-8 word aan die ander kant gepak. Deur hiervan gebruik te maak, het ons die lus herskryf om die hele bladsy gelyktydig deur te soek:
Hierdie weergawe werk direk op die aansig raw byte[] en deursoek alle boodskappe gelyktydig oor die hele 4K-bladsy.
Dit is baie makliker om te optimaliseer vir die brute force-metode. Die interne soeklus word gelyktydig vir die hele 4K-bladsy geroep, eerder as afsonderlik op elke pos. Daar is geen kopiëring van data, geen toekenning van voorwerpe nie. En meer komplekse metadata-bewerkings word slegs opgeroep wanneer die resultaat positief is, en nie op elke boodskap nie. Op hierdie manier het ons 'n ton oorhoofse koste uitgeskakel, en die res van die vrag is gekonsentreer in 'n klein interne soeklus, wat goed geskik is vir verdere optimalisering.
Ons werklike soekalgoritme is gebaseer op . Dit is soortgelyk aan die Boyer-Moore-algoritme, en slaan ongeveer die lengte van die soekstring by elke stap oor. Die belangrikste verskil is dat dit twee grepe op 'n slag nagaan om vals passings te minimaliseer.
Ons implementering vereis die skep van 'n 64K-opsoektabel vir elke soektog, maar dit is niks in vergelyking met die gigagrepe data waardeur ons soek nie. Die binnelus verwerk verskeie gigagrepe per sekonde op 'n enkele kern. In die praktyk is die stabiele werkverrigting ongeveer 1,25 GB per sekonde op elke kern, en daar is ruimte vir verbetering. Dit is moontlik om van die bokoste buite die binnelus uit te skakel, en ons beplan om te eksperimenteer met 'n binnelus in C in plaas van Java.
Ons gebruik geweld
Ons het bespreek dat logboeksoektog "rofweg" geïmplementeer kan word, maar hoeveel "krag" het ons? Nogals baie.
1 jaar: Wanneer dit korrek gebruik word, is 'n enkele kern van 'n moderne verwerker nogal kragtig in sy eie reg.
8 kerne: Ons werk tans op Amazon hi1.4xlarge en i2.4xlarge SSD-bedieners, elk met 8 kerns (16 drade). Soos hierbo genoem, is hierdie kerne gewoonlik besig met agtergrondbedrywighede. Wanneer die gebruiker 'n soektog uitvoer, word agtergrondbewerkings opgeskort, wat al 8 kerns vir soektog bevry. Die soektog word gewoonlik binne 'n breukdeel van 'n sekonde voltooi, waarna agtergrondwerk hervat word (die smoorprogram verseker dat die stortvloed soeknavrae nie met belangrike agtergrondwerk inmeng nie).
16 kerne: vir betroubaarheid organiseer ons bedieners in meester-/slaafgroepe. Elke meester het een SSD en een EBS-bediener onder sy bevel. As die hoofbediener ineenstort, neem die SSD-bediener onmiddellik sy plek in. Byna heeltyd werk meester en slaaf goed, sodat elke datablok op twee verskillende bedieners deursoekbaar is (die EBS-slaafbediener het 'n swak verwerker, so ons oorweeg dit nie). Ons verdeel die taak tussen hulle, sodat ons altesaam 16 kerne beskikbaar het.
Baie kerne: In die nabye toekoms sal ons data oor bedieners versprei op so 'n manier dat hulle almal deelneem aan die verwerking van elke nie-onbeduidende versoek. Elke kern sal werk. [Let wel: ons het die plan geïmplementeer en die soekspoed tot 1 TB/s verhoog, sien nota aan die einde van die artikel].
Eenvoud verseker betroubaarheid
Nog 'n voordeel van die brute force-metode is sy redelik konsekwente werkverrigting. Tipies is soektog nie baie sensitief vir die besonderhede van die probleem en datastel nie (ek dink dis hoekom dit "grof" genoem word).
Die sleutelwoordindeks lewer soms ongelooflike vinnige resultate, en ander kere nie. Kom ons sê jy het 50 GB logs waarin die term 'customer_5987235982' presies drie keer voorkom. 'n Soektog na hierdie term tel drie liggings direk vanaf die indeks en sal onmiddellik voltooi word. Maar komplekse jokertekensoektogte kan duisende sleutelwoorde skandeer en lank neem.
Aan die ander kant voer brute force-soektogte min of meer dieselfde spoed vir enige navraag uit. Dit is beter om na lang woorde te soek, maar selfs om na 'n enkele karakter te soek is redelik vinnig.
Die eenvoud van die brute force metode beteken dat sy prestasie naby aan sy teoretiese maksimum is. Daar is minder opsies vir onverwagte skyfoorladings, slotkonflik, wyserjaag en duisende ander redes vir mislukking. Ek het net gekyk na die versoeke wat Scalyr-gebruikers verlede week op ons besigste bediener gemaak het. Daar was 14 000 versoeke. Presies agt van hulle het meer as een sekonde geneem; 99% voltooi binne 111 millisekondes (as jy nie log-analise-nutsmiddels gebruik het nie, vertrou my: dit is vinnig).
Stabiele, betroubare werkverrigting is belangrik vir die gemak van gebruik van die diens. As dit periodiek agterbly, sal gebruikers dit as onbetroubaar beskou en huiwerig wees om dit te gebruik.
Tekensoektog in aksie
Hier is 'n kort animasie wat Scalyr-soektog in aksie wys. Ons het 'n demo-rekening waar ons elke geleentheid in elke publieke Github-bewaarplek invoer. In hierdie demonstrasie ondersoek ek 'n week se data: ongeveer 600 MB se rou logs.
Die video is regstreeks opgeneem, sonder spesiale voorbereiding, op my lessenaar (ongeveer 5000 kilometer van die bediener af). Die prestasie wat jy sal sien is grootliks te danke aan , sowel as 'n vinnige en betroubare backend. Wanneer daar 'n pouse is sonder 'n 'laai'-aanwyser, is dit ek wat pouseer sodat jy kan lees wat ek gaan druk.
Ten slotte
Wanneer groot hoeveelhede data verwerk word, is dit belangrik om 'n goeie algoritme te kies, maar "goed" beteken nie "fancy" nie. Dink na oor hoe jou kode in die praktyk sal werk. Die teoretiese analise van algoritmes laat 'n paar faktore uit wat van groot belang in die werklike wêreld kan wees. Eenvoudiger algoritmes is makliker om te optimaliseer en meer stabiel in randsituasies.
Dink ook aan die konteks waarin die kode uitgevoer sal word. In ons geval het ons voldoende kragtige bedieners nodig om agtergrondtake te bestuur. Gebruikers begin soektogte relatief selde, so ons kan 'n hele groep bedieners leen vir die kort tydperk wat nodig is om elke soektog te voltooi.
Deur 'n brute force-metode te gebruik, het ons 'n vinnige, betroubare, buigsame soektog oor 'n stel logs geïmplementeer. Ons hoop hierdie idees is nuttig vir jou projekte.
Wysig: Die titel en teks het verander van "Soek teen 20 GB per sekonde" na "Soek teen 1 TB per sekonde" om die prestasieverhogings oor die afgelope paar jaar te weerspieël. Hierdie toename in spoed is hoofsaaklik te wyte aan veranderinge in die tipe en aantal EC2-bedieners wat ons vandag opstel om ons groter kliëntebasis te bedien. Daar is binnekort veranderinge wat nog 'n dramatiese hupstoot in bedryfsdoeltreffendheid sal gee, en ons kan nie wag om dit te deel nie.
Bron: will.com