🥇Optymalizacje Go w VictoriaMetrics. Aleksander Waliłkin

Zachęcam do zapoznania się z transkrypcją wystąpienia Aleksandra Waliłkina z końca 2019 roku "Optymalizacje Go w VictoriaMetrics"

VictoriaMetrics — szybka i skalowalna baza danych do przechowywania i przetwarzania danych w postaci szeregu czasowego (zapis tworzy czas oraz zbiór odpowiadających temu czasowi wartości, na przykład uzyskanych za pomocą okresowego odczytu stanu czujników lub zbierania metryk).

Oto link do wideo z tego wystąpienia — https://youtu.be/MZ5P21j_HLE

Slajdy

Zaraz opowiem coś o sobie. Nazywam się Aleksander Waliłkin. Oto moje konto GitHub. Zafascynowany jestem Go i optymalizacją wydajności. Napisałem wiele różnych przydatnych i mniej przydatnych bibliotek. Zaczynają się one od fast, albo od quick prefiksu.

Obecnie pracuję nad VictoriaMetrics. Czym jest i co tam robię? O tym opowiem w tej prezentacji.

Plan wystąpienia jest następujący:

Na początku opowiem, czym jest VictoriaMetrics.
Następnie omówię, czym są szeregi czasowe.
Potem wyjaśnię, jak działa baza danych dla szeregów czasowych.
Następnie opowiem o architekturze bazy danych: z czego się składa.
A potem przejdziemy do optymalizacji, które są w VictoriaMetrics. To optymalizacja indeksu odwróconego oraz optymalizacja dla implementacji bitset w Go.

Czy ktoś w audytorium wie, czym jest VictoriaMetrics? Nic sobie, wiele osób już wie. To dobra wiadomość. Dla tych, którzy nie wiedzą – to baza danych dla szeregów czasowych. Jest oparta na architekturze ClickHouse oraz na niektórych detalach implementacji ClickHouse. Na przykład takich jak: MergeTree, równoległe obliczenia na wszystkich dostępnych rdzeniach procesora oraz optymalizacja wydajności dzięki pracy z blokami danych, które są umieszczane w pamięci podręcznej procesora.

VictoriaMetrics zapewnia lepsze kompresję danych w porównaniu do innych baz danych dla szeregów czasowych.

Skaluje się pionowo — tzn. możesz dodawać więcej procesorów, więcej pamięci RAM na jednym komputerze. VictoriaMetrics efektywnie wykorzysta te dostępne zasoby i zwiększy liniową wydajność.

VictoriaMetrics skaluje się również poziomo — tzn. możesz dodawać dodatkowe węzły do klastra VictoriaMetrics, a jej wydajność wzrośnie prawie liniowo.

Jak się domyśliliście, VictoriaMetrics to szybka baza danych, ponieważ nie mogę pisać o innych. I jest napisana w Go, dlatego opowiadam o niej na tym meet-upie.

Kto wie, co to jest szereg czasowy? Wiele osób to wie. Szereg czasowy to seria par (timestamp, wartość), gdzie te pary są uporządkowane według czasu. Wartość to liczba zmiennoprzecinkowa – float64.

Każdy szereg czasowy jest unikalnie identyfikowany kluczem. Z czego składa się ten klucz? Składa się z niepustego zbioru par klucz-wartość.

Oto przykład szeregu czasowego. Kluczem tego szeregu jest lista par: __name__="cpu_usage" – to nazwa metryki, instance="my-server" – to komputer, na którym ta metryka została zebrana, datacenter="us-east" – to centrum danych, w którym znajduje się ten komputer.

Uzyskaliśmy nazwę szeregu czasowego, składającą się z trzech par klucz-wartość. Do tego klucza odpowiada lista par (timestamp, value). t1, t2, t3, ..., tN – to znaczniki czasu, 10, 20, 12, ..., 15 – odpowiadające wartości. To cpu-usage w danym momencie czasu dla tego szeregu.

Gdzie można wykorzystać szeregi czasowe? Czy ktoś ma jakieś pomysły?

W DevOps można mierzyć obciążenie CPU, RAM, sieci, rps, liczbę błędów itp.
IoT – możemy mierzyć temperaturę, ciśnienie, współrzędne geograficzne i inne rzeczy.
Również w finansach – możemy monitorować ceny różnych akcji i walut.
Ponadto, szeregi czasowe mogą być wykorzystywane do monitorowania procesów produkcyjnych w fabrykach. Mamy użytkowników, którzy wykorzystują VictoriaMetrics do monitorowania turbin wiatrowych, dla robotów.
Szeregi czasowe są również przydatne do zbierania informacji z czujników różnych urządzeń. Na przykład, dla silnika; do mierzenia ciśnienia w oponach; do mierzenia prędkości, dystansu; do mierzenia zużycia paliwa itp.
Szeregi czasowe mogą być także wykorzystywane do monitorowania samolotów. W każdym samolocie znajduje się czarna skrzynka, która zbiera szeregi czasowe na temat różnych parametrów stanu samolotu. Szeregi czasowe są również używane w przemyśle kosmicznym.
Ochrona zdrowia – to ciśnienie krwi, puls itp.

Może są jeszcze inne zastosowania, o których zapomniałem, ale mam nadzieję, że zrozumieliście, że szeregi czasowe są aktywnie wykorzystywane w nowoczesnym świecie. A ich zastosowanie rośnie z każdym rokiem.

Do czego potrzebna jest baza danych dla szeregów czasowych? Dlaczego nie można używać zwykłej bazy relacyjnej do przechowywania szeregów czasowych?

Ponieważ w szeregach czasowych zazwyczaj znajduje się duża ilość informacji, którą trudno przechowywać i przetwarzać w zwykłych bazach danych. Dlatego powstały specjalistyczne bazy danych do szeregów czasowych. Bazy te skutecznie przechowują punkty (timestamp, value) z określonym kluczem. Oferują interfejs API do odczytu zapisanych danych po kluczu, pojedynczej parze klucz-wartość, grupie par lub za pomocą regexp. Na przykład, jeśli chcesz znaleźć obciążenie CPU wszystkich swoich usług w centrum danych w Ameryce, musisz użyć takiego pseudo zapytania.

Zazwyczaj bazy danych do szeregów czasowych oferują specjalistyczne języki zapytań, ponieważ SQL nie nadaje się dobrze do tych zastosowań. Choć są bazy danych, które wspierają SQL, nie jest to rozwiązanie optymalne. Lepiej nadają się takie języki zapytań jak PromQL, InfluxQL, Flux, Q. Mam nadzieję, że ktoś słyszał przynajmniej o jednym z tych języków. O PromQL, prawdopodobnie, słyszało wielu. To jest język zapytań Prometheusa.

Oto jak wygląda architektura nowoczesnej bazy danych do szeregów czasowych na przykładzie VictoriaMetrics.

Składa się z dwóch części. To magazyn dla indeksu odwróconego i magazyn dla wartości szeregów czasowych. Te magazyny są oddzielone.

Kiedy przychodzi nowy zapis do bazy danych, najpierw zwracamy się do indeksu odwróconego, aby znaleźć identyfikator szeregów czasowych według danego zestawu label=value dla danej metryki. Znajdujemy ten identyfikator i zapisujemy wartość w magazynie danych.

Kiedy przychodzi jakieś zapytanie o wyciągnięcie danych z TSDB, w pierwszej kolejności zaglądamy do indeksu odwróconego. Wyciągamy wszystkie timeseries_ids zapisy, które odpowiadają danemu zestawowi. label=valueA następnie wydobywamy wszystkie niezbędne dane z magazynu danych, indeksowanych według timeseries_ids.

Zobaczmy przykład, jak baza danych do szeregów czasowych przetwarza przychodzące zapytanie select.

W pierwszej kolejności wyciąga wszystkie timeseries_ids z indeksu odwróconego, które zawierają podane pary label=value, lub spełniają określony wzór regularny.
Następnie wyciąga wszystkie punkty danych z magazynu danych w określonym przedziale czasowym dla znalezionych timeseries_ids.
Po tym baza danych przeprowadza jakieś obliczenia nad tymi punktami danych, zgodnie z zapytaniem użytkownika. A potem zwraca odpowiedź.

W tej prezentacji opowiem o pierwszej części. To jest wyszukiwanie timeseries_ids na temat indeksu inwersyjnego. O drugiej części i trzeciej części możesz później spojrzeć źródła VictoriaMetrics, albo poczekać, aż przygotuję inne prezentacje 🙂

Zacznijmy od indeksu inwersyjnego. Wielu może wydawać się, że to proste. Kto wie, co to jest indeks inwersyjny i jak działa? O, już nie tak wiele osób. Spróbujmy zrozumieć, czym to jest.

W rzeczywistości wszystko jest proste. To po prostu słownik, który mapuje klucz na wartość. Co to jest klucz? Ta para label=value, gdzie label i value to ciągi. A wartości to zestaw timeseries_ids, który zawiera daną parę label=value.

Indeks inwersyjny pozwala szybko znajdować wszystkie timeseries_ids, które mają daną label=value.

A także pozwala szybko znajdować timeseries_ids szeregów czasowych dla kilku par label=value, albo dla par label=regexp. Jak to działa? Poprzez znalezienie przecięcia zbioru timeseries_ids dla każdej pary label=value.

Rozważmy różne implementacje indeksu inwersyjnego. Zacznijmy od najprostszej naiwnej implementacji. Wygląda to tak.

veth_xdp_flush_bq() getMetricIDs uzyskuje listę ciągów. Każdy ciąg zawiera label=value. Ta funkcja zwraca listę metricIDs.

Jak to działa? Mamy globalną zmienną, która nazywa się invertedIndex. To zwykły słownik (map), który mapuje ciąg na slice int-ów. Ciąg zawiera label=value.

Implementacja funkcji: pobieramy metricIDs dla pierwszego label=value, następnie przechodzimy przez wszystkie pozostałe label=value, pobieramy metricIDs dla nich. I wywołujemy funkcję intersectInts, o której będzie mowa później. Ta funkcja zwraca przecięcie tych list.

Jak widać, implementacja indeksu inwersyjnego nie jest bardzo skomplikowana. Ale to naiwna implementacja. Jakie ma wady? Główną wadą naiwnej implementacji jest to, że taki indeks inwersyjny przechowujemy w pamięci RAM. Po ponownym uruchomieniu aplikacji tracimy ten indeks. Nie ma zapisu tego indeksu na dysku. Dla bazy danych taki indeks inwersyjny raczej się nie nada.

Drugą wadą jest również związana z pamięcią. Indeks inwersyjny musi mieścić się w pamięci RAM. Jeśli przekroczy rozmiar pamięci RAM, to oczywiście otrzymamy – błąd pamięci. I program nie będzie działał.

Ten problem można rozwiązać przy pomocy gotowych rozwiązań takich jak LevelDB, albo RocksDB.

Jeśli pokrótce, potrzebujemy bazy danych, która pozwala na szybkie wykonanie trzech operacji.

Pierwsza operacja to zapis klucz-wartość do tej bazy. Robi to bardzo szybko, gdzie klucz-wartość są to dowolne ciągi.
Druga operacja to szybkie wyszukiwanie wartości na podstawie zadanego klucza.
A trzecia operacja to szybkie wyszukiwanie wszystkich wartości na podstawie zadanego prefiksu.

LevelDB i RocksDB – te bazy zostały opracowane w Google i Facebooku. Najpierw powstała LevelDB. Potem ludzie z Facebooka wzięli LevelDB i zaczęli ją ulepszać, tworząc RocksDB. Obecnie na RocksDB w Facebooku pracują niemal wszystkie wewnętrzne bazy danych, w tym przekształcono także MySQL na RocksDB. Nazywają to MyRocks.

Indeks odwrócony można zrealizować za pomocą LevelDB. Jak to zrobić? Zapisujemy jako klucz label=value. A jako wartość – identyfikator szeregów czasowych, w których występuje para label=value.

Jeśli mamy wiele szeregów czasowych z daną parą label=value, to będzie wiele wierszy w tej bazie danych z takim samym kluczem i różnymi timeseries_ids. Aby uzyskać listę wszystkich timeseries_ids, które zaczynają się od danego label=prefix, wykonujemy skanowanie zakresu, dla którego ta baza danych jest zoptymalizowana. Tzn. wybieramy wszystkie wiersze, które zaczynają się od label=prefix i otrzymujemy potrzebne timeseries_ids.

Oto przykładowa implementacja, jak mogłaby wyglądać w Go. Mamy indeks odwrócony. To jest LevelDB.

Funkcja jest taka sama jak w naiwnej implementacji. Prawie linijka w linijkę powtarza naiwną implementację. Jedyny moment, że zamiast odwołania do map odwołujemy się do indeksu odwróconego. Wyciągamy wszystkie wartości dla pierwszej label=value. Potem przechodzimy przez wszystkie pozostałe pary label=value i wyciągamy odpowiednie zestawy metricIDs dla nich. Następnie znajdujemy przecięcia.

Wydaje się, że wszystko jest w porządku, ale w tym rozwiązaniu są wady. VictoriaMetrics na początku zaimplementowała indeks odwrócony na podstawie LevelDB. Ale ostatecznie musiała z niego zrezygnować.

Dlaczego? Ponieważ LevelDB jest wolniejsza niż naiwna implementacja. W naiwnym podejściu na podstawie zadanego klucza od razu wyciągamy cały slice metricIDs. To bardzo szybka operacja — cały slice jest gotowy do użycia.

W LevelDB natomiast przy każdym wywołaniu funkcji GetValues trzeba przejść przez wszystkie wiersze, które zaczynają się od label=value. I dla każdego wiersza wyciągnąć wartość timeseries_ids. Z takich timeseries_ids zebrać slice tych timeseries_ids. Oczywiście, że to znacznie wolniejsze niż po prostu odwołanie się do zwykłego mapy wg klucza.

Drugą wadą jest to, że LevelDB jest napisany w C. Wywołanie funkcji C z Go nie jest zbyt szybkie. Zajmuje to setki nanosekund. To nie jest bardzo szybkie, ponieważ w porównaniu z typowym wywołaniem funkcji napisanej w Go, które zajmuje 1-5 nanosekund, różnica w wydajności wynosi dziesiątki razy. Dla VictoriaMetrics była to tragiczna wada 🙂

Dlatego napisałem własną implementację indeksu odwróconego. Nazwałem ją mergeset.

Mergeset oparty jest na strukturze danych MergeTree. Ta struktura danych została zapożyczona z ClickHouse. Oczywiście, że mergeset musi być optymalizowany do szybkiego wyszukiwania timeseries_ids na podstawie określonego klucza. Mergeset jest napisany w całości w Go. Możesz zobaczyć źródła VictoriaMetrics na GitHubie. Implementacja mergeset znajduje się w folderze /lib/mergeset. Możesz spróbować zrozumieć, co tam się dzieje.

API mergeset jest bardzo podobne do LevelDB i RocksDB. T. j. pozwala szybko zapisać nowe rekordy i szybko wybierać rekordy na podstawie określonego prefiksu.

O wadach mergeset porozmawiamy później. Teraz omówimy problemy, jakie wystąpiły z VictoriaMetrics w produkcji przy realizacji indeksu odwróconego.

Dlaczego się pojawiły?

Pierwszą przyczyną jest wysoka rotacja. W tłumaczeniu na polski – to częsta zmiana szeregów czasowych. To wtedy szereg czasowy kończy się, a zaczyna nowy, lub zaczyna się wiele nowych szeregów czasowych. I dzieje się to często.

Drugą przyczyną jest duża liczba szeregów czasowych. Na początku, gdy monitorowanie zyskiwało na popularności, liczba szeregów czasowych była mała. Na przykład, na każdy komputer trzeba monitorować obciążenie procesora, pamięci, sieci i dysku. 4 szeregi czasowe na każdy komputer. Powiedzmy, że masz 100 komputerów i 400 szeregów czasowych. To bardzo mało.

Z czasem ludzie wymyślili, że można mierzyć bardziej szczegółowe informacje. Na przykład, mierzyć obciążenie nie całego procesora, ale oddzielnie każdego rdzenia procesora. Jeśli masz 40 rdzeni procesora, to odpowiednio pojawia się 40 razy więcej szeregów czasowych do pomiaru obciążenia procesora.

Ale to nie wszystko. Każde jądro procesora może mieć kilka stanów, takich jak idle, kiedy jest nieaktywne. A także praca w przestrzeni użytkownika, praca w przestrzeni jądra i inne stany. I każdy z tych stanów również można mierzyć jako oddzielny szereg czasowy. To dodatkowo zwiększa liczbę szeregów o 7-8 razy.

Z jednej metryki uzyskaliśmy 40 x 8 = 320 metryk tylko na jeden komputer. Mnożymy przez 100, otrzymujemy 32 000 zamiast 400.

Potem pojawił się Kubernetes. I sytuacja się pogorszyła, ponieważ w Kubernetes może być hostowanych wiele różnych usług. Każda usługa w Kubernetes składa się z wielu podów. Wszystko to trzeba monitorować. Dodatkowo mamy stały deployment nowych wersji twoich usług. Dla każdej nowej wersji trzeba tworzyć nowe szeregi czasowe. W efekcie liczba szeregów czasowych rośnie wykładniczo i stajemy przed problemem dużej liczby szeregów czasowych, który nazywa się high-cardinality. VictoriaMetrics skutecznie radzi sobie z tym w porównaniu z innymi bazami danych dla szeregów czasowych.

Przyjrzyjmy się bliżej high churn rate. Z jakich powodów pojawia się high churn rate w produkcji? Ponieważ niektóre wartości etykiet i tagów stale się zmieniają.

Na przykład weźmy Kubernetes, w którym istnieje pojęcie deployment, tj. kiedy wprowadzana jest nowa wersja twojej aplikacji. Twórcy Kubernetes z jakiegoś powodu postanowili dodać id deploymentu do etykiety.

Do czego to doprowadziło? Do tego, że przy każdym nowym deploymencie wszystkie stare szeregi czasowe są przerywane, a zamiast nich zaczynają się nowe szeregi czasowe z nową wartością etykiety deployment_id. Takich szeregów może być setki tysięcy, a nawet miliony.

Ważną cechą całej tej sytuacji jest to, że całkowita liczba szeregów czasowych rośnie, ale liczba aktywnych szeregów czasowych, na które spływają dane, pozostaje stała. Taki stan nazywa się high churn rate.

Głównym problemem high churn rate jest zapewnienie stałej prędkości wyszukiwania wszystkich szeregów czasowych zgodnie z określonym zestawem etykiet w danym przedziale czasowym. Zazwyczaj jest to przedział czasowy za ostatnią godzinę lub ostatni dzień.

Jak rozwiązać ten problem? Oto pierwszy wariant. Jest to podzielenie indeksu odwrotnego na niezależne części w czasie. Tzn. mija jakiś okres czasu, kończymy pracę z bieżącym indeksem odwrotnym i tworzymy nowy indeks odwrotny. Mija kolejny okres czasu, tworzymy jeszcze jeden i jeszcze jeden.

Podczas odpytywania tych indeksów odwrotnych znajdujemy zbiór indeksów odwrotnych, które mieszczą się w określonym przedziale. I odpowiednio wybieramy stamtąd identyfikatory szeregów czasowych.

To pozwala zaoszczędzić zasoby, ponieważ nie musimy przeglądać części, które nie mieszczą się w określonym przedziale. Tzn. zazwyczaj, jeśli wybieramy dane za ostatnią godzinę, to pominamy zapytania z wcześniejszych przedziałów czasowych.

Jest jeszcze jedna opcja rozwiązania tego problemu. To przechowywanie dla każdego dnia oddzielnej listy identyfikatorów szeregów czasowych, które pojawiły się w tym dniu.

Zaletą tego rozwiązania w porównaniu do poprzedniego jest to, że nie duplikujemy informacji o szeregach czasowych, które nie znikają z upływem czasu. One są stale dostępne i się nie zmieniają.

Wadą jest to, że takie rozwiązanie jest trudniejsze w realizacji i w debugowaniu. I VictoriaMetrics wybrała to rozwiązanie. Tak się złożyło historycznie. To rozwiązanie również sprawdza się nieźle w porównaniu do poprzedniego. Ponieważ to rozwiązanie nie zostało zrealizowane z powodu potrzeby duplikacji danych w każdej partycji dla szeregów czasowych, które się nie zmieniają, tzn. które nie znikają z upływem czasu. VictoriaMetrics była przede wszystkim zoptymalizowana pod kątem zużycia przestrzeni dyskowej, a poprzednia realizacja pogarszała zużycie przestrzeni dyskowej. Natomiast ta realizacja lepiej nadaje się do minimalizacji zużycia przestrzeni dyskowej, dlatego została wybrana.

Trzeba było z nią walczyć. Walka polegała na tym, że w tej realizacji trzeba było mimo wszystko wybierać znacznie większą ilość timeseries_ids danych, niż gdy indeks odwrotny jest podzielony w czasie.

Jak rozwiązaliśmy ten problem? Rozwiązaliśmy go w oryginalny sposób – poprzez zapisanie kilku identyfikatorów szeregów czasowych w każdym wpisie indeksu odwrotnego zamiast jednego identyfikatora. Tzn. mamy klucz label=value, który występuje w każdym szereg czasowym. Teraz przechowujemy kilka timeseries_ids w jednym rekordzie.

Oto przykład. Wcześniej mieliśmy N rekordów, a teraz mamy jeden rekord, którego prefiks jest taki sam jak w przypadku wszystkich innych. W poprzednim rekordzie wartość zawiera wszystkie id szeregów czasowych.

To pozwoliło zwiększyć prędkość skanowania takiego odwróconego indeksu do 10 razy. I pozwoliło to zmniejszyć zużycie pamięci na cache, ponieważ teraz przechowujemy ciąg label=value tylko raz w cache zamiast N razy. Ten ciąg może być duży, jeśli w tagach i etykietach są długie ciągi, które lubi tam wkładać Kubernetes.

Inną opcją przyspieszenia wyszukiwania w odwróconym indeksie jest sharding. Tworzenie kilku odwróconych indeksów zamiast jednego i shardowanie danych między nimi według klucza. To zestaw klucz=wartość par. To znaczy, że otrzymujemy kilka niezależnych odwróconych indeksów, które możemy przeszukiwać równolegle na kilku procesorach. Poprzednie implementacje pozwalały działać tylko w trybie jednoproc, to znaczy skanować dane tylko na jednym rdzeniu. To rozwiązanie pozwala skanować dane jednocześnie na kilku rdzeniach, tak jak lubi to robić ClickHouse. Plan mamy to zrealizować.

A teraz wróćmy do naszego sedna sprawy — do funkcji przecięcia timeseries_ids. Zobaczmy, jakie mogą być implementacje. Ta funkcja pozwala znajdować timeseries_ids dla określonego zestawu label=value.

Pierwsza opcja to naiwna implementacja. Dwa zagnieżdżone pętle. Oto wprowadzenie do funkcji intersectInts dwa slices — a i b. Na wyjściu powinna nam zwrócić przecięcie tych slices.

Naiwna implementacja wygląda tak. Przechodzimy przez wszystkie wartości z slice a, wewnątrz tej pętli przechodzimy przez wszystkie wartości slice b. I porównujemy je. Jeśli się zgadzają, oznacza to, że znaleźliśmy przecięcie. I zapisujemy to w result.

Jakie są wady? Kwadratowa złożoność — to jej główna wada. Na przykład, jeśli rozmiary slice a i b mają po milionie, to ta funkcja nigdy nie zwróci ci odpowiedzi. Ponieważ potrzebuje wykonać trylion iteracji, co jest bardzo dużo, nawet dla nowoczesnych komputerów.

Druga implementacja opiera się na mapie. Tworzymy mapę. Umieszczamy w tej mapie wszystkie wartości z slice a. Następnie przechodzimy oddzielną pętlą przez slice b. I sprawdzamy — czy ta wartość z slice istnieje b w map. Jeśli jest, to dodajemy go do wyniku.

Jakie są zalety? Zaletą jest to, że tutaj występuje tylko liniowa złożoność. To znaczy, że funkcja wykona się znacznie szybciej dla dużych rozmiarów slices. Dla rozmiaru slice wynoszącego milion ta funkcja wykona się w 2 milionach iteracji, w przeciwieństwie do biliona iteracji, jak w poprzedniej funkcji.

A wadą jest to, że ta funkcja wymaga więcej pamięci, aby stworzyć tę mapę.

Drugą wadą jest duży overhead związany z haszowaniem. Ta wada nie jest zbyt oczywista. Dla nas również nie była bardzo oczywista, więc na początku w VictoriaMetrics implementacja intersection była za pomocą map. Ale późniejsze profilowanie pokazało, że główny czas procesora był poświęcany na zapis do mapy i sprawdzanie obecności wartości w tej mapie.

Dlaczego w tych miejscach marnuje się czas procesora? Ponieważ w tych linijkach Go wykonuje operację haszowania. To znaczy, że oblicza hash klucza, aby następnie odwołać się do określonego indeksu w HashMap. Operacja obliczania hasha wykonuje się w dziesiątkach nanosekund. To jest wolne dla VictoriaMetrics.

Postanowiłem zaimplementować bitset, zoptymalizowany specjalnie na tę okazję. Oto jak teraz wygląda przecięcie dwóch slices. Tu tworzymy bitset. Dodajemy do niego elementy z pierwszego slice. Następnie sprawdzamy obecność tych elementów w drugim slice. I dodajemy je do wyniku. To znaczy, że praktycznie nie różni się od poprzedniego przykładu. Jedyną różnicą jest to, że tutaj zastąpiliśmy odwołanie do mapy funkcjami niestandardowymi. add i has.

Na pierwszy rzut oka wydaje się, że powinno to działać wolniej, jeśli wcześniej używano standardowej mapy, a teraz wywoływane są jakieś funkcje, ale profilowanie pokazuje, że to działa 10 razy szybciej niż standardowa mapa w przypadku VictoriaMetrics.

Dodatkowo używa dużo mniej pamięci w porównaniu z implementacją opartej na mapie. Ponieważ przechowujemy tutaj bity zamiast ośmiobajtowych wartości.

Wadą takiej implementacji jest to, że nie jest ona tak oczywista, nie jest trywialna.

Kolejną wadą, którą wiele osób może przeoczyć, jest to, że to wdrożenie może działać źle w niektórych przypadkach. To znaczy, że jest zoptymalizowane dla konkretnego przypadku, dla tego przypadku przecięcia identyfikatorów czasowych VictoriaMetrics. Nie oznacza to, że będzie odpowiednie dla wszystkich sytuacji. Jeśli zostanie źle użyte, zamiast poprawy wydajności uzyskamy błąd out of memory i spowolnienie działania.

Rozważmy wdrożenie tej struktury. Jeśli chcesz zobaczyć, znajduje się w źródłach VictoriaMetrics, w folderze lib/uint64set. Jest zoptymalizowane dokładnie pod kątem VictoriaMetrics, gdzie timeseries_id reprezentuje 64-bitową wartość, gdzie pierwsze 32 bity są stałe, a zmieniają się tylko ostatnie 32 bity.

Ta struktura danych nie jest przechowywana na dysku, działa tylko w pamięci.

Oto jej API. Nie jest ono zbyt skomplikowane. API jest dostosowane dokładnie do konkretnego przypadku użycia VictoriaMetrics. To znaczy, że nie ma zbędnych funkcji. Tutaj znajdują się funkcje, które są wyraźnie używane przez VictoriaMetrics.

Jest funkcja add, która dodaje nowe wartości. Jest funkcja has, która sprawdza nowe wartości. I jest funkcja del, która usuwa wartości. Jest pomocnicza funkcja len, która zwraca rozmiar zbioru. Funkcja clone klonuje zbiór. I funkcja appendto przekształca ten zbiór w slice. timeseries_ids.

Oto jak wygląda implementacja tej struktury danych. W zbiorze są dwa elementy:

ItemsCount – to pole pomocnicze, aby szybko zwrócić liczbę elementów w zbiorze. Można by obejść się bez tego pola pomocniczego, ale musiano je dodać tutaj, ponieważ VictoriaMetrics często sprawdza długość bitsetu w swoich algorytmach.
Drugie pole to buckets. To slice ze struktury bucket32.W każdej strukturze przechowywane jest hi pole. To górne 32 bity. I dwa slice — b16his i buckets z bucket16 struktur.

Tutaj przechowywane są górne 16 bitów drugiej części 64-bitowej struktury. A tutaj znajdują się bitsety dla niższych 16 bitów każdego bajtu.

Bucket64 składa się z tablicy uint64.Długość oblicza się przy pomocy tych konstant. W jednym bucket16 maksimum może być przechowywane 2^16=65536 bitów. Jeśli podzielimy to przez 8, to mamy 8 kilobajtów. Jeśli podzielimy jeszcze raz przez 8, to mamy 1000 uint64. wartości. To znaczy, że Bucket16 to 8-kilobajtowa struktura.

Rozważmy, jak zaimplementowano jedną z metod tej struktury dodawania nowej wartości.

Wszystko zaczyna się od uint64. wartości. Obliczamy górne 32 bity, obliczamy dolne 32 bity. Przechodzimy przez wszystkie buckets. Porównujemy górne 32 bity w każdym kubełku z dodawaną wartością. A jeśli się zgadzają, wywołujemy funkcję add w strukturze b32 buckets. I dodajemy tam dolne 32 bity. A jeśli to zwróciło true, to znaczy, że dodaliśmy taką wartość i wcześniej nie mieliśmy jej. Jeśli zwraca false, to taka wartość już istniała. Następnie zwiększamy liczbę elementów w strukturze.

Jeśli nie znaleźliśmy potrzebnej bucket z odpowiednią wartością hi, wywołujemy funkcję addAlloc, która przydziela nowy bucket, dodając go do struktury kubełków.

To realizacja funkcji b32.add. Jest podobna do poprzedniej realizacji. Obliczamy starsze 16 bitów, młodsze 16 bitów.

Potem przechodzimy przez wszystkie górne 16 bitów. Znajdujemy dopasowania. A w przypadku dopasowania wywołujemy metodę add, którą omówimy na następnej stronie dla bucket16.

I oto najniższy poziom, który powinien być maksymalnie zoptymalizowany. Obliczamy dla uint64. id wartość w slice bit oraz bitmask. To maska dla tej 64-bitowej wartości, na podstawie której można sprawdzić obecność tego bitu lub go ustawić. Sprawdzamy obecność tego bitu, ustawionego i ustawiamy go, a następnie zwracamy obecność. Oto taka realizacja, która umożliwiła przyspieszenie operacji przecięcia ids szeregów czasowych 10 razy w porównaniu do zwykłych map.

W VictoriaMetrics oprócz tej optymalizacji istnieje wiele innych optymalizacji. Większość z tych optymalizacji została dodana nie bez powodu, a po profilowaniu kodu w produkcji.

To główna zasada optymalizacji - nie dodawać optymalizacji, zakładając, że tutaj będzie wąskie miejsce, ponieważ może okazać się, że tam wąskiego miejsca nie ma. Optymalizacja zazwyczaj pogarsza jakość kodu. Dlatego warto optymalizować tylko po profilowaniu, a najlepiej w produkcji, aby miały to rzeczywiste dane. Kto jest zainteresowany, może zajrzeć do źródeł VictoriaMetrics i zbadać inne optymalizacje, które tam są.

Mam pytanie dotyczące bitset. Bardzo przypomina implementację C++ vector bool, zoptymalizowany bitset. Czy wzięliście stamtąd tę realizację?

Nie, nie stamtąd. Przy realizacji tego bitsetu opierałem się na wiedzy o strukturze tych identyfikatorów czasowych, które są wykorzystywane w VictoriaMetrics. Ich struktura jest taka, że górne 32 bity są głównie stałe. Dolne 32 bity mogą się zmieniać. Im niższy bit, tym częściej może się zmieniać. Dlatego ta realizacja jest dokładnie zoptymalizowana pod tę strukturę danych. Implementacja w C++, o ile wiem, jest zoptymalizowana pod ogólny przypadek. Jeśli dokonuje się optymalizacji pod ogólny przypadek, to oznacza, że nie będzie ona najbardziej optymalna dla konkretnego przypadku.

Zalecam również zapoznanie się z prezentacją Aleksieja Miłowida. Mówił około miesiąca temu o optymalizacjach w ClickHouse pod konkretne specjalizacje. Właśnie wskazuje, że w ogólnym przypadku implementacja w C++ lub jakakolwiek inna implementacja jest dostosowana do dobrej pracy średnio w szpitalu. Może działać gorzej niż specjalizowana implementacja, jak w naszym przypadku, gdy wiemy, że górne 32 bity są głównie stałe.

Mam drugie pytanie. Jaka jest fundamentalna różnica w porównaniu do InfluxDB?

Istnieje wiele zasadniczych różnic. Jeśli chodzi o wydajność i zużycie pamięci, to InfluxDB w testach wykazuje dziesięciokrotnie wyższe zużycie pamięci dla wzorców czasowych o dużej kardynalności, gdy jest ich dużo, na przykład miliony. Na przykład VictoriaMetrics zużywa 1 GB na milion aktywnych serii, podczas gdy InfluxDB zużywa 10 GB. To jest duża różnica.

Drugą fundamentalną różnicą jest to, że w InfluxDB występują dziwne języki zapytań – Flux i InfluxQL. Nie są one zbyt wygodne do pracy z szeregami czasowymi w porównaniu z PromQL, który jest obsługiwany w VictoriaMetrics. PromQL to język zapytań w Prometheus.

I jeszcze jedna różnica – to, że InfluxDB ma nieco dziwny model danych, w którym w każdej linii może być przechowywanych kilka fields z różnymi zestawami tagów. Te linie dzielą się jeszcze na różne tabele. Te dodatkowe komplikacje utrudniają późniejszą pracę z tą bazą. Jest trudno ją utrzymywać i rozumieć.

W VictoriaMetrics wszystko jest znacznie prostsze. Tam każdy szereg czasowy przedstawia parę klucz-wartość. Wartość to zestaw punktów – (timestamp, value), a klucz to zestaw label=value. Nie ma żadnego podziału na pola i pomiary. Umożliwia to wybieranie dowolnych danych, a następnie ich łączenie, dodawanie, odejmowanie, mnożenie, dzielenie, co różni się od InfluxDB, gdzie obliczenia między różnymi wierszami wciąż nie są zrealizowane, o ile mi wiadomo. Nawet jeśli byłyby zrealizowane, to są skomplikowane i wymagałyby napisania dużej ilości kodu.

Mam pytanie do wyjaśnienia. Czy dobrze zrozumiałem, że był jakiś problem, o którym mówiłeś, że ten odwrócony indeks nie mieści się w pamięci, przez co stosujecie partycjonowanie?

Na początku pokazałem naiwne wdrożenie odwróconego indeksu na standardowej mapie Go. Takie wdrożenie nie nadaje się do baz danych, ponieważ ten odwrócony indeks nie jest zapisywany na dysku, a baza danych musi przechowywać dane na dysku, aby po restarcie pozostały one dostępne. W tej implementacji po restarcie aplikacji odwrócony indeks zniknie, a Ty stracisz dostęp do wszystkich danych, ponieważ nie będziesz w stanie ich znaleźć.

Cześć! Dziękuję za prezentację! Nazywam się Pawel. Jestem z firmy Wildberries. Mam do Ciebie kilka pytań. Pierwsze pytanie. Jak uważasz, gdybyś wybrał inną zasadę przy budowie architektury swojej aplikacji i partycjonował dane według czasu, to być może udałoby Ci się przeprowadzać przecięcia danych podczas wyszukiwania, opierając się wyłącznie na tym, że w jednej partycji znajdują się dane za jeden okres czasu, tzn. za jeden przedział czasu i nie musiałbyś się martwić, że kawałki są różnie rozrzucone? Drugie pytanie — skoro wdrażasz podobny algorytm z bitsetem i wszystkim innym, to być może próbowałeś używać instrukcji procesora? Może próbowałeś takich optymalizacji?

Na drugie od razu odpowiem. Jeszcze do tego nie doszliśmy. Ale jeśli będzie trzeba, dojdziemy. A pierwsze, jakie było pytanie?

Dyskutowałeś o dwóch scenariuszach. I powiedziałeś, że wybrałeś drugi z bardziej skomplikowaną implementacją. A pierwszy, gdzie dane są partycjonowane według czasu, Cię nie interesował.

Tak. W pierwszym przypadku całkowity rozmiar indeksu byłby większy, ponieważ w każdej partycji musielibyśmy przechowywać duplikaty danych dla tych wszystkich szeregów czasowych, które przechodzą przez wszystkie te partycje. A jeśli wskaźnik churn dla szeregów czasowych jest niski, tzn. stale używane są te same szeregi, to w pierwszym przypadku znacznie bardziej stracilibyśmy na zajmowanej przestrzeni dyskowej w porównaniu do drugiego przypadku.

Zgadza się, partycjonowanie według czasu to dobry wybór. Używa go Prometheus. Ale w Prometheus jest inna wada. Podczas łączenia tych fragmentów danych wymaga trzymania w pamięci informacji meta na temat wszystkich etykiet i szeregów czasowych. Dlatego, jeśli fragmenty danych są duże, które on łączy, to zużycie pamięci znacznie wzrasta w trakcie tego procesu, w przeciwieństwie do VictoriaMetrics. Podczas łączenia VictoriaMetrics w ogóle nie zużywa pamięci, tam zużycie wynosi kilka kilobajtów, niezależnie od rozmiarów łączonych fragmentów danych.

Algorytm, który używacie, korzysta z pamięci. W niej zaznaczane są etykiety szeregów czasowych, dla których istnieją wartości. W ten sposób sprawdzacie, czy występuje współistnienie w jednej i drugiej tablicy danych. I rozumiecie – czy wystąpiło przecięcie, czy nie. Zwykle w bazach danych wdrażane są kursory, iteratory, które przechowują swoje bieżące stany i poruszają się po posortowanych danych, co zapewnia prostą złożoność tych operacji.

Dlaczego nie używamy kursorów do przecięcia danych?

Tak.

W LevelDB lub w mergeset przechowywane są właśnie posortowane wiersze. Możemy przejść kursorem i znaleźć przecięcie. A dlaczego tego nie robimy? Ponieważ to jest wolne. Ponieważ kursory sugerują, że dla każdego wiersza należy wywołać funkcję. Wywołanie funkcji to 5 nanosekund. A jeśli macie 100 000 000 wierszy, to okazuje się, że tracimy pół sekundy tylko na wywołanie funkcji.

Tak, to prawda. I mam ostatnie pytanie. Pytanie może brzmieć nieco dziwnie. Dlaczego w momencie przyjęcia danych nie można od razu obliczyć wszystkich niezbędnych agregatów i zapisać ich w wymaganej formie? Po co przechowywać ogromne ilości w różnych systemach, takich jak VictoriaMetrics, ClickHouse itd., aby później marnować na nie wiele czasu?

Podam przykład, aby to było jaśniejsze. Załóżmy, jak działa mały, zabawkowy licznik prędkości? Rejestruje on odległość, którą przejechałeś, cały czas dodając ją do jednej wielkości, a do drugiej – czas. I dzieli. A potem uzyskuje średnią prędkość. Można zrobić podobnie. Zbierać wszystkie niezbędne fakty na bieżąco.

Dobrze, rozumiem pytanie. Twój przykład ma sens. Jeśli wiesz, jakie agregaty potrzebujesz, to jest to najlepsza realizacja. Ale problem w tym, że ludzie przechowują te metryki, jakieś dane w ClickHouse i nie wiedzą jeszcze, jak będą je w przyszłości agregować czy filtrować, więc muszą przechowywać wszystkie surowe dane. Ale jeśli wiesz, że potrzebujesz obliczyć coś średniego, to dlaczego nie obliczyć tego, zamiast przechowywać tam mnóstwo surowych wartości? Ale to tylko wtedy, gdy dokładnie wiesz, co jest ci potrzebne.

Zresztą, bazy do przechowywania szeregów czasowych wspierają liczenie agregatów. Na przykład, Prometheus wspiera reguły rejestracji. To znaczy, można to zrobić, jeśli wiesz, jakie agregaty będą ci potrzebne. W VictoriaMetrics na razie tego nie ma, ale zazwyczaj przed nią stawia się Prometheus, w którym można to zrobić w regułach rejestracji.

Na przykład, w mojej poprzedniej pracy trzeba było liczyć liczbę zdarzeń w oknie przesuwającym się za ostatnią godzinę. Problem w tym, że musiałem stworzyć niestandardową realizację w Go, to znaczy serwis do liczenia tej rzeczy. Ten serwis był ostatecznie nieprosty, ponieważ liczenie tego jest skomplikowane. Realizacja może być prosta, jeśli potrzebujesz liczyć jakieś agregaty w stałych przedziałach czasowych. Jeśli jednak chcesz liczyć zdarzenia w oknie przesuwającym się, to nie jest to tak proste, jak się wydaje. Myślę, że to nadal nie jest zrealizowane w ClickHouse ani w bazach danych czasowych, ponieważ jest to skomplikowane do realizacji.

I jeszcze jedno pytanie. Teraz rozmawialiśmy o średniej, a przypomniałem sobie, że kiedyś istniał taki system jak Graphite z backendem Carbon. Potrafił on odrzucać stare dane, to znaczy zostawiać jeden punkt na minutę, jeden punkt na godzinę itd. W zasadzie, to dość wygodne, jeśli potrzebujemy surowych danych, powiedzmy, za miesiąc, a wszystko inne można odrzucić. Ale Prometheus i VictoriaMetrics tej funkcjonalności nie wspierają. Czy planuje się wprowadzenie wsparcia dla tego? Jeśli nie, to dlaczego?

Dziękujemy za pytanie. Nasi użytkownicy często je zadają. Pytają, kiedy dodamy wsparcie dla próbkowania (downsampling). Jest kilka problemów. Po pierwsze, każdy użytkownik rozumie pod downsampling to coś innego: niektórzy chcą uzyskać dowolny punkt w zadanym przedziale, inni potrzebują wartości maksymalne, minimalne lub średnie. Jeśli w Twojej bazie danych dane piszą różne systemy, nie można ich łączyć w jedną całość. Może się okazać, że dla każdego systemu należy zastosować inne próbkowanie. A to jest trudne do zrealizowania.

A po drugie – to, że VictoriaMetrics, podobnie jak ClickHouse, jest zoptymalizowana do pracy z dużymi zbiorami surowych danych, dlatego może przetworzyć miliard wierszy w mniej niż sekundę, jeśli masz wiele rdzeni w swoim systemie. Skanowanie punktów szeregów czasowych w VictoriaMetrics – 50 000 000 punktów na sekundę na jeden rdzeń. I ta wydajność skaluję się w zależności od dostępnych rdzeni. Tzn. jeśli masz na przykład 20 rdzeni, to uda się przeskanować miliard punktów na sekundę. Ta cecha VictoriaMetrics i ClickHouse zmniejsza zapotrzebowanie na downsampling.

Kolejną cechą jest to, że VictoriaMetrics efektywnie kompresuje te dane. Kompresja w średniej produkcji wynosi od 0,4 do 0,8 bajta na punkt. Każdy punkt to timestamp + wartość. I średnio kompresuje się poniżej jednego bajta.

Sergie. Mam pytanie. Jaki jest minimalny kwant czasu zapisu?

Jedna milisekunda. Niedawno rozmawialiśmy z innymi deweloperami baz danych dla szeregów czasowych. U nich minimalny kwant czasu to jedna sekunda. W Graphite na przykład również jedna sekunda. W OpenTSDB także jedna sekunda. W InfluxDB – precyzja nanosekundowa. W VictoriaMetrics – jedna milisekunda, ponieważ w Prometheus jest jedna milisekunda. VictoriaMetrics była rozwijana jako zdalna przestrzeń do przechowywania dla Prometheus na początku. Ale teraz może przechowywać dane również z innych systemów.

Osoba, z którą rozmawiałem, mówi, że mają precyzję sekundy – to im wystarcza, ponieważ to zależy od rodzaju danych, które są zapisywane w bazie szeregów czasowych. Jeśli to są dane DevOps lub dane z infrastruktury, gdzie zbierasz je co 30 sekund, co minutę, to precyzja sekundy jest wystarczająca, mniej nie jest potrzebne. A jeśli zbierasz te dane z systemów handlu wysokoczęstotliwościowego, to tam potrzebna jest precyzja nanosekundowa.

Milisekundowa precyzja w VictoriaMetrics nadaje się zarówno do przypadków użycia DevOps, jak i do większości przypadków, które wspomniałem na początku prezentacji. Jedynym przypadkiem, w którym może nie być odpowiednia, są systemy handlu wysokiej częstotliwości.

Dziękuję! I jeszcze jedno pytanie. Jaka jest kompatybilność w PromQL?

Pełna kompatybilność wsteczna. VictoriaMetrics wspiera w pełni PromQL. Dodatkowo dodaje jeszcze dodatkową rozszerzoną funkcjonalność do PromQL, która nazywa się MetricsQL. W tej sprawie jest prezentacja na YouTube. Opowiadałem o tym na Monitoring Meetup wiosną w Petersburgu.

Kanał Telegram VictoriaMetrics.

Tylko zarejestrowani użytkownicy mogą brać udział w ankiecie. Zaloguj się, proszę.