TL;DR: For fire år siden forlot jeg Google med en idé om et nytt serverovervåkingsverktøy. Tanken var å kombinere vanligvis isolerte funksjoner til én tjeneste og logganalyse, metrikkinnsamling, og dashbord. Et av prinsippene er at tjenesten skal være ekte rask, som gir devops en enkel, interaktiv og hyggelig opplevelse. Dette krever behandling av multi-gigabyte datasett på brøkdeler av et sekund mens du holder deg innenfor budsjettet. Eksisterende loggadministrasjonsverktøy er ofte trege og klønete, så vi ble møtt med en god utfordring: smart utforme et verktøy for å gi brukerne en ny opplevelse.
Denne artikkelen beskriver hvordan vi i Scalyr løste dette problemet ved å bruke gamle skolemetoder, en brute force-tilnærming, eliminere unødvendige lag og unngå komplekse datastrukturer. Du kan bruke disse leksjonene på dine egne tekniske problemer.
Old School Power
Logganalyse begynner vanligvis med et søk: finn alle meldinger som samsvarer med et bestemt mønster. I Scalyr er dette titalls eller hundrevis av gigabyte med logger fra mange servere. Moderne tilnærminger innebærer som regel konstruksjon av en kompleks datastruktur optimalisert for søk. Jeg har absolutt sett dette på Google, hvor de er ganske gode på denne typen ting. Men vi bestemte oss for en mye grovere tilnærming: lineær skanning av logger. Og det fungerte – vi tilbyr et søkbart grensesnitt som er størrelsesordener raskere enn våre konkurrenter (se animasjon til slutt).
Nøkkelinnsikten var at moderne prosessorer faktisk er veldig raske ved enkle, greie operasjoner. Dette er lett å gå glipp av i komplekse flerlagssystemer som er avhengige av I/O-hastighet og nettverksoperasjoner, og slike systemer er svært vanlige i dag. Så vi utviklet et design som minimerer lag og overflødig rusk. Med flere prosessorer og servere parallelt, når søkehastigheten 1 TB per sekund.
Viktige ting fra denne artikkelen:
- Brute-force-søk er en levedyktig tilnærming for å løse reelle problemer i stor skala.
- Brute force er en designteknikk, ikke en arbeidsfri løsning. Som enhver teknikk er den bedre egnet for noen problemer enn andre, og kan implementeres dårlig eller godt.
- Brute force er spesielt bra for å oppnå stabil opptreden.
- Effektiv bruk av brute force krever optimalisering av kode og bruk av tilstrekkelige ressurser til rett tid. Det er egnet hvis serverne dine er under stor ikke-brukerbelastning og brukeroperasjoner fortsatt er en prioritet.
- Ytelsen avhenger av utformingen av hele systemet, ikke bare den indre sløyfealgoritmen.
(Denne artikkelen beskriver søk etter data i minnet. I de fleste tilfeller, når en bruker utfører et loggsøk, har Scalyr-serverne allerede bufret det. Den neste artikkelen vil diskutere søk etter ubufrede logger. De samme prinsippene gjelder: effektiv kode, brute force med store beregningsressurser).
Brute force metode
Tradisjonelt søkes et stort datasett ved hjelp av en nøkkelordindeks. Når det brukes på serverlogger, betyr dette å søke etter hvert unike ord i loggen. For hvert ord må du lage en liste over alle inkluderinger. Dette gjør det enkelt å finne alle meldinger med dette ordet, for eksempel 'error', 'firefox' eller "transaction_16851951" - bare se i indeksen.
Jeg brukte denne tilnærmingen hos Google, og den fungerte bra. Men i Scalyr søker vi loggene byte for byte.
Hvorfor? Fra et abstrakt algoritmisk synspunkt er nøkkelordindekser mye mer effektive enn brute force-søk. Vi selger imidlertid ikke algoritmer, vi selger ytelse. Og ytelse handler ikke bare om algoritmer, men også om systemutvikling. Vi må vurdere alt: datamengde, type søk, tilgjengelig maskinvare og programvarekontekst. Vi bestemte oss for at for vårt spesielle problem var noe som 'grep' bedre egnet enn en indeks.
Indekser er flotte, men de har begrensninger. Ett ord er lett å finne. Men å søke etter meldinger med flere ord, for eksempel "googlebot" og "404", er mye vanskeligere. Å søke etter en setning som "ufanget unntak" krever en mer tungvint indeks som registrerer ikke bare alle meldinger med det ordet, men også den spesifikke plasseringen til ordet.
Den virkelige vanskeligheten kommer når du ikke leter etter ord. La oss si at du vil se hvor mye trafikk som kommer fra roboter. Den første tanken er å søke i loggene etter ordet 'bot'. Slik finner du noen roboter: Googlebot, Bingbot og mange andre. Men her er ikke 'bot' et ord, men en del av det. Hvis vi søker etter 'bot' i indeksen, finner vi ingen innlegg med ordet 'Googlebot'. Hvis du sjekker hvert ord i indeksen og deretter skanner indeksen for søkeordene som er funnet, vil søket tregere kraftig. Som et resultat tillater noen loggprogrammer ikke delordsøk eller (i beste fall) tillater spesiell syntaks med lavere ytelse. Dette ønsker vi å unngå.
Et annet problem er tegnsetting. Ønsker du å finne alle forespørsler fra 50.168.29.7? Hva med å feilsøke logger som inneholder [error]? Abonnementer hopper vanligvis over tegnsetting.
Endelig elsker ingeniører kraftige verktøy, og noen ganger kan et problem bare løses med et regulært uttrykk. Nøkkelordindeksen er lite egnet for dette.
I tillegg kommer indeksene kompleks. Hver melding må legges til flere søkeordlister. Disse listene bør holdes i et lett søkbart format til enhver tid. Spørringer med fraser, ordfragmenter eller regulære uttrykk må oversettes til flerlisteoperasjoner, og resultatene skannes og kombineres for å produsere et resultatsett. I sammenheng med en storskala tjeneste med flere leietakere, skaper denne kompleksiteten ytelsesproblemer som ikke er synlige når man analyserer algoritmene.
Nøkkelordindekser tar også opp mye plass, og lagring er en stor kostnad i et loggstyringssystem.
På den annen side kan hvert søk forbruke mye datakraft. Våre brukere setter pris på høyhastighetssøk etter unike søk, men slike søk gjøres relativt sjelden. For typiske søk, for eksempel for et dashbord, bruker vi spesielle teknikker (vi vil beskrive dem i neste artikkel). Andre forespørsler er sjeldne nok til at du sjelden må behandle mer enn én om gangen. Men dette betyr ikke at serverne våre ikke er opptatt: de er opptatt med arbeidet med å motta, analysere og komprimere nye meldinger, evaluere varsler, komprimere gamle data, og så videre. Dermed har vi en ganske betydelig tilgang på prosessorer som kan brukes til å utføre spørringer.
Brute force fungerer hvis du har et brute problem (og mye kraft)
Brute force fungerer best på enkle problemer med små interne løkker. Ofte kan du optimalisere den interne sløyfen til å kjøre i svært høye hastigheter. Hvis koden er kompleks, er det mye vanskeligere å optimalisere den.
Vår søkekode hadde opprinnelig en ganske stor indre løkke. Vi lagrer meldinger på sider ved 4K; hver side inneholder noen meldinger (i UTF-8) og metadata for hver melding. Metadata er en struktur som koder lengden på verdien, intern meldings-ID og andre felt. Søkesyklusen så slik ut:
Dette er en forenklet versjon av den faktiske koden. Men selv her er flere objektplasseringer, datakopier og funksjonskall synlige. JVM er ganske god til å optimalisere funksjonskall og tildele flyktige objekter, så denne koden fungerte bedre enn vi fortjente. Under testing brukte kundene det ganske vellykket. Men til slutt tok vi det til neste nivå.
(Du kan spørre hvorfor vi lagrer meldinger i dette formatet med 4K-sider, tekst og metadata, i stedet for å jobbe med logger direkte. Det er mange grunner som koker ned til det faktum at Scalyr-motoren internt er mer som en distribuert database enn en filsystem. Tekstsøk kombineres ofte med DBMS-stilfiltre i margene etter loggparsing. Vi kan samtidig søke i mange tusen logger på en gang, og enkle tekstfiler egner seg ikke for vår transaksjonelle, replikerte, distribuerte databehandling).
I utgangspunktet så det ut til at slik kode ikke var særlig egnet for brute force-optimalisering. "Ekte arbeid" i String.indexOf() dominerte ikke engang CPU-profilen. Det vil si at optimalisering av denne metoden alene ikke ville gi noen signifikant effekt.
Det har seg slik at vi lagrer metadata i begynnelsen av hver side, og teksten til alle meldinger i UTF-8 pakkes i den andre enden. Ved å dra nytte av dette, skrev vi om loopen for å søke på hele siden samtidig:
Denne versjonen fungerer direkte på visningen raw byte[] og søker i alle meldinger samtidig på hele 4K-siden.
Dette er mye lettere å optimalisere for brute force-metoden. Den interne søkesløyfen kalles samtidig for hele 4K-siden, i stedet for separat på hvert innlegg. Det er ingen kopiering av data, ingen allokering av objekter. Og mer komplekse metadataoperasjoner kalles bare når resultatet er positivt, og ikke på hver melding. På denne måten har vi eliminert massevis av overhead, og resten av belastningen er konsentrert i en liten intern søkesløyfe, som er godt egnet for videre optimalisering.
Vår faktiske søkealgoritme er basert på . Den ligner på Boyer-Moore-algoritmen, og hopper omtrent over lengden på søkestrengen ved hvert trinn. Hovedforskjellen er at den sjekker to byte om gangen for å minimere falske treff.
Implementeringen vår krever å lage en 64K oppslagstabell for hvert søk, men det er ingenting sammenlignet med gigabytene med data vi søker gjennom. Den indre sløyfen behandler flere gigabyte per sekund på en enkelt kjerne. I praksis er stabil ytelse rundt 1,25 GB per sekund på hver kjerne, og det er rom for forbedring. Det er mulig å eliminere noe av overheaden utenfor den indre sløyfen, og vi planlegger å eksperimentere med en indre sløyfe i C i stedet for Java.
Vi bruker makt
Vi har diskutert at loggsøking kan implementeres «omtrent», men hvor mye «kraft» har vi? Ganske mye.
1 kjerne: Når den brukes riktig, er en enkelt kjerne i en moderne prosessor ganske kraftig i seg selv.
8 kjerner: Vi kjører for tiden på Amazon hi1.4xlarge og i2.4xlarge SSD-servere, hver med 8 kjerner (16 tråder). Som nevnt ovenfor er disse kjernene vanligvis opptatt med bakgrunnsoperasjoner. Når brukeren utfører et søk, blir bakgrunnsoperasjoner suspendert, noe som frigjør alle 8 kjerner for søk. Søket fullføres vanligvis på et brøkdel av et sekund, hvoretter bakgrunnsarbeidet gjenopptas (strupeprogrammet sørger for at floken av søkeforespørsler ikke forstyrrer viktig bakgrunnsarbeid).
16 kjerner: for pålitelighet organiserer vi servere i master/slave-grupper. Hver master har én SSD og én EBS-server under sin kommando. Hvis hovedserveren krasjer, tar SSD-serveren sin plass umiddelbart. Nesten hele tiden fungerer master og slave fint, slik at hver datablokk er søkbar på to forskjellige servere (EBS-slaveserveren har en svak prosessor, så vi vurderer det ikke). Vi deler oppgaven mellom dem, slik at vi totalt har 16 kjerner tilgjengelig.
Mange kjerner: I nær fremtid vil vi distribuere data på tvers av servere på en slik måte at de alle deltar i behandlingen av alle ikke-trivielle forespørseler. Hver kjerne vil fungere. [Merk: vi implementerte planen og økte søkehastigheten til 1 TB/s, se merknad på slutten av artikkelen].
Enkelhet sikrer pålitelighet
En annen fordel med brute force-metoden er dens ganske konsistente ytelse. Vanligvis er ikke søk veldig sensitivt for detaljene i problemet og datasettet (jeg antar at det er derfor det kalles "grovt").
Nøkkelordindeksen gir noen ganger utrolig raske resultater, og andre ganger gjør den det ikke. La oss si at du har 50 GB med logger der begrepet 'customer_5987235982' vises nøyaktig tre ganger. Et søk etter denne termen teller tre steder direkte fra indeksen og vil fullføres umiddelbart. Men komplekse jokertegnsøk kan skanne tusenvis av søkeord og ta lang tid.
På den annen side utfører brute force-søk med mer eller mindre samme hastighet for alle søk. Det er bedre å søke etter lange ord, men selv å søke etter et enkelt tegn er ganske raskt.
Enkelheten til brute force-metoden betyr at ytelsen er nær det teoretiske maksimum. Det er færre alternativer for uventede diskoverbelastninger, låsestrid, pekerjaging og tusenvis av andre årsaker til feil. Jeg så nettopp på forespørslene fra Scalyr-brukere forrige uke på vår travleste server. Det var 14 000 forespørsler. Nøyaktig åtte av dem tok mer enn ett sekund; 99 % fullført innen 111 millisekunder (hvis du ikke har brukt logganalyseverktøy, stol på meg: det er raskt).
Stabil, pålitelig ytelse er viktig for enkel bruk av tjenesten. Hvis det henger med jevne mellomrom, vil brukerne oppleve det som upålitelig og være motvillige til å bruke det.
Loggsøk i aksjon
Her er en kort animasjon som viser Scalyr-søk i aksjon. Vi har en demokonto der vi importerer hver hendelse i alle offentlige Github-depoter. I denne demoen undersøker jeg en ukes data: omtrent 600 MB rålogger.
Videoen ble spilt inn live, uten spesielle forberedelser, på skrivebordet mitt (omtrent 5000 kilometer fra serveren). Ytelsen du vil se skyldes i stor grad , samt en rask og pålitelig backend. Når det er en pause uten en "lasting"-indikator, er det jeg som stopper, slik at du kan lese hva jeg skal trykke.
i konklusjonen
Når du behandler store datamengder, er det viktig å velge en god algoritme, men "bra" betyr ikke "fancy". Tenk på hvordan koden din vil fungere i praksis. Den teoretiske analysen av algoritmer utelater noen faktorer som kan ha stor betydning i den virkelige verden. Enklere algoritmer er lettere å optimalisere og mer stabile i kantsituasjoner.
Tenk også på konteksten som koden skal kjøres i. I vårt tilfelle trenger vi tilstrekkelig kraftige servere for å håndtere bakgrunnsoppgaver. Brukere starter søk relativt sjelden, så vi kan låne en hel gruppe servere i den korte perioden som trengs for å fullføre hvert søk.
Ved å bruke en brute force-metode implementerte vi et raskt, pålitelig, fleksibelt søk på tvers av et sett med logger. Vi håper disse ideene er nyttige for dine prosjekter.
Redigere: Tittelen og teksten har endret seg fra «Søk med 20 GB per sekund» til «Søk med 1 TB per sekund» for å gjenspeile ytelsesøkningene de siste årene. Denne hastighetsøkningen skyldes først og fremst endringer i typen og antallet EC2-servere vi setter opp i dag for å betjene vår økte kundebase. Det kommer snart endringer som vil gi enda et dramatisk løft i operasjonell effektivitet, og vi gleder oss til å dele dem.
Kilde: www.habr.com