KDB+, en produkt frĂ„n företaget Ă€r en vĂ€lkĂ€nd, extremt snabb kolumndatabas avsedd för lagring av tidsserier och analytiska berĂ€kningar baserat pĂ„ dem. Den har ursprungligen haft (och har fortfarande) stor popularitet inom finanssektorn â alla topp-10 investeringsbanker och mĂ„nga kĂ€nda hedgefonder, börser och andra organisationer anvĂ€nder den. PĂ„ senare tid har KX beslutat att utöka sin kundbas och erbjuder nu lösningar Ă€ven inom andra omrĂ„den dĂ€r det finns stora mĂ€ngder data som Ă€r ordnade tidsmĂ€ssigt eller pĂ„ annat sĂ€tt â telekom, bioinformatik, produktion osv. De har ocksĂ„ blivit partner till Aston Martin Red Bull Racing-teamet inom Formel 1, dĂ€r de hjĂ€lper till att samla in och bearbeta data frĂ„n bilarnas sensorer och analysera tester i vindtunneln. I den hĂ€r artikeln vill jag förklara vilka egenskaper KDB+ har som gör den supersnabb, varför företag Ă€r villiga att spendera stora summor pĂ„ den, och varför det faktiskt inte Ă€r en databas.
Â

Â
I den hĂ€r artikeln kommer jag att försöka förklara vad KDB+ Ă€r, vilka möjligheter och begrĂ€nsningar den har, samt vilken nytta den erbjuder företag som vill bearbeta stora datavolymer. Jag kommer inte att gĂ„ in pĂ„ detaljerna för hur KDB+ implementeras och detaljerna för dess programmeringssprĂ„k Q. BĂ„da dessa Ă€mnen Ă€r mycket omfattande och förtjĂ€nar egna artiklar. Mycket information om dessa Ă€mnen kan hittas pĂ„ webbplatsen code.kx.com, inklusive en bok om Q â Q For Mortals (se lĂ€nken nedan).
NÄgra termer
- In-memory databas. En databas som lagrar data i RAM för att snabba upp Ätkomsten. Fördelarna med en sÄdan databas Àr uppenbara, medan nackdelarna Àr risken för dataloss, samt behovet av mycket minne pÄ servern.
- Kolumn databas. En databas dÀr data lagras kolumnvis istÀllet för radvis. Huvudfördelen med en sÄdan databas Àr att data frÄn en kolumn lagras tillsammans pÄ disk och i minnet, vilket avsevÀrt snabbar upp Ätkomsten. Det Àr inte nödvÀndigt att ladda kolumner som inte anvÀnds i frÄgan. Huvudnackdelen Àr att det Àr svÄrt att modifiera och ta bort poster.
- Tidsserier. Data med datu- eller tidskolumn. Vanligtvis Ă€r ordning i tid viktig för sĂ„dana data, sĂ„ att man enkelt kan avgöra vilken post som föregĂ„r eller följer den aktuella, eller för att tillĂ€mpa funktioner vars resultat beror pĂ„ ordningen pĂ„ posterna. Klassiska databaser Ă€r uppbyggda pĂ„ helt andra principer â presenterar en uppsĂ€ttning poster som en mĂ€ngd, dĂ€r ordningen pĂ„ posterna i princip inte Ă€r definierad.
- Vektor. I KDB+-sammanhang Àr det en lista av element av en och samma atomÀra typ, till exempel nummer. Med andra ord, en array av element. Arrays, till skillnad frÄn listor, kan lagras kompakt och bearbetas med hjÀlp av vektorbaserade processorinstruktioner.
Â
Historisk översikt
Företaget KX grundades 1993 av Arthur Whitney, som tidigare arbetat pĂ„ Morgan Stanley med sprĂ„ket A+, som var en efterföljare till APL â ett mycket originellt och populĂ€rt sprĂ„k inom finansvĂ€rlden. SjĂ€lvklart fortsatte Arthur i KX med samma anda och skapade det vektorfunktionella sprĂ„ket K, styrt av idĂ©erna om radikal minimalism. Program skrivna i K ser ut som en kaotisk uppsĂ€ttning skiljetecken och speciella symboler, dĂ€r betydelsen av tecken och funktioner beror pĂ„ sammanhanget, och varje operation har en mycket djupare innebörd Ă€n vad man vanligtvis ser i klassiska programmeringssprĂ„k. Tack vare detta tar ett K-program minimal plats â nĂ„gra rader kan ersĂ€tta sidor av text i lĂ„ngrandiga sprĂ„k som Java â och Ă€r en superkoncentrerad implementering av algoritmen.
Â
En funktion i K som implementerar största delen av LL1-parsergeneratorn enligt en given grammatik:
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),"]";""]]}Â Â
 Denna filosofi om extrem effektivitet med minimala rörelser har Arthur ocksĂ„ förverkligat i KDB+, som lanserades 2003 (nu tror jag att det Ă€r klart varifrĂ„n bokstaven K i namnet kommer) och Ă€r inget annat Ă€n en tolk av den fjĂ€rde versionen av K-sprĂ„ket. OvanpĂ„ K har en mer anvĂ€ndarvĂ€nlig version av K lagts till, kallad Q. I Q har Ă€ven stöd för en specifik SQL-dialekt â QSQL, samt stöd för tabeller som datatyp, verktyg för att hantera tabeller i minnet och pĂ„ disk osv. lagts till.
Â
SĂ„ledes, sett ur ett anvĂ€ndarperspektiv, Ă€r KDB+ helt enkelt en tolk för Q-sprĂ„ket med stöd för tabeller och SQL-liknande uttryck i LINQ-stil frĂ„n C#. Detta Ă€r den viktigaste skillnaden mellan KDB+ och andra databaser och dess frĂ€msta konkurrensfördel som ofta förbises. Det Ă€r inte en databas + ett hjĂ€lp-sprĂ„k, utan ett fullvĂ€rdigt kraftfullt programmeringssprĂ„k + inbyggt stöd för databasfunktioner. Denna skillnad kommer att spela en avgörande roll nĂ€r man rĂ€knar upp alla fördelar med KDB+. Till exempelâŠ
Â
Dimensions
Enligt moderna standarder har KDB+ en mikroskopisk storlek. Det Ă€r i bokstavlig mening en körbar fil pĂ„ mindre Ă€n en megabyte och en liten textfil med vissa systemfunktioner. Faktiskt â mindre Ă€n en megabyte och för detta program betalar företag tiotusentals dollar per Ă„r för en processor pĂ„ servern.
- En sĂ„dan storlek gör att KDB+ fungerar utmĂ€rkt pĂ„ vilken hĂ„rdvara som helst â frĂ„n mikrodatorn Pi till servrar med terabyte av minne. Detta pĂ„verkar inte funktionaliteten, snarare startar Q omedelbart, vilket ocksĂ„ gör att det kan anvĂ€ndas som ett skriptsprĂ„k.
- Med en sÄdan storlek ryms Q-tolken helt i processorens cache, vilket snabbar upp körningen av program.
- Med en sÄdan storlek pÄ den körbara filen tar Q-processen försvinnande lite minnesutrymme, och de kan startas i hundratals. Samtidigt kan Q vid behov hantera tiotals eller hundratals gigabyte minne inom en och samma process.
Allsidighet
Q passar utmÀrkt för en mÀngd olika uppgifter. Q-processen kan fungera som en historisk databas och ge snabb tillgÄng till terabyte av information. Vi har till exempel Dussintals historiska databaser, dÀr en ospecificerad dag med data tar mer Àn 100 gigabyte. Trots detta, med rimliga begrÀnsningar, kommer en databasfrÄga att utföras inom tiotals till hundratals millisekunder. Generellt har vi en universell tidsgrÀns för anvÀndarförfrÄgningar pÄ 30 sekunder, och den utlöses mycket sÀllan.
Â
Med samma lĂ€tthet kan Q fungera som en in-memory databas. Att lĂ€gga till nya data i tabellerna i minnet sker sĂ„ snabbt att det begrĂ€nsande faktorn Ă€r anvĂ€ndarförfrĂ„gningar. Data i tabellerna lagras kolumnvis, vilket innebĂ€r att varje operation pĂ„ en kolumn utnyttjar processorns cache till max. DĂ€rtill har KX försökt implementera alla grundlĂ€ggande operationer, som aritmetiska, genom vektoriserade processorinstruktioner för att maximera deras hastighet. Q kan Ă€ven utföra uppgifter som inte Ă€r typiska för databaser â till exempel bearbeta strömmande data och berĂ€kna i "real tid" (med en fördröjning frĂ„n tiotals millisekunder till nĂ„gra sekunder beroende pĂ„ uppgiften) olika aggregatfunktioner för finansiella instrument över olika tidsintervall eller bygga en modell för hur en genomförd transaktion pĂ„verkar marknaden och genomföra profilering nĂ€stan omedelbart efter att den har genomförts. I sĂ„dana uppgifter bidrar oftast inte Q till den primĂ€ra tidsfördröjningen, utan behovet av att synkronisera data frĂ„n olika kĂ€llor. Den höga hastigheten uppnĂ„s tack vare att data och funktioner som behandlar dem finns i samma process, och bearbetningen begrĂ€nsas till att utföra nĂ„gra QSQL-uttryck och joins, som inte tolkas utan körs som binĂ€r kod.
Â
Slutligen kan man pÄ Q skriva vilket serviceprogram som helst. Till exempel Gateway-processer som automatiskt fördelar anvÀndarförfrÄgningar till rÀtt databaser och servrar. Utvecklaren har full frihet att implementera vilken algoritm som helst för lastbalansering, prioritering, felhantering, ÄtkomstrÀttigheter, kvoter och egentligen vad som helst som önskas. Huvudproblemet hÀr Àr att man mÄste implementera allt detta sjÀlv.
Â
Som exempel kommer jag att lista vilka typer av processer vi har. Alla anvÀnds aktivt och fungerar tillsammans, vilket sammanför tiotals olika databaser, behandlar data frÄn mÄnga kÀllor och betjÀnar hundratals anvÀndare och applikationer.
- Kopplare (feedhandler) till datakÀllor. Dessa processer anvÀnder vanligtvis externa bibliotek som laddas in i Q. C-grÀnssnittet i Q Àr mycket enkelt och gör det lÀtt att skapa proxyfunktioner för vilket C/C++-bibliotek som helst. Q Àr tillrÀckligt snabbt för att hantera till exempel bearbetningen av en ström av FIX-meddelanden frÄn alla europeiska börser samtidigt.
- Datadistributörer (tickerplant), som fungerar som ett mellanled mellan kopplarna och konsumenterna. Samtidigt skriver de indata i en speciell binÀr logg, vilket ger konsumenterna stabilitet mot förlust av anslutningar eller omstarter.
- In-memory databaser (rdb). Dessa databaser ger maximalt snabb Ätkomst till fÀrska rÄdata genom att lagra dem i minnet. I allmÀnhet samlar de in data i tabeller under dagen och nollstÀller dem pÄ natten.
- Persistenta databaser (pdb). Dessa databaser sÀkerstÀller att dagens data sparas i en historisk databas. Vanligtvis, till skillnad frÄn rdb, lagrar de inte data i minnet, utan anvÀnder en speciell cache pÄ disken under dagen och kopierar data till den historiska databasen vid midnatt.
- Historiska databaser (hdb). Dessa databaser ger Ätkomst till data frÄn tidigare dagar, mÄnader och Är. Deras storlek (i dagar) Àr endast begrÀnsad av hÄrddiskens kapacitet. Data kan placeras var som helst, inklusive pÄ olika diskar för att pÄskynda Ätkomsten. Det finns möjlighet att komprimera data med hjÀlp av flera algoritmer att vÀlja mellan. Databasstrukturen Àr vÀl dokumenterad och enkel, data lagras kolumnvis i vanliga filer sÄ att de ocksÄ kan bearbetas med hjÀlp av operativsystemets verktyg.
- Databaser med aggregerad information. De lagrar olika aggregationer, vanligtvis grupperade efter instrumentets namn och tidsintervall. In-memory databaser uppdaterar sitt tillstÄnd vid varje inkommande meddelande, medan historiska databaser lagrar förberÀknade data för att pÄskynda Ätkomsten till historiska data.
- Slutligen, gateway processer, för att stödja applikationer och anvĂ€ndare. Q möjliggör helt asynkron hantering av inkommande meddelanden, fördelning av dessa till databaser, Ă„tkomstkontroll och sĂ„ vidare. Jag vill pĂ„peka att meddelandena inte Ă€r begrĂ€nsade och oftast inte Ă€r SQL-uttalanden, som det Ă€r fallet i andra databaser. Oftast göms SQL-uttalandet i en specialfunktion och konstrueras baserat pĂ„ de parametrar som anvĂ€ndaren begĂ€r â tidskonvertering genomförs, filtrering utförs, data normaliseras (till exempel justeras aktiepriser om utdelningar har betalats) och sĂ„ vidare.
Typisk arkitektur för en datatyp:

Hastighet
Ăven om Q Ă€r ett tolkande sprĂ„k, Ă€r det ocksĂ„ ett vektoriserat sprĂ„k. Det innebĂ€r att mĂ„nga inbyggda funktioner, sĂ€rskilt aritmetiska, accepterar argument i vilken form som helst â tal, vektorer, matriser, listor, och det förvĂ€ntas av programmeraren att programmet implementeras som operationer pĂ„ arrayer. I ett sĂ„dant sprĂ„k, om du lĂ€gger ihop tvĂ„ vektorer med en miljon element, spelar det ingen roll att sprĂ„ket Ă€r tolkande; additionen kommer att utföras med en superoptimerad binĂ€r funktion. Eftersom en stor del av tiden i Q-program spenderas pĂ„ operationer med tabeller som anvĂ€nder dessa grundlĂ€ggande vektoriserade funktioner, fĂ„r vi en ganska bra hastighet som möjliggör hantering av enorma datamĂ€ngder Ă€ven i en och samma process. Det liknar matematikbibliotek i Python â Ă€ven om Python som sprĂ„k Ă€r ganska lĂ„ngsamt, finns det mĂ„nga utmĂ€rkta bibliotek som numpy, vilka gör det möjligt att bearbeta numeriska data med hastigheten hos ett kompilatorbaserat sprĂ„k (för övrigt Ă€r numpy ideologiskt nĂ€ra Q).
Â
Dessutom har KX lagt stor vikt vid designen av tabeller och optimering av dem. För det första stöds flera typer av index, som kan anvĂ€ndas med inbyggda funktioner och som kan tillĂ€mpas inte bara pĂ„ kolumner i tabeller utan ocksĂ„ pĂ„ alla vektorer â gruppering, sortering, unika attribut och speciell gruppering för historiska databaser. Index appliceras enkelt och justeras automatiskt vid tillĂ€gg av element i kolumnen/vektorn. Index kan framgĂ„ngsrikt tillĂ€mpas pĂ„ kolumner i tabeller bĂ„de i minnet och pĂ„ disken. Vid utförande av en QSQL-förfrĂ„gan anvĂ€nds index automatiskt om sĂ„ Ă€r möjligt. För det andra hanteras historiska data genom en mekanism för avbildning av OS-filer (memory map). Stora tabeller laddas aldrig helt in i minnet, utan nödvĂ€ndiga kolumner avbildas direkt i minnet, och endast den del som behövs laddas faktiskt (Ă€ven index hjĂ€lper till med det). För programmeraren spelar det ingen roll om data finns i minnet eller inte; mekanismen för arbete med mmap döljs helt inuti Q.
Â
KDB+ Ă€r en icke-relationell databas, dĂ€r tabeller kan innehĂ„lla godtyckliga data. Ordningen pĂ„ raderna i tabellen förĂ€ndras inte vid tillĂ€gg av nya element och kan och bör anvĂ€ndas vid skrivning av förfrĂ„gningar. Denna funktion Ă€r oerhört viktig för arbete med tidsserier (data frĂ„n börser, telemetri, hĂ€ndelseloggar), eftersom om data Ă€r sorterade efter tid, sĂ„ behöver anvĂ€ndaren inte tillĂ€mpa nĂ„gra SQL-tricks för att hitta den första eller sista raden i tiden i tabellen eller N rader, eller avgöra vilken rad som följer efter den N:e raden, och sĂ„ vidare. Ănnu enklare blir join-avfrĂ„gningar, till exempel att hitta den senaste kursen för 16000 affĂ€rer i VOD.L (Vodafone) i en tabell med 500 miljoner element tar cirka en sekund pĂ„ disken och ett tiotal millisekunder i minnet.
Â
Ett exempel pĂ„ en tidsjoin â quote-tabellen avbildas i minnet, sĂ„ det finns ingen anledning att ange VOD.L i where, indexet pĂ„ sym-kolumnen och det faktum att data Ă€r sorterade efter tid anvĂ€nds implicit. NĂ€stan alla joins i Q Ă€r vanliga funktioner, snarare Ă€n en del av select-uttrycket:
1. aj[`sym`time;select from trade where date=2019.03.26, sym=`VOD.L;select from quote where date=2019.03.26]Â Â
Slutligen Àr det vÀrt att nÀmna att ingenjörerna pÄ KX, ledda av Arthur Whitney, verkligen Àr besatta av effektivitet och gör allt för att maximera standardfunktionerna i Q och optimera de vanligaste anvÀndningsmönstren.
Â
Resultat
KDB+ Ă€r populĂ€r bland företag frĂ€mst pĂ„ grund av sin exceptionella mĂ„ngsidighet â den fungerar lika bra som en in-memory databas, som en databas för lagring av terabyte av historiska data, och som en plattform för dataanalys. Eftersom databehandling sker direkt i databasen uppnĂ„s hög hastighet och resursbesparing. Ett fullstĂ€ndigt programmeringssprĂ„k, integrerat med databasfunktioner, gör det möjligt att implementera hela det nödvĂ€ndiga processstacken pĂ„ en plattform â frĂ„n datainsamling till bearbetning av anvĂ€ndarförfrĂ„gningar.
Â
Ytterligare information
Nackdelar
En betydande nackdel med KDB+/Q Àr den höga inlÀrningströskeln. SprÄket har en udda syntax, vissa funktioner Àr kraftigt överbelastade (value, till exempel, har cirka 11 anvÀndningsvarianter). Viktigast av allt, det krÀver en radikalt annan instÀllning till programmeringsskrivande. I det vektorbaserade sprÄket mÄste man alltid tÀnka i termer av arrayomvandlingar, alla loopar implementeras genom olika varianter av funktioner map/reduce (som kallas adverbs i Q), och man fÄr aldrig försöka spara genom att ersÀtta vektoroperationer med atomÀra. Till exempel, för att hitta indexet för den N:e förekomsten av ett element i en array bör man skriva:
1. (where element=vector)[N]Â Â
Àven om detta verkar fruktansvÀrt ineffektivt i termer av C/Java (skapar en boolesk vektor, dÀr where returnerar indexen för true element i den). Men sÄdan notation gör betydelsen av uttrycket mer begriplig och du anvÀnder snabba vektoroperationer istÀllet för lÄngsamma atomÀra. Den konceptuella skillnaden mellan vektorbaserade sprÄk och andra liknar skillnaden mellan imperativ och funktionell programmering, och man mÄste vara beredd pÄ detta.
Â
Vissa anvĂ€ndare Ă€r ocksĂ„ missnöjda med QSQL. Problemet Ă€r att det bara liknar riktig SQL. I verkligheten Ă€r det bara en tolk för SQL-liknande uttryck som inte stödjer optimering av frĂ„gor. AnvĂ€ndaren mĂ„ste sjĂ€lv skriva optimala frĂ„gor, vilket mĂ„nga inte Ă€r redo för. Ă
andra sidan kan man alltid sjÀlv skriva en optimal frÄga istÀllet för att förlita sig pÄ en svart lÄda-optimerare.
Â
Som en fördel Ă€r boken om Q â Q For Mortals tillgĂ€nglig gratis pĂ„ , dĂ€r det ocksĂ„ finns mĂ„nga andra nyttiga material.
Â
En annan stor nackdel Àr kostnaden för licensen. Det handlar om tiotusentals dollar per Är för en CPU. Endast stora företag har rÄd med sÄdana utgifter. Nyligen har KX gjort sin licenspolicy mer flexibel och ger möjlighet att betala endast för anvÀndningstid eller hyra KDB+ i molnen frÄn Google och Amazon. Dessutom erbjuder KX för nedladdning (32-bitarsversion eller 64-bitarsversion pÄ begÀran).
Â
Konkurrenter
Det finns ganska mĂ„nga specialiserade databaser som bygger pĂ„ liknande principer â kolumnbaserade, in-memory, fokuserade pĂ„ mycket stora datavolymer. Problemet Ă€r att det just Ă€r specialiserade databaser. Ett tydligt exempel Ă€r Clickhouse. Denna databas har en lagringsprincip pĂ„ disk och indexbyggande som liknar KDB+, och vissa förfrĂ„gningar utför den snabbare Ă€n KDB+, Ă€ven om det inte Ă€r vĂ€sentligt. Men Ă€ven som databas Ă€r Clickhouse mer specialiserad Ă€n KDB+ â webbanalys mot godtyckliga tidsserier (denna skillnad Ă€r mycket viktig â pĂ„ grund av den finns det till exempel ingen möjlighet att anvĂ€nda ordningen av poster i Clickhouse). Men viktigast av allt, Clickhouse saknar den allsidighet som KDB+ har, ett sprĂ„k som skulle tillĂ„ta att bearbeta data direkt i databasen, istĂ€llet för att först ladda dem i en separat applikation, bygga godtyckliga SQL-uttryck, tillĂ€mpa godtyckliga funktioner i förfrĂ„gningar, skapa processer som inte Ă€r relaterade till utförandet av historiska funktionsanrop. DĂ€rför Ă€r det svĂ„rt att jĂ€mföra KDB+ med andra databaser, de kan vara bĂ€ttre i specifika anvĂ€ndningsscenarier eller helt enkelt bĂ€ttre nĂ€r det gĂ€ller traditionella databasanvĂ€ndningar, men jag kĂ€nner inte till nĂ„got annat lika effektivt och allsidigt verktyg för bearbetning av tidsdata.
Â
Integration med Python
För att förenkla arbetet med KDB+ för personer som inte Ă€r bekanta med teknologin har KX skapat bibliotek för nĂ€ra integration med Python inom samma process. Man kan anropa vilken python-funktion som helst frĂ„n Q, och vice versa â anropa vilken Q-funktion som helst frĂ„n Python (sĂ€rskilt QSQL-uttryck). Biblioteken konverterar vid behov (för effektivitetens skull, inte alltid) data frĂ„n formatet av det ena sprĂ„ket till formatet av det andra. Som ett resultat lever Q och Python i ett sĂ„dant nĂ€ra symbios att grĂ€nserna mellan dem suddas ut. Som ett resultat har programmeraren, Ă„ ena sidan, full tillgĂ„ng till mĂ„nga anvĂ€ndbara Python-bibliotek, och Ă„ andra sidan fĂ„r han en integrerad snabb databas för att arbeta med stora datamĂ€ngder, vilket Ă€r sĂ€rskilt anvĂ€ndbart för dem som sysslar med maskininlĂ€rning eller modellering.
Â
Arbeta med Q i 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')Â Â
LĂ€nkar
Företagets webbplats â
Utvecklarwebbplats â
Boken Q For Mortals (pĂ„ engelska) â
Artiklar om tillĂ€mpningar av KDB+/Q frĂ„n anstĂ€llda pĂ„ kx â
KĂ€lla: habr.com
