Gambaran

Beberapa bulan yang lalu saya mulai mengerjakan prototipe database relasional di Metal. Apple baru saja merilis M1 Max dan M1 Ultra beberapa bulan sebelumnya dengan memori terpadu sebanyak 128GB (di Mac Studio).

Saya melihat ini sebagai peluang untuk melakukan sesuatu dengan pemrosesan yang sangat berat yang membutuhkan banyak memori GPU: memproses tabel relasional besar pada GPU.

Saya bukan orang pertama yang berpikir untuk menulis database relasional pada GPU. Basis data seperti BlazingSQL , basis data relasional GPU yang dibangun di atas Rapids.AI . Rapids.AI adalah pustaka Python dari NVIDIA yang mencerminkan fungsionalitas banyak pustaka Python populer, seperti Pandas, tetapi menjalankan fungsi yang setara pada GPU. NVIDIA telah banyak berinvestasi di pusat data dan membantu mengembangkan lebih banyak alat yang berjalan di kartu mereka, terutama untuk pembelajaran mesin dan pemrosesan data besar.

Dari menonton konferensi Apple akhir-akhir ini, saya merasa banyak potensi performa yang tidak benar-benar digunakan. Dari apa yang saya lihat, pengembang memanfaatkan kemampuan grafis baru dari chip baru. Di sisi komputasi, demo dan perangkat lunak sumber terbuka yang dibuat dengan Metal masih kurang. Apple membuat proyek sampel simulasi partikel, saya kira menunjukkan yang setara dengan sampel CUDA. Mereka menunjukkan bagaimana Anda dapat menggunakan komputasi di CUDA dan merender di OpenGL pada GPU tanpa harus kembali ke CPU di antaranya. Tempat lain di mana Apple banyak menggunakan GPU adalah untuk tugas-tugas AI. Setiap kali Neural Engine tidak mendukung operasi dalam suatu model, CoreML akan secara otomatis melakukan fallback pada GPU untuk kinerja yang lebih baik. Meskipun ini sangat berguna dan menarik,

Saya memilih database relasional karena kebetulan saya sangat menyukai database dan telah memikirkan sejumlah desain untuknya, beberapa di antaranya telah saya buat prototipenya selama bertahun-tahun. Database relasional juga menarik karena menggunakan string dan nilai null. Contoh AI dan simulator partikel, meskipun sangat mengesankan, hanya menggunakan pelampung dan bilangan bulat.

Implementasi yang saya bangun dapat ditemukan di sini: MetalDB Github

Ide desain

Saya tidak ingat apakah itu tepat di awal atau di tengah proses, namun saya terinspirasi oleh dokumentasi dari BigQuery Query Plans yang berbicara tentang grafik tahapan kueri yang menyusun rencana eksekusi kueri.

Salah satu batasan desain utama dengan Metal adalah semua memori harus berukuran statis pada waktu kompilasi. Ini menghadirkan tantangan karena saya tidak dapat menyalin string karena saya tidak tahu berapa banyak string yang ada di baris database, atau berapa lama setiap string pada waktu kompilasi.

Saya pikir menggunakan algoritme penjumlahan awalan untuk menyalin semua data kembali dari GPU ke CPU dengan cara yang efisien akan paling sederhana jika setiap utas memproses satu baris. Saya juga perlu menggunakan blok tersinkronisasi terbesar yang tersedia, yang dalam Metal adalah ThreadGroup.

Sebagian sebagai pengoptimalan, dan sebagian lagi sebagai tantangan pribadi, saya ingin memaksimalkan jumlah pekerjaan yang dilakukan pada GPU. Untuk alasan tersebut, saya memilih untuk memulai dengan membaca file CSV di CPU, dan melakukan penguraian CSV di GPU.

Saat mengimplementasikan, saya juga ingin dapat menguji database pada CPU sehingga pengujian unit dapat dilakukan dalam debugger. Untuk alasan ini, saya menyiapkan pipa build agar semua kernel Metal saya ditulis sebagai header. Akibatnya saya bisa memasukkannya ke dalam file kernel Metal, tetapi juga memasukkannya ke dalam pengujian di C++. Desain ini juga akan memungkinkan saya untuk mendefinisikan konstanta dan tipe di header Metal dan menjamin mereka selalu sama dalam kode C++ yang akan menyebutnya.

Latar belakang tentang Threadgroups dan konsep Metal

Sebagai latar belakang untuk ide dan penjelasan lebih lanjut, Metal execution disusun dalam grid. Grid adalah grup ThreadGroups 1D, 2D atau 3D. ThreadGroup adalah grup yang dapat disinkronkan di dalam kisi itu. Utas di dalam ThreadGroup dipecah dan dieksekusi menjadi grup lebih lanjut, yang disebut warps.

Utas adalah blok paling dasar dalam pemrograman GPU, dan secara kasar diterjemahkan menjadi model utas pada inti CPU. Ini adalah eksekusi instruksi tunggal, linier, dalam urutan. Utas memiliki register yang dapat diakses secara langsung serta membaca dan menulis ke memori bersama. Ini adalah model memori yang berbeda dari pada CPU, tetapi itu berada di luar cakupan artikel ini.

Sebuah warp (disebut SIMD dalam dokumentasi Metal) seringkali merupakan grup yang terdiri dari 16 atau 32 utas. Instruksi yang sama harus dijalankan pada waktu yang sama pada semua utas dalam warp, meskipun berpotensi pada data yang berbeda (SIMD, Instruksi Tunggal, Banyak Data). Jika beberapa utas mengambil jalur yang berbeda dalam kode, semua utas di dalam warp itu harus menunggu semua cabang dieksekusi secara berurutan. Ini mengarah pada perancangan kode GPU dengan cabang sesedikit mungkin, sehingga Anda membuat semua utas dalam warp sibuk sebanyak mungkin.

Sistem lain seperti CUDA dan OpenCL memiliki konsep serupa, hanya dengan nama yang berbeda.

Penerapan

Tautan ke implementasi:https://github.com/mattpaletta/metaldb

Menurut pendapat saya, menurut saya paling masuk akal untuk membicarakan implementasi dalam urutan aliran data melalui sistem. Namun, ini hampir kebalikan sempurna dari bagaimana saya menerapkannya.

Biner

Hasil akhir yang dihasilkan sangat sederhana. Ini adalah panggilan biner metaldbdan hanya memiliki fungsi utama di dalamnya. Saya membuat aplikasi ini sangat ringan sehingga saya, serta yang lainnya, dapat menggunakan kembali pustaka internal dengan mudah sebagai bagian dari pustaka dan aplikasi lain di masa mendatang.

Mesin

Engine adalah tempat sebagian besar logika sistem dikoordinasikan. Engine berinteraksi dengan QueryPlanner, yang diimplementasikan di pustaka QueryPlanner, serta Scheduler, yang bertanggung jawab untuk menjalankan dan mengoordinasikan pelaksanaan rencana kueri yang dihasilkan.

Pengurai Kueri

Query Parser adalah komponen yang bertanggung jawab untuk mengubah kueri seperti SQL menjadi AST yang dapat diurai dengan lebih mudah oleh sistem lainnya.

Versi pertama database ini tidak mengimplementasikan Query Parser. Sebagai gantinya, saya telah meng-hardcode AST untuk berbagai pertanyaan yang ingin saya uji. Menulis parser dan menghasilkan AST, meskipun kedengarannya sangat menarik, adalah sesuatu yang telah saya lakukan di proyek lain, dan bukan fokus proyek ini.

Saya juga tidak bermaksud agar proyek ini menjadi database siap produksi. Oleh karena itu tidak memerlukan parser kueri saat ini, tetapi semua stub tersedia untuk saya terapkan di lain waktu jika saya mau.

Selain sistem yang menerima string kueri, saya berencana untuk akhirnya mengimplementasikan API Dataframe, mirip dengan Panda, tetapi dalam C++. Dari sudut pandang saya, API semacam ini akan lebih mudah digunakan oleh perpustakaan lain. Ini juga menghemat langkah perpustakaan lain yang harus menghasilkan string kueri hanya untuk kemudian segera diurai oleh parser. API Dataframe ini juga dibiarkan sebagai pekerjaan di masa mendatang.

Sebagai dataset uji, saya pertama kali menggunakan dataset Iris yang tersedia untuk umum . Saya memilih dataset ini karena relatif kecil, dalam format CSV, dan kebanyakan angka, tanpa nilai null.

Setelah kumpulan data itu berfungsi, saya ingin mencoba kumpulan data yang jauh lebih besar dengan banyak file. Untuk ini saya menggunakan New York Taxi Dataset . Kumpulan data yang lebih besar ini membuktikan beberapa tantangan menarik yang tidak saya duga, lebih lanjut tentang ini nanti.

Perencana Kueri

Setelah Query Parser menghasilkan AST, komponen selanjutnya adalah Query Planner. Ini bertanggung jawab untuk mengubah AST menjadi rencana eksekusi yang dioptimalkan.

Langkah pertama membuat rencana eksekusi yang optimal adalah membuat rencana sama sekali. Terinspirasi oleh referensi BigQuery , saya menyukai ide memecah rencana eksekusi menjadi grafik "Tahapan". Di BigQuery, setiap tahapan terdiri dari satu atau beberapa langkah. Setiap langkah bisa berupa baca atau tulis, agregat atau gabungan, dll. Saya tidak terlalu ingin turun ke perincian langkah, tetapi saya memiliki konsep serupa, saya sebut "parsial".

Untuk beralih dari AST ke grafik tahapan, pertama-tama saya membuat daftar file pada disk untuk tabel. Selanjutnya saya pergi ke daun AST dan untuk masing-masing, saya membuat tahap baru yang akan membaca file itu.

Saat saya berjalan kembali ke atas pohon, saya memutuskan apakah saya akan membuat sebagian baru sebagai bagian dari panggung yang ada atau membuat panggung baru. Poin kuncinya adalah ketika saya harus beralih dari GPU ke CPU atau sebaliknya untuk satu langkah, saya membuat tahapan baru. Ini berarti sebanyak mungkin data dapat diproses pada GPU sambil meminimalkan waktu transfer antara CPU dan GPU. Ini sangat relevan untuk perangkat yang tidak memiliki memori terpadu.

Setiap tahap memiliki daftar parsial tunggal untuk dijalankan. Ini nantinya akan diterjemahkan sebagai instruksi ke GPU dalam tahap itu, karena kita akan mempelajari lebih lanjut di bagian tentang penjadwal.

Setiap kali saya membuat tahapan baru, saya menyisipkan "Shuffle Instruction", yang memberi tahu GPU untuk menyalin informasi kembali ke CPU.

Di masa mendatang, saya juga akan menulis pengoptimal yang dapat menulis ulang kueri untuk meminimalkan jumlah data yang dibaca dari setiap file dan disalin kembali ke CPU setelah dibaca.

Penjadwal

Penjadwal bertanggung jawab atas eksekusi paralel kueri. Saya tergoda untuk menulis perpustakaan multithread saya sendiri untuk melakukan ini. Saya akhirnya menulis implementasi saya di atas TaskFlow , pustaka grafik tugas C++ sumber terbuka.

Pada level tinggi, pembuatan grafik tugas mengikuti grafik tahapan. Setiap tahap adalah tugas dalam grafik, dan bergantung pada anak-anaknya.

Dalam satu tahap, setiap bagian, daftar langkah-langkah yang harus dilakukan pada CPU atau GPU, diperluas secara berurutan. Karena setiap bagian sedang didaftarkan, ia memiliki beberapa tugas di dalam grafik tugas yang dapat dihubungkan.

Tugas utama yang dapat dihubungkan, adalah tugas penyandian dari tugas sebelumnya. Sebagian harus membuat tugas baru yang bergantung pada tugas penyandian parsial induk. Ini menggunakan Encoder yang diteruskan untuk menyandikan dirinya sendiri menjadi representasi serial yang dapat dikirim ke GPU. Untuk sebagian besar tugas, hanya ini yang diperlukan dan implementasi parsial ada di GPU di Metal.

Tugas lain yang tersedia adalah tugas kerja. Ini ada jika sebagian ingin mengesampingkan sesuatu tentang bagaimana pekerjaan dieksekusi untuk sebagian itu alih-alih perilaku default.

Sebagian besar tugas membaca buffer dari satu atau beberapa tahapan anak dan menulis ke buffer keluarannya. Instruksi baca unik karena harus dibaca dari disk, bukan dari buffer anak.

Instruksi baca mengatur rantai tugas yang membaca file CSV (satu-satunya jenis file yang saat ini diterapkan) yang telah ditetapkan dan membacanya ke dalam buffer. Saat membaca ke buffer, ia melacak offset baris saat ini dan menyimpannya sebagai bagian dari RawTableobjek, dijelaskan di bawah.

Setelah file dibaca, GPU bebas untuk mulai memproses baris. Desain database membutuhkan satu utas per baris. Metal kebetulan memiliki batasan berapa banyak utas yang dapat ditetapkan per ThreadGroup. Oleh karena itu, pertama-tama kami membagi baris menjadi beberapa buffer yang masing-masing akan dikirim ke GPU secara terpisah.

TaskFlow memungkinkan subtugas dinamis dalam suatu tugas. Ketika saya mendapatkan RawTable, saya menanyakan jumlah utas yang dapat saya jadwalkan oleh Metal dan memecah baris asli menjadi potongan-potongan sebesar itu.

Setiap potongan kemudian dikirim ke GPU secara paralel.

Setelah semua potongan diproses, saya menjalankan tugas penggabungan yang menyalin semua OutputRowobjek dari GPU dan menggabungkannya menjadi satu raksasa OutputRowsehingga tahap berikutnya dapat membacanya bersama.

Di masa mendatang, saya ingin mengoptimalkan pemisahan beberapa batch. Segera setelah batch telah dipecah, itu dapat dikirim ke GPU. Segera setelah potongan itu kembali, itu dapat disalin ke buffer terakhir sementara tugas lainnya diproses secara tidak sinkron.

Selain itu, saya ingin membebaskan yang asli RawTablesetelah semua baris dipecah menjadi potongan-potongan, yang masing-masing menyimpan salinannya. Selain itu, saya harus dapat membebaskan buffer keluaran dari potongan segera setelah disalin ke buffer akhir, mengurangi jumlah total memori yang diperlukan.

Instruksi ParseRow

ParseRowInstructionDimulai dengan premis sederhana . Diberikan daftar indeks untuk awal setiap baris dan informasi tentang jumlah baris dan jenis kolom, uraikan nilai untuk baris tertentu, masukkan ke jenis yang benar.

Jenis kolom paling sederhana adalah string. Untuk baris N , kita dapat melompat ke awal baris tersebut dengan melihat indeksnya, yang disimpan oleh CPU saat kita membaca file dari disk. Kami kemudian bisa mendapatkan pointer ke indeks itu. Ini adalah awal dari baris. Akhir dari setiap kolom adalah posisi sebelum koma berikutnya (menandai kolom berikutnya) saat kita maju satu karakter pada satu waktu, atau satu sebelum awal baris berikutnya (jika itu kolom terakhir dari baris), atau satu sebelum akhir buffer (jika itu adalah kolom terakhir dari baris terakhir).

Instruksi membaca setiap kolom sebagai string terlebih dahulu. Itu mem-parsing kolom persis seperti yang dijelaskan dan membacanya sebagai string, karakter demi karakter. Sekarang untuk membaca kolom selanjutnya, kita mulai dari awal baris. Ketika kita sampai pada koma pertama, kita menandainya sebagai awal, dan berlanjut sampai koma setelah itu. Proses berulang untuk kolom berikutnya.

Jika kami memiliki bilangan bulat, kami meneruskan penunjuk ke awal dan akhir string ke stoifungsi khusus. Ini mirip dengan yang ada di pustaka standar C, yang mengubah string menjadi representasi bilangan bulat. Saya juga menulis versi saya sendiri stof.

Seperti yang dapat Anda bayangkan, membaca setiap kolom dari awal baris setiap kali sangat lambat dan ada banyak pekerjaan rangkap. Kita bisa melakukan lebih baik, jauh lebih baik.

Realisasi pertama dalam mengoptimalkan pencarian awal kolom adalah, seringkali jumlah kolomnya sedikit. Saya telah memilih 16 sebagai jumlah kolom yang berubah-ubah untuk di-cache.

Dengan level cache pertama ini, jika saya membaca kolom dalam 16 kolom pertama, saya mencoba dan membaca pointer yang sebelumnya di-cache untuk kolom itu. Jika bukan nol, saya sudah memiliki nilainya. Baris tidak dapat diubah, jadi penunjuk harus valid, dan proses selesai!

Jika penunjuknya nol, saya dapat mengulangi cache saya mundur dari indeks kolom ke-16 sampai saya menemukan kolom yang sebelumnya di-cache atau saya sampai ke entri pertama.

Dari mana pun saya berhenti, saya dapat mengulangi baris dengan cara yang naif, satu karakter dalam satu waktu. Setiap kali saya menemukan koma, saya menyimpan pointer ke awal kolom itu di cache saya sehingga kueri berikutnya dapat langsung menuju ke sana.

Ini berarti bahwa akses acak ke 16 kolom pertama pada dasarnya harus gratis karena menjadi pencarian pointer langsung. Ini tidak termasuk akses pertama, yaitu O(n) .

Bagaimana dengan baris dengan lebih dari 16 kolom? Saya sudah tahu di mana kolom ke-15 (mulai dari 0), jadi saya bisa langsung melompat ke kolom ke-15 dan kemudian menginterasi dengan cara yang naif setelah itu. Jika saya tidak tahu di mana kolom ke-15, saya dapat menghitung dan menyimpannya dengan cepat.

Ini cukup bagus, kecuali ada satu optimasi lagi yang bisa dilakukan. Realisasi lainnya adalah bahwa di dalam ParseRowInstruction saat membangun baris keluaran, ia mengakses kolom secara berurutan. Selain cache acak ukuran tetap untuk 16 kolom pertama, kita dapat menyimpan penunjuk tambahan yang menyimpan awal kolom terakhir yang diakses, dan indeks kolom tersebut. Ini memungkinkan pencarian pointer langsung untuk akses berurutan untuk sejumlah kolom, tanpa harus menyimpan pointer dalam jumlah tak terbatas, seperti di tingkat pertama caching. Tentu saja, kedua lapisan caching ini bekerja sama. Saat kami memperbarui 16 nilai pertama, kami juga memperbarui last_accessedpointer.

Saat berjalan di GPU, setiap utas bertanggung jawab atas satu baris. Jadi setiap utas memiliki cache berlapis-lapisnya sendiri seperti yang dijelaskan. Cache juga melacak baris mana yang kita cache. Jika berbeda dengan yang diminta, kami mereset cache, sehingga kami tahu cache selalu relevan. Dimungkinkan untuk memperluas ini untuk mencakup kasus penggunaan membaca beberapa baris atau berbagi cache antar utas, tetapi ini berada di luar cakupan implementasi awal.

Instruksi Proyeksi

ProjectionInstructionPerbandingannya sangat sederhana . Itu diberikan daftar indeks kolom untuk diambil. Itu membuat objek TempRow baru dan menyalin kolom tersebut dari TempRow terakhir, memperbarui metadata di objek TempRow baru.

Instruksi Filter

Implementasi dasar dari FilterInstructiondirancang untuk mengevaluasi beberapa baris terhadap beberapa ekspresi yang mengembalikan salah satu trueatau false.

Ini diimplementasikan sebagai mesin virtual berbasis stack. Alokasi tumpukan ditetapkan pada waktu kompilasi dan karenanya selalu mengalokasikan ukuran maksimumnya.

Tumpukan itu agak menarik untuk diterapkan. Saya memilih untuk mendesain bytecode untuk VM untuk memasukkan tipe serta instruksi untuk mentransmisikan satu tipe ke tipe lainnya. Implementasi tumpukan memungkinkan data yang heterogen, tetapi penelepon bertanggung jawab untuk menyediakan jenisnya.

Dalam tumpukan normal, Anda dapat membuat kotak untuk suatu objek, dan kotak tersebut akan menyimpan jenis objek serta penunjuk ke objek tersebut. Dalam hal ini, compiler (belum diimplementasikan) bertanggung jawab untuk menulis bytecode untuk menyertakan semua casting yang diperlukan. Hal ini memungkinkan runtime untuk mendorong bilangan bulat ke tumpukan, yaitu xbyte, dan kemudian saat membaca bilangan bulat, ia dapat xmengeluarkan byte dari tumpukan dan mendapatkan bilangan bulat yang sama. Tidak diperlukan kotak atau pengecoran dinamis. Ini menempatkan tanggung jawab pada kompiler untuk memperbaiki semua tipe, tetapi itu diserahkan untuk implementasi di masa mendatang.

Instruksi Keluaran

digunakan untuk menggabungkan semua data dari masing-masing utas di OutputInstructiondalam ThreadGroup dan menghapus semua data duplikat yang dibutuhkan setiap utas, tetapi itu hanya perlu disalin sekali ke CPU, dan secara efisien memasukkannya ke dalam satu buffer besar .

Langkah pertama adalah setiap baris (setiap utas) menghitung ukurannya sendiri. Kemudian kami menjalankan jumlah awalan dari ukuran. Ini memberi kami indeks di mana kami tahu kami dapat mulai menulis data kami.

Jumlah awalan adalah algoritme yang sering digunakan dalam perhitungan GPU di mana diberikan array bilangan bulat, mengembalikan array baru di mana untuk setiap indeks i, berisi jumlah semua item yang kurang dari i . Jika penjumlahan mencakup item i untuk posisi i , maka disebut penjumlahan inklusif, jika tidak maka disebut penjumlahan eksklusif. Saya menggunakan jumlah eksklusif untuk implementasi saya.

Sebelum kita dapat mulai menulis data, utas harus mengoordinasikan penulisan header OutputRow. Untuk melakukan ini, baris pertama, yang bertanggung jawab untuk menulis tajuk, juga menambahkan ukuran tajuk ke ukurannya sendiri. Setelah kami melakukan penjumlahan awalan, kami juga menjalankan pengurangan ukuran baris sehingga utas pertama dapat menulis jumlah total byte ke header.

Setelah itu selesai, setiap baris dapat melompat ke offsetnya dari output jumlah awalan dan menyalin byte-nya ke buffer mulai dari titik itu secara paralel, dan kami dijamin tidak akan ada tabrakan.

TempRow

Itu TempRowadalah struktur data yang diedarkan saat data sedang diproses di Metal. Idealnya, kami akan mengalokasikan ukuran yang dapat diubah TempRowpada heap, untuk meminimalkan jejak memori, tetapi karena Metal tidak mendukung alokasi memori dinamis. Every TempRowadalah buffer dengan ukuran tetap. Saya memilihnya menjadi 1024 byte, atau 1 kilobyte. Bagian pertama TempRowadalah header, diikuti dengan data.

Nilai pertama di header adalah panjangnya. Ini penting karena data dimulai segera setelah header, dan header adalah ukuran variabel yang bergantung pada jumlah kolom dan jenisnya.

Byte berikutnya adalah jumlah kolom. Karena ini hanya 1 byte, maka jumlah maksimum kolom adalah 256. Saya rasa ini cukup banyak untuk sebagian besar kasus penggunaan.

N byte berikutnya adalah tipe kolom. Kolom dapat berupa salah satu dari: Integer, Float, Stringatau padanannya yang dapat dibatalkan. Nilai boolean hanya dinyatakan sebagai bilangan bulat.

Integer dan float selalu berukuran konstan, jadi kita tidak perlu menyimpan ukurannya di header, kecuali kolom nullable. Sebaliknya, sebuah string dapat memiliki sejumlah karakter. Oleh karena itu kami menyimpan ukuran semua kolom panjang variabel (string dan kolom opsional) dalam byte berikutnya. Sekali lagi, karena ukuran kolom hanya 1 byte, panjang maksimal string adalah 256 karakter.

Setelah header, semua data untuk kolom ditambahkan satu per satu.

Untuk membuat konstruksi TempRowlebih sederhana, ada kelas pembantu TempRowBuilderdi mana pemanggil dapat menulis semua tipe dan ukuran kolom, dll. ke dalam larik terpisah. The TempRowkemudian dapat dengan mudah dibangun dari pembangun dengan menyalin nilai-nilai.

Data dari kolom kemudian dapat ditambahkan secara berurutan. Ada metode pembantu untuk membantu menyalin dalam string, integer, dan float, dan menulisnya byte demi byte.

Ketika metode selanjutnya pergi untuk membaca TempRow, ada metode pembantu yang membaca dari header untuk menentukan indeks awal dan akhir dalam buffer untuk kolom itu, dan mengembalikan byte ke tipe yang sesuai. Penelepon bertanggung jawab untuk menanyakan ColumnTypekolom yang mereka minati, sebelum membacanya sebagai tipe itu.

Karena TempRowmembaca semua data secara langsung dari buffer berukuran tetap, itu bisa diadaptasi dengan mudah ke constexprkelas untuk aplikasi lain.

OutputRow

The OutputRowdibuat oleh OutputRowInstruction(dijelaskan di atas) dan berfungsi untuk memindahkan beberapa baris di sekitarnya yang memiliki skema yang sama. Akan sia-sia untuk menyalin semua TempRowobjek secara langsung karena setiap baris memiliki skema yang sama, sehingga ada banyak metadata duplikat. Sebagai gantinya, kami menyalin semua data ke dalam struktur tunggal sehingga kami dapat menyalinnya ke TempRowobjek terpisah jika diperlukan nanti, atau membaginya menjadi dua OutputRowobjek atau lebih jika diperlukan.

Mirip dengan TempRow, the OutputRowmemiliki definisi tajuk, meskipun sedikit berbeda dari TempRow. Nilai pertama seperti yang dijelaskan sebelumnya adalah ukuran header, tetapi nilai ini lebih besar, dengan 2 byte yang dialokasikan, bukan 1. Nilai selanjutnya adalah jumlah byte dalam OutputRow, dan ini adalah bilangan bulat 32-bit yang tidak ditandatangani. Setelah ini adalah jumlah kolom, dan ini hanya satu byte. Diikuti oleh tipe kolom, mirip dengan TempRow.

Setelah header, semua data ditambahkan. Karena OutputRowselalu dibangun dari satu atau lebih TempRowatau dari yang lain OutputRow, kita dapat menghitung ukuran data setiap baris secara paralel menggunakan algoritma penjumlahan awalan, dan menulis ke buffer data secara paralel.

Saat berjalan di Metal, OutputRowsecara statis dialokasikan menjadi ukuran tetap 1.000.000 byte. Pada CPU, kita bisa lebih efisien dan menggunakan a std::vectorhanya mengalokasikan jumlah ruang yang kita perlukan.

Untuk lebih memfasilitasi setiap utas membaca dan menulis OutputRowsecara paralel, alih-alih ukuran kolom ukuran variabel yang ditulis di header seperti di TempRow, mereka malah ditambahkan ke data untuk kolom itu per baris. Jadi misalnya, baris dengan 2 bilangan bulat diikuti dengan string 3 karakter “abc”, akan memiliki format: <integer><integer>3abc. Pembaca OutputRow(saat ini hanya diimplementasikan pada CPU) mengetahui bahwa kolom adalah string, dan karena itu dapat melompat ke awal string untuk membaca isinya. Ukuran setiap baris tidak ditulis keOutputRow. Sebagai gantinya, pembaca mengulang melalui buffer dan mencatat awal setiap baris dan ukuran setiap kolom ukuran variabel untuk setiap baris. Hal ini dilakukan untuk menghemat ruang, tetapi dapat dioptimalkan untuk ditulis ke dalam header atau per baris, sehingga membaca OutputRowlebih efisien dan lebih cepat. Detail membaca, memisahkan, dan menggabungkan OutputRowobjek pada CPU telah dibahas secara singkat sebelumnya di bagian tentang Scheduler.

Pekerjaan masa depan

Saya mengerjakan proyek ini sebagai percobaan untuk melihat apakah itu mungkin. Ada banyak hal yang ingin saya terapkan, jika saya ingin membuatnya siap produksi, atau bahkan hanya menghabiskan lebih banyak waktu untuk prototipe daripada yang saya miliki.

Bug yang satu itu

Masalah pertama yang ingin saya selesaikan adalah (apa yang saya yakini sebagai bug di Xcode 13), di mana banyak utas ditugaskan utas 0 di dalam ThreadGroup. Beri tahu saya jika Anda punya ide. Ini menyebabkan banyak utas mencoba dan menulis tajuk. Hal ini menyebabkan header tergencet sebagian dengan data, tergantung pada urutan utas. Saya mencoba mencari di Google tentang hal itu, tetapi tidak dapat menemukan sumber yang sangat membantu. Saya pikir itu ada hubungannya dengan jumlah memori yang saya coba alokasikan untuk setiap utas. Sayangnya dokumentasi resmi Apple tidak menyebutkan apa pun tentang hal itu yang dapat saya temukan.

Mesin Kueri + Parser

Tugas besar berikutnya adalah mengimplementasikan parser dan mesin kueri sehingga database dapat menerima kueri seperti SQL dan mengubahnya menjadi paket kueri dan menjalankannya. Tugas ini juga melibatkan implementasi API DataFrame, atau menulis dalam berbagai format ke disk, untuk digunakan oleh pustaka dan program lain.

Gabung + Kelompokkan Oleh

Memperluas spesifikasi SQL, akan menyenangkan untuk dapat menghitung gabungan dan klausa Grup Menurut. Saya pikir cara naif untuk mengimplementasikan gabungan adalah menghitung setiap baris mentah pada GPU secara paralel, dan kemudian melakukan hash-join pada CPU, sekali per potongan. Namun, mungkin lebih efisien daripada mencari cara untuk mengirimkan satu potongan dari 2 tabel berbeda yang ingin Anda gabungkan pada saat yang sama, dan minta GPU mengembalikan baris yang digabungkan.

Untuk Group By, Anda bisa melakukannya di CPU, atau mungkin melakukan agregasi parsial di GPU. Atau Anda dapat melakukan beberapa kombinasi di mana Anda melakukan pemrosesan mentah awal pada GPU, dan kemudian memiliki kernel berbeda yang Anda jalankan di mana diberikan satu set baris, menghitung grup untuk setiap baris dalam set tersebut. Ini akan memungkinkan Anda untuk dengan cepat mengelompokkan baris pada CPU tempat Anda dapat mengalokasikan lebih banyak data untuk menampung baris, sambil memanfaatkan sifat paralel GPU untuk menghitung grup secara paralel.

Sistem Terdistribusi

Jika sistem ini akan digunakan dalam produksi, kemungkinan sistem ini harus dapat memanfaatkan banyak mesin. Saya dapat membayangkan jaringan heterogen dari perangkat yang terhubung dengan Apple (dan non-Apple) bekerja bersama. Bayangkan sebuah iPhone sebagai pengontrol host mengirimkan perintah ke mesin lain, dan sekelompok iPad yang masing-masing memproses data yang mereka miliki secara lokal dan mengirimkan baris yang diproses kembali ke pengontrol pusat. Alternatifnya, mungkin Anda memiliki penerapan cloud yang menjalankan kode yang sama di CPU dalam instans lambda AWS, atau di beberapa GPU dengan server Mac Pro di tempat. Semua sistem ini dapat bekerja sama untuk memberi Anda akses responsif yang sangat cepat ke kumpulan data yang sangat besar dengan perangkat yang (menurut saya) masih memiliki banyak kekuatan pemrosesan yang belum dimanfaatkan.

Kurangi Jejak Memori

Sebagai pengoptimalan lainnya, terutama karena saya ingin ini berjalan di perangkat apa pun yang menjalankan Metal, alangkah baiknya menjaga jejak memori sekecil mungkin sehingga kami dapat memaksimalkan sumber daya di perangkat untuk aplikasi pengguna akhir yang sedang berjalan . Idealnya, kita harus dapat membaca potongan file dari disk ke dalam memori, mengubahnya menjadi buffer untuk mengirimkannya ke GPU, dan kemudian membebaskan potongan memori tersebut. Saya mencoba merancang sistem seperti itu dengan menggunakan shared_ptr, sehingga saya akan memiliki sistem alokasi memori penghitungan referensi untuk buffer. Namun dalam praktiknya saya menemukan bahwa karena pustaka tugas yang saya gunakan tidak tahu apakah perlu menjalankan kembali grafik tugas dengan banyak input, pustaka tidak membebaskan lambda yang menangkap referensi ke buffer saat berjalan. Ini berarti bahwashared_ptryang ditangkap oleh lambda masih direferensikan, dan karena itu tidak mengosongkan memorinya hingga setelah grafik tugas dihancurkan, yang hanya terjadi ketika seluruh grafik selesai dieksekusi.

Kesimpulan

Secara keseluruhan saya sangat senang bekerja dan memikirkan proyek ini. Itu sangat berbeda dari banyak proyek lain yang pernah saya lakukan. Saya harap Anda menikmati membaca artikel ini. Implementasi penuh saya ditautkan di bagian atas artikel ini. Jika Anda memiliki komentar atau ide tentang hal-hal yang Anda suka atau ingin Anda lakukan secara berbeda, jangan ragu untuk menghubungi saya. Terima kasih!