База данни KDB+: от финансите до „Формула 1“

KDB+, продукт на компанията KX — това е широко известна в тесни кръгове, изключително бърза колонообразна база данни, предназначена за съхранение на времеви редици и аналитични изчисления на тяхна база. Първоначално тя беше (и все още е) много популярна в индустрията на финансите — използва се от всички топ 10 инвестиционни банки и много известни хедж фондове, борси и други организации. В последно време KX реши да разшири клиентската си база и сега предлага решения и в други области, където има големи обеми структурирани данни — телекомуникации, биоинформатика, производство и т.н. Включително те станаха партньор на екипа Aston Martin Red Bull Racing във Формула 1, където помагат за събиране и обработка на данни от сензорите на автомобилите и анализират тестовете в аеродинамичния тунел. В тази статия искам да разкажа какви особености правят KDB+ свръх производителна, защо компаниите са готови да инвестират значителни суми в нея, и накрая, защо всъщност това не е само база данни.
 

 
В тази статия ще се опитам да обясня по принцип какво представлява KDB+, какви възможности и ограничения има, и каква е ползата от нея за компаниите, които искат да обработват големи обеми данни. Няма да задълбочавам в детайлите на реализацията на KDB+ и в детайлите на нейния език за програмиране Q. И двете теми са много обширни и заслужават отделни статии. Много информация по тези теми може да се намери на сайта code.kx.com, включително книга по Q — Q For Mortals (виж линка по-долу).

Някои термини

• In-memory база данни. База данни, която съхранява данни в оперативната памет за ускоряване на достъпа. Предимствата на такава база са ясни, а недостатъците — възможността за загуба на данни, необходимостта от много памет на сървъра.
• Колонообразна база данни. База данни, където данните се съхраняват по колони, а не ред по ред. Основното предимство на такава база е, че данните от една колона се съхраняват заедно на диска и в паметта, което значително ускорява достъпа до тях. Няма нужда да зареждате колоните, които не се използват в заявката. Основен недостатък — трудно е да се модифицират и премахват записи.
• Времеви ред. Данни с колонка тип дата или време. Обикновено за такива данни важи редът по време, за да бъде лесно определено коя запис предшества или следва текущия, или да бъдат приложени функции, чийто резултат зависи от реда на записите. Класическите бази данни са изградени на напълно различен принцип — представяне на съвкупност от записи като множество, където редът на записите по принцип не е определен.
• Вектор. В контекста на KDB+ — това е списък от елементи с един атомарен тип, например числа. С други думи, масив от елементи. Масивите, за разлика от списъците, могат да се съхраняват компактно и да се обработват с помощта на векторни инструкции на процесора.

Историческа справка

Компанията KX е основана през 1993 година от Артър Уитни, който преди това е работил в банка Морган Стенли върху езика A+, наследник на APL — много оригинален и в свое време популярен език във финансовия свят. Разбира се, в KX Артър е продължил в същия дух и е създал векторно-функционалния език K, ръководейки се от идеите на радикалния минимализъм. Програмите на K изглеждат като безпорядъчен набор от знакове за препинание и специални символи, значението на знаците и функциите зависи от контекста, а всяка операция носи много повече значение, отколкото в традиционните програмни езици. Поради това програмата на K заема минимум място — няколко реда могат да заменят страници текст на многословни езици като Java — и е свръхконцентрирана реализация на алгоритъм.
 
Функцията на K, реализираща по-голямата част от генератора на LL1 парсера според зададена граматика:

1. pp:{q:{(x;p3(),y)};r:$[-11=@x;$x;11=@x;q[`N;$*x];10=abs@@x;q[`N;x]  
2.   ($)~*x;(`P;p3 x 1);(1=#x)&11=@*x;pp[{(1#x;$[2=#x;;,:]1_x)}@*x]  
3.      (?)~*x;(`Q;pp[x 1]);(*)~*x;(`M;pp[x 1]);(+)~*x;(`MP;pp[x 1]);(!)~*x;(`Y;p3 x 1)  
4.      (2=#x)&(@x 1)in 100 101 107 7 -7h;($[(@x 1)in 100 101 107h;`Ff;`Fi];p3 x 1;pp[*x])  
5.      (|)~*x;`S,(pp'1_x);2=#x;`C,{@[@[x;-1+#x;{x,")"}];0;"(",]}({$[".s.C"~4#x;6_-2_x;x]}'pp'x);'`pp];  
6.   $[@r;r;($[1<#r;".s.";""],$*r),$[1<#r;"[",(";"/1_r),"]";""]]}  

 Тази философия на екстремалната ефективност с минимално движение Артур е реализирал и в KDB+, който се появи през 2003 година (мисля, сега е ясно откъде идва буквата K в името) и всъщност е интерпретатор на четвъртата версия на езика K. Върху K е добавена по-приятна за окото версия, наречена Q. В Q е добавена и поддръжка на специфичен диалект на SQL — QSQL, а в интерпретатора — поддръжка на таблици като системен тип данни и средства за работа с таблици в паметта и на диска и т.н.
 
Така, от гледна точка на потребителя, KDB+ е просто интерпретатор на езика Q с поддръжка на таблици и изрази, наподобяващи SQL в стил LINQ от C#. Това е най-важната разлика на KDB+ от другите бази данни и основното й конкурентно предимство, което често се изпуска. Това не е база данни + помощен език, а цялостен мощен език за програмиране + вградена поддръжка на функции за бази данни. Тази разлика ще играе решаваща роля при изброяване на всички предимства на KDB+. Например…
 

Размер

Според съвременните стандарти KDB+ има просто микроскопичен размер. Това е в буквален смисъл един изпълним файл с размер по-малък от един мегабайт и един малък текстов файл с някои системни функции. Всъщност — по-малко от един мегабайт и за тази програма компаниите плащат десетки хиляди долари годишно за един процесор на сървър.

• Такъв размер позволява на KDB+ прекрасно да работи на всякакъв хардуер — от микрокомпютъра Pi до сървъри с терабайти памет. Това по никакъв начин не влияе на функционалността, а и Q стартира моментално, което позволява да се използва и като скриптов език.
• При такъв размер интерпретаторът Q напълно помещава в кеша на процесора, което ускорява изпълнението на програмите.
• При такъв размер на изпълнимия файл процесът Q заема незначително малко място в паметта, може да се стартира стотици. В същото време, при нужда, Q може да оперира и с десетки или стотици гигабайти памет в рамките на един процес.

Универсалност

Q е прекрасно подходяща за най-разнообразни задачи. Процесът Q може да изпълнява ролята на историческа база данни и да предоставя бърз достъп до терабайти информация. Например, имаме десетки исторически бази, в които един несжат ден данни заема повече от 100 гигабайта. Въпреки това, при разумни ограничения, запитване към базата ще бъде изпълнено за десетки до стотици милисекунди. Общо взето, за потребителските запитвания имаме универсален тайм-аут — 30 секунди — и той сработва много рядко.
 
Със същата лекота Q може да бъде in-memory база данни. Добавянето на нови данни в таблиците в паметта става толкова бързо, че ограничителният фактор са потребителските запитвания. Данните в таблиците се съхраняват по колони, което означава, че всяка операция по колона ще използва кеша на процесора на пълна мощност. В допълнение към това, в KX се опитаха да реализират всички базови операции, като аритметични, чрез векторни инструкции на процесора, максимизирайки тяхната скорост. Q може да изпълнява и задачи, които не са присъщи за бази данни — например, да обработва потокови данни и да изчислява в „реално време“ (с забавяне от десетки милисекунди до няколко секунди в зависимост от задачата) различни агрегатни функции за финансови инструменти за различни времеви интервали или да изгражда модел на влиянието на извършена сделка на пазара и да провежда нейното профилиране почти незабавно след извършването й. При такива задачи основната времева закъснение най-често не се дължи на Q, а на необходимостта от синхронизиране на данни от различни източници. Високата скорост се постига благодарение на това, че данните и функциите, които ги обработват, се намират в един процес, а обработката се свежда до изпълнение на няколко QSQL израза и join-ове, които не се интерпретират, а се изпълняват с бинарен код.
 
Накрая, на Q може да се пишат и всякакви сервизни процеси. Например, Gateway процеси, които автоматично разпределят потребителските запитвания по нужните бази и сървъри. Програмистът има пълна свобода да реализира всеки алгоритъм за балансиране, приоритизиране, отказоустойчивост, права за достъп, квоти и всичко, което му е на ума. Главната проблематика тук е, че ще трябва всичко това да се реализира самостоятелно.
 
За пример ще изброя какви типове процеси имаме. Те активно се използват и работят заедно, обединявайки десетки различни бази, обработвайки данни от множество източници и обслужвайки стотици потребители и приложения.

• Конектори (feedhandler) към източниците на данни. Тези процеси обикновено използват външни библиотеки, които се зареждат в Q. C-интерфейсът в Q е изключително прост и позволява лесно създаване на прокси функции за всяка C/C++ библиотека. Q е достатъчно бърз, за да се справи, например, с обработката на потока FIX съобщения от всички европейски фондови борси едновременно.
• Разпределители на данни (tickerplant), които служат като междинно звено между конекторите и потребителите. В същото време те записват входящите данни в специален бинарен лог, осигурявайки устойчивост на потребителите при загуба на връзка или рестартиране.
• In-memory бази данни (rdb). Тези бази осигуряват максимално бърз достъп до свежи сурови данни, съхранявайки ги в паметта. Обикновено те натрупват данни в таблици през деня и ги обнуляват през нощта.
• Persist бази данни (pdb). Тези бази осигуряват запазване на данните за текущия ден в историческа база. Обикновено, за разлика от rdb, те не съхраняват данните в паметта, а използват специален кеш на диска в течение на деня и копират данните в полунощ в историческата база.
• Исторически бази (hdb). Тези бази предоставят достъп до данни за предишни дни, месеци и години. Размерът им (в дни) е ограничен само от капацитета на твърдия диск. Данните могат да бъдат разположени навсякъде, включително на различни дискове за ускоряване на достъпа. Съществува възможност за компресиране на данните, използвайки няколко алгоритма по избор. Структурата на базата е добре документирана и проста, данните се съхраняват по колони в обикновени файлове, така че те могат да бъдат обработвани и с помощта на операционната система.
• Бази с агрегирана информация. Съхраняват различни агрегирани данни, обикновено групирани по наименование на инструмента и времеви интервал. In-memory базите актуализират състоянието си при всяко входящо съобщение, а историческите хранят предварително изчислени данни за ускоряване на достъпа до историческите данни.
• Накрая, gateway процеси, обслужващи приложения и потребители. Q позволява да се реализира напълно асинхронна обработка на входящи съобщения, разпределянето им по бази, проверка на права за достъп и др. Забелязвам, че съобщенията не са ограничени и най-често не представляват SQL изрази, както е в другите бази данни. Най-често SQL изразът е скрит в специална функция и се конструира въз основа на параметрите, поискани от потребителя — извършва се конвертиране на времето, филтриране, данните се нормализират (например, цената на акциите се изравнява, ако е имало дивидентни плащания) и т.н.

Типична архитектура за един тип данни:

Скорост

Въпреки че Q е интерпретираем език, той също така е векторен език. Това означава, че много вградени функции, по-специално аритметичните, приемат аргументи във всякаква форма — числа, вектори, матрици, списъци, а от програмиста се очаква да реализира програмата като операции с масиви. В такъв език, ако съберете два вектора с милион елемента, вече няма значение, че езикът е интерпретируем, събирането ще се извърши с супероптимизирана бинарна функция. Тъй като голямата част от времето в програмите на Q отива за операции с таблици, които използват тези основни векторизирани функции, в крайна сметка имаме доста прилична скорост на работа, позволяваща обработката на огромен обем данни дори в един процес. Това е подобно на математическите библиотеки в Python — въпреки че самият Python е доста бавен език, в него има много прекрасни библиотеки като numpy, които позволяват обработка на числови данни със скоростта на компилиран език (между другото, numpy е идеологически близка до Q).
 
Освен това, в KX внимателно са подхождали към проектирането на таблиците и оптимизацията на работата с тях. Първо, поддържат се няколко вида индекси, които се поддържат от вградени функции и могат да бъдат приложени не само към колоните на таблиците, но и към всякакви вектори — групиране, сортиране, атрибут на уникалност и специално групиране за исторически бази. Индексът се налага елементарно и автоматично се коригира при добавяне на елементи в колоната/вектора. Индексите успешно могат да се налагат на колоните на таблиците както в паметта, така и на диска. При изпълнение на QSQL запитване индексите се използват автоматично, ако е възможно. На второ място, работата с исторически данни се осъществява чрез механизъм за отразяване на файловете на ОС (memory map). Големи таблици никога не се зареждат в паметта; вместо това нужните колони се отразяват директно в паметта и наистина се зарежда само онзи техен фрагмент (тук помагат и индексите), който е необходим. За програмиста няма значение дали данните са в паметта или не, механизъмът за работа с mmap е напълно скрит в недрата на Q.
 
KDB+ е нерелационна база данни, таблиците могат да съдържат произволни данни, при това реда на редовете в таблицата не се променя при добавяне на нови елементи и може и трябва да се използва при написването на запитвания. Тази особеност е крайно необходима за работа с времеви редици (данни от борси, телеметрия, логове на събития), защото, ако данните са сортирани по време, потребителят не трябва да прилага никакви SQL трикове, за да намери в таблицата първия или последния по време ред или N реда, да определи кой ред следва след N-ти ред и т.н. Още повече се опростяват join-овете на таблиците, например да се намери за 16000 сделки VOD.L (Водафон) последната котировка в таблица с 500 милиона елемента отнема около секунда на диска и десетина милисекунди в паметта.
 
Пример за join по време — таблицата quote се отразява в паметта, така че няма нужда да се посочва VOD.L в where, неявно се използва индексът на колоната sym и фактът, че данните са сортирани по време. Почти всички join-ове в Q са обикновени функции, а не част от израза select:

1. aj[`sym`time;select from trade where date=2019.03.26, sym=`VOD.L;select from quote where date=2019.03.26]  

Накрая, трябва да се отбележи, че инженерите в KX, започвайки от Артър Уитни, наистина са обсебени от ефективността и полагат всички усилия да извлекат максимума от стандартните функции на Q и да оптимизират най-често срещаните модели на използване.
 

Резюме

KDB+ е популярна сред бизнеса най-вече благодарение на своята изключителна универсалност - тя служи еднакво добре и като in-memory база, и като база за съхранение на терабайти исторически данни, и като платформа за анализ на данни. Благодарение на факта, че обработката на данни се извършва директно в базата, се постига висока скорост на работа и икономия на ресурси. Пълноценен език за програмиране, интегриран с функциите на базата данни, позволява да се реализира на една платформа целият стек от необходими процеси - от получаване на данни до обработка на потребителски запитвания.
 

Допълнителна информация

Недостатъци

Съществен недостатък на KDB+/Q е високият праг на влизане. Языкът има странен синтаксис, някои функции са силно претоварени (например, value има около 11 варианта на използване). Най-важното е, че изисква радикално различен подход към писането на програми. Векторният език изисква постоянно мислене в термини на преобразувания на масиви, всички цикли да се реализират чрез няколко варианта на функции map/reduce (които в Q се наричат adverbs), никога да не се опитвате да спестите, заменяйки векторните операции с атомарни. Например, за намиране на индекса на N-то вхождане на елемента в масива трябва да се пише:

1. (where element=vector)[N]  

въпреки че това изглежда ужасно неефективно според стандартите на C/Java (създава булев вектор, where връща индексите на истинските елементи в него). Но такава запис прави смисъла на израза по-разбираем и вие използвате бързи векторни операции вместо бавни атомарни. Концептуалната разлика между векторния език и останалите е сравнима с разликата между императивния и функционалния подходи към програмирането, и към това трябва да се подготвите.
 
Някои потребители също са недоволни от QSQL. Фактът е, че той само прилича на истински SQL. В действителност, това е просто интерпретатор на SQL-подобни изрази, който не поддържа оптимизация на запитванията. Потребителят трябва сам да пише оптимални запитвания, и то на Q, което много хора не са готови да направят. От друга страна, разбира се, винаги може сам да напишете оптимизирано запитване, вместо да разчитате на черния кутия-оптимизатор.
 
Като плюс книгата по Q — Q For Mortals е налична безплатно на уебсайта на компанията, където е събрано много други полезни материали.
 
Още един голям минус — цената на лиценза. Това са десетки хиляди долари годишно за един CPU. Само големи компании могат да си позволят такива разходи. Наскоро KX направи лиценза по-гъвкав и предлага възможност да плащате само за времето на ползване или да наемете KDB+ в облаците на Google и Amazon. KX предлага също и за изтегляне безплатна версия за необлагаеми цели (32-битова версия или 64-битова по запитване).
 

Конкуренти

Съществуват доста специализирани бази данни, изградени на подобни принципи — колонни, in-memory, ориентирани към много големи обеми данни. Проблемът е в това, че това са специализирани бази данни. Ясен пример е Clickhouse. Тази база данни има много сходен с KDB+ принцип на съхранение на данни на диска и изграждане на индекси, някои заявки тя изпълнява по-бързо от KDB+, макар и не съществено. Но дори и като база данни, Clickhouse е по-специализирана от KDB+ — уеб аналитика срещу произволни времеви редици (това разграничение е много важно — заради него, например, в Clickhouse няма възможност за използване на подреденост на записите). Но най-важното е, че Clickhouse няма универсалността на KDB+, език, който позволява обработка на данните директно в базата, а не натоварването им предварително в отделно приложение, изграждането на произволни SQL изрази, прилагането на произволни функции в заявката, създаването на процеси, несвързани с изпълнението на функции от историческата база. Поради това е трудно да се сравнява KDB+ с други бази, те могат да бъдат по-добри в отделни сценарии на използване или просто по-добри, когато става въпрос за задачи на класическите бази данни, но не ми е известен друг толкова ефективен и универсален инструмент за обработка на времеви данни.
 

Интеграция с Python

За да се опрости работата с KDB+ за хора, които не са запознати с технологията, KX създадоха библиотеки за тясна интеграция с Python в рамките на един процес. Може както да извиквате всяка python-функция от Q, така и обратното — да извиквате всяка Q функция от Python (в частност QSQL изрази). Библиотеките конвертират, когато е необходимо (за ефективност не винаги), данните от формата на един език в формата на друг. В резултат Q и Python съжителстват в толкова тясна симбиоза, че границите между тях се размиват. В резултат на това програмистът, от една страна, има пълен достъп до многобройни полезни библиотека на Python, а от друга страна, получава интегрирана в Python бърза база за работа с големи данни, което е особено полезно за тези, които се занимават с машинно обучение или моделиране.
 
Работа с Q в Python:

1. >>> q()  
2.q)trade:([]date:();sym:();qty:())  
3. q)  
4. >>> q.insert('trade', (date(2006,10,6), 'IBM', 200))  
5. k(',0')  
6. >>> q.insert('trade', (date(2006,10,6), 'MSFT', 100))  
7. k(',1')  

Връзки

Сайт на компанията — https://kx.com/
Сайт за разработчици — https://code.kx.com/v2/
Книга Q For Mortals (на английском) — https://code.kx.com/q4m3/
Статьи на тема приложений KDB+ / Q от служителите на kx — https://code.kx.com/v2/wp/

Източник: habr.com