TL;DR: Vor vier Jahren habe ich Google verlassen, um ein neues Tool zur Serverüberwachung zu entwickeln. Die Idee war, normalerweise isolierte Funktionen in einem Dienst zu vereinen. und -analyse, das Sammeln von Metriken, und Dashboards. Eines der Prinzipien ist, dass der Dienst wirklich schnell, sodass DevOps eine einfache, interaktive, angenehme Arbeitserfahrung hat. Das erfordert die Verarbeitung von Datensätzen mit mehreren Gigabytes in Bruchteilen von Sekunden, ohne das Budget zu sprengen. Bestehende Tools zur Logbearbeitung sind oft langsam und ungeschickt, daher standen wir vor der Herausforderung, ein Werkzeug richtig zu entwerfen, um den Nutzern ein neues Gefühl bei der Arbeit zu geben.
In diesem Artikel beschreiben wir, wie wir bei Scalyr dieses Problem gelöst haben, indem wir alte Methoden angewendet, einen brutalen Ansatz verfolgt und unnötige Schichten entfernt und komplexe Datenstrukturen vermieden haben. Diese Lektionen können Sie auf ihre eigenen Ingenieuraufgaben anwenden.
Die Kraft der alten Schule
Die Loganalyse beginnt normalerweise mit der Suche: Alle Nachrichten finden, die einem bestimmten Muster entsprechen. Bei Scalyr sind das Dutzende oder Hunderte Gigabytes an Logs von vielen Servern. Moderne Ansätze beinhalten oft den Aufbau einer komplexen Datenstruktur, die für die Suche optimiert ist. Ich habe genau so etwas bei Google gesehen, wo sie ziemlich gut darin sind. Aber wir haben uns für einen viel raueren Ansatz entschieden: die lineare Durchsuchung der Logs. Und das hat funktioniert — wir bieten eine Suchoberfläche, die um ein Vielfaches schneller ist als die der Konkurrenz (siehe Animation am Ende).
Die entscheidende Erkenntnis war, dass moderne Prozessoren in einfachen, geradlinigen Operationen tatsächlich sehr schnell sind. Dies übersieht man leicht in komplexen, mehrschichtigen Systemen, die von der I/O- und Netzwerkgeschwindigkeit abhängig sind, und solche Systeme sind heute sehr verbreitet. Daher haben wir ein Design entwickelt, das die Anzahl der Schichten und unnötigen Abfälle minimiert. Mit mehreren Prozessoren und Servern parallel erreichen wir eine Suchgeschwindigkeit von 1 TB pro Sekunde.
Wesentliche Erkenntnisse aus diesem Artikel:
- Brutale Suche ist ein durchaus tragfähiger Ansatz zur Lösung realer, großangelegter Probleme.
- Rohe Gewalt ist eine Designtechnik und keine Arbeitsbefreiung. Wie jede Technik ist sie besser für einige Probleme geeignet als für andere, und sie kann schlecht oder gut umgesetzt werden.
- Rohe Gewalt ist besonders gut geeignet, um stabile Leistung zu erreichen.
- Ein effektiver Einsatz von Roher Gewalt erfordert Code-Optimierung und einen rechtzeitigen Einsatz ausreichender Ressourcen. Sie ist geeignet, wenn Ihre Server einer hohen Last ausgesetzt sind, die nicht benutzerbezogen ist, während Benutzeraktionen Priorität haben.
- Die Leistung hängt vom Design des gesamten Systems ab und nicht nur vom Algorithmus des inneren Kreises.
(In diesem Artikel wird die Datensuche im Speicher beschrieben. In den meisten Fällen, wenn ein Benutzer in Protokollen sucht, haben die Scalyr-Server diese bereits zwischengespeichert. Im nächsten Artikel werden wir die Suche in nicht zwischengespeicherten Protokollen besprechen. Die gleichen Prinzipien gelten: effizienter Code, die Methode der Rohe Gewalt mit großen Rechenressourcen).
Methode der Rohe Gewalt
Traditionell erfolgt die Suche in großen Datensätzen über einen Schlüsselwortindex. In Bezug auf Serverprotokolle bedeutet dies, dass jedes einzigartige Wort im Protokoll gesucht wird. Für jedes Wort muss eine Liste aller Vorkommen erstellt werden. Dies ermöglicht es, schnell alle Nachrichten mit diesem Wort zu finden, beispielsweise 'error', 'firefox' oder 'transaction_16851951' — einfach im Index nachschauen.
Ich habe diesen Ansatz bei Google verwendet, und er hat gut funktioniert. Aber bei Scalyr suchen wir in den Protokollen Byte für Byte.
Warum? Aus abstrakter algorithmischer Sicht sind Schlüsselwortindizes viel effizienter als rohe Suche. Allerdings verkaufen wir keine Algorithmen, wir verkaufen Leistung. Und Leistung ist nicht nur Algorithmen, sondern auch Systemtechnik. Wir müssen alles berücksichtigen: Datenvolumen, Art der Suche, verfügbare Hardware und den Softwarekontext. Wir haben entschieden, dass für unser spezifisches Problem eine Option wie 'grep' besser geeignet ist als ein Index.
Indizes sind großartig, aber sie haben ihre Einschränkungen. Ein Wort zu finden ist einfach. Aber die Suche nach Nachrichten mit mehreren Wörtern, wie 'googlebot' und '404', ist schon viel schwieriger. Die Suche nach einer Phrase wie 'uncaught exception' erfordert einen umfangreicheren Index, der nicht nur alle Nachrichten mit diesem Wort registriert, sondern auch den genauen Standort des Wortes.
Die eigentliche Schwierigkeit tritt auf, wenn Sie nicht nach Wörtern suchen. Angenommen, Sie möchten sehen, wie viel Verkehr von Bots kommt. Der erste Gedanke ist, in den Protokollen nach dem Wort 'bot' zu suchen. So finden Sie einige Bots: Googlebot, Bingbot und viele andere. Aber hier ist 'bot' kein Wort, sondern ein Teil davon. Wenn Sie 'bot' im Index suchen, werden Sie keine Nachrichten mit dem Wort 'Googlebot' finden. Wenn Sie jedes Wort im Index überprüfen und dann den Index nach den gefundenen Schlüsselwörtern durchsuchen, verlangsamt sich die Suche erheblich. Infolgedessen erlauben einige Programme zur Protokollanalyse keine Partialsuchen oder (im besten Fall) erlauben die Verwendung einer speziellen Syntax mit geringerer Leistung. Wir möchten das vermeiden.
Ein weiteres Problem ist die Interpunktion. Möchten Sie alle Anfragen von 50.168.29.7? Что насчёт отладки логов, содержащих [error]? Индексы обычно пропускают пунктуацию.
Schließlich lieben Ingenieure leistungsstarke Werkzeuge, und manchmal kann ein Problem nur mit regulären Ausdrücken gelöst werden. Der Schlüsselwortindex eignet sich dafür nicht sehr gut.
Darüber hinaus sind die Indizes komplex. Jede Nachricht muss in mehreren Schlüsselwortlisten hinzugefügt werden. Diese Listen sollten ständig in einem durchsuchbaren Format gehalten werden. Anfragen mit Phrasen, Wortfragmenten oder regulären Ausdrücken müssen in Operationen mit mehreren Listen übersetzt werden, und die Ergebnisse müssen gescannt und kombiniert werden, um ein Ergebnis-Set zu erhalten. Im Kontext eines groß angelegten Multi-User-Dienstes schafft diese Komplexität Leistungsprobleme, die bei der Analyse von Algorithmen nicht sichtbar sind.
Schlüsselwortindizes beanspruchen auch viel Platz, und der Speicher ist der Hauptkostenfaktor in einem Protokollmanagementsystem.
Andererseits kann jede Suche eine Menge Rechenleistung in Anspruch nehmen. Unsere Nutzer schätzen die Hochgeschwindigkeitssuche nach einzigartigen Abfragen, aber solche Abfragen kommen relativ selten vor. Für typische Suchanfragen, zum Beispiel beim Dashboard, verwenden wir spezielle Techniken (wir werden sie im nächsten Artikel beschreiben). Andere Abfragen sind recht selten, sodass es selten erforderlich ist, mehr als eine auf einmal zu verarbeiten. Aber das bedeutet nicht, dass unsere Server nicht beschäftigt sind: Sie sind mit der Verarbeitung, Analyse und Komprimierung neuer Nachrichten, der Bewertung von Benachrichtigungen, der Komprimierung alter Daten und so weiter ausgelastet. So haben wir einen recht erheblichen Pool an Prozessoren, die zur Ausführung von Anfragen eingesetzt werden können.
Brute Force funktioniert, wenn Sie ein grobes Problem (und viel Kraft) haben.
Brute Force funktioniert am besten bei einfachen Aufgaben mit kleinen internen Schleifen. Oft können Sie die interne Schleife optimieren, um mit sehr hohen Geschwindigkeiten zu arbeiten. Wenn der Code komplex ist, wird es viel schwieriger, ihn zu optimieren.
Ursprünglich hatte unser Suchcode eine ziemlich große interne Schleife. Wir speichern Nachrichten in Seiten zu je 4K; jede Seite enthält einige Nachrichten (in UTF-8) und Metadaten für jede Nachricht. Die Metadaten sind eine Struktur, in der die Länge des Wertes, die interne ID der Nachricht und andere Felder codiert sind. Die Suchschleife sah folgendermaßen aus:
Dies ist eine vereinfachte Version im Vergleich zum tatsächlichen Code. Aber selbst hier sieht man mehrere Objektplatzierungen, Datenkopien und Funktionsaufrufe. Die JVM optimiert Funktionsaufrufe und allokiert flüchtige Objekte ziemlich gut, weshalb dieser Code besser funktionierte, als wir es verdient hatten. Während der Tests hatten die Kunden recht guten Erfolg damit. Aber letztendlich sind wir auf ein neues Niveau übergegangen.
(Sie fragen sich vielleicht, warum wir Nachrichten in einem Format mit 4K-Seiten, Text und Metadaten speichern, anstatt direkt mit Protokolldateien zu arbeiten. Es gibt viele Gründe, die darauf hinauslaufen, dass der Scalyr-Engine intern mehr einer verteilten Datenbank als einem Dateisystem ähnelt. Die Textsuche wird oft mit DBMS-ähnlichen Filtern in Feldern nach der Protokollanalyse kombiniert. Wir können gleichzeitig in vielen Tausend Protokollen suchen, und einfache Textdateien sind nicht für unser transaktionales, repliziertes, verteiltes Datenmanagement geeignet.)
Ursprünglich schien dieser Code nicht besonders geeignet für die Optimierung der Brute-Force-Methode zu sein. „Die eigentliche Arbeit“ in String.indexOf() dominierte nicht einmal im CPU-Profil. Das bedeutet, dass die Optimierung nur dieser Methode keinen wesentlichen Effekt bringen würde.
Es stellte sich heraus, dass wir Metadaten am Anfang jeder Seite speichern und der Text aller Nachrichten am anderen Ende in UTF-8 verpackt ist. Aus diesem Grund haben wir die Schleife umgeschrieben, um die gesamte Seite auf einmal zu durchsuchen:
Diese Version arbeitet direkt auf der Darstellung raw byte[] und führt die Suche nach allen Nachrichten gleichzeitig auf der gesamten 4K-Seite aus.
Das ist viel leichter für die Brute-Force-Methode zu optimieren. Die interne Suchschleife wird gleichzeitig für die gesamte 4K-Seite aufgerufen, anstatt separat für jede Nachricht. Es gibt keine Datenkopien und keine Objektallokationen. Und komplexere Operationen mit Metadaten werden nur bei einem positiven Ergebnis aufgerufen, nicht für jede Nachricht. So haben wir eine Menge Overhead ausgeschlossen, und der verbleibende Aufwand konzentriert sich auf eine kleine interne Suchschleife, die gut für eine weitere Optimierung geeignet ist.
Unser tatsächlicher Suchalgorithmus basiert auf . Er ähnelt dem Boyer-Moore-Algorithmus, wobei bei jedem Schritt ungefähr die Länge des Suchstrings übersprungen wird. Der Hauptunterschied besteht darin, dass er zwei Bytes gleichzeitig überprüft, um falsche Übereinstimmungen zu minimieren.
Unsere Implementierung erfordert für jede Suche die Erstellung einer 64K-Suchertabelle, aber das ist nichts im Vergleich zu den Gigabytes an Daten, in denen wir suchen. Die interne Schleife verarbeitet mehrere Gigabytes pro Sekunde auf einem Kern. In der Praxis liegt die stabile Leistung bei etwa 1,25 GB pro Sekunde auf jedem Kern, und es gibt Potenzial für Verbesserungen. Einige Overhead-Kosten außerhalb der internen Schleife können eliminiert werden, und wir planen, mit der internen Schleife in C anstelle von Java zu experimentieren.
Die Kraft anwenden
Wir haben besprochen, dass die Suche in Logs "grob" umgesetzt werden kann, aber wie viel "Kraft" haben wir? Nicht wenig.
1 Kern: Bei richtiger Nutzung ist ein Kern eines modernen Prozessors ziemlich leistungsstark für sich.
8 Kerne: Derzeit verwenden wir Amazon-Server hi1.4xlarge und i2.4xlarge SSD, von denen jeder 8 Kerne (16 Threads) hat. Wie oben erwähnt, sind diese Kerne normalerweise mit Hintergrundoperationen beschäftigt. Wenn ein Benutzer eine Suche durchführt, werden die Hintergrundoperationen angehalten, wodurch alle 8 Kerne für die Suche frei werden. Die Suche wird normalerweise in einem Bruchteil einer Sekunde abgeschlossen, woraufhin die Hintergrundarbeit fortgesetzt wird (das Regulierungssystem gewährleistet, dass eine Flut von Suchanfragen wichtige Hintergrundarbeiten nicht stört).
16 Kerne: Zur Zuverlässigkeit organisieren wir die Server in Master/Slave-Gruppen. Jeder Master hat einen SSD-Server und einen EBS-Server untergestellt. Wenn der Hauptserver ausfällt, übernimmt der SSD-Server sofort dessen Platz. Fast die gesamte Zeit arbeiten Master und Slave normal, sodass jeder Datenblock auf zwei verschiedenen Servern für Suchanfragen zugänglich ist (der Slave-EBS-Server hat einen schwachen Prozessor, daher betrachten wir ihn nicht). Wir teilen die Aufgabe zwischen ihnen auf, sodass uns insgesamt 16 Kerne zur Verfügung stehen.
Viele Kerne: In naher Zukunft werden wir die Daten auf den Servern so verteilen, dass alle an der Verarbeitung jeder nicht trivialen Anfrage beteiligt sind. Jeder Kern wird arbeiten. [Hinweis: wir haben einen 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 Bruteforce-Methode ist die ziemlich stabile Leistung. Generell ist die Suche nicht besonders empfindlich gegenüber den Details der Aufgabe und des Datensatzes (ich denke, deshalb wird sie "grob" genannt).
Der Index der Schlüsselwörter liefert manchmal unglaublich schnelle Ergebnisse, manchmal jedoch nicht. Angenommen, Sie haben 50 GB Protokolldateien, in denen der Begriff 'customer_5987235982' genau dreimal vorkommt. Die Suche nach diesem Begriff findet direkt im Index drei Standorte und wird sofort abgeschlossen. Aber eine komplexe Suche mit Platzhaltern kann Tausende von Schlüsselwörtern scannen und viel Zeit in Anspruch nehmen.
Auf der anderen Seite wird die brute-force-Suche für jede Anfrage mehr oder weniger mit der gleichen Geschwindigkeit ausgeführt. Die Suche nach längeren Wörtern ist besser, aber selbst die Suche nach einem einzelnen Zeichen erfolgt recht schnell.
Die Einfachheit der brute-force-Methode bedeutet, dass ihre Leistung nahe am theoretischen Maximum liegt. Hier gibt es weniger Möglichkeiten für unerwartete Festplattenüberlastungen, Konflikte bei Sperren, Zeigerverfolgen und Tausende von anderen Gründen für Fehlfunktionen. Ich habe gerade die Anfragen, die letzte Woche von Scalyr-Benutzern auf unserem am stärksten frequentierten Server gemacht wurden, angeschaut. Es gab 14.000 Anfragen. Genau acht von ihnen dauerten mehr als eine Sekunde; 99% wurden innerhalb von 111 Millisekunden ausgeführt (wenn Sie keine Analysewerkzeuge verwendet haben, glauben Sie mir: das ist schnell).
Stabile, zuverlässige Leistung ist wichtig für die Benutzerfreundlichkeit des Dienstes. Wenn er gelegentlich stockt, werden die Benutzer ihn als unzuverlässig empfinden und zögern, ihn zu nutzen.
Protokollsuchen in Aktion
Hier ist eine kurze Animation, die die Scalyr-Suche in Aktion zeigt. Wir haben ein Demokonto, in das wir jedes Ereignis aus jedem öffentlichen Github-Repository importieren. In dieser Demo untersuche ich Daten über eine Woche: etwa 600 MB unbearbeitete Protokolle.
Das Video wurde live, ohne spezielle Vorbereitung, auf meinem Desktop (ungefähr 5000 Kilometer vom Server entfernt) aufgenommen. Die Leistung, die Sie sehen werden, verdankt sich größtenteils , sowie einem schnellen und zuverlässigen Backend. Jedes Mal, wenn es eine Pause ohne den 'loading'-Indikator gibt, mache ich eine Pause, damit Sie lesen können, was ich gleich anklicken werde.
Abschließend
Bei der Verarbeitung großer Datenmengen ist es wichtig, einen guten Algorithmus auszuwählen, aber "gut" bedeutet nicht "komplex". Denken Sie darüber nach, wie Ihr Code in der Praxis funktionieren wird. Einige Faktoren, die in der theoretischen Analyse von Algorithmen nicht berücksichtigt werden, können in der realen Welt von großer Bedeutung sein. Einfachere Algorithmen sind leichter zu optimieren und stabiler in Grenzsituationen.
Denken Sie auch an den Kontext, in dem der Code ausgeführt wird. In unserem Fall benötigen wir leistungsstarke Server, um Hintergrundaufgaben zu verwalten. Benutzer initiieren Suchen relativ selten, daher können wir eine ganze Gruppe von Servern für den kurzen Zeitraum ausleihen, der für die Durchführung jeder Suche erforderlich ist.
Mit der Bruteforce-Methode haben wir eine schnelle, zuverlässige und flexible Suche durch einen Satz von Protokollen implementiert. Wir hoffen, dass diese Ideen für Ihre Projekte nützlich sein werden.
Änderung: Der Titel und der Text wurden von „Suche mit 20 GB pro Sekunde“ auf „Suche mit 1 TB pro Sekunde“ geändert, um die Leistungssteigerung in den letzten Jahren widerzuspiegeln. Diese Geschwindigkeitssteigerung hängt vor allem mit der Veränderung des Typs und der Anzahl der EC2-Server zusammen, die wir heute bereitstellen, um der gestiegenen Kundenbasis gerecht zu werden. In naher Zukunft erwarten wir Änderungen, die eine weitere drastische Effizienzsteigerung ermöglichen, und wir freuen uns darauf, die Möglichkeit zu haben, darüber zu berichten.
Quelle: habr.com
