Jeg foreslår at du leser utskriften av rapporten fra slutten av 2019 av Alexander Valyalkin "Go optimizations in VictoriaMetrics"
– en rask og skalerbar DBMS for lagring og behandling av data i form av en tidsserie (posten danner tid og et sett med verdier som tilsvarer denne tiden, for eksempel oppnådd gjennom periodisk polling av statusen til sensorer eller innsamling av beregninger).
Her er en lenke til videoen av denne rapporten -
Fortell oss om deg selv. Jeg er Alexander Valyalkin. Her . Jeg brenner for Go og ytelsesoptimalisering. Jeg skrev mange nyttige og lite nyttige biblioteker. De begynner med enten fast, eller med quick prefiks.
Jeg jobber for tiden med VictoriaMetrics. Hva er det og hva gjør jeg der? Jeg vil snakke om dette i denne presentasjonen.
Oversikten til rapporten er som følger:
- Først vil jeg fortelle deg hva VictoriaMetrics er.
- Da skal jeg fortelle deg hva tidsserier er.
- Så skal jeg fortelle deg hvordan en tidsseriedatabase fungerer.
- Deretter vil jeg fortelle deg om databasearkitekturen: hva den består av.
- Og la oss så gå videre til optimaliseringene som VictoriaMetrics har. Dette er en optimalisering for den inverterte indeksen og en optimalisering for bitsettimplementeringen i Go.
Er det noen i publikum som vet hva VictoriaMetrics er? Wow, mange vet allerede. Det er gode nyheter. For de som ikke vet, er dette en tidsseriedatabase. Den er basert på ClickHouse-arkitekturen, på noen detaljer om ClickHouse-implementeringen. For eksempel på som: MergeTree, parallellberegning på alle tilgjengelige prosessorkjerner og ytelsesoptimering ved å jobbe med datablokker som plasseres i prosessorcachen.
VictoriaMetrics gir bedre datakomprimering enn andre tidsseriedatabaser.
Den skaleres vertikalt – det vil si at du kan legge til flere prosessorer, mer RAM på én datamaskin. VictoriaMetrics vil med hell utnytte disse tilgjengelige ressursene og forbedre lineær produktivitet.
VictoriaMetrics skalerer også horisontalt - det vil si at du kan legge til flere noder til VictoriaMetrics-klyngen, og ytelsen vil øke nesten lineært.
Som du gjettet, er VictoriaMetrics en rask database, fordi jeg ikke kan skrive andre. Og det er skrevet i Go, så jeg snakker om det på dette møtet.
Hvem vet hva en tidsserie er? Han kjenner også mange mennesker. En tidsserie er en serie av par (timestamp, значение), hvor disse parene er sortert etter tid. Verdien er et flyttallstall – float64.
Hver tidsserie er unikt identifisert med en nøkkel. Hva består denne nøkkelen av? Den består av et ikke-tomt sett med nøkkelverdi-par.
Her er et eksempel på en tidsserie. Nøkkelen til denne serien er en liste over par: __name__="cpu_usage" er navnet på metrikken, instance="my-server" - dette er datamaskinen som denne beregningen er samlet inn på, datacenter="us-east" - dette er datasenteret der denne datamaskinen er plassert.
Vi endte opp med et tidsserienavn bestående av tre nøkkelverdi-par. Denne nøkkelen tilsvarer en liste med par (timestamp, value). t1, t3, t3, ..., tN - dette er tidsstempler, 10, 20, 12, ..., 15 — de tilsvarende verdiene. Dette er CPU-bruken på et gitt tidspunkt for en gitt serie.
Hvor kan tidsserier brukes? Er det noen som har noen anelse?
- I DevOps kan du måle CPU, RAM, nettverk, rps, antall feil, etc.
- IoT – vi kan måle temperatur, trykk, geokoordinater og noe annet.
- Også finans – vi kan overvåke priser for alle slags aksjer og valutaer.
- I tillegg kan tidsserier brukes til å overvåke produksjonsprosesser i fabrikker. Vi har brukere som bruker VictoriaMetrics til å overvåke vindturbiner, for roboter.
- Tidsserier er også nyttige for å samle informasjon fra sensorer til ulike enheter. For eksempel for en motor; for måling av dekktrykk; for måling av hastighet, avstand; for måling av bensinforbruk osv.
- Tidsserier kan også brukes til å overvåke fly. Hvert fly har en svart boks som samler tidsserier for ulike parametere for flyets helse. Tidsserier brukes også i romfartsindustrien.
- Helsetjenester er blodtrykk, puls osv.
Det kan være flere applikasjoner jeg har glemt, men jeg håper du forstår at tidsserier brukes aktivt i den moderne verden. Og volumet av bruken deres vokser hvert år.
Hvorfor trenger du en tidsseriedatabase? Hvorfor kan du ikke bruke en vanlig relasjonsdatabase til å lagre tidsserier?
Fordi tidsserier vanligvis inneholder en stor mengde informasjon, som er vanskelig å lagre og behandle i konvensjonelle databaser. Derfor dukket det opp spesialiserte databaser for tidsserier. Disse basene lagrer effektivt poeng (timestamp, value) med den oppgitte nøkkelen. De gir et API for å lese lagrede data etter nøkkel, etter et enkelt nøkkelverdi-par, eller etter flere nøkkelverdi-par, eller etter regexp. Hvis du for eksempel vil finne CPU-belastningen til alle tjenestene dine i et datasenter i Amerika, må du bruke denne pseudo-spørringen.
Vanligvis gir tidsseriedatabaser spesialiserte spørringsspråk fordi tidsserie-SQL ikke er særlig godt egnet. Selv om det finnes databaser som støtter SQL, er det lite egnet. Spørrespråk som f.eks , , , . Jeg håper at noen har hørt minst ett av disse språkene. Mange har sikkert hørt om PromQL. Dette er Prometheus spørrespråk.
Slik ser en moderne tidsseriedatabasearkitektur ut ved å bruke VictoriaMetrics som eksempel.
Den består av to deler. Dette er lagring for den inverterte indeksen og lagring for tidsserieverdier. Disse depotene er atskilt.
Når en ny post kommer inn i databasen, får vi først tilgang til den inverterte indeksen for å finne tidsserieidentifikatoren for et gitt sett label=value for en gitt beregning. Vi finner denne identifikatoren og lagrer verdien i datalageret.
Når det kommer en forespørsel om å hente data fra TSDB, går vi først til den inverterte indeksen. La oss få alt timeseries_ids rekorder som samsvarer med dette settet label=value. Og så får vi alle nødvendige data fra datavarehuset, indeksert av timeseries_ids.
La oss se på et eksempel på hvordan en tidsseriedatabase behandler en innkommende utvalgsspørring.
- Først av alt får hun alt
timeseries_idsfra en invertert indeks som inneholder de gitte parenelabel=value, eller tilfredsstille et gitt regulært uttrykk. - Deretter henter den alle datapunkter fra datalageret ved et gitt tidsintervall for de funnet
timeseries_ids. - Etter dette utfører databasen noen beregninger på disse datapunktene, i henhold til brukerens forespørsel. Og etter det returnerer den svaret.
I denne presentasjonen vil jeg fortelle deg om den første delen. Dette er et søk timeseries_ids etter invertert indeks. Du kan se om den andre delen og den tredje delen senere , eller vent til jeg forbereder andre rapporter :)
La oss gå videre til den inverterte indeksen. Mange tror kanskje dette er enkelt. Hvem vet hva en invertert indeks er og hvordan den fungerer? Å, ikke så mange mennesker lenger. La oss prøve å forstå hva det er.
Det er faktisk enkelt. Det er rett og slett en ordbok som kartlegger en nøkkel til en verdi. Hva er en nøkkel? Dette paret label=valueDer label и value - Dette er linjer. Og verdiene er et sett timeseries_ids, som inkluderer det gitte paret label=value.
Invertert indeks lar deg raskt finne alt timeseries_ids, som har gitt label=value.
Den lar deg også raskt finne timeseries_ids tidsserier for flere par label=value, eller for par label=regexp. Hvordan skjer dette? Ved å finne skjæringspunktet mellom settet timeseries_ids for hvert par label=value.
La oss se på ulike implementeringer av den inverterte indeksen. La oss starte med den enkleste naive implementeringen. Hun ser slik ut.
Funksjon getMetricIDs får en liste over strenger. Hver linje inneholder label=value. Denne funksjonen returnerer en liste metricIDs.
Hvordan det fungerer? Her har vi en global variabel kalt invertedIndex. Dette er en vanlig ordbok (map), som vil kartlegge strengen til skive ints. Linjen inneholder label=value.
Funksjonsimplementering: få metricIDs først og fremst label=value, så går vi gjennom alt annet label=value, vi forstår det metricIDs for dem. Og ring funksjonen intersectInts, som vil bli diskutert nedenfor. Og denne funksjonen returnerer skjæringspunktet mellom disse listene.
Som du kan se, er det ikke veldig komplisert å implementere en invertert indeks. Men dette er en naiv implementering. Hvilke ulemper har det? Den største ulempen med den naive implementeringen er at en slik invertert indeks lagres i RAM. Etter å ha startet programmet på nytt mister vi denne indeksen. Det er ingen lagring av denne indeksen på disk. En slik invertert indeks er neppe egnet for en database.
Den andre ulempen er også relatert til hukommelsen. Den inverterte indeksen må passe inn i RAM. Hvis det overstiger størrelsen på RAM, vil vi åpenbart få - ut av minnefeil. Og programmet vil ikke fungere.
Dette problemet kan løses ved hjelp av ferdige løsninger som f.eks Eller .
Kort sagt, vi trenger en database som lar oss gjøre tre operasjoner raskt.
- Den første operasjonen er opptak
ключ-значениеtil denne databasen. Hun gjør dette veldig raskt, hvorключ-значениеer vilkårlige strenger. - Den andre operasjonen er et raskt søk etter en verdi ved hjelp av en gitt nøkkel.
- Og den tredje operasjonen er et raskt søk etter alle verdier med et gitt prefiks.
LevelDB og RocksDB - disse databasene ble utviklet av Google og Facebook. Først kom LevelDB. Så tok gutta fra Facebook LevelDB og begynte å forbedre det, de laget RocksDB. Nå fungerer nesten alle interne databaser på RocksDB inne på Facebook, inkludert de som er overført til RocksDB og MySQL. De ga ham navn .
En invertert indeks kan implementeres ved hjelp av LevelDB. Hvordan gjøre det? Vi lagrer som nøkkel label=value. Og verdien er identifikatoren for tidsserien der paret er til stede label=value.
Hvis vi har mange tidsserier med et gitt par label=value, så vil det være mange rader i denne databasen med samme nøkkel og forskjellige timeseries_ids. For å få en liste over alle timeseries_ids, som starter med dette label=prefix, gjør vi en rekkeviddeskanning som denne databasen er optimalisert for. Det vil si at vi velger alle linjer som begynner med label=prefix og få det nødvendige timeseries_ids.
Her er et eksempel på implementering av hvordan det vil se ut i Go. Vi har en invertert indeks. Dette er LevelDB.
Funksjonen er den samme som for den naive implementeringen. Den gjentar den naive implementeringen nesten linje for linje. Det eneste poenget er at i stedet for å vende seg til map vi får tilgang til den inverterte indeksen. Vi får alle verdiene for det første label=value. Deretter går vi gjennom alle de resterende parene label=value og få de tilsvarende settene med metriske IDer for dem. Så finner vi krysset.
Alt ser ut til å være bra, men det er ulemper med denne løsningen. VictoriaMetrics implementerte opprinnelig en invertert indeks basert på LevelDB. Men til slutt måtte jeg gi opp.
Hvorfor? Fordi LevelDB er tregere enn den naive implementeringen. I en naiv implementering, gitt en gitt nøkkel, henter vi umiddelbart hele skiven metricIDs. Dette er en veldig rask operasjon - hele skiven er klar til bruk.
I LevelDB, hver gang en funksjon kalles GetValues du må gå gjennom alle linjene som begynner med label=value. Og få verdien for hver linje timeseries_ids. Av sånn timeseries_ids samle en skive av disse timeseries_ids. Dette er åpenbart mye tregere enn å bare få tilgang til et vanlig kart med nøkkel.
Den andre ulempen er at LevelDB er skrevet i C. Å ringe C-funksjoner fra Go er ikke veldig raskt. Det tar hundrevis av nanosekunder. Dette er ikke veldig raskt, for sammenlignet med et vanlig funksjonskall skrevet i gang, som tar 1-5 nanosekunder, er forskjellen i ytelse titalls ganger. For VictoriaMetrics var dette en fatal feil :)
Så jeg skrev min egen implementering av den inverterte indeksen. Og han ringte henne .
Mergeset er basert på MergeTree-datastrukturen. Denne datastrukturen er lånt fra ClickHouse. Tydeligvis bør mergeset optimaliseres for raskt søk timeseries_ids i henhold til den gitte nøkkelen. Mergeset er skrevet helt i Go. Du kan se . Implementeringen av mergeset er i mappen . Du kan prøve å finne ut hva som skjer der.
Mergeset API er veldig lik LevelDB og RocksDB. Det vil si at den lar deg raskt lagre nye poster der og raskt velge poster med et gitt prefiks.
Vi vil snakke om ulempene med mergeset senere. La oss nå snakke om hvilke problemer som oppsto med VictoriaMetrics i produksjonen ved implementering av en invertert indeks.
Hvorfor oppsto de?
Den første grunnen er den høye churn rate. Oversatt til russisk er dette en hyppig endring i tidsserier. Dette er når en tidsserie slutter og en ny serie begynner, eller mange nye tidsserier begynner. Og dette skjer ofte.
Den andre grunnen er det store antallet tidsserier. I begynnelsen, da overvåking ble stadig mer populær, var antallet tidsserier lite. For hver datamaskin må du for eksempel overvåke CPU, minne, nettverk og diskbelastning. 4 tidsserier per datamaskin. La oss si at du har 100 datamaskiner og 400 tidsserier. Dette er veldig lite.
Over tid fant folk ut at de kunne måle mer detaljert informasjon. Mål for eksempel belastningen ikke for hele prosessoren, men separat for hver prosessorkjerne. Hvis du har 40 prosessorkjerner, har du 40 ganger flere tidsserier for å måle prosessorbelastning.
Men det er ikke alt. Hver prosessorkjerne kan ha flere tilstander, for eksempel inaktiv, når den er inaktiv. Og også arbeid i brukerrom, arbeid i kjerneplass og andre tilstander. Og hver slik tilstand kan også måles som en egen tidsserie. Dette øker i tillegg antall rader med 7-8 ganger.
Fra én beregning fikk vi 40 x 8 = 320 beregninger for bare én datamaskin. Multipliser med 100, får vi 32 000 i stedet for 400.
Så kom Kubernetes. Og det ble verre fordi Kubernetes kan være vert for mange forskjellige tjenester. Hver tjeneste i Kubernetes består av mange pods. Og alt dette må overvåkes. I tillegg har vi en konstant utrulling av nye versjoner av tjenestene dine. For hver ny versjon må det opprettes nye tidsserier. Som et resultat vokser antallet tidsserier eksponentielt og vi står overfor problemet med et stort antall tidsserier, som kalles høykardinalitet. VictoriaMetrics takler det med hell sammenlignet med andre tidsseriedatabaser.
La oss se nærmere på høy churn rate. Hva forårsaker en høy churn rate i produksjonen? Fordi noen betydninger av etiketter og etiketter er i konstant endring.
Ta for eksempel Kubernetes, som har konseptet deployment, det vil si når en ny versjon av applikasjonen din rulles ut. Av en eller annen grunn bestemte Kubernetes-utviklerne seg for å legge til distribusjons-IDen til etiketten.
Hva førte dette til? Dessuten, med hver nye distribusjon, blir alle de gamle tidsseriene avbrutt, og i stedet for dem begynner nye tidsserier med en ny etikettverdi deployment_id. Det kan være hundretusener og til og med millioner av slike rader.
Det viktige med alt dette er at det totale antallet tidsserier vokser, men antallet tidsserier som for øyeblikket er aktive og mottar data forblir konstant. Denne tilstanden kalles høy churn rate.
Hovedproblemet med høy churn rate er å sikre en konstant søkehastighet for alle tidsserier for et gitt sett med etiketter over et visst tidsintervall. Vanligvis er dette tidsintervallet for den siste timen eller den siste dagen.
Hvordan løse dette problemet? Her er det første alternativet. Dette for å dele den inverterte indeksen i uavhengige deler over tid. Det vil si at det går noe tidsintervall, vi avslutter arbeidet med den nåværende inverterte indeksen. Og lag en ny invertert indeks. Et nytt tidsintervall går, vi skaper en og en til.
Og når vi prøver fra disse inverterte indeksene, finner vi et sett med inverterte indekser som faller innenfor det gitte intervallet. Og følgelig velger vi id-en til tidsserien derfra.
Dette sparer ressurser fordi vi ikke trenger å se på deler som ikke faller innenfor det gitte intervallet. Det vil si at hvis vi velger data for den siste timen, hopper vi over forespørsler for tidligere tidsintervaller.
Det er et annet alternativ for å løse dette problemet. Dette er for å lagre for hver dag en egen liste over IDer for tidsserier som fant sted den dagen.
Fordelen med denne løsningen fremfor den forrige løsningen er at vi ikke dupliserer tidsserieinformasjon som ikke forsvinner over tid. De er konstant tilstede og forandrer seg ikke.
Ulempen er at en slik løsning er vanskeligere å implementere og vanskeligere å feilsøke. Og VictoriaMetrics valgte denne løsningen. Slik skjedde det historisk. Denne løsningen fungerer også bra sammenlignet med den forrige. Fordi denne løsningen ikke ble implementert på grunn av det faktum at det er nødvendig å duplisere data i hver partisjon for tidsserier som ikke endres, dvs. som ikke forsvinner over tid. VictoriaMetrics var først og fremst optimalisert for diskplassforbruk, og den forrige implementeringen gjorde diskplassforbruket verre. Men denne implementeringen er bedre egnet for å minimere diskplassforbruk, så den ble valgt.
Jeg måtte kjempe mot henne. Kampen var at i denne implementeringen må du fortsatt velge et mye større antall timeseries_ids for data enn når den inverterte indeksen er tidspartisjonert.
Hvordan løste vi dette problemet? Vi løste det på en original måte – ved å lagre flere tidsserieidentifikatorer i hver invertert indeksoppføring i stedet for én identifikator. Det vil si at vi har en nøkkel label=value, som forekommer i hver tidsserie. Og nå sparer vi flere timeseries_ids i én oppføring.
Her er et eksempel. Tidligere hadde vi N oppføringer, men nå har vi en oppføring hvis prefiks er det samme som alle de andre. For forrige oppføring inneholder verdien alle tidsserie-ID-er.
Dette gjorde det mulig å øke skannehastigheten til en slik invertert indeks opptil 10 ganger. Og det tillot oss å redusere minneforbruket for cachen, for nå lagrer vi strengen label=value bare én gang i cachen sammen N ganger. Og denne linjen kan bli stor hvis du lagrer lange linjer i tagger og etiketter, som Kubernetes liker å skyve dit.
Et annet alternativ for å øke hastigheten på søk på en invertert indeks er sharding. Opprette flere inverterte indekser i stedet for én og dele data mellom dem med nøkkel. Dette er et sett key=value damp. Det vil si at vi får flere uavhengige inverterte indekser, som vi kan spørre parallelt på flere prosessorer. Tidligere implementeringer tillot kun drift i enkeltprosessormodus, dvs. skanning av data på bare én kjerne. Denne løsningen lar deg skanne data på flere kjerner samtidig, slik ClickHouse liker å gjøre. Det er dette vi planlegger å gjennomføre.
La oss nå gå tilbake til sauene våre - til kryssfunksjonen timeseries_ids. La oss vurdere hvilke implementeringer det kan være. Denne funksjonen lar deg finne timeseries_ids for et gitt sett label=value.
Det første alternativet er en naiv implementering. To nestede løkker. Her får vi funksjonsinngangen intersectInts to skiver - a и b. Ved utgangen skal den returnere til oss skjæringspunktet mellom disse skivene.
En naiv implementering ser slik ut. Vi itererer over alle verdier fra skive a, inne i denne løkken går vi gjennom alle verdiene til skive b. Og vi sammenligner dem. Hvis de samsvarer, så har vi funnet et veikryss. Og lagre den inn result.
Hva er ulempene? Kvadratisk kompleksitet er dens største ulempe. For eksempel hvis dimensjonene dine er skive a и b en million om gangen, så vil denne funksjonen aldri gi deg svar. Fordi det vil trenge en trillion iterasjoner, noe som er mye selv for moderne datamaskiner.
Den andre implementeringen er basert på kart. Vi lager kart. Vi legger alle verdiene fra slice inn i dette kartet a. Deretter går vi gjennom skive i en egen løkke b. Og vi sjekker om denne verdien er fra skive b i kartet. Hvis den eksisterer, legg den til i resultatet.
Hva er fordelene? Fordelen er at det kun er lineær kompleksitet. Det vil si at funksjonen vil utføres mye raskere for større skiver. For et stykke på millionstørrelse, vil denne funksjonen utføres i 2 millioner iterasjoner, i motsetning til trillioner iterasjoner av den forrige funksjonen.
Ulempen er at denne funksjonen krever mer minne for å lage dette kartet.
Den andre ulempen er den store overheaden for hashing. Denne ulempen er ikke særlig åpenbar. Og for oss var det heller ikke veldig åpenbart, så først i VictoriaMetrics var implementeringen av krysset gjennom et kart. Men så viste profilering at hovedprosessortiden brukes på å skrive til kartet og sjekke om det er en verdi i dette kartet.
Hvorfor er CPU-tid bortkastet på disse stedene? Fordi Go utfører en hashing-operasjon på disse linjene. Det vil si at den beregner hashen til nøkkelen for deretter å få tilgang til den ved en gitt indeks i HashMap. Hash-beregningsoperasjonen er fullført på titalls nanosekunder. Dette er tregt for VictoriaMetrics.
Jeg bestemte meg for å implementere et bitsett optimalisert spesielt for dette tilfellet. Slik ser nå skjæringspunktet mellom to skiver ut. Her lager vi et bitsett. Vi legger til elementer fra den første skiven til den. Deretter sjekker vi tilstedeværelsen av disse elementene i den andre skiven. Og legg dem til resultatet. Det vil si at det nesten ikke er forskjellig fra forrige eksempel. Det eneste her er at vi erstattet tilgang til kart med tilpassede funksjoner add и has.
Ved første øyekast ser det ut til at dette burde fungere langsommere, hvis det tidligere ble brukt et standardkart der, og da kalles noen andre funksjoner, men profilering viser at denne tingen fungerer 10 ganger raskere enn standardkartet i tilfellet med VictoriaMetrics.
I tillegg bruker den mye mindre minne sammenlignet med kartimplementeringen. Fordi vi lagrer biter her i stedet for åtte-byte verdier.
Ulempen med denne implementeringen er at den ikke er så åpenbar, ikke triviell.
En annen ulempe som mange kanskje ikke legger merke til, er at denne implementeringen kanskje ikke fungerer bra i noen tilfeller. Det vil si at den er optimalisert for et spesifikt tilfelle, for dette tilfellet med skjæringspunktet mellom VictoriaMetrics tidsserie-IDer. Dette betyr ikke at det passer for alle tilfeller. Hvis den brukes feil, vil vi ikke få en ytelsesøkning, men en feil med tomt minne og en nedgang i ytelsen.
La oss vurdere implementeringen av denne strukturen. Hvis du vil se, ligger den i VictoriaMetrics-kildene, i mappen . Den er optimalisert spesifikt for VictoriaMetrics-saken, hvor timeseries_id er en 64-bits verdi, der de første 32 bitene i utgangspunktet er konstante og bare de siste 32 bitene endres.
Denne datastrukturen er ikke lagret på disk, den fungerer kun i minnet.
Her er dens API. Det er ikke veldig komplisert. API-en er skreddersydd spesifikt til et spesifikt eksempel på bruk av VictoriaMetrics. Det vil si at det ikke er noen unødvendige funksjoner her. Her er funksjonene som eksplisitt brukes av VictoriaMetrics.
Det er funksjoner add, som tilfører nye verdier. Det er en funksjon has, som ser etter nye verdier. Og det er en funksjon del, som fjerner verdier. Det er en hjelpefunksjon len, som returnerer størrelsen på settet. Funksjon clone kloner mye. Og funksjon appendto konverterer dette settet til skive timeseries_ids.
Slik ser implementeringen av denne datastrukturen ut. settet har to elementer:
-
ItemsCounter et hjelpefelt for raskt å returnere antall elementer i et sett. Det ville vært mulig å klare seg uten dette hjelpefeltet, men det måtte legges til her fordi VictoriaMetrics ofte spør etter bitsettlengden i sine algoritmer. -
Det andre feltet er
buckets. Dette er et stykke fra strukturenbucket32. Hver struktur lagrerhifelt. Dette er de øverste 32 bitene. Og to skiver -b16hisиbucketsavbucket16strukturer.
De øverste 16 bitene i den andre delen av 64-bits strukturen er lagret her. Og her lagres bitsett for de nederste 16 bitene av hver byte.
Bucket64 består av en matrise uint64. Lengden beregnes ved hjelp av disse konstantene. I en bucket16 maksimalt kan lagres 2^16=65536 bit. Hvis du deler dette på 8, så er det 8 kilobyte. Hvis du deler på 8 igjen, er det 1000 uint64 betydning. Det er Bucket16 – dette er vår 8-kilobyte struktur.
La oss se på hvordan en av metodene til denne strukturen for å legge til en ny verdi implementeres.
Det hele begynner med uint64 betydninger. Vi beregner de øvre 32 bitene, vi beregner de nedre 32 bitene. La oss gå gjennom alt buckets. Vi sammenligner de 32 beste bitene i hver bøtte med verdien som legges til. Og hvis de samsvarer, kaller vi funksjonen add i struktur b32 buckets. Og legg til de nederste 32 bitene der. Og om den kom tilbake true, så betyr dette at vi la til en slik verdi der og vi hadde ikke en slik verdi. Hvis den kommer tilbake false, da eksisterte en slik betydning allerede. Deretter øker vi antall elementer i strukturen.
Hvis vi ikke har funnet den du trenger bucket med den nødvendige hi-verdien, kaller vi funksjonen addAlloc, som vil produsere en ny bucket, legger den til bøttestrukturen.
Dette er implementeringen av funksjonen b32.add. Det ligner på forrige implementering. Vi beregner de mest signifikante 16 bitene, de minst signifikante 16 bitene.
Deretter går vi gjennom alle de øverste 16 bitene. Vi finner matcher. Og hvis det er en match, kaller vi add-metoden, som vi vil vurdere på neste side for bucket16.
Og her er det laveste nivået, som bør optimaliseres så mye som mulig. Vi beregner for uint64 id-verdi i skivebit og også bitmask. Dette er en maske for en gitt 64-bits verdi, som kan brukes til å sjekke tilstedeværelsen av denne biten, eller sette den. Vi sjekker om denne biten er satt og setter den inn, og returnerer tilstedeværelse. Dette er implementeringen vår, som tillot oss å øke hastigheten på driften av kryssende IDer for tidsserier med 10 ganger sammenlignet med konvensjonelle kart.
I tillegg til denne optimaliseringen har VictoriaMetrics mange andre optimaliseringer. De fleste av disse optimaliseringene ble lagt til av en grunn, men etter profilering av koden i produksjonen.
Dette er hovedregelen for optimalisering - ikke legg til optimalisering forutsatt at det vil være en flaskehals her, fordi det kan vise seg at det ikke vil være en flaskehals der. Optimalisering forringer vanligvis kvaliteten på koden. Derfor er det verdt å optimalisere først etter profilering og gjerne i produksjon, slik at dette er reelle data. Hvis noen er interessert, kan du se på VictoriaMetrics kildekode og utforske andre optimaliseringer som er der.
Jeg har et spørsmål om bitset. Svært lik C++ vektor bool-implementeringen, optimalisert bitsett. Tok du implementeringen derfra?
Nei, ikke derfra. Da jeg implementerte dette bitsettet, ble jeg veiledet av kunnskap om strukturen til disse ids-tidsseriene, som brukes i VictoriaMetrics. Og strukturen deres er slik at de øvre 32 bitene er i utgangspunktet konstante. De nederste 32 bitene kan endres. Jo lavere bit, jo oftere kan det endres. Derfor er denne implementeringen spesifikt optimalisert for denne datastrukturen. C++-implementeringen, så vidt jeg vet, er optimalisert for det generelle tilfellet. Hvis du optimaliserer for den generelle saken, betyr dette at det ikke vil være det mest optimale for en spesifikk sak.
Jeg anbefaler deg også å se rapporten til Alexey Milovid. For omtrent en måned siden snakket han om optimalisering i ClickHouse for spesifikke spesialiseringer. Han sier bare at i det generelle tilfellet er en C++-implementering eller en annen implementering skreddersydd for å fungere godt i gjennomsnitt på et sykehus. Den kan yte dårligere enn en kunnskapsspesifikk implementering som vår, der vi vet at de øverste 32 bitene stort sett er konstante.
Jeg har et andre spørsmål. Hva er den grunnleggende forskjellen fra InfluxDB?
Det er mange grunnleggende forskjeller. Når det gjelder ytelse og minneforbruk, viser InfluxDB i tester 10 ganger mer minneforbruk for tidsserier med høy kardinalitet, når du har mange av dem, for eksempel millioner. For eksempel bruker VictoriaMetrics 1 GB per million aktive rader, mens InfluxDB bruker 10 GB. Og det er en stor forskjell.
Den andre grunnleggende forskjellen er at InfluxDB har merkelige søkespråk - Flux og InfluxQL. De er ikke særlig praktiske å jobbe med tidsserier i forhold til , som støttes av VictoriaMetrics. PromQL er et spørrespråk fra Prometheus.
Og en annen forskjell er at InfluxDB har en litt merkelig datamodell, der hver linje kan lagre flere felt med forskjellige sett med tagger. Disse linjene er videre delt inn i ulike tabeller. Disse ekstra komplikasjonene kompliserer påfølgende arbeid med denne databasen. Det er vanskelig å støtte og forstå.
I VictoriaMetrics er alt mye enklere. Der er hver tidsserie en nøkkelverdi. Verdien er et sett med poeng - (timestamp, value), og nøkkelen er settet label=value. Det er ingen skille mellom felt og mål. Den lar deg velge hvilken som helst data og deretter kombinere, addere, subtrahere, multiplisere, dividere, i motsetning til InfluxDB hvor beregninger mellom forskjellige rader fortsatt ikke er implementert så vidt jeg vet. Selv om de er implementert er det vanskelig, du må skrive mye kode.
Jeg har et oppklarende spørsmål. Forsto jeg riktig at det var en slags problem du snakket om, at denne inverterte indeksen ikke passer inn i minnet, så det er partisjonering der?
Først viste jeg en naiv implementering av en invertert indeks på et standard Go-kart. Denne implementeringen er ikke egnet for databaser fordi denne inverterte indeksen ikke er lagret på disk, og databasen må lagre på disk slik at disse dataene forblir tilgjengelige ved omstart. I denne implementeringen, når du starter applikasjonen på nytt, vil den inverterte indeksen forsvinne. Og du vil miste tilgangen til alle dataene fordi du ikke vil kunne finne den.
Hallo! Takk for rapporten! Jeg heter Pavel. Jeg er fra Wildberries. Jeg har noen spørsmål til deg. Spørsmål en. Tror du at hvis du hadde valgt et annet prinsipp når du bygde arkitekturen til applikasjonen din og partisjonert dataene over tid, så ville du kanskje ha vært i stand til å krysse data når du søker, kun basert på det faktum at en partisjon inneholder data for en tidsperiode , det vil si i ett tidsintervall, og du trenger ikke å bekymre deg for det faktum at brikkene dine er spredt annerledes? Spørsmål nummer 2 - siden du implementerer en lignende algoritme med bitsett og alt annet, så har du kanskje prøvd å bruke prosessorinstruksjoner? Kanskje du har prøvd slike optimaliseringer?
Jeg svarer på den andre med en gang. Vi har ikke kommet til det punktet ennå. Men om nødvendig kommer vi dit. Og det første, hva var spørsmålet?
Du diskuterte to scenarier. Og de sa at de valgte den andre med en mer kompleks implementering. Og de foretrakk ikke den første, hvor dataene er partisjonert etter tid.
Ja. I det første tilfellet vil det totale volumet av indeksen være større, fordi vi i hver partisjon må lagre dupliserte data for de tidsseriene som fortsetter gjennom alle disse partisjonene. Og hvis tidsseriens churn rate er liten, det vil si at de samme seriene brukes konstant, vil vi i det første tilfellet miste mye mer i mengden diskplass som er okkupert sammenlignet med det andre tilfellet.
Og så - ja, tidspartisjonering er et godt alternativ. Prometheus bruker det. Men Prometheus har en annen ulempe. Når du slår sammen disse dataene, må den lagre metainformasjon for alle etiketter og tidsserier i minnet. Derfor, hvis databitene som den slår sammen er store, øker minneforbruket veldig mye under sammenslåing, i motsetning til VictoriaMetrics. Ved sammenslåing bruker ikke VictoriaMetrics minne i det hele tatt; bare et par kilobyte forbrukes, uavhengig av størrelsen på de sammenslåtte dataene.
Algoritmen du bruker bruker minne. Den markerer tidsserie-tagger som inneholder verdier. Og på denne måten sjekker du for sammenkoblet tilstedeværelse i én datamatrise og i en annen. Og du forstår om krysset skjedde eller ikke. Vanligvis implementerer databaser markører og iteratorer som lagrer deres nåværende innhold og kjører gjennom de sorterte dataene på grunn av den enkle kompleksiteten til disse operasjonene.
Hvorfor bruker vi ikke markører for å krysse data?
Ja.
Vi lagrer sorterte rader i LevelDB eller mergeset. Vi kan flytte markøren og finne krysset. Hvorfor bruker vi det ikke? Fordi det går sakte. Fordi markører betyr at du må kalle en funksjon for hver linje. Et funksjonskall er 5 nanosekunder. Og hvis du har 100 000 000 linjer, så viser det seg at vi bruker et halvt sekund på å bare ringe funksjonen.
Det er noe slikt, ja. Og mitt siste spørsmål. Spørsmålet høres kanskje litt merkelig ut. Hvorfor er det ikke mulig å lese alle nødvendige aggregater i det øyeblikket dataene kommer og lagre dem i ønsket form? Hvorfor spare store volumer i noen systemer som VictoriaMetrics, ClickHouse osv., og deretter bruke mye tid på dem?
Jeg skal gi et eksempel for å gjøre det klarere. La oss si hvordan fungerer et lite lekespeedometer? Den registrerer avstanden du har reist, hele tiden legger den til én verdi, og den andre - gang. Og deler. Og får gjennomsnittsfart. Du kan gjøre omtrent det samme. Legg sammen alle nødvendige fakta på et øyeblikk.
Ok, jeg forstår spørsmålet. Ditt eksempel har sin plass. Hvis du vet hvilke aggregater du trenger, er dette den beste implementeringen. Men problemet er at folk lagrer disse beregningene, noen data i ClickHouse, og de vet ennå ikke hvordan de vil samle og filtrere dem i fremtiden, så de må lagre alle rådataene. Men hvis du vet at du trenger å beregne noe i gjennomsnitt, hvorfor ikke beregne det i stedet for å lagre en haug med råverdier der? Men dette er bare hvis du vet nøyaktig hva du trenger.
Forresten, databaser for lagring av tidsserier støtter telling av aggregater. For eksempel støtter Prometheus . Det vil si at dette kan gjøres hvis du vet hvilke enheter du trenger. VictoriaMetrics har ikke dette ennå, men det er vanligvis innledet med Prometheus, der dette kan gjøres i omkodingsreglene.
For eksempel, i min forrige jobb trengte jeg å telle antall hendelser i et skyvevindu den siste timen. Problemet er at jeg måtte lage en tilpasset implementering i Go, det vil si en tjeneste for å telle denne tingen. Denne tjenesten var til syvende og sist ikke-triviell, fordi den er vanskelig å beregne. Implementeringen kan være enkel hvis du trenger å telle noen aggregater med faste tidsintervaller. Hvis du vil telle hendelser i et skyvevindu, er det ikke så enkelt som det ser ut til. Jeg tror dette ennå ikke er implementert i ClickHouse eller i tidsseriedatabaser, fordi det er vanskelig å implementere.
Og ett spørsmål til. Vi snakket bare om gjennomsnittsberegning, og jeg husket at det en gang fantes noe som Graphite med en Carbon-backend. Og han visste hvordan han skulle tynne ut gamle data, det vil si å legge igjen ett poeng per minutt, ett poeng per time osv. I prinsippet er dette ganske praktisk hvis vi trenger rådata, relativt sett, i en måned, og alt annet kan tynnes ut. Men Prometheus og VictoriaMetrics støtter ikke denne funksjonaliteten. Er det planlagt å støtte det? Hvis ikke, hvorfor ikke?
Takk for spørsmålet. Våre brukere stiller dette spørsmålet med jevne mellomrom. De spør når vi vil legge til støtte for nedsampling. Det er flere problemer her. For det første forstår hver bruker downsampling noe annet: noen ønsker å få et hvilket som helst vilkårlig poeng på et gitt intervall, noen vil ha maksimum, minimum, gjennomsnittsverdier. Hvis mange systemer skriver data til databasen din, kan du ikke slå alt sammen. Det kan være at hvert system krever forskjellig tynning. Og dette er vanskelig å gjennomføre.
Og den andre tingen er at VictoriaMetrics, i likhet med ClickHouse, er optimalisert for å jobbe med store mengder rådata, slik at den kan skyve en milliard linjer på mindre enn et sekund hvis du har mange kjerner i systemet ditt. Skanning av tidsseriepunkter i VictoriaMetrics – 50 000 000 poeng per sekund per kjerne. Og denne ytelsen skalerer til eksisterende kjerner. Det vil si at hvis du for eksempel har 20 kjerner, vil du skanne en milliard poeng per sekund. Og denne egenskapen til VictoriaMetrics og ClickHouse reduserer behovet for nedsamling.
En annen funksjon er at VictoriaMetrics effektivt komprimerer disse dataene. Komprimering i gjennomsnitt i produksjon er fra 0,4 til 0,8 byte per punkt. Hvert punkt er et tidsstempel + verdi. Og den er komprimert til mindre enn én byte i gjennomsnitt.
Sergey. Jeg har et spørsmål. Hva er minimum opptakstidskvantum?
Ett millisekund. Vi hadde nylig en samtale med andre utviklere av tidsseriedatabaser. Deres minimumstid er ett sekund. Og i Graphite, for eksempel, er det også ett sekund. I OpenTSDB er det også ett sekund. InfluxDB har nanosekunders presisjon. I VictoriaMetrics er det ett millisekund, fordi i Prometheus er det ett millisekund. Og VictoriaMetrics ble opprinnelig utviklet som fjernlagring for Prometheus. Men nå kan den lagre data fra andre systemer.
Personen jeg snakket med sier de har andre til sekund nøyaktighet - det er nok for dem fordi det avhenger av typen data som blir lagret i tidsseriedatabasen. Hvis dette er DevOps-data eller data fra infrastruktur, der du samler det inn med intervaller på 30 sekunder, per minutt, så er sekunds nøyaktighet nok, du trenger ikke noe mindre. Og hvis du samler inn disse dataene fra høyfrekvente handelssystemer, trenger du nanosekunders nøyaktighet.
Millisekundens nøyaktighet i VictoriaMetrics er også egnet for DevOps-saken, og kan passe for de fleste tilfellene som jeg nevnte i begynnelsen av rapporten. Det eneste som det kanskje ikke er egnet for er høyfrekvente handelssystemer.
Takk skal du ha! Og et annet spørsmål. Hva er kompatibilitet i PromQL?
Full bakoverkompatibilitet. VictoriaMetrics støtter PromQL fullt ut. I tillegg legger den til ytterligere avansert funksjonalitet i PromQL, som kalles . Det er en snakk på YouTube om denne utvidede funksjonaliteten. Jeg talte på Monitoring Meetup våren i St. Petersburg.
Telegram kanal .
Kun registrerte brukere kan delta i undersøkelsen. , vær så snill.
Hva hindrer deg i å bytte til VictoriaMetrics som din langtidslagring for Prometheus? (Skriv i kommentarfeltet, jeg legger det til i avstemningen))
-
71,4%Jeg bruker ikke Prometheus5
-
28,6%Visste ikke om VictoriaMetrics2
7 brukere stemte. 12 brukere avsto.
Kilde: www.habr.com