Gå till optimeringar i VictoriaMetrics. Alexander Valyalkin

Jag föreslår att du läser utskriften av rapporten från sena 2019 av Alexander Valyalkin "Go optimizations in VictoriaMetrics"

VictoriaMetrics — ett snabbt och skalbart DBMS för lagring och bearbetning av data i form av en tidsserie (posten bildar tid och en uppsättning värden som motsvarar denna tid, till exempel erhållen genom periodisk undersökning av sensorernas status eller insamling av metrik).

Här är en länk till videon av denna rapport - https://youtu.be/MZ5P21j_HLE

Diabilder

Berätta för oss om dig själv. Jag är Alexander Valyalkin. Här mitt GitHub-konto. Jag brinner för Go och prestandaoptimering. Jag skrev många användbara och inte särskilt användbara bibliotek. De börjar med antingen fast, eller med quick prefix.

Jag jobbar just nu med VictoriaMetrics. Vad är det och vad gör jag där? Jag kommer att prata om detta i denna presentation.

Sammanfattningen av rapporten är som följer:

• Först ska jag berätta vad VictoriaMetrics är.
• Då ska jag berätta vad tidsserier är.
• Sedan ska jag berätta hur en tidsseriedatabas fungerar.
• Därefter ska jag berätta om databasarkitekturen: vad den består av.
• Och låt oss sedan gå vidare till de optimeringar som VictoriaMetrics har. Detta är en optimering för det inverterade indexet och en optimering för bitsetimplementeringen i Go.

Vet någon i publiken vad VictoriaMetrics är? Wow, många vet redan. Det är goda nyheter. För den som inte vet är detta en tidsseriedatabas. Den är baserad på ClickHouse-arkitekturen, på vissa detaljer om ClickHouse-implementeringen. Till exempel på som: MergeTree, parallell beräkning på alla tillgängliga processorkärnor och prestandaoptimering genom att arbeta på datablock som placeras i processorcachen.

VictoriaMetrics ger bättre datakomprimering än andra tidsseriedatabaser.

Den skalas vertikalt - det vill säga du kan lägga till fler processorer, mer RAM på en dator. VictoriaMetrics kommer att framgångsrikt använda dessa tillgängliga resurser och kommer att förbättra linjär produktivitet.

VictoriaMetrics skalar också horisontellt - det vill säga du kan lägga till ytterligare noder till VictoriaMetrics-klustret, och dess prestanda kommer att öka nästan linjärt.

Som du gissade är VictoriaMetrics en snabb databas, eftersom jag inte kan skriva andra. Och det är skrivet i Go, så jag pratar om det på det här mötet.

Vem vet vad en tidsserie är? Han känner också många människor. En tidsserie är en serie av par (timestamp, значение), där dessa par sorteras efter tid. Värdet är ett flyttal – float64.

Varje tidsserie identifieras unikt med en nyckel. Vad består denna nyckel av? Den består av en icke-tom uppsättning nyckel-värdepar.

Här är ett exempel på en tidsserie. Nyckeln i denna serie är en lista med par: __name__="cpu_usage" är namnet på måtten, instance="my-server" - det här är datorn på vilken detta mått samlas in, datacenter="us-east" - det här är datacentret där den här datorn finns.

Vi slutade med ett tidsserienamn bestående av tre nyckel-värdepar. Denna nyckel motsvarar en lista med par (timestamp, value). t1, t3, t3, ..., tN - det här är tidsstämplar, 10, 20, 12, ..., 15 — motsvarande värden. Detta är CPU-användningen vid en given tidpunkt för en given rad.

Var kan tidsserier användas? Är det någon som har någon aning?

• I DevOps kan du mäta CPU, RAM, nätverk, rps, antal fel osv.
• IoT – vi kan mäta temperatur, tryck, geokoordinater och något annat.
• Även ekonomi – vi kan övervaka priser för alla typer av aktier och valutor.
• Dessutom kan tidsserier användas för att övervaka produktionsprocesser i fabriker. Vi har användare som använder VictoriaMetrics för att övervaka vindkraftverk, för robotar.
• Tidsserier är också användbara för att samla in information från sensorer för olika enheter. Till exempel för en motor; för mätning av däcktryck; för mätning av hastighet, avstånd; för mätning av bensinförbrukning m.m.
• Tidsserier kan också användas för att övervaka flygplan. Varje flygplan har en svart låda som samlar in tidsserier för olika parametrar för flygplanets hälsa. Tidsserier används också inom flygindustrin.
• Sjukvård är blodtryck, puls osv.

Det kan finnas fler applikationer som jag glömt bort, men jag hoppas att du förstår att tidsserier aktivt används i den moderna världen. Och volymen av deras användning växer varje år.

Varför behöver du en tidsseriedatabas? Varför kan du inte använda en vanlig relationsdatabas för att lagra tidsserier?

Eftersom tidsserier vanligtvis innehåller en stor mängd information, vilket är svårt att lagra och bearbeta i konventionella databaser. Därför dök det upp specialiserade databaser för tidsserier. Dessa baser lagrar effektivt poäng (timestamp, value) med den angivna nyckeln. De tillhandahåller ett API för att läsa lagrad data efter nyckel, med ett enda nyckel-värde-par, eller av flera nyckel-värde-par, eller efter regexp. Om du till exempel vill hitta CPU-belastningen för alla dina tjänster i ett datacenter i Amerika, då måste du använda den här pseudofrågan.

Vanligtvis tillhandahåller tidsseriedatabaser specialiserade frågespråk eftersom tidsserier SQL inte är särskilt väl lämpade. Även om det finns databaser som stöder SQL är det inte särskilt lämpligt. Fråga språk som t.ex PromQL, InfluxQL, Flux, Q. Jag hoppas att någon har hört åtminstone ett av dessa språk. Många har säkert hört talas om PromQL. Detta är frågespråket Prometheus.

Så här ser en modern tidsseriedatabasarkitektur ut med VictoriaMetrics som exempel.

Den består av två delar. Detta är lagring för det inverterade indexet och lagring för tidsserievärden. Dessa förråd är separerade.

När en ny post kommer in i databasen kommer vi först åt det inverterade indexet för att hitta tidsserieidentifieraren för en given uppsättning label=value för ett givet mått. Vi hittar denna identifierare och sparar värdet i datalagret.

När en begäran kommer att hämta data från TSDB går vi först till det inverterade indexet. Låt oss få allt timeseries_ids rekord som matchar denna uppsättning label=value. Och sedan får vi all nödvändig data från datalagret, indexerad av timeseries_ids.

Låt oss titta på ett exempel på hur en tidsseriedatabas behandlar en inkommande urvalsfråga.

• Först och främst får hon allt timeseries_ids från ett inverterat index som innehåller de givna paren label=value, eller uppfyller ett givet reguljärt uttryck.
• Sedan hämtar den alla datapunkter från datalagringen vid ett givet tidsintervall för de hittade timeseries_ids.
• Efter detta utför databasen vissa beräkningar på dessa datapunkter, enligt användarens begäran. Och efter det returnerar den svaret.

I den här presentationen kommer jag att berätta om den första delen. Det här är en sökning timeseries_ids genom inverterat index. Du kan se om den andra delen och den tredje delen senare VictoriaMetrics källor, eller vänta tills jag förbereder andra rapporter :)

Låt oss gå vidare till det inverterade indexet. Många kanske tycker att detta är enkelt. Vem vet vad ett inverterat index är och hur det fungerar? Åh, inte så mycket folk längre. Låt oss försöka förstå vad det är.

Det är faktiskt enkelt. Det är helt enkelt en ordbok som mappar en nyckel till ett värde. Vad är en nyckel? Detta par label=valuevar label и value - det här är rader. Och värdena är en uppsättning timeseries_ids, som inkluderar det givna paret label=value.

Inverterat index gör att du snabbt kan hitta allt timeseries_ids, som har gett label=value.

Det låter dig också snabbt hitta timeseries_ids tidsserier för flera par label=value, eller för par label=regexp. Hur går det till? Genom att hitta skärningspunkten för uppsättningen timeseries_ids för varje par label=value.

Låt oss titta på olika implementeringar av det inverterade indexet. Låt oss börja med den enklaste naiva implementeringen. Hon ser ut så här.

Funktion getMetricIDs får en lista med strängar. Varje rad innehåller label=value. Denna funktion returnerar en lista metricIDs.

Hur det fungerar? Här har vi en global variabel som heter invertedIndex. Detta är en vanlig ordbok (map), vilket kommer att mappa strängen till segmentints. Linjen innehåller label=value.

Funktionsimplementering: get metricIDs för det första label=value, sedan går vi igenom allt annat label=value, vi förstår metricIDs för dem. Och ring funktionen intersectInts, som kommer att diskuteras nedan. Och den här funktionen returnerar skärningspunkten mellan dessa listor.

Som du kan se är det inte särskilt komplicerat att implementera ett inverterat index. Men det här är en naiv implementering. Vilka nackdelar har det? Den största nackdelen med den naiva implementeringen är att ett sådant inverterat index lagras i RAM. Efter att ha startat om programmet tappar vi detta index. Det finns ingen lagring av detta index på disk. Ett sådant inverterat index är osannolikt lämpligt för en databas.

Den andra nackdelen är också relaterad till minnet. Det inverterade indexet måste passa in i RAM. Om det överstiger storleken på RAM-minnet, kommer vi uppenbarligen att få ett minnesfel. Och programmet fungerar inte.

Detta problem kan lösas med hjälp av färdiga lösningar som t.ex NivåDBEller StenarDB.

Kort sagt, vi behöver en databas som gör att vi kan göra tre operationer snabbt.

• Den första operationen är inspelning ключ-значение till denna databas. Hon gör det här väldigt snabbt, var ключ-значение är godtyckliga strängar.
• Den andra operationen är en snabb sökning efter ett värde med hjälp av en given nyckel.
• Och den tredje operationen är en snabb sökning efter alla värden med ett givet prefix.

LevelDB och RocksDB - dessa databaser har utvecklats av Google och Facebook. Först kom LevelDB. Sedan tog killarna från Facebook LevelDB och började förbättra det, de gjorde RocksDB. Nu fungerar nästan alla interna databaser på RocksDB inuti Facebook, inklusive de som har överförts till RocksDB och MySQL. De namngav honom MyRocks.

Ett inverterat index kan implementeras med LevelDB. Hur man gör det? Vi sparar som nyckel label=value. Och värdet är identifieraren för tidsserien där paret finns label=value.

Om vi ​​har många tidsserier med ett givet par label=value, då kommer det att finnas många rader i denna databas med samma nyckel och olika timeseries_ids. För att få en lista över alla timeseries_ids, som börjar med detta label=prefix, gör vi en räckviddsskanning för vilken denna databas är optimerad. Det vill säga vi väljer alla rader som börjar med label=prefix och få det nödvändiga timeseries_ids.

Här är ett exempel på hur det skulle se ut i Go. Vi har ett inverterat index. Det här är LevelDB.

Funktionen är densamma som för den naiva implementeringen. Den upprepar den naiva implementeringen nästan rad för rad. Den enda poängen är att istället för att vända sig till map vi kommer åt det inverterade indexet. Vi får alla värden för den första label=value. Sedan går vi igenom alla återstående par label=value och få motsvarande uppsättningar av metricIDs för dem. Sedan hittar vi korsningen.

Allt verkar vara bra, men det finns nackdelar med denna lösning. VictoriaMetrics implementerade initialt ett inverterat index baserat på LevelDB. Men till slut var jag tvungen att ge upp.

Varför? Eftersom LevelDB är långsammare än den naiva implementeringen. I en naiv implementering, givet en given nyckel, hämtar vi omedelbart hela segmentet metricIDs. Detta är en mycket snabb operation - hela skivan är redo att användas.

I LevelDB, varje gång en funktion anropas GetValues du måste gå igenom alla rader som börjar med label=value. Och få värdet för varje rad timeseries_ids. Av sådant timeseries_ids samla en bit av dessa timeseries_ids. Uppenbarligen är detta mycket långsammare än att bara komma åt en vanlig karta med nyckel.

Den andra nackdelen är att LevelDB är skrivet i C. Att anropa C-funktioner från Go går inte särskilt snabbt. Det tar hundratals nanosekunder. Detta är inte särskilt snabbt, för jämfört med ett vanligt funktionsanrop skrivet i go, som tar 1-5 nanosekunder, är skillnaden i prestanda tiotals gånger. För VictoriaMetrics var detta ett ödesdigert fel :)

Så jag skrev min egen implementering av det inverterade indexet. Och han ringde henne mergeset.

Mergeset är baserat på MergeTree-datastrukturen. Denna datastruktur är lånad från ClickHouse. Självklart bör mergeset optimeras för snabb sökning timeseries_ids enligt den givna nyckeln. Mergeset är skrivet helt i Go. Du kan se VictoriaMetrics källor på GitHub. Implementeringen av mergeset finns i mappen /lib/mergeset. Du kan försöka ta reda på vad som händer där.

Mergeset API är väldigt lik LevelDB och RocksDB. Det vill säga att du snabbt kan spara nya poster där och snabbt välja poster med ett givet prefix.

Vi kommer att prata om nackdelarna med mergeset senare. Låt oss nu prata om vilka problem som uppstod med VictoriaMetrics i produktionen när vi implementerade ett inverterat index.

Varför uppstod de?

Den första anledningen är den höga churn rate. Översatt till ryska är detta en frekvent förändring i tidsserier. Det är när en tidsserie slutar och en ny serie börjar, eller många nya tidsserier börjar. Och detta händer ofta.

Det andra skälet är det stora antalet tidsserier. I början, när övervakningen blev populär, var antalet tidsserier litet. Till exempel, för varje dator måste du övervaka CPU, minne, nätverk och diskbelastning. 4 tidsserier per dator. Låt oss säga att du har 100 datorer och 400 tidsserier. Det här är väldigt lite.

Med tiden kom människor på att de kunde mäta mer detaljerad information. Mät till exempel belastningen inte för hela processorn, utan separat för varje processorkärna. Om du har 40 processorkärnor har du 40 gånger fler tidsserier för att mäta processorbelastningen.

Men det är inte allt. Varje processorkärna kan ha flera tillstånd, till exempel inaktiv, när den är inaktiv. Och även arbeta i användarutrymme, arbeta i kärnutrymme och andra tillstånd. Och varje sådant tillstånd kan också mätas som en separat tidsserie. Detta ökar dessutom antalet rader med 7-8 gånger.

Från ett mått fick vi 40 x 8 = 320 mått för bara en dator. Multiplicera med 100, vi får 32 000 istället för 400.

Sedan kom Kubernetes. Och det blev värre eftersom Kubernetes kan vara värd för många olika tjänster. Varje tjänst i Kubernetes består av många poddar. Och allt detta måste övervakas. Dessutom har vi en ständig distribution av nya versioner av dina tjänster. För varje ny version måste nya tidsserier skapas. Som ett resultat växer antalet tidsserier exponentiellt och vi står inför problemet med ett stort antal tidsserier, vilket kallas högkardinalitet. VictoriaMetrics klarar det framgångsrikt jämfört med andra tidsseriedatabaser.

Låt oss ta en närmare titt på hög churn rate. Vad orsakar en hög churn rate i produktionen? Eftersom vissa betydelser av etiketter och taggar förändras hela tiden.

Ta till exempel Kubernetes, som har konceptet deployment, det vill säga när en ny version av din applikation rullas ut. Av någon anledning bestämde sig Kubernetes-utvecklarna för att lägga till distributions-id:t på etiketten.

Vad ledde detta till? Dessutom avbryts alla gamla tidsserier med varje ny implementering, och istället för dem börjar nya tidsserier med ett nytt etikettvärde deployment_id. Det kan finnas hundratusentals och till och med miljoner sådana rader.

Det viktiga med allt detta är att det totala antalet tidsserier växer, men antalet tidsserier som för närvarande är aktiva och tar emot data förblir konstant. Detta tillstånd kallas hög churn rate.

Huvudproblemet med hög churn-hastighet är att säkerställa en konstant sökhastighet för alla tidsserier för en given uppsättning etiketter under ett visst tidsintervall. Vanligtvis är detta tidsintervallet för den sista timmen eller den sista dagen.

Hur löser man detta problem? Här är det första alternativet. Detta för att dela upp det inverterade indexet i oberoende delar över tiden. Det vill säga, ett tidsintervall går, vi slutar arbeta med det aktuella inverterade indexet. Och skapa ett nytt inverterat index. Ännu ett tidsintervall går, vi skapar en till och en till.

Och vid sampling från dessa inverterade index hittar vi en uppsättning inverterade index som faller inom det givna intervallet. Och följaktligen väljer vi id för tidsserien därifrån.

Detta sparar resurser eftersom vi inte behöver titta på delar som inte faller inom det givna intervallet. Det vill säga, vanligtvis, om vi väljer data för den senaste timmen, så hoppar vi över förfrågningar för tidigare tidsintervall.

Det finns ett annat alternativ för att lösa detta problem. Detta är för att lagra en separat lista för varje dag med id för tidsserier som inträffade den dagen.

Fördelen med denna lösning gentemot den tidigare lösningen är att vi inte duplicerar tidsserieinformation som inte försvinner med tiden. De är ständigt närvarande och förändras inte.

Nackdelen är att en sådan lösning är svårare att implementera och svårare att felsöka. Och VictoriaMetrics valde denna lösning. Så här gick det till historiskt. Denna lösning fungerar också bra jämfört med den tidigare. Eftersom denna lösning inte implementerades på grund av att det är nödvändigt att duplicera data i varje partition för tidsserier som inte förändras, d.v.s. som inte försvinner med tiden. VictoriaMetrics var i första hand optimerad för diskutrymmesförbrukning, och den tidigare implementeringen gjorde diskutrymmesförbrukningen värre. Men den här implementeringen är bättre lämpad för att minimera diskutrymmesförbrukningen, så den valdes.

Jag var tvungen att slåss mot henne. Kampen var att i den här implementeringen måste du fortfarande välja ett mycket större antal timeseries_ids för data än när det inverterade indexet är tidspartitionerat.

Hur löste vi detta problem? Vi löste det på ett originellt sätt - genom att lagra flera tidsserieidentifierare i varje inverterad indexpost istället för en identifierare. Det vill säga vi har en nyckel label=value, som förekommer i varje tidsserie. Och nu sparar vi flera timeseries_ids i en post.

Här är ett exempel. Tidigare hade vi N poster, men nu har vi en post vars prefix är detsamma som alla andra. För den föregående posten innehåller värdet alla tidsserie-ID.

Detta gjorde det möjligt att öka skanningshastigheten för ett sådant inverterat index upp till 10 gånger. Och det gjorde det möjligt för oss att minska minnesförbrukningen för cachen, för nu lagrar vi strängen label=value endast en gång i cachen tillsammans N gånger. Och den här raden kan bli stor om du lagrar långa rader i dina taggar och etiketter, som Kubernetes gärna trycker dit.

Ett annat alternativ för att påskynda sökningen på ett inverterat index är skärning. Skapa flera inverterade index istället för ett och dela data mellan dem med nyckel. Det här är ett set key=value ånga. Det vill säga att vi får flera oberoende inverterade index, som vi kan fråga parallellt på flera processorer. Tidigare implementeringar tillät endast drift i enprocessorläge, d.v.s. skanning av data på endast en kärna. Denna lösning låter dig skanna data på flera kärnor samtidigt, som ClickHouse gillar att göra. Detta är vad vi planerar att genomföra.

Låt oss nu återgå till våra får - till korsningsfunktionen timeseries_ids. Låt oss överväga vilka implementeringar det kan finnas. Denna funktion låter dig hitta timeseries_ids för en given uppsättning label=value.

Det första alternativet är en naiv implementering. Två kapslade slingor. Här får vi funktionen input intersectInts två skivor - a и b. Vid utgången bör det återvända till oss skärningspunkten mellan dessa skivor.

En naiv implementering ser ut så här. Vi itererar över alla värden från slice a, inuti denna loop går vi igenom alla värden för skiva b. Och vi jämför dem. Om de matchar, då har vi hittat en korsning. Och spara in den result.

Vilka är nackdelarna? Kvadratisk komplexitet är dess största nackdel. Till exempel om dina dimensioner är skiva a и b en miljon åt gången, då kommer den här funktionen aldrig att ge dig ett svar. Eftersom det kommer att behöva göra en biljon iterationer, vilket är mycket även för moderna datorer.

Den andra implementeringen är baserad på karta. Vi skapar en karta. Vi lägger in alla värden från slice i den här kartan a. Sedan går vi igenom skiva i en separat slinga b. Och vi kontrollerar om detta värde är från skiva b i kartan. Om det finns, lägg till det i resultatet.

Vad är fördelarna? Fördelen är att det bara finns linjär komplexitet. Det vill säga, funktionen kommer att köras mycket snabbare för större skivor. För en miljonstor skiva kommer den här funktionen att köras i 2 miljoner iterationer, i motsats till biljonerna iterationer av den tidigare funktionen.

Nackdelen är att den här funktionen kräver mer minne för att skapa den här kartan.

Den andra nackdelen är den stora overheaden för hash. Denna nackdel är inte särskilt uppenbar. Och för oss var det inte heller särskilt uppenbart, så till en början i VictoriaMetrics var genomförandet av korsningen genom en karta. Men sedan visade profilering att huvudprocessortiden går åt till att skriva till kartan och kontrollera om det finns ett värde i denna karta.

Varför slösas CPU-tid på dessa platser? Eftersom Go utför en hashoperation på dessa rader. Det vill säga, den beräknar nyckelns hash för att sedan komma åt den vid ett givet index i HashMap. Hashberäkningsoperationen slutförs på tiotals nanosekunder. Detta är långsamt för VictoriaMetrics.

Jag bestämde mig för att implementera en bituppsättning optimerad specifikt för det här fallet. Så här ser skärningspunkten mellan två skivor ut nu. Här skapar vi ett bitset. Vi lägger till element från den första skivan till den. Sedan kontrollerar vi närvaron av dessa element i den andra skivan. Och lägg till dem i resultatet. Det vill säga att det nästan inte skiljer sig från det tidigare exemplet. Det enda här är att vi har ersatt åtkomst till kartan med anpassade funktioner add и has.

Vid en första anblick verkar det som att detta borde fungera långsammare, om det tidigare använts en standardkarta där, och då kallas vissa andra funktioner, men profilering visar att denna sak fungerar 10 gånger snabbare än standardkartan i fallet med VictoriaMetrics.

Dessutom använder den mycket mindre minne jämfört med kartimplementeringen. Eftersom vi lagrar bitar här istället för åttabytevärden.

Nackdelen med denna implementering är att den inte är så uppenbar, inte trivial.

En annan nackdel som många kanske inte märker är att denna implementering kanske inte fungerar bra i vissa fall. Det vill säga, den är optimerad för ett specifikt fall, för det här fallet med korsningen av VictoriaMetrics tidsserie-ID. Det betyder inte att det är lämpligt för alla fall. Om den används felaktigt får vi ingen prestandaökning, utan ett fel på minnet och en nedgång i prestanda.

Låt oss överväga implementeringen av denna struktur. Om du vill titta så finns det i VictoriaMetrics källor, i mappen lib/uint64set. Den är optimerad specifikt för VictoriaMetrics-fallet, där timeseries_id är ett 64-bitars värde, där de första 32 bitarna är i princip konstanta och endast de sista 32 bitarna ändras.

Denna datastruktur lagras inte på disk, den fungerar bara i minnet.

Här är dess API. Det är inte särskilt komplicerat. API:et är skräddarsytt specifikt för ett specifikt exempel på användning av VictoriaMetrics. Det vill säga att det inte finns några onödiga funktioner här. Här är de funktioner som uttryckligen används av VictoriaMetrics.

Det finns funktioner add, vilket tillför nya värden. Det finns en funktion has, som söker efter nya värden. Och det finns en funktion del, vilket tar bort värden. Det finns en hjälpfunktion len, vilket returnerar storleken på uppsättningen. Fungera clone klonar mycket. Och funktion appendto konverterar denna uppsättning till skiva timeseries_ids.

Så här ser implementeringen av denna datastruktur ut. set har två element:

• ItemsCount är ett hjälpfält för att snabbt returnera antalet element i en uppsättning. Det skulle vara möjligt att klara sig utan detta hjälpfält, men det måste läggas till här eftersom VictoriaMetrics ofta frågar bituppsättningslängden i sina algoritmer.

• Det andra fältet är buckets. Detta är en skiva från strukturen bucket32. Varje struktur lagrar hi fält. Dessa är de övre 32 bitarna. Och två skivor - b16his и buckets av bucket16 strukturer.

De översta 16 bitarna i den andra delen av 64-bitars strukturen lagras här. Och här lagras bituppsättningar för de lägre 16 bitarna av varje byte.

Bucket64 består av en array uint64. Längden beräknas med dessa konstanter. I ett bucket16 maximalt kan lagras 2^16=65536 bit. Om du delar detta med 8 så är det 8 kilobyte. Om du delar med 8 igen är det 1000 uint64 menande. Det är Bucket16 – det här är vår 8-kilobyte struktur.

Låt oss titta på hur en av metoderna i denna struktur för att lägga till ett nytt värde implementeras.

Allt börjar med uint64 betydelser. Vi beräknar de övre 32 bitarna, vi beräknar de nedre 32 bitarna. Låt oss gå igenom allt buckets. Vi jämför de översta 32 bitarna i varje hink med värdet som läggs till. Och om de matchar, då kallar vi funktionen add i struktur b32 buckets. Och lägg till de lägre 32 bitarna där. Och om det återvände true, då betyder det att vi lagt till ett sådant värde där och att vi inte hade ett sådant värde. Om den kommer tillbaka false, då fanns redan en sådan innebörd. Sedan ökar vi antalet element i strukturen.

Om vi ​​inte har hittat den du behöver bucket med önskat hi-värde, då anropar vi funktionen addAlloc, som kommer att producera en ny bucket, lägga till den i hinkstrukturen.

Detta är implementeringen av funktionen b32.add. Det liknar den tidigare implementeringen. Vi beräknar de mest signifikanta 16 bitarna, de minst signifikanta 16 bitarna.

Sedan går vi igenom alla de övre 16 bitarna. Vi hittar matcher. Och om det finns en matchning kallar vi add-metoden, som vi kommer att överväga på nästa sida för bucket16.

Och här är den lägsta nivån, som bör optimeras så mycket som möjligt. Vi räknar för uint64 id-värde i skivbit och även bitmask. Detta är en mask för ett givet 64-bitars värde, som kan användas för att kontrollera närvaron av denna bit, eller ställa in den. Vi kontrollerar om den här biten är inställd och ställer in den, och återgår närvaro. Detta är vår implementering, som gjorde det möjligt för oss att påskynda driften av korsande id för tidsserier med 10 gånger jämfört med konventionella kartor.

Utöver denna optimering har VictoriaMetrics många andra optimeringar. De flesta av dessa optimeringar lades till av en anledning, men efter profilering av koden i produktionen.

Detta är huvudregeln för optimering - lägg inte till optimering förutsatt att det kommer att finnas en flaskhals här, eftersom det kan visa sig att det inte kommer att finnas en flaskhals där. Optimering försämrar vanligtvis kodens kvalitet. Därför är det värt att optimera först efter profilering och helst i produktion, så att detta är riktiga data. Om någon är intresserad kan du titta på VictoriaMetrics källkod och utforska andra optimeringar som finns där.

Jag har en fråga om bitset. Mycket lik C++ vektorboolimplementeringen, optimerad bituppsättning. Tog du implementeringen därifrån?

Nej, inte därifrån. När jag implementerade denna bituppsättning vägleddes jag av kunskap om strukturen för dessa ids-tidsserier, som används i VictoriaMetrics. Och deras struktur är sådan att de övre 32 bitarna är i princip konstanta. De lägre 32 bitarna kan ändras. Ju lägre bit, desto oftare kan det ändras. Därför är denna implementering specifikt optimerad för denna datastruktur. C++-implementeringen, så vitt jag vet, är optimerad för det allmänna fallet. Om man optimerar för det generella fallet betyder det att det inte blir det mest optimala för ett specifikt fall.

Jag råder dig också att titta på rapporten från Alexey Milovid. För ungefär en månad sedan pratade han om optimering i ClickHouse för specifika specialiseringar. Han säger bara att i det allmänna fallet är en C++-implementering eller någon annan implementering skräddarsydd för att fungera bra i genomsnitt på ett sjukhus. Det kan fungera sämre än en kunskapsspecifik implementering som vår, där vi vet att de översta 32 bitarna är mestadels konstanta.

Jag har en andra fråga. Vad är den grundläggande skillnaden från InfluxDB?

Det finns många grundläggande skillnader. Sett till prestanda och minnesförbrukning visar InfluxDB i tester 10 gånger mer minnesförbrukning för tidsserier med hög kardinalitet, när man har många av dem, till exempel miljoner. Till exempel förbrukar VictoriaMetrics 1 GB per miljon aktiva rader, medan InfluxDB förbrukar 10 GB. Och det är en stor skillnad.

Den andra grundläggande skillnaden är att InfluxDB har konstiga frågespråk - Flux och InfluxQL. De är inte särskilt bekväma att arbeta med tidsserier jämfört med PromQL, som stöds av VictoriaMetrics. PromQL är ett frågespråk från Prometheus.

Och ytterligare en skillnad är att InfluxDB har en lite konstig datamodell, där varje rad kan lagra flera fält med olika taggar. Dessa rader är vidare uppdelade i olika tabeller. Dessa ytterligare komplikationer komplicerar efterföljande arbete med denna databas. Det är svårt att stödja och förstå.

I VictoriaMetrics är allt mycket enklare. Där är varje tidsserie ett nyckel-värde. Värdet är en uppsättning poäng - (timestamp, value), och nyckeln är setet label=value. Det finns ingen åtskillnad mellan fält och mått. Det låter dig välja vilken data som helst och sedan kombinera, addera, subtrahera, multiplicera, dividera, till skillnad från InfluxDB där beräkningar mellan olika rader fortfarande inte är implementerade så vitt jag vet. Även om de är implementerade är det svårt, man måste skriva mycket kod.

Jag har en klargörande fråga. Förstod jag rätt att det var något slags problem som du pratade om, att detta inverterade index inte passar in i minnet, så det finns partitionering där?

Först visade jag en naiv implementering av ett inverterat index på en standard Go-karta. Denna implementering är inte lämplig för databaser eftersom detta inverterade index inte sparas på disk, och databasen måste spara på disk så att denna data förblir tillgänglig vid omstart. I den här implementeringen, när du startar om programmet, kommer ditt inverterade index att försvinna. Och du kommer att förlora tillgången till all data eftersom du inte kommer att kunna hitta den.

Hallå! Tack för rapporten! Jag heter Pavel. Jag kommer från Wildberries. Jag har några frågor till dig. Fråga ett. Tror du att om du hade valt en annan princip när du byggde arkitekturen för din applikation och partitionerat data över tid, så kanske du skulle ha kunnat skära data vid sökning, bara baserat på det faktum att en partition innehåller data för en tidsperiod , det vill säga i ett tidsintervall och du behöver inte oroa dig för att dina pjäser är olika utspridda? Fråga nummer 2 - eftersom du implementerar en liknande algoritm med bitset och allt annat, kanske du försökte använda processorinstruktioner? Kanske har du provat sådana optimeringar?

Jag svarar på den andra direkt. Vi har inte kommit dit än. Men om det behövs kommer vi dit. Och den första, vad var frågan?

Du diskuterade två scenarier. Och de sa att de valde den andra med en mer komplex implementering. Och de föredrog inte den första, där data är uppdelad efter tid.

Ja. I det första fallet skulle den totala volymen av indexet vara större, eftersom vi i varje partition skulle behöva lagra dubblettdata för de tidsserier som fortsätter genom alla dessa partitioner. Och om din tidsserieavgångshastighet är liten, dvs samma serie används ständigt, så skulle vi i det första fallet förlora mycket mer i mängden diskutrymme som upptas jämfört med det andra fallet.

Och så - ja, tidspartitionering är ett bra alternativ. Prometheus använder det. Men Prometheus har en annan nackdel. När du slår samman dessa databitar måste den lagra metainformation för alla etiketter och tidsserier i minnet. Därför, om databitarna som den sammanfogar är stora, ökar minnesförbrukningen väldigt mycket under sammanslagning, till skillnad från VictoriaMetrics. Vid sammanslagning förbrukar VictoriaMetrics inte minne alls, endast ett par kilobyte förbrukas, oavsett storleken på de sammanslagna databitarna.

Algoritmen du använder använder minne. Den markerar tidsserietaggar som innehåller värden. Och på detta sätt kontrollerar du om det finns parad närvaro i en datamatris och i en annan. Och du förstår om korsning inträffade eller inte. Vanligtvis implementerar databaser markörer och iteratorer som lagrar deras nuvarande innehåll och kör igenom de sorterade data på grund av den enkla komplexiteten i dessa operationer.

Varför använder vi inte markörer för att gå igenom data?

Ja.

Vi lagrar sorterade rader i LevelDB eller mergeset. Vi kan flytta markören och hitta korsningen. Varför använder vi det inte? För det går långsamt. Eftersom markörer betyder att du måste anropa en funktion för varje rad. Ett funktionsanrop är 5 nanosekunder. Och om du har 100 000 000 rader, så visar det sig att vi lägger en halv sekund på att bara anropa funktionen.

Det finns en sådan sak, ja. Och min sista fråga. Frågan låter kanske lite konstig. Varför är det inte möjligt att läsa alla nödvändiga aggregat i det ögonblick då data anländer och spara dem i den form som krävs? Varför spara stora volymer i vissa system som VictoriaMetrics, ClickHouse, etc., och sedan spendera mycket tid på dem?

Jag ska ge ett exempel för att göra det tydligare. Låt oss säga hur fungerar en liten leksakshastighetsmätare? Den registrerar sträckan du har tillryggalagt, hela tiden lägger den till ett värde, och den andra - gången. Och delar. Och får medelhastighet. Du kan göra ungefär samma sak. Lägg ihop alla nödvändiga fakta i farten.

Okej, jag förstår frågan. Ditt exempel har sin plats. Om du vet vilka aggregat du behöver är detta den bästa implementeringen. Men problemet är att människor sparar dessa mätvärden, en del data i ClickHouse och de vet ännu inte hur de kommer att samlas och filtrera dem i framtiden, så de måste spara all rådata. Men om du vet att du behöver beräkna något i genomsnitt, varför inte beräkna det istället för att lagra ett gäng råvärden där? Men detta är bara om du vet exakt vad du behöver.

Förresten, databaser för lagring av tidsserier stödjer räkning av aggregat. Prometheus stödjer till exempel inspelningsregler. Det vill säga att detta kan göras om du vet vilka enheter du behöver. VictoriaMetrics har inte detta ännu, men det föregås vanligtvis av Prometheus, där detta kan göras i omkodningsreglerna.

Till exempel, i mitt tidigare jobb behövde jag räkna antalet händelser i ett glidande fönster under den senaste timmen. Problemet är att jag var tvungen att göra en anpassad implementering i Go, det vill säga en tjänst för att räkna den här saken. Denna tjänst var i slutändan icke-trivial, eftersom den är svår att beräkna. Implementeringen kan vara enkel om du behöver räkna några aggregat med fasta tidsintervall. Om du vill räkna händelser i ett glidande fönster, så är det inte så enkelt som det verkar. Jag tror att detta ännu inte har implementerats i ClickHouse eller i tidsseriedatabaser, eftersom det är svårt att implementera.

Och en fråga till. Vi pratade bara om medelvärde, och jag kom ihåg att det en gång fanns något sådant som Graphite med en Carbon-backend. Och han visste hur man tunnade ut gammal data, det vill säga lämna en poäng per minut, en poäng per timme, etc. I princip är detta ganska bekvämt om vi behöver rådata, relativt sett, för en månad, och allt annat kan tunnas ut. Men Prometheus och VictoriaMetrics stöder inte den här funktionen. Är det planerat att stödja det? Om inte, varför inte?

Tack för frågan. Våra användare ställer denna fråga med jämna mellanrum. De frågar när vi kommer att lägga till stöd för nedsampling. Det finns flera problem här. För det första förstår varje användare downsampling något annat: någon vill få vilken godtycklig punkt som helst på ett givet intervall, någon vill ha maximala, lägsta, medelvärden. Om många system skriver data till din databas kan du inte klumpa ihop allt. Det kan vara så att varje system kräver olika gallring. Och detta är svårt att genomföra.

Och det andra är att VictoriaMetrics, precis som ClickHouse, är optimerat för att arbeta med stora mängder rådata, så det kan skyffla en miljard rader på mindre än en sekund om du har många kärnor i ditt system. Skanna tidsseriepunkter i VictoriaMetrics – 50 000 000 poäng per sekund per kärna. Och denna prestanda skalar till befintliga kärnor. Det vill säga, om du till exempel har 20 kärnor kommer du att skanna en miljard poäng per sekund. Och denna egenskap hos VictoriaMetrics och ClickHouse minskar behovet av nedsamling.

En annan funktion är att VictoriaMetrics effektivt komprimerar denna data. Kompression i genomsnitt i produktionen är från 0,4 till 0,8 byte per punkt. Varje punkt är en tidsstämpel + värde. Och den komprimeras till mindre än en byte i genomsnitt.

Sergey. Jag har en fråga. Vad är det minsta kvantumet för inspelningstid?

En millisekund. Vi hade nyligen ett samtal med andra tidsseriedatabasutvecklare. Deras minsta tidsintervall är en sekund. Och i Graphite, till exempel, är det också en sekund. I OpenTSDB är det också en sekund. InfluxDB har nanosekundsprecision. I VictoriaMetrics är det en millisekund, för i Prometheus är det en millisekund. Och VictoriaMetrics utvecklades ursprungligen som fjärrlagring för Prometheus. Men nu kan den spara data från andra system.

Personen jag pratade med säger att de har andra till sekunds noggrannhet - det räcker för dem eftersom det beror på vilken typ av data som lagras i tidsseriedatabasen. Om det här är DevOps-data eller data från infrastruktur, där du samlar in det med intervaller på 30 sekunder, per minut, så räcker det med andras noggrannhet, du behöver inget mindre. Och om du samlar in dessa data från högfrekventa handelssystem, behöver du nanosekundsnoggrannhet.

Millisekundens noggrannhet i VictoriaMetrics är också lämplig för DevOps-fallet, och kan vara lämplig för de flesta fall som jag nämnde i början av rapporten. Det enda som det kanske inte är lämpligt för är högfrekventa handelssystem.

Tack! Och en annan fråga. Vad är kompatibilitet i PromQL?

Full bakåtkompatibilitet. VictoriaMetrics stöder fullt ut PromQL. Dessutom lägger den till ytterligare avancerad funktionalitet i PromQL, som kallas MetricsQL. Det pratas på YouTube om denna utökade funktionalitet. Jag talade på Monitoring Meetup i våras i St. Petersburg.

Telegram kanal VictoriaMetrics.

Endast registrerade användare kan delta i undersökningen. Logga in, Snälla du.

Vad hindrar dig från att byta till VictoriaMetrics som din långtidslagring för Prometheus? (Skriv i kommentarerna, jag lägger till det i omröstningen))

• 71,4%Jag använder inte Prometheus5

• 28,6%Visste inte om VictoriaMetrics2

7 användare röstade. 12 användare avstod från att rösta.

Källa: will.com