TL;DR: För fyra år sedan lämnade jag Google med en idé om ett nytt serverövervakningsverktyg. Tanken var att kombinera vanligtvis isolerade funktioner till en tjänst och logganalys, insamling av mätvärden, och instrumentpaneler. En av principerna är att tjänsten ska vara sann snabb, ger devops en enkel, interaktiv och njutbar upplevelse. Detta kräver bearbetning av multi-gigabyte datamängder på bråkdelar av en sekund samtidigt som budgeten hålls. Befintliga logghanteringsverktyg är ofta långsamma och klumpiga, så vi stod inför en bra utmaning: att smart designa ett verktyg för att ge användarna en ny upplevelse.
Den här artikeln beskriver hur vi på Scalyr löste detta problem genom att tillämpa old school-metoder, en brute force approach, eliminera onödiga lager och undvika komplexa datastrukturer. Du kan tillämpa dessa lektioner på dina egna tekniska problem.
Old School Power
Logganalys börjar vanligtvis med en sökning: hitta alla meddelanden som matchar ett visst mönster. I Scalyr är dessa tiotals eller hundratals gigabyte loggar från många servrar. Moderna tillvägagångssätt involverar som regel konstruktionen av en komplex datastruktur som är optimerad för sökning. Jag har verkligen sett det här på Google, där de är ganska bra på sånt här. Men vi bestämde oss för ett mycket grövre tillvägagångssätt: linjär skanning av stockar. Och det fungerade – vi tillhandahåller ett sökbart gränssnitt som är storleksordningar snabbare än våra konkurrenter (se animation i slutet).
Den viktigaste insikten var att moderna processorer verkligen är mycket snabba vid enkla, okomplicerade operationer. Detta är lätt att missa i komplexa flerskiktssystem som är beroende av I/O-hastighet och nätverksdrift, och sådana system är mycket vanliga idag. Så vi utvecklade en design som minimerar lager och överflödigt skräp. Med flera processorer och servrar parallellt når sökhastigheten 1 TB per sekund.
Viktiga tips från den här artikeln:
- Brute-force-sökning är ett gångbart tillvägagångssätt för att lösa verkliga, storskaliga problem.
- Brute force är en designteknik, inte en arbetsfri lösning. Som vilken teknik som helst är den bättre lämpad för vissa problem än andra och kan implementeras dåligt eller bra.
- Brute force är särskilt bra för att uppnå stabil produktivitet.
- Effektiv användning av brute force kräver optimering av kod och applicering av tillräckliga resurser vid rätt tidpunkt. Det är lämpligt om dina servrar är under tung icke-användarbelastning och användaroperationer förblir en prioritet.
- Prestanda beror på utformningen av hela systemet, inte bara den inre slingalgoritmen.
(Den här artikeln beskriver sökning efter data i minnet. I de flesta fall, när en användare utför en loggsökning, har Scalyr-servrarna redan cachat den. Nästa artikel kommer att diskutera sökning efter uncachade loggar. Samma principer gäller: effektiv kod, brute force med stora beräkningsresurser).
Brute force metod
Traditionellt söks en stor datamängd med hjälp av ett nyckelordsindex. När det tillämpas på serverloggar betyder det att man söker efter varje unikt ord i loggen. För varje ord måste du göra en lista över alla inneslutningar. Detta gör det enkelt att hitta alla meddelanden med detta ord, till exempel 'error', 'firefox' eller "transaction_16851951" - titta bara i indexet.
Jag använde detta tillvägagångssätt på Google och det fungerade bra. Men i Scalyr söker vi loggarna byte för byte.
Varför? Ur en abstrakt algoritmisk synvinkel är nyckelordsindex mycket effektivare än brute force-sökningar. Däremot säljer vi inte algoritmer, vi säljer prestanda. Och prestanda handlar inte bara om algoritmer, utan också om systemteknik. Vi måste ta hänsyn till allt: datavolym, typ av sökning, tillgänglig hårdvara och mjukvarukontext. Vi bestämde oss för att för vårt specifika problem var något som 'grep' bättre lämpat än ett index.
Index är bra, men de har begränsningar. Ett ord är lätt att hitta. Men att söka efter meddelanden med flera ord, som "googlebot" och "404", är mycket svårare. Att söka efter en fras som "uncaught exception" kräver ett mer besvärligt index som inte bara registrerar alla meddelanden med det ordet, utan också den specifika platsen för ordet.
Den verkliga svårigheten kommer när du inte letar efter ord. Låt oss säga att du vill se hur mycket trafik som kommer från bots. Den första tanken är att söka i loggarna efter ordet "bot". Så här hittar du några bots: Googlebot, Bingbot och många andra. Men här är 'bot' inte ett ord, utan en del av det. Om vi söker efter "bot" i indexet hittar vi inga inlägg med ordet "Googlebot". Om du kontrollerar varje ord i indexet och sedan skannar indexet efter sökorden som hittas, kommer sökningen att sakta ner kraftigt. Som ett resultat tillåter vissa loggprogram inte sökningar med delord eller tillåter (i bästa fall) speciell syntax med lägre prestanda. Vi vill undvika detta.
Ett annat problem är skiljetecken. Vill du hitta alla förfrågningar från 50.168.29.7? Vad sägs om att felsöka loggar som innehåller [error]? Prenumerationer hoppar vanligtvis över skiljetecken.
Slutligen, ingenjörer älskar kraftfulla verktyg, och ibland kan ett problem bara lösas med ett reguljärt uttryck. Sökordsindexet är inte särskilt lämpligt för detta.
Dessutom indexen komplex. Varje meddelande måste läggas till i flera sökordslistor. Dessa listor bör alltid hållas i ett lättsökbart format. Frågor med fraser, ordfragment eller reguljära uttryck måste översättas till operationer med flera listor, och resultaten skannas och kombineras för att skapa en resultatuppsättning. I samband med en storskalig tjänst med flera hyresgäster skapar denna komplexitet prestandaproblem som inte är synliga när man analyserar algoritmerna.
Nyckelordsindex tar också upp mycket utrymme och lagring är en stor kostnad i ett logghanteringssystem.
Å andra sidan kan varje sökning förbruka mycket datorkraft. Våra användare uppskattar snabba sökningar efter unika frågor, men sådana frågor görs relativt sällan. För typiska sökfrågor, till exempel för en instrumentpanel, använder vi speciella tekniker (vi kommer att beskriva dem i nästa artikel). Andra förfrågningar är sällsynta nog att du sällan behöver behandla mer än en åt gången. Men det betyder inte att våra servrar inte är upptagna: de är upptagna med arbetet med att ta emot, analysera och komprimera nya meddelanden, utvärdera varningar, komprimera gammal data och så vidare. Vi har alltså ett ganska stort utbud av processorer som kan användas för att utföra frågor.
Brute force fungerar om du har ett brute problem (och mycket kraft)
Brute force fungerar bäst på enkla problem med små interna öglor. Ofta kan man optimera den interna slingan för att köras i mycket höga hastigheter. Om koden är komplex är det mycket svårare att optimera den.
Vår sökkod hade ursprungligen en ganska stor inre slinga. Vi lagrar meddelanden på sidor i 4K; varje sida innehåller några meddelanden (i UTF-8) och metadata för varje meddelande. Metadata är en struktur som kodar längden på värdet, internt meddelande-ID och andra fält. Sökcykeln såg ut så här:
Detta är en förenklad version av den faktiska koden. Men även här är flera objektplaceringar, datakopior och funktionsanrop synliga. JVM är ganska bra på att optimera funktionsanrop och allokera tillfälliga objekt, så den här koden fungerade bättre än vi förtjänade. Under testningen använde kunderna det ganska framgångsrikt. Men så småningom tog vi det till nästa nivå.
(Du kanske frågar varför vi lagrar meddelanden i det här formatet med 4K-sidor, text och metadata, snarare än att arbeta med loggar direkt. Det finns många anledningar som kokar ner till det faktum att Scalyr-motorn internt är mer som en distribuerad databas än en filsystem. Textsökning kombineras ofta med DBMS-liknande filter i marginalerna efter loggparsning. Vi kan samtidigt söka i många tusen loggar på en gång, och enkla textfiler är inte lämpliga för vår transaktionsmässiga, replikerade, distribuerade datahantering).
Till en början verkade det som om sådan kod inte var särskilt lämplig för brute force-optimering. "Riktigt arbete" i String.indexOf() dominerade inte ens CPU-profilen. Det vill säga, enbart optimering av denna metod skulle inte ge någon signifikant effekt.
Det råkar vara så att vi lagrar metadata i början av varje sida, och texten i alla meddelanden i UTF-8 packas i andra änden. Genom att dra nytta av detta skrev vi om slingan för att söka igenom hela sidan på en gång:
Denna version fungerar direkt på vyn raw byte[] och söker igenom alla meddelanden samtidigt över hela 4K-sidan.
Detta är mycket lättare att optimera för brute force-metoden. Den interna sökslingan anropas samtidigt för hela 4K-sidan, snarare än separat på varje inlägg. Det finns ingen kopiering av data, ingen allokering av objekt. Och mer komplexa metadataoperationer anropas bara när resultatet är positivt, och inte på varje meddelande. På så sätt har vi eliminerat massor av overhead, och resten av belastningen är koncentrerad i en liten intern sökslinga, som är väl lämpad för ytterligare optimering.
Vår faktiska sökalgoritm är baserad på . Den liknar Boyer-Moore-algoritmen och hoppar över ungefär längden på söksträngen vid varje steg. Den största skillnaden är att den kontrollerar två byte åt gången för att minimera falska matchningar.
Vår implementering kräver att skapa en 64K uppslagstabell för varje sökning, men det är ingenting jämfört med gigabyte med data vi söker igenom. Den inre slingan bearbetar flera gigabyte per sekund på en enda kärna. I praktiken är den stabila prestandan runt 1,25 GB per sekund på varje kärna, och det finns utrymme för förbättringar. Det är möjligt att eliminera en del av overheaden utanför den inre loopen, och vi planerar att experimentera med en inre loop i C istället för Java.
Vi använder våld
Vi har diskuterat att loggsökning kan implementeras "ungefär", men hur mycket "kraft" har vi? Ganska mycket.
1 år: När den används på rätt sätt är en enda kärna i en modern processor ganska kraftfull i sin egen rätt.
8 kärnor: Vi kör för närvarande på Amazon hi1.4xlarge och i2.4xlarge SSD-servrar, var och en med 8 kärnor (16 trådar). Som nämnts ovan är dessa kärnor vanligtvis upptagna med bakgrundsoperationer. När användaren utför en sökning avbryts bakgrundsoperationerna, vilket frigör alla 8 kärnor för sökning. Sökningen slutförs vanligtvis på en bråkdel av en sekund, varefter bakgrundsarbetet återupptas (strypprogrammet ser till att störtfloden av sökfrågor inte stör viktigt bakgrundsarbete).
16 kärnor: för tillförlitlighet organiserar vi servrar i master/slavgrupper. Varje master har en SSD och en EBS-server under sitt kommando. Om huvudservern kraschar tar SSD-servern omedelbart dess plats. Nästan hela tiden fungerar master och slav bra, så att varje datablock är sökbart på två olika servrar (EBS-slavservern har en svag processor, så det tar vi inte hänsyn till). Vi delar upp uppgiften mellan dem, så att vi har totalt 16 kärnor tillgängliga.
Många kärnor: Inom en snar framtid kommer vi att distribuera data över servrar på ett sådant sätt att de alla deltar i behandlingen av varje icke-trivial begäran. Varje kärna kommer att fungera. [Notera: vi implementerade planen och ökade sökhastigheten till 1 TB/s, se not i slutet av artikeln].
Enkelhet garanterar tillförlitlighet
En annan fördel med brute force-metoden är dess ganska konsekventa prestanda. Vanligtvis är sökning inte särskilt känslig för detaljerna i problemet och datamängden (jag antar att det är därför det kallas "grovt").
Sökordsindex ger ibland otroligt snabba resultat, och andra gånger inte. Låt oss säga att du har 50 GB loggar där termen "customer_5987235982" förekommer exakt tre gånger. En sökning på denna term räknar tre platser direkt från indexet och kommer att slutföras direkt. Men komplexa jokerteckensökningar kan skanna tusentals sökord och ta lång tid.
Å andra sidan utförs brute force-sökningar med mer eller mindre samma hastighet för alla sökfrågor. Att söka efter långa ord är bättre, men även att söka efter ett enstaka tecken går ganska snabbt.
Enkelheten i brute force-metoden gör att dess prestanda är nära sitt teoretiska maximum. Det finns färre alternativ för oväntade disköverbelastningar, låskonflikter, pekarjakt och tusentals andra orsaker till misslyckanden. Jag tittade precis på förfrågningarna från Scalyr-användare förra veckan på vår mest trafikerade server. Det kom 14 000 förfrågningar. Exakt åtta av dem tog mer än en sekund; 99 % slutförda inom 111 millisekunder (om du inte har använt logganalysverktyg, lita på mig: det är snabbt).
Stabil, pålitlig prestanda är viktig för att tjänsten ska vara enkel att använda. Om det släpar med jämna mellanrum kommer användarna att uppfatta det som opålitligt och vara ovilliga att använda det.
Loggsökning i aktion
Här är en kort animation som visar Scalyr-sökning i aktion. Vi har ett demokonto där vi importerar varje event i alla offentliga Github-förråd. I den här demon undersöker jag en veckas data: cirka 600 MB råloggar.
Videon spelades in live, utan speciella förberedelser, på mitt skrivbord (cirka 5000 kilometer från servern). Prestandan du kommer att se beror till stor del på , samt en snabb och pålitlig backend. När det är en paus utan en "laddnings"-indikator är det jag som pausar så att du kan läsa vad jag ska trycka på.
Sammanfattningsvis
När du bearbetar stora mängder data är det viktigt att välja en bra algoritm, men "bra" betyder inte "fancy". Fundera på hur din kod kommer att fungera i praktiken. Den teoretiska analysen av algoritmer utelämnar några faktorer som kan ha stor betydelse i den verkliga världen. Enklare algoritmer är lättare att optimera och mer stabila i kantsituationer.
Tänk också på i vilket sammanhang koden kommer att exekveras. I vårt fall behöver vi tillräckligt kraftfulla servrar för att hantera bakgrundsuppgifter. Användare initierar sökningar relativt sällan, så vi kan låna en hel grupp servrar under den korta period som behövs för att slutföra varje sökning.
Med hjälp av en brute force-metod implementerade vi en snabb, pålitlig, flexibel sökning i en uppsättning loggar. Vi hoppas att dessa idéer är användbara för dina projekt.
Redigera: Titeln och texten har ändrats från "Sök med 20 GB per sekund" till "Sök med 1 TB per sekund" för att återspegla prestandaökningarna under de senaste åren. Denna hastighetsökning beror främst på förändringar i typen och antalet EC2-servrar som vi sätter upp idag för att betjäna vår ökade kundbas. Det kommer snart förändringar som kommer att ge ytterligare en dramatisk ökning av operativ effektivitet, och vi kan inte vänta med att dela dem.
Källa: will.com