TL; DR: Vor vier Jahren verließ ich Google mit der Idee eines neuen Tools zur Überwachung von Servern. Die Idee war, die normalerweise isolierten Funktionen des Sammelns und Analysierens von Protokollen, Sammeln von Metriken, Warnungen und eines Dashboards in einem Dienst zu kombinieren. Eines der Prinzipien - der Service sollte sehr schnell sein und den Entwicklern einen einfachen, interaktiven und unterhaltsamen Job bieten. Dies erfordert die Verarbeitung von Datensätzen mit mehreren Gigabyte in Sekundenbruchteilen, ohne das Budget zu überschreiten. Bestehende Tools für die Arbeit mit Protokollen sind oft langsam und ungeschickt, daher standen wir vor einer guten Aufgabe: ein Tool richtig zu entwickeln, um den Benutzern neue Empfindungen bei der Arbeit zu vermitteln.

Dieser Artikel beschreibt, wie wir bei Scalyr dieses Problem gelöst haben, indem wir die Methoden der alten Schule, den Brute-Force-Ansatz, die Beseitigung redundanter Schichten und die Vermeidung komplexer Datenstrukturen angewendet haben. Sie können diese Lektionen auf Ihre eigenen technischen Aufgaben anwenden.

Die Stärke der alten Schule

Die Protokollanalyse beginnt normalerweise mit einer Suche: Finden Sie alle Nachrichten, die einer bestimmten Vorlage entsprechen. In Scalyr sind dies Dutzende oder Hunderte von Gigabyte an Protokollen von vielen Servern. Moderne Ansätze beinhalten in der Regel den Aufbau einer komplexen Datenstruktur, die für die Suche optimiert ist. Natürlich habe ich das bei Google gesehen, wo sie in solchen Dingen ziemlich gut sind. Wir haben uns jedoch für einen viel gröberen Ansatz entschieden: das lineare Scannen von Protokollen. Und es hat funktioniert - wir bieten eine Schnittstelle mit einer um eine Größenordnung schnelleren Suche als die der Konkurrenz (siehe Animation am Ende).

Die wichtigste Erkenntnis ist, dass moderne Prozessoren in einfachen und unkomplizierten Vorgängen sehr schnell sind. Dies wird in komplexen, mehrschichtigen Systemen, die von der E / A-Geschwindigkeit und dem Netzwerkbetrieb abhängen, leicht übersehen, und solche Systeme sind heutzutage sehr verbreitet. Aus diesem Grund haben wir ein Design entwickelt, das die Anzahl der Schichten und den überschüssigen Müll minimiert. Bei mehreren parallelen Prozessoren und Servern erreicht die Suchgeschwindigkeit 1 TB pro Sekunde.

Wichtigste Ergebnisse aus diesem Artikel:

• Grobe Suche ist ein praktikabler Ansatz zur Lösung realer, großer Probleme.
  
• Brute Force ist eine Designtechnik, keine Befreiung von der Arbeit. Wie jede Technik ist sie für einige Probleme besser geeignet als für andere und kann schlecht oder gut implementiert werden.
  
• Brute Force ist besonders gut für eine stabile Leistung.
  
• Der effektive Einsatz von Brute Force erfordert eine Codeoptimierung und den rechtzeitigen Einsatz ausreichender Ressourcen. Dies ist geeignet, wenn Ihre Server einer hohen Arbeitsbelastung durch Nichtbenutzer ausgesetzt sind und Benutzervorgänge weiterhin Priorität haben.
  
• Die Leistung hängt vom Design des gesamten Systems ab und nicht nur vom internen Schleifenalgorithmus.

(In diesem Artikel wird beschrieben, wie nach Daten im Speicher gesucht wird. In den meisten Fällen, wenn ein Benutzer nach Protokollen sucht, haben Scalyr-Server diese bereits zwischengespeichert. Im nächsten Artikel wird die Suche nach nicht zwischengespeicherten Protokollen erläutert. Es gelten dieselben Prinzipien: Effizienter Code, Brute-Force-Methode mit großem Rechenaufwand Ressourcen).

Brute-Force-Methode

Traditionell wird eine Suche in einem großen Datensatz mithilfe eines Schlüsselwortindex durchgeführt. In Bezug auf Serverprotokolle bedeutet dies, nach jedem eindeutigen Wort im Protokoll zu suchen. Für jedes Wort müssen Sie eine Liste aller Einschlüsse erstellen. Dies macht es einfach, alle Nachrichten mit diesem Wort zu finden, z. B. "Fehler", "Firefox" oder "Transaktion_16851951" - schauen Sie einfach in den Index.

Ich habe diesen Ansatz bei Google verwendet und er hat gut funktioniert. In Scalyr suchen wir in den Protokollen nach Byte für Byte.

Warum? Aus abstrakter algorithmischer Sicht sind Keyword-Indizes viel effektiver als eine grobe Suche. Wir verkaufen jedoch keine Algorithmen, sondern Leistung. Und Leistung ist nicht nur Algorithmen, sondern auch Systemtechnik. Wir müssen alles berücksichtigen: die Datenmenge, die Art der Suche, die verfügbare Hardware und den Softwarekontext. Wir haben entschieden, dass für unser spezielles Problem eine Option wie 'grep' besser ist als ein Index.

Indizes sind großartig, haben aber Einschränkungen. Ein Wort ist leicht zu finden. Das Auffinden von Nachrichten mit wenigen Wörtern wie "googlebot" und "404" ist jedoch bereits viel komplizierter. Die Suche nach Phrasen wie "nicht erfasste Ausnahme" erfordert einen umständlicheren Index, der nicht nur alle Nachrichten mit diesem Wort, sondern auch die spezifische Position des Wortes aufzeichnet.

Die eigentliche Schwierigkeit entsteht, wenn Sie nicht nach Worten suchen. Angenommen, Sie möchten sehen, wie viel Verkehr von Bots kommt. Der erste Gedanke ist, die Protokolle nach dem Wort "Bot" zu durchsuchen. So finden Sie einige Bots: Googlebot, Bingbot und viele andere. Aber hier ist 'Bot' kein Wort, sondern ein Teil davon. Wenn wir im Index nach "bot" suchen, finden wir keine Nachrichten mit dem Wort "Googlebot". Wenn Sie jedes Wort im Index überprüfen und dann den Index nach den gefundenen Schlüsselwörtern durchsuchen, wird die Suche erheblich verlangsamt. Infolgedessen erlauben einige Programme zum Arbeiten mit Protokollen nicht die Suche in Teilen eines Wortes oder (bestenfalls) die Verwendung einer speziellen Syntax mit geringerer Leistung. Das wollen wir vermeiden.

Ein weiteres Problem ist die Zeichensetzung. 50.168.29.7 Sie alle Anfragen von 50.168.29.7 ? Was ist mit dem Debuggen von Protokollen, die [error] ? Indizes überspringen normalerweise die Interpunktion.

Schließlich lieben Ingenieure leistungsstarke Werkzeuge, und manchmal kann ein Problem nur mit einem regulären Ausdruck gelöst werden. Der Keyword-Index ist dafür nicht sehr geeignet.

Darüber hinaus sind Indizes komplex . Jede Nachricht muss mehreren Keyword-Listen hinzugefügt werden. Diese Listen sollten immer in einem suchfreundlichen Format aufbewahrt werden. Abfragen mit Phrasen, Wortfragmenten oder regulären Ausdrücken müssen in Operationen mit mehreren Listen übersetzt und die Ergebnisse gescannt und kombiniert werden, um eine Ergebnismenge zu erhalten. Im Kontext eines umfangreichen Mehrbenutzerdienstes führt diese Komplexität zu Leistungsproblemen, die bei der Analyse der Algorithmen nicht sichtbar sind.

Schlüsselwortindizes nehmen ebenfalls viel Platz ein, und Speicher ist das Hauptkostenelement im Protokollverwaltungssystem.

Andererseits kann für jede Suche viel Rechenleistung aufgewendet werden. Unsere Benutzer schätzen die schnelle Suche nach eindeutigen Abfragen, aber solche Abfragen sind relativ selten. Für typische Suchanfragen, zum Beispiel für das Dashboard, verwenden wir spezielle Techniken (wir werden sie im nächsten Artikel beschreiben). Andere Abfragen sind recht selten, sodass Sie selten mehr als eine Abfrage gleichzeitig verarbeiten müssen. Dies bedeutet jedoch nicht, dass unsere Server nicht ausgelastet sind: Sie sind damit beschäftigt, neue Nachrichten zu empfangen, zu analysieren und zu komprimieren, Warnungen auszuwerten, alte Daten zu komprimieren usw. Somit verfügen wir über ein ziemlich umfangreiches Angebot an Prozessoren, mit denen Anforderungen erfüllt werden können.

Brute Force funktioniert, wenn Sie ein Brute Force-Problem haben (und viel Gewalt).

Brute Force eignet sich am besten für einfache Aufgaben mit kleinen internen Schleifen. Oft können Sie die innere Schleife optimieren, um mit sehr hohen Geschwindigkeiten zu arbeiten. Wenn der Code komplex ist, ist es viel schwieriger, ihn zu optimieren.

Anfangs hatte unser Suchcode eine ziemlich große innere Schleife. Wir speichern Nachrichten auf 4K-Seiten. Jede Seite enthält einige Nachrichten (in UTF-8) und Metadaten für jede Nachricht. Metadaten sind eine Struktur, in der die Länge des Werts, die interne Nachrichten-ID und andere Felder codiert sind. Die Suchschleife sah folgendermaßen aus:



Dies ist eine vereinfachte Option im Vergleich zum tatsächlichen Code. Aber auch hier sehen Sie mehrere Objektplatzierungen, Datenkopien und Funktionsaufrufe. Die JVM optimiert Funktionsaufrufe ziemlich gut und weist kurzlebige Objekte zu, sodass dieser Code besser funktioniert hat, als wir es verdient haben. Während des Tests haben Clients es ziemlich erfolgreich verwendet. Aber am Ende sind wir auf eine neue Ebene gegangen.

(Sie fragen sich möglicherweise, warum wir Nachrichten in diesem Format mit 4K-Seiten, Text und Metadaten speichern, anstatt direkt mit den Protokollen zu arbeiten. Es gibt viele Gründe, warum die interne Scalyr-Engine eher einer verteilten Datenbank ähnelt als Dateisystem Die Textsuche wird häufig mit DBMS-Stilfiltern in den Feldern nach der Protokollanalyse kombiniert. Wir können viele tausend Protokolle gleichzeitig durchsuchen, und einfache Textdateien eignen sich nicht für unsere transaktionale, replizierte und verteilte Transaktionssteuerung Daten).

Anfangs schien ein solcher Code für die Optimierung nach der Brute-Force-Methode nicht sehr geeignet zu sein. Der „echte Job“ in String.indexOf() dominierte nicht einmal das CPU-Profil. Das heißt, eine Optimierung nur dieser Methode würde keinen signifikanten Effekt bringen.

So kam es, dass wir Metadaten am Anfang jeder Seite speichern und der Text aller Nachrichten in UTF-8 am anderen Ende gepackt wird. Aus diesem Grund haben wir die Suchschleife auf der gesamten Seite auf einmal neu geschrieben:



Diese Version arbeitet direkt mit der raw byte[] Ansicht raw byte[] und sucht auf der gesamten 4K-Seite gleichzeitig nach allen Nachrichten.

Dies ist viel einfacher für Brute Force zu optimieren. Der interne Suchzyklus wird gleichzeitig für die gesamte 4K-Seite und nicht für jede Nachricht separat aufgerufen. Es gibt kein Kopieren von Daten, keine Auswahl von Objekten. Und komplexere Operationen mit Metadaten werden nur mit einem positiven Ergebnis und nicht für jede Nachricht aufgerufen. Auf diese Weise haben wir eine Menge Overhead eliminiert, und der Rest der Last konzentriert sich auf einen kleinen internen Suchzyklus, der für die weitere Optimierung gut geeignet ist.

Unser eigentlicher Suchalgorithmus basiert auf der großartigen Idee von Leonid Volnitsky . Es ähnelt dem Boyer-Moore-Algorithmus, bei dem bei jedem Schritt die Länge der Suchzeichenfolge übersprungen wird. Der Hauptunterschied besteht darin, dass zwei Bytes gleichzeitig überprüft werden, um falsche Übereinstimmungen zu minimieren.

Unsere Implementierung erfordert das Erstellen einer 64K-Nachschlagetabelle für jede Suche. Dies ist jedoch Unsinn im Vergleich zu den Gigabyte an Daten, nach denen wir suchen. Die innere Schleife verarbeitet mehrere Gigabyte pro Sekunde auf einem einzelnen Kern. In der Praxis liegt die stabile Leistung auf jedem Kern bei etwa 1,25 GB pro Sekunde, und es besteht Verbesserungspotenzial. Sie können einen Teil des Overheads außerhalb der inneren Schleife eliminieren, und wir planen, mit der inneren Schleife in C anstelle von Java zu experimentieren.

Kraft anwenden

Wir haben diskutiert, dass Protokollsuchen "grob" implementiert werden können, aber wie viel "Leistung" haben wir? Viel.

1 Kern : Bei korrekter Verwendung ist ein Kern eines modernen Prozessors an sich sehr leistungsfähig.

8 Kerne : Wir arbeiten derzeit an Amazon hi1.4xlarge- und i2.4xlarge-SSD-Servern mit jeweils 8 Kernen (16 Threads). Wie oben erwähnt, sind diese Kernel normalerweise mit Hintergrundoperationen beschäftigt. Wenn der Benutzer eine Suche durchführt, werden die Hintergrundvorgänge angehalten, wodurch alle 8 Kerne für die Suche freigegeben werden. Die Suche wird normalerweise in Sekundenbruchteilen abgeschlossen, danach wird die Hintergrundarbeit fortgesetzt (das Controller-Programm stellt sicher, dass eine Flut von Suchanfragen wichtige Hintergrundarbeiten nicht beeinträchtigt).

16 Kerne : Aus Gründen der Zuverlässigkeit organisieren wir Server in Master / Slave-Gruppen. Jeder Master hat einen SSD-Server und einen untergeordneten EBS. Wenn der Hauptserver abstürzt, tritt der Server auf der SSD sofort an seine Stelle. Fast immer funktionieren Master und Slave einwandfrei, sodass jeder Datenblock auf zwei verschiedenen Servern durchsucht werden kann (der Slave-EBS-Server verfügt über einen schwachen Prozessor, daher wird dies nicht berücksichtigt). Wir teilen die Aufgabe zwischen ihnen auf, so dass insgesamt 16 Kerne zur Verfügung stehen.

Viele Kerne : In naher Zukunft werden wir die Daten auf die Server verteilen, damit alle an der Verarbeitung jeder nicht trivialen Anfrage teilnehmen. Jeder Kern wird funktionieren. [Hinweis: Wir haben den Plan implementiert und die Suchgeschwindigkeit auf 1 TB / s erhöht, siehe Hinweis am Ende des Artikels ].

Einfachheit sorgt für Zuverlässigkeit

Ein weiterer Vorteil der Brute Force ist ihre relativ stabile Leistung. In der Regel reagiert die Suche nicht zu empfindlich auf die Details der Aufgabe und des Datensatzes (ich denke, deshalb wird sie als "unhöflich" bezeichnet).

Der Keyword-Index führt manchmal zu unglaublich schnellen Ergebnissen, in anderen Fällen jedoch nicht. Angenommen, Sie haben 50 GB Protokolle, in denen der Begriff "customer_5987235982" genau dreimal vorkommt. Eine Suche nach diesem Begriff zählt drei Stellen direkt aus dem Index und endet sofort. Eine komplexe Platzhaltersuche kann jedoch Tausende von Schlüsselwörtern scannen und viel Zeit in Anspruch nehmen.

Andererseits werden Brute-Force-Suchen nach Abfragen mit mehr oder weniger derselben Geschwindigkeit durchgeführt. Die Suche nach langen Wörtern ist besser, aber selbst die Suche nach einem einzelnen Zeichen ist schnell genug.

Die Einfachheit der Brute-Force-Methode bedeutet, dass ihre Produktivität nahe am theoretischen Maximum liegt. Es gibt weniger Optionen für unerwartete Festplattenüberlastung, Sperrkonflikte, Zeigerjagden und Tausende anderer Gründe für Fehler. Ich habe mir gerade die Anfragen angesehen, die Scalyr-Benutzer letzte Woche auf unserem am stärksten frequentierten Server gestellt haben. Es gab 14.000 Anfragen. Genau acht von ihnen brauchten mehr als eine Sekunde; 99% wurden innerhalb von 111 Millisekunden ausgeführt (wenn Sie die Protokollanalysetools nicht verwendet haben, glauben Sie mir: Dies ist schnell ).

Eine stabile, zuverlässige Leistung ist wichtig für die Benutzerfreundlichkeit des Dienstes. Wenn es regelmäßig langsamer wird, wird es von Benutzern als unzuverlässig empfunden und es wird nur ungern verwendet.

Protokollsuche in Aktion

Hier ist eine kleine Animation, die zeigt, wie Scalyr in Aktion sucht. Wir haben ein Demo-Konto, in das wir jedes Ereignis in jedes öffentliche Github-Repository importieren. In dieser Demo studiere ich die Daten für die Woche: ungefähr 600 MB Rohprotokolle.

Das Video wurde ohne besondere Vorbereitung live auf meinem Desktop aufgezeichnet (ca. 5000 Kilometer vom Server entfernt). Die Leistung, die Sie sehen werden, ist hauptsächlich auf die Optimierung des Webclients sowie auf das schnelle und zuverlässige Backend zurückzuführen. Immer wenn es eine Pause ohne die Anzeige "Laden" gibt, pausiere ich sie, damit Sie lesen können, auf was ich klicken werde.

Abschließend

Bei der Verarbeitung großer Datenmengen ist es wichtig, einen guten Algorithmus zu wählen, aber „gut“ bedeutet nicht „ausgefallen“. Überlegen Sie, wie Ihr Code in der Praxis funktioniert. Einige Faktoren, die in der realen Welt von großer Bedeutung sein können, fallen aus der theoretischen Analyse von Algorithmen heraus. Einfachere Algorithmen sind einfacher zu optimieren und in Grenzsituationen stabiler.

Denken Sie auch an den Kontext, in dem der Code ausgeführt wird. In unserem Fall benötigen wir ausreichend leistungsfähige Server, um Hintergrundaufgaben zu verwalten. Benutzer initiieren relativ selten eine Suche, sodass wir eine ganze Gruppe von Servern für den kurzen Zeitraum ausleihen können, der für die Durchführung jeder Suche erforderlich ist.

Mit Brute Force haben wir eine schnelle, zuverlässige und flexible Suche in einer Reihe von Protokollen implementiert. Wir hoffen, dass diese Ideen für Ihre Projekte nützlich sind.

Bearbeiten: Titel und Text wurden von "Suche mit 20 GB pro Sekunde" in "Suche mit 1 TB pro Sekunde" geändert, um die Leistungssteigerung in den letzten Jahren widerzuspiegeln. Diese Geschwindigkeitssteigerung ist hauptsächlich auf eine Änderung des Typs und der Anzahl der EC2-Server zurückzuführen, die wir heute erhöhen, um den erweiterten Kundenstamm zu bedienen. In naher Zukunft werden Änderungen erwartet, die zu einer weiteren deutlichen Steigerung der Arbeitseffizienz führen werden, und wir freuen uns auf die Gelegenheit, darüber zu berichten.