Ga voor optimalisaties in VictoriaMetrics. Alexander Valyalkin

Ik stel voor dat u het transcript leest van het rapport van eind 2019 van Alexander Valyalkin “Go Optimizations in VictoriaMetrics”

VictoriaMetrics — een snel en schaalbaar DBMS voor het opslaan en verwerken van gegevens in de vorm van een tijdreeks (het record vormt de tijd en een reeks waarden die overeenkomen met deze tijd, bijvoorbeeld verkregen door periodieke opvraging van de status van sensoren of het verzamelen van statistieken).

Hier is een link naar de video van dit rapport - https://youtu.be/MZ5P21j_HLE

Dia's

Vertel ons over jezelf. Ik ben Alexander Valyalkin. Hier mijn GitHub-account. Ik ben gepassioneerd door Go en prestatie-optimalisatie. Ik heb veel nuttige en niet erg nuttige bibliotheken geschreven. Ze beginnen met een van beide fast, of met quick voorvoegsel.

Momenteel werk ik aan VictoriaMetrics. Wat is het en wat doe ik daar? Hierover zal ik het hebben in deze presentatie.

De opzet van het rapport is als volgt:

• Eerst zal ik je vertellen wat VictoriaMetrics is.
• Dan zal ik je vertellen wat tijdreeksen zijn.
• Dan vertel ik je hoe een tijdreeksdatabase werkt.
• Vervolgens vertel ik je over de databasearchitectuur: waaruit deze bestaat.
• En laten we dan verder gaan met de optimalisaties die VictoriaMetrics heeft. Dit is een optimalisatie voor de omgekeerde index en een optimalisatie voor de bitsetimplementatie in Go.

Weet iemand in het publiek wat VictoriaMetrics is? Wauw, veel mensen weten het al. Het is goed nieuws. Voor degenen die het niet weten: dit is een tijdreeksdatabase. Het is gebaseerd op de ClickHouse-architectuur en op enkele details van de ClickHouse-implementatie. Bijvoorbeeld op: MergeTree, parallelle berekening op alle beschikbare processorcores en prestatie-optimalisatie door te werken aan datablokken die in de processorcache worden geplaatst.

VictoriaMetrics biedt betere datacompressie dan andere tijdreeksdatabases.

Het schaalt verticaal - dat wil zeggen dat u meer processors en meer RAM op één computer kunt toevoegen. VictoriaMetrics zal deze beschikbare middelen met succes gebruiken en de lineaire productiviteit verbeteren.

VictoriaMetrics schaalt ook horizontaal, dat wil zeggen dat u extra knooppunten aan het VictoriaMetrics-cluster kunt toevoegen, waardoor de prestaties vrijwel lineair zullen toenemen.

Zoals je al geraden had, is VictoriaMetrics een snelle database, omdat ik anderen niet kan schrijven. En het is geschreven in Go, dus ik heb het erover tijdens deze bijeenkomst.

Wie weet wat een tijdreeks is? Hij kent ook veel mensen. Een tijdreeks is een reeks paren (timestamp, значение), waar deze paren op tijd zijn gesorteerd. De waarde is een getal met drijvende komma – float64.

Elke tijdreeks wordt uniek geïdentificeerd door een sleutel. Waaruit bestaat deze sleutel? Het bestaat uit een niet-lege set sleutel-waardeparen.

Hier is een voorbeeld van een tijdreeks. De sleutel van deze serie is een lijst met paren: __name__="cpu_usage" is de naam van de statistiek, instance="my-server" - dit is de computer waarop deze statistiek wordt verzameld, datacenter="us-east" - dit is het datacentrum waar deze computer zich bevindt.

We eindigden met een tijdreeksnaam die uit drie sleutel-waardeparen bestond. Deze sleutel komt overeen met een lijst met paren (timestamp, value). t1, t3, t3, ..., tN - dit zijn tijdstempels, 10, 20, 12, ..., 15 — de overeenkomstige waarden. Dit is het CPU-gebruik op een bepaald moment voor een bepaalde serie.

Waar kunnen tijdreeksen worden gebruikt? Heeft iemand enig idee?

• In DevOps kunt u CPU, RAM, netwerk, rps, aantal fouten, enz. meten.
• IoT - we kunnen temperatuur, druk, geocoördinaten en nog iets anders meten.
• Ook op het gebied van financiën: we kunnen de prijzen van allerlei soorten aandelen en valuta's volgen.
• Daarnaast kunnen tijdreeksen worden gebruikt bij het monitoren van productieprocessen in fabrieken. We hebben gebruikers die VictoriaMetrics gebruiken om windturbines te monitoren, voor robots.
• Tijdreeksen zijn ook handig voor het verzamelen van informatie van sensoren van verschillende apparaten. Voor een motor bijvoorbeeld; voor het meten van de bandenspanning; voor het meten van snelheid, afstand; voor het meten van het benzineverbruik, enz.
• Tijdreeksen kunnen ook worden gebruikt om vliegtuigen te monitoren. Elk vliegtuig heeft een zwarte doos die tijdreeksen verzamelt voor verschillende parameters van de gezondheid van het vliegtuig. Tijdreeksen worden ook gebruikt in de lucht- en ruimtevaartindustrie.
• Gezondheidszorg is bloeddruk, hartslag, enz.

Er zijn misschien nog meer toepassingen die ik ben vergeten, maar ik hoop dat je begrijpt dat tijdreeksen actief worden gebruikt in de moderne wereld. En het volume van hun gebruik groeit elk jaar.

Waarom heb je een tijdreeksdatabase nodig? Waarom kun je geen reguliere relationele database gebruiken om tijdreeksen op te slaan?

Omdat tijdreeksen doorgaans een grote hoeveelheid informatie bevatten, die in conventionele databases moeilijk op te slaan en te verwerken is. Daarom verschenen er gespecialiseerde databases voor tijdreeksen. Deze bases slaan effectief punten op (timestamp, value) met de opgegeven sleutel. Ze bieden een API voor het lezen van opgeslagen gegevens per sleutel, per enkel sleutel-waardepaar, of per meerdere sleutel-waardeparen, of per regexp. Wilt u bijvoorbeeld de CPU-belasting van al uw diensten in een datacenter in Amerika achterhalen, dan moet u deze pseudo-query gebruiken.

Normaal gesproken bieden tijdreeksdatabases gespecialiseerde zoektalen, omdat tijdreeks-SQL niet erg geschikt is. Hoewel er databases zijn die SQL ondersteunen, is dit niet erg geschikt. Querytalen zoals PromQL, InfluxQL, Stroom, Q. Ik hoop dat iemand minstens één van deze talen heeft gehoord. Veel mensen hebben waarschijnlijk wel eens van PromQL gehoord. Dit is de Prometheus-querytaal.

Dit is hoe een moderne tijdreeksdatabase-architectuur eruit ziet met VictoriaMetrics als voorbeeld.

Het bestaat uit twee delen. Dit is opslag voor de omgekeerde index en opslag voor tijdreekswaarden. Deze opslagplaatsen zijn gescheiden.

Wanneer een nieuw record in de database arriveert, hebben we eerst toegang tot de omgekeerde index om de tijdreeks-ID voor een bepaalde set te vinden label=value voor een gegeven metriek. We vinden deze identificatie en slaan de waarde op in de gegevensopslag.

Wanneer er een verzoek komt om gegevens uit TSDB op te halen, gaan we eerst naar de omgekeerde index. Laten we alles pakken timeseries_ids records die overeenkomen met deze set label=value. En dan halen we alle benodigde gegevens uit het datawarehouse, geïndexeerd door timeseries_ids.

Laten we eens kijken naar een voorbeeld van hoe een tijdreeksdatabase een binnenkomende selectiequery verwerkt.

• Allereerst krijgt ze alles timeseries_ids van een omgekeerde index die de gegeven paren bevat label=value, of voldoen aan een gegeven reguliere expressie.
• Vervolgens haalt het alle datapunten uit de dataopslag op een bepaald tijdsinterval voor de gevonden datapunten timeseries_ids.
• Hierna voert de database enkele berekeningen uit op deze datapunten, afhankelijk van het verzoek van de gebruiker. En daarna geeft het het antwoord terug.

In deze presentatie vertel ik je over het eerste deel. Dit is een zoektocht timeseries_ids door omgekeerde index. Het tweede deel en het derde deel kun je later bekijken VictoriaMetrics-bronnen, of wacht tot ik andere rapporten heb voorbereid :)

Laten we verder gaan met de omgekeerde index. Velen denken misschien dat dit eenvoudig is. Wie weet wat een omgekeerde index is en hoe deze werkt? Oh, niet zoveel mensen meer. Laten we proberen te begrijpen wat het is.

Het is eigenlijk eenvoudig. Het is gewoon een woordenboek dat een sleutel aan een waarde koppelt. Wat is een sleutel? Dit koppel label=valueWaar label и value - dit zijn lijnen. En de waarden zijn een set timeseries_ids, inclusief het gegeven paar label=value.

Met de omgekeerde index kunt u snel alles vinden timeseries_ids, die hebben gegeven label=value.

Het zorgt er ook voor dat je snel kunt vinden timeseries_ids tijdreeksen voor meerdere paren label=value, of voor koppels label=regexp. Hoe gebeurde dit? Door het snijpunt van de verzameling te vinden timeseries_ids voor elk paar label=value.

Laten we eens kijken naar verschillende implementaties van de omgekeerde index. Laten we beginnen met de eenvoudigste naïeve implementatie. Ze ziet er zo uit.

Functie getMetricIDs krijgt een lijst met strings. Elke regel bevat label=value. Deze functie retourneert een lijst metricIDs.

Hoe het werkt? Hier hebben we een globale variabele genaamd invertedIndex. Dit is een normaal woordenboek (map), waarmee de string wordt toegewezen aan het segmenteren van ints. De lijn bevat label=value.

Functie-implementatie: get metricIDs voor het eerst label=value, dan gaan we door al het andere label=value, we begrijpen het metricIDs voor hen. En roep de functie aan intersectInts, die hieronder zullen worden besproken. En deze functie retourneert het snijpunt van deze lijsten.

Zoals u kunt zien, is het implementeren van een omgekeerde index niet erg ingewikkeld. Maar dit is een naïeve implementatie. Welke nadelen heeft het? Het belangrijkste nadeel van de naïeve implementatie is dat een dergelijke omgekeerde index in RAM wordt opgeslagen. Na het herstarten van de applicatie verliezen we deze index. Er is geen opslag van deze index op schijf. Het is onwaarschijnlijk dat een dergelijke omgekeerde index geschikt is voor een database.

Het tweede nadeel heeft ook te maken met het geheugen. De omgekeerde index moet in het RAM-geheugen passen. Als het de grootte van het RAM-geheugen overschrijdt, krijgen we uiteraard een geheugenfout. En het programma werkt niet.

Dit probleem kan worden opgelost met behulp van kant-en-klare oplossingen zoals NiveauDBOf RotsDB.

Kortom, we hebben een database nodig waarmee we snel drie bewerkingen kunnen uitvoeren.

• De eerste bewerking is opnemen ключ-значение naar deze databank. Ze doet dit heel snel, waar ключ-значение zijn willekeurige strings.
• De tweede bewerking is een snelle zoektocht naar een waarde met behulp van een bepaalde sleutel.
• En de derde bewerking is een snelle zoektocht naar alle waarden met een bepaald voorvoegsel.

LevelDB en RocksDB - deze databases zijn ontwikkeld door Google en Facebook. Eerst kwam LevelDB. Toen namen de jongens van Facebook LevelDB en begonnen het te verbeteren, ze maakten RocksDB. Nu werken bijna alle interne databases op RocksDB binnen Facebook, inclusief de databases die zijn overgebracht naar RocksDB en MySQL. Ze noemden hem MijnRocks.

Een omgekeerde index kan worden geïmplementeerd met behulp van LevelDB. Hoe je dat doet? Wij bewaren als sleutel label=value. En de waarde is de identificatie van de tijdreeks waarin het paar aanwezig is label=value.

Als we veel tijdreeksen hebben met een bepaald paar label=value, dan zullen er veel rijen in deze database zijn met dezelfde sleutel en verschillend timeseries_ids. Om een ​​lijst van allemaal te krijgen timeseries_ids, die hiermee beginnen label=prefix, doen we een bereikscan waarvoor deze database is geoptimaliseerd. Dat wil zeggen, we selecteren alle regels die beginnen met label=prefix en haal het nodige timeseries_ids.

Hier is een voorbeeldimplementatie van hoe het eruit zou zien in Go. We hebben een omgekeerde index. Dit is LevelDB.

De functie is dezelfde als voor de naïeve implementatie. Het herhaalt de naïeve implementatie bijna regel voor regel. Het enige punt is dat in plaats van zich te wenden tot map we hebben toegang tot de omgekeerde index. We krijgen alle waarden voor de eerste label=value. Vervolgens doorlopen we alle resterende paren label=value en haal de bijbehorende sets metrische ID's ervoor op. Dan vinden we het kruispunt.

Alles lijkt in orde, maar er kleven nadelen aan deze oplossing. VictoriaMetrics implementeerde aanvankelijk een omgekeerde index op basis van LevelDB. Maar uiteindelijk moest ik het opgeven.

Waarom? Omdat LevelDB langzamer is dan de naïeve implementatie. In een naïeve implementatie halen we, gegeven een bepaalde sleutel, onmiddellijk het hele segment op metricIDs. Dit is een zeer snelle handeling: het hele segment is klaar voor gebruik.

In LevelDB, elke keer dat een functie wordt aangeroepen GetValues je moet alle regels doorlopen die beginnen met label=value. En krijg de waarde voor elke regel timeseries_ids. Dergelijke timeseries_ids verzamel een stukje hiervan timeseries_ids. Uiteraard is dit veel langzamer dan simpelweg toegang krijgen tot een gewone kaart met een sleutel.

Het tweede nadeel is dat LevelDB in C is geschreven. Het aanroepen van C-functies vanuit Go gaat niet erg snel. Het duurt honderden nanoseconden. Dit is niet erg snel, want vergeleken met een gewone in go geschreven functieaanroep, die 1-5 nanoseconden duurt, is het prestatieverschil tientallen malen groter. Voor VictoriaMetrics was dit een fatale fout :)

Dus schreef ik mijn eigen implementatie van de omgekeerde index. En hij belde haar samenvoegset.

Mergeset is gebaseerd op de MergeTree-gegevensstructuur. Deze datastructuur is ontleend aan ClickHouse. Uiteraard moet mergeset worden geoptimaliseerd voor snel zoeken timeseries_ids volgens de gegeven sleutel. Mergeset is volledig in Go geschreven. Je kan zien VictoriaMetrics-bronnen op GitHub. De implementatie van mergeset bevindt zich in de map /lib/mergeset. Je kunt proberen uit te zoeken wat daar aan de hand is.

De mergeset-API lijkt sterk op LevelDB en RocksDB. Dat wil zeggen, u kunt er snel nieuwe records opslaan en snel records selecteren met een bepaald voorvoegsel.

We zullen het later hebben over de nadelen van mergeset. Laten we het nu hebben over de problemen die zich voordeden met VictoriaMetrics in de productie bij het implementeren van een omgekeerde index.

Waarom zijn ze ontstaan?

De eerste reden is het hoge churnpercentage. Vertaald in het Russisch is dit een frequente verandering in tijdreeksen. Dit is het moment waarop een tijdreeks eindigt en een nieuwe reeks begint, of er beginnen veel nieuwe tijdreeksen. En dit gebeurt vaak.

De tweede reden is het grote aantal tijdreeksen. In het begin, toen monitoring steeds populairder werd, was het aantal tijdreeksen klein. Voor elke computer moet u bijvoorbeeld de CPU-, geheugen-, netwerk- en schijfbelasting controleren. 4 tijdreeksen per computer. Laten we zeggen dat u 100 computers en 400 tijdreeksen heeft. Dit is heel weinig.

Na verloop van tijd kwamen mensen erachter dat ze gedetailleerdere informatie konden meten. Meet bijvoorbeeld niet de belasting van de hele processor, maar afzonderlijk van elke processorkern. Als je 40 processorkernen hebt, heb je 40 keer meer tijdreeksen om de processorbelasting te meten.

Maar dat is niet alles. Elke processorkern kan verschillende statussen hebben, zoals inactief, wanneer deze inactief is. En werk ook in de gebruikersruimte, werk in de kernelruimte en andere staten. En elk van deze toestanden kan ook als een afzonderlijke tijdreeks worden gemeten. Dit verhoogt bovendien het aantal rijen met 7-8 keer.

Van één metriek kregen we 40 x 8 = 320 statistieken voor slechts één computer. Vermenigvuldig met 100 en we krijgen 32 in plaats van 000.

Toen kwam Kubernetes langs. En het werd nog erger omdat Kubernetes veel verschillende services kan hosten. Elke service in Kubernetes bestaat uit vele pods. En dit alles moet gemonitord worden. Daarnaast zijn wij voortdurend bezig met de inzet van nieuwe versies van uw diensten. Voor elke nieuwe versie moeten nieuwe tijdreeksen worden aangemaakt. Als gevolg hiervan groeit het aantal tijdreeksen exponentieel en worden we geconfronteerd met het probleem van een groot aantal tijdreeksen, dat hoge kardinaliteit wordt genoemd. VictoriaMetrics gaat er met succes mee om in vergelijking met andere tijdreeksdatabases.

Laten we het hoge churnpercentage eens nader bekijken. Wat veroorzaakt een hoog verloop in de productie? Omdat sommige betekenissen van labels en tags voortdurend veranderen.

Neem bijvoorbeeld Kubernetes, dat het concept heeft deployment, dat wil zeggen wanneer er een nieuwe versie van uw applicatie wordt uitgerold. Om de een of andere reden besloten de Kubernetes-ontwikkelaars om de implementatie-ID aan het label toe te voegen.

Waar heeft dit toe geleid? Bovendien worden bij elke nieuwe implementatie alle oude tijdreeksen onderbroken en in plaats daarvan beginnen nieuwe tijdreeksen met een nieuwe labelwaarde deployment_id. Er kunnen honderdduizenden en zelfs miljoenen van dergelijke rijen zijn.

Het belangrijkste bij dit alles is dat het totale aantal tijdreeksen groeit, maar het aantal tijdreeksen dat momenteel actief is en gegevens ontvangt, blijft constant. Deze toestand wordt een hoog klantverloop genoemd.

Het belangrijkste probleem van een hoge churn-snelheid is het garanderen van een constante zoeksnelheid voor alle tijdreeksen voor een gegeven set labels gedurende een bepaald tijdsinterval. Meestal is dit het tijdsinterval voor het laatste uur of de laatste dag.

Hoe dit probleem op te lossen? Hier is de eerste optie. Dit is om de omgekeerde index in de loop van de tijd in onafhankelijke delen te verdelen. Dat wil zeggen, als er een tijdsinterval verstrijkt, zijn we klaar met werken met de huidige omgekeerde index. En maak een nieuwe omgekeerde index. Er gaat weer een tijdsinterval voorbij, we creëren nog een en nog een.

En bij het nemen van steekproeven uit deze omgekeerde indices vinden we een reeks omgekeerde indices die binnen het gegeven interval vallen. En dienovereenkomstig selecteren we van daaruit de id van de tijdreeks.

Dit bespaart middelen omdat we niet hoeven te kijken naar onderdelen die niet binnen het gegeven interval vallen. Dat wil zeggen dat als we gegevens van het afgelopen uur selecteren, we voor eerdere tijdsintervallen verzoeken overslaan.

Er is nog een andere optie om dit probleem op te lossen. Dit is om voor elke dag een aparte lijst met ID's van tijdreeksen op te slaan die op die dag plaatsvonden.

Het voordeel van deze oplossing ten opzichte van de vorige oplossing is dat we geen tijdreeksinformatie dupliceren die niet in de loop van de tijd verdwijnt. Ze zijn voortdurend aanwezig en veranderen niet.

Het nadeel is dat een dergelijke oplossing moeilijker te implementeren en moeilijker te debuggen is. En VictoriaMetrics koos voor deze oplossing. Zo is het historisch gezien gebeurd. Deze oplossing presteert ook goed vergeleken met de vorige. Omdat deze oplossing niet is geïmplementeerd vanwege het feit dat het nodig is om gegevens in elke partitie te dupliceren voor tijdreeksen die niet veranderen, dat wil zeggen die niet verdwijnen in de loop van de tijd. VictoriaMetrics was voornamelijk geoptimaliseerd voor het verbruik van schijfruimte, en de vorige implementatie maakte het verbruik van schijfruimte nog erger. Maar deze implementatie is beter geschikt voor het minimaliseren van het schijfruimteverbruik, dus werd er voor gekozen.

Ik moest met haar vechten. De strijd was dat je bij deze implementatie toch een veel groter aantal moet kiezen timeseries_ids voor gegevens dan wanneer de omgekeerde index in de tijd is gepartitioneerd.

Hoe hebben we dit probleem opgelost? We hebben het op een originele manier opgelost: door verschillende tijdreeksidentificatoren op te slaan in elke omgekeerde indexingang in plaats van één identificator. Dat wil zeggen, we hebben een sleutel label=value, die in elke tijdreeks voorkomt. En nu redden we er meerdere timeseries_ids in één inzending.

Hier is een voorbeeld. Vroeger hadden we N vermeldingen, maar nu hebben we één vermelding waarvan het voorvoegsel hetzelfde is als alle andere. Voor de vorige invoer bevat de waarde alle tijdreeks-ID's.

Dit maakte het mogelijk om de scansnelheid van een dergelijke omgekeerde index tot 10 keer te verhogen. En het stelde ons in staat het geheugengebruik voor de cache te verminderen, omdat we nu de string opslaan label=value slechts één keer in de cache samen N keer. En deze regel kan groot zijn als je lange regels in je tags en labels opslaat, die Kubernetes daar graag stopt.

Een andere optie om het zoeken op een omgekeerde index te versnellen is sharding. Het maken van meerdere omgekeerde indexen in plaats van één en het verdelen van gegevens daartussen op basis van een sleutel. Dit is een set key=value stoom. Dat wil zeggen, we krijgen verschillende onafhankelijke omgekeerde indexen, die we parallel op verschillende processors kunnen opvragen. Eerdere implementaties maakten alleen gebruik in de modus met één processor mogelijk, dat wil zeggen het scannen van gegevens op slechts één kern. Met deze oplossing kunt u gegevens op meerdere kernen tegelijk scannen, zoals ClickHouse graag doet. Dit is wat we van plan zijn te implementeren.

Laten we nu terugkeren naar onze schapen - naar de kruispuntfunctie timeseries_ids. Laten we eens kijken welke implementaties er kunnen zijn. Met deze functie kunt u zoeken timeseries_ids voor een gegeven set label=value.

De eerste optie is een naïeve implementatie. Twee geneste lussen. Hier krijgen we de functie-invoer intersectInts twee plakjes - a и b. Aan de uitgang zou het de kruising van deze plakjes naar ons moeten retourneren.

Een naïeve implementatie ziet er zo uit. We herhalen alle waarden van slice a, binnen deze lus doorlopen we alle waarden van slice b. En wij vergelijken ze. Als ze overeenkomen, hebben we een kruispunt gevonden. En sla het op result.

Wat zijn de nadelen? Kwadratische complexiteit is het grootste nadeel. Als uw afmetingen bijvoorbeeld slice a и b één miljoen tegelijk, dan zal deze functie u nooit een antwoord teruggeven. Omdat het een biljoen iteraties zal moeten maken, wat zelfs voor moderne computers veel is.

De tweede implementatie is gebaseerd op kaart. Wij maken een kaart. We hebben alle waarden van Slice in deze kaart geplaatst a. Vervolgens gaan we door de slice in een aparte lus b. En we controleren of deze waarde afkomstig is van slice b op de kaart. Als het bestaat, voeg het dan toe aan het resultaat.

Wat zijn de voordelen? Het voordeel is dat er alleen sprake is van lineaire complexiteit. Dat wil zeggen dat de functie veel sneller wordt uitgevoerd voor grotere segmenten. Voor een segment ter grootte van een miljoen wordt deze functie uitgevoerd in 2 miljoen iteraties, in tegenstelling tot de biljoen iteraties van de vorige functie.

Het nadeel is dat deze functie meer geheugen vereist om deze kaart te maken.

Het tweede nadeel is de grote overhead voor hashing. Dit nadeel is niet erg duidelijk. En voor ons was het ook niet erg duidelijk, dus in VictoriaMetrics gebeurde de implementatie van kruispunt aanvankelijk via een kaart. Maar toen bleek uit profilering dat de tijd van de hoofdprocessor wordt besteed aan het schrijven naar de kaart en het controleren op de aanwezigheid van een waarde op deze kaart.

Waarom wordt op deze plaatsen CPU-tijd verspild? Omdat Go een hashbewerking uitvoert op deze lijnen. Dat wil zeggen, het berekent de hash van de sleutel om er vervolgens toegang toe te krijgen via een bepaalde index in de HashMap. De hashberekening is in tientallen nanoseconden voltooid. Dit is traag voor VictoriaMetrics.

Ik besloot een bitset te implementeren die speciaal voor dit geval was geoptimaliseerd. Zo ziet het snijpunt van twee plakjes er nu uit. Hier maken we een bitset. We voegen er elementen uit het eerste segment aan toe. Vervolgens controleren we de aanwezigheid van deze elementen in het tweede segment. En voeg ze toe aan het resultaat. Dat wil zeggen, het verschilt bijna niet van het vorige voorbeeld. Het enige hier is dat we de toegang tot de kaart hebben vervangen door aangepaste functies add и has.

Op het eerste gezicht lijkt het erop dat dit langzamer zou moeten werken, als daar voorheen een standaardkaart werd gebruikt, en vervolgens enkele andere functies worden aangeroepen, maar uit profilering blijkt dat dit ding 10 keer sneller werkt dan de standaardkaart in het geval van VictoriaMetrics.

Bovendien gebruikt het veel minder geheugen in vergelijking met de kaartimplementatie. Omdat we hier bits opslaan in plaats van waarden van acht bytes.

Het nadeel van deze implementatie is dat deze niet zo voor de hand liggend en niet triviaal is.

Een ander nadeel dat velen misschien niet opmerken, is dat deze implementatie in sommige gevallen mogelijk niet goed werkt. Dat wil zeggen dat het is geoptimaliseerd voor een specifiek geval, voor dit geval van kruising van VictoriaMetrics-tijdreeks-ID's. Dit betekent niet dat het voor alle gevallen geschikt is. Als het verkeerd wordt gebruikt, krijgen we geen prestatieverbetering, maar een fout met onvoldoende geheugen en een vertraging van de prestaties.

Laten we eens kijken naar de implementatie van deze structuur. Als je wilt kijken: deze bevindt zich in de VictoriaMetrics-bronnen, in de map lib/uint64set. Het is specifiek geoptimaliseerd voor de VictoriaMetrics-zaak, waar timeseries_id is een 64-bits waarde, waarbij de eerste 32 bits in principe constant zijn en alleen de laatste 32 bits veranderen.

Deze datastructuur wordt niet op schijf opgeslagen, maar werkt alleen in het geheugen.

Hier is de API. Het is niet erg ingewikkeld. De API is specifiek afgestemd op een specifiek voorbeeld van het gebruik van VictoriaMetrics. Dat wil zeggen, er zijn hier geen onnodige functies. Dit zijn de functies die expliciet door VictoriaMetrics worden gebruikt.

Er zijn functies add, wat nieuwe waarden toevoegt. Er is een functie has, waarmee wordt gecontroleerd op nieuwe waarden. En er is een functie del, waarmee waarden worden verwijderd. Er is een helpfunctie len, wat de grootte van de set retourneert. Functie clone klonen veel. En functie appendto converteert deze set naar een segment timeseries_ids.

Zo ziet de implementatie van deze datastructuur eruit. set bestaat uit twee elementen:

• ItemsCount is een hulpveld om snel het aantal elementen in een set terug te geven. Het zou mogelijk zijn om dit hulpveld te missen, maar het moest hier worden toegevoegd omdat VictoriaMetrics in zijn algoritmen vaak de lengte van de bitset opvraagt.

• Het tweede veld is buckets. Dit is een stukje van de structuur bucket32. Elke structuur slaat op hi veld. Dit zijn de bovenste 32 bits. En twee plakjes - b16his и buckets van bucket16 structuren.

De bovenste 16 bits van het tweede deel van de 64-bits structuur worden hier opgeslagen. En hier worden bitsets opgeslagen voor de onderste 16 bits van elke byte.

Bucket64 bestaat uit een array uint64. Met behulp van deze constanten wordt de lengte berekend. In een bucket16 maximaal kan worden opgeslagen 2^16=65536 beetje. Deel je dit door 8, dan is het 8 kilobyte. Als je weer door 8 deelt, is het 1000 uint64 betekenis. Dat is Bucket16 – dit is onze structuur van 8 kilobyte.

Laten we eens kijken hoe een van de methoden van deze structuur voor het toevoegen van een nieuwe waarde wordt geïmplementeerd.

Het begint allemaal met uint64 betekenissen. We berekenen de bovenste 32 bits, we berekenen de onderste 32 bits. Laten we alles doornemen buckets. We vergelijken de bovenste 32 bits in elke bucket met de toegevoegde waarde. En als ze overeenkomen, roepen we de functie aan add in structuur b32 buckets. En voeg daar de onderste 32 bits toe. En als het terugkwam true, dan betekent dit dat we daar zo’n waarde hebben toegevoegd en dat we zo’n waarde niet hadden. Als het terugkeert false, dan bestond zo'n betekenis al. Vervolgens vergroten we het aantal elementen in de structuur.

Als we niet degene hebben gevonden die u nodig heeft bucket met de vereiste hi-waarde, dan roepen we de functie aan addAlloc, die een nieuwe zal opleveren bucket, door het toe te voegen aan de bucketstructuur.

Dit is de implementatie van de functie b32.add. Het is vergelijkbaar met de vorige implementatie. We berekenen de meest significante 16 bits, de minst significante 16 bits.

Vervolgens doorlopen we alle bovenste 16 bits. Wij vinden overeenkomsten. En als er een match is, noemen we de add-methode, die we op de volgende pagina zullen bespreken bucket16.

En hier is het laagste niveau, dat zoveel mogelijk moet worden geoptimaliseerd. Wij rekenen voor uint64 id-waarde in slice-bit en ook bitmask. Dit is een masker voor een bepaalde 64-bits waarde, waarmee de aanwezigheid van dit bit kan worden gecontroleerd of ingesteld. We controleren of dit bit is ingesteld en stellen het in, en retourneren de aanwezigheid. Dit is onze implementatie, waarmee we de werking van kruisende ID's van tijdreeksen tien keer konden versnellen in vergelijking met conventionele kaarten.

Naast deze optimalisatie kent VictoriaMetrics nog vele andere optimalisaties. De meeste van deze optimalisaties zijn met een reden toegevoegd, maar na het profileren van de code in productie.

Dit is de hoofdregel van optimalisatie: voeg geen optimalisatie toe in de veronderstelling dat er hier een knelpunt zal zijn, omdat het kan blijken dat er daar geen knelpunt zal zijn. Optimalisatie verslechtert meestal de kwaliteit van de code. Daarom is het de moeite waard om pas na profilering en bij voorkeur in productie te optimaliseren, zodat dit echte gegevens zijn. Als iemand geïnteresseerd is, kunt u de VictoriaMetrics-broncode bekijken en andere optimalisaties verkennen die er zijn.

Ik heb een vraag over bitsets. Zeer vergelijkbaar met de C++ vectorbool-implementatie, geoptimaliseerde bitset. Heb je de implementatie vanaf daar overgenomen?

Nee, niet vanaf daar. Bij het implementeren van deze bitset heb ik mij laten leiden door kennis van de structuur van deze ID-tijdreeksen, die in VictoriaMetrics worden gebruikt. En hun structuur is zodanig dat de bovenste 32 bits in principe constant zijn. De onderste 32 bits kunnen worden gewijzigd. Hoe lager het bit, hoe vaker deze kan veranderen. Daarom is deze implementatie specifiek geoptimaliseerd voor deze datastructuur. De C++-implementatie is, voor zover ik weet, geoptimaliseerd voor het algemene geval. Als u optimaliseert voor het algemene geval, betekent dit dat dit voor een specifiek geval niet het meest optimaal zal zijn.

Ik raad je ook aan om het rapport van Alexey Milovid te bekijken. Ongeveer een maand geleden vertelde hij over optimalisatie in ClickHouse voor specifieke specialisaties. Hij zegt alleen dat in het algemeen een C++-implementatie of een andere implementatie op maat is gemaakt om gemiddeld goed te werken in een ziekenhuis. Het zou slechter kunnen presteren dan een kennisspecifieke implementatie zoals de onze, waarbij we weten dat de bovenste 32 bits grotendeels constant zijn.

Ik heb een tweede vraag. Wat is het fundamentele verschil met InfluxDB?

Er zijn veel fundamentele verschillen. In termen van prestaties en geheugengebruik laat InfluxDB in tests 10 keer meer geheugengebruik zien voor tijdreeksen met hoge kardinaliteit, als je er veel hebt, bijvoorbeeld miljoenen. VictoriaMetrics verbruikt bijvoorbeeld 1 GB per miljoen actieve rijen, terwijl InfluxDB 10 GB verbruikt. En dat is een groot verschil.

Het tweede fundamentele verschil is dat InfluxDB vreemde zoektalen heeft: Flux en InfluxQL. Ze zijn niet erg handig om met tijdreeksen te werken in vergelijking met PromQL, dat wordt ondersteund door VictoriaMetrics. PromQL is een querytaal van Prometheus.

En nog een verschil is dat InfluxDB een ietwat vreemd datamodel heeft, waarbij elke regel meerdere velden met een andere set tags kan opslaan. Deze regels zijn verder onderverdeeld in verschillende tabellen. Deze extra complicaties bemoeilijken het latere werk met deze database. Het is moeilijk te ondersteunen en te begrijpen.

In VictoriaMetrics is alles veel eenvoudiger. Daar is elke tijdreeks een sleutelwaarde. De waarde is een reeks punten - (timestamp, value), en de sleutel is de set label=value. Er is geen scheiding tussen velden en metingen. Hiermee kun je alle gegevens selecteren en vervolgens combineren, optellen, aftrekken, vermenigvuldigen en delen, in tegenstelling tot InfluxDB waar berekeningen tussen verschillende rijen voor zover ik weet nog steeds niet zijn geïmplementeerd. Zelfs als ze geïmplementeerd zijn, is het moeilijk, je moet veel code schrijven.

Ik heb een verduidelijkende vraag. Heb ik goed begrepen dat er een probleem was waar u het over had, dat deze omgekeerde index niet in het geheugen past, en dat er dus sprake is van partitie?

Eerst liet ik een naïeve implementatie zien van een omgekeerde index op een standaard Go-kaart. Deze implementatie is niet geschikt voor databases omdat deze omgekeerde index niet op schijf wordt opgeslagen en de database op schijf moet worden opgeslagen zodat deze gegevens bij opnieuw opstarten beschikbaar blijven. In deze implementatie zal uw omgekeerde index verdwijnen wanneer u de applicatie opnieuw start. En u verliest de toegang tot alle gegevens omdat u deze niet meer kunt vinden.

Hallo! Bedankt voor het rapport! Mijn naam is Pavel. Ik kom uit Wildberries. Ik heb een paar vragen voor je. Vraag één. Denkt u dat als u bij het bouwen van de architectuur van uw applicatie een ander principe had gekozen en de gegevens in de loop van de tijd had gepartitioneerd, u tijdens het zoeken misschien gegevens had kunnen kruisen, alleen gebaseerd op het feit dat één partitie gegevens bevat voor één partitie? tijdsinterval, dat wil zeggen in één tijdsinterval en u zich geen zorgen hoeft te maken over het feit dat uw stukken anders verspreid zijn? Vraag nummer 2: aangezien je een soortgelijk algoritme implementeert met bitset en al het andere, heb je misschien geprobeerd processorinstructies te gebruiken? Misschien heb je dergelijke optimalisaties geprobeerd?

Ik zal de tweede meteen beantwoorden. Op dat punt zijn we nog niet aangekomen. Maar als het nodig is, komen we er wel. En de eerste: wat was de vraag?

U hebt twee scenario's besproken. En ze zeiden dat ze de tweede kozen met een complexere implementatie. En ze gaven niet de voorkeur aan de eerste, waarbij de gegevens op tijd worden gepartitioneerd.

Ja. In het eerste geval zou het totale volume van de index groter zijn, omdat we in elke partitie dubbele gegevens zouden moeten opslaan voor de tijdreeksen die door al deze partities lopen. En als de churn-snelheid van uw tijdreeks klein is, d.w.z. dezelfde reeks wordt voortdurend gebruikt, dan zouden we in het eerste geval veel meer schijfruimte verliezen vergeleken met het tweede geval.

En dus - ja, tijdpartitionering is een goede optie. Prometheus gebruikt het. Maar Prometheus heeft nog een ander nadeel. Bij het samenvoegen van deze gegevens moet meta-informatie voor alle labels en tijdreeksen in het geheugen worden bewaard. Als de stukjes gegevens die worden samengevoegd groot zijn, neemt het geheugengebruik tijdens het samenvoegen dus sterk toe, in tegenstelling tot VictoriaMetrics. Bij het samenvoegen verbruikt VictoriaMetrics helemaal geen geheugen; er worden slechts een paar kilobytes verbruikt, ongeacht de grootte van de samengevoegde gegevens.

Het algoritme dat u gebruikt, maakt gebruik van geheugen. Het markeert tijdreekstags die waarden bevatten. En op deze manier controleer je op gepaarde aanwezigheid in de ene data-array en in de andere. En je begrijpt of er een kruising heeft plaatsgevonden of niet. Doorgaans implementeren databases cursors en iterators die hun huidige inhoud opslaan en de gesorteerde gegevens doorlopen vanwege de eenvoudige complexiteit van deze bewerkingen.

Waarom gebruiken we geen cursors om gegevens te doorkruisen?

Да.

We slaan gesorteerde rijen op in LevelDB of mergeset. We kunnen de cursor verplaatsen en het snijpunt vinden. Waarom gebruiken we het niet? Omdat het langzaam is. Omdat cursors betekenen dat u voor elke regel een functie moet aanroepen. Een functieaanroep duurt 5 nanoseconden. En als je 100 regels hebt, blijkt dat we een halve seconde besteden aan het aanroepen van de functie.

Er bestaat zoiets, ja. En mijn laatste vraag. De vraag klinkt misschien een beetje vreemd. Waarom is het niet mogelijk om alle benodigde aggregaten te lezen op het moment dat de gegevens binnenkomen en deze in de gewenste vorm op te slaan? Waarom enorme volumes besparen in sommige systemen zoals VictoriaMetrics, ClickHouse, enz., en er vervolgens veel tijd aan besteden?

Ik zal een voorbeeld geven om het duidelijker te maken. Laten we zeggen: hoe werkt een kleine speelgoedsnelheidsmeter? Het registreert de afstand die u hebt afgelegd, voegt deze voortdurend toe aan één waarde en de tweede keer. En verdeelt. En haalt gemiddelde snelheid. Je kunt ongeveer hetzelfde doen. Tel alle noodzakelijke feiten direct bij elkaar op.

Oké, ik begrijp de vraag. Jouw voorbeeld heeft zijn plaats. Als u weet welke aggregaten u nodig heeft, dan is dit de beste uitvoering. Maar het probleem is dat mensen deze statistieken en sommige gegevens in ClickHouse opslaan en nog niet weten hoe ze deze in de toekomst zullen samenvoegen en filteren, dus moeten ze alle onbewerkte gegevens opslaan. Maar als je weet dat je iets gemiddelds moet berekenen, waarom zou je het dan niet berekenen in plaats van daar een aantal ruwe waarden op te slaan? Maar dit is alleen als u precies weet wat u nodig heeft.

Overigens ondersteunen databases voor het opslaan van tijdreeksen het tellen van aggregaten. Prometheus ondersteunt bijvoorbeeld opnameregels. Dat wil zeggen, dit kan worden gedaan als u weet welke eenheden u nodig heeft. VictoriaMetrics heeft dit nog niet, maar wordt meestal voorafgegaan door Prometheus, waarin dit in de hercoderingsregels kan worden gedaan.

In mijn vorige baan moest ik bijvoorbeeld het aantal gebeurtenissen in een glijdend venster van het afgelopen uur tellen. Het probleem is dat ik een aangepaste implementatie in Go moest maken, dat wil zeggen een service om dit ding te tellen. Deze service was uiteindelijk niet triviaal, omdat deze moeilijk te berekenen is. De implementatie kan eenvoudig zijn als u bepaalde aggregaten op vaste tijdsintervallen moet tellen. Als je gebeurtenissen in een glijdend venster wilt tellen, is dat niet zo eenvoudig als het lijkt. Ik denk dat dit nog niet is geïmplementeerd in ClickHouse of in tijdreeksdatabases, omdat het moeilijk te implementeren is.

En nog een vraag. We hadden het net over middelen, en ik herinnerde me dat er ooit zoiets bestond als grafiet met een carbon-backend. En hij wist hoe hij oude gegevens moest uitdunnen, dat wil zeggen één punt per minuut, één punt per uur, enz. Overlaten. In principe is dit best handig als we, relatief gezien, een maand lang ruwe gegevens nodig hebben, en al het andere kan uitgedund worden. Maar Prometheus en VictoriaMetrics ondersteunen deze functionaliteit niet. Is het de bedoeling om dit te ondersteunen? Zo niet, waarom niet?

Bedankt voor de vraag. Onze gebruikers stellen deze vraag regelmatig. Ze vragen wanneer we ondersteuning voor downsampling toevoegen. Er zijn hier verschillende problemen. Ten eerste begrijpt elke gebruiker het downsampling iets anders: iemand wil een willekeurig punt op een bepaald interval krijgen, iemand wil maximale, minimale, gemiddelde waarden. Als veel systemen gegevens naar uw database schrijven, kunt u deze niet allemaal op één hoop gooien. Het kan zijn dat elk systeem een ​​andere verdunning vereist. En dit is lastig uit te voeren.

En het tweede is dat VictoriaMetrics, net als ClickHouse, is geoptimaliseerd voor het werken met grote hoeveelheden onbewerkte gegevens, zodat het in minder dan een seconde een miljard regels kan verzamelen als je veel kernen in je systeem hebt. Tijdreekspunten scannen in VictoriaMetrics – 50 punten per seconde per kern. En deze prestaties schalen naar bestaande kernen. Dat wil zeggen: als u bijvoorbeeld twintig kernen heeft, scant u een miljard punten per seconde. En deze eigenschap van VictoriaMetrics en ClickHouse vermindert de noodzaak voor downsamling.

Een ander kenmerk is dat VictoriaMetrics deze gegevens effectief comprimeert. De compressie tijdens de productie bedraagt ​​gemiddeld 0,4 tot 0,8 bytes per punt. Elk punt is een tijdstempel + waarde. En het wordt gemiddeld gecomprimeerd tot minder dan één byte.

Sergej. Ik heb een vraag. Wat is de minimale opnametijd quantum?

Eén milliseconde. We hadden onlangs een gesprek met andere ontwikkelaars van tijdreeksdatabases. Hun minimale tijdschijf is één seconde. En in grafiet is dit bijvoorbeeld ook één seconde. In OpenTSDB is het ook één seconde. InfluxDB heeft een nauwkeurigheid van nanoseconden. In VictoriaMetrics is het één milliseconde, omdat het in Prometheus één milliseconde is. En VictoriaMetrics is oorspronkelijk ontwikkeld als externe opslag voor Prometheus. Maar nu kan het gegevens van andere systemen opslaan.

De persoon met wie ik sprak, zegt dat ze van seconde tot seconde nauwkeurig zijn. Dat is voor hen genoeg omdat het afhangt van het type gegevens dat in de tijdreeksdatabase wordt opgeslagen. Als dit DevOps-gegevens zijn of gegevens uit de infrastructuur, waar u deze verzamelt met intervallen van 30 seconden per minuut, dan is secondenauwkeurigheid voldoende, u heeft niets minder nodig. En als u deze gegevens verzamelt via hoogfrequente handelssystemen, dan heeft u nauwkeurigheid van nanoseconden nodig.

De nauwkeurigheid van milliseconden in VictoriaMetrics is ook geschikt voor het geval van DevOps, en kan geschikt zijn voor de meeste gevallen die ik aan het begin van het rapport noemde. Het enige waarvoor het misschien niet geschikt is, zijn hoogfrequente handelssystemen.

Bedankt! En nog een vraag. Wat is compatibiliteit in PromQL?

Volledige achterwaartse compatibiliteit. VictoriaMetrics ondersteunt PromQL volledig. Daarnaast voegt het extra geavanceerde functionaliteit toe in PromQL, genaamd MetriekQL. Er is een gesprek op YouTube over deze uitgebreide functionaliteit. Ik sprak op de Monitoring Meetup in het voorjaar in St. Petersburg.

Telegram-kanaal VictoriaMetrics.

Alleen geregistreerde gebruikers kunnen deelnemen aan het onderzoek. Inloggen, Alsjeblieft.

Wat houdt u tegen om over te stappen naar VictoriaMetrics als uw langetermijnopslag voor Prometheus? (Schrijf in de reacties, ik voeg het toe aan de poll))

• 71,4%Ik gebruik Prometheus5 niet

• 28,6%Ik kende VictoriaMetrics2 niet

7 gebruikers hebben gestemd. 12 gebruikers onthielden zich van stemming.

Bron: www.habr.com