TL;DR: For fire år siden forlod jeg Google med en idé til et nyt serverovervågningsværktøj. Ideen var at kombinere normalt isolerede funktioner i én tjeneste og loganalyse, metrikindsamling, og dashboards. Et af principperne er, at servicen skal være ægte hurtig, der giver devops en nem, interaktiv og fornøjelig oplevelse. Dette kræver behandling af multi-gigabyte datasæt på brøkdele af et sekund, mens man holder sig inden for budgettet. Eksisterende logadministrationsværktøjer er ofte langsomme og klodsede, så vi stod over for en god udfordring: smart at designe et værktøj til at give brugerne en ny oplevelse.
Denne artikel beskriver, hvordan vi hos Scalyr løste dette problem ved at anvende old school metoder, en brute force tilgang, eliminere unødvendige lag og undgå komplekse datastrukturer. Du kan anvende disse lektioner på dine egne tekniske problemer.
Old School Power
Loganalyse begynder normalt med en søgning: find alle beskeder, der matcher et bestemt mønster. I Scalyr er det titusinder eller hundredvis af gigabyte logfiler fra mange servere. Moderne tilgange involverer som regel opbygningen af en kompleks datastruktur, der er optimeret til søgning. Jeg har bestemt set dette på Google, hvor de er ret gode til den slags. Men vi slog os fast på en meget mere grov tilgang: lineær scanning af logfiler. Og det virkede - vi leverer en søgbar grænseflade, der er størrelsesordener hurtigere end vores konkurrenter (se animation til sidst).
Den vigtigste indsigt var, at moderne processorer faktisk er meget hurtige til enkle, ligetil operationer. Dette er let at gå glip af i komplekse flerlagssystemer, der er afhængige af I/O-hastighed og netværksoperationer, og sådanne systemer er meget almindelige i dag. Så vi udviklede et design, der minimerer lag og overskydende snavs. Med flere processorer og servere parallelt når søgehastigheden 1 TB pr. sekund.
Vigtige ting fra denne artikel:
- Brute-force-søgning er en brugbar tilgang til at løse store problemer i den virkelige verden.
- Brute force er en designteknik, ikke en arbejdsfri løsning. Som enhver teknik er den bedre egnet til nogle problemer end andre og kan implementeres dårligt eller godt.
- Brute force er især god til at opnå stabil produktivitet.
- Effektiv brug af brute force kræver optimering af kode og anvendelse af tilstrækkelige ressourcer på det rigtige tidspunkt. Det er velegnet, hvis dine servere er under stor ikke-brugerbelastning, og brugeroperationer forbliver en prioritet.
- Ydeevne afhænger af designet af hele systemet, ikke kun den indre sløjfe-algoritme.
(Denne artikel beskriver søgning efter data i hukommelsen. I de fleste tilfælde, når en bruger udfører en logsøgning, har Scalyr-serverne allerede cache det. Den næste artikel vil diskutere søgning efter ikke-cachede logfiler. De samme principper gælder: effektiv kode, brute force med store beregningsressourcer).
Brute force metode
Traditionelt søges et stort datasæt ved hjælp af et søgeordsindeks. Når det anvendes på serverlogfiler, betyder det, at du søger efter hvert unikt ord i loggen. For hvert ord skal du lave en liste over alle indeslutninger. Dette gør det nemt at finde alle beskeder med dette ord, for eksempel 'fejl', 'firefox' eller "transaction_16851951" - se blot i indekset.
Jeg brugte denne tilgang hos Google, og det fungerede godt. Men i Scalyr søger vi logfilerne byte for byte.
Hvorfor? Fra et abstrakt algoritmisk synspunkt er søgeordsindekser meget mere effektive end brute force-søgninger. Vi sælger dog ikke algoritmer, vi sælger ydeevne. Og ydeevne handler ikke kun om algoritmer, men også om systemudvikling. Vi skal overveje alt: mængden af data, type søgning, tilgængelig hardware og software kontekst. Vi besluttede, at til vores særlige problem var noget som 'grep' bedre egnet end et indeks.
Indekser er gode, men de har begrænsninger. Et ord er let at finde. Men at søge efter beskeder med flere ord, såsom 'googlebot' og '404', er meget sværere. At søge efter en sætning som 'ufanget undtagelse' kræver et mere besværligt indeks, der registrerer ikke kun alle beskeder med det pågældende ord, men også den specifikke placering af ordet.
Den virkelige vanskelighed kommer, når du ikke leder efter ord. Lad os sige, at du vil se, hvor meget trafik der kommer fra bots. Den første tanke er at søge i logfilerne efter ordet 'bot'. Sådan finder du nogle bots: Googlebot, Bingbot og mange andre. Men her er 'bot' ikke et ord, men en del af det. Hvis vi søger efter 'bot' i indekset, finder vi ingen indlæg med ordet 'Googlebot'. Hvis du tjekker hvert ord i indekset og derefter scanner indekset for de fundne søgeord, vil søgningen blive meget langsommere. Som et resultat tillader nogle logprogrammer ikke delordssøgninger eller tillader (i bedste fald) speciel syntaks med lavere ydeevne. Det vil vi gerne undgå.
Et andet problem er tegnsætning. Ønsker du at finde alle forespørgsler fra 50.168.29.7? Hvad med debugging logs, der indeholder [error]? Abonnementer springer normalt tegnsætning over.
Endelig elsker ingeniører kraftfulde værktøjer, og nogle gange kan et problem kun løses med et regulært udtryk. Søgeordsindekset er ikke særlig velegnet til dette.
Hertil kommer indekserne kompleks. Hver besked skal føjes til flere søgeordslister. Disse lister bør altid opbevares i et let søgbart format. Forespørgsler med sætninger, ordfragmenter eller regulære udtryk skal oversættes til flerlisteoperationer, og resultaterne skal scannes og kombineres for at producere et resultatsæt. I forbindelse med en storstilet service med flere lejere skaber denne kompleksitet præstationsproblemer, som ikke er synlige, når man analyserer algoritmerne.
Søgeordsindekser fylder også meget, og opbevaring er en stor omkostning i et logstyringssystem.
På den anden side kan hver søgning tære meget computerkraft. Vores brugere sætter pris på højhastighedssøgninger efter unikke forespørgsler, men sådanne forespørgsler foretages relativt sjældent. Til typiske søgeforespørgsler, for eksempel til et dashboard, bruger vi specielle teknikker (vi vil beskrive dem i den næste artikel). Andre anmodninger er sjældne nok til, at du sjældent skal behandle mere end én ad gangen. Men det betyder ikke, at vores servere ikke er optaget: de har travlt med arbejdet med at modtage, analysere og komprimere nye beskeder, evaluere alarmer, komprimere gamle data og så videre. Vi har således et ret betydeligt udbud af processorer, der kan bruges til at udføre forespørgsler.
Brute force virker, hvis du har et brute problem (og en masse kraft)
Brute force fungerer bedst på simple problemer med små interne løkker. Ofte kan du optimere den interne sløjfe til at køre med meget høje hastigheder. Hvis koden er kompleks, er det meget sværere at optimere den.
Vores søgekode havde oprindeligt en ret stor indre løkke. Vi gemmer beskeder på sider ved 4K; hver side indeholder nogle beskeder (i UTF-8) og metadata for hver besked. Metadata er en struktur, der koder længden af værdien, internt meddelelses-id og andre felter. Søgecyklussen så således ud:
Dette er en forenklet version af den faktiske kode. Men selv her er flere objektplaceringer, datakopier og funktionskald synlige. JVM'en er ret god til at optimere funktionskald og tildele flygtige objekter, så denne kode fungerede bedre, end vi fortjente. Under testning brugte kunderne det ganske med succes. Men til sidst tog vi det til næste niveau.
(Du kan spørge, hvorfor vi gemmer beskeder i dette format med 4K-sider, tekst og metadata, i stedet for at arbejde med logs direkte. Der er mange grunde, der bunder i, at Scalyr-motoren internt er mere som en distribueret database end en filsystem. Tekstsøgning kombineres ofte med DBMS-lignende filtre i marginerne efter log-parsing. Vi kan samtidig søge i mange tusinde logfiler på én gang, og simple tekstfiler er ikke egnede til vores transaktionelle, replikerede, distribuerede datahåndtering).
I starten så det ud til, at en sådan kode ikke var særlig velegnet til brute force-optimering. "rigtigt arbejde" i String.indexOf() dominerede ikke engang CPU-profilen. Det vil sige, at optimering af denne metode alene ikke ville give en væsentlig effekt.
Det sker sådan, at vi gemmer metadata i begyndelsen af hver side, og teksten i alle beskeder i UTF-8 er pakket i den anden ende. Ved at udnytte dette omskrev vi løkken for at søge på hele siden på én gang:
Denne version virker direkte på visningen raw byte[] og søger i alle beskeder på én gang på tværs af hele 4K-siden.
Dette er meget nemmere at optimere til brute force-metoden. Den interne søgeloop kaldes samtidigt for hele 4K-siden i stedet for separat på hvert indlæg. Der er ingen kopiering af data, ingen allokering af objekter. Og mere komplekse metadata-operationer kaldes kun, når resultatet er positivt, og ikke på hver besked. På denne måde har vi elimineret et væld af overhead, og resten af belastningen er koncentreret i en lille intern søgeloop, som er velegnet til yderligere optimering.
Vores egentlige søgealgoritme er baseret på . Det ligner Boyer-Moore-algoritmen, der springer omtrent længden af søgestrengen over ved hvert trin. Den største forskel er, at den kontrollerer to bytes ad gangen for at minimere falske matches.
Vores implementering kræver oprettelse af en 64K opslagstabel for hver søgning, men det er ingenting sammenlignet med de gigabyte data, vi søger igennem. Den indre sløjfe behandler flere gigabyte i sekundet på en enkelt kerne. I praksis er den stabile ydeevne omkring 1,25 GB i sekundet på hver kerne, og der er plads til forbedringer. Det er muligt at fjerne noget af overhead uden for den indre løkke, og vi planlægger at eksperimentere med en indre løkke i C i stedet for Java.
Vi bruger magt
Vi har diskuteret, at logsøgning kan implementeres "omtrent", men hvor meget "power" har vi? Ret meget.
1 kerne: Når den bruges korrekt, er en enkelt kerne i en moderne processor ret kraftfuld i sig selv.
8 kerner: Vi kører i øjeblikket på Amazon hi1.4xlarge og i2.4xlarge SSD-servere, hver med 8 kerner (16 tråde). Som nævnt ovenfor er disse kerner normalt optaget af baggrundsoperationer. Når brugeren udfører en søgning, suspenderes baggrundshandlinger, hvilket frigør alle 8 kerner til søgning. Søgningen afsluttes normalt på et splitsekund, hvorefter baggrundsarbejdet genoptages (gasreguleringsprogrammet sørger for, at bølgen af søgeforespørgsler ikke forstyrrer vigtigt baggrundsarbejde).
16 kerner: For pålidelighed organiserer vi servere i master/slave-grupper. Hver master har én SSD og én EBS-server under sin kommando. Hvis hovedserveren går ned, overtager SSD-serveren straks dens plads. Næsten hele tiden fungerer master og slave fint, så hver datablok er søgbar på to forskellige servere (EBS slaveserveren har en svag processor, så vi overvejer det ikke). Vi fordeler opgaven mellem dem, så vi i alt har 16 kerner til rådighed.
Mange kerner: I den nærmeste fremtid vil vi distribuere data på tværs af servere på en sådan måde, at de alle deltager i behandlingen af enhver ikke-triviel anmodning. Hver kerne vil fungere. [Bemærk: vi implementerede planen og øgede søgehastigheden til 1 TB/s, se note i slutningen af artiklen].
Enkelhed sikrer pålidelighed
En anden fordel ved brute force-metoden er dens ret konsistente ydeevne. Typisk er søgning ikke særlig følsom over for detaljerne i problemet og datasættet (det er vel derfor, det kaldes "groft").
Søgeordsindekset giver nogle gange utroligt hurtige resultater, og andre gange gør det ikke. Lad os sige, at du har 50 GB logfiler, hvor udtrykket 'customer_5987235982' optræder nøjagtigt tre gange. En søgning på dette udtryk tæller tre steder direkte fra indekset og afsluttes øjeblikkeligt. Men komplekse jokertegnssøgninger kan scanne tusindvis af søgeord og tage lang tid.
På den anden side udfører brute force-søgninger med mere eller mindre samme hastighed for enhver forespørgsel. Det er bedre at søge efter lange ord, men selv at søge efter et enkelt tegn er ret hurtigt.
Enkelheden af brute force-metoden betyder, at dens ydeevne er tæt på dets teoretiske maksimum. Der er færre muligheder for uventede diskoverbelastninger, låsestrid, pointerjagt og tusindvis af andre årsager til fejl. Jeg har lige set på anmodningerne fra Scalyr-brugere i sidste uge på vores travleste server. Der var 14 anmodninger. Præcis otte af dem tog mere end et sekund; 000 % fuldført inden for 99 millisekunder (hvis du ikke har brugt loganalyseværktøjer, tro mig: det er hurtigt).
Stabil, pålidelig ydeevne er vigtig for brugervenligheden af tjenesten. Hvis det halter med jævne mellemrum, vil brugerne opfatte det som upålideligt og være tilbageholdende med at bruge det.
Logsøgning i aktion
Her er en kort animation, der viser Scalyr-søgning i aktion. Vi har en demokonto, hvor vi importerer hver begivenhed i alle offentlige Github-depoter. I denne demo undersøger jeg en uges data: cirka 600 MB rå logfiler.
Videoen blev optaget live, uden særlig forberedelse, på mit skrivebord (ca. 5000 kilometer fra serveren). Den præstation, du vil se, skyldes i høj grad , samt en hurtig og pålidelig backend. Når der er en pause uden en "indlæsnings"-indikator, er det mig, der holder pause, så du kan læse, hvad jeg er ved at trykke på.
Afslutningsvis
Når du behandler store mængder data, er det vigtigt at vælge en god algoritme, men "god" betyder ikke "fancy". Tænk over, hvordan din kode vil fungere i praksis. Den teoretiske analyse af algoritmer udelader nogle faktorer, der kan have stor betydning i den virkelige verden. Enklere algoritmer er nemmere at optimere og mere stabile i kantsituationer.
Tænk også på den kontekst, hvori koden vil blive eksekveret. I vores tilfælde har vi brug for tilstrækkeligt stærke servere til at håndtere baggrundsopgaver. Brugere starter søgninger relativt sjældent, så vi kan låne en hel gruppe af servere i den korte periode, der er nødvendig for at gennemføre hver søgning.
Ved at bruge en brute force-metode implementerede vi en hurtig, pålidelig, fleksibel søgning på tværs af et sæt logfiler. Vi håber, at disse ideer er nyttige til dine projekter.
Redigere: Titlen og teksten er ændret fra "Søg med 20 GB pr. sekund" til "Søg med 1 TB pr. sekund" for at afspejle ydeevnestigningerne i løbet af de seneste par år. Denne stigning i hastigheden skyldes primært ændringer i typen og antallet af EC2-servere, vi sætter op i dag for at betjene vores øgede kundebase. Der kommer snart ændringer, som vil give endnu et dramatisk løft i den operationelle effektivitet, og vi kan ikke vente med at dele dem.
Kilde: www.habr.com