Geekly articles weekly

Basis Data KDB +: Dari Keuangan ke Formula 1

KDB +, produk KX , adalah lingkaran kecil yang terkenal, sangat cepat, basis data kolom yang dirancang untuk menyimpan deret waktu dan perhitungan analitik berdasarkan pada mereka. Awalnya, ia menikmati (dan menikmati) popularitas besar di industri keuangan - ini digunakan oleh semua 10 bank investasi top dan banyak dana lindung nilai yang terkenal, bursa dan organisasi lain. Baru-baru ini, KX memutuskan untuk memperluas basis pelanggannya dan sekarang menawarkan solusi di bidang lain di mana ada sejumlah besar data yang diurutkan berdasarkan waktu atau dengan cara lain - telekomunikasi, bioinformatika, produksi, dll. Secara khusus, mereka menjadi mitra tim Aston Martin Red Bull Racing di Formula 1, di mana mereka membantu mengumpulkan dan memproses data dari sensor mobil dan menganalisis tes di terowongan angin. Pada artikel ini saya ingin memberi tahu Anda fitur-fitur apa dari KDB + yang membuatnya superproduksi, mengapa perusahaan mau mengeluarkan banyak uang untuk itu, dan akhirnya, mengapa ini bukan database.



Pada artikel ini saya akan mencoba memberi tahu secara umum apa itu KDB +, fitur dan batasan apa yang dimilikinya, apa manfaatnya bagi perusahaan yang ingin memproses data dalam volume besar. Saya tidak akan membahas rincian implementasi KDB + dan rincian bahasa pemrograman Q. Kedua topik ini sangat luas dan layak mendapatkan artikel terpisah. Banyak informasi tentang topik-topik ini dapat ditemukan di code.kx.com, termasuk buku tentang Q - Q For Mortals (lihat tautan di bawah).

Beberapa istilah


  • Database dalam memori. Database yang menyimpan data dalam RAM untuk akses yang lebih cepat. Kelebihan dari basis data seperti itu dapat dipahami, dan kerugiannya adalah kemungkinan kehilangan data, kebutuhan untuk memiliki banyak memori di server.
  • Database kolom. Basis data tempat data disimpan secara seri, bukan catatan demi catatan. Keuntungan utama dari database tersebut adalah bahwa data dari satu kolom disimpan bersama dalam disk dan memori, yang sangat mempercepat aksesnya. Tidak perlu memuat kolom yang tidak digunakan dalam permintaan. Kerugian utama adalah sulit untuk memodifikasi dan menghapus catatan.
  • Seri waktu. Data dengan kolom seperti tanggal atau waktu. Sebagai aturan, memesan dalam waktu penting untuk data tersebut, sehingga Anda dapat dengan mudah menentukan rekaman mana yang mendahului atau mengikuti arus, atau untuk menerapkan fungsi yang hasilnya tergantung pada urutan catatan. Database klasik dibangun di atas prinsip yang sama sekali berbeda - mewakili serangkaian catatan sebagai satu set, di mana urutan catatan tidak didefinisikan pada prinsipnya.
  • Vektor. Dalam konteksnya, KDB + adalah daftar elemen dengan tipe atom yang sama, misalnya angka. Dengan kata lain, array elemen. Array, tidak seperti daftar, dapat disimpan secara kompak dan diproses menggunakan instruksi prosesor vektor.

Latar belakang sejarah


KX didirikan pada tahun 1993 oleh Arthur Whitney, yang sebelumnya bekerja di Morgan Stanley Bank pada A +, penerus APL, bahasa yang sangat asli dan populer di dunia keuangan. Tentu saja, di KX, Arthur melanjutkan semangat yang sama dan menciptakan bahasa fungsional vektor K, dipandu oleh ide-ide minimalis radikal. Program K terlihat seperti sekumpulan tanda baca dan karakter khusus yang berantakan, makna karakter dan fungsi tergantung pada konteksnya, dan setiap operasi membawa lebih banyak makna daripada dalam bahasa pemrograman biasa. Karena itu, program K membutuhkan ruang minimum - beberapa baris dapat menggantikan halaman teks dari bahasa verbose seperti Java - dan merupakan implementasi algoritma yang sangat terkonsentrasi.

Fungsi pada K yang mengimplementasikan sebagian besar generator parser LL1 menurut tata bahasa yang diberikan:

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 juga mewujudkan filosofi efisiensi ekstrem ini dengan gerakan tubuh minimum di KDB +, yang muncul pada tahun 2003 (saya pikir sekarang sudah jelas dari mana huruf K berasal dari namanya) dan tidak ada yang lebih dari seorang penerjemah dari versi keempat bahasa K. Versi yang lebih menyenangkan bagi mata pengguna ditambahkan ke K K dengan nama Q. Q juga menambahkan dukungan untuk dialek SQL tertentu - QSQL, dan pada interpreter - dukungan untuk tabel sebagai tipe data sistem, alat untuk bekerja dengan tabel dalam memori dan pada disk, dll.

Jadi, dari sudut pandang pengguna, KDB + hanyalah penerjemah bahasa Q dengan dukungan untuk tabel dan ekspresi gaya-LINQ seperti SQL dari C #. Ini adalah perbedaan paling penting antara KDB + dan basis data lainnya dan keunggulan kompetitif utamanya, yang seringkali diabaikan. Ini bukan basis data + bahasa bantu yang dinonaktifkan, tetapi bahasa pemrograman yang kuat lengkap + dukungan bawaan untuk fungsi basis data. Perbedaan ini akan memainkan peran yang menentukan dalam daftar semua manfaat KDB +. Misalnya ...

Ukuran


Dengan standar modern, KDB + hanyalah ukuran mikroskopis. Ini benar-benar satu file yang dapat dieksekusi lebih kecil dari satu megabyte dan satu file teks kecil dengan beberapa fungsi sistem. Sebenarnya - kurang dari satu megabyte dan untuk program ini perusahaan membayar puluhan ribu dolar per tahun untuk satu prosesor di server.

  • Ukuran ini memungkinkan KDB + untuk merasa hebat pada perangkat keras apa pun - dari komputer mikro Pi ke server dengan memori terabyte. Ini tidak mempengaruhi fungsi dengan cara apa pun, apalagi, Q mulai secara instan, yang memungkinkannya untuk digunakan termasuk sebagai bahasa scripting.
  • Dengan ukuran ini, interpreter Q sepenuhnya ditempatkan dalam cache prosesor, yang mempercepat eksekusi program.
  • Dengan ukuran file yang dapat dieksekusi ini, proses Q membutuhkan ruang memori yang dapat diabaikan, Anda dapat menjalankannya dalam ratusan. Pada saat yang sama, jika perlu, Q dapat beroperasi dengan puluhan atau ratusan gigabyte memori dalam satu proses.

Keserbagunaan


Q sangat cocok untuk berbagai tugas. Proses Q dapat berfungsi sebagai basis data historis dan menyediakan akses cepat ke terabyte informasi. Sebagai contoh, kami memiliki lusinan database historis, di mana beberapa hari dalam satu data terkompresi membutuhkan lebih dari 100 gigabita. Namun, dengan batasan yang masuk akal, kueri basis data akan dieksekusi dalam puluhan hingga ratusan milidetik. Secara umum, kami memiliki batas waktu universal untuk permintaan pengguna - 30 detik - dan ini berfungsi sangat jarang.

Dengan kemudahan yang sama, Q bisa menjadi basis data dalam memori. Menambahkan data baru ke tabel dalam memori sangat cepat sehingga permintaan pengguna adalah faktor pembatas. Data dalam tabel disimpan dalam kolom, yang berarti bahwa setiap operasi dalam kolom akan menggunakan cache prosesor pada kapasitas penuh. Selain itu, KX mencoba menerapkan semua operasi dasar seperti aritmatika melalui instruksi prosesor vektor, memaksimalkan kecepatannya. Q dapat melakukan tugas yang bukan merupakan karakteristik dari basis data - misalnya, memproses streaming data dan menghitung dalam "waktu nyata" (dengan penundaan puluhan milidetik hingga beberapa detik tergantung pada tugasnya) berbagai fungsi agregat untuk instrumen keuangan untuk interval waktu yang berbeda atau membangun model dampak sempurna. transaksi ke pasar dan melakukan pembuatan profil segera setelah selesai. Dalam masalah seperti itu, paling sering waktu tunda utama bukanlah Q, tetapi kebutuhan untuk menyinkronkan data dari berbagai sumber. Kecepatan tinggi dicapai karena fakta bahwa data dan fungsi yang memprosesnya berada dalam proses yang sama, dan pemrosesan dikurangi menjadi beberapa ekspresi QSQL dan gabungan yang tidak diinterpretasikan, tetapi dieksekusi dalam kode biner.

Akhirnya, setiap proses layanan juga dapat ditulis dalam Q. Misalnya, Gateway memproses yang secara otomatis mendistribusikan permintaan pengguna ke database dan server yang diperlukan. Programmer memiliki kebebasan penuh untuk menerapkan algoritma apa pun untuk menyeimbangkan, memprioritaskan, toleransi kesalahan, hak akses, kuota, dan umumnya apa pun yang diinginkan hati Anda. Masalah utama di sini adalah Anda harus menerapkan semua ini sendiri.

Sebagai contoh, saya akan mencantumkan jenis proses yang kita miliki. Semuanya secara aktif digunakan dan bekerja bersama, menggabungkan puluhan database yang berbeda, memproses data dari berbagai sumber dan melayani ratusan pengguna dan aplikasi.

  • Konektor (pengumpan) ke sumber data. Proses ini biasanya menggunakan pustaka eksternal yang dimuat di Q. Antarmuka C di Q sangat sederhana dan memungkinkan Anda untuk dengan mudah membuat fungsi proxy untuk pustaka C / C ++ apa pun. Q cukup cepat untuk menangani, misalnya, memproses aliran pesan FIX dari semua bursa efek Eropa secara bersamaan.
  • Distributor Tickerplant, yang berfungsi sebagai penghubung antara konektor dan konsumen. Pada saat yang sama, mereka menulis data yang masuk dalam log biner khusus, memberikan perlawanan bagi konsumen untuk kehilangan koneksi atau memulai kembali.
  • Database dalam memori (rdb). Database ini menyediakan akses tercepat ke data mentah, segar, menyimpannya dalam memori. Sebagai aturan, mereka mengakumulasi data dalam tabel di siang hari dan nol di malam hari.
  • Database Persist (pdb). Basis data ini menyediakan penyimpanan data hari ini di basis data historis. Sebagai aturan, tidak seperti rdb, mereka tidak menyimpan data dalam memori, tetapi menggunakan cache khusus pada disk selama sehari dan menyalin data pada tengah malam ke database historis.
  • Basis historis (hdb). Basis data ini menyediakan akses ke data untuk hari, bulan, dan tahun sebelumnya. Ukurannya (dalam berhari-hari) hanya dibatasi oleh ukuran hard drive. Data dapat ditemukan di mana saja, khususnya pada disk yang berbeda untuk akses yang lebih cepat. Dimungkinkan untuk memampatkan data menggunakan beberapa algoritma untuk dipilih. Struktur basis data terdokumentasi dengan baik dan sederhana, data disimpan berdasarkan per-unit dalam file biasa, sehingga dapat diproses, termasuk menggunakan sistem operasi.
  • Database dengan informasi agregat. Berbagai agregasi disimpan, biasanya dengan, dikelompokkan berdasarkan nama instrumen dan interval waktu. Database dalam memori memperbarui status mereka dengan setiap pesan yang masuk, dan yang historis menyimpan data yang sudah dihitung untuk mempercepat akses ke data historis.
  • Akhirnya, gateway memproses aplikasi dan pengguna. Q memungkinkan Anda untuk mengimplementasikan pemrosesan pesan masuk yang sepenuhnya tidak sinkron, mendistribusikannya di antara basis data, memeriksa hak akses, dll. Saya perhatikan bahwa pesan tidak terbatas dan paling sering bukan pernyataan SQL, seperti halnya di database lain. Paling sering, ekspresi SQL disembunyikan dalam fungsi khusus dan dibangun berdasarkan parameter yang diminta oleh pengguna - waktu dikonversi, disaring, data dinormalisasi (misalnya, harga saham disamakan jika dividen dibayarkan), dll.

Arsitektur khas untuk satu tipe data:



Kecepatan


Meskipun Q adalah bahasa yang diartikan, itu secara bersamaan adalah bahasa vektor. Ini berarti bahwa banyak fungsi bawaan, khususnya aritmatika, menerima argumen dalam bentuk apa pun - angka, vektor, matriks, daftar, dan pemrogram diharapkan untuk mengimplementasikan program sebagai operasi pada array. Dalam bahasa seperti itu, jika Anda menambahkan dua vektor dalam sejuta elemen, itu tidak lagi berarti bahwa bahasa ditafsirkan, penambahan akan dilakukan oleh fungsi biner yang dioptimalkan. Karena bagian terbesar dari waktu dalam program Q dihabiskan untuk operasi dengan tabel menggunakan fungsi-fungsi dasar vektor ini, output memiliki kecepatan yang sangat baik yang memungkinkan Anda untuk memproses sejumlah besar data bahkan dalam satu proses. Ini mirip dengan perpustakaan matematika di python - walaupun python sendiri adalah bahasa yang sangat lambat, ia memiliki banyak perpustakaan numpy yang memungkinkan Anda untuk memproses data numerik dengan kecepatan bahasa yang dikompilasi (omong-omong, numpy secara ideologis dekat dengan Q).

Selain itu, KX sangat hati-hati mendekati desain tabel dan mengoptimalkan pekerjaan dengannya. Pertama, beberapa jenis indeks didukung, yang didukung oleh fungsi bawaan dan dapat diterapkan tidak hanya pada kolom tabel, tetapi juga untuk vektor apa pun - pengelompokan, pengurutan, atribut keunikan dan pengelompokan khusus untuk basis data historis. Indeks ditumpangkan secara elemen dan secara otomatis disesuaikan ketika menambahkan elemen ke kolom / vektor. Indeks dapat juga tumpang tindih kolom tabel baik di memori dan pada disk. Saat menjalankan kueri QSQL, indeks digunakan secara otomatis, jika memungkinkan. Kedua, bekerja dengan data historis dilakukan melalui mekanisme pemetaan file OS (peta memori). Tabel besar tidak pernah dimuat ke dalam memori, sebaliknya, kolom yang diperlukan dipetakan langsung ke memori dan hanya sebagian dari mereka yang benar-benar dimuat (indeks juga membantu di sini), yang diperlukan. Tidak ada perbedaan untuk programmer apakah data ada dalam memori atau tidak, mekanisme untuk bekerja dengan mmap sepenuhnya tersembunyi di dalam usus Q.

KDB + bukan database relasional, tabel dapat berisi data arbitrer, sedangkan urutan baris dalam tabel tidak berubah ketika elemen baru ditambahkan dan dapat dan harus digunakan saat menulis kueri. Fitur ini sangat diperlukan untuk bekerja dengan deret waktu (data dari pertukaran, telemetri, event log), karena jika data diurutkan berdasarkan waktu, maka pengguna tidak perlu menggunakan trik SQL apa pun untuk menemukan baris pertama atau terakhir atau baris N dalam tabel. , tentukan baris mana yang mengikuti baris ke-N, dll. Gabungan tabel bahkan lebih disederhanakan, misalnya, menemukan untuk 16.000 transaksi VOD.L (Vodafone) kutipan terakhir dalam tabel 500 juta elemen membutuhkan waktu sekitar satu detik pada disk dan selusin milidetik dalam memori.

Contoh waktu bergabung adalah tabel kutipan dipetakan ke memori, sehingga tidak perlu menentukan VOD.L di mana, indeks pada kolom sym secara implisit digunakan dan fakta bahwa data diurutkan berdasarkan waktu. Hampir semua gabungan dalam Q adalah fungsi biasa, bukan bagian dari pernyataan pilih:

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

Akhirnya, perlu dicatat bahwa para insinyur di KX, dimulai dengan Arthur Whitney sendiri, benar-benar terobsesi dengan efisiensi dan melakukan segala upaya untuk mendapatkan hasil maksimal dari fungsi Q standar dan mengoptimalkan pola penggunaan yang paling umum.

Ringkasan


KDB + populer di kalangan bisnis terutama karena keserbagunaannya yang luar biasa - ia berfungsi dengan baik sebagai basis di memori, dan sebagai basis untuk menyimpan terabyte data historis, dan sebagai platform untuk analisis data. Karena kenyataan bahwa pemrosesan data terjadi langsung dalam database, kecepatan tinggi operasi dan penghematan sumber daya tercapai. Bahasa pemrograman lengkap, terintegrasi dengan fungsi basis data, memungkinkan Anda untuk mengimplementasikan pada platform yang sama seluruh tumpukan proses yang diperlukan - mulai dari menerima data hingga memproses permintaan pengguna.

Informasi tambahan


Kekurangan


Kelemahan signifikan dari KDB + / Q adalah ambang masuknya yang tinggi. Bahasa ini memiliki sintaks yang aneh, beberapa fungsi kelebihan beban (nilai, misalnya, memiliki sekitar 11 kasus penggunaan). Yang paling penting, ini membutuhkan pendekatan yang sangat berbeda untuk program penulisan. Dalam bahasa vektor, Anda harus berpikir sepanjang waktu dalam hal transformasi array, mengimplementasikan semua siklus melalui beberapa opsi peta / mengurangi fungsi (disebut keterangan dalam Q), tidak pernah mencoba menghemat uang dengan mengganti operasi vektor dengan yang atom. Misalnya, untuk menemukan indeks kemunculan elemen ke-N dalam array, tulis:

 1. (where element=vector)[N]

meskipun ini terlihat sangat tidak efisien oleh standar C / Java (= menciptakan vektor Boolean, di mana mengembalikan indeks elemen sebenarnya di dalamnya). Tetapi catatan seperti itu membuat makna ungkapan lebih dapat dipahami dan Anda menggunakan operasi vektor cepat alih-alih yang lambat atom. Perbedaan konseptual antara bahasa vektor dan sisanya sebanding dengan perbedaan antara pendekatan imperatif dan fungsional untuk pemrograman, dan Anda harus siap untuk ini.

Beberapa pengguna juga tidak senang dengan QSQL. Faktanya adalah itu hanya tampak seperti SQL nyata. Pada kenyataannya, itu hanya sebuah penafsiran ekspresi seperti SQL yang tidak mendukung optimisasi kueri. Pengguna sendiri harus menulis kueri optimal, dan pada Q, yang banyak di antaranya tidak siap. Di sisi lain, tentu saja, Anda selalu dapat menulis sendiri kueri optimal Anda sendiri, dan tidak mengandalkan pengoptimal kotak hitam.

Sebagai plus, buku tentang Q - Q For Mortals tersedia secara gratis di situs web perusahaan , dan ada juga banyak bahan bermanfaat lainnya.

Kekurangan besar lainnya adalah biaya lisensi. Ini adalah puluhan ribu dolar per tahun untuk satu CPU. Hanya perusahaan besar yang mampu membayar biaya seperti itu. Baru-baru ini, KX telah membuat kebijakan lisensi lebih fleksibel dan memberikan kemampuan untuk membayar hanya untuk saat menggunakan atau menyewa KDB + di cloud Google dan Amazon. KX juga menawarkan untuk mengunduh versi gratis untuk tujuan non-komersial (versi 32-bit atau 64-bit atas permintaan).

Pesaing


Ada beberapa basis data khusus yang dibangun berdasarkan prinsip yang sama - kolumnis, di dalam memori, berfokus pada jumlah data yang sangat besar. Masalahnya adalah bahwa ini adalah database khusus. Contoh utama adalah Clickhouse. Basis data ini memiliki prinsip yang sangat mirip dengan KDB + untuk menyimpan data pada disk dan membangun indeks, ia melakukan beberapa pertanyaan lebih cepat daripada KDB +, meskipun tidak signifikan. Tetapi bahkan ketika basis data Clickhouse lebih terspesialisasi daripada KDB + - analisis web vs deret waktu sewenang-wenang (perbedaan ini sangat penting - karena itu, misalnya, tidak ada cara untuk menggunakan pemesanan catatan di Clickhouse). Tapi, yang paling penting, Clickhouse tidak memiliki universalitas KDB +, bahasa yang memungkinkan pemrosesan data secara langsung dalam database, daripada memuatnya sebelumnya ke dalam aplikasi terpisah, membangun ekspresi SQL yang sewenang-wenang, menerapkan fungsi sewenang-wenang dalam kueri, menciptakan proses yang tidak terkait dengan pelaksanaan fungsi database historis . Oleh karena itu, sulit untuk membandingkan KDB + dengan database lain, mereka mungkin lebih baik dalam kasus penggunaan terpisah atau hanya lebih baik jika kita berbicara tentang tugas-tugas database klasik, tetapi saya tidak tahu alat lain yang sama efektif dan universal untuk memproses data sementara.

Integrasi Python


Untuk membuat KDB + lebih mudah bagi orang-orang yang baru mengenal teknologi, KX telah membuat perpustakaan untuk integrasi ketat dengan Python dalam satu proses tunggal. Anda bisa memanggil fungsi python dari Q, atau sebaliknya - memanggil fungsi Q dari Python (khususnya ekspresi QSQL). Perpustakaan mengkonversi jika perlu (demi efisiensi tidak selalu) data dari format satu bahasa ke format yang lain. Akibatnya, Q dan Python hidup dalam simbiosis yang sangat dekat sehingga batas-batas di antara mereka terhapus. Akibatnya, seorang programmer, di satu sisi, memiliki akses penuh ke berbagai pustaka Python yang bermanfaat, di sisi lain, ia mendapatkan basis cepat untuk bekerja dengan data besar yang diintegrasikan dengan Python, yang sangat berguna bagi mereka yang terlibat dalam pembelajaran mesin atau pemodelan.

Bekerja dengan Q dengan 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')

Referensi


Situs web perusahaan - https://kx.com/
Situs web untuk pengembang - https://code.kx.com/v2/
Buku Q For Mortals (dalam bahasa Inggris) - https://code.kx.com/q4m3/
Artikel tentang topik aplikasi KDB + / Q dari karyawan kx - https://code.kx.com/v2/wp/

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

More articles:


All Articles