Přejděte na optimalizace ve VictoriaMetrics. Alexandr Valjalkin

Navrhuji, abyste si přečetli přepis zprávy z konce roku 2019 od Alexandra Valyalkina „Go optimalizace ve VictoriaMetrics“

VictoriaMetrics — rychlý a škálovatelný DBMS pro ukládání a zpracování dat ve formě časové řady (záznam tvoří čas a soubor hodnot odpovídajících tomuto času, např. získaný periodickým dotazováním na stav senzorů nebo sběrem metriky).

Zde je odkaz na video této zprávy - https://youtu.be/MZ5P21j_HLE

Diapozitivy

Řekněte nám o sobě. Jsem Alexandr Valjalkin. Tady můj účet GitHub. Jsem nadšený pro Go a optimalizaci výkonu. Napsal jsem spoustu užitečných i méně užitečných knihoven. Začínají buď fast, nebo s quick předpona.

Momentálně pracuji na VictoriaMetrics. Co to je a co tam dělám? Budu o tom mluvit v této prezentaci.

Nástin zprávy je následující:

• Nejprve vám řeknu, co je VictoriaMetrics.
• Pak vám řeknu, co jsou časové řady.
• Pak vám řeknu, jak funguje databáze časových řad.
• Dále vám řeknu o architektuře databáze: z čeho se skládá.
• A pak přejdeme k optimalizacím, které má VictoriaMetrics. Toto je optimalizace pro invertovaný index a optimalizace pro implementaci bitové sady v Go.

Ví někdo z publika, co je VictoriaMetrics? Páni, spousta lidí už ví. Je to dobrá zpráva. Pro ty, kteří nevědí, je to databáze časových řad. Je založen na architektuře ClickHouse, na některých detailech implementace ClickHouse. Například na: MergeTree, paralelní výpočet na všech dostupných jádrech procesoru a optimalizace výkonu prací na datových blocích, které jsou umístěny v mezipaměti procesoru.

VictoriaMetrics poskytuje lepší kompresi dat než jiné databáze časových řad.

Vertikálně se škáluje – to znamená, že můžete přidat více procesorů, více RAM na jednom počítači. VictoriaMetrics úspěšně využije tyto dostupné zdroje a zlepší lineární produktivitu.

VictoriaMetrics se také mění horizontálně – to znamená, že do clusteru VictoriaMetrics můžete přidat další uzly a jeho výkon se zvýší téměř lineárně.

Jak jste uhodli, VictoriaMetrics je rychlá databáze, protože nemohu psát další. A je to napsané v Go, takže o tom mluvím na tomto setkání.

Kdo ví, co je časová řada? Zná také spoustu lidí. Časová řada je řada dvojic (timestamp, значение), kde jsou tyto dvojice seřazeny podle času. Hodnota je číslo s pohyblivou řádovou čárkou – float64.

Každá časová řada je jednoznačně identifikována klíčem. Z čeho se tento klíč skládá? Skládá se z neprázdné sady párů klíč–hodnota.

Zde je příklad časové řady. Klíčem této série je seznam párů: __name__="cpu_usage" je název metriky, instance="my-server" – toto je počítač, na kterém se tato metrika shromažďuje, datacenter="us-east" - toto je datové centrum, kde je umístěn tento počítač.

Skončili jsme u názvu časové řady sestávajícího ze tří párů klíč–hodnota. Tento klíč odpovídá seznamu dvojic (timestamp, value). t1, t3, t3, ..., tN - to jsou časová razítka, 10, 20, 12, ..., 15 — odpovídající hodnoty. Toto je využití procesoru v daném čase pro danou sérii.

Kde lze časové řady použít? Má někdo nějaký nápad?

• V DevOps můžete měřit CPU, RAM, síť, rps, počet chyb atd.
• IoT – umíme měřit teplotu, tlak, geo souřadnice a něco dalšího.
• Také finance – můžeme sledovat ceny všech druhů akcií a měn.
• Časové řady lze navíc využít při sledování výrobních procesů v továrnách. Máme uživatele, kteří používají VictoriaMetrics k monitorování větrných turbín pro roboty.
• Časové řady jsou také užitečné pro sběr informací ze senzorů různých zařízení. Například pro motor; pro měření tlaku v pneumatikách; pro měření rychlosti, vzdálenosti; pro měření spotřeby benzínu atd.
• Časové řady lze také použít pro sledování letadel. Každé letadlo má černou skříňku, která shromažďuje časové řady pro různé parametry zdraví letadla. Časové řady se používají také v leteckém průmyslu.
• Zdravotní péče je krevní tlak, puls atd.

Možná existuje více aplikací, na které jsem zapomněl, ale doufám, že chápete, že časové řady se v moderním světě aktivně používají. A objem jejich využití každým rokem roste.

Proč potřebujete databázi časových řad? Proč nemůžete k ukládání časových řad použít běžnou relační databázi?

Protože časové řady obvykle obsahují velké množství informací, které se v běžných databázích obtížně ukládají a zpracovávají. Objevily se proto specializované databáze pro časové řady. Tyto základny efektivně ukládají body (timestamp, value) s daným klíčem. Poskytují rozhraní API pro čtení uložených dat podle klíče, pomocí jednoho páru klíč-hodnota nebo podle více párů klíč-hodnota nebo podle regulárního výrazu. Chcete-li například zjistit zatížení CPU všech vašich služeb v datovém centru v Americe, musíte použít tento pseudodotaz.

Databáze časových řad obvykle poskytují specializované dotazovací jazyky, protože časové řady SQL nejsou příliš vhodné. I když existují databáze, které SQL podporují, není to příliš vhodné. Dotazovací jazyky jako např PromQL, InfluxQL, Proudění, Q. Doufám, že někdo slyšel alespoň jeden z těchto jazyků. Mnoho lidí pravděpodobně slyšelo o PromQL. Toto je dotazovací jazyk Prometheus.

Takto vypadá moderní architektura databází časových řad na příkladu VictoriaMetrics.

Skládá se ze dvou částí. Toto je úložiště pro invertovaný index a úložiště pro hodnoty časových řad. Tato úložiště jsou oddělena.

Když do databáze dorazí nový záznam, nejprve přistoupíme k invertovanému indexu, abychom našli identifikátor časové řady pro danou množinu label=value pro danou metriku. Najdeme tento identifikátor a uložíme hodnotu do datového úložiště.

Když přijde požadavek na načtení dat z TSDB, nejprve přejdeme na invertovaný index. Pojďme všechno timeseries_ids záznamy, které odpovídají této sadě label=value. A pak získáme všechna potřebná data z datového skladu, indexovaná podle timeseries_ids.

Podívejme se na příklad, jak databáze časových řad zpracovává příchozí výběrový dotaz.

• V první řadě dostane všechno timeseries_ids z invertovaného indexu, který obsahuje dané dvojice label=value, nebo splňují daný regulární výraz.
• Poté načte všechny datové body z datového úložiště v daném časovém intervalu pro nalezené timeseries_ids.
• Poté databáze provede některé výpočty na těchto datových bodech podle požadavku uživatele. A poté vrátí odpověď.

V této prezentaci vám povím o první části. Toto je vyhledávání timeseries_ids podle obráceného indexu. Na druhý díl a třetí díl se můžete podívat později Zdroje VictoriaMetrics, nebo počkejte, až připravím další reporty :)

Přejděme k obrácenému indexu. Mnozí si mohou myslet, že je to jednoduché. Kdo ví, co je invertovaný index a jak funguje? Oh, už ne tolik lidí. Pokusme se pochopit, co to je.

Je to vlastně jednoduché. Je to prostě slovník, který mapuje klíč k hodnotě. co je klíč? Tento pár label=valueKde label и value - to jsou čáry. A hodnoty jsou soubor timeseries_ids, který zahrnuje danou dvojici label=value.

Invertovaný index vám umožní rychle najít vše timeseries_ids, které daly label=value.

Umožňuje také rychle najít timeseries_ids časové řady pro několik párů label=value, nebo pro páry label=regexp. Jak se to stane? Hledáním průsečíku množiny timeseries_ids pro každý pár label=value.

Podívejme se na různé implementace invertovaného indexu. Začněme tou nejjednodušší naivní implementací. Vypadá takhle.

Funkce getMetricIDs získá seznam řetězců. Každý řádek obsahuje label=value. Tato funkce vrací seznam metricIDs.

Jak to funguje? Zde máme globální proměnnou tzv invertedIndex. Toto je běžný slovník (map), který namapuje řetězec na slice ints. Řádek obsahuje label=value.

Implementace funkce: get metricIDs pro prvního label=value, pak projdeme vším ostatním label=value, chápeme to metricIDs pro ně. A zavolejte funkci intersectInts, o kterém bude řeč níže. A tato funkce vrací průnik těchto seznamů.

Jak vidíte, implementace invertovaného indexu není příliš složitá. Ale to je naivní implementace. Jaké to má nevýhody? Hlavní nevýhodou naivní implementace je, že takto převrácený index je uložen v RAM. Po restartu aplikace tento index ztratíme. Tento index se neukládá na disk. Takový invertovaný index pravděpodobně nebude vhodný pro databázi.

S pamětí souvisí i druhý nedostatek. Invertovaný index se musí vejít do paměti RAM. Pokud překročí velikost paměti RAM, pak samozřejmě dostaneme - nedostatek paměti. A program nebude fungovat.

Tento problém lze vyřešit pomocí hotových řešení jako např LevelDBNebo RocksDB.

Stručně řečeno, potřebujeme databázi, která nám umožní rychle provést tři operace.

• První operací je nahrávání ключ-значение do této databáze. Dělá to velmi rychle, kde ключ-значение jsou libovolné řetězce.
• Druhou operací je rychlé vyhledání hodnoty pomocí daného klíče.
• A třetí operací je rychlé vyhledání všech hodnot podle daného prefixu.

LevelDB a RocksDB – tyto databáze byly vyvinuty společnostmi Google a Facebook. Nejprve přišel LevelDB. Pak kluci z Facebooku vzali LevelDB a začali ho vylepšovat, udělali RocksDB. Nyní téměř všechny interní databáze fungují na RocksDB uvnitř Facebooku, včetně těch, které byly převedeny do RocksDB a MySQL. Pojmenovali ho MyRocks.

Invertovaný index lze implementovat pomocí LevelDB. Jak to udělat? Uložíme jako klíč label=value. A hodnota je identifikátor časové řady, kde je pár přítomen label=value.

Pokud máme s danou dvojicí mnoho časových řad label=value, pak bude v této databázi mnoho řádků se stejným klíčem a různými timeseries_ids. Chcete-li získat seznam všech timeseries_ids, které začínají tímto label=prefix, provádíme sken rozsahu, pro který je tato databáze optimalizována. To znamená, že vybereme všechny řádky, které začínají label=prefix a získat potřebné timeseries_ids.

Zde je ukázková implementace toho, jak by to vypadalo v Go. Máme obrácený index. Toto je LevelDB.

Funkce je stejná jako u naivní implementace. Téměř řádek po řádku opakuje naivní implementaci. Jediným bodem je, že místo toho, abyste se obrátili k map přistupujeme k obrácenému indexu. Dostaneme všechny hodnoty pro první label=value. Poté projdeme všechny zbývající dvojice label=value a získat pro ně odpovídající sady metricID. Pak najdeme křižovatku.

Vše se zdá být v pořádku, ale toto řešení má své nevýhody. VictoriaMetrics zpočátku implementovala invertovaný index založený na LevelDB. Nakonec jsem to ale musel vzdát.

Proč? Protože LevelDB je pomalejší než naivní implementace. V naivní implementaci s daným klíčem okamžitě načteme celý řez metricIDs. Jedná se o velmi rychlou operaci – celý plátek je připraven k použití.

V LevelDB pokaždé, když je volána funkce GetValues musíte projít všechny řádky, které začínají label=value. A získejte hodnotu pro každý řádek timeseries_ids. Z takových timeseries_ids shromáždit plátek těchto timeseries_ids. Je zřejmé, že je to mnohem pomalejší než jednoduchý přístup k běžné mapě pomocí klíče.

Druhou nevýhodou je, že LevelDB je napsán v C. Volání C funkcí z Go není příliš rychlé. Trvá to stovky nanosekund. To není příliš rychlé, protože oproti běžnému volání funkce napsané v go, které trvá 1-5 nanosekund, je rozdíl ve výkonu desetinásobný. Pro VictoriaMetrics to byla fatální chyba :)

Napsal jsem tedy vlastní implementaci invertovaného indexu. A on jí zavolal mergeset.

Mergeset je založen na datové struktuře MergeTree. Tato datová struktura je vypůjčena od ClickHouse. Je zřejmé, že mergeset by měl být optimalizován pro rychlé vyhledávání timeseries_ids podle daného klíče. Mergeset je celý napsán v Go. Můžeš vidět Zdroje VictoriaMetrics na GitHubu. Implementace mergeset je ve složce /lib/mergeset. Můžete zkusit zjistit, co se tam děje.

Slučovací rozhraní API je velmi podobné LevelDB a RocksDB. To znamená, že vám umožňuje rychle ukládat nové záznamy a rychle vybírat záznamy podle daného prefixu.

O nevýhodách mergesetu si povíme později. Nyní si povíme, jaké problémy vznikly s VictoriaMetrics v produkci při implementaci invertovaného indexu.

Proč vznikly?

Prvním důvodem je vysoká míra odchodu zákazníků. Přeloženo do ruštiny je to častá změna časových řad. To je, když časová řada končí a začíná nová řada nebo začíná mnoho nových časových řad. A to se stává často.

Druhým důvodem je velké množství časových řad. Zpočátku, kdy sledování získávalo na popularitě, byl počet časových řad malý. Například u každého počítače potřebujete sledovat zatížení CPU, paměti, sítě a disku. 4 časové řady na počítač. Řekněme, že máte 100 počítačů a 400 časových řad. To je velmi málo.

Postupem času lidé přišli na to, že mohou měřit podrobnější informace. Změřte například zátěž nikoli celého procesoru, ale každého jádra procesoru zvlášť. Pokud máte 40 procesorových jader, pak máte 40krát více časových řad pro měření zatížení procesoru.

Ale to není vše. Každé jádro procesoru může mít několik stavů, například nečinnost, když je nečinné. A také práci v uživatelském prostoru, práci v prostoru jádra a dalších stavech. A každý takový stav lze měřit i jako samostatnou časovou řadu. Tím se navíc počet řádků zvýší 7-8krát.

Z jedné metriky jsme dostali 40 x 8 = 320 metrik pouze pro jeden počítač. Vynásobíme-li 100, dostaneme 32 000 místo 400.

Pak přišel Kubernetes. A zhoršilo se to, protože Kubernetes může hostovat mnoho různých služeb. Každá služba v Kubernetes se skládá z mnoha modulů. A to vše je potřeba sledovat. Kromě toho máme neustálé nasazování nových verzí vašich služeb. Pro každou novou verzi musí být vytvořena nová časová řada. V důsledku toho počet časových řad exponenciálně roste a my se potýkáme s problémem velkého počtu časových řad, kterému se říká vysoká kardinalita. VictoriaMetrics se s ním ve srovnání s jinými databázemi časových řad vyrovnává úspěšně.

Podívejme se blíže na vysokou míru odchodu. Co způsobuje vysokou míru odchodu ve výrobě? Protože některé významy štítků a značek se neustále mění.

Vezměme si například Kubernetes, který má tento koncept deployment, tj. když je uvedena nová verze vaší aplikace. Z nějakého důvodu se vývojáři Kubernetes rozhodli přidat na štítek ID nasazení.

K čemu to vedlo? Navíc s každým novým nasazením jsou všechny staré časové řady přerušeny a místo nich začínají nové časové řady s novou hodnotou štítku deployment_id. Takových řádků mohou být stovky tisíc a dokonce miliony.

Důležité na tom všem je, že celkový počet časových řad roste, ale počet časových řad, které jsou aktuálně aktivní a přijímají data, zůstává konstantní. Tento stav se nazývá vysoký churn rate.

Hlavním problémem vysokého churn rate je zajistit konstantní rychlost vyhledávání pro všechny časové řady pro danou sadu štítků v určitém časovém intervalu. Obvykle se jedná o časový interval za poslední hodinu nebo poslední den.

Jak tento problém vyřešit? Tady je první možnost. To má za úkol rozdělit obrácený index na nezávislé části v průběhu času. To znamená, že po uplynutí určitého časového intervalu skončíme práci s aktuálním obráceným indexem. A vytvořte nový obrácený index. Ubíhá další časový interval, vytváříme další a další.

A při vzorkování z těchto převrácených indexů najdeme množinu převrácených indexů, které spadají do daného intervalu. A podle toho odtud vybereme id časové řady.

To šetří prostředky, protože se nemusíme dívat na díly, které nespadají do daného intervalu. To znamená, že obvykle, pokud vybereme data za poslední hodinu, pak pro předchozí časové intervaly dotazy vynecháme.

Existuje další možnost, jak tento problém vyřešit. Slouží k uložení samostatného seznamu ID časových řad pro každý den, které se v daný den vyskytly.

Výhodou tohoto řešení oproti předchozímu řešení je, že neduplikujeme informace o časové řadě, které časem nezmizí. Jsou neustále přítomni a nemění se.

Nevýhodou je, že takové řešení je náročnější na implementaci a obtížnější odladění. A toto řešení zvolila společnost VictoriaMetrics. Tak se to historicky stalo. Toto řešení také funguje dobře ve srovnání s předchozím. Protože toto řešení nebylo implementováno z toho důvodu, že je nutné duplikovat data v každém oddílu pro časové řady, které se nemění, tedy v čase nezmizí. VictoriaMetrics byl primárně optimalizován pro spotřebu místa na disku a předchozí implementace spotřebu místa na disku zhoršila. Tato implementace je ale vhodnější pro minimalizaci spotřeby místa na disku, proto byla zvolena.

Musel jsem s ní bojovat. Boj byl v tom, že v této implementaci je stále potřeba zvolit mnohem větší číslo timeseries_ids pro data, než když je invertovaný index časově rozdělen.

Jak jsme tento problém vyřešili? Vyřešili jsme to originálně - uložením více identifikátorů časových řad do každé invertované položky indexu místo jednoho identifikátoru. To znamená, že máme klíč label=value, který se vyskytuje v každé časové řadě. A teď jich několik ušetříme timeseries_ids v jednom vstupu.

Zde je příklad. Dříve jsme měli N záznamů, ale nyní máme jeden záznam, jehož předpona je stejná jako u všech ostatních. U předchozí položky hodnota obsahuje všechna ID časových řad.

To umožnilo zvýšit rychlost skenování takto převráceného indexu až 10x. A to nám umožnilo snížit spotřebu paměti pro cache, protože nyní ukládáme řetězec label=value pouze jednou v keši dohromady Nkrát. A tento řádek může být velký, pokud do svých štítků a štítků ukládáte dlouhé řádky, které tam Kubernetes rád strká.

Další možností, jak urychlit vyhledávání na obráceném indexu, je sharding. Vytvoření několika invertovaných indexů namísto jednoho a sdílení dat mezi nimi pomocí klíče. Toto je sada key=value parní. To znamená, že získáme několik nezávislých invertovaných indexů, které můžeme dotazovat paralelně na několika procesorech. Předchozí implementace umožňovaly provoz pouze v jednoprocesorovém režimu, tedy skenování dat pouze na jednom jádru. Toto řešení umožňuje skenovat data na několika jádrech najednou, jak to s oblibou dělá ClickHouse. To je to, co plánujeme implementovat.

Nyní se vraťme k našim ovečkám – k funkci křižovatky timeseries_ids. Zvažme, jaké implementace mohou existovat. Tato funkce vám umožňuje najít timeseries_ids pro danou sadu label=value.

První možností je naivní implementace. Dvě vnořené smyčky. Zde získáme vstup funkce intersectInts dva plátky - a и b. Na výstupu by nám měl vrátit průsečík těchto řezů.

Naivní implementace vypadá takto. Iterujeme přes všechny hodnoty z řezu a, uvnitř této smyčky procházíme všechny hodnoty řezu b. A porovnáváme je. Pokud se shodují, pak jsme našli křižovatku. A uložte si to result.

Jaké jsou nevýhody? Jeho hlavní nevýhodou je kvadratická složitost. Například, pokud jsou vaše rozměry řez a и b jeden milion najednou, pak vám tato funkce nikdy nevrátí odpověď. Protože bude potřeba provést jeden bilion iterací, což je hodně i pro moderní počítače.

Druhá implementace je založena na mapě. Vytváříme mapu. Všechny hodnoty z řezu jsme vložili do této mapy a. Poté procházíme plátkem v samostatné smyčce b. A zkontrolujeme, zda je tato hodnota z řezu b v mapě. Pokud existuje, přidejte jej do výsledku.

Jaké jsou výhody? Výhodou je, že existuje pouze lineární složitost. To znamená, že u větších řezů se funkce provede mnohem rychleji. U řezu o velikosti milionu se tato funkce provede ve 2 milionech iteracích, na rozdíl od bilionu iterací předchozí funkce.

Nevýhodou je, že tato funkce vyžaduje více paměti pro vytvoření této mapy.

Druhou nevýhodou je velká režie pro hashování. Tato nevýhoda není příliš zřejmá. A pro nás to také nebylo příliš zřejmé, takže nejprve ve VictoriaMetrics byla implementace křižovatky přes mapu. Pak ale profilování ukázalo, že čas hlavního procesoru je strávený zápisem do mapy a kontrolou přítomnosti hodnoty v této mapě.

Proč se na těchto místech plýtvá časem CPU? Protože Go na těchto řádcích provádí operaci hash. To znamená, že vypočítá hash klíče, aby k němu poté přistupoval v daném indexu v HashMap. Operace výpočtu hash je dokončena v desítkách nanosekund. To je pro VictoriaMetrics pomalé.

Rozhodl jsem se implementovat bitset optimalizovaný speciálně pro tento případ. Takto nyní vypadá průnik dvou řezů. Zde vytvoříme bitset. Přidáme do něj prvky z prvního plátku. Poté zkontrolujeme přítomnost těchto prvků ve druhém řezu. A přidejte je k výsledku. To znamená, že se téměř neliší od předchozího příkladu. Jediná věc je, že jsme nahradili přístup k mapě vlastními funkcemi add и has.

Na první pohled se zdá, že by to mělo fungovat pomaleji, pokud se tam dříve používala standardní mapa a pak se volají nějaké další funkce, ale profilování ukazuje, že tato věc funguje 10x rychleji než standardní mapa v případě VictoriaMetrics.

Kromě toho využívá mnohem méně paměti ve srovnání s implementací mapy. Protože zde ukládáme bity místo osmibajtových hodnot.

Nevýhodou této implementace je, že není tak samozřejmá, ne triviální.

Další nevýhodou, které si mnozí nemusí všimnout, je, že tato implementace nemusí v některých případech dobře fungovat. To znamená, že je optimalizován pro konkrétní případ, pro tento případ průniku ID časových řad VictoriaMetrics. To neznamená, že je vhodný pro všechny případy. Pokud se použije nesprávně, nezískáme zvýšení výkonu, ale chybu nedostatku paměti a zpomalení výkonu.

Zvažme implementaci této struktury. Pokud se chcete podívat, nachází se ve zdrojích VictoriaMetrics ve složce lib/uint64set. Je optimalizován speciálně pro případ VictoriaMetrics, kde timeseries_id je 64bitová hodnota, kde prvních 32 bitů je v podstatě konstantních a mění se pouze posledních 32 bitů.

Tato datová struktura není uložena na disku, funguje pouze v paměti.

Zde je jeho API. Není to moc složité. Rozhraní API je přizpůsobeno speciálně pro konkrétní příklad použití VictoriaMetrics. To znamená, že zde nejsou žádné zbytečné funkce. Zde jsou funkce, které VictoriaMetrics výslovně používá.

Existují funkce add, která přidává nové hodnoty. Existuje funkce has, který kontroluje nové hodnoty. A je tu funkce del, který odstraňuje hodnoty. K dispozici je pomocná funkce len, který vrátí velikost sady. Funkce clone hodně klonuje. A funkce appendto převede tuto sadu na řez timeseries_ids.

Takto vypadá implementace této datové struktury. sada má dva prvky:

• ItemsCount je pomocné pole pro rychlé vrácení počtu prvků v sadě. Bylo by možné se obejít bez tohoto pomocného pole, ale muselo se sem přidat, protože VictoriaMetrics se ve svých algoritmech často dotazuje na délku bitsetu.

• Druhé pole je buckets. Toto je řez ze struktury bucket32. Každá struktura ukládá hi pole. Toto je horních 32 bitů. A dva plátky - b16his и buckets z bucket16 struktur.

Zde je uloženo horních 16 bitů druhé části 64bitové struktury. A zde jsou bitové sady uloženy pro spodních 16 bitů každého bajtu.

Bucket64 sestává z pole uint64. Délka se vypočítá pomocí těchto konstant. V jednom bucket16 lze uložit maximum 2^16=65536 bit. Pokud to vydělíte 8, pak je to 8 kilobajtů. Pokud znovu vydělíte 8, je to 1000 uint64 význam. To znamená Bucket16 – toto je naše 8kilobajtová struktura.

Podívejme se, jak je implementována jedna z metod této struktury pro přidání nové hodnoty.

Všechno začíná tím uint64 významy. Počítáme horních 32 bitů, vypočítáme spodních 32 bitů. Pojďme si vše projít buckets. Porovnáváme horních 32 bitů v každém segmentu s přidanou hodnotou. A pokud se shodují, zavoláme funkci add ve struktuře b32 buckets. A přidejte tam spodních 32 bitů. A kdyby se to vrátilo true, tak to znamená, že jsme tam přidali takovou hodnotu a takovou jsme neměli. Pokud se vrátí false, pak už takový význam existoval. Poté zvýšíme počet prvků ve struktuře.

Pokud jsme nenašli ten, který potřebujete bucket s požadovanou vysokou hodnotou, pak zavoláme funkci addAlloc, který vyrobí nový bucketpřidáním do struktury kbelíku.

Jedná se o implementaci funkce b32.add. Je to podobné jako u předchozí implementace. Počítáme nejvýznamnějších 16 bitů, nejméně významných 16 bitů.

Poté projdeme všech horních 16 bitů. Najdeme shody. A pokud existuje shoda, zavoláme metodu add, kterou budeme zvažovat na další stránce bucket16.

A zde je nejnižší úroveň, která by měla být co nejvíce optimalizována. Počítáme pro uint64 hodnota id v bitu řezu a také bitmask. Jedná se o masku pro danou 64bitovou hodnotu, kterou lze přítomnost tohoto bitu zkontrolovat, případně nastavit. Zkontrolujeme, zda je tento bit nastaven a nastavíme jej a vrátíme přítomnost. Toto je naše implementace, která nám umožnila zrychlit provoz protínajících se id časových řad 10x oproti běžným mapám.

Kromě této optimalizace má VictoriaMetrics mnoho dalších optimalizací. Většina těchto optimalizací byla přidána z nějakého důvodu, ale po profilování kódu ve výrobě.

Toto je hlavní pravidlo optimalizace – nepřidávejte optimalizaci za předpokladu, že zde bude úzké hrdlo, protože se může ukázat, že tam úzké hrdlo nebude. Optimalizace obvykle zhoršuje kvalitu kódu. Proto se vyplatí optimalizovat až po vyprofilování a nejlépe ve výrobě, aby se jednalo o reálná data. Pokud by to někoho zajímalo, můžete se podívat na zdrojový kód VictoriaMetrics a prozkoumat další optimalizace, které tam jsou.

Mám dotaz ohledně bitsetu. Velmi podobné implementaci vektorových boolů v C++, optimalizovaná bitová sada. Odtamtud jste převzali realizaci?

Ne, odtud ne. Při implementaci tohoto bitsetu jsem se řídil znalostí struktury těchto časových řad ids, které se používají ve VictoriaMetrics. A jejich struktura je taková, že horních 32 bitů je v podstatě konstantních. Spodních 32 bitů se může změnit. Čím nižší bit, tím častěji se může měnit. Proto je tato implementace speciálně optimalizována pro tuto datovou strukturu. Implementace C++, pokud vím, je optimalizována pro obecný případ. Pokud optimalizujete pro obecný případ, znamená to, že pro konkrétní případ to nebude nejoptimálnější.

Doporučuji vám také sledovat zprávu Alexeje Milovida. Asi před měsícem mluvil o optimalizaci v ClickHouse pro konkrétní specializace. Jen říká, že v obecném případě je implementace C++ nebo nějaká jiná implementace přizpůsobena tak, aby v průměru dobře fungovala v nemocnici. Může fungovat hůře než implementace specifická pro znalosti, jako je ta naše, kde víme, že horních 32 bitů je většinou konstantních.

Mám druhou otázku. Jaký je zásadní rozdíl od InfluxDB?

Zásadních rozdílů je mnoho. Co se týče výkonu a spotřeby paměti, InfluxDB v testech ukazuje 10x větší spotřebu paměti pro časové řady s vysokou kardinalitou, kdy jich máte hodně, třeba miliony. Například VictoriaMetrics spotřebuje 1 GB na milion aktivních řádků, zatímco InfluxDB spotřebuje 10 GB. A to je velký rozdíl.

Druhým zásadním rozdílem je, že InfluxDB má podivné dotazovací jazyky - Flux a InfluxQL. Nejsou příliš vhodné pro práci s časovými řadami oproti PromQL, který je podporován společností VictoriaMetrics. PromQL je dotazovací jazyk od společnosti Prometheus.

A ještě jeden rozdíl je v tom, že InfluxDB má trochu zvláštní datový model, kde každý řádek může uložit několik polí s jinou sadou značek. Tyto řádky jsou dále rozděleny do různých tabulek. Tyto další komplikace komplikují následnou práci s touto databází. Je těžké to podpořit a pochopit.

Ve VictoriaMetrics je vše mnohem jednodušší. Tam je každá časová řada párem klíč–hodnota. Hodnota je sada bodů - (timestamp, value), a klíčem je sada label=value. Mezi poli a měřením není žádné oddělení. Umožňuje vám vybrat jakákoli data a poté je kombinovat, sčítat, odečítat, násobit, dělit, na rozdíl od InfluxDB, kde výpočty mezi různými řádky stále nejsou implementovány, pokud vím. I když jsou implementovány, je to obtížné, musíte napsat spoustu kódu.

Mám upřesňující otázku. Pochopil jsem správně, že došlo k nějakému problému, o kterém jste mluvil, že se tento invertovaný index nevejde do paměti, takže je tam rozdělení?

Nejprve jsem ukázal naivní implementaci invertovaného indexu na standardní Go mapě. Tato implementace není vhodná pro databáze, protože tento invertovaný index se neukládá na disk a databáze se musí uložit na disk, aby tato data zůstala dostupná i po restartu. V této implementaci, když restartujete aplikaci, váš invertovaný index zmizí. A ztratíte přístup ke všem datům, protože je nebudete moci najít.

Ahoj! Díky za zprávu! Jmenuji se Pavel. Jsem z Wildberries. Mám na vás pár otázek. Otázka jedna. Myslíte si, že kdybyste při budování architektury své aplikace zvolili jiný princip a rozdělili data v čase, pak by se vám možná podařilo protínat data při vyhledávání pouze na základě toho, že jeden oddíl obsahuje data pro jeden období , tedy v jednom časovém intervalu a nemuseli byste se bát, že jsou vaše dílky různě rozházené? Otázka číslo 2 - protože implementujete podobný algoritmus s bitsetem a vším ostatním, možná jste zkusili použít instrukce procesoru? Možná jste takové optimalizace vyzkoušeli?

Na tu druhou odpovím hned. Do toho jsme se ještě nedostali. Ale když to bude nutné, tak se tam dostaneme. A ta první, jaká byla otázka?

Mluvil jste o dvou scénářích. A řekli, že zvolili to druhé se složitější implementací. A nedali přednost tomu prvnímu, kde jsou data rozdělena podle času.

Ano. V prvním případě by byl celkový objem indexu větší, protože v každém oddílu bychom museli ukládat duplicitní data pro ty časové řady, které pokračují všemi těmito oddíly. A pokud je vaše časová řada churn rate malá, tj. jsou neustále používány stejné řady, pak v prvním případě bychom ve srovnání s druhým případem ztratili mnohem více místa na disku.

A tak – ano, časové rozdělení je dobrá volba. Používá to Prometheus. Prometheus má ale ještě jednu nevýhodu. Při slučování těchto částí dat je třeba zachovat v paměti metainformace pro všechny štítky a časové řady. Pokud jsou tedy části dat, které sloučí, velké, spotřeba paměti se během slučování na rozdíl od VictoriaMetrics velmi zvýší. Při slučování VictoriaMetrics vůbec nespotřebovává paměť, spotřebuje se pouze několik kilobajtů bez ohledu na velikost sloučených dat.

Algoritmus, který používáte, využívá paměť. Označuje tagy časové řady, které obsahují hodnoty. A tímto způsobem zkontrolujete spárovanou přítomnost v jednom datovém poli a v jiném. A pochopíte, zda došlo k průniku nebo ne. Databáze obvykle implementují kurzory a iterátory, které ukládají jejich aktuální obsah a procházejí setříděnými daty kvůli jednoduché složitosti těchto operací.

Proč nepoužíváme kurzory k procházení dat?

Ano.

Seřazené řádky ukládáme do LevelDB nebo mergeset. Můžeme pohybovat kurzorem a najít průsečík. Proč to nepoužíváme? Protože je to pomalé. Protože kurzory znamenají, že musíte volat funkci pro každý řádek. Volání funkce je 5 nanosekund. A pokud máte 100 000 000 řádků, pak se ukáže, že strávíme půl sekundy voláním funkce.

Něco takového existuje, ano. A moje poslední otázka. Otázka může znít trochu zvláštně. Proč není možné přečíst všechny potřebné agregáty v okamžiku příchodu dat a uložit je v požadované podobě? Proč ukládat obrovské objemy v některých systémech, jako je VictoriaMetrics, ClickHouse atd., a pak na nich trávit spoustu času?

Uvedu příklad, aby to bylo jasnější. Řekněme si, jak funguje malý rychloměr na hraní? Zaznamenává vzdálenost, kterou jste urazili, po celou dobu ji připočítává k jedné hodnotě a k druhé době. A rozděluje. A dosáhne průměrné rychlosti. Můžete udělat totéž. Sečtěte všechna potřebná fakta za chodu.

Dobře, rozumím otázce. Váš příklad má své místo. Pokud víte, jaké agregáty potřebujete, pak je to nejlepší implementace. Problém je ale v tom, že lidé si tyto metriky, některá data, uloží do ClickHouse a ještě nevědí, jak je budou v budoucnu agregovat a filtrovat, takže si musí uložit všechna nezpracovaná data. Ale pokud víte, že potřebujete něco vypočítat v průměru, tak proč to nespočítat místo toho, abyste tam uložili spoustu hrubých hodnot? Ale to je jen v případě, že přesně víte, co potřebujete.

Mimochodem, databáze pro ukládání časových řad podporují počítání agregátů. Podporuje například Prometheus pravidla nahrávání. To znamená, že to lze provést, pokud víte, jaké jednotky budete potřebovat. VictoriaMetrics to zatím nemá, ale většinou mu předchází Prometheus, ve kterém to lze udělat v pravidlech překódování.

Například v předchozí práci jsem potřeboval spočítat počet událostí v posuvném okně za poslední hodinu. Problém je v tom, že jsem musel udělat vlastní implementaci v Go, tedy službu pro počítání této věci. Tato služba byla nakonec netriviální, protože je obtížné ji vypočítat. Implementace může být jednoduchá, pokud potřebujete počítat nějaké agregáty v pevných časových intervalech. Pokud chcete počítat události v posuvném okně, pak to není tak jednoduché, jak se zdá. Myslím, že to ještě nebylo implementováno v ClickHouse nebo v databázích timeseries, protože je obtížné to implementovat.

A ještě jedna otázka. Zrovna jsme mluvili o průměrování a vzpomněl jsem si, že kdysi existovalo něco jako Graphite s karbonovým backendem. A uměl stará data prořídnout, tedy ponechat jeden bod za minutu, jeden bod za hodinu atd. V zásadě se to docela hodí, pokud potřebujeme nezpracovaná data, relativně vzato, na měsíc a všechno ostatní může být ztenčen . Prometheus a VictoriaMetrics však tuto funkci nepodporují. Plánuje se jeho podpora? Pokud ne, proč ne?

Děkuji za otázku. Naši uživatelé kladou tuto otázku pravidelně. Ptají se, kdy přidáme podporu pro downsampling. Problémů je zde několik. Za prvé, každý uživatel rozumí downsampling něco jiného: někdo chce získat libovolný bod na daném intervalu, někdo chce maximální, minimální, průměrné hodnoty. Pokud mnoho systémů zapisuje data do vaší databáze, nemůžete je dát dohromady. Je možné, že každý systém vyžaduje jiné ředění. A to se těžko realizuje.

A druhá věc je, že VictoriaMetrics, stejně jako ClickHouse, je optimalizována pro práci s velkým množstvím nezpracovaných dat, takže pokud máte v systému mnoho jader, dokáže hodit miliardu řádků za méně než sekundu. Skenování bodů časových řad ve VictoriaMetrics – 50 000 000 bodů za sekundu na jádro. A tento výkon se škáluje na stávající jádra. To znamená, že pokud máte například 20 jader, naskenujete miliardu bodů za sekundu. A tato vlastnost VictoriaMetrics a ClickHouse snižuje potřebu downsamlingu.

Další funkcí je, že VictoriaMetrics tato data efektivně komprimuje. Průměrná komprese ve výrobě je od 0,4 do 0,8 bajtů na bod. Každý bod je časové razítko + hodnota. A je komprimován v průměru do méně než jednoho bajtu.

Sergeji. Mám otázku. Jaká je minimální kvantová doba záznamu?

Jedna milisekunda. Nedávno jsme vedli rozhovor s dalšími vývojáři databází časových řad. Jejich minimální časový úsek je jedna sekunda. A například v grafitu je to také jedna sekunda. V OpenTSDB je to také jedna sekunda. InfluxDB má nanosekundovou přesnost. Ve VictoriaMetrics je to jedna milisekunda, protože v Prometheus je to jedna milisekunda. A VictoriaMetrics byl původně vyvinut jako vzdálené úložiště pro Prometheus. Nyní však může ukládat data z jiných systémů.

Osoba, se kterou jsem mluvil, říká, že má přesnost sekundy na sekundu – to jim stačí, protože to závisí na typu dat, která jsou uložena v databázi časových řad. Pokud se jedná o data DevOps nebo data z infrastruktury, kde je sbíráte v intervalech 30 sekund za minutu, pak stačí sekundová přesnost, nic méně nepotřebujete. A pokud tato data sbíráte z vysokofrekvenčních obchodních systémů, pak potřebujete nanosekundovou přesnost.

Milisekundová přesnost ve VictoriaMetrics je vhodná i pro případ DevOps a může být vhodná pro většinu případů, které jsem zmínil na začátku zprávy. Jediná věc, pro kterou nemusí být vhodná, jsou vysokofrekvenční obchodní systémy.

Děkuji! A další otázka. Co je kompatibilita v PromQL?

Plná zpětná kompatibilita. VictoriaMetrics plně podporuje PromQL. Navíc přidává další pokročilou funkcionalitu v PromQL, která se nazývá MetricsQL. Na YouTube se o této rozšířené funkcionalitě mluví. Mluvil jsem na Monitorovacím setkání na jaře v St. Petersburgu.

Telegramový kanál VictoriaMetrics.

Průzkumu se mohou zúčastnit pouze registrovaní uživatelé. Přihlásit se, prosím.

Co vám brání přejít na VictoriaMetrics jako své dlouhodobé úložiště pro Prometheus? (Napište do komentářů, přidám to do ankety))

• 71,4%Prometheus5 nepoužívám

• 28,6%Nevěděl jsem o VictoriaMetrics2

Hlasovalo 7 uživatelů. 12 uživatelů se zdrželo hlasování.

Zdroj: www.habr.com