KDB+, produkt firmy — to szeroko znana w wąskich kręgach, niezwykle szybka, kolumnowa baza danych, zaprojektowana do przechowywania szeregów czasowych oraz analitycznych obliczeń opartych na tych danych. Początkowo cieszyła się (i cieszy) dużą popularnością w branży finansowej — korzystają z niej wszystkie 10 najlepszych banków inwestycyjnych oraz wiele znanych funduszy hedgingowych, giełd i innych organizacji. Ostatnio zespół KX postanowił rozszerzyć swoją bazę klientów i teraz oferuje rozwiązania także w innych obszarach, gdzie występuje duża ilość danych uporządkowanych w czasie lub w inny sposób — telekomunikacja, bioinformatyka, produkcja itd. W tym zakresie zostali także partnerem zespołu Aston Martin Red Bull Racing w „Formule 1”, gdzie pomagają zbierać i przetwarzać dane z czujników bolidów oraz analizować testy w tunelu aerodynamicznym. W tym artykule chciałbym opisać, jakie cechy KDB+ sprawiają, że jest ona niezwykle wydajna, dlaczego firmy są skłonne inwestować w nią duże pieniądze i w końcu, dlaczego tak naprawdę nie jest to baza danych.
W tym artykule postaram się ogólnie opisać, czym jest KDB+, jakie możliwości i ograniczenia posiada oraz jakie korzyści przynosi firmom chcącym przetwarzać duże ilości danych. Nie zamierzam zagłębiać się w szczegóły implementacji KDB+ oraz jej języka programowania Q. Oba te tematy są bardzo rozległe i zasługują na osobne artykuły. Wiele informacji na ten temat można znaleźć na stronie code.kx.com, w tym książkę na temat Q — Q For Mortals (patrz link poniżej).
Niektóre terminy
- Baza danych w pamięci. Baza danych, która przechowuje dane w pamięci operacyjnej w celu przyspieszenia dostępu. Zalety takiej bazy są oczywiste, a wady — możliwość utraty danych, konieczność posiadania dużej pamięci na serwerze.
- Kolumnowa baza danych. Baza danych, w której dane są przechowywane kolumnami, a nie rekord po rekordzie. Główną zaletą takiej bazy jest to, że dane z jednej kolumny są przechowywane razem na dysku i w pamięci, co znacznie przyspiesza dostęp do nich. Nie ma potrzeby ładowania kolumn, które nie są używane w zapytaniu. Główną wadą jest to, że trudno jest modyfikować i usuwać rekordy.
- Szereg czasowy. Dane z kolumn typu data lub czasu. Z reguły dla takich danych ważne jest uporządkowanie według czasu, aby łatwo można było określić, który zapis poprzedza lub następuje po bieżącym, lub aby stosować funkcje, których wyniki zależą od kolejności zapisów. Klasyczne bazy danych są zbudowane na zupełnie innym zasadzie — przedstawieniu zbioru zapisów jako zbioru, gdzie kolejność zapisów w zasadzie nie jest określona.
- Wektor. W kontekście KDB+ — to lista elementów jednego atomowego typu, na przykład liczb. Innymi słowy, to tablica elementów. Tablice, w przeciwieństwie do list, można przechowywać w sposób kompaktowy i przetwarzać przy użyciu instrukcji wektorowych procesora.
Kontekst historyczny
Firma KX została założona w 1993 roku przez Arthura Whitneya, który wcześniej pracował w banku Morgan Stanley nad językiem A+, następcą APL — bardzo oryginalnym i w swoim czasie popularnym językiem w świecie finansów. Oczywiście w KX Arthur kontynuował w tym samym duchu i stworzył wektorowo-funkcjonalny język K, kierując się ideami radykalnego minimalizmu. Programy w K wyglądają jak chaotyczny zbiór znaków interpunkcyjnych i symboli specjalnych, znaczenie znaków i funkcji zależy od kontekstu, a każda operacja niesie w sobie znacznie więcej sensu, niż ma to miejsce w tradycyjnych językach programowania. Dzięki temu program w K zajmuje minimalną przestrzeń — kilka linii może zastąpić strony tekstu z rozbudowanego języka takiego jak Java — i jest ultra skoncentrowaną realizacją algorytmu.
Funkcja w K, która realizuje większą część generatora parsowania LL1 według określonej gramatyki:
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),"]";""]]}
Filosofia ekstremalnej efektywności przy minimalnych ruchach, jaką Arthur wcielił w KDB+, pojawiła się w 2003 roku (myślę, że teraz jasne jest, skąd wzięła się litera K w nazwie) i jest niczym innym jak interpretatorem czwartej wersji języka K. Na K nałożona została bardziej przyjemna dla oka wersja K o nazwie Q. W Q dodano również wsparcie dla specyficznego dialektu SQL — QSQL, a w interpreterze — wsparcie dla tabel, jako systemowego typu danych, oraz narzędzi do pracy z tabelami w pamięci i na dysku itd.
W ten sposób, z perspektywy użytkownika, KDB+ to po prostu interpreter języka Q z wsparciem dla tabel i podobnych do SQL wyrażeń w stylu LINQ z C#. To kluczowa różnica KDB+ w porównaniu do innych baz danych i jej główna przewaga konkurencyjna, która często umyka uwadze. To nie baza danych + wspomagający język, ale pełnoprawny mocny język programowania + wbudowane wsparcie dla funkcji bazy danych. Ta różnica odegra decydującą rolę przy przedstawianiu wszystkich zalet KDB+. Na przykład…
Wymiary
Według współczesnych standardów KDB+ ma po prostu mikroskopijny rozmiar. To dosłownie jeden plik wykonywalny o rozmiarze mniejszym niż megabajt oraz jeden mały plik tekstowy z kilkoma funkcjami systemowymi. Rzeczywiście — mniej niż jeden megabajt, a firmy płacą dziesiątki tysięcy dolarów rocznie za jeden procesor na serwerze.
- Taki rozmiar pozwala KDB+ doskonale funkcjonować na każdym sprzęcie — od mikrokomputera Pi po serwery z terabajtami pamięci. Nie wpływa to na funkcjonalność, co więcej, Q uruchamia się błyskawicznie, co pozwala używać go również jako języka skryptowego.
- Przy takim rozmiarze interpreter Q w całości mieści się w pamięci podręcznej procesora, co przyspiesza wykonanie programów.
- Przy takim rozmiarze pliku wykonywalnego proces Q zajmuje znikomo mało miejsca w pamięci, można uruchamiać ich setki. Przy tym, w razie potrzeby, Q może operować również na dziesiątkach-setkach gigabajtów pamięci w ramach jednego procesu.
Wszechstronność
Q doskonale nadaje się do różnorodnych zadań. Proces Q może pełnić rolę historycznej bazy danych i zapewniać szybki dostęp do terabajtów informacji. Mamy na przykład dziesiątki historycznych baz danych, z których w niektórych jeden nieskompresowany dzień danych zajmuje ponad 100 gigabajtów. Niemniej jednak, przy rozsądnych ograniczeniach, zapytanie do bazy zostanie zrealizowane w dziesiątkach lub setkach milisekund. Ogólnie rzecz biorąc, dla zapytań użytkowników mamy uniwersalny limit czasowy wynoszący 30 sekund, który działa bardzo rzadko.
Z taką samą łatwością Q może działać jako baza danych w pamięci. Dodawanie nowych danych do tabel w pamięci odbywa się na tyle szybko, że ograniczającym czynnikiem są zapytania użytkowników. Dane w tabelach są przechowywane w kolumnach, co oznacza, że każda operacja na kolumnie wykorzystuje pamięć podręczną procesora w pełni. Dodatkowo, w KX starano się wdrożyć wszystkie podstawowe operacje, takie jak arytmetyka, za pomocą instrukcji wektorowych procesora, maksymalizując ich prędkość. Q może także wykonywać zadania, które nie są typowe dla baz danych — na przykład przetwarzać dane strumieniowe i obliczać w „czasie rzeczywistym” (z opóźnieniem od dziesiątek milisekund do kilku sekund w zależności od zadania) różne funkcje agregujące dla instrumentów finansowych na różnych przedziałach czasowych lub budować model wpływu zrealizowanej transakcji na rynek i przeprowadzać jego profilowanie praktycznie natychmiast po dokonaniu transakcji. W takich zadaniach głównym źródłem opóźnień nie jest Q, lecz konieczność synchronizacji danych z różnych źródeł. Wysoka prędkość jest osiągana dzięki temu, że dane i funkcje, które je przetwarzają, znajdują się w jednym procesie, a przetwarzanie sprowadza się do wykonania kilku wyrażeń QSQL i złączeń, które nie są interpretowane, a wykonywane poprzez kod binarny.
W końcu na Q można pisać także wszelkie procesy serwisowe. Na przykład procesy Gateway, które automatycznie rozdzielają zapytania użytkowników do odpowiednich baz i serwerów. Programista ma pełną swobodę w realizacji dowolnego algorytmu do balansowania, priorytetyzacji, odporności na awarie, praw dostępu, limitów i w zasadzie czegokolwiek mu się żywnie podoba. Główny problem polega jednak na tym, że trzeba to wszystko wdrożyć samodzielnie.
Na przykład, wymienię, jakie typy procesów są dostępne w naszej ofercie. Wszystkie one są aktywnie wykorzystywane i współpracują ze sobą, łącząc w jedną całość dziesiątki różnych baz, przetwarzając dane z wielu źródeł i obsługując setki użytkowników oraz aplikacji.
- Connectory (feedhandler) do źródeł danych. Te procesy zazwyczaj wykorzystują zewnętrzne biblioteki, które są ładowane w Q. Interfejs C w Q jest wyjątkowo prosty i pozwala bez trudu stworzyć funkcje proxy dla dowolnej biblioteki C/C++. Q jest wystarczająco szybki, aby poradzić sobie na przykład z przetwarzaniem strumienia komunikatów FIX z wszystkich europejskich giełd jednocześnie.
- Dystrybutory danych (tickerplant), które pełnią rolę pośrednika między konektorami a konsumentami. Jednocześnie zapisują przychodzące dane w specjalnym dzienniku binarnym, zapewniając niezawodność dla konsumentów w przypadku utraty połączenia lub ponownych uruchomień.
- Bazy danych w pamięci (rdb). Te bazy zapewniają maksymalnie szybki dostęp do surowych, świeżych danych, przechowując je w pamięci. Zazwyczaj gromadzą dane w tabelach przez cały dzień i resetują je w nocy.
- Bazy danych persystentnych (pdb). Te bazy zapewniają przechowywanie danych z dzisiejszego dnia w bazie historycznej. Zazwyczaj, w przeciwieństwie do rdb, nie przechowują danych w pamięci, lecz wykorzystują specjalny cache na dysku przez cały dzień i kopiują dane o północy do bazy historycznej.
- Bazy historyczne (hdb). Te bazy zapewniają dostęp do danych z poprzednich dni, miesięcy i lat. Ich rozmiar (w dniach) jest ograniczony jedynie pojemnością dysków twardych. Dane mogą być rozmieszczone gdziekolwiek, w tym na różnych dyskach w celu przyspieszenia dostępu. Istnieje możliwość kompresji danych przy użyciu kilku algorytmów do wyboru. Struktura bazy jest dobrze udokumentowana i prosta, dane są przechowywane w kolumnach w zwykłych plikach, co umożliwia ich przetwarzanie również za pomocą narzędzi systemu operacyjnego.
- Bazy z danymi z agregacji. Przechowują różne agregacje, zazwyczaj zgrupowane według nazwy instrumentu i przedziału czasowego. Bazy w pamięci aktualizują swoje dane przy każdym przychodzącym komunikacie, a historyczne przechowują wcześniej obliczone dane w celu przyspieszenia dostępu do danych historycznych.
- Na koniec, procesy gateway, obsługujących aplikacje i użytkowników. Q umożliwia pełną asynchroniczną obsługę przychodzących wiadomości, ich rozdzielanie do baz, kontrolę uprawnień itp. Zauważam, że wiadomości nie ograniczają się i najczęściej nie są wyrażeniami SQL, jak to bywa w innych bazach danych. Najczęściej wyrażenie SQL jest ukryte w specjalnej funkcji i konstruowane na podstawie parametrów żądanych przez użytkownika — następuje konwersja czasu, filtrowanie, dane są normalizowane (na przykład, cena akcji jest wyrównywana, jeśli była wypłata dywidend) itp.
Typowa architektura dla jednego typu danych:
Szybkość
Chociaż Q jest językiem interpretowanym, jest jednocześnie językiem wektorowym. Oznacza to, że wiele wbudowanych funkcji, w szczególności arytmetycznych, przyjmuje argumenty w dowolnej formie — liczby, wektory, macierze, listy, a programista jest zobowiązany do realizacji programu jako operacji na tablicach. W takim języku, jeśli dodajesz dwa wektory po milionie elementów, nie ma już znaczenia, że język jest interpretowany, dodawanie będzie odbywało się za pomocą superoptymalizowanej funkcji binarnej. Ponieważ lwia część czasu w programach napisanych w Q poświęcona jest operacjom na tabelach, które wykorzystują te podstawowe funkcje wektorowe, otrzymujemy całkiem przyzwoitą prędkość działania, umożliwiającą przetwarzanie ogromnych ilości danych nawet w jednym procesie. To przypomina biblioteki matematyczne w Pythonie — choć sam Python jest dość wolny, posiada wiele znakomitych bibliotek, takich jak numpy, które pozwalają przetwarzać dane liczbowe z prędkością skompilowanego języka (swoją drogą, numpy ideologicznie jest bliskie Q).
Ponadto, w KX bardzo starannie podeszli do projektowania tabel oraz optymalizacji pracy z nimi. Po pierwsze, wspierane są różne rodzaje indeksów, które są dostępne dzięki wbudowanym funkcjom i mogą być stosowane nie tylko do kolumn tabel, lecz także do dowolnych wektorów — grupowanie, sortowanie, atrybut unikalności oraz specjalne grupowanie dla baz danych historycznych. Indeks nakłada się elementarnie i automatycznie dostosowuje przy dodawaniu elementów do kolumny/wektora. Indeksy z powodzeniem mogą być stosowane na kolumnach tabel zarówno w pamięci, jak i na dysku. W przypadku wykonywania zapytania QSQL indeksy są wykorzystywane automatycznie, jeśli jest to możliwe. Po drugie, praca z danymi historycznymi odbywa się za pomocą mechanizmu mapowania plików systemu operacyjnego (memory map). Duże tabele nigdy nie są ładowane do pamięci, zamiast tego potrzebne kolumny są bezpośrednio mapowane do pamięci, a naprawdę ładowana jest tylko ta ich część (w tym pomagają również indeksy), która jest niezbędna. Dla programisty nie ma różnicy, czy dane znajdują się w pamięci, czy nie, mechanizm pracy z mmap jest całkowicie ukryty w głębi Q.
KDB+ to nierelacyjna baza danych, tabele mogą zawierać dowolne dane, przy tym porządek wierszy w tabeli nie zmienia się przy dodawaniu nowych elementów i może oraz powinien być używany przy pisaniu zapytań. Ta cecha jest szczególnie potrzebna do pracy z szeregami czasowymi (dane giełdowe, telemetryczne, logi zdarzeń), ponieważ jeśli dane są posortowane według czasu, użytkownik nie musi stosować żadnych sztuczek SQL, aby znaleźć w tabeli pierwszy lub ostatni wiersz w czasie lub N wierszy, określić, który wiersz następuje po N-tym wierszu itp. Jeszcze bardziej ułatwiają się łączenia tabel, na przykład dla 16000 transakcji VOD.L (Vodafone) znalezienie ostatniej wyceny w tabeli liczącej 500 milionów elementów zajmuje około sekundy na dysku i dziesiątki milisekund w pamięci.
Przykład łączenia według czasu — tabela quote jest mapowana do pamięci, dlatego nie ma potrzeby wskazywania VOD.L w warunku where, niejawnie używane są indeks na kolumnie sym oraz fakt, że dane są posortowane według czasu. Prawie wszystkie połączenia w Q to standardowe funkcje, a nie część wyrażenia select:
1. aj[`sym`time;select from trade where date=2019.03.26, sym=`VOD.L;select from quote where date=2019.03.26]
Na koniec warto zaznaczyć, że inżynierowie w KX, zaczynając od samego Artura Whitney'a, rzeczywiście obsesyjnie dążą do efektywności i podejmują wszelkie starania, aby maksymalnie wykorzystać standardowe funkcje Q oraz zoptymalizować najczęstsze wzorce użycia.
Podsumowanie
KDB+ cieszy się popularnością wśród firm przede wszystkim dzięki swojej wyjątkowej wszechstronności — z powodzeniem pełni rolę zarówno bazy danych w pamięci, jak i bazy do przechowywania terabajtów historycznych danych oraz platformy do analizy danych. Dzięki temu, że przetwarzanie danych odbywa się bezpośrednio w bazie, osiągana jest wysoka prędkość działania i oszczędność zasobów. Pełnoprawny język programowania, zintegrowany z funkcjami bazy danych, pozwala na realizację całego stosu niezbędnych procesów na jednej platformie — od pozyskiwania danych po przetwarzanie zapytań użytkowników.
Dodatkowe informacje
Wady
Istotnym minusem KDB+/Q jest wysoki próg wejścia. Język ma dziwną składnię, a niektóre funkcje są silnie przeciążone (na przykład value ma około 11 wariantów użycia). Najważniejsze jest to, że wymaga radykalnie innego podejścia do pisania programów. W języku wektorowym należy cały czas myśleć w kategoriach transformacji tablic, a wszystkie pętle realizować za pomocą kilku wariantów funkcji map/reduce (zwanych przysłówkami w Q), nigdy nie próbować oszczędzać, zastępując operacje wektorowe atomowymi. Na przykład, aby znaleźć indeks N-tego wystąpienia elementu w tablicy, należy napisać:
1. (where element=vector)[N]
choć wygląda to przerażająco nieefektywnie w porównaniu do C/Java (= tworzy wektor boolowski, where zwraca indeksy prawdziwych elementów w nim). Jednak taka notacja sprawia, że sens wyrażenia jest bardziej zrozumiały, a używasz szybkich operacji wektorowych zamiast wolnych atomowych. Różnica koncepcyjna między językiem wektorowym a innymi jest porównywalna z różnicą między podejściem imperatywnym a funkcyjnym w programowaniu, i należy się na to przygotować.
Niektórzy użytkownicy mogą być także niezadowoleni z QSQL. Chodzi o to, że jedynie przypomina on prawdziwy SQL. W rzeczywistości jest to jedynie interpreter wyrażeń podobnych do SQL, który nie wspiera optymalizacji zapytań. Użytkownik musi sam pisać optymalne zapytania, i to w Q, do czego wielu nie jest gotowych. Z drugiej strony, oczywiście, zawsze można samodzielnie napisać optymalne zapytanie, zamiast polegać na czarnej skrzynce-optimizatorze.
Kolejną zaletą książki o Q - Q For Mortals jest to, że jest dostępna za darmo na , na której znajdziesz również wiele innych przydatnych materiałów.
Kolejnym dużym minusem jest koszt licencji. To dziesiątki tysięcy dolarów rocznie za jeden CPU. Tylko duże firmy mogą pozwolić sobie na takie wydatki. Ostatnio KX wprowadziła bardziej elastyczną politykę licencyjną, oferując możliwość płacenia tylko za czas użytkowania lub wynajmu KDB+ w chmurach Google i Amazon. KX oferuje także do pobrania (32-bitową wersję lub 64-bitową na życzenie).
Konkurenci
Istnieje wiele specjalistycznych baz danych opartych na podobnych zasadach — kolumnowe, in-memory, zaprojektowane pod kątem bardzo dużych objętości danych. Problem polega na tym, że są to właśnie specjalistyczne bazy danych. Jaskrawym przykładem jest Clickhouse. Ta baza danych ma bardzo podobny do KDB+ sposób przechowywania danych na dysku i budowy indeksów; niektóre zapytania wykonuje szybciej niż KDB+, choć nieznacznie. Jednak nawet jako baza danych, Clickhouse jest bardziej specjalistyczna niż KDB+ — web analytics vs ogólne szereg czasowy (ta różnica jest bardzo ważna — na przykład w Clickhouse nie ma możliwości wykorzystania uporządkowania zapisów). Jednak najważniejsze, że Clickhouse nie ma wszechstronności KDB+, języka, który umożliwia przetwarzanie danych bezpośrednio w bazie, a nie wcześniejsze wczytywanie ich do osobnej aplikacji, tworzenie dowolnych wyrażeń SQL, stosowanie dowolnych funkcji w zapytaniu, tworzenie procesów niezwiązanych z realizacją funkcji bazy historycznej. Dlatego trudno porównywać KDB+ z innymi bazami; mogą być lepsze w poszczególnych scenariuszach użycia lub po prostu lepsze, jeśli chodzi o zadania klasycznych baz danych, ale nie znam innego równie efektywnego i wszechstronnego narzędzia do przetwarzania danych czasowych.
Integracja z Pythonem
Aby uprościć pracę z KDB+ dla osób, które nie są zaznajomione z technologią, KX stworzyło biblioteki do ścisłej integracji z Pythonem w ramach jednego procesu. Można zarówno wywołać dowolną funkcję Pythona z Q, jak i odwrotnie — wywołać dowolną funkcję Q z Pythona (w szczególności wyrażenia QSQL). Biblioteki konwertują dane z formatu jednego języka na format drugiego, gdy jest to konieczne (dla efektywności nie zawsze). Ostatecznie Q i Python żyją w tak bliskim symbiozie, że granice między nimi zacierają się. W efekcie programista z jednej strony ma pełny dostęp do wielu użytecznych bibliotek Pythona, a z drugiej strony, otrzymuje zintegrowaną z Pythonem szybką bazę do pracy z wielkimi danymi, co jest szczególnie przydatne dla osób zajmujących się uczeniem maszynowym lub modelowaniem.
Praca z Q w Pythonie:
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')
Linki
Strona internetowa firmy —
Strona dla programistów —
Książka Q For Mortals (w języku angielskim) —
Artykuły na temat zastosowań KDB+/Q od pracowników kx —
Źródło: habr.com
