TL;DR: Vier jaar geleden verliet ik Google met een idee voor een nieuwe servermonitoringtool. Het idee was om doorgaans geïsoleerde functies te combineren in één dienst en loganalyse, verzameling van statistieken, en dashboards. Eén van de uitgangspunten is dat de dienstverlening echt moet zijn snel, waardoor devops een gemakkelijke, interactieve en plezierige ervaring krijgen. Dit vereist het verwerken van datasets van meerdere gigabytes in fracties van een seconde, terwijl we binnen het budget blijven. Bestaande tools voor logbeheer zijn vaak traag en onhandig, dus we stonden voor een mooie uitdaging: het slim ontwerpen van een tool om gebruikers een nieuwe ervaring te bieden.
Dit artikel beschrijft hoe wij bij Scalyr dit probleem hebben opgelost door ouderwetse methoden toe te passen, een brute force-aanpak, onnodige lagen te elimineren en complexe datastructuren te vermijden. U kunt deze lessen toepassen op uw eigen technische problemen.
Ouderwetse macht
Loganalyse begint meestal met een zoekopdracht: zoek alle berichten die overeenkomen met een bepaald patroon. In Scalyr zijn dit tientallen of honderden gigabytes aan logs van veel servers. Moderne benaderingen omvatten in de regel de constructie van een complexe datastructuur die is geoptimaliseerd voor zoeken. Ik heb dit zeker op Google gezien, waar ze behoorlijk goed zijn in dit soort dingen. Maar we kozen voor een veel grovere aanpak: lineair scannen van logboeken. En het werkte: we bieden een doorzoekbare interface die een orde van grootte sneller is dan die van onze concurrenten (zie animatie aan het einde).
Het belangrijkste inzicht was dat moderne processors inderdaad erg snel zijn in eenvoudige, duidelijke handelingen. Dit kun je gemakkelijk over het hoofd zien in complexe, meerlaagse systemen die afhankelijk zijn van I/O-snelheid en netwerkbewerkingen, en dergelijke systemen zijn tegenwoordig heel gebruikelijk. Daarom hebben we een ontwerp ontwikkeld dat lagen en overtollig vuil minimaliseert. Met meerdere processors en servers parallel bereikt de zoeksnelheid 1 TB per seconde.
Belangrijkste conclusies uit dit artikel:
- Zoeken met brute kracht is een haalbare aanpak voor het oplossen van grootschalige problemen in de echte wereld.
- Brute kracht is een ontwerptechniek, geen werkloze oplossing. Zoals elke techniek is deze voor sommige problemen beter geschikt dan andere, en kan ze slecht of goed worden geïmplementeerd.
- Brute kracht is vooral goed om iets te bereiken stal productiviteit.
- Effectief gebruik van brute kracht vereist het optimaliseren van code en het inzetten van voldoende middelen op het juiste moment. Het is geschikt als uw servers zwaar worden belast door niet-gebruikers en gebruikersactiviteiten een prioriteit blijven.
- De prestaties zijn afhankelijk van het ontwerp van het hele systeem, niet alleen van het binnenste lusalgoritme.
(Dit artikel beschrijft het zoeken naar gegevens in het geheugen. Wanneer een gebruiker een logzoekopdracht uitvoert, hebben de Scalyr-servers deze in de meeste gevallen al in de cache opgeslagen. In het volgende artikel wordt het zoeken naar niet-gecachte logbestanden besproken. Dezelfde principes zijn van toepassing: efficiënte code, brute kracht met grote rekencapaciteit).
Brute force-methode
Traditioneel wordt een grote dataset doorzocht met behulp van een trefwoordindex. Wanneer dit wordt toegepast op serverlogboeken, betekent dit dat er moet worden gezocht naar elk uniek woord in het logbestand. Voor elk woord moet u een lijst maken van alle insluitsels. Dit maakt het gemakkelijk om alle berichten met dit woord te vinden, bijvoorbeeld 'error', 'firefox' of 'transaction_16851951' - kijk gewoon in de index.
Ik gebruikte deze aanpak bij Google en het werkte goed. Maar in Scalyr doorzoeken we de logs byte voor byte.
Waarom? Vanuit abstract algoritmisch oogpunt zijn trefwoordindexen veel efficiënter dan zoekopdrachten met brute kracht. Wij verkopen echter geen algoritmen, wij verkopen prestaties. En prestatie gaat niet alleen over algoritmen, maar ook over systeemtechniek. We moeten met alles rekening houden: de hoeveelheid gegevens, het type zoekopdracht, de beschikbare hardware- en softwarecontext. We besloten dat voor ons specifieke probleem zoiets als 'grep' beter geschikt was dan een index.
Indexen zijn geweldig, maar ze hebben beperkingen. Eén woord is gemakkelijk te vinden. Maar zoeken naar berichten met meerdere woorden, zoals 'googlebot' en '404', is veel lastiger. Zoeken naar een zinsnede als 'uncaught exception' vereist een omslachtiger index die niet alleen alle berichten met dat woord registreert, maar ook de specifieke locatie van het woord.
De echte moeilijkheid ontstaat als je niet naar woorden zoekt. Stel dat u wilt zien hoeveel verkeer er van bots komt. De eerste gedachte is om in de logs te zoeken naar het woord 'bot'. Zo vind je enkele bots: Googlebot, Bingbot en vele anderen. Maar hier is 'bot' geen woord, maar een onderdeel ervan. Als we in de index zoeken naar 'bot', vinden we geen berichten met het woord 'Googlebot'. Als u elk woord in de index controleert en vervolgens de index scant op de gevonden trefwoorden, zal het zoeken aanzienlijk vertragen. Als gevolg hiervan staan sommige logprogramma's geen zoekopdrachten naar gedeelten van woorden toe, of (in het beste geval) een speciale syntaxis met lagere prestaties. Wij willen dit vermijden.
Een ander probleem is de interpunctie. Wilt u alle aanvragen vinden van 50.168.29.7? Hoe zit het met foutopsporingslogboeken die [error]? Subscripten slaan meestal interpunctie over.
Ten slotte houden ingenieurs van krachtige tools, en soms kan een probleem alleen worden opgelost met een reguliere expressie. De zoekwoordenindex is hiervoor niet erg geschikt.
Daarnaast de indexen complex. Elk bericht moet aan verschillende trefwoordenlijsten worden toegevoegd. Deze lijsten moeten te allen tijde in een gemakkelijk doorzoekbaar formaat worden bewaard. Zoekopdrachten met woordgroepen, woordfragmenten of reguliere expressies moeten worden vertaald in bewerkingen met meerdere lijsten, en de resultaten moeten worden gescand en gecombineerd om een resultatenset te produceren. In de context van een grootschalige, multi-tenant dienst zorgt deze complexiteit voor prestatieproblemen die niet zichtbaar zijn bij het analyseren van de algoritmen.
Trefwoordindexen nemen ook veel ruimte in beslag, en opslag is een grote kostenpost in een logbeheersysteem.
Aan de andere kant kan elke zoekopdracht veel rekenkracht verbruiken. Onze gebruikers waarderen snelle zoekopdrachten naar unieke zoekopdrachten, maar dergelijke zoekopdrachten worden relatief zelden uitgevoerd. Voor typische zoekopdrachten, bijvoorbeeld voor een dashboard, gebruiken we speciale technieken (die beschrijven we in het volgende artikel). Andere verzoeken komen zo weinig voor dat u er zelden meer dan één tegelijk hoeft te verwerken. Maar dit betekent niet dat onze servers niet druk zijn: ze zijn bezig met het ontvangen, analyseren en comprimeren van nieuwe berichten, het evalueren van waarschuwingen, het comprimeren van oude gegevens, enzovoort. We hebben dus een vrij aanzienlijk aanbod aan processors die kunnen worden gebruikt om zoekopdrachten uit te voeren.
Brute force werkt als je een brute probleem hebt (en veel kracht)
Brute kracht werkt het beste bij eenvoudige problemen met kleine interne lussen. Vaak kunt u de interne lus optimaliseren zodat deze op zeer hoge snelheden werkt. Als de code complex is, is het veel moeilijker om deze te optimaliseren.
Onze zoekcode had oorspronkelijk een vrij grote binnenlus. We slaan berichten op pagina's op in 4K; elke pagina bevat enkele berichten (in UTF-8) en metadata voor elk bericht. Metagegevens zijn een structuur die de lengte van de waarde, de interne bericht-ID en andere velden codeert. De zoekcyclus zag er als volgt uit:
Dit is een vereenvoudigde versie van de daadwerkelijke code. Maar zelfs hier zijn meerdere objectplaatsingen, gegevenskopieën en functieaanroepen zichtbaar. De JVM is redelijk goed in het optimaliseren van functieaanroepen en het toewijzen van kortstondige objecten, dus deze code werkte beter dan we verdienden. Tijdens het testen gebruikten klanten het met succes. Maar uiteindelijk hebben we het naar een hoger niveau getild.
(Je kunt je afvragen waarom we berichten in dit formaat opslaan met 4K-pagina's, tekst en metadata, in plaats van rechtstreeks met logs te werken. Er zijn veel redenen, die neerkomen op het feit dat de Scalyr-engine intern meer op een gedistribueerde database lijkt dan op een bestandssysteem. Zoeken naar tekst wordt vaak gecombineerd met DBMS-achtige filters in de marges na het parseren van logs. We kunnen tegelijkertijd vele duizenden logs tegelijk doorzoeken, en eenvoudige tekstbestanden zijn niet geschikt voor ons transactioneel, gerepliceerd, gedistribueerd gegevensbeheer).
Aanvankelijk leek het erop dat dergelijke code niet erg geschikt was voor brute force-optimalisatie. "Echt werk" in String.indexOf() domineerde niet eens het CPU-profiel. Dat wil zeggen dat het optimaliseren van deze methode alleen geen significant effect zou opleveren.
Het gebeurt zo dat we metadata aan het begin van elke pagina opslaan, en de tekst van alle berichten in UTF-8 aan het andere uiteinde wordt ingepakt. We hebben hiervan geprofiteerd en de lus herschreven, zodat de hele pagina in één keer kan worden doorzocht:
Deze versie werkt rechtstreeks op de weergave raw byte[] en doorzoekt alle berichten in één keer over de hele 4K-pagina.
Dit is veel gemakkelijker te optimaliseren voor de brute force-methode. De interne zoeklus wordt gelijktijdig voor de gehele 4K-pagina opgeroepen, in plaats van afzonderlijk voor elk bericht. Er vindt geen kopiëren van gegevens plaats, geen toewijzing van objecten. En complexere metadatabewerkingen worden alleen aangeroepen als het resultaat positief is, en niet voor elk bericht. Op deze manier hebben we een hoop overhead geëlimineerd en is de rest van de belasting geconcentreerd in een kleine interne zoeklus, die zeer geschikt is voor verdere optimalisatie.
Ons daadwerkelijke zoekalgoritme is gebaseerd op . Het is vergelijkbaar met het Boyer-Moore-algoritme, waarbij bij elke stap ongeveer de lengte van de zoekreeks wordt overgeslagen. Het belangrijkste verschil is dat het twee bytes tegelijk controleert om valse overeenkomsten te minimaliseren.
Onze implementatie vereist het maken van een opzoektabel van 64 KB voor elke zoekopdracht, maar dat is niets vergeleken met de gigabytes aan gegevens die we doorzoeken. De binnenste lus verwerkt meerdere gigabytes per seconde op één kern. In de praktijk bedragen de stabiele prestaties ongeveer 1,25 GB per seconde op elke core, en er is ruimte voor verbetering. Het is mogelijk om een deel van de overhead buiten de binnenste lus te elimineren, en we zijn van plan te experimenteren met een binnenste lus in C in plaats van Java.
Wij gebruiken geweld
We hebben besproken dat zoeken in logboeken "grofweg" kan worden geïmplementeerd, maar hoeveel "macht" hebben we? Best veel.
1 uur: Bij correct gebruik is een enkele kern van een moderne processor op zichzelf behoorlijk krachtig.
8 kernen: We draaien momenteel op Amazon hi1.4xlarge en i2.4xlarge SSD-servers, elk met 8 cores (16 threads). Zoals hierboven vermeld, zijn deze kernen meestal bezig met achtergrondbewerkingen. Wanneer de gebruiker een zoekopdracht uitvoert, worden achtergrondbewerkingen opgeschort, waardoor alle 8 kernen vrijkomen voor zoeken. Het zoeken is doorgaans binnen een fractie van een seconde voltooid, waarna het achtergrondwerk wordt hervat (het throttling-programma zorgt ervoor dat het spervuur van zoekopdrachten het belangrijke achtergrondwerk niet verstoort).
16 kernen: voor betrouwbaarheid organiseren we servers in master/slave-groepen. Elke master heeft één SSD en één EBS-server onder zijn bevel. Als de hoofdserver crasht, neemt de SSD-server onmiddellijk zijn plaats in. Bijna altijd werken master en slave prima, zodat elk datablok op twee verschillende servers doorzoekbaar is (de EBS-slaveserver heeft een zwakke processor, dus daar houden we geen rekening mee). We verdelen de taak onderling, zodat we in totaal 16 kernen ter beschikking hebben.
Veel kernen: In de nabije toekomst zullen we gegevens zodanig over servers verdelen dat ze allemaal deelnemen aan de verwerking van elk niet-triviaal verzoek. Elke kern zal werken. [Opmerking: we hebben het plan geïmplementeerd en de zoeksnelheid verhoogd naar 1 TB/s, zie de opmerking aan het einde van het artikel].
Eenvoud zorgt voor betrouwbaarheid
Een ander voordeel van de brute force-methode zijn de redelijk consistente prestaties. Meestal is zoeken niet erg gevoelig voor de details van het probleem en de dataset (ik denk dat het daarom "grof" wordt genoemd).
De trefwoordindex levert soms ongelooflijk snelle resultaten op, en andere keren niet. Stel dat u 50 GB aan logboeken heeft waarin de term 'klant_5987235982' precies drie keer voorkomt. Een zoekopdracht naar deze term telt drie locaties rechtstreeks uit de index en wordt onmiddellijk voltooid. Maar bij complexe zoekopdrachten met jokertekens kunnen duizenden trefwoorden worden gescand, wat veel tijd in beslag neemt.
Aan de andere kant presteren zoekopdrachten met brute kracht min of meer met dezelfde snelheid voor elke zoekopdracht. Zoeken naar lange woorden is beter, maar zelfs zoeken naar een enkel teken gaat behoorlijk snel.
De eenvoud van de brute force-methode betekent dat de prestaties dicht bij het theoretische maximum liggen. Er zijn minder opties voor onverwachte schijfoverbelasting, vergrendelingsconflicten, pointer-chaing en duizenden andere redenen voor mislukking. Ik heb zojuist gekeken naar de verzoeken van Scalyr-gebruikers vorige week op onze drukste server. Er waren 14 aanvragen. Precies acht daarvan hadden meer dan een seconde nodig; 000% voltooid binnen 99 milliseconden (als je geen loganalysetools hebt gebruikt, geloof me dan: het is snel).
Stabiele, betrouwbare prestaties zijn belangrijk voor het gebruiksgemak van de dienst. Als het periodiek achterblijft, zullen gebruikers het als onbetrouwbaar beschouwen en terughoudend zijn om het te gebruiken.
Zoeken in logboeken in actie
Hier is een korte animatie die de Scalyr-zoekopdracht in actie laat zien. We hebben een demo-account waarmee we elk evenement in elke openbare Github-repository importeren. In deze demo onderzoek ik de gegevens van een week: ongeveer 600 MB aan onbewerkte logbestanden.
De video werd zonder speciale voorbereiding live opgenomen op mijn desktop (ongeveer 5000 kilometer van de server). De prestaties die je ziet zijn grotendeels te danken aan , evenals een snelle en betrouwbare backend. Telkens wanneer er een pauze is zonder een 'laad'-indicator, pauzeer ik, zodat je kunt lezen waar ik op ga drukken.
Concluderend
Bij het verwerken van grote hoeveelheden data is het belangrijk om een goed algoritme te kiezen, maar ‘goed’ betekent niet ‘luxueus’. Bedenk hoe uw code in de praktijk zal werken. De theoretische analyse van algoritmen laat enkele factoren buiten beschouwing die in de echte wereld van groot belang kunnen zijn. Eenvoudigere algoritmen zijn gemakkelijker te optimaliseren en stabieler in randsituaties.
Denk ook na over de context waarin de code wordt uitgevoerd. In ons geval hebben we voldoende krachtige servers nodig om achtergrondtaken te beheren. Gebruikers starten relatief zelden zoekopdrachten, dus we kunnen een hele groep servers lenen voor de korte periode die nodig is om elke zoekopdracht te voltooien.
Met behulp van een brute force-methode hebben we een snelle, betrouwbare en flexibele zoekactie in een reeks logboeken geïmplementeerd. We hopen dat deze ideeën nuttig zijn voor uw projecten.
Bewerking: De titel en tekst zijn gewijzigd van 'Zoeken met 20 GB per seconde' in 'Zoeken met 1 TB per seconde' om de prestatieverbeteringen van de afgelopen jaren weer te geven. Deze snelheidsverhoging is voornamelijk te danken aan veranderingen in het type en aantal EC2-servers die we vandaag opzetten om ons grotere klantenbestand te bedienen. Er komen binnenkort veranderingen aan die een nieuwe dramatische impuls zullen geven aan de operationele efficiëntie, en we kunnen niet wachten om deze te delen.
Bron: www.habr.com