Vortex - format file Columnar berkinerja tinggi

xguru · 2024-10-17T11:01:27+09:00

"LLVM untuk format berkas kolumnar" Format berkas berbasis kolom yang mencakup toolkit untuk menangani array Apache Arrow terkompresi melalui memori, disk, dan jaringan Penerus ambisius Apache Parquet, mendukung pembacaan akses acak 100–200x lebih cepat dan pemindaian 2–10x lebih cepat, sambil mempertahankan rasio kompresi dan throughput penulisan yang hampir sama dengan Parquet yang menggunakan zstd Juga mendukung tabel yang sangat besar (puluhan ribu kolom) serta dekompresi di atas GPU Vortex dirancang untuk berperan pada format berkas berbasis kolom seperti halnya Apache DataFusion berperan pada mesin kueri Artinya, fokus pada skalabilitas tinggi, kecepatan sangat tinggi, dan fitur lengkap bawaan [!Perhatian] > Masih dalam pengembangan aktif Fitur utama: Logical Types - Definisi skema yang tidak membuat asumsi apa pun tentang tata letak fisik Zero-Copy to Arrow - Array Vortex yang telah dinormalisasi (canonicalized) dapat dikonversi ke array Apache Arrow tanpa copy Extensible Encodings - Kumpulan tata letak fisik berbasis plugin. Selain encoding yang kompatibel dengan Arrow, juga menyediakan encoding modern (FastLanes, ALP, FSST, dll.) sebagai ekstensi Cascading Compression - Data dapat dikompresi secara rekursif dengan beberapa encoding bertingkat Pluggable Compression Strategies - Compressor bawaan berbasis BtrBlocks, tetapi strategi lain juga mudah digunakan Compute - Kernel komputasi dasar yang bekerja pada data ter-encoding (misalnya filter pushdown) Statistics - Setiap array memiliki statistik ringkasan yang dihitung secara opsional saat dibaca. Dapat digunakan oleh kernel komputasi dan compressor Serialization - Serialisasi zero-copy untuk array bagi IPC dan format berkas Columnar File Format (sedang dikerjakan) - Format berkas modern untuk menyimpan data array terkompresi menggunakan pustaka serde Vortex. Dioptimalkan untuk pembacaan akses acak dan pemindaian sangat cepat. Ditujukan sebagai penerus Apache Parquet Ikhtisar: Logical vs Physical Salah satu prinsip desain inti Vortex adalah pemisahan ketat antara aspek logis dan fisik Contoh: array Vortex didefinisikan oleh tipe data logis (tipe elemen skalar) dan encoding fisik (tipe array itu sendiri) Encoding bawaan terutama dirancang untuk memodelkan format in-memory Apache Arrow. Ada juga encoding bawaan (sparse, chunked) yang digunakan sebagai komponen berguna untuk encoding lain. Encoding ekstensi terutama ditujukan untuk memodelkan array in-memory terkompresi seperti length encoding atau dictionary encoding vortex-serde dirancang untuk menangani detail fisik tingkat rendah dari array Vortex. Pilihan encoding yang digunakan atau bagaimana data dipecah secara logis menjadi chunk diserahkan kepada implementasi Compressor Salah satu sifat unik dari format berkas Vortex (yang sedang dikembangkan) adalah tata letak fisik data dienkode ke dalam footer berkas. Dengan ini, format berkas menjadi secara efektif mendeskripsikan dirinya sendiri, dan dapat berevolusi tanpa merusak kompatibilitas spesifikasi format berkas Dirancang untuk mendukung kompatibilitas maju dengan secara opsional menyertakan decoder WASM di dalam berkas itu sendiri. Ini diharapkan membantu menghindari pembekuan dini yang telah menjadi masalah pada format berkas kolumnar lainnya Komponen Logical Types Sistem tipe Vortex masih terus berubah. Tipe logis saat ini: Null Bool Integer(8, 16, 32, 64) Float(16, b16, 32, 64) Binary UTF8 Struct List (diimplementasikan sebagian) Date/Time/DateTime/Duration (diimplementasikan sebagai tipe ekstensi) TODO: Decimal, FixedList, Tensor, Union Canonical/Flat Encodings Vortex secara bawaan menyertakan encoding "Flat" yang dirancang agar zero-copy dengan Apache Arrow. Ini adalah representasi kanonis dari setiap tipe data logis. Encoding kanonis yang saat ini didukung: Null Bool Primitive (Integer, Float) Struct VarBin (Binary, UTF8) VarBinView (Binary, UTF8) Extension Encoding lainnya akan ditambahkan nanti Compressed Encodings Vortex mencakup sekumpulan encoding yang sangat data-parallel dan tervectorisasi. Masing-masing encoding ini memiliki implementasi array in-memory terkompresi yang sesuai, sehingga dekompresi dapat ditunda. Saat ini tersedia encoding berikut: Adaptive Lossless Floating Point (ALP) BitPacked (FastLanes) Constant Chunked Delta (FastLanes) Dictionary Fast Static Symbol Table (FSST) Frame-of-Reference Run-end Encoding RoaringUInt RoaringBool Sparse ZigZag Encoding lainnya akan ditambahkan nanti Compression Strategi kompresi default Vortex didasarkan pada paper BtrBlocks Secara kasar, Vortex mengambil sampel minimal ~1% data untuk setiap chunk data Lalu mencoba mengompresnya secara (rekursif) dengan sekumpulan encoding ringan Dari sana dipilih kombinasi encoding dengan kinerja terbaik untuk meng-encode seluruh chunk Ini terdengar sangat mahal, tetapi dengan hanya statistik dasar pada chunk, banyak encoding dapat dipangkas dengan murah agar ruang pencarian tidak meledak Compute Vortex memungkinkan setiap encoding mengkhususkan implementasi fungsi komputasi agar sedapat mungkin menghindari dekompresi. Misalnya, untuk memfilter array UTF8 yang dienkode dengan dictionary, lebih murah memfilter dictionary-nya terlebih dahulu Vortex tidak berusaha menjadi mesin komputasi penuh, melainkan hanya mengimplementasikan operasi komputasi dasar yang mungkin diperlukan untuk pemindaian efisien dan pushdown Statistics Array Vortex memiliki statistik ringkasan yang dihitung secara malas Berbeda dari pustaka array lain, statistik ini dapat diisi dari format disk seperti Parquet dan dipertahankan apa adanya hingga ke mesin komputasi Statistik dapat digunakan oleh kernel komputasi dan compressor Statistik saat ini: BitWidthFreq TrailingZeroFreq IsConstant IsSorted IsStrictSorted Max Min RunCount TrueCount NullCount Serialization / Deserialization (Serde) Tujuan implementasi vortex-serde: Mendukung pemindaian (proyeksi kolom + pemfilteran baris) dengan zero-copy dan zero heap allocation Mendukung akses acak dalam waktu konstan atau nyaris konstan Menyampaikan informasi statistik seperti apakah data terurut kepada konsumen Menyediakan format IPC untuk mengirim array antarproses Menyediakan format berkas yang dapat diperluas dan terbaik di kelasnya untuk menyimpan data kolumnar di disk atau object storage Integrasi dengan Apache Arrow Apache Arrow adalah standar de facto untuk interoperabilitas data array kolumnar. Karena itu, Vortex secara alami dirancang agar semaksimal mungkin kompatibel dengan Apache Arrow Semua array Arrow dapat dikonversi menjadi array Vortex tanpa copy. Array Vortex yang dibuat dari array Arrow juga dapat dikonversi kembali ke Arrow tanpa copy Perlu dicatat bahwa Vortex dan Arrow memiliki tujuan yang berbeda, tetapi saling melengkapi Vortex membedakan dirinya dari Arrow dengan memisahkan secara eksplisit tipe logis dan encoding fisik. Ini memungkinkan Vortex memodelkan array yang lebih kompleks sambil tetap mengekspos antarmuka logis Contoh: Vortex dapat memodelkan ChunkedArray UTF8 di mana chunk pertama menggunakan run-length encoding dan chunk kedua menggunakan dictionary encoding. Di Arrow, RunLengthArray dan DictionaryArray adalah tipe terpisah yang tidak kompatibel, sehingga tidak dapat digabungkan dengan cara seperti ini

(github.com/spiraldb)

9 poin oleh xguru 2024-10-17 | Belum ada komentar. | Bagikan ke WhatsApp

"LLVM untuk format berkas kolumnar"
Format berkas berbasis kolom yang mencakup toolkit untuk menangani array Apache Arrow terkompresi melalui memori, disk, dan jaringan
Penerus ambisius Apache Parquet, mendukung pembacaan akses acak 100–200x lebih cepat dan pemindaian 2–10x lebih cepat, sambil mempertahankan rasio kompresi dan throughput penulisan yang hampir sama dengan Parquet yang menggunakan zstd
- Juga mendukung tabel yang sangat besar (puluhan ribu kolom) serta dekompresi di atas GPU
Vortex dirancang untuk berperan pada format berkas berbasis kolom seperti halnya Apache DataFusion berperan pada mesin kueri
- Artinya, fokus pada skalabilitas tinggi, kecepatan sangat tinggi, dan fitur lengkap bawaan

[!Perhatian] > Masih dalam pengembangan aktif

Fitur utama:
- Logical Types - Definisi skema yang tidak membuat asumsi apa pun tentang tata letak fisik
- Zero-Copy to Arrow - Array Vortex yang telah dinormalisasi (canonicalized) dapat dikonversi ke array Apache Arrow tanpa copy
- Extensible Encodings - Kumpulan tata letak fisik berbasis plugin. Selain encoding yang kompatibel dengan Arrow, juga menyediakan encoding modern (FastLanes, ALP, FSST, dll.) sebagai ekstensi
- Cascading Compression - Data dapat dikompresi secara rekursif dengan beberapa encoding bertingkat
- Pluggable Compression Strategies - Compressor bawaan berbasis BtrBlocks, tetapi strategi lain juga mudah digunakan
- Compute - Kernel komputasi dasar yang bekerja pada data ter-encoding (misalnya filter pushdown)
- Statistics - Setiap array memiliki statistik ringkasan yang dihitung secara opsional saat dibaca. Dapat digunakan oleh kernel komputasi dan compressor
- Serialization - Serialisasi zero-copy untuk array bagi IPC dan format berkas
- Columnar File Format (sedang dikerjakan) - Format berkas modern untuk menyimpan data array terkompresi menggunakan pustaka serde Vortex. Dioptimalkan untuk pembacaan akses acak dan pemindaian sangat cepat. Ditujukan sebagai penerus Apache Parquet

Ikhtisar: Logical vs Physical

Salah satu prinsip desain inti Vortex adalah pemisahan ketat antara aspek logis dan fisik
- Contoh: array Vortex didefinisikan oleh tipe data logis (tipe elemen skalar) dan encoding fisik (tipe array itu sendiri)
Encoding bawaan terutama dirancang untuk memodelkan format in-memory Apache Arrow. Ada juga encoding bawaan (sparse, chunked) yang digunakan sebagai komponen berguna untuk encoding lain. Encoding ekstensi terutama ditujukan untuk memodelkan array in-memory terkompresi seperti length encoding atau dictionary encoding
vortex-serde dirancang untuk menangani detail fisik tingkat rendah dari array Vortex. Pilihan encoding yang digunakan atau bagaimana data dipecah secara logis menjadi chunk diserahkan kepada implementasi Compressor
Salah satu sifat unik dari format berkas Vortex (yang sedang dikembangkan) adalah tata letak fisik data dienkode ke dalam footer berkas. Dengan ini, format berkas menjadi secara efektif mendeskripsikan dirinya sendiri, dan dapat berevolusi tanpa merusak kompatibilitas spesifikasi format berkas
Dirancang untuk mendukung kompatibilitas maju dengan secara opsional menyertakan decoder WASM di dalam berkas itu sendiri. Ini diharapkan membantu menghindari pembekuan dini yang telah menjadi masalah pada format berkas kolumnar lainnya

Komponen

Logical Types

Sistem tipe Vortex masih terus berubah. Tipe logis saat ini:
- Null
- Bool
- Integer(8, 16, 32, 64)
- Float(16, b16, 32, 64)
- Binary
- UTF8
- Struct
- List (diimplementasikan sebagian)
- Date/Time/DateTime/Duration (diimplementasikan sebagai tipe ekstensi)
- TODO: Decimal, FixedList, Tensor, Union

Canonical/Flat Encodings

Vortex secara bawaan menyertakan encoding "Flat" yang dirancang agar zero-copy dengan Apache Arrow. Ini adalah representasi kanonis dari setiap tipe data logis. Encoding kanonis yang saat ini didukung:
- Null
- Bool
- Primitive (Integer, Float)
- Struct
- VarBin (Binary, UTF8)
- VarBinView (Binary, UTF8)
- Extension
- Encoding lainnya akan ditambahkan nanti

Compressed Encodings

Vortex mencakup sekumpulan encoding yang sangat data-parallel dan tervectorisasi. Masing-masing encoding ini memiliki implementasi array in-memory terkompresi yang sesuai, sehingga dekompresi dapat ditunda. Saat ini tersedia encoding berikut:
- Adaptive Lossless Floating Point (ALP)
- BitPacked (FastLanes)
- Constant
- Chunked
- Delta (FastLanes)
- Dictionary
- Fast Static Symbol Table (FSST)
- Frame-of-Reference
- Run-end Encoding
- RoaringUInt
- RoaringBool
- Sparse
- ZigZag
- Encoding lainnya akan ditambahkan nanti

Compression

Strategi kompresi default Vortex didasarkan pada paper BtrBlocks
- Secara kasar, Vortex mengambil sampel minimal ~1% data untuk setiap chunk data
- Lalu mencoba mengompresnya secara (rekursif) dengan sekumpulan encoding ringan
- Dari sana dipilih kombinasi encoding dengan kinerja terbaik untuk meng-encode seluruh chunk
- Ini terdengar sangat mahal, tetapi dengan hanya statistik dasar pada chunk, banyak encoding dapat dipangkas dengan murah agar ruang pencarian tidak meledak

Compute

Vortex memungkinkan setiap encoding mengkhususkan implementasi fungsi komputasi agar sedapat mungkin menghindari dekompresi. Misalnya, untuk memfilter array UTF8 yang dienkode dengan dictionary, lebih murah memfilter dictionary-nya terlebih dahulu
Vortex tidak berusaha menjadi mesin komputasi penuh, melainkan hanya mengimplementasikan operasi komputasi dasar yang mungkin diperlukan untuk pemindaian efisien dan pushdown

Statistics

Array Vortex memiliki statistik ringkasan yang dihitung secara malas
Berbeda dari pustaka array lain, statistik ini dapat diisi dari format disk seperti Parquet dan dipertahankan apa adanya hingga ke mesin komputasi
Statistik dapat digunakan oleh kernel komputasi dan compressor
Statistik saat ini:
- BitWidthFreq
- TrailingZeroFreq
- IsConstant
- IsSorted
- IsStrictSorted
- Max
- Min
- RunCount
- TrueCount
- NullCount

Serialization / Deserialization (Serde)

Tujuan implementasi vortex-serde:
- Mendukung pemindaian (proyeksi kolom + pemfilteran baris) dengan zero-copy dan zero heap allocation
- Mendukung akses acak dalam waktu konstan atau nyaris konstan
- Menyampaikan informasi statistik seperti apakah data terurut kepada konsumen
- Menyediakan format IPC untuk mengirim array antarproses
- Menyediakan format berkas yang dapat diperluas dan terbaik di kelasnya untuk menyimpan data kolumnar di disk atau object storage

Integrasi dengan Apache Arrow

Apache Arrow adalah standar de facto untuk interoperabilitas data array kolumnar. Karena itu, Vortex secara alami dirancang agar semaksimal mungkin kompatibel dengan Apache Arrow
Semua array Arrow dapat dikonversi menjadi array Vortex tanpa copy. Array Vortex yang dibuat dari array Arrow juga dapat dikonversi kembali ke Arrow tanpa copy
Perlu dicatat bahwa Vortex dan Arrow memiliki tujuan yang berbeda, tetapi saling melengkapi
Vortex membedakan dirinya dari Arrow dengan memisahkan secara eksplisit tipe logis dan encoding fisik. Ini memungkinkan Vortex memodelkan array yang lebih kompleks sambil tetap mengekspos antarmuka logis
- Contoh: Vortex dapat memodelkan ChunkedArray UTF8 di mana chunk pertama menggunakan run-length encoding dan chunk kedua menggunakan dictionary encoding. Di Arrow, RunLengthArray dan DictionaryArray adalah tipe terpisah yang tidak kompatibel, sehingga tidak dapat digabungkan dengan cara seperti ini