Go-Optimierungen in VictoriaMetrics. Alexander Valjalkin

Der umgekehrte Index ermöglicht es, schnell alle timeseries_ids, die die gegebenen label=value.

enthält. Außerdem ermöglicht er es, schnell die timeseries_ids Zeitreihen für mehrere Paare label=value, oder für Paare label=regexp. Wie geschieht das? Durch das Finden der Schnittmenge mehrerer timeseries_ids für jedes Paar label=value.

Betrachten wir verschiedene Implementierungen des umgekehrten Index. Fangen wir mit der einfachsten naiven Implementierung an. Sie sieht so aus.

Funktion getMetricIDs erhält eine Liste von Zeichenfolgen. Jede Zeichenfolge enthält label=value. Diese Funktion gibt eine Liste zurück metricIDs.

Wie funktioniert das? Hier haben wir eine globale Variable, die heißt invertedIndex. Das ist ein gewöhnliches Wörterbuch (map), das eine Zeichenfolge auf ein Slice von Ints abbildet. Die Zeichenfolge enthält label=value.

Implementierung der Funktion: wir holen metricIDs für den ersten label=value, dann gehen wir alle anderen durch label=value, holen metricIDs für sie. Und wir rufen die Funktion intersectInts, über die später gesprochen wird. Und diese Funktion gibt die Schnittmenge dieser Listen zurück.

Wie Sie sehen, ist die Implementierung des umgekehrten Index nicht sehr kompliziert. Aber das ist eine naive Implementierung. Was sind ihre Nachteile? Der Hauptnachteil der naiven Implementierung ist, dass ein solcher umgekehrter Index im Arbeitsspeicher gespeichert wird. Nach einem Neustart der Anwendung verlieren wir diesen Index. Es gibt keine Speicherung dieses Index auf der Festplatte. Für eine Datenbank ist ein solcher umgekehrter Index kaum geeignet.

Der zweite Nachteil hängt ebenfalls mit dem Speicher zusammen. Der invertierte Index muss im Arbeitsspeicher untergebracht werden. Wenn er die Größe des Arbeitsspeichers überschreitet, bekommen wir offensichtlich einen 'Out of Memory'-Fehler. Das Programm wird dann nicht mehr funktionieren.

Dieses Problem kann mit fertigen Lösungen wie LevelDB, oder RocksDB.

Kurz gesagt, wir brauchen eine Datenbank, die es uns ermöglicht, drei Operationen schnell durchzuführen.

• Die erste Operation ist das Schreiben von Schlüssel-Wert-Paaren in diese Datenbank. Dies geschieht sehr schnell, wobei von Schlüssel-Wert-Paaren beliebige Strings sind.
• Die zweite Operation ist die schnelle Suche nach dem Wert anhand des gegebenen Schlüssels.
• Und die dritte Operation ist die schnelle Suche nach allen Werten anhand eines vorgegebenen Prefix.

LevelDB und RocksDB – diese Datenbanken wurden von Google und Facebook entwickelt. Zuerst erschien LevelDB. Dann haben die Leute von Facebook LevelDB genommen und verbessert, was zu RocksDB führte. Derzeit laufen fast alle internen Datenbanken bei Facebook auf RocksDB, einschließlich MySQL, das ebenfalls auf RocksDB umgestellt wurde. Sie nannten es MyRocks.

Der invertierte Index kann mit LevelDB implementiert werden. Wie geht das? Wir speichern als Schlüssel label=value. Und als Wert verwenden wir die ID der Zeitreihe, in der das Paar vorkommt. label=value.

Wenn wir viele Zeitreihen mit diesem Paar haben label=value, wird es viele Zeilen in dieser Datenbank mit denselben Schlüsseln und verschiedenen timeseries_idsgeben. Um eine Liste aller timeseries_ids, die mit diesem beginnen label=prefix, zu erhalten, führen wir einen Range Scan durch, für den diese Datenbank optimiert ist. Das heißt, wir wählen alle Zeilen aus, die mit label=prefix beginnen und erhalten die notwendigen timeseries_ids.

Hier ist eine beispielhafte Umsetzung, wie sie in Go aussehen würde. Wir haben einen invertierten Index. Das ist LevelDB.

Die Funktion ist die gleiche wie bei der naiven Implementierung. Sie wiederholt fast Zeile für Zeile die naive Implementierung. Der einzige Unterschied ist, dass wir anstelle des Zugriffs auf map auf den invertierten Index zugreifen. Wir holen alle Werte für das erste label=value. Dann gehen wir alle verbleibenden Paare durch label=value und holen die entsprechenden Sets von metricIDs für sie. Danach finden wir die Schnittmenge.

Es scheint alles gut zu sein, aber diese Lösung hat Nachteile. VictoriaMetrics hat ursprünglich den invertierten Index auf Basis von LevelDB implementiert. Letztendlich musste man jedoch darauf verzichten.

Warum? Weil LevelDB langsamer ist als die naive Implementierung. Bei der naiven Implementierung holen wir sofort den gesamten Slice für den gegebenen Schlüssel. metricIDsDiese sehr schnelle Operation – der gesamte Slice ist bereit zur Verwendung.

In LevelDB muss bei jedem Aufruf der Funktion GetValues über alle Zeilen iteriert werden, die mit label=valuebeginnen. Für jede Zeile muss der Wert timeseries_idsabgerufen werden. Aus diesen timeseries_ids muss ein Slice erstellt werden. timeseries_idsOffensichtlich ist das viel langsamer als der einfache Zugriff auf eine gewöhnliche Map über den Schlüssel.

Ein weiterer Nachteil ist, dass LevelDB in C geschrieben ist. Der Zugriff auf C-Funktionen aus Go ist nicht sehr schnell. Es dauert Hunderte von Nanosekunden. Das ist nicht sehr schnell, da im Vergleich zu einem gewöhnlichen Funktionsaufruf, der in Go geschrieben ist und 1-5 Nanosekunden benötigt, der Performance-Unterschied in Zehnerordnungen beträgt. Für VictoriaMetrics war das ein fataler Nachteil 🙂

Deshalb habe ich meine eigene Implementierung eines invertierten Index geschrieben. Ich nannte sie mergeset.

Mergeset basiert auf der Datenstruktur MergeTree. Diese Datenstruktur stammt aus ClickHouse. Offensichtlich muss der Mergeset für eine schnelle Suche timeseries_ids nach dem angegebenen Schlüssel optimiert sein. Mergeset ist vollständig in Go geschrieben. Sie können die Quellcodes von VictoriaMetrics auf GitHub einsehen.Die Implementierung des Mergeset befindet sich im Ordner /lib/mergeset. Sie können versuchen, zu verstehen, was dort passiert.

Die API des Mergeset ähnelt der von LevelDB und RocksDB. Das heißt, sie ermöglicht es, neue Einträge schnell zu speichern und Einträge anhand eines angegebenen Präfixes schnell auszuwählen.

Über die Nachteile des Mergeset werden wir später sprechen. Jetzt reden wir über die Probleme, die bei VictoriaMetrics in der Produktion bei der Implementierung des invertierten Index aufgetreten sind.

Warum sind sie aufgetreten?

Der erste Grund ist die hohe Wechselrate. Auf Russisch übersetzt bedeutet das die häufige Änderung von Zeitreihen. Dies geschieht, wenn eine Zeitreihe endet und eine neue beginnt oder viele neue Zeitreihen beginnen. Und das passiert häufig.

Der zweite Grund ist die große Anzahl von Zeitreihen. Zu Beginn, als das Monitoring an Popularität gewann, war die Anzahl der Zeitreihen gering. Beispielsweise muss jeder Computer die CPU-, Arbeitsspeicher-, Netzwerk- und Festplattennutzung überwachen. 4 Zeitreihen pro Computer. Angenommen, Sie haben 100 Computer und 400 Zeitreihen. Das ist sehr wenig.

Im Laufe der Zeit haben die Menschen herausgefunden, dass man detailliertere Informationen messen kann. Zum Beispiel kann man nicht nur die Auslastung des gesamten Prozessors messen, sondern auch die der einzelnen Prozessorkerne. Wenn Sie 40 Prozessorkerne haben, haben Sie dementsprechend 40-mal so viele Zeitreihen zur Messung der Prozessorlast.

Aber das ist noch nicht alles. Jeder Prozessorkern kann mehrere Zustände haben, wie zum Beispiel idle, wenn er nicht aktiv ist. Außerdem gibt es die Arbeit im User Space, die Arbeit im Kernel Space und andere Zustände. Jedes dieser Zustände kann ebenfalls als separate Zeitreihe gemessen werden. Dies erhöht die Anzahl der Reihen zusätzlich um das 7- bis 8-fache.

Aus einer Metrik ergeben sich somit 40 x 8 = 320 Metriken nur für einen Computer. Multiplizieren wir das mit 100, erhalten wir 32.000 statt 400.

Dann kam Kubernetes. Und das Ganze wird noch komplizierter, da in Kubernetes viele verschiedene Dienste gehostet werden können. Jeder Dienst in Kubernetes besteht aus vielen Pods. Und all das muss überwacht werden. Darüber hinaus haben wir einen ständigen Deployment-Prozess neuer Versionen Ihrer Dienste. Für jede neue Version müssen neue Zeitreihen erstellt werden. Am Ende wächst die Anzahl der Zeitreihen exponentiell, und wir stehen vor dem Problem einer hohen Anzahl von Zeitreihen, das als High-Cardinality bekannt ist. VictoriaMetrics bewältigt dies im Vergleich zu anderen Zeitreihendatenbanken erfolgreich.

Lassen Sie uns den hohen Churn-Rate genauer betrachten. Was verursacht einen hohen Churn-Rate in der Produktion? Weil einige Werte von Labels und Tags sich ständig ändern.

Nehmen wir zum Beispiel Kubernetes, wo es das Konzept gibt von deployment, d. h. wenn eine neue Version Ihrer Anwendung ausgerollt wird. Die Entwickler von Kubernetes haben sich aus irgendeinem Grund entschieden, die ID des Deployments in das Label aufzunehmen.

Was hat das zur Folge? Bei jedem neuen Deployment werden all unsere alten Zeitreihen unterbrochen, und an ihrer Stelle beginnen neue Zeitreihen mit dem neuen Wert des Labels deployment_id. Solcherart Reihen können Hunderttausende und sogar Millionen betragen.

Eine wichtige Besonderheit dabei ist, dass die Gesamtzahl der Zeitreihen steigt, während die Anzahl der derzeit aktiven Zeitreihen, für die Daten eintreffen, konstant bleibt. Ein solcher Zustand wird als hoher Churn-Rate bezeichnet.

Das Hauptproblem der hohen Abwanderungsrate besteht darin, eine konstante Suchgeschwindigkeit für alle Zeitreihen über einen festgelegten Satz von Labels in einem bestimmten Zeitraum zu gewährleisten. In der Regel handelt es sich um den Zeitraum der letzten Stunde oder des letzten Tages.

Wie kann man dieses Problem lösen? Hier ist die erste Variante. Man unterteilt den Inverted Index in unabhängige Teile nach Zeit. Das heißt, ein bestimmter Zeitraum verstreicht, der aktuelle Inverted Index wird beendet. Und wir erstellen einen neuen Inverted Index. Verstreicht ein weiterer Zeitraum, erstellen wir einen weiteren und noch einen.

Bei der Abfrage dieser Inverted Indizes finden wir eine Menge von Inverted Indizes, die in den festgelegten Zeitraum fallen. Dementsprechend wählen wir die IDs der Zeitreihen daraus aus.

Das spart Ressourcen, denn wir müssen keine Teile durchsuchen, die nicht in den festgelegten Zeitraum fallen. Das heißt, normalerweise überspringen wir Anfragen für vorherige Zeitintervalle, wenn wir Daten für die letzte Stunde auswählen.

Es gibt eine weitere Variante zur Lösung dieses Problems. Man speichert für jeden Tag eine separate Liste von IDs der Zeitreihen, die an diesem Tag aufgetreten sind.

Der Vorteil dieser Lösung im Vergleich zur vorherigen ist, dass wir keine Informationen über Zeitreihen duplizieren, die mit der Zeit nicht verschwinden. Sie sind ständig vorhanden und verändern sich nicht.

Der Nachteil ist, dass eine solche Lösung schwieriger umzusetzen und schwieriger zu debuggen ist. Und VictoriaMetrics hat sich für diese Lösung entschieden. Historisch gesehen hat sich das so entwickelt. Diese Lösung zeigt sich auch besser im Vergleich zur vorherigen. Denn diese Lösung wurde nicht umgesetzt, weil es notwendig ist, Daten in jeder Partition für Zeitreihen zu duplizieren, die sich nicht ändern, das heißt, die mit der Zeit nicht verschwinden. VictoriaMetrics wurde in erster Linie hinsichtlich des Speicherplatzverbrauchs optimiert, und die vorherige Implementierung verschlechterte den Speicherplatzverbrauch. Diese Implementierung eignet sich besser zur Minimierung des Speicherplatzverbrauchs, weshalb sie ausgewählt wurde.

Wir mussten damit kämpfen. Der Kampf bestand darin, dass in dieser Implementierung trotzdem deutlich mehr Daten ausgewählt werden müssen, timeseries_ids als wenn der Inverted Index zeitlich unterteilt wird.

Wie haben wir dieses Problem gelöst? Wir haben es auf originelle Weise gelöst – indem wir mehrere Identifikatoren von Zeitreihen in jedem Datensatz des invertierten Index anstelle eines einzigen Identifikators gespeichert haben. Das heißt, wir haben einen Schlüssel label=value, der in jeder Zeitreihe vorkommt. Und jetzt speichern wir mehrere timeseries_ids in einem Datensatz.

Hier ist ein Beispiel. Früher hatten wir N Datensätze, jetzt haben wir einen Datensatz, dessen Präfix das gleiche ist wie das aller anderen. Der vorherige Datensatz enthält alle id der Zeitreihen.

Das hat es ermöglicht, die Scangeschwindigkeit eines solchen invertierten Index um das 10-Fache zu erhöhen. Außerdem konnte der Speicherverbrauch für den Cache gesenkt werden, weil wir jetzt die Zeichenfolge label=value nur einmal im Cache zusammen mit N mal speichern. Und diese Zeichenfolge kann groß sein, wenn in Ihren Tags und Labels lange Zeichenfolgen gespeichert sind, die Kubernetes gerne da einfügt.

Eine weitere Möglichkeit zur Beschleunigung der Suche im invertierten Index ist das Sharding. Erstellen mehrerer invertierter Indizes statt eines und das Sharding der Daten zwischen ihnen nach Schlüssel. Das ist eine Menge key=value Paare. Das heißt, wir haben mehrere unabhängige invertierte Indizes, die wir parallel auf mehreren Prozessoren abfragen können. frühere Implementierungen ermöglichten nur den Betrieb im Einzelprozessmodus, das heißt, Daten nur auf einem Kern zu scannen. Diese Lösung ermöglicht es, Daten sofort auf mehreren Kernen zu scannen, wie es ClickHouse gerne macht. Das planen wir zu implementieren.

Und jetzt zurück zu unseren Schafen – zur Schnittfunktion timeseries_ids. Betrachten wir, welche Implementierungen möglich sind. Diese Funktion ermöglicht es, timeseries_ids für eine gegebene Menge label=value.

Die erste Möglichkeit ist die naive Implementierung. Zwei geschachtelte Schleifen. Wir erhalten als Eingabe der Funktion intersectInts zwei Slices — a und b. Am Ende sollte sie uns die Schnittmenge dieser Slices zurückgeben.

Die naive Implementierung sieht so aus. Wir gehen alle Werte aus dem Slice adurch, innerhalb dieser Schleife durchlaufen wir alle Werte aus Slice b. Und vergleichen sie. Wenn sie übereinstimmen, dann haben wir die Schnittmenge gefunden. Und speichern sie in result.

. Welche Nachteile gibt es? Die quadratische Komplexität — das ist ihr Hauptnachteil. Zum Beispiel, wenn Sie Größen des Slices haben a und b Wenn Sie eine Million pro Iteration verwenden, wird diese Funktion Ihnen niemals eine Antwort zurückgeben. Denn sie müsste eine Billion Iterationen durchführen, was selbst für moderne Computer extrem viel ist.

Die zweite Implementierung basiert auf map. Wir erstellen eine map und fügen alle Werte aus dem Slice in diese map ein. aDann durchlaufen wir den Slice mit einer separaten Schleife. bUnd überprüfen, ob dieser Wert im Slice b in der map vorhanden ist. Wenn ja, fügen wir ihn dem Ergebnis hinzu.

Welche Vorteile gibt es? Der Vorteil liegt darin, dass hier nur eine lineare Komplexität vorliegt. Das heißt, die Funktion wird für größere Slice-Größen viel schneller ausgeführt. Für einen Slice mit einer Million Elementen wird diese Funktion in 2 Millionen Iterationen ausgeführt, im Gegensatz zu einer Billion Iterationen wie in der vorherigen Funktion.

Ein Nachteil ist jedoch, dass diese Funktion mehr Speicher benötigt, um die map zu erstellen.

Ein zweiter Nachteil ist der große Overhead beim Hashing. Dieser Nachteil ist nicht sehr offensichtlich. Auch uns war er anfangs nicht sehr klar, weshalb die Intersection in VictoriaMetrics zuerst über map implementiert wurde. Aber das Profiling zeigte, dass die meiste CPU-Zeit für das Schreiben in die map und die Überprüfung, ob ein Wert in dieser map vorhanden ist, verwendet wird.

Warum wird in diesen Stellen CPU-Zeit verbraucht? Weil in diesen Zeilen Go die Hashing-Operation durchführt. Das heißt, es berechnet den Hash vom Schlüssel, um dann über den angegebenen Index in der HashMap zuzugreifen. Der Vorgang zur Berechnung des Hashes dauert mehrere Dutzend Nanosekunden. Das ist für VictoriaMetrics langsam.

Ich habe beschlossen, ein Bitset zu implementieren, das speziell für diesen Fall optimiert ist. So sieht jetzt die Intersection von zwei Slices aus. Hier erstellen wir ein Bitset. Wir fügen die Elemente aus dem ersten Slice hinzu und prüfen dann die Anwesenheit dieser Elemente im zweiten Slice und fügen sie dem Ergebnis hinzu. Es unterscheidet sich fast nicht vom vorherigen Beispiel. Das einzige, was wir hier geändert haben, ist der Zugriff auf die map durch benutzerdefinierte Funktionen. add und has.

Auf den ersten Blick scheint es, dass das langsamer sein sollte, wenn zuvor eine Standardmap verwendet wurde und hier zusätzliche Funktionen aufgerufen werden, aber das Profiling zeigt, dass dieses Ding zehnmal schneller arbeitet als die Standardmap für den Fall mit VictoriaMetrics.

Darüber hinaus verbraucht es wesentlich weniger Speicher im Vergleich zur Implementierung mit map. Denn wir speichern hier Bits statt achtbyte-Werte.

Ein Nachteil dieser Umsetzung ist, dass sie nicht so offensichtlich und nicht trivial ist.

Ein weiterer Nachteil, den viele möglicherweise übersehen, ist, dass diese Implementierung in bestimmten Fällen schlecht funktionieren kann. Das heißt, sie ist für einen spezifischen Fall optimiert, nämlich für den Schnittpunkt der IDs der Zeitreihen von VictoriaMetrics. Das bedeutet nicht, dass sie für alle Fälle geeignet ist. Wenn sie falsch verwendet wird, führt das nicht zu einer Leistungssteigerung, sondern zu einem Out-of-Memory-Fehler und einer Verlangsamung der Leistung.

Betrachten wir die Implementierung dieser Struktur. Wenn Sie schauen möchten, befindet sie sich im Quellcode von VictoriaMetrics im Ordner lib/uint64set. Sie ist speziell für den Fall von VictoriaMetrics optimiert, wo timeseries_id einen 64-Bit-Wert darstellt, wobei die ersten 32 Bits konstant sind und nur die letzten 32 Bits sich ändern.

Diese Datenstruktur wird nicht auf der Festplatte gespeichert, sie funktioniert nur im Speicher.

Hier ist ihre API. Sie ist nicht kompliziert. Die API ist genau auf das spezifische Beispiel der Nutzung von VictoriaMetrics abgestimmt. Das heißt, es gibt hier keine überflüssigen Funktionen. Hier sind die Funktionen, die VictoriaMetrics eindeutig verwendet.

Es gibt die Funktion add, die neue Werte hinzufügt. Es gibt die Funktion has, die neue Werte überprüft. Und es gibt die Funktion del, die Werte löscht. Es gibt eine Hilfsfunktion len, die die Größe der Menge zurückgibt. Die Funktion clone klont die Menge. Und die Funktion appendto wandelt dieses Set in einen Slice um. timeseries_ids.

So sieht die Implementierung dieser Datenstruktur aus. Im Set gibt es zwei Elemente:

• ItemsCount – dies ist ein Hilfsfeld, um schnell die Anzahl der Elemente im Set zurückzugeben. Man könnte auf dieses Hilfsfeld verzichten, aber es musste hier hinzugefügt werden, da VictoriaMetrics oft in seinen Algorithmen die Länge des Bitsets abfragt.

• Das zweite Feld ist buckets. Dies ist ein Slice aus der Struktur bucket32. Jede Struktur enthält hi ein Feld. Dies sind die oberen 32 Bits. Und zwei Slices — b16his und buckets aus bucket16 Strukturen.

Hier werden die oberen 16 Bits des zweiten Teils der 64-Bit-Struktur gespeichert. Und hier werden die Bitsets für die unteren 16 Bits jedes Bytes gespeichert.

Bucket64 besteht aus einem Array uint64. Die Länge wird anhand dieser Konstanten berechnet. In einem bucket16 kann maximal 2^16=65536 Bits gespeichert werden. Wenn man das durch 8 teilt, sind das 8 Kilobyte. Wenn man das noch einmal durch 8 teilt, sind das 1000 uint64 Werte. Das heißt, Bucket16 – das ist unsere 8-Kilobyte-Struktur.

Lassen Sie uns betrachten, wie eine der Methoden dieser Struktur zur Hinzufügung eines neuen Wertes implementiert ist.

Alles beginnt mit uint64 dem Wert. Wir berechnen die oberen 32 Bit, berechnen die unteren 32 Bit. Wir gehen alle bucketsdurch. Wir vergleichen die oberen 32 Bit in jedem Bucket mit dem hinzuzufügenden Wert. Und wenn sie übereinstimmen, rufen wir die Funktion add in der Struktur b32 bucketsauf. Und fügen die unteren 32 Bit dort hinzu. Und wenn dies zurückgegeben wurde, true, bedeutet das, dass wir diesen Wert dort hinzugefügt haben und wir diesen Wert nicht hatten. Wenn es zurückgibt false, bedeutet das, dass ein solcher Wert bereits vorhanden war. Dann erhöhen wir die Anzahl der Elemente in der Struktur.

Wenn wir den benötigten Bucket mit dem entsprechenden Hi-Wert nicht gefunden haben, rufen wir die Funktion addAlloc, die einen neuen Bucketzuweist, indem sie ihn in die Bucket-Struktur hinzufügt.

Dies ist die Implementierung der Funktion b32.add. Sie ähnelt der vorherigen Implementierung. Wir berechnen die oberen 16 Bit und die unteren 16 Bit.

Dann gehen wir alle oberen 16 Bit durch. Wir finden Übereinstimmungen. Und bei Übereinstimmung rufen wir die Methode add auf, die wir auf der nächsten Seite für bucket16.

und hier ist die unterste Ebene, die maximal optimiert sein sollte. Wir berechnen für uint64 die ID den Wert im Slice-Bit sowie bitmask.Dies ist die Maske für den angegebenen 64-Bit-Wert, mit der wir das Vorhandensein dieses Bits überprüfen oder es setzen können. Wir prüfen, ob dieses Bit gesetzt ist, setzen es und geben das Vorhandensein zurück. So haben wir eine Implementierung, die die Schnittoperation von IDs zeitlicher Reihen um das 10-fache im Vergleich zu gewöhnlichen Maps beschleunigt hat.

In VictoriaMetrics gibt es neben dieser Optimierung viele andere Optimierungen. Die meisten dieser Optimierungen wurden nicht grundlos hinzugefügt, sondern nach der Profilerstellung des Codes in der Produktion.

Das Hauptprinzip der Optimierung lautet – keine Optimierung hinzufügen, nur weil angenommen wird, dass hier ein Engpass besteht, denn es kann sich herausstellen, dass dort kein Engpass existiert. Optimierung verschlechtert in der Regel die Codequalität. Daher sollte man nur nach der Profilerstellung optimieren und vorzugsweise in der Produktion, damit es sich um reale Daten handelt. Wer interessiert ist, kann sich den Quellcode von VictoriaMetrics ansehen und andere Optimierungen studieren, die dort vorhanden sind.

Ich habe eine Frage zu bitset. Es ähnelt sehr der Implementierung des C++ Vektors Bool, dem optimierten bitset. Haben Sie die Implementierung von dort übernommen?

Nein, nicht von dort. Bei der Umsetzung dieses Bitsets habe ich mich an das Wissen über die Struktur dieser IDs-Zeiten orientiert, die in VictoriaMetrics verwendet werden. Ihre Struktur ist so, dass die oberen 32 Bits größtenteils konstant sind. Die unteren 32 Bits können variieren. Je niedriger das Bit, desto häufiger kann es sich ändern. Daher ist diese Implementierung speziell auf diese Datenstruktur optimiert. Die C++-Implementierung ist, soweit ich weiß, für den allgemeinen Fall optimiert. Eine Optimierung für den allgemeinen Fall bedeutet, dass sie nicht die beste Lösung für den speziellen Fall ist.

Ich empfehle Ihnen auch, den Vortrag von Alexey Milovid zu sehen. Er hat vor etwa einem Monat über Optimierungen in ClickHouse für spezielle Anforderungen gesprochen. Er erklärt genau, dass die C++-Implementierung oder eine andere Implementierung im Allgemeinen für eine gute durchschnittliche Leistung optimiert sind. Sie kann schlechter abschneiden als eine spezialisierte Implementierung für bestimmte Kenntnisse, wie bei uns, wo wir wissen, dass die oberen 32 Bits größtenteils konstant sind.

Ich habe eine zweite Frage. Was ist der grundlegende Unterschied zu InfluxDB?

Es gibt viele grundlegende Unterschiede. Im Hinblick auf Leistung und Speicherverbrauch zeigt InfluxDB in Tests 10-mal höheren Speicherverbrauch für hochkarätige Zeitreihen, wenn Sie viele davon haben, zum Beispiel Millionen. Von VictoriaMetrics benötigen 1 GB für eine Million aktiver Serien, während InfluxDB dabei 10 GB verbraucht. Und das ist ein erheblicher Unterschied.

Der zweite grundlegende Unterschied besteht darin, dass InfluxDB merkwürdige Abfragesprachen – Flux und InfluxQL – verwendet. Diese sind im Vergleich zu PromQL, das in VictoriaMetrics unterstützt wird, nicht sehr benutzerfreundlich für die Arbeit mit Zeitreihen. PromQL ist die Abfragesprache aus Prometheus.

Ein weiteres Unterscheidungsmerkmal ist, dass InfluxDB ein etwas seltsames Datenmodell hat, in dem jede Zeile mehrere Felder mit unterschiedlichen Tag-Sets speichern kann. Diese Zeilen werden weiter in verschiedene Tabellen unterteilt. Diese zusätzlichen Komplikationen erschweren die spätere Arbeit mit dieser Datenbank. Es ist schwierig, sie zu pflegen und zu verstehen.

In VictoriaMetrics ist alles viel einfacher. Jede Zeitreihe stellt ein Schlüssel-Wert-Paar dar. Der Wert ist eine Menge von Punkten – (timestamp, value), während der Schlüssel ein Satz ist. label=value. Es gibt keine Trennung zwischen Feldern und Messwerten. Das ermöglicht Ihnen, beliebige Daten auszuwählen und diese dann zu kombinieren, zu addieren, zu subtrahieren, zu multiplizieren und zu dividieren, im Gegensatz zu InfluxDB, wo Berechnungen zwischen verschiedenen Reihen meines Wissens nach noch nicht implementiert sind. Selbst wenn sie implementiert wären, wäre es kompliziert, da man eine Menge Code schreiben müsste.

Ich habe eine klärende Frage. Habe ich richtig verstanden, dass es ein Problem gab, von dem Sie erzählt haben, dass dieser invertierte Index nicht im Speicher Platz findet, weshalb das Partitionieren stattfindet?

Zuerst habe ich eine naive Implementierung des invertierten Index auf einer standardmäßigen Go-Map gezeigt. Eine solche Implementierung eignet sich nicht für Datenbanken, da dieser invertierte Index nicht auf der Festplatte gespeichert wird, und eine Datenbank muss auf die Festplatte speichern, damit diese Daten beim Neustart verfügbar bleiben. In dieser Implementierung würde der invertierte Index beim Neustart der Anwendung verloren gehen. Und Sie würden den Zugang zu allen Daten verlieren, da Sie sie nicht mehr finden könnten.

Hallo! Vielen Dank für den Vortrag! Mein Name ist Pavel. Ich komme von der Firma Wildberries. Ich habe mehrere Fragen an Sie. Die erste Frage. Glauben Sie, dass wenn Sie ein anderes Prinzip beim Entwurf der Architektur Ihrer Anwendung gewählt und die Daten nach Zeit partitioniert hätten, es Ihnen vielleicht möglich gewesen wäre, Daten bei der Suche zu kreuzen, basierend nur darauf, dass in einer Partition die Daten für einen bestimmten Zeitraum liegen, d.h. für einen Zeitintervall, und dass Sie sich nicht darum kümmern müssten, dass Ihre Teile unterschiedlich verteilt sind? Die zweite Frage — da Sie solchen Algorithmus mit Bitset und allem anderen implementieren, haben Sie vielleicht versucht, Prozessoranweisungen zu verwenden? Vielleicht haben Sie solche Optimierungen ausprobiert?

Auf die zweite Frage antworte ich sofort. Damit sind wir noch nicht so weit gekommen. Aber wenn es notwendig ist, werden wir das tun. Und die erste, was war die Frage?

Sie haben zwei Szenarien diskutiert. Und gesagt, dass Sie das zweite mit einer komplizierteren Implementierung gewählt haben. Und dass Sie das erste, wo die Daten nach Zeit partitioniert sind, nicht bevorzugt haben.

Ja. Im ersten Fall wäre das gesamte Volumen des Index größer gewesen, weil wir in jeder Partition Daten-Duplikate für die Zeitreihen speichern müssten, die sich durch all diese Partitionen ziehen. Und wenn Sie eine geringe Churn-Rate bei den Zeitreihen haben, d.h. ständig die gleichen Reihen verwendet werden, hätten wir im ersten Fall erheblich mehr Speicherplatz im Vergleich zum zweiten Fall verloren.

So ist es – ja, zeitbasierte Partitionierung ist eine gute Option. Das verwendet auch Prometheus. Aber Prometheus hat einen anderen Nachteil. Beim Zusammenführen dieser Datenstücke benötigt er viel Speicherplatz für die Metainformation über alle Labels und Zeitreihen. Daher steigt der Speicherverbrauch beim Zusammenführen von großen Datenstücken erheblich, im Gegensatz zu VictoriaMetrics. Beim Zusammenführen verbraucht VictoriaMetrics überhaupt keinen Speicher, es werden nur einige Kilobyte verwendet, unabhängig von der Größe der zusammenzuführenden Datenstücke.

Der Algorithmus, den Sie verwenden, nutzt Speicher. Dort werden Zeitreihen-Labels markiert, auf denen Werte vorhanden sind. So prüfen Sie die Paarweise Existenz in einem Datenarray und im anderen. Und Sie verstehen – gab es ein Intersect oder nicht. Normalerweise implementieren Datenbanken Cursors, Iteratoren, die ihren aktuellen Zustand speichern und durch sortierte Daten laufen, was Ihnen eine einfache Komplexität dieser Operationen ermöglicht.

Warum verwenden wir keine Cursors für das Überschneiden von Daten?

Ja.

In LevelDB oder im mergeset haben wir genau die sortierten Zeilen gespeichert. Wir könnten mit einem Cursor durchgehen und das Überschneiden finden. Aber warum benutzen wir das nicht? Weil das langsam ist. Denn Cursors implizieren, dass für jede Zeile eine Funktion aufgerufen werden muss. Der Funktionsaufruf dauert 5 Nanosekunden. Und wenn Sie 100.000.000 Zeilen haben, dann verbringen wir allein für den Funktionsaufruf eine halbe Sekunde.

Das gibt es, ja. Und ich habe eine letzte Frage. Die Frage mag vielleicht etwas seltsam klingen. Warum kann man beim Eingeben von Daten nicht alle erforderlichen Aggregationen berechnen und in der notwendigen Form speichern? Warum riesige Datenmengen in Systeme wie VictoriaMetrics, ClickHouse usw. speichern, um später viel Zeit mit ihnen zu verbringen?

Ich werde ein Beispiel geben, um es verständlicher zu machen. Angenommen, wie funktioniert ein kleiner Spielzeug-Tachometer? Er zeichnet die Strecke auf, die Sie zurückgelegt haben, und addiert sie ständig zu einer Größe, zur zweiten – die Zeit. Und teilt. Und erhält die Durchschnittsgeschwindigkeit. Man kann ungefähr das Gleiche machen. Alle notwendigen Fakten zusammenzählen.

Gut, ich habe die Frage verstanden. Ihr Beispiel ist in der Praxis relevant. Wenn Sie wissen, welche Aggregationen Sie benötigen, ist dies die beste Implementierung. Aber das Problem ist, dass die Leute diese Metriken, einige Daten in ClickHouse speichern, und sie wissen noch nicht, wie sie diese in Zukunft aggregieren oder filtern werden, deshalb müssen sie alle Rohdaten speichern. Aber wenn Sie wissen, dass Sie etwas Durchschnittliches berechnen müssen, warum sollten Sie es dann nicht berechnen, anstatt dort eine Menge Rohwerte zu speichern? Aber das gilt nur, wenn Sie genau wissen, was Sie brauchen.

Übrigens unterstützen Datenbanken zur Speicherung von Zeitserien die Berechnung von Aggregaten. Zum Beispiel unterstützt Prometheus Aufzeichnungsregeln. Das heißt, Sie können das tun, wenn Sie wissen, welche Aggregationen Sie benötigen. In VictoriaMetrics gibt es das zurzeit nicht, aber normalerweise wird Prometheus davor gesetzt, wo Sie dies in den Aufzeichnungsregeln machen können.

Zum Beispiel musste ich bei meinem vorherigen Job die Anzahl der Ereignisse in einem gleitenden Fenster der letzten Stunde zählen. Das Problem war, dass ich eine benutzerdefinierte Implementierung in Go machen musste, d. h. einen Dienst zur Zählung dieser Sache. Dieser Dienst war letztendlich nicht trivial, weil es kompliziert zu berechnen ist. Die Implementierung kann einfach sein, wenn Sie einige Aggregate in festgelegten Zeitintervallen zählen müssen. Wenn Sie jedoch Ereignisse in einem gleitenden Fenster zählen möchten, ist das nicht so einfach, wie es scheint. Ich denke, das ist bis jetzt nicht in ClickHouse oder in Zeitseriendatenbanken implementiert, weil es in der Implementierung schwierig ist.

Und noch eine Frage. Wir haben gerade über das Mittelmaß gesprochen, und ich erinnere mich daran, dass es einmal so etwas wie Graphite mit dem Backend Carbon gab. Und es konnte alte Daten verdichten, d. h. eine Punkt pro Minute, einen Punkt pro Stunde usw. beibehalten. Im Grunde ist das recht praktisch, wenn wir Rohdaten, sagen wir, für einen Monat benötigen, während alles andere verdichtet werden kann. Aber Prometheus und VictoriaMetrics unterstützen diese Funktionalität nicht. Ist geplant, das zu unterstützen? Wenn nicht, warum?

Danke für die Frage. Unsere Nutzer stellen sie gelegentlich. Sie fragen, wann wir die Unterstützung für Downsampling hinzufügen. Hier gibt es mehrere Probleme. Erstens versteht jeder Nutzer unter Downsampling etwas anderes: Manche wünschen sich einen beliebigen Punkt im angegebenen Intervall, andere möchten die maximalen, minimalen oder durchschnittlichen Werte. Wenn viele Systeme Daten in Ihre Datenbank schreiben, kann man sie nicht über einen Kamm scheren. Es kann sein, dass für jedes System unterschiedliche Downsampling-Verfahren erforderlich sind. Und das ist kompliziert umzusetzen.

Und zweitens ist es so, dass VictoriaMetrics, genau wie ClickHouse, für die Verarbeitung großer Mengen Rohdaten optimiert ist. Daher kann es eine Milliarde Zeilen in weniger als einer Sekunde verarbeiten, wenn Sie viele Kerne in Ihrem System haben. Das Scannen von Zeitreihenpunkten in VictoriaMetrics beträgt 50.000.000 Punkte pro Sekunde pro Kern. Diese Leistung skaliert mit der Anzahl der vorhandenen Kerne. Das heißt, wenn Sie zum Beispiel 20 Kerne haben, können Sie eine Milliarde Punkte pro Sekunde scannen. Diese Eigenschaft von VictoriaMetrics und ClickHouse verringert die Notwendigkeit für Downsampling.

Eine weitere Eigenschaft ist, dass VictoriaMetrics diese Daten effizient komprimiert. Die Kompression liegt im Durchschnitt im Produktivbetrieb zwischen 0,4 und 0,8 Byte pro Punkt. Jeder Punkt besteht aus einem Zeitstempel + Wert. Und er wird im Durchschnitt auf weniger als ein Byte komprimiert.

Sergey. Ich habe eine Frage. Wie groß ist das minimale Zeitquantum für die Speicherung?

Eine Millisekunde. Kürzlich hatten wir ein Gespräch mit anderen Entwicklern von Zeitreihendatenbanken. Bei ihnen liegt das minimale Zeitquantum bei einer Sekunde. Auch in Graphite beträgt es beispielsweise eine Sekunde. In OpenTSDB ebenfalls eine Sekunde. In InfluxDB gibt es nanosekundengenaue Genauigkeit. In VictoriaMetrics beträgt es eine Millisekunde, weil es in Prometheus eine Millisekunde beträgt. VictoriaMetrics wurde ursprünglich als Remote-Speicher für Prometheus entwickelt. Aber jetzt kann es auch Daten aus anderen Systemen speichern.

Die Person, mit der ich gesprochen habe, sagt, dass sie eine sekündliche Genauigkeit haben – das genügt ihnen, da dies von der Art der Daten abhängt, die in die Zeitreihe gespeichert werden. Wenn es sich um DevOps-Daten oder Daten von Infrastrukturen handelt, bei denen Sie sie alle 30 Sekunden oder einmal pro Minute sammeln, dann reicht eine sekündliche Genauigkeit aus, weniger ist nicht nötig. Wenn Sie jedoch diese Daten von Hochfrequenzhandelsystemen sammeln, benötigen Sie nanosekundengenaue Genauigkeit.

Millisekunden-Genauigkeit in VictoriaMetrics eignet sich sowohl für DevOps-Fälle als auch für die meisten der Fälle, die ich zu Beginn des Vortrags erwähnt habe. Das Einzige, wofür sie möglicherweise nicht geeignet ist, sind Hochfrequenzhandelssysteme.

Danke! Und eine weitere Frage. Wie ist die Kompatibilität in PromQL?

Vollständige Abwärtskompatibilität. VictoriaMetrics unterstützt PromQL vollständig. Darüber hinaus fügt es zusätzliche erweiterte Funktionen zu PromQL hinzu, die MetricsQLheißen. Zu dieser erweiterten Funktionalität gibt es einen Vortrag auf YouTube. Ich habe beim Monitoring Meetup im Frühling in St. Petersburg darüber gesprochen.

Telegram-Kanal VictoriaMetrics.

Nur registrierte Benutzer können an der Umfrage teilnehmen. Bitte einloggen.

Was hindert Sie daran, VictoriaMetrics als langfristigen Speicher für Prometheus zu verwenden? (Schreiben Sie in die Kommentare, ich füge es zur Umfrage hinzu))

• 71,4%Nutze Prometheus5 nicht

• 28,6%Wusste nichts über VictoriaMetrics2

7 Benutzer haben abgestimmt. 12 Benutzer haben sich enthalten.

Quelle: habr.com