Banco de dados KDB +: do setor financeiro à fórmula 1

O KDB +, um produto KX , é um banco de dados de colunas conhecido por círculo estreito e extremamente rápido, projetado para armazenar séries temporais e cálculos analíticos com base neles. Inicialmente, ele gozou (e goza) de grande popularidade no setor financeiro - é usado por todos os 10 principais bancos de investimento e por muitos hedge funds, bolsas e outras organizações bem conhecidas. Recentemente, a KX decidiu expandir sua base de clientes e agora oferece soluções em outras áreas onde há uma grande quantidade de dados classificados por tempo ou de outra maneira - telecomunicações, bioinformática, produção, etc. Em particular, eles se tornaram um parceiro da equipe da Aston Martin Red Bull Racing na Fórmula 1, onde ajudam a coletar e processar dados de sensores de automóveis e analisar testes em um túnel de vento. Neste artigo, quero dizer quais recursos do KDB + o tornam superprodutivo, por que as empresas estão dispostas a gastar muito dinheiro com ele e, finalmente, por que esse não é realmente um banco de dados.



Neste artigo, tentarei dizer em geral o que é o KDB +, quais recursos e limitações ele possui, qual é o seu benefício para as empresas que desejam processar grandes volumes de dados. Não entrarei nos detalhes da implementação do KDB + e nos detalhes de sua linguagem de programação Q. Ambos os tópicos são muito extensos e merecem artigos separados. Muitas informações sobre esses tópicos podem ser encontradas em code.kx.com, incluindo um livro sobre o Q-Q For Mortals (veja o link abaixo).

Alguns termos


  • Banco de dados na memória. Um banco de dados que armazena dados na RAM para acesso mais rápido. As vantagens desse banco de dados são compreensíveis e as desvantagens são a possibilidade de perda de dados, a necessidade de ter muita memória no servidor.
  • Banco de dados da coluna. Um banco de dados em que os dados são armazenados em série, não registrados por registro. A principal vantagem desse banco de dados é que os dados de uma coluna são armazenados juntos no disco e na memória, o que acelera bastante o acesso a eles. Não há necessidade de carregar colunas que não são usadas na solicitação. A principal desvantagem é que é difícil modificar e excluir registros.
  • Séries temporais. Dados com uma coluna como data ou hora. Como regra, a ordem no tempo é importante para esses dados, para que você possa determinar facilmente qual registro precede ou segue a corrente ou aplicar funções cujo resultado depende da ordem dos registros. Os bancos de dados clássicos são criados com base em um princípio completamente diferente - representando um conjunto de registros como um conjunto, em que a ordem dos registros não é definida em princípio.
  • Vector. No contexto, o KDB + é uma lista de elementos do mesmo tipo atômico, por exemplo, números. Em outras palavras, uma matriz de elementos. As matrizes, ao contrário das listas, podem ser armazenadas de forma compacta e processadas usando as instruções do processador vetorial.

Antecedentes históricos


O KX foi fundado em 1993 por Arthur Whitney, que anteriormente trabalhou no Morgan Stanley Bank no A +, o sucessor do APL, uma linguagem muito original e popular no mundo financeiro. Obviamente, no KX, Arthur continuou com o mesmo espírito e criou a linguagem funcional do vetor K, guiada pelas idéias do minimalismo radical. Os programas K parecem um conjunto bagunçado de sinais de pontuação e caracteres especiais, o significado de caracteres e funções depende do contexto e cada operação possui muito mais significado do que nas linguagens de programação comuns. Devido a isso, o programa K ocupa um espaço mínimo - várias linhas podem substituir as páginas de texto de uma linguagem detalhada como Java - e é uma implementação super concentrada do algoritmo.

Uma função em K que implementa a maioria do gerador de analisador LL1 de acordo com uma dada gramática:

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;"(",]}({$[".sC"~4#x;6_-2_x;x]}'pp'x);'`pp];  6.   $[@r;r;($[1<#r;".s.";""],$*r),$[1<#r;"[",(";"/:1_r),"]";""]]} 

Arthur também incorporou essa filosofia de extrema eficiência com um mínimo de movimentos corporais no KDB +, que apareceu em 2003 (acho que agora está claro de onde vem a letra K) e não há nada além de um intérprete da quarta versão da linguagem K. Uma versão mais agradável aos olhos do usuário é adicionada a K K, com o nome Q. Q também adiciona suporte para um dialeto SQL específico - QSQL, e no intérprete - suporte para tabelas como um tipo de dados do sistema, ferramentas para trabalhar com tabelas na memória e no disco, etc.

Portanto, do ponto de vista do usuário, o KDB + é apenas um intérprete Q com suporte para tabelas e expressões no estilo LINQ do tipo SQL do C #. Essa é a diferença mais importante entre o KDB + e outros bancos de dados e sua principal vantagem competitiva, que geralmente é negligenciada. Este não é um banco de dados + uma linguagem auxiliar que está desabilitada, mas uma poderosa linguagem de programação completa + suporte interno para funções de banco de dados. Essa diferença terá um papel decisivo na listagem de todos os benefícios do KDB +. Por exemplo ...

Tamanho


Pelos padrões modernos, o KDB + é apenas um tamanho microscópico. Este é literalmente um arquivo executável menor que um megabyte e um pequeno arquivo de texto com algumas funções do sistema. Na verdade - menos de um megabyte e, para esse programa, as empresas pagam dezenas de milhares de dólares por ano por um processador no servidor.

  • Esse tamanho permite que o KDB + se sinta bem em qualquer hardware - do microcomputador Pi aos servidores com terabytes de memória. Isso não afeta a funcionalidade de nenhuma maneira; além disso, o Q é iniciado instantaneamente, o que permite que ele seja usado inclusive como uma linguagem de script.
  • Com esse tamanho, o intérprete Q é completamente colocado no cache do processador, o que acelera a execução dos programas.
  • Com esse tamanho do arquivo executável, o processo Q ocupa um espaço de memória insignificante; você pode executá-los em centenas. Ao mesmo tempo, se necessário, o Q pode operar com dezenas ou centenas de gigabytes de memória em um processo.

Versatilidade


Q é perfeito para uma variedade de tarefas. O processo Q pode servir como um banco de dados histórico e fornecer acesso rápido a terabytes de informações. Por exemplo, temos dezenas de bancos de dados históricos, em alguns dos quais um dia não compactado de dados leva mais de 100 gigabytes. No entanto, com restrições razoáveis, a consulta ao banco de dados será executada em dezenas a centenas de milissegundos. Em geral, temos um tempo limite universal para solicitações de usuários - 30 segundos - e isso funciona muito raramente.

Com a mesma facilidade, Q pode ser um banco de dados na memória. Adicionar novos dados a tabelas na memória é tão rápido que as consultas do usuário são um fator limitante. Os dados nas tabelas são armazenados em colunas, o que significa que qualquer operação na coluna utilizará o cache do processador na capacidade total. Além disso, o KX tentou implementar todas as operações básicas, como a aritmética, através de instruções do processador vetorial, maximizando sua velocidade. O Q pode executar tarefas que não são características dos bancos de dados - por exemplo, processar dados de fluxo contínuo e calcular em “tempo real” (com um atraso de dezenas de milissegundos a vários segundos, dependendo da tarefa) várias funções agregadas para instrumentos financeiros por diferentes intervalos de tempo ou criar um modelo do impacto da perfeita transações ao mercado e realizar seus perfis quase imediatamente após sua conclusão. Nesses problemas, na maioria das vezes o atraso principal não é Q, mas a necessidade de sincronizar dados de diferentes fontes. A alta velocidade é alcançada devido ao fato de que os dados e funções que os processam estão no mesmo processo e o processamento é reduzido à execução de várias expressões e junções QSQL que não são interpretadas, mas são executadas em código binário.

Por fim, qualquer processo de serviço também pode ser escrito em Q. Por exemplo, processos de gateway que distribuem automaticamente solicitações de usuário para os bancos de dados e servidores necessários. O programador tem total liberdade para implementar qualquer algoritmo para equilibrar, priorizar, tolerância a falhas, direitos de acesso, cotas e geralmente o que seu coração deseja. O principal problema aqui é que você deve implementar tudo isso sozinho.

Por exemplo, listarei quais tipos de processos temos. Todos eles são usados ​​ativamente e trabalham juntos, combinando dezenas de bancos de dados diferentes, processando dados de várias fontes e atendendo a centenas de usuários e aplicativos.

  • Conectores (manipulador de feeds) para fontes de dados. Esses processos geralmente usam bibliotecas externas carregadas no Q. A interface C no Q é extremamente simples e permite criar facilmente funções de proxy para qualquer biblioteca C / C ++. Q é rápido o suficiente para manipular, por exemplo, o processamento do fluxo de mensagens FIX de todas as bolsas de valores europeias simultaneamente.
  • Distribuidores Tickerplant, que servem como um elo intermediário entre conectores e consumidores. Ao mesmo tempo, eles gravam dados recebidos em um log binário especial, fornecendo resistência para os consumidores perderem ou reiniciarem a conexão.
  • Banco de dados na memória (rdb). Esses bancos de dados fornecem o acesso mais rápido a dados brutos e frescos, armazenando-os na memória. Como regra, eles acumulam dados em tabelas durante o dia e os zeram à noite.
  • Persistir banco de dados (pdb). Esses bancos de dados fornecem armazenamento de dados hoje no banco de dados histórico. Como regra, diferentemente do rdb, eles não armazenam dados na memória, mas usam um cache especial no disco por um dia e copiam os dados à meia-noite no banco de dados histórico.
  • Bases históricas (hdb). Esses bancos de dados fornecem acesso aos dados para dias, meses e anos anteriores. Seu tamanho (em dias) é limitado apenas pelo tamanho dos discos rígidos. Os dados podem ser localizados em qualquer lugar, principalmente em discos diferentes, para acesso mais rápido. É possível compactar dados usando vários algoritmos para escolher. A estrutura do banco de dados é bem documentada e simples, os dados são armazenados por unidade em arquivos comuns, para que possam ser processados, inclusive usando o sistema operacional.
  • Bancos de dados com informações agregadas. Várias agregações são armazenadas, geralmente com, agrupadas por nome do instrumento e intervalo de tempo. Os bancos de dados na memória atualizam seu status a cada mensagem recebida, e os históricos armazenam dados pré-calculados para acelerar o acesso aos dados históricos.
  • Por fim, processos de gateway que atendem a aplicativos e usuários. O Q permite implementar o processamento completamente assíncrono das mensagens recebidas, distribuindo-as entre os bancos de dados, verificando os direitos de acesso etc. Observo que as mensagens não são limitadas e, na maioria das vezes, não são instruções SQL, como é o caso em outros bancos de dados. Na maioria das vezes, a expressão SQL é oculta em uma função especial e é construída com base nos parâmetros solicitados pelo usuário - o tempo é convertido, filtrado, os dados são normalizados (por exemplo, o preço das ações é igualado se os dividendos forem pagos) etc.

Arquitetura típica para um tipo de dados:



Velocidade


Embora Q seja uma linguagem interpretada, é simultaneamente uma linguagem vetorial. Isso significa que muitas funções internas, em particular aritmética, aceitam argumentos de qualquer forma - números, vetores, matrizes, listas e o programador deve implementar o programa como operações em matrizes. Nesse idioma, se você adicionar dois vetores em um milhão de elementos, não importa mais que o idioma seja interpretado, a adição será realizada por uma função binária super-otimizada. Como a maior parte do tempo nos programas Q é gasta em operações com tabelas usando essas funções vetorizadas básicas, temos uma velocidade de produção bastante decente que nos permite processar uma enorme quantidade de dados, mesmo em um processo. Isso é semelhante às bibliotecas matemáticas em python - embora o próprio python seja uma linguagem muito lenta, ele possui muitas bibliotecas numpy excelentes que permitem processar dados numéricos na velocidade de uma linguagem compilada (a propósito, numpy é ideologicamente próximo de Q).

Além disso, o KX abordou com muito cuidado o design das tabelas e otimizou o trabalho com elas. Primeiramente, vários tipos de índices são suportados, que são suportados por funções internas e podem ser aplicados não apenas às colunas da tabela, mas também a quaisquer vetores - agrupamento, classificação, atributo de exclusividade e agrupamento especial para bancos de dados históricos. O índice é sobreposto elementarmente e é ajustado automaticamente ao adicionar elementos à coluna / vetor. Os índices também podem sobrepor colunas da tabela na memória e no disco. Ao executar uma consulta QSQL, os índices são usados ​​automaticamente, se possível. Em segundo lugar, o trabalho com dados históricos é feito através do mecanismo de mapeamento de arquivos do SO (mapa de memória). As tabelas grandes nunca são carregadas na memória; em vez disso, as colunas necessárias são mapeadas diretamente na memória e somente essa parte delas é realmente carregada (os índices também ajudam aqui). Não há diferença para o programador, quer os dados estejam na memória ou não, o mecanismo para trabalhar com o mmap está completamente oculto nas entranhas do Q.

O KDB + não é um banco de dados relacional, as tabelas podem conter dados arbitrários, enquanto a ordem das linhas na tabela não muda quando novos elementos são adicionados e pode e deve ser usada ao escrever consultas. Esse recurso é necessário com urgência para trabalhar com séries temporais (dados de trocas, telemetria, logs de eventos), porque se os dados são classificados por tempo, o usuário não precisa usar nenhum truque SQL para encontrar a primeira ou a última linha ou N linhas na tabela , determine qual linha segue a enésima linha etc. Junções de tabelas são ainda mais simplificadas, por exemplo, encontrando para 16.000 transações VOD.L (Vodafone) a última cotação em uma tabela de 500 milhões de elementos que leva cerca de um segundo no disco e uma dúzia de milissegundos na memória.

Um exemplo de junção de tempo é que a tabela de cotações é mapeada para a memória; portanto, não há necessidade de especificar VOD.L em que local, o índice na coluna sym é usado implicitamente e o fato de os dados serem classificados por tempo. Quase todas as junções em Q são funções comuns, não fazem parte da instrução select:

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

Finalmente, vale a pena notar que os engenheiros da KX, começando com o próprio Arthur Whitney, são realmente obcecados por eficiência e estão fazendo todos os esforços para tirar o máximo proveito das funções Q padrão e otimizar os padrões de uso mais comuns.

Sumário


O KDB + é popular entre as empresas principalmente devido à sua versatilidade excepcional - serve igualmente bem como base na memória e como base para armazenar terabytes de dados históricos e como plataforma para análise de dados. Devido ao fato de o processamento de dados ocorrer diretamente no banco de dados, é obtida uma alta velocidade de operação e economia de recursos. Uma linguagem de programação completa, integrada às funções do banco de dados, permite implementar na mesma plataforma toda a pilha de processos necessários - do recebimento de dados ao processamento de solicitações do usuário.

Informações Adicionais


Desvantagens


Uma desvantagem significativa do KDB + / Q é seu alto limite de entrada. A linguagem possui uma sintaxe estranha, algumas funções estão sobrecarregadas (o valor, por exemplo, possui cerca de 11 casos de uso). Mais importante ainda, requer uma abordagem radicalmente diferente para escrever programas. Em uma linguagem vetorial, você precisa pensar o tempo todo em termos de transformações de array, implementar todos os ciclos através de várias opções de funções de mapear / reduzir (chamadas advérbios em Q), nunca tentar economizar dinheiro substituindo operações vetoriais por operações atômicas. Por exemplo, para encontrar o índice da enésima ocorrência de um elemento em uma matriz, escreva:

 1. (where element=vector)[N] 

embora isso pareça terrivelmente ineficiente para os padrões C / Java (= cria um vetor booleano, onde retorna os índices dos elementos verdadeiros nele). Mas esse registro torna o significado da expressão mais compreensível e você usa operações de vetor rápidas em vez de operações atômicas lentas. A diferença conceitual entre a linguagem vetorial e o restante é comparável à diferença entre as abordagens imperativa e funcional da programação, e você precisa estar preparado para isso.

Alguns usuários também não estão satisfeitos com o QSQL. O fato é que ele parece apenas com SQL real. Na verdade, é apenas um intérprete de expressões semelhantes a SQL que não suporta a otimização de consultas. O próprio usuário deve escrever as consultas ideais e no Q, para as quais muitas não estão prontas. Por outro lado, é claro, você sempre pode escrever sua própria consulta ideal e não confiar em um otimizador de caixa preta.

Além disso, um livro sobre Q-Q For Mortals está disponível gratuitamente no site da empresa , e também existem muitos outros materiais úteis.

Outro grande ponto negativo é o custo da licença. São dezenas de milhares de dólares por ano para uma CPU. Somente grandes empresas podem arcar com essas despesas. Recentemente, a KX tornou a política de licenciamento mais flexível e oferece a capacidade de pagar apenas pelo tempo de uso ou alugar o KDB + nas nuvens do Google e da Amazon. O KX também oferece o download de uma versão gratuita para fins não comerciais (versão de 32 bits ou 64 bits, mediante solicitação).

Concorrentes


Existem alguns bancos de dados especializados construídos sobre princípios semelhantes - colunar, na memória, focados em quantidades muito grandes de dados. O problema é que esses são bancos de dados especializados. Um excelente exemplo é o Clickhouse. Esse banco de dados tem um princípio muito semelhante ao KDB + de armazenar dados no disco e criar o índice; ele realiza algumas consultas mais rapidamente que o KDB +, embora não significativamente. Mas mesmo que o banco de dados Clickhouse seja mais especializado que o KDB + - análise da web versus séries temporais arbitrárias (essa diferença é muito importante - por causa disso, por exemplo, não há como usar a ordenação de registros no Clickhouse). Mas, o mais importante, o Clickhouse não possui a universalidade do KDB +, uma linguagem que permitiria processar dados diretamente no banco de dados, em vez de carregá-los anteriormente em um aplicativo separado, construindo expressões SQL arbitrárias, aplicando funções arbitrárias em uma consulta, criando processos não relacionados à execução de funções históricas do banco de dados . Portanto, é difícil comparar o KDB + com outros bancos de dados, eles podem ser melhores em casos de uso separados ou simplesmente melhores se estivermos falando sobre as tarefas dos bancos de dados clássicos, mas não conheço outra ferramenta igualmente eficaz e universal para processar dados temporários.

Integração Python


Para tornar o KDB + mais fácil para quem é iniciante em tecnologia, o KX criou bibliotecas para uma forte integração com o Python em um único processo. Você pode chamar qualquer função python do Q ou vice-versa - chamar qualquer função Q do Python (em particular expressões QSQL). As bibliotecas convertem, se necessário (por uma questão de eficiência nem sempre), os dados do formato de um idioma para o formato de outro. Como resultado, Q e Python vivem em uma simbiose tão estreita que os limites entre eles são apagados. Como resultado, um programador, por um lado, tem acesso total a inúmeras bibliotecas úteis do Python; por outro, ele obtém uma base rápida para trabalhar com big data integrado no Python, o que é especialmente útil para os envolvidos no aprendizado ou modelagem de máquinas.

Trabalhando com Q em 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') 

Referências


Site da empresa - https://kx.com/
Site para desenvolvedores - https://code.kx.com/v2/
Livro Q For Mortals (em inglês) - https://code.kx.com/q4m3/
Artigos sobre o tópico de aplicativos KDB + / Q de funcionários da kx - https://code.kx.com/v2/wp/

Source: https://habr.com/ru/post/pt446412/


All Articles