🥇Оптимизация на Go в VictoriaMetrics. Александър Валялкин

Предлагам да се запознаете с разшифровката на доклада от края на 2019 година на Александър Валялкин "Оптимизации на Go в VictoriaMetrics"

VictoriaMetrics — бърза и мащабируема СУБД за съхранение и обработка на данни във форма на времеви ред (записът създава време и набор от съответните на това време стойности, например, получени чрез периодично опрашване на състоянието на сензорите или събиране на метрики).

Ето линк към видеото на този доклад — https://youtu.be/MZ5P21j_HLE

Слайдове

Ще ви разкажа малко за себе си. Аз съм Александър Валялкин. Ето мой GitHub акаунт. Аз съм запален по Go и оптимизация на производителността. Написал съм много полезни и не толкова полезни библиотеки. Те започват или с fast, или с quick префикс.

В момента работя върху VictoriaMetrics. Какво е това и какво правя там? За това ще разкажа в тази презентация.

Планът на доклада е следният:

Първо ще ви разкажа какво е VictoriaMetrics.
После ще разкажа какво са времевите редове.
После ще разкажа как работи базата данни за времеви редове.
Нататък ще разкажа за архитектурата на базата данни: от какво се състои.
И после ще преминем към оптимизациите, които има в VictoriaMetrics. Това е оптимизация на инвертирания индекс и оптимизация за bitset-реализация на Go.

Някой в аудиторията знае какво е VictoriaMetrics? О, много хора знаят. Това е добра новина. За тези, които не знаят – това е база данни за времеви редове. Тя е изградена на архитектурата на ClickHouse, със споменаване на някои детайли от реализацията на ClickHouse. Например, такива като: MergeTree, паралелно изчисление на всички налични ядра на процесора и оптимизация на производителността чрез работа с блокове данни, които се поставят в кеша на процесора.

VictoriaMetrics предлага най-доброто компресиране на данни в сравнение с други бази данни за времеви редове.

Тя мащабира вертикално — т.е. можете да добавяте повече процесори, повече оперативна памет на един компютър. VictoriaMetrics успешно ще използва тези налични ресурси и ще повиши линейната производителност.

Също така VictoriaMetrics мащабира хоризонтално — т.е. можете да добавяте допълнителни възли в кластера на VictoriaMetrics, и нейната производителност ще нараства почти линейно.

Както се досещате, VictoriaMetrics е бърза база данни, защото не мога да пиша за други. И тя е написана на Go, затова ви разказвам за нея на тази среща.

Кой знае какво е времеви ред? Много хора знаят. Времевият ред е поредица от двойки (маркер, стойност), където тези двойки са подредени по време. Стойността представлява число с плаваща запетая – float64.

Всеки времеви ред е уникално идентифициран с ключ. От какво се състои този ключ? Той се състои от непразен набор от двойки ключ-стойност.

Ето пример за времеви ред. Ключът на този ред е списък от двойки: __name__="cpu_usage" – това е името на метриката, instance="my-server" – това е компютърът, на който е събрана тази метрика, datacenter="us-east" – това е датацентърът, където се намира този компютър.

Получихме име на времеви ред, състоящо се от три двойки ключ-стойност. На този ключ отговаря списък от двойки (маркер, стойност). t1, t3, t3, ..., tN – това са времеви точки, 10, 20, 12, ..., 15 – съответстващите стойности. Това е cpu-usage в момента за този ред.

Къде могат да се използват времеви редове? Някой има ли идеи?

В DevOps можем да измерваме натоварването на CPU, RAM, мрежата, rps, брой грешки и т.н.
IoT – можем да измерваме температура, налягане, географски координати и още.
Също така в финансите – можем да следим цените на различни акции и валути.
Освен това, времевите редове могат да се използват за мониторинг на производствени процеси в заводи. Имаме потребители, които използват VictoriaMetrics за мониторинг на вятърни турбини, на роботи.
Също така времевите редове са полезни за събиране на информация от датчици на различни устройства. Например, за двигатели; за измерване на налягането в гумите; за измерване на скорост, разстояние; за измерване на разхода на бензин и т.н.
Също така времевите редове могат да се използват за мониторинг на самолети. Във всеки самолет има черна кутия, която събира времеви редове по различни параметри за здравето на самолета. Времевите редове се използват и в аерокосмическата индустрия.
Здравеопазване – това е кръвно налягане, пулс и т.н.

Може би има и други приложения, за които съм забравил, но се надявам, че разбрахте, че времевите редове се използват активно в съвременния свят. И обемът им на използване нараства с всяка година.

За какво е необходима база данни за времеви редове? Защо не можем да използваме обикновена релационна база за съхранение на времеви редове?

Защото при времевите редици обикновено има голямо количество информация, която е трудно да се съхранява и обработва в обикновени бази данни. Затова се появиха специализирани бази данни за времеви редици. Тези бази ефективно съхраняват точки (маркер, стойност) с определен ключ. Те предоставят API за четене на съхранените данни по ключ, по една двойка ключ-стойност, или по няколко такива двойки, или по regexp. Например, ако искате да намерите натоварването на процесора на всичките си услуги в дата центъра в Америка, трябва да използвате подобен псевдозапит.

Обикновено базите данни за времеви редици представят специализирани езици за запитвания, защото SQL за времеви редици не е много подходящ. Въпреки че има бази данни, които поддържат SQL, но той не е особено подходящ. По-добре подхождат такива езици за запитвания като PromQL, InfluxQL, Flux, Q. Надявам се, че някой е чувал поне един от тези езици. За PromQL вероятно много хора са чували. Това е езикът за запитвания на Prometheus.

Ето как изглежда архитектурата на съвременна база данни за времеви редици на примера на VictoriaMetrics.

Тя се състои от две части. Това е хранилище за инвертирован индекс и хранилище за стойности на времеви редици. Тези хранилища са разделени.

Когато в базата данни постъпи нов запис, първо се обърщаме към инвертирания индекс, за да намерим идентификатора на времевия ред в съответствие с зададен набор label=value за тази метрика. Намираме този идентификатор и запазваме стойността в хранилището за данни.

Когато постъпи запитване за извличане на данни от TSDB, ние първо проверяваме инвертирания индекс. Изваждаме всички timeseries_ids запазвания, които съответстват на зададения набор. label=valueИ след това извличаме всичките необходими данни от хранилището за данни, индексировано по timeseries_ids.

Нека разгледаме пример как базата данни за времеви редици обработва входящо select-запитване.

На първо място, тя извлича всички timeseries_ids от инвертирания индекс, които съдържат зададените двойки label=value, или удовлетворяват зададеното регулярното изразяване.
След това извлича всички точки от данни от хранилището за данни за зададения интервал от време за намерените timeseries_ids.
След това базата данни извършва някакви изчисления с тези точки от данни, в зависимост от запитването на потребителя. И след това връща отговор.

В настоящата презентация ще ви разкажа за първата част. Това е търсенето timeseries_ids по инвертирания индекс. За втората и третата част можете да погледнете по-късно изходните файлове на VictoriaMetrics, или изчакайте, докато подготвя други доклади 🙂

Да започнем с инвертирания индекс. На много хора може да им се стори, че това е просто. Кой знае какво е инвертиран индекс и как работи? О, не е много хората. Нека се опитаме да разберем какво е това.

Всъщност всичко е просто. Това е просто речник, който свързва ключ с значение. Какво е ключ? Тази двойка label=value, където label и value — това са низове. А стойностите - това е набор timeseries_ids, който включва зададената двойка label=value.

Инвертирания индекс позволява бързо намиране на всички timeseries_ids, които имат зададени label=value.

Също така позволява бързо намиране на timeseries_ids временни редици за няколко двойки label=value, или за двойки label=regexp. Как става това? Чрез намиране на пресечната точка на множеството timeseries_ids за всяка двойка label=value.

Нека разгледаме различни реализации на инвертирания индекс. Нека започнем с най-простата наивна реализация. Тя изглежда така.

Функция getMetricIDs получава списък с низове. Всеки низ съдържа label=value. Тази функция връща списък metricIDs.

Как работи това? Ето, че имаме глобална променлива, която се нарича invertedIndex. Това е обикновен речник (карта), който свързва низ с slice int-ове. Низът съдържа label=value.

Реализация на функция: извличаме metricIDs за първия label=value, след което минаваме през всички останали label=value, извличаме metricIDs за тях. И извикваме функцията intersectInts, за която ще се говори по-нататък. И тази функция връща пресечението на тези списъци.

Както виждате, реализацията на инвертирания индекс не е много сложна. Но това е наивна реализация. Какви недостатъци има? Главният недостатък на наивната реализация е, че такъв инвертиран индекс се съхранява в оперативната памет. След рестартиране на приложението губим този индекс. Няма запазване на този индекс на диск. За база данни такава инвертирана индекс едва ли е подходящ.

Вторият недостатък също е свързан с паметта. Инвертирания индекс трябва да се помести в оперативната памет. Ако надвиши размера на оперативната памет, очевидно ще получим – out of memory error. И програмата няма да работи.

Този проблем може да се реши с помощта на готови решения като LevelDB, или RocksDB.

Накратко, необходима ни е база данни, която позволява бързо извършване на три операции.

Първата операция – това е запис ключ-стойност в тази база. Тя го прави много бързо, където ключ-стойност – това са произволни редове.
Втората операция – това е бързо търсене на стойност по зададен ключ.
А третата операция – това е бързо търсене на всички стойности по зададен префикс.

LevelDB и RocksDB – тези бази са разработени в Google и Facebook. Първо се появи LevelDB. После момчетата от Facebook взеха LevelDB и започнаха да я подобряват, създавайки RocksDB. Сега на RocksDB вътре във Facebook работят почти всички вътрешни бази данни, включително те прехвърлиха MySQL на RocksDB. Те го нарекоха MyRocks.

Обратният индекс може да бъде реализиран с помощта на LevelDB. Как да го направим? Запазваме като ключ label=value. А като стойност – идентификатор на времеви ред, където присъства двойката label=value.

Ако имаме много временни редове с тази двойка label=value, ще има много редове в тази база данни с един и същ ключ и различни timeseries_ids. За да получим списък на всички timeseries_ids, които започват с даден label=prefix, правим обхождане на диапазон, за което е оптимизирана тази база данни. Тоест, избираме всички редове, които започват с label=prefix и получаваме необходимите timeseries_ids.

Ето примерна реализация как би изглеждала на Go. Имаме обратен индекс. Това е LevelDB.

Функцията е същата, каквато е за наивната реализация. Тя почти ред по ред повтаря наивната реализация. Единственият момент е, че вместо да се обръщаме към карта , се обръщаме към обратния индекс. Извличаме всички стойности за първата label=value. После преминаваме през всички останали двойки label=value и извличаме съответстващите набори metricIDs за тях. След това намираме пресечението.

Изглежда всичко е наред, но в това решение има недостатъци. VictoriaMetrics първоначално реализираше обратния индекс на база LevelDB. Но в крайна сметка се наложи да се откаже от него.

Защо? Защото LevelDB е по-бавен от наивната реализация. В наивната реализация по зададен ключ веднага извличаме целия slice metricIDs. Тази операция е много бърза – целият slice е готов за употреба.

При LevelDB обаче при всяко извикване на функцията GetValues трябва да преминем през всички редове, които започват с label=value. И за всеки ред да извлечем стойността timeseries_ids. От такива timeseries_ids събираме slice от тези timeseries_ids. Очевидно е, че това е много по-бавно от просто обръщение към обикновен map по ключ.

Вторият недостатък е, че LevelDB е написан на C. Обаждането към C-функции от Go не е много бързо. То отнема стотици наносекунди. Това не е много бързо, защото в сравнение с обикновеното извикване на функция, написана на Go, което отнема 1-5 наносекунди, разликата в производителността е десетки пъти. За VictoriaMetrics – това беше фатален недостатък 🙂

Затова написах собствена реализация на обратно индекс. И я нарекох mergeset.

Mergeset е основан на структурата от данни MergeTree. Тази структура от данни е взета от ClickHouse. Очевидно е, че mergeset трябва да бъде оптимизиран за бързо търсене timeseries_ids по зададен ключ. Mergeset е написан изцяло на Go. Можете да видите изходния код на VictoriaMetrics в GitHub. Реализацията на mergeset се намира в папката /lib/mergeset. Можете да се опитате да разберете какво се случва там.

API на mergeset е много подобен на LevelDB и RocksDB. Т.е. той позволява бързо да се запазят нови записи и бързо да се изберат записи по зададен префикс.

За недостатъците на mergeset ще говорим по-късно. Сега ще обсъдим какви проблеми възникнаха с VictoriaMetrics в production при реализацията на обратно индекс.

Защо те възникнаха?

Първата причина е високата честота на ротация. В превод на български – това е честа смяна на времеви редове. Това е, когато времевият ред завършва и започва нов ред, или започват много нови времеви редове. И това се случва често.

Втората причина е голямото количество времеви редове. В началото, когато мониторингът набираше популярност, количеството времеви редове беше малко. Например, за всеки компютър трябва да се следят натоварванията на процесора, паметта, мрежата и диска. 4 времеви реда за всеки компютър. Да кажем, имате 100 компютъра и 400 времеви реда. Това е много малко.

С течение на времето хората измислиха, че могат да измерват по-подробна информация. Например, да измерват натоварването не на целия процесор, а на отделните ядра на процесора. Ако имате 40 процесорни ядра, то съответно получавате 40 пъти повече времеви редове за измерване на натоварването на процесора.

Но това не е всичко. Всяко ядро на процесора може да има няколко състояния, като idle, когато е в режим на изчакване. А също така работа в user space, работа в kernel space и други състояния. И всяко от тези състояния също може да бъде измерено като отделен времеви ред. Това допълнително увеличава броя на редовете с 7-8 пъти.

От една метрика получаваме 40 х 8 = 320 метрики само за един компютър. Умножаваме по 100, получаваме 32 000 вместо 400.

След това се появи Kubernetes. И всичко се влоши, защото в Kubernetes могат да хостват много различни услуги. Всяка услуга в Kubernetes се състои от много подове. И всичко това трябва да бъде мониторирано. Освен това имаме постоянно внедряване на нови версии на вашите услуги. За всяка нова версия трябва да създадем нови времеви редове. В резултат на това броят на времевите редове нараства експоненциално и се сблъскваме с проблема с голямото количество времеви редове, известен като high-cardinality. VictoriaMetrics успешно се справя с него в сравнение с други бази данни за времеви редове.

Нека да разгледаме по-подробно high churn rate. Какво причинява high churn rate на продукция? Защото някои стойности на етикети и тагове постоянно се променят.

Например, вземаме Kubernetes, в който има понятието deployment, т.е. когато се внедрява нова версия на вашето приложение. Разработчиците на Kubernetes по някаква причина решиха да добавят id на deployment-а в етикета.

Какво доведе до това? До това, че при всяко ново внедряване всички стари времеви редове се прекратяват и вместо тях започват нови времеви редове с новата стойност на етикета deployment_id. Такива редове могат да бъдат стотици хиляди и дори милиони.

Важно е да се отбележи, че общият брой на времевите редове нараства, но броят на времевите редове, които в момента са активни и получават данни, остава постоянен. Това състояние се нарича high churn rate.

Основният проблем на high churn rate е да се осигури постоянна скорост на търсене на всички времеви редове по зададен набор от етикети за определен интервал от време. Обикновено това е интервал от време за последния час или последния ден.

Как да решим този проблем? Ето първият вариант. Да разделим инвертирания индекс на независими части по време. Тоест, след като изтече определен интервал от време, спираме работа с текущия инвертиран индекс и създаваме нов инвертиран индекс. Изминава още един интервал от време, създаваме още един и още един.

При извличането от тези инвертирани индекси намираме набор от инвертирани индекси, които попадат в зададения интервал. Следователно, избираме от тях id на времевите редове.

Това позволява да спестим ресурси, тъй като не е необходимо да преглеждаме части, които не попадат в зададения интервал. Тоест, обикновено, когато избираме данни за последния час, пропускаме заявките за предишни времеви интервали.

Има още един вариант за решаване на този проблем. Това е да съхраняваме за всеки ден отделен списък с id на времевите редове, които са се появили през този ден.

Предимството на това решение в сравнение с предишното е, че не дублираме информацията за времевите редове, които не изчезват с течение на времето. Те постоянно присъстват и не се променят.

Недостатъкът е, че такова решение е по-сложно за реализация и отстраняване на грешки. И VictoriaMetrics избра това решение. Исторически се е сложило така. Това решение също се проявява добре в сравнение с предишното, защото не е било реализирано поради необходимостта от дублиране на данните във всеки partition за времевите редове, които не се променят, т.е. които не изчезват с времето. VictoriaMetrics е била първоначално оптимизирана за консумация на дисково пространство и предишната реализация е влошавала консумацията на дисково пространство. А това изпълнение е по-подходящо за минимизиране на консумацията на дисково пространство, затова е било избрано.

Трябваше да се борим с това. Борбата се състоя в това, че в настоящата реализация все пак трябва да изберем много по-голямо количество timeseries_ids за данни, отколкото когато инвертирания индекс е разделен по време.

Как решихме този проблем? Решихме го оригинално - като запазихме няколко идентификатора на времеви редове в всяка записка на инвертирания индекс вместо един идентификатор. Тоест, имаме ключ label=value, който се среща във всяка времева линия. И сега запазваме няколко timeseries_ids в една запис.

Ето пример. Преди имахме N записа, а сега имаме един запис, чийто префикс е същият като на всички останали. Предишният запис съдържа всички id на времевите линии.

Това увеличи скоростта на сканиране на такъв инвертиран индекс до 10 пъти. И намали потреблението на памет за кеша, защото сега съхраняваме строката label=value само веднъж в кеша вместо N пъти. И тази строка може да бъде голяма, ако в етикетите и labels съхранявате дълги редове, които Kubernetes обича да вкарва там.

Още един вариант за ускоряване на търсенето в инвертирания индекс е шардироването. Създаване на няколко инвертирани индекса вместо един и шардирване на данните между тях по ключ. Това е набор ключ=стойност от двойки. Т.е. получаваме няколко независими инвертирани индекса, които можем да запитваме паралелно на няколко процесора. Предишните реализации позволяваха работа само в едноядрен режим, т.е. сканиране на данните само на едно ядро. Това решение позволява сканиране на данните веднага на няколко ядра, както ClickHouse обича да прави. Това планираме да реализираме.

А сега да се върнем на нашите овце – функцията на пресичане timeseries_ids. Нека разгледаме какви могат да бъдат реализациите. Тази функция позволява да се намира timeseries_ids за зададен набор label=value.

Първият вариант – е наивната реализация. Два вложени цикъла. Получаваме входни стойности на функцията intersectInts две slices — a и b. Като изход тя трябва да ни върне пресечението на тези slices.

Наивната реализация изглежда така. Преминаваме през всички стойности от slice a, вътре в този цикъл преминаваме през всички стойности на slice b. И ги сравняваме. Ако съвпадат, значи сме намерили пресечението. И го запазваме в резултат.

Какви са недостатъците? Квадратичната сложност — това е основният й недостатък. Например, ако размерите на slice a и b са по един милион, то тази функция никога няма да ви върне отговор. Защото ще й трябват един трилион итерации, което е много дори за съвременни компютри.

Втората реализация е базирана на map. Създаваме map. Помещаваме в тази map всички стойности от slice a. След това преминаваме с отделен цикъл по slice b. И проверяваме – има ли тази стойност от slice b в map. Ако тя съществува, добавяме я в резултата.

Какви са предимствата? Предимството е, че тук имаме само линейна сложност. Т.е. функцията ще се изпълни много по-бързо за големи размери на slices. За slice от милион елемента, тази функция ще се изпълни за 2 милиона итерации, в отличие от трилион итерации, както в предишната функция.

Недостатъкът е, че тази функция изисква повече памет за създаване на тази map.

Вторият недостатък – е значителен overhead за хеширане. Този недостатък не е много очевиден. И за нас той също не беше особено ясен, затова в началото реализацията на intersection в VictoriaMetrics беше чрез map. Но след това профилирането показа, че основното процесорно време се изразходва за запис в map и за проверка на наличието на стойност в тази map.

Защо в тези места се изразходва процесорно време? Защото в тези редове Go извършва операция по хеширане. Т.е. той изчислява hash от ключа, за да се обърне после по зададения индекс в HashMap. Операцията по изчисление на hash се изпълнява за десетки наносекунди. Това е бавно за VictoriaMetrics.

Реших да реализирам bitset, оптимизиран специално за този случай. Ето как изглежда сега пресичането на два slices. Тук създаваме bitset. Добавяме в него елементи от първия slice. След това проверяваме наличието на тези елементи във втория slice. И ги добавяме в резултата. Т.е. почти не се различава от предишния пример. Единственото, което заменихме, е достъпът до map с потребителски функции. add и has.

От първоначален поглед изглежда, че това трябва да работи по-бавно, ако преди е била използвана стандартна map, а сега се извикват още някакви функции, но профилирането показва, че тази структура работи 10 пъти по-бързо от стандартната map в случая с VictoriaMetrics.

Освен това, тя използва много по-малко памет в сравнение с реализацията на map. Защото тук съхраняваме битове вместо осембайтови стойности.

Недостатъкът на такава реализация е, че тя не е толкова очевидна и не е тривиална.

Още един недостатък, който много хора могат да не забележат – това е, че тази реализация може да работи лошо в определени случаи. Т. е. тя е оптимизирана за конкретен случай, за дадения случай на пресичане на идентификатори на времеви редове на VictoriaMetrics. Това не означава, че тя е подходяща за всички случаи. Ако бъде използвана неправилно, ще получим не увеличение на производителността, а грешка out of memory и забавяне на ефективността.

Нека разгледаме реализирането на тази структура. Ако искате да видите, тя се намира в източниците на VictoriaMetrics, в папката lib/uint64set. Тя е оптимизирана именно за случая на VictoriaMetrics, където timeseries_id представлява 64-битова стойност, където първите 32 бита са постоянни, а само последните 32 бита се променят.

Тази структура от данни не се съхранява на диска, тя работи само в паметта.

Ето нейния API. Не е особено сложен. API е съобразен именно с конкретния пример на използване на VictoriaMetrics. Т. е. тук няма излишни функции. Има функции, които са явно използвани от VictoriaMetrics.

Има функции add, която добавя нови стойности. Има функция has, която проверява новите стойности. И има функция del, която премахва стойности. Има помощна функция len, която връща размера на множеството. Функцията clone клонира множеството. И функция appendto преобразува това множество в slice. timeseries_ids.

Ето как изглежда реализирането на тази структура от данни. В set има два елемента:

ItemsCount – това е помощно поле, за да може бързо да се върне броят на елементите в set. Можеше да се мине и без това помощно поле, но трябваше да бъде добавено тук, защото VictoriaMetrics често проверява в алгоритмите си дължината на битовия набор.
Второто поле – това е бъкетс. Това е slice от структура bucket32.Във всяка структура се съхранява hi поле. Това са горните 32 бита. И два slice — b16his и бъкетс от bucket16 структури.

Тук се съхраняват горните 16 бита от втората част на 64-битовата структура. А тук се съхраняват битовите множества за младшите 16 бита на всеки байт.

Bucket64 се състои от масив uint64.Дължината се изчислява с помощта на тези константи. В един bucket16 максимум може да се съхранява 2^16=65536 бит. Ако се раздели на 8, това е 8 килобайта. Ако се раздели отново на 8, това е 1000 uint64. стойности. Т. е. Bucket16 – имаме 8-килобайтна структура.

Нека разгледаме как е реализиран един от методите на тази структура за добавяне на нова стойност.

Всичко започва с uint64. значения. Изчисляваме горните 32 бита, изчисляваме долните 32 бита. Преминаваме през всички бъкетс. Сравняваме горните 32 бита във всеки bucket с добавената стойност. И ако те съвпадат, извикваме функцията add в структурата b32 бъкетс. И добавяме там долните 32 бита. И ако това е върнало истинно, то това означава, че сме добавили такава стойност и не сме имали такава стойност преди. Ако тя връща неверно, то такава стойност вече е имало. След това увеличаваме броя на елементите в структурата.

Ако не сме намерили необходимия бакет с необходимото hi-значение, тогава извикваме функцията addAlloc, която заделя нов бакет, добавяйки го в структурата bucket.

Това е реализацията на функцията b32.add. Тя е подобна на предишната реализация. Изчисляваме старшите 16 бита, младшите 16 бита.

След това преминаваме през всички горни 16 бита. Намираме съвпадения. И при съвпадение извикваме метода add, който ще разгледаме на следващата страница за bucket16.

И ето най-ниското ниво, което трябва да бъде максимално оптимизирано. Изчисляваме за uint64. id стойността в slice bit, както и bitmask. Това е маска за тази 64-битова стойност, чрез която можем да проверим наличието на този бит или да го установим. Проверяваме наличието на този бит, задаваме го и връщаме наличието. Ето такава реализация имаме, която позволи да ускорим операцията на пресичане на ids времеви редици 10 пъти в сравнение с обикновените maps.

В VictoriaMetrics, освен тази оптимизация, има много други оптимизации. Повечето от тези оптимизации не са добавени просто така, а след профилиране на кода в продукция.

Това е основното правило за оптимизация – не добавяйте оптимизация, предполагайки, че тук ще бъде тясно място, защото може да се окаже, че там не ще има тясно място. Оптимизацията обикновено влошава качеството на кода. Поради това е необходимо да се оптимизира само след профилиране и за предпочитане в продукция, за да са реални данните. Който има интерес, може да разгледа източниците на VictoriaMetrics и да изучи другите оптимизации, които има там.

Имам въпрос относно bitset. Много прилича на реализацията на C++ vector bool, оптимизиран bitset. Взели ли сте реализацията от там?

Не, не оттам. При реализация на този bitset се ръководих от знанията за структурата на тези ids времеви серии, които се използват в VictoriaMetrics. Структурата им е такава, че горните 32 бита по принцип са постоянни. Долни 32 бита могат да се променят. Колкото по-нисък е битът, толкова по-често може да се променя. Затова тази реализация е специфично оптимизирана за тази структура от данни. C++ реализацията, колкото знам, е оптимизирана за общия случай. Ако направите оптимизация за общия случай, това означава, че тя няма да бъде най-оптималната за конкретния случай.

Препоръчвам ви да се запознаете с доклада на Алексей Миловид. Той преди около месец разказа за оптимизации в ClickHouse за конкретни специализации. Той точно казва, че в общия случай C++ реализацията или някоя друга реализация са насочени към добро представяне в средния случай. Тя може да работи по-зле от специализирана реализация за конкретни знания, както е при нас, когато знаем, че горните 32 бита по принцип са постоянни.

Имам втори въпрос. Каква е основната разлика от InfluxDB?

Основната разлика е много. По производителност и потребление на памет, InfluxDB в тестовете показва 10 пъти по-високо потребление на памет за high cardinality времеви редове, когато имате много, например, милиони. Например, VictoriaMetrics консумира 1 GB на милион активни реда, а InfluxDB тогава консумира 10 GB. И това е голяма разлика.

Втората основна разлика е, че в InfluxDB имаме странни езици за запитвания – Flux и InfluxQL. Те не са особено удобни за работа с времеви редове в сравнение с PromQL, който се поддържа в VictoriaMetrics. PromQL – това е езикът за запитвания от Prometheus.

И още едно отличие – InfluxDB има малко странна модел на данни, където в всяка линия могат да се съхраняват няколко fields с различен набор от тагове. Тези редове се разделят на различни таблици. Тези допълнителни усложнения усложняват последващата работа с тази база. Тя е трудна за поддръжка и разбиране.

В VictoriaMetrics всичко е много по-просто. Всеки времеви ред представлява ключ-стойност. Стойността – това е набор от точки – (маркер, стойност), а ключът – това е набор label=valueНяма разделение на fields и measurements. Това ви позволява да избирате всякакви данни и след това да ги комбинирате, сглобявате, изчитате, умножавате и делите, за разлика от InfluxDB, където изчисленията между различни редове досега не са реализирани, доколкото знам. Дори и да са реализирани, е сложно, трябва да пишете много код.

Имам уточняващ въпрос. Правилно ли разбрах, че имаше някакъв проблем, за който разказвахте, че този инвертиран индекс не се побира в паметта и затова там се прави партициониране?

Първоначално показах наивна реализация на инвертирания индекс на стандартната Go map. Тази реализация не е подходяща за бази данни, тъй като този инвертиран индекс не се запазва на диска, а базата данни трябва да запазва на диск, за да са налични данните след рестартиране. При тази реализация, след рестартиране на приложението, инвертираният индекс ще изчезне. И ще загубите достъп до всички данни, защото няма да можете да ги намерите.

Здравейте! Благодаря за доклада! Казвам се Павел. Аз съм от компания Wildberries. Имам няколко въпроса към вас. Първият въпрос. Как ви се струва, ако бяхте избрали различен принцип при изграждането на архитектурата на приложението си и партиционирали данните по време, бихте ли могли да правите пресичане на данни при търсене, основавайки се само на факта, че в една партиция се намират данни за един период от време, т.е. за един времеви интервал, и нямаше да се налага да се тревожите за това, че имате части, разпръснати по различен начин? Въпрос номер 2 - тъй като реализирате подобен алгоритъм с bitset и всичко останало, може би сте опитвали да използвате инструкции на процесора? Може би сте се опитвали с такива оптимизации?

На втория момент ще отговоря веднага. Още не сме стигнали до там. Но ако е необходимо, ще стигнем. А първият, какъв беше въпросът?

Обсъждахте два сценария. И казахте, че избрахте втория с по-сложна имплементация. И не предпочетохте първия, в който данните са партиционирани по време.

Да. В първия случай общият обем на индекса би бил по-голям, защото в всяка партиция трябва да съхраняваме дублирани данни за тези времеви редове, които преминават през всички тези партиции. И ако имате нисък churn rate на времевите редове, т.е. постоянно се използват одни и същи редове, в първия случай значително ще загубим по отношение на заетото дисково пространство в сравнение с втория случай.

Но така – да, партиционирането по време е добър вариант. Този метод се използва от Prometheus. Но Prometheus има друг недостатък. При сливането на тези фрагменти от данни, той трябва да поддържа в паметта мета-информация за всички label и timeseries. Следователно, ако фрагментите от данни, които той слива, са големи, употребата на памет се увеличава значително при сливането, за разлика от VictoriaMetrics. При сливането VictoriaMetrics изобщо не консумира памет, там се използват няколко килобайта, независимо от размерите на обединените фрагменти от данни.

Алгоритъмът, който използвате, консумира памет. В нея се обозначават timeseries-етикети, за които има стойности. И по този начин проверявате за наличието на двойки в един масив данни и в друг. И разбирате – настъпил е intersect или не. Обикновено в базите данни се реализират курсори, итератори, които съхраняват текущото си състояние и преминават по сортирани данни, което ви дава проста сложност на данните операции.

Защо не използваме курсори за пресичане на данни?

Да.

В LevelDB или в mergeset имаме точно така подредени редове. Можем да използваме курсор, за да намерим пресечението. А защо не го правим? Защото – е бавно. Защото курсорите предполагат, че за всеки ред трябва да се извика функция. Извикването на функция – е 5 наносекунди. И ако имате 100 000 000 реда, излиза, че само за извикването на функция харчим половин секунда.

Такова нещо съществува, да. И последният ми въпрос. Въпросът, може би, звучи малко странно. Защо при постъпването на данни не може да се изчислят всички необходими агрегати и да се запазят в необходимия формат? Защо да се съхраняват огромни обеми в системи като VictoriaMetrics, ClickHouse и т.н., за да се губи много време за тях по-късно?

Дам пример за по-добро разбиране. Да предположим, как работи малък играчки спидометър? Той записва разстоянието, което сте изминали, добавяйки го постоянно в едно количество и времето в друго. И го дели. И получава средната скорост. Може да се направи нещо подобно. Да се събират на лето всички необходими факти.

Добре, разбрах въпроса. Вашият пример е валиден. Ако знаете какви агрегати ви трябват, това е най-доброто решение. Но проблемът е, че хората запазват тези метрики, някакви данни в ClickHouse и не знаят как ще ги агрегатират или филтрират в бъдеще, така че трябва да запазват всички сурови данни. Но ако знаете, че трябва да изчислите нещо средно, защо просто не го изчислите, вместо да запазите куп сурови стойности там? Но това важи само ако точно знаете какво ви е нужно.

Между другото, базите за съхранение на времеви редове поддържат изчисление на агрегати. Например, Prometheus поддържа правила за записване. Тоест, това може да бъде направено, ако знаете какви агрегати ще ви трябват. В VictoriaMetrics това все още не е налично, но обикновено преди нея се поставя Prometheus, в който може да се направи в правилата за записване.

Например, на предишната ми работа трябваше да изчислявам броя на събитията в подвижен прозорец за последния час. Проблемът беше, че трябваше да направя кастомна реализация на Go, тоест услуга за изчисляване на това нещо. Тази услуга всъщност беше сложна, защото е трудно да се изчисли. Реализацията може да бъде проста, ако трябва да изчислявате агрегати на фиксирани времеви интервали. Но ако искате да изчислявате събития в подвижен прозорец, това не е толкова просто, колкото изглежда. Мисля, че все още не е реализирано в ClickHouse или в базите за времеви редове, защото е сложно за реализиране.

И още един въпрос. В момента говорихме за усредняване и си спомних, че преди имаше нещо като Graphite с бекенд Carbon. Той можеше да редуцира старите данни, т.е. да оставя една точка на минута, една точка на час и т.н. Всъщност, това е доста удобно, ако ни трябват сурови данни, условно казано, за месец, а всичко останало може да се редуцира. Но Prometheus и VictoriaMetrics не поддържат тази функционалност. Планира ли се да я поддържат? Ако не, защо?

Благодаря за въпроса. Нашите потребители го задават периодично. Питат, кога ще добавим поддръжка за downsampling. Има няколко проблема. Първо, всеки потребител разбира под downsampling нещо свое: някой иска да получи произволна точка в зададен интервал, друг иска максимални, минимални и средни стойности. Ако данни в базата ви се записват от много системи, не може да ги съберете под един чадър. Може да се окаже, че за всяка система е необходимо да се използва различно downsampling. И това е сложно за изпълнение.

Второ, VictoriaMetrics, също като ClickHouse, е оптимизирана за работа с големи обеми сурови данни, затова може да преработи един милиард реда за по-малко от секунда, ако имате много ядра в системата си. Сканирането на точки от времеви ред в VictoriaMetrics е 50 000 000 точки в секунда на едно ядро. И тази производителност се мащабира спрямо наличните ядра. Т.е. ако имате 20 ядра, например, ще получите сканиране на един милиард точки в секунда. И това свойство на VictoriaMetrics и ClickHouse намалява нуждата от downsampling.

Още едно свойство е, че VictoriaMetrics ефективно компресира тези данни. Компресията средно на продукция е от 0,4 до 0,8 байта на точка. Всяка точка е timestamp + стойност. И се компресира на по-малко от един байт средно.

Сергей. Имам въпрос. Каква е минималната стъпка на времето за запис?

Една милесекунда. Наскоро имахме разговор с други разработчици на бази данни за времеви редове. При тях минималната стъпка на времето е една секунда. В Graphite, например, също е една секунда. В OpenTSDB също е една секунда. В InfluxDB – нано-секундна точност. В VictoriaMetrics – една милесекунда, защото в Prometheus е една милесекунда. И VictoriaMetrics е разработена първоначално като remote storage за Prometheus. Но сега може да съхранява данни и от други системи.

Човекът, с когото разговарях, казва, че имат секундна точност – това им е достатъчно, защото зависи от типа данни, които се съхраняват в базата от времеви редове. Ако това са DevOps данни или данни от инфраструктура, където ги събирате с интервал от 30 секунди до минута, тогава секундната точност е достатъчна, по-малка не е необходима. А ако събирате тези данни от системи за висока честота на търговия, тогава е необходима нано-секундна точност.

Милисекундната точност на VictoriaMetrics е подходяща както за DevOps случаи, така и за повечето случаи, които споменах в началото на доклада. Единственото, за което може да не е подходяща, е high frequency trading системите.

Благодаря! И още един въпрос. Каква е съвместимостта с PromQL?

Пълна обратна съвместимост. VictoriaMetrics напълно поддържа PromQL. Освен това, тя добавя и допълнителни разширени функции към PromQL, която се нарича MetricsQL. За тази разширена функционалност има доклад в YouTube. Разказвах на Monitoring Meetup през пролетта в Санкт Петербург.

Telegram канал VictoriaMetrics.

Само регистрирани потребители могат да участват в анкетата. Влезте, моля.