Geekly articles weekly

Base de données KDB +: de la finance à la Formule 1

KDB +, un produit KX , est une base de données à colonnes étroites très connue, extrêmement rapide, conçue pour stocker des séries chronologiques et des calculs analytiques basés sur eux. Initialement, il jouissait (et jouit) d'une grande popularité dans le secteur financier - il est utilisé par les 10 premières banques d'investissement et de nombreux hedge funds, bourses et autres organisations bien connus. Récemment, KX a décidé d'élargir sa base de clients et propose désormais des solutions dans d'autres domaines où il y a une grande quantité de données triées par le temps ou d'une autre manière - télécom, bioinformatique, production, etc. En particulier, ils sont devenus un partenaire de l'équipe Aston Martin Red Bull Racing en Formule 1, où ils aident à collecter et à traiter les données des capteurs de voiture et à analyser les tests dans une soufflerie. Dans cet article, je veux vous dire quelles fonctionnalités de KDB + le rendent super-productif, pourquoi les entreprises sont prêtes à dépenser beaucoup d'argent dessus, et enfin, pourquoi ce n'est pas vraiment une base de données.



Dans cet article, je vais essayer de dire en général ce qu'est KDB +, quelles sont ses fonctionnalités et ses limites, quels sont ses avantages pour les entreprises qui souhaitent traiter de gros volumes de données. Je n'entrerai pas dans les détails de l'implémentation de KDB + et les détails de son langage de programmation Q. Ces deux sujets sont très étendus et méritent des articles séparés. De nombreuses informations sur ces sujets peuvent être trouvées sur code.kx.com, y compris un livre sur Q-Q For Mortals (voir le lien ci-dessous).

Quelques termes


  • Base de données en mémoire. Une base de données qui stocke les données dans la RAM pour un accès plus rapide. Les avantages d'une telle base de données sont compréhensibles, et les inconvénients sont la possibilité de perte de données, la nécessité d'avoir beaucoup de mémoire sur le serveur.
  • Base de données de colonnes. Une base de données où les données sont stockées en série et non enregistrement par enregistrement. Le principal avantage d'une telle base de données est que les données d'une colonne sont stockées ensemble sur disque et en mémoire, ce qui accélère considérablement leur accès. Il n'est pas nécessaire de charger des colonnes qui ne sont pas utilisées dans la demande. Le principal inconvénient est qu'il est difficile de modifier et de supprimer des enregistrements.
  • Séries chronologiques. Données avec une colonne telle que la date ou l'heure. En règle générale, l'ordre dans le temps est important pour ces données, afin que vous puissiez facilement déterminer quel enregistrement précède ou suit celui en cours, ou pour appliquer des fonctions dont le résultat dépend de l'ordre des enregistrements. Les bases de données classiques sont construites sur un principe complètement différent - représentant un ensemble d'enregistrements comme un ensemble, où l'ordre des enregistrements n'est pas défini en principe.
  • Vecteur. Dans le contexte, KDB + est une liste d'éléments du même type atomique, par exemple des nombres. En d'autres termes, un tableau d'éléments. Contrairement aux listes, les tableaux peuvent être stockés de manière compacte et traités à l'aide d'instructions de processeur vectoriel.

Contexte historique


KX a été fondée en 1993 par Arthur Whitney, qui a précédemment travaillé chez Morgan Stanley Bank sur A +, le successeur d'APL, un langage très original et populaire dans le monde financier. Bien sûr, dans KX, Arthur a continué dans le même esprit et a créé le langage vectoriel fonctionnel K, guidé par les idées du minimalisme radical. Les programmes K ressemblent à un ensemble désordonné de signes de ponctuation et de caractères spéciaux, la signification des caractères et des fonctions dépend du contexte, et chaque opération a beaucoup plus de sens que dans les langages de programmation habituels. Pour cette raison, le programme K prend un minimum d'espace - plusieurs lignes peuvent remplacer des pages de texte d'un langage verbeux comme Java - et est une implémentation super concentrée de l'algorithme.

Une fonction sur K qui implémente la plupart du générateur d'analyseur LL1 selon une grammaire donnée:

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 a également incarné cette philosophie d'efficacité extrême avec un minimum de mouvements corporels dans KDB +, qui est apparu en 2003 (je pense qu'il est maintenant clair d'où vient la lettre K du nom) et il n'y a rien de plus qu'un interprète de la quatrième version de la langue K.Une version plus agréable à l'œil de l'utilisateur est ajoutée à K K sous le nom Q. Q ajoute également la prise en charge d'un dialecte SQL spécifique - QSQL, et dans l'interpréteur - la prise en charge des tables comme type de données système, des outils pour travailler avec des tables en mémoire et sur disque, etc.

Ainsi, du point de vue de l'utilisateur, KDB + n'est qu'un interpréteur Q avec prise en charge des tables et des expressions de style LINQ de type SQL à partir de C #. C'est la différence la plus importante entre KDB + et d'autres bases de données et son principal avantage concurrentiel, qui est souvent négligé. Ce n'est pas une base de données + un langage auxiliaire qui est désactivé, mais un langage de programmation puissant à part entière + un support intégré pour les fonctions de base de données. Cette différence jouera un rôle décisif dans l'énumération de tous les avantages de KDB +. Par exemple ...

La taille


Selon les normes modernes, KDB + est juste une taille microscopique. Il s'agit littéralement d'un fichier exécutable plus petit qu'un mégaoctet et d'un petit fichier texte avec certaines fonctions système. En fait - moins d'un mégaoctet et pour ce programme, les entreprises paient des dizaines de milliers de dollars par an pour un processeur sur le serveur.

  • Cette taille permet à KDB + de se sentir bien sur n'importe quel matériel - du micro-ordinateur Pi aux serveurs avec des téraoctets de mémoire. Cela n'affecte en rien la fonctionnalité; de plus, Q démarre instantanément, ce qui permet de l'utiliser notamment en tant que langage de script.
  • Avec cette taille, l'interpréteur Q est complètement placé dans le cache du processeur, ce qui accélère l'exécution des programmes.
  • Avec cette taille du fichier exécutable, le processus Q occupe un espace mémoire négligeable; vous pouvez les exécuter par centaines. Dans le même temps, si nécessaire, Q peut fonctionner avec des dizaines ou des centaines de gigaoctets de mémoire en un seul processus.

Polyvalence


Q est parfait pour une variété de tâches. Le processus Q peut servir de base de données historique et fournir un accès rapide à des téraoctets d'informations. Par exemple, nous avons des dizaines de bases de données historiques, dans certaines desquelles une journée de données non compressée prend plus de 100 gigaoctets. Cependant, avec des restrictions raisonnables, la requête de base de données sera exécutée en dizaines à centaines de millisecondes. En général, nous avons un délai d'expiration universel pour les demandes des utilisateurs - 30 secondes - et cela fonctionne très rarement.

Avec la même facilité, Q peut être une base de données en mémoire. L'ajout de nouvelles données aux tables en mémoire est si rapide que les requêtes des utilisateurs sont un facteur limitant. Les données des tables sont stockées dans des colonnes, ce qui signifie que toute opération dans la colonne utilisera le cache du processeur à pleine capacité. En plus de cela, KX a essayé d'implémenter toutes les opérations de base telles que l'arithmétique via des instructions de processeur vectoriel, en maximisant leur vitesse. Q peut effectuer des tâches qui ne sont pas caractéristiques des bases de données - par exemple, traiter des données en continu et calculer en «temps réel» (avec un retard de plusieurs dizaines de millisecondes à plusieurs secondes selon la tâche) diverses fonctions d'agrégation pour les instruments financiers pour différents intervalles de temps ou construire un modèle de l'impact de la perfection transactions sur le marché et effectuer son profilage presque immédiatement après son achèvement. Dans de tels problèmes, le plus souvent, le retard principal n'est pas Q, mais la nécessité de synchroniser les données de différentes sources. La vitesse élevée est obtenue du fait que les données et les fonctions qui les traitent sont dans le même processus, et le traitement est réduit à l'exécution de plusieurs expressions et jointures QSQL qui ne sont pas interprétées, mais sont exécutées en code binaire.

Enfin, tout processus de service peut également être écrit en Q. Par exemple, les processus de passerelle qui distribuent automatiquement les demandes des utilisateurs aux bases de données et aux serveurs nécessaires. Le programmeur a la liberté totale d'implémenter n'importe quel algorithme pour l'équilibrage, la priorisation, la tolérance aux pannes, les droits d'accès, les quotas et généralement tout ce que votre cœur désire. Le principal problème ici est que vous devez implémenter tout cela vous-même.

Pour un exemple, je vais énumérer les types de processus que nous avons. Tous sont activement utilisés et fonctionnent ensemble, combinant des dizaines de bases de données différentes, traitant des données provenant de nombreuses sources et desservant des centaines d'utilisateurs et d'applications.

  • Connecteurs (feedhandler) aux sources de données. Ces processus utilisent généralement des bibliothèques externes chargées en Q. L'interface C de Q est extrêmement simple et vous permet de créer facilement des fonctions proxy pour n'importe quelle bibliothèque C / C ++. Q est suffisamment rapide pour gérer, par exemple, le traitement simultané du flux de messages FIX de toutes les bourses européennes.
  • Distributeurs Tickerplant, qui servent de lien intermédiaire entre les connecteurs et les consommateurs. Dans le même temps, ils écrivent les données entrantes dans un journal binaire spécial, offrant aux consommateurs une résistance à la perte de connexion ou au redémarrage.
  • Base de données en mémoire (rdb). Ces bases de données fournissent l'accès le plus rapide aux données brutes et fraîches, en les stockant en mémoire. En règle générale, ils accumulent des données dans des tableaux pendant la journée et les remettent à zéro la nuit.
  • Base de données persistante (pdb). Ces bases de données fournissent aujourd'hui un stockage de données dans la base de données historique. En règle générale, contrairement à rdb, ils ne stockent pas de données en mémoire, mais utilisent un cache spécial sur le disque pendant une journée et copient les données à minuit dans la base de données historique.
  • Bases historiques (hdb). Ces bases de données permettent d'accéder aux données des jours, mois et années précédents. Leur taille (en jours) n'est limitée que par la taille des disques durs. Les données peuvent être localisées n'importe où, en particulier sur différents disques pour un accès plus rapide. Il est possible de compresser les données en utilisant plusieurs algorithmes au choix. La structure de la base de données est bien documentée et simple, les données sont stockées sur une base unitaire dans des fichiers ordinaires, afin qu'elles puissent être traitées, y compris en utilisant le système d'exploitation.
  • Bases de données avec informations agrégées. Différentes agrégations sont stockées, généralement avec, regroupées par nom d'instrument et intervalle de temps. Les bases de données en mémoire mettent à jour leur état à chaque message entrant, et les historiques stockent des données précalculées pour accélérer l'accès aux données historiques.
  • Enfin, les processus de passerelle au service des applications et des utilisateurs. Q vous permet de mettre en œuvre un traitement complètement asynchrone des messages entrants, en les répartissant entre les bases de données, en vérifiant les droits d'accès, etc. Je note que les messages ne sont pas limités et le plus souvent ne sont pas des instructions SQL, comme c'est le cas dans d'autres bases de données. Le plus souvent, l'expression SQL est cachée dans une fonction spéciale et est construite en fonction des paramètres demandés par l'utilisateur - le temps est converti, filtré, les données sont normalisées (par exemple, le prix des actions est égalisé si des dividendes ont été payés), etc.

Architecture typique pour un type de données:



La vitesse


Bien que Q soit un langage interprété, il est simultanément un langage vectoriel. Cela signifie que de nombreuses fonctions intégrées, en particulier l'arithmétique, acceptent des arguments de toute forme - nombres, vecteurs, matrices, listes, et le programmeur devrait implémenter le programme comme des opérations sur des tableaux. Dans un tel langage, si vous ajoutez deux vecteurs dans un million d'éléments, peu importe que le langage soit interprété, l'addition sera effectuée par une fonction binaire superoptimisée. Étant donné que la majeure partie du temps dans les programmes Q est consacrée à des opérations avec des tables utilisant ces fonctions vectorisées de base, la sortie a une vitesse très décente qui vous permet de traiter une énorme quantité de données même en un seul processus. Ceci est similaire aux bibliothèques mathématiques de python - bien que python lui-même soit un langage très lent, il possède de nombreuses bibliothèques numpy excellentes qui vous permettent de traiter des données numériques à la vitesse d'un langage compilé (en passant, numpy est idéologiquement proche de Q).

De plus, KX a très soigneusement abordé la conception des tables et optimisé le travail avec elles. Premièrement, plusieurs types d'index sont pris en charge, qui sont pris en charge par les fonctions intégrées et peuvent être appliqués non seulement aux colonnes de table, mais également à tous les vecteurs - regroupement, tri, attribut d'unicité et regroupement spécial pour les bases de données historiques. L'index est superposé élémentairement et est automatiquement ajusté lors de l'ajout d'éléments à la colonne / au vecteur. Les index peuvent également chevaucher des colonnes de table en mémoire et sur disque. Lors de l'exécution d'une requête QSQL, les index sont utilisés automatiquement, si possible. Deuxièmement, le travail avec les données historiques se fait via le mécanisme de mappage de fichiers OS (carte mémoire). Les grandes tables ne sont jamais chargées en mémoire, au lieu de cela, les colonnes nécessaires sont directement mappées en mémoire et seule cette partie d'entre elles est réellement chargée (les index aident ici aussi). Il n'y a aucune différence pour le programmeur, que les données soient en mémoire ou non, le mécanisme de travail avec mmap est complètement caché dans les entrailles de Q.

KDB + n'est pas une base de données relationnelle, les tables peuvent contenir des données arbitraires, tandis que l'ordre des lignes dans la table ne change pas lorsque de nouveaux éléments sont ajoutés et peuvent et doivent être utilisés lors de l'écriture de requêtes. Cette fonctionnalité est requise de toute urgence pour travailler avec des séries chronologiques (données d'échanges, télémétrie, journaux d'événements), car si les données sont triées par heure, l'utilisateur n'a pas besoin d'utiliser d'astuces SQL pour trouver la première ou la dernière ligne ou N lignes dans la table , déterminez quelle ligne suit la Nième ligne, etc. Les jointures de tableaux sont encore plus simplifiées, par exemple, en trouvant pour 16 000 transactions VOD.L (Vodafone) la dernière cotation dans un tableau de 500 millions d'éléments prend environ une seconde sur disque et une dizaine de millisecondes en mémoire.

Un exemple de jointure temporelle est que la table de devis est mappée en mémoire, il n'est donc pas nécessaire de spécifier VOD.L où, l'index de la colonne sym est implicitement utilisé et le fait que les données sont triées par heure. Presque toutes les jointures dans Q sont des fonctions ordinaires, ne faisant pas partie de l'instruction select:

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

Enfin, il convient de noter que les ingénieurs de KX, à commencer par Arthur Whitney lui-même, sont vraiment obsédés par l'efficacité et s'efforcent de tirer le meilleur parti des fonctions Q standard et d'optimiser les modèles d'utilisation les plus courants.

Résumé


KDB + est populaire parmi les entreprises principalement en raison de sa polyvalence exceptionnelle - il sert aussi bien comme base en mémoire que comme base de stockage de téraoctets de données historiques et comme plate-forme d'analyse de données. Du fait que le traitement des données s'effectue directement dans la base de données, une vitesse de fonctionnement élevée et une économie de ressources sont obtenues. Un langage de programmation à part entière, intégré aux fonctions de la base de données, vous permet de mettre en œuvre sur la même plate-forme toute la pile des processus nécessaires - de la réception des données au traitement des demandes des utilisateurs.

Information additionnelle


Inconvénients


Un inconvénient important de KDB + / Q est son seuil d'entrée élevé. Le langage a une syntaxe étrange, certaines fonctions sont fortement surchargées (la valeur, par exemple, a environ 11 cas d'utilisation). Plus important encore, cela nécessite une approche radicalement différente de l'écriture de programmes. Dans un langage vectoriel, vous devez penser tout le temps en termes de transformations de tableaux, implémenter tous les cycles à travers plusieurs options des fonctions map / réduire (appelées adverbes en Q), ne jamais essayer d'économiser de l'argent en remplaçant les opérations vectorielles par des opérations atomiques. Par exemple, pour trouver l'index de la Nème occurrence d'un élément dans un tableau, écrivez:

 1. (where element=vector)[N]

bien que cela semble terriblement inefficace par rapport aux normes C / Java (= crée un vecteur booléen, où renvoie les indices des vrais éléments qu'il contient). Mais un tel enregistrement rend le sens de l'expression plus compréhensible et vous utilisez des opérations vectorielles rapides au lieu de celles atomiques lentes. La différence conceptuelle entre le langage vectoriel et le reste est comparable à la différence entre les approches impératives et fonctionnelles de la programmation, et vous devez vous y préparer.

Certains utilisateurs sont également mécontents de QSQL. Le fait est qu'il ne ressemble qu'à du vrai SQL. En fait, c'est juste un interpréteur d'expressions de type SQL qui ne prend pas en charge l'optimisation des requêtes. L'utilisateur lui-même doit écrire les requêtes optimales, et sur Q, pour lesquelles beaucoup ne sont pas prêtes. D'un autre côté, bien sûr, vous pouvez toujours écrire votre propre requête optimale vous-même, et ne pas compter sur un optimiseur de boîte noire.

En plus, un livre sur Q - Q For Mortals est disponible gratuitement sur le site Web de l'entreprise , et il existe également de nombreux autres documents utiles.

Un autre gros inconvénient est le coût de la licence. Cela représente des dizaines de milliers de dollars par an pour un processeur. Seules les grandes entreprises peuvent se permettre de telles dépenses. Récemment, KX a rendu la politique de licence plus flexible et offre la possibilité de payer uniquement pour le temps d'utilisation ou de louer KDB + dans les clouds Google et Amazon. KX propose également de télécharger une version gratuite à des fins non commerciales (version 32 bits ou 64 bits sur demande).

Concurrents


Il existe un certain nombre de bases de données spécialisées reposant sur des principes similaires - en colonnes, en mémoire, axées sur de très grandes quantités de données. Le problème est qu'il s'agit de bases de données spécialisées. Un exemple typique est Clickhouse. Cette base de données a un principe très similaire au stockage de données sur disque et à la construction de l'index KDB +; elle effectue certaines requêtes plus rapidement que KDB +, mais pas de manière significative. Mais même si la base de données Clickhouse est plus spécialisée que KDB + - analyse Web vs séries temporelles arbitraires (cette différence est très importante - à cause de cela, par exemple, il n'y a aucun moyen d'utiliser l'ordre des enregistrements dans Clickhouse). Mais, plus important encore, Clickhouse n'a pas l'universalité de KDB +, un langage qui permettrait de traiter les données directement dans la base de données, plutôt que de les charger précédemment dans une application distincte, de créer des expressions SQL arbitraires, d'appliquer des fonctions arbitraires dans une requête, de créer des processus non liés à l'exécution des fonctions de base de données historiques. . Par conséquent, il est difficile de comparer KDB + avec d'autres bases de données, elles peuvent être meilleures dans des cas d'utilisation distincts ou simplement meilleures si nous parlons des tâches des bases de données classiques, mais je ne connais pas d'autre outil tout aussi efficace et universel pour le traitement des données temporaires.

Intégration Python


Pour rendre KDB + plus facile pour les personnes nouvelles dans la technologie, KX a créé des bibliothèques pour une intégration étroite avec Python dans un seul processus. Vous pouvez soit appeler n'importe quelle fonction python depuis Q, ou vice versa - appeler n'importe quelle fonction Q depuis Python (en particulier les expressions QSQL). Les bibliothèques convertissent si nécessaire (pour des raisons d'efficacité pas toujours) les données du format d'une langue au format d'une autre. En conséquence, Q et Python vivent dans une symbiose si étroite que les frontières entre eux sont effacées. En conséquence, un programmeur, d'une part, a un accès complet à de nombreuses bibliothèques Python utiles, d'autre part, il obtient une base rapide pour travailler avec des mégadonnées intégrées dans Python, ce qui est particulièrement utile pour ceux impliqués dans l'apprentissage automatique ou la modélisation.

Travailler avec Q en 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')

Les références


Site Web de l'entreprise - https://kx.com/
Site Web pour les développeurs - https://code.kx.com/v2/
Livre Q For Mortals (en anglais) - https://code.kx.com/q4m3/
Articles sur le sujet des applications KDB + / Q des employés de kx - https://code.kx.com/v2/wp/

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

More articles:


All Articles