TL;DR: Vor vier Jahren verließ ich Google mit einer Idee für ein neues Serverüberwachungstool. Die Idee war, normalerweise isolierte Funktionen in einem Dienst zu vereinen Sammlung und Protokollanalyse, Metrikerfassung, Warnungen und Dashboards. Einer der Grundsätze ist, dass der Dienst wahr sein muss schnellund bietet Entwicklern ein einfaches, interaktives und unterhaltsames Erlebnis. Dies erfordert die Verarbeitung von Multi-Gigabyte-Datensätzen in Sekundenbruchteilen und unter Einhaltung des Budgets. Bestehende Protokollverwaltungstools sind oft langsam und umständlich, daher standen wir vor einer großen Herausforderung: ein Tool intelligent zu entwerfen, um Benutzern ein neues Erlebnis zu bieten.

In diesem Artikel wird beschrieben, wie wir bei Scalyr dieses Problem gelöst haben, indem wir Methoden der alten Schule, einen Brute-Force-Ansatz, die Eliminierung unnötiger Ebenen und die Vermeidung komplexer Datenstrukturen angewendet haben. Sie können diese Lektionen auf Ihre eigenen technischen Probleme anwenden.

Old-School-Power

Die Protokollanalyse beginnt normalerweise mit einer Suche: Finden Sie alle Nachrichten, die einem bestimmten Muster entsprechen. In Scalyr sind dies Dutzende oder Hunderte Gigabyte an Protokollen von vielen Servern. Moderne Ansätze beinhalten in der Regel den Aufbau einer komplexen, für die Suche optimierten Datenstruktur. Ich habe das auf jeden Fall 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 durchsuchbare Schnittstelle, die um Größenordnungen schneller ist als unsere Konkurrenten (siehe Animation am Ende).

Die wichtigste Erkenntnis war, dass moderne Prozessoren bei einfachen, unkomplizierten Vorgängen tatsächlich sehr schnell sind. Dies ist in komplexen, mehrschichtigen Systemen, die auf E/A-Geschwindigkeit und Netzwerkbetrieb angewiesen sind, leicht zu übersehen, und solche Systeme sind heutzutage weit verbreitet. Deshalb haben wir ein Design entwickelt, das Schichten und überschüssigen Schmutz minimiert. Bei der Parallelschaltung mehrerer Prozessoren und Server erreicht die Suchgeschwindigkeit 1 TB pro Sekunde.

Wichtigste Erkenntnisse aus diesem Artikel:

• Brute-Force-Suche ist ein praktikabler Ansatz zur Lösung realer, groß angelegter Probleme.
• Brute Force ist eine Designtechnik, keine arbeitslose Lösung. Wie jede Technik ist sie für einige Probleme besser geeignet als für andere und kann schlecht oder gut implementiert werden.
• Brutale Gewalt lässt sich besonders gut erreichen stabil Produktivität.
• Der effektive Einsatz von Brute-Force erfordert die Optimierung des Codes und den Einsatz ausreichender Ressourcen zum richtigen Zeitpunkt. Es ist geeignet, wenn Ihre Server einer starken Nichtbenutzerlast ausgesetzt sind und Benutzervorgänge weiterhin Priorität haben.
• Die Leistung hängt vom Design des gesamten Systems ab, nicht nur vom Algorithmus der inneren Schleife.

(In diesem Artikel wird die Suche nach Daten im Speicher beschrieben. Wenn ein Benutzer eine Protokollsuche durchführt, haben die Scalyr-Server diese in den meisten Fällen bereits zwischengespeichert. Im nächsten Artikel wird die Suche nach nicht zwischengespeicherten Protokollen erläutert. Es gelten die gleichen Prinzipien: effizienter Code, Brute Force mit großen Rechenressourcen).

Brute-Force-Methode

Traditionell wird ein großer Datensatz mithilfe eines Stichwortindexes durchsucht. Bei der Anwendung auf Serverprotokolle bedeutet dies, dass nach jedem einzelnen Wort im Protokoll gesucht wird. Für jedes Wort müssen Sie eine Liste aller Einschlüsse erstellen. Dadurch ist es einfach, alle Nachrichten mit diesem Wort zu finden, zum Beispiel „error“, „firefox“ oder „transaction_16851951“ – schauen Sie einfach im Index nach.

Ich habe diesen Ansatz bei Google verwendet und er hat gut funktioniert. Aber in Scalyr durchsuchen wir die Protokolle Byte für Byte.

Warum? Aus abstrakter algorithmischer Sicht sind Schlüsselwortindizes wesentlich effizienter als Brute-Force-Suchen. Allerdings verkaufen wir keine Algorithmen, sondern Leistung. Und bei Leistung geht es nicht nur um Algorithmen, sondern auch um Systemtechnik. Wir müssen alles berücksichtigen: Datenvolumen, Art der Suche, verfügbarer Hardware- und Softwarekontext. Wir kamen zu dem Schluss, dass für unser spezielles Problem etwas wie „grep“ besser geeignet sei als ein Index.

Indizes sind großartig, aber sie haben Einschränkungen. Ein Wort ist leicht zu finden. Die Suche nach Nachrichten mit mehreren Wörtern wie „googlebot“ und „404“ ist jedoch viel schwieriger. Die Suche nach einer Phrase wie „nicht erfasste Ausnahme“ erfordert einen umständlicheren Index, der nicht nur alle Nachrichten mit diesem Wort, sondern auch die spezifische Position des Worts aufzeichnet.

Die eigentliche Schwierigkeit entsteht, wenn Sie nicht nach Worten suchen. Nehmen wir an, Sie möchten sehen, wie viel Traffic von Bots kommt. Der erste Gedanke besteht darin, 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 Beiträge 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 stark verlangsamt. Aus diesem Grund erlauben einige Protokollprogramme keine Teilwortsuche oder (bestenfalls) eine spezielle Syntax mit geringerer Leistung. Das wollen wir vermeiden.

Ein weiteres Problem ist die Zeichensetzung. Möchten Sie alle Anfragen von finden? 50.168.29.7? Was ist mit Debugging-Protokollen, die Folgendes enthalten? [error]? Indizes überspringen normalerweise die Zeichensetzung.

Schließlich lieben Ingenieure leistungsstarke Tools, und manchmal kann ein Problem nur mit einem regulären Ausdruck gelöst werden. Der Stichwortindex ist hierfür wenig geeignet.

Darüber hinaus die Indizes Komplex. Jede Nachricht muss mehreren Schlüsselwortlisten hinzugefügt werden. Diese Listen sollten jederzeit in einem leicht durchsuchbaren 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 einen Ergebnissatz zu erstellen. Im Kontext eines umfangreichen, mandantenfähigen Dienstes führt diese Komplexität zu Leistungsproblemen, die bei der Analyse der Algorithmen nicht sichtbar sind.

Schlüsselwortindizes beanspruchen außerdem viel Platz und die Speicherung stellt einen großen Kostenfaktor in einem Protokollverwaltungssystem dar.

Andererseits kann jede Suche viel Rechenleistung verbrauchen. Unsere Nutzer schätzen die schnelle Suche nach eindeutigen Suchanfragen, allerdings werden solche Suchanfragen relativ selten gestellt. Für typische Suchanfragen, beispielsweise für ein Dashboard, nutzen wir spezielle Techniken (die wir im nächsten Artikel beschreiben). Andere Anfragen sind so selten, dass Sie selten mehr als eine gleichzeitig bearbeiten 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 einen recht großen Vorrat an Prozessoren, die zur Ausführung von Abfragen eingesetzt werden können.

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

Brute Force funktioniert am besten bei einfachen Problemen mit kleinen internen Schleifen. Oftmals lässt sich die interne Schleife so optimieren, dass sie mit sehr hohen Geschwindigkeiten läuft. Wenn der Code komplex ist, ist es viel schwieriger, ihn zu optimieren.

Unser Suchcode hatte ursprünglich eine ziemlich große innere Schleife. Wir speichern Nachrichten auf Seiten in 4K; Jede Seite enthält einige Nachrichten (in UTF-8) und Metadaten für jede Nachricht. Metadaten sind eine Struktur, die die Länge des Werts, die interne Nachrichten-ID und andere Felder kodiert. Der Suchzyklus sah so aus:

Dies ist eine vereinfachte Version des eigentlichen Codes. Aber auch hier sind mehrere Objektplatzierungen, Datenkopien und Funktionsaufrufe sichtbar. Die JVM ist ziemlich gut darin, Funktionsaufrufe zu optimieren und kurzlebige Objekte zuzuweisen, daher hat dieser Code besser funktioniert, als wir es verdient haben. Im Test haben Kunden es recht erfolgreich eingesetzt. Aber irgendwann haben wir es auf die nächste Stufe gebracht.

(Sie fragen sich vielleicht, warum wir Nachrichten in diesem Format mit 4K-Seiten, Text und Metadaten speichern, anstatt direkt mit Protokollen zu arbeiten. Dafür gibt es viele Gründe, die darauf hinauslaufen, dass die Scalyr-Engine intern eher einer verteilten Datenbank als einer ähnelt Dateisystem. Die Textsuche wird oft mit Filtern im DBMS-Stil an den Rändern nach der Protokollanalyse kombiniert. Wir können gleichzeitig viele tausend Protokolle gleichzeitig durchsuchen, und einfache Textdateien sind für unsere transaktionale, replizierte, verteilte Datenverwaltung nicht geeignet.

Zunächst schien es, dass ein solcher Code für die Brute-Force-Optimierung nicht sehr geeignet sei. „Echte Arbeit“ in String.indexOf() dominierte nicht einmal das CPU-Profil. Das heißt, die Optimierung dieser Methode allein würde keinen signifikanten Effekt bringen.

Es kommt vor, dass wir am Anfang jeder Seite Metadaten speichern und am anderen Ende den Text aller Nachrichten in UTF-8 packen. Aus diesem Grund haben wir die Schleife so umgeschrieben, dass sie die gesamte Seite auf einmal durchsucht:

Diese Version funktioniert direkt auf der Ansicht raw byte[] und durchsucht alle Nachrichten auf einmal auf der gesamten 4K-Seite.

Dies ist für die Brute-Force-Methode viel einfacher zu optimieren. Die interne Suchschleife wird gleichzeitig für die gesamte 4K-Seite aufgerufen und nicht separat für jeden Beitrag. Es erfolgt kein Kopieren von Daten, keine Zuordnung von Objekten. Und komplexere Metadatenoperationen werden nur dann aufgerufen, wenn das Ergebnis positiv ist, und nicht bei jeder Nachricht. Auf diese Weise haben wir eine Menge Overhead eliminiert und der Rest der Last wird in einer kleinen internen Suchschleife konzentriert, die sich gut für die weitere Optimierung eignet.

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

Unsere Implementierung erfordert die Erstellung einer 64-KByte-Nachschlagetabelle für jede Suche, aber das ist nichts im Vergleich zu den Gigabytes an Daten, die wir durchsuchen. 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 gibt Raum für Verbesserungen. Es ist möglich, einen Teil des Overheads außerhalb der inneren Schleife zu eliminieren, und wir planen, mit einer inneren Schleife in C statt in Java zu experimentieren.

Wir wenden Gewalt an

Wir haben besprochen, dass die Protokollsuche „ungefähr“ implementiert werden kann, aber wie viel „Leistung“ haben wir? Ziemlich viel.

1 Jahre: Bei richtiger Verwendung ist ein einzelner Kern eines modernen Prozessors für sich genommen ziemlich leistungsstark.

8 Kerne: Wir laufen derzeit auf den SSD-Servern Amazon hi1.4xlarge und i2.4xlarge mit jeweils 8 Kernen (16 Threads). Wie oben erwähnt, sind diese Kerne normalerweise mit Hintergrundoperationen beschäftigt. Wenn der Benutzer eine Suche durchführt, werden Hintergrundvorgänge angehalten, wodurch alle 8 Kerne für die Suche frei werden. Die Suche ist normalerweise im Bruchteil einer Sekunde abgeschlossen, danach wird die Hintergrundarbeit wieder aufgenommen (das Drosselungsprogramm stellt sicher, dass die Flut an Suchanfragen wichtige Hintergrundarbeiten nicht beeinträchtigt).

16 Kerne: Aus Gründen der Zuverlässigkeit organisieren wir Server in Master/Slave-Gruppen. Jeder Master verfügt über eine SSD und einen EBS-Server unter seinem Kommando. Fällt der Hauptserver aus, tritt sofort der SSD-Server an seine Stelle. Master und Slave funktionieren fast immer einwandfrei, sodass jeder Datenblock auf zwei verschiedenen Servern durchsuchbar ist (der EBS-Slave-Server hat einen schwachen Prozessor, daher berücksichtigen wir ihn nicht). Wir teilen die Aufgabe untereinander auf, so dass uns insgesamt 16 Kerne zur Verfügung stehen.

Viele Kerne: In naher Zukunft werden wir Daten so auf Server verteilen, dass alle an der Verarbeitung jeder nicht trivialen Anfrage beteiligt sind. Jeder Kern wird funktionieren. [Notiz: Wir haben den Plan umgesetzt 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-Methode ist ihre ziemlich konstante Leistung. Typischerweise reagiert die Suche nicht sehr empfindlich auf die Details des Problems und des Datensatzes (ich vermute, dass sie deshalb „grob“ genannt wird).

Manchmal liefert der Keyword-Index unglaublich schnelle Ergebnisse, manchmal aber auch nicht. Nehmen wir an, Sie haben 50 GB Protokolle, in denen der Begriff „customer_5987235982“ genau dreimal vorkommt. Eine Suche nach diesem Begriff zählt drei Standorte direkt aus dem Index und wird sofort abgeschlossen. Komplexe Wildcard-Suchen können jedoch Tausende von Schlüsselwörtern scannen und viel Zeit in Anspruch nehmen.

Andererseits sind Brute-Force-Suchen bei jeder Abfrage mehr oder weniger gleich schnell. Die Suche nach langen Wörtern ist besser, aber selbst die Suche nach einem einzelnen Zeichen geht recht schnell.

Aufgrund der Einfachheit der Brute-Force-Methode liegt ihre Leistung nahe am theoretischen Maximum. Es gibt weniger Optionen für unerwartete Festplattenüberlastungen, Sperrkonflikte, Zeigerverfolgung und Tausende anderer Fehlergründe. Ich habe mir gerade die Anfragen angesehen, die Scalyr-Benutzer letzte Woche auf unserem am stärksten ausgelasteten Server gestellt haben. Es gab 14 Anfragen. Genau acht davon dauerten mehr als eine Sekunde; 000 % innerhalb von 99 Millisekunden abgeschlossen (wenn Sie noch keine Protokollanalysetools verwendet haben, vertrauen Sie mir: Es ist schnell).

Eine stabile, zuverlässige Leistung ist wichtig für die Benutzerfreundlichkeit des Dienstes. Wenn es regelmäßig zu Verzögerungen kommt, empfinden Benutzer es als unzuverlässig und zögern, es zu verwenden.

Protokollsuche in Aktion

Hier ist eine kurze Animation, die die Scalyr-Suche in Aktion zeigt. Wir haben ein Demo-Konto, über das wir jedes Ereignis in jedes öffentliche Github-Repository importieren. In dieser Demo untersuche ich die Daten einer Woche: etwa 600 MB Rohprotokolle.

Das Video wurde ohne besondere Vorbereitung live auf meinem Desktop (ca. 5000 Kilometer vom Server entfernt) aufgezeichnet. Die Leistung, die Sie sehen werden, ist größtenteils darauf zurückzuführen Web-Client-Optimierungsowie ein schnelles und zuverlässiges Backend. Immer wenn es eine Pause ohne Ladeanzeige gibt, mache ich eine Pause, damit Sie lesen können, was ich drücken 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 funktionieren wird. Bei der theoretischen Analyse von Algorithmen werden einige Faktoren außer Acht gelassen, die in der realen Welt von großer Bedeutung sein können. Einfachere Algorithmen sind einfacher zu optimieren und in Randsituationen stabiler.

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

Mithilfe einer Brute-Force-Methode 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 den Leistungssteigerungen der letzten Jahre Rechnung zu tragen. Diese Geschwindigkeitssteigerung ist in erster Linie auf Änderungen in der Art und Anzahl der EC2-Server zurückzuführen, die wir heute einsetzen, um unseren wachsenden Kundenstamm zu bedienen. In Kürze stehen Änderungen an, die die betriebliche Effizienz noch einmal dramatisch steigern werden, und wir können es kaum erwarten, sie mitzuteilen.

Source: habr.com