Прапаную азнаёміцца з расшыфроўкай даклада канца 2019 года Аляксандра Валялкіна "Go optimizations in VictoriaMetrics"
- хуткая і якая маштабуецца СКБД для захоўвання і апрацоўкі дадзеных у форме часавага шэрагу (запіс утворыць час і набор адпаведных гэтаму часу значэнняў, напрыклад, атрыманых праз перыядычнае апытанне стану датчыкаў або збор метрык).
Вось спасылка на відэа гэтага дакладу.
Раскажу крыху пра сябе. Я - Аляксандр Валялкін. Вось . Я захапляюся Go і аптымізацыяй прадукцыйнасці. Напісаў шмат усялякіх карысных і не вельмі бібліятэк. Яны пачынаюцца альбо з fast, альбо з quick прэфікса.
У дадзены момант я працую над VictoriaMetrics. Што гэта такое і што я там раблю? Пра гэта я раскажу ў гэтай прэзентацыі.
План даклада такі:
- Спачатку я вам раскажу, што такое VictoriaMetrics.
- Потым раскажу, што такое часовыя рады.
- Потым раскажу, як працуе база дадзеных часовых шэрагаў.
- Далей раскажу пра архітэктуру базы даных: з чаго яна складаецца.
- І потым пяройдзем да аптымізацыям, якія ёсць у VictoriaMetrics. Гэта аптымізацыя інвертаванага азначніка і аптымізацыя для bitset-рэалізацыі на Go.
Што такое VictoriaMetrics хто-небудзь у аўдыторыі ведае? Нічога сабе, ужо шмат людзей ведаюць. Гэта добрая навіна. Для тых, хто не ведае - гэта база дадзеных для часовых шэрагаў. Яна заснавана на архітэктуры ClickHouse, на некаторых дэталях рэалізацыі ClickHouse. Напрыклад, на такіх, як: MergeTree, раўналежнае вылічэнне на ўсіх даступных ядрах працэсара і аптымізацыя прадукцыйнасці з дапамогай працы над блокамі дадзеных, якія змяшчаюцца ў кэш працэсара.
VictoriaMetrics дае лепшы сціск дадзеных у параўнанні з іншымі базамі дадзеных для часовых шэрагаў.
Яна маштабуецца вертыкальна – т. е. вы можаце дадаваць большую колькасць працэсараў, большую колькасць аператыўнай памяці на адным кампе. VictoriaMetrics будзе паспяхова ўтылізаваць гэтыя даступныя рэсурсы і будзе падвышаць лінейную прадукцыйнасць.
Таксама VictoriaMetrics маштабуецца гарызантальна - т. е. вы можаце дадаваць дадатковыя ноды ў кластар VictoriaMetrics, і яе прадукцыйнасць будзе расці амаль лінейна.
Як вы здагадаліся, VictoriaMetrics хуткая база даных, таму што іншых я не магу пісаць. І яна напісана на Go, таму я пра яе расказваю на гэтым мітапе.
Хто ведае, што такое часовы рад? Таксама шмат людзей ведае. Часова шэраг - гэта серыя пар (timestamp, значение), дзе гэтыя пары адсартаваны па часе. Значэнне ўяўляе сабой лік з якая плавае кропкай - float64.
Кожны часавы шэраг унікальна ідэнтыфікаваны ключом. З чаго складаецца гэты ключ? Ён складаецца з непустога набору пар ключ-значэння.
Вось прыклад часовага шэрагу. Ключом гэтага шэрагу з'яўляецца спіс пар: __name__="cpu_usage" – гэта назва метрыкі, instance="my-server" - Гэта кампутар, на якім гэтая метрыка сабрана, datacenter="us-east" - Гэта датацэнтр, дзе стаіць гэты кампутар.
У нас атрымалася імя часавага шэрагу, якое складаецца з трох пар ключ-значэнні. Гэтаму ключу адпавядае спіс пар (timestamp, value). t1, t3, t3, ..., tN - Гэта timestamps, 10, 20, 12, ..., 15 - Адпаведныя значэння. Гэта cpu-usage у дадзены момант часу для дадзенага шэрагу.
Дзе могуць быць скарыстаны часовыя шэрагі? У каго-небудзь ёсць ідэі?
- У DevOps можна вымяраць паказанні загрузкі CPU, RAM, сеткі, rps, колькасць памылак і т. д.
- IoT - можам мераць тэмпературу ціск, geo coordinates і яшчэ што-небудзь.
- Таксама фінансы - можам маніторыць цэны на ўсякія акцыі і валюты.
- Акрамя гэтага, часовыя рады могуць выкарыстоўвацца ў маніторынгу вытворчых працэсаў на заводах. У нас ёсць карыстальнікі, якія выкарыстоўваюць VictoriaMetrics для маніторынгу ветравых турбін, для робатаў.
- Таксама часовыя шэрагі карысныя для збору інфармацыі з датчыкаў розных прылад. Напрыклад, для рухавіка; для вымярэння ціску ў шынах; для вымярэння хуткасці, адлегласці; для вымярэння выдатку бензіну і т. д.
- Таксама часовыя рады могуць выкарыстоўвацца для маніторынгу самалётаў. У кожным самалёце ёсць чорная скрыня, якая збірае часовыя шэрагі па розных параметрах здароўя самалёта. Часовыя шэрагі таксама выкарыстоўваюцца ў аэракасмічнай прамысловасці.
- Healthcare - гэта ціск крыві, пульс і г.д.
Можа быць, яшчэ ёсць ужыванні, пра якія я забыўся, але, спадзяюся, што вы зразумелі, што часавыя шэрагі актыўна выкарыстоўваюцца ў сучасным міры. І аб'ём іх выкарыстання з кожным годам расце.
Навошта патрэбна база дадзеных для часовых шэрагаў? Чаму нельга выкарыстоўваць звычайную рэляцыйную базу для захоўвання часавых шэрагаў?
Таму што ў часавых шэрагах звычайна вялікі аб'ём інфармацыі, які складана захоўваць і апрацоўваць у звычайных базах даных. Таму з'явіліся спецыялізаваныя БД для часавых радоў. Гэтыя базы эфектыўна захоўваюць кропкі (timestamp, value) з зададзеным ключом. Яны падаюць API для чытання захаваных дадзеных па ключы, па адной пары ключ-значэнне, альбо па некалькіх такім парам, альбо па regexp. Напрыклад, вы хочаце знайсці загрузку працэсара ўсіх вашых сэрвісаў у датацэнтры ў Амерыцы, то трэба выкарыстоўваць вось такі псеўдазапыт.
Звычайна базы дадзеных для часовых шэрагаў уяўляюць спецыялізаваныя мовы запытаў, таму што SQL для часовых шэрагаў не вельмі добра падыходзіць. Хаця ёсць базы дадзеных, якія SQL падтрымліваюць, але ён не вельмі добра падыходзіць. Больш добра падыходзяць такія мовы запытаў, як , , , . Я спадзяюся, што нехта чуў хаця б адной з гэтых моў. Аб PromQL, напэўна, чулі многія. Гэта мова запытаў Prometheus.
Вось як выглядае архітэктура сучаснай базы дадзеных для часавых шэрагаў на прыкладзе VictoriaMetrics.
Яна складаецца з дзвюх частак. Гэта сховішча для інвертаванага азначніка і сховішча для значэнняў часавых шэрагаў. Гэтыя сховішчы падзелены.
Калі прыходзіць новы запіс у базу дадзеных, то мы спачатку звяртаемся ў інвертаваны азначнік, каб знайсці ідэнтыфікатар часавага шэрагу па зададзеным наборы. label=value для дадзенай метрыкі. Знаходзім гэты ідэнтыфікатар і захоўваем значэнне ў сховішчы дадзеных.
Калі прыходзіць нейкі запыт на выбарку дадзеных з TSDB, мы ў першую чаргу лезем у інвертаваны азначнік. Дастаем усё timeseries_ids запісы, якія адпавядаюць гэтаму набору label=value. І затым дастаем усе неабходныя дадзеныя са сховішча дадзеных, індэксаванага па timeseries_ids.
Разгледзім прыклад, як база дадзеных для часавых шэрагаў апрацоўвае ўваходны select-запыт.
- У першую чаргу яна дастае ўсё
timeseries_idsз інвертаванага індэкса, якія змяшчаюць зададзеныя парыlabel=value, альбо задавальняюць зададзенаму рэгулярнаму выразу. - Потым яна дастае ўсе data points са сховішча дадзеных на зададзеным інтэрвале часу для знойдзеных
timeseries_ids. - Пасля гэтага база дадзеных вырабляе нейкія вылічэнні над гэтымі data points, паводле запыту карыстальніка. І пасьля гэтага вяртае адказ.
У дадзенай прэзентацыі я вам раскажу пра першую частку. Гэта пошук timeseries_ids па інвертаваным індэксе. Пра другую частку і трэцюю частку вы можаце потым паглядзець , альбо пачакаць, пакуль я падрыхтую іншыя даклады 🙂
Прыступім да інвертаванага азначніка. Многім можа здацца, што гэта проста. Хто ведае, што такое інвертаваны азначнік і як ён працуе? О, ужо не так шмат людзей. Давайце паспрабуем зразумець, што гэта такое.
Насамрэч усё проста. Гэта проста слоўнік, які адлюстроўвае ключ да значэння. Што такое ключ? Гэтая пара 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. Гэта звычайны слоўнік (map), які адлюстроўвае радок на slice int-ов. Радок змяшчае label=value.
Рэалізацыя функцыі: дастаем metricIDs для першага label=value, затым праходзімся па ўсіх астатніх label=value, дастаем metricIDs для іх. І выклікаем функцыю intersectInts, пра якую будзе расказана далей. І гэтая функцыя вяртае скрыжаванне гэтых спісаў.
Як вы бачыце, рэалізацыя інвертаванага азначніка не вельмі складаная. Але гэта наіўная рэалізацыя. Якія ў яе ёсць недахопы? Галоўны недахоп наіўнай рэалізацыі ў тым, што такі інвертаваны індэкс у нас захоўваецца ў аператыўнай памяці. Пасля перазапуску прыкладання мы губляем гэты індэкс. Няма захавання гэтага азначніка на дыск. Для базы дадзеных такі інвертаваны індэкс ці наўрад падыдзе.
Другі недахоп таксама злучаны з памяццю. Інвертаваны індэкс павінен змяшчацца ў аператыўную памяць. Калі ён перавысіць памер аператыўнай памяці, то відавочна, што мы атрымаем - out of memory error. І праграма не будзе працаваць.
Дадзеную праблему можна вырашыць з дапамогай гатовых рашэнняў такіх, як , Альбо .
Калі сцісла, то нам патрэбна база дадзеных, якая дазваляе зрабіць хутка тры аперацыі.
- Першая аперацыя - гэта запіс
ключ-значениеу гэтую базу. Гэта яна робіць вельмі хутка, дзеключ-значение- гэта адвольныя радкі. - Другая аперацыя - гэта хуткі пошук значэння па зададзеным ключы.
- І трэцяя аперацыя - гэта хуткі пошук усіх значэнняў па зададзеным прэфіксе.
LevelDB і RocksDB - гэтыя базы распрацаваны ў Google і Facebook. Спачатку з'явілася LevelDB. Пасля хлопцы з Facebook узялі LevelDB і пачалі яе паляпшаць, зрабіў RocksDB. Цяпер на RocksDB усярэдзіне Facebook працуюць амаль усе ўнутраныя базы дадзеных, у тым ліку яны перавялі на RocksDB і MySQL. Яны назвалі яго .
Інвертаваны індэкс можна рэалізаваць з дапамогай LevelDB. Як гэта зрабіць? Мы захоўваем у якасці ключа label=value. А ў якасці значэння - ідэнтыфікатар часовага шэрагу, дзе прысутнічае пара label=value.
Калі ў нас ёсць шмат часовых шэрагаў з дадзенай парай label=value, то будзе шмат радкоў у гэтай базе дадзеных з аднолькавымі ключом і рознымі timeseries_ids. Каб атрымаць спіс усіх timeseries_ids, якія пачынаюцца з дадзенай label=prefix, мы робім range scan, пад які аптымізавана дадзеная база дадзеных. Т. е. выбіраемы ўсе радкі, якія пачынаюцца з label=prefix і атрымліваем неабходныя timeseries_ids.
Вось прыкладная рэалізацыя, як яна выглядала б на Go. У нас ёсць інвертаваны індэкс. Гэта LevelDB.
Функцыя такая ж, як для наіўнай рэалізацыі. Яна амаль радок у радок паўтарае наіўную рэалізацыю. Адзіны момант, што замест звароту да map мы звяртаемся да інвертаванага азначніка. Дастаем усе значэння для першай 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 заснаваны на структуры даных MergeTree. Гэтая структура дадзеных запазычаная з ClickHouse. Відавочна, што mergeset павінен быць аптымізаваны для хуткага пошуку timeseries_ids па зададзеным ключы. Mergeset напісаны поўнасцю на Go. Вы можаце паглядзець . Рэалізацыя mergeset ляжыць у татачку . Вы можаце паспрабаваць разабрацца, што тамака адбываецца.
API mergeset вельмі падобны да LevelDB і RocksDB. Т. е. ён дазваляе хутка захаваць туды новыя запісы і хутка абраць запісы па зададзеным прэфіксе.
Пра недахопы mergeset мы пагаворым пазней. Цяпер пагаворым аб тым, якія ўзніклі праблемы з VictoriaMetrics у production пры рэалізацыі інвертаванага індэкса.
Чаму яны ўзніклі?
Першая прычына - гэта high churn rate. У перакладзе на рускую – гэта частая змена часовых шэрагаў. Гэта калі часавы шэраг заканчваецца і пачынаецца новы шэраг, альбо пачынаюцца шмат новых часовых шэрагаў. І гэта адбываецца часта.
Другая прычына - гэта вялікая колькасць часовых шэрагаў. Спачатку, калі маніторынг набіраў папулярнасць, колькасць часавых шэрагаў была маленькай. Напрыклад, на кожны кампутар трэба маніторыць загрузку працэсара, памяці, сеткі і дыска. 4 часовых шэрагу на кожны кампутар. У вас, дапусцім, 100 кампутараў і 400 часавых шэрагаў. Гэта мала.
З цягам часу людзі прыдумалі, што можна вымяраць больш дэталізаваную інфармацыю. Напрыклад, вымяраць загрузку не ўсяго працэсара, а ў асобнасці кожнага працэсарнага ядра. Калі ў вас ёсць 40 працэсарных ядраў, то, адпаведна, у вас з'яўляецца ў 40 разоў больш часавых шэрагаў для вымярэння загрузкі працэсара.
Але гэта яшчэ ня ўсё. У кожнага працэсарнага ядра можа быць некалькі станаў такіх, як idle, калі ен прастойвае. А таксама праца ў user space, праца ў kernel space і іншыя станы. І кожны такі стан таксама можна вымяраць, як асобны часавы шэраг. Гэта дадаткова павялічвае колькасць шэрагаў у 7-8 разоў.
У нас з адной метрыкі атрымалася 40х8 = 320 метрык толькі на адзін кампутар. Памнажаем на 100, атрымліваем 32 000 замест 400.
Пасля з'явіўся Kubernetes. І ўсё яшчэ пагоршыў, таму што ў Kubernetes можа размяшчацца шмат розных сэрвісаў. Кожны сэрвіс у Kubernetes складаецца з шматлікіх подаў. І ўсё гэта трэба маніторыць. Акрамя гэтага, у нас ёсць пастаянны deployment новых версій вашых сэрвісаў. Для кожнай новай версіі трэба ствараць новыя часовыя рады. У выніку колькасць часавых шэрагаў расце экспанентна і мы сутыкаемся з праблемай вялікай колькасці часовых шэрагаў, якая называецца high-cardinality. VictoriaMetrics з ёй паспяхова спраўляецца ў параўнанні з іншымі базамі даных для часовых шэрагаў.
Разгледзім падрабязней high churn rate. Чаму з'яўляецца high churn rate на production? Таму што некаторыя значэнні лэйблаў і тэгаў увесь час змяняюцца.
Напрыклад, возьмем Kubernetes, у якім ёсць паняцце deployment, т. е. калі выкочваецца новая версія вашага прыкладання. Распрацоўнікі Kubernetes чамусьці вырашылі дадаць id'шку deployment'а ў label.
Да чаго гэта прывяло? Да таго, што пры кожным новым 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.
Яшчэ адзін варыянт паскарэння пошуку па інвертаваным азначніку – гэта шардирование. Стварэнне некалькіх інвертаваных індэксаў замест аднаго і шакіраванне дадзеных паміж імі па ключы. Гэта набор key=value пар. Т. е. у нас атрымліваецца некалькі незалежных інвертаваных індэксаў, якія мы можам апытваць паралельна на некалькіх працэсарах. Папярэднія рэалізацыі дазвалялі працаваць толькі ў аднапрацэсарным рэжыме, т. е. сканаваць дадзеныя толькі на адным ядры. Дадзенае рашэнне дазваляе сканаваць дадзеныя адразу на некалькіх ядрах, як гэта любіць рабіць ClickHouse. Гэта мы плянуем рэалізаваць.
А зараз вернемся да нашых бараноў - да функцыі скрыжавання timeseries_ids. Разгледзім, якія могуць быць рэалізацыі. Гэтая функцыя дазваляе знаходзіць timeseries_ids для зададзенага набору label=value.
Першы варыянт - гэта наіўная рэалізацыя. Два ўкладзеныя цыклы. Вось мы атрымліваем на ўваходзе функцыі intersectInts два slices a и b. На выхадзе яна павінна вярнуць нам скрыжаванне гэтых slices.
Наіўная рэалізацыя выглядае так. Мы праходзімся па ўсіх значэннях з slice a, усярэдзіне гэтага цыклу праходзімся па ўсіх значэннях slice b. І параўноўваем іх. Калі яны супадаюць, значыць, мы знайшлі скрыжаванне. І захоўваем яго ў result.
Якія ёсць недахопы? Квадратычная складанасць - гэта галоўны яе недахоп. Напрыклад, калі ў вас памеры slice a и b па адным мільёне, то гэтая функцыя ніколі вам не верне адказ. Бо ёй трэба будзе зрабіць адзін трыльён ітэрацый, што вельмі шмат нават для сучасных камп'ютараў.
Другая рэалізацыя заснавана на map. Мы ствараем map. Змяшчаем у гэтую map усе значэння з slice a. Затым прабягаемся асобным цыклам па slice. b. І правяраем - ці ёсць гэта значэнне з slice b у map. Калі яно ёсць, то дадаем яго ў вынік.
Якія перавагі? Перавага ў тым, што тут толькі лінейная складанасць. Т. е. функцыя нашмат хутчэй выканаецца для вялікіх памераў slices. Для мільённага памеру slice гэтая функцыя выканаецца за 2 мільёны ітэрацый, у адрозненні ад трыльёна ітэрацый, як у папярэдняй функцыі.
А недахоп у тым, што гэтая функцыя патрабуе больш памяці для таго, каб стварыць гэтую map.
Другі недахоп - гэта вялікі overhead на хэшаванне. Гэты недахоп не вельмі відавочны. І для нас ён таксама быў не вельмі відавочным, таму спачатку ў VictoriaMetrics рэалізацыя intersection была праз map. Але потым прафіляванне паказала, што асноўны працэсарны час марнуецца на запіс у map і на праверку наяўнасці значэння ў гэтай map.
Чаму ў гэтых месцах марнуецца працэсарны час? Таму што ў дадзеных радках Go вырабляе аперацыю хэшавання. Т. е. ён вылічае hash ад ключа, каб звярнуцца потым па зададзеным азначніку ў HashMap. Аперацыя па вылічэнні hash'а выконваецца за дзясяткі нанасекунд. Гэта павольна для VictoriaMetrics.
Я вырашыў рэалізаваць bitset, аптымізаваны спецыяльна для гэтага выпадку. Вось як зараз выглядае скрыжаванне двух slices. Тут ствараем bitset. Дадаем у яго элементы з першага slice. Потым правяраем наяўнасць гэтых элементаў у другім slice. І дадаем іх у вынік. Т. е. амаль не адрозніваецца ад папярэдняга прыкладу. Адзінае, што мы тут замянілі зварот да map кастамнымі функцыямі. add и has.
З першага погляду здаецца, што гэта павінна працаваць павольней, калі раней тамака выкарыстоўвалася стандартная map, а тут яшчэ нейкія функцыі выклікаюцца, але прафіляванне паказвае, што гэтая штука працуе ў 10 раз хутчэй, чым стандартная map для выпадку з VictoriaMetrics.
Акрамя гэтага, яна выкарыстоўвае значна менш памяці ў параўнанні з рэалізацыяй на map. Таму што мы захоўваем тут біты замест васьмібайтавых значэнняў.
Недахоп у такой рэалізацыі ў тым, што яна не такая відавочная, не трывіяльная.
Яшчэ адзін недахоп, які многія могуць не заўважаць - гэта тое, што дадзеная рэалізацыя можа дрэнна працаваць у некаторых выпадках. Т. е. яна аптымізавана для канкрэтнага выпадку, для дадзенага выпадку перасячэння ids часовых шэрагаў VictoriaMetrics. Гэта не значыць, што яна падыдзе для ўсіх выпадкаў. Калі яе няправільна выкарыстоўваць, тое атрымаем не прырост прадукцыйнасці, а out of memory error і запаволенне прадукцыйнасці.
Разгледзім рэалізацыю дадзенай структуры. Калі жадаеце паглядзець, то яна знаходзіцца ў зыходніках VictoriaMetrics, у тэчцы . Яна аптымізавана менавіта для выпадку VictoriaMetrics, дзе timeseries_id уяўляе з сябе 64-бітнае значэнне, дзе першыя 32 біта ў асноўным пастаянныя і мяняюцца толькі апошнія 32 біта.
Гэтая структура дадзеных не захоўваецца на дыску, яна працуе толькі ў памяці.
Вось яе API. Ён ня вельмі складаны. API падагнаны менавіта пад пэўны прыклад выкарыстання VictoriaMetrics. Т. е. тут няма лішніх функцый. Тут функцыі, якія відавочна выкарыстоўваюцца VictoriaMetrics.
Ёсць функцыі add, якая дадае новыя значэння. Ёсць функцыя has, якая правярае новыя значэння. І ёсць функцыя del, якая выдаляе значэння. Ёсць дапаможная функцыя len, Якая вяртае памер мноства. Функцыя clone клануе мноства. І функцыя appendto пераўтворыць гэты сэт у slice timeseries_ids.
Вось як выглядае рэалізацыя гэтай структуры звестак. У set ёсць два элемента:
-
ItemsCount- гэта дапаможнае поле, каб хутка вярнуць колькасць элементаў у set. Можна было б абысціся без гэтага дапаможнага поля, але яго прыйшлося дадаць сюды, таму што VictoriaMetrics часта апытвае ў сваіх алгарытмах даўжыню bitset. -
Другое поле - гэта
buckets. Гэта slice з структурыbucket32. У кожнай структуры захоўваеццаhiполе. Гэта верхнія 32 біта. І два slice -b16hisиbucketsзbucket16структур.
Тут захоўваюцца верхнія 16 біт другой часткі 64-бітнай структуры. А тут захоўваюцца bitsets для малодшых 16 біт кожнага байта.
Bucket64 складаецца з масіва uint64. Даўжыня вылічаецца з дапамогай гэтых канстант. У адным bucket16 максімум можа захоўваецца 2^16=65536 біт. Калі гэта падзяліць на 8, тое гэта 8 кілабайт. Калі падзяліць яшчэ раз на 8, то гэта 1000 uint64 значэнні. Г. зн. Bucket16 - гэта ў нас 8-кілабайтная структура.
Разгледзім, як рэалізаваны адзін з метадаў гэтай структуры дадання новага значэння.
Усё пачынаецца з uint64 значэння. Вылічаем верхнія 32 біта, вылічаем ніжнія 32 біта. Праходзімся па ўсіх buckets. Параўноўваем верхнія 32 біта ў кожным bucket з дадаваным значэннем. І калі яны супадаюць, то выклікаем функцыю add у структуры b32 buckets. І дадаем туды ніжнія 32 біта. І калі гэта вярнула true, то гэта значыць, што мы дадалі такое значэнне туды і ў нас такога значэння не было. Калі ён вяртае false, то такое значэнне ўжо было. Затым павялічваем колькасць элементаў у структуры.
Калі мы не знайшлі патрэбны bucket з патрэбным hi-значэннем, то мы выклікаем функцыю addAlloc, якая выробіць новы bucket, дадаючы яго ў bucket-структуру.
Гэта рэалізацыя функцыі b32.add. Яна падобная да папярэдняй рэалізацыі. Мы вылічаем старэйшыя 16 біт, малодшыя 16 біт.
Потым мы праходзімся па ўсіх верхніх 16 бітах. Знаходзім супадзенні. І пры супадзенні выкліканы метад add, які разгледзім на наступнай старонцы для bucket16.
І вось самы ніжні ўзровень, які мусіць быць максімальна аптымізаваны. Мы вылічаем для uint64 id значэнне ў slice bit, а таксама bitmask. Гэта маска для дадзенага 64-бітнага значэння, па якой можна праверыць наяўнасць гэтага біта, ці ўсталяваць яго. Мы правяраем наяўнасць гэтага біта, усталяванага і ўсталёўваны яго, і які вяртаецца наяўнасць. Вось такая рэалізацыя ў нас, якая дазволіла паскорыць аперацыю скрыжавання ids часавых шэрагаў у 10 раз у параўнанні са звычайнымі maps.
У VictoriaMetrics апроч гэтай аптымізацыі ёсць шмат іншых аптымізацый. Большасць з гэтых аптымізацый дададзены не проста так, а пасля прафілявання кода ў production.
Гэта галоўнае правіла аптымізацыі - не дадаваць аптымізацыю, мяркуючы, што тут будзе вузкае месца, таму што можа аказацца, што там не будзе вузкага месца. Аптымізацыя звычайна пагаршае якасць кода. Таму варта аптымізаваць толькі пасля прафілявання і пажадана ў production, каб гэта былі рэальныя дадзеныя. Каму цікава, можаце паглядзець зыходнікі VictoriaMetrics і вывучыць іншыя аптымізацыі, якія тамака ёсць.
У мяне пытанне пра bitset. Вельмі падобна на рэалізацыю C++ vector bool, аптымізаваны bitset. Вы адтуль узялі рэалізацыю?
Не, не адтуль. Пры рэалізацыі гэтага bitset я арыентаваўся на веды структуры гэтых ids timeseries, якія выкарыстоўваюць у VictoriaMetrics. А структура ў іх такая, што верхнія 32 біта ў асноўным пастаянныя. Ніжнія 32 біта могуць мяняцца. Чым ніжэй біт, тым часцей ён можа мяняцца. Таму гэтая рэалізацыя менавіта аптымізавана пад дадзеную структуру дадзеных. C++ рэалізацыя, наколькі я ведаю, аптымізавана пад агульны выпадак. Калі рабіць аптымізацыю пад агульны выпадак, тое гэта значыць, што яна будзе не самай аптымальнай пад пэўны выпадак.
Раю вам яшчэ паглядзець даклад Аляксея Мілавіда. Ён недзе з месяц таму расказваў пра аптымізацыю ў ClickHouse пад канкрэтныя спецыялізацыі. Ён як раз распавядае, што ў агульным выпадку C++ рэалізацыя або якая-небудзь іншая рэалізацыя заменчаны пад добрую працу ў сярэднім па бальніцы. Яна можа працаваць горш, чым спецыялізаваная рэалізацыя пад канкрэтныя веды, як у нас, калі мы ведаем, што верхнія 32 біта ў асноўным пастаянныя.
У мяне другое пытанне. У чым кардынальнае адрозненне ад InfluxDB?
Кардынальных адрозненняў шмат. Калі па прадукцыйнасці і па спажыванні памяці, то InfluxDB у тэстах паказвае ў 10 разоў больш спажывання памяці для high cardinality часовых шэрагаў, калі іх у вас шмат, напрыклад, мільёны. Напрыклад, VictoriaMetrics спажывае 1 GB на мільён актыўных шэрагаў, а InfluxDB пры гэтым спажывае 10 Gb. І гэта вялікая розніца.
Другое кардынальнае адрозненне ў тым, што ў InfluxDB дзіўныя мовы запытаў - Flux і InfluxQL. Яны не вельмі зручныя для працы з часовымі шэрагамі ў параўнанні з , які падтрымліваецца ў VictoriaMetrics. PromQL - гэта мова запытаў з Prometheus.
І яшчэ адно адрозненне - гэта тое, што ў InfluxDB трохі дзіўная мадэль дадзеных, дзе ў кожным радку можа захоўвацца некалькі fields з розным наборам тэгаў. Гэтыя радкі дзеляцца яшчэ на ўсякія табліцы. Вось гэтыя дадатковыя ўскладненні ўскладняюць наступную працу з гэтай базай. Яе складана падтрымліваць і разумець.
У VictoriaMetrics усё значна прасцей. Там кожны часавы шэраг уяўляе з сябе ключ-значэнне. Значэнне - гэта набор кропак - (timestamp, value), а ключ - гэта набор label=value. Няма ніякага падзелу на fields і measurements. Гэта дазваляе вам выбіраць любыя дадзеныя, а затым іх камбінаваць, складаць, адымаць, памнажаць, дзяліць у адрозненне ад InfluxDB, дзе вылічэнні паміж рознымі шэрагамі да гэтага часу не рэалізаваны, наколькі я ведаю. Калі нават рэалізаваны, то складана, трэба пісаць кучу кода.
У мяне ёсць удакладняючае пытанне. Я правільна зразумеў, што была нейкая праблема, пра якую вы расказвалі, што гэты інвертаваны індэкс не ўмяшчаецца ў памяць, таму там партыцыраванне ідзе?
Спачатку я паказаў наіўную рэалізацыю інвертаванага азначніка на стандартнай Go'шнай map'е. Такая рэалізацыя не падыходзіць для баз дадзеных, таму што гэты інвертаваны індэкс не захоўваецца на дыску, а база дадзеных павінна захоўваць на дыск, каб пры рэстарце гэтыя дадзеныя заставаліся даступнымі. У дадзенай рэалізацыі пры рэстарце прыкладання ў вас інвертаваны індэкс знікне. І вы страціце доступ да ўсіх дадзеных, таму што не зможаце знайсці іх.
Добры дзень! Дзякуй за даклад! Мяне клічуць Павел. Я з кампаніі Wildberries. У мяне некалькі пытанняў да вас. Пытанне першае. Як вам здаецца, калі б вы абралі іншы прынцып пры пабудове архітэктуры свайго прыкладання і партыцыянавалі дадзеныя па часе, то, магчыма, у вас атрымалася б рабіць скрыжаванне дадзеных пры пошуку, засноўваючыся толькі на тым, што ў адной партыцыі знаходзіцца дадзеныя за адзін прамежак часу , т. е. за адзін інтэрвал часу і вам бы не прыйшлося клапаціцца аб тым, што ў вас кавалкі па-рознаму раскіданыя? Пытанне нумар 2 - раз вы рэалізуеце падобны алгарытм з bitset і ўсім астатнім, то, магчыма, вы спрабавалі выкарыстоўваць інструкцыі працэсара? Можа, вы спрабавалі такія аптымізацыі?
На другі адразу адкажу. Мы да гэтага яшчэ не дайшлі. Але калі трэба будзе, дойдзем. А першае, якое было пытанне?
Вы абмяркоўвалі два сцэнары. І сказалі, што выбралі другі з больш складанай імплементацыяй. І не ўпадабалі першы, дзе дадзеныя партыцыянаваны па часе.
Так. У першым выпадку сумарны аб'ём азначніка быў бы больш, таму што мы ў кожнай партіціі павінны былі б захоўваць дублі дадзеных для тых часавых шэрагаў, якія працягваюцца скрозь гэтыя ўсе партіціі. І калі ў вас churn rate у часавых шэрагаў невялікі, т. е. увесь час адны і тыя ж шэрагі выкарыстоўваюцца, то ў першым выпадку мы бы нашмат мацней прайгралі ў аб'ёме займанай дыскавай прасторы ў параўнанні са другім выпадкам.
А так - так, партыцыянаванне па часе - добры варыянт. Яго Prometheus выкарыстоўвае. Але ў Prometheus ёсць іншы недахоп. Пры зліцці гэтых кавалкаў дадзеных, яму патрабуецца трымаць у памяці мета-інфармацыю па ўсіх label і timeseries. Таму, калі кавалкі дадзеных вялікія, якія ён злівае, тое спажыванне памяці вельмі моцна расце пры зліцці, у адрозненні ад VictoriaMetrics. Пры зліцці VictoriaMetrics наогул не спажывае памяць, там нейкія пары кілабайт спажываюцца, незалежна ад памераў аб'ядноўваных кавалкаў дадзеных.
Алгарытм, які ў вас выкарыстоўваецца, ён выкарыстоўвае памяць. У ёй адзначаюцца timeseries-пазнакі, на якіх ёсць значэнні. І такім чынам вы правяраеце парную наяўнасць у адным масіве дадзеных і ў іншым. І разумееце - адбыўся intersect ці не. Звычайна ў базах дадзеных рэалізуюць курсоры, ітэратары, якія захоўваюць бягучае сваё якое складаецца і што бегае па адсартаваных дадзеных за рахунак вы маеце простую складанасць у дадзеных аперацый.
Чаму мы не выкарыстоўваем курсоры для перасячэння дадзеных?
Да.
У нас у LevelDB ці ў mergeset захоўваюцца як раз адсартаваныя радкі. Мы можам курсорам прайсціся і знайсці скрыжаванне. А чаму не выкарыстоўваем? Таму што - гэта павольна. Таму што курсоры маюць на ўвазе пад сабой, што на кожны радок трэба выклікаць функцыю. Выклік функцыі - гэта 5 нанасекунд. І калі ў вас 100 радкоў, то атрымліваецца, што мы трацім паўсекунды толькі на выклік функцыі.
Такое ёсць, так. І апошняе ў мяне пытанне. Пытанне, можа быць, крыху дзіўна прагучыць. Чаму ў момант паступлення даных нельга лічыць усе неабходныя агрэгаты і ў неабходным выглядзе іх захоўваць? Навошта захоўваць вялізныя аб'ёмы ў нейкія сістэмы тыпу VictoriaMetrics, ClickHouse і т. д., каб потым вельмі шмат часу марнаваць на іх?
Прывяду прыклад, каб было больш зразумела. Дапушчальны, як працуе маленькі цацачны спідометр? Ён запісвае адлегласць, якую вы праехалі, увесь час яго дадаючы ў адну велічыню, у другую - час. І дзеліць. І атрымлівае сярэднюю хуткасць. Можна рабіць прыкладна тое ж самае. Складаць налёту ўсе неабходныя факты.
Добра, зразумеў пытанне. Ваш прыклад мае месца для жыцця. Калі вы ведаеце, якія вам патрэбныя агрэгаты, тое гэта самая лепшая рэалізацыя. Але праблема ў тым, што людзі захоўваюць гэтыя метрыкі, нейкія дадзеныя ў ClickHouse і яны не ведаюць яшчэ, як яны ў будучыні будуць іх агрэгаваць, фільтраваць, таму даводзіцца захоўваць усе волкія дадзеныя. Але калі вы ведаеце, што вам трэба падлічыць нешта сярэдняе, то чаму б не падлічыць яго замест таго, каб захоўваць там кучу сырых значэнняў? Але гэта толькі ў тым выпадку, калі вы сапраўды ведаеце, што вам трэба.
Дарэчы, базы для захоўвання часавых шэрагаў падтрымліваюць падлік агрэгатаў. Напрыклад, Prometheus падтрымлівае . Т. е. гэта можна зрабіць, калі вы ведаеце, якія вам спатрэбяцца агрэгаты. У VictoriaMetrics гэтага пакуль няма, але перад ёй звычайна ставіцца Prometheus, у якім можна гэта зрабіць у recoding rules.
Напрыклад, на папярэдняй працы трэба было падлічваць колькасць падзей у слізгальным акне за апошнюю гадзіну. Праблема ў тым, што прыйшлося рабіць кастамную рэалізацыю на Go, т. е. сэрвіс для падліку гэтай штукі. Гэты сэрвіс быў у выніку нетрывіяльным, таму што гэта складана лічыць. Рэалізацыя можа быць простай, калі вам трэба лічыць нейкія агрэгаты на фіксаваных інтэрвалах часу. Калі ж вы хочаце лічыць падзеі ў слізгальным акне, тое гэта не так проста, як здаецца. Я думаю, гэта не рэалізавана да гэтага часу ў ClickHouse або ў timeseries-базах, таму што складана ў рэалізацыі.
І яшчэ адно пытанне. Мы зараз казалі аб асерадненні, і я ўспомніў, што калісьці была такая штука як Graphite з бэкэндам Carbon. І ён умеў старыя дадзеныя прарэжваць, т. е. пакідаць адну кропку ў хвіліну, адну кропку ў гадзіну і т. д. У прынцыпе, гэта досыць зручна, калі нам патрэбныя волкія дадзеныя, умоўна кажучы, за месяц, а ўсё астатняе можна прарэдзіць . Але Prometheus, VictoriaMetrics гэтую функцыянальнасць не падтрымліваюць. Ці плануецца падтрымліваць? Калі не, то чаму?
Дзякуй за пытанне. Нашы карыстачы яго перыядычна задаюць. Пытаюцца, калі мы дадамо падтрымку прарэджвання (downsampling). Тут некалькі праблем. Па-першае, кожны карыстач разумее пад downsampling штосьці сваё: хтосьці жадае атрымаць любую адвольную кропку на зададзеным інтэрвале, хтосьці жадае максімальныя, мінімальныя, сярэднія значэнні. Калі ў вашу базу пішуць дадзеныя шматлікія сістэмы, то нельга іх веславаць пад адзін грабянец. Можа аказацца, што для кожнай сістэмы трэба выкарыстоўваць рознае прарэджванне. І гэта складана ў рэалізацыі.
І другое - гэта тое, што VictoriaMetrics, як і ClickHouse, аптымізавана пад працу над вялікім аб'ёмам сырых дадзеных, таму яна можа пералапаціць мільярд радкоў менш, чым за секунду, калі ў вас ёсць шмат ядраў у вашай сістэме. Сканіраванне кропак часавага шэрагу ў VictoriaMetrics - 50 000 000 кропак у секунду на адно ядро. І гэтая прадукцыйнасць маштабуецца на наяўныя ядры. Т. е. калі ў вас 20 ядраў, напрыклад, тое атрымаецца сканаванне мільярда кропак у секунду. І гэтая ўласцівасць VictoriaMetrics і ClickHouse змяншае запатрабаванне ў downsamling.
Яшчэ адна ўласцівасць у тым, што VictoriaMetrics эфектыўна сціскае гэтыя дадзеныя. Сціск у сярэднім на production ад 0,4 да 0,8 байт на кропку. Кожная кропка - гэта timestamp + значэнне. І яна сціскаецца менш, чым у XNUMX байт у сярэднім.
Сяргей. У мяне ёсць пытанне. Які мінімальны квант часу запісы?
Адна мілісекунда. Нядаўна ў нас была размова з іншымі распрацоўшчыкамі баз дадзеных для часовых шэрагаў. У іх мінімальны квант часу - гэта адна секунда. І у Graphite, напрыклад, таксама адна секунда. У OpenTSDB таксама адна секунда. У InfluxDB - нанасекундная дакладнасць. У VictoriaMetrics - адна мілісекунда, таму што ў Prometheus адна мілісекунда. І VictoriaMetrics распрацоўвалася як remote storage для Prometheus першапачаткова. Але зараз яна можа захоўваць дадзеныя і з іншых сістэм.
Чалавек, з якім я размаўляў, кажа, што ў іх секундная дакладнасць - ім гэтага дастаткова, таму што гэта залежыць ад тыпу дадзеных, якія захоўваюцца ў базу часовых шэрагаў. Калі гэта DevOps-дадзеныя або дадзеныя з інфраструктуры, дзе вы збіраеце іх з інтэрвалам у 30 секунд, у хвіліну, то там секунднай дакладнасці дастаткова, менш ужо не трэба. А калі вы збіраеце гэтыя дадзеныя high frequency trading systems, то тамака патрэбна нанасекундная дакладнасць.
Мілісекундная дакладнасць у VictoriaMetrics падыходзіць і для DevOps-кейса, і можа падысці для большасці кейсаў, якія я згадаў у пачатку даклада. Адзінае, для чаго яна можа не падысці гэта high frequency trading systems.
Дзякуй! І яшчэ пытанне. Якая сумяшчальнасць у PromQL?
Поўная зваротная сумяшчальнасць. VictoriaMetrics падтрымлівае поўнасцю PromQL. Акрамя гэтага яна дадае яшчэ дадатковую пашыраную функцыянальнасць на PromQL, якая называецца . Наконт гэтай пашыранай функцыянальнасці ёсць даклад на YouTube. Я расказваў на Monitoring Meetup вясной у Піцеры.
Telegram канал .
Толькі зарэгістраваныя карыстачы могуць удзельнічаць у апытанні. , Калі ласка.
Што вам перашкаджае перайсці на VictoriaMetrics як доўгатэрміновае сховішча для Prometheus? (Пішыце ў каментарах, я дадам у апытанне))
-
71,4%Не выкарыстоўваю Prometheus5
-
28,6%Не ведаў пра VictoriaMetrics2
Прагаласавалі 7 карыстальнікаў. Устрымаліся 12 карыстальнікаў.
Крыніца: habr.com