F3 - Format File Data Open Source untuk Masa Depan

• F3(Future-proof File Format) adalah format penyimpanan kolumnar open source generasi berikutnya, dengan interoperabilitas, ekstensibilitas, dan efisiensi sebagai prinsip desain utamanya, sehingga menghilangkan kebutuhan untuk membuat format baru setiap kali lingkungan pemrosesan data dan komputasi berubah
• Setiap file F3 memiliki struktur self-describing, yang menyematkan bukan hanya data dan metadata tetapi juga decoder biner WebAssembly(Wasm), sehingga kompatibilitas di semua platform tetap terjamin bahkan tanpa decoder native
• Format ini menyediakan layout penyimpanan yang efisien dengan teknik encoding terbaru (compressed stair-step, vectorized decoding), serta memperbaiki masalah layout pada Parquet dan ORC dengan memisahkan unit I/O, encoding, dan dictionary
• Melalui API decoding berbasis plugin dan mekanisme embedding Wasm, pengembang dapat dengan mudah menambahkan skema encoding baru, dan semua file tetap bisa dibaca tanpa bergantung pada versi library, sehingga menyelesaikan masalah interoperabilitas Parquet
• Hasil evaluasi membuktikan efisiensi layout penyimpanan F3 dan manfaat decoding berbasis Wasm, dengan overhead penyimpanan yang sangat kecil pada tingkat kilobyte dan penurunan performa decoding Wasm hanya 10~30% dibanding native, pada tingkat yang dapat diterima

---

Latar belakang dan motivasi

Keterbatasan format kolumnar yang ada

• Parquet dan ORC dikembangkan pada awal 2010-an untuk sistem analitik data seperti Hive, Impala, dan Spark, serta memungkinkan berbagi data antara data warehouse dan data lake
• Setelah 10 tahun, berbagai riset menunjukkan bahwa format-format ini kurang memadai untuk analitik data modern, karena didasarkan pada asumsi performa hardware lama dan asumsi pola akses workload saat dirancang
  • Dalam 10 tahun terakhir, performa storage dan jaringan meningkat puluhan kali lipat, tetapi performa CPU tidak, sehingga sistem kini mengalami bottleneck pada komputasi, bukan I/O
  • Dengan naiknya data lake, lebih banyak data disimpan di cloud storage berbandwidth tinggi namun berlatensi tinggi (misalnya Amazon S3)
  • Aplikasi tidak lagi hanya menyimpan data tabular dengan sedikit kolom. Pada workload ML, sudah umum menyimpan tabel lebar dengan ribuan kolom, embedding vektor berdimensi tinggi, dan blob berukuran besar (gambar, video)
  • Kebutuhan untuk melakukan random access atau update juga meningkat, tetapi format lama tidak cocok untuk pola penggunaan seperti ini
• Perkembangan terbaru dalam kompresi, indexing, dan filtering berupaya mengatasi kelemahan ini, tetapi format file yang ada tidak dirancang agar mudah diperluas
  • Bahkan jika fitur baru ditambahkan, terlalu banyak implementasi library Parquet dan ORC dalam berbagai bahasa, sehingga sulit mengharapkan semua menggunakan versi terbaru
  • Sistem yang memakai library versi lama mungkin tidak dapat mendekode isi file baru, sehingga sebagian besar sistem hanya mendukung fitur penyebut persekutuan terkecil untuk menghindari masalah interoperabilitas

Munculnya format file baru dan keterbatasannya

• Untuk mengatasi hal ini, muncul proposal format file yang benar-benar baru seperti Meta Nimble, Lance, TSFile, Bullion, BtrBlocks
• Namun, format-format ini juga mengulangi kesalahan yang sama seperti pendahulunya
  • Dirancang berdasarkan asumsi hardware dan workload modern
  • Tidak mendorong ekstensibilitas yang mudah agar dapat mendukung fitur baru tanpa merusak interoperabilitas dengan deployment yang sudah ada
  • Bahkan jika salah satunya menjadi format utama pengganti Parquet atau ORC, dalam 10 tahun kita akan menghadapi masalah yang sama lagi: perlu membuat format baru lain untuk mengatasi kekurangannya

Pendekatan F3

• F3 bertujuan mencapai interoperabilitas, ekstensibilitas, dan efisiensi secara bersamaan
• Inti F3 adalah mendefinisikan tiga spesifikasi berikut:
  1. Metadata untuk konten file
  2. Layout pengelompokan fisik untuk data yang di-encode di dalam file
  3. API akses data yang tidak bergantung pada skema encoding data
• Skema metadata F3 meminimalkan data yang diperlukan untuk mengambil subset kolom dari sebuah tabel
• F3 menghapus konsep luas row group pada Parquet dan mengatasi masalah layout dengan memisahkan unit I/O, encoding, dan dictionary
• F3 juga mengintegrasikan metode modern seperti compressed stair-step dan vectorized decoding

Ikhtisar F3

Struktur keseluruhan

• File F3 terdiri dari bagian metadata dan bagian data
  • Bagian metadata: OptionalData(OptData), Column Metadata(ColMetadata), Footer, Postscript
  • Bagian data: terdiri dari Row Groups(RG) dan berisi data aktual
• F3 mengadopsi layout PAX yang sama dengan Parquet dan ORC
• Namun, F3 memiliki beberapa perbedaan inti dibanding format yang ada:
  1. Metadata menghilangkan overhead deserialisasi (memperbaiki masalah pada Parquet/ORC)
  2. Physical I/O Unit(IOUnit) dipisahkan dari logical row group, sehingga ukuran IOUnit dapat disesuaikan secara independen sesuai media penyimpanan
  3. Cakupan dictionary encoding dipisahkan dari logical row group, sehingga rentang paling efektif dapat ditentukan untuk tiap kolom
  4. Setiap IOUnit terdiri dari beberapa Encoding Unit(EncUnit), dan EncUnit adalah unit minimum untuk encoding dan decoding

Mekanisme interoperabilitas dan ekstensibilitas

• F3 mengekspos API publik yang mendefinisikan bagaimana implementasi mendekode data terkompresi di dalam file
• Metode encoding diperlakukan sebagai plugin, sehingga dapat dipasang dan di-upgrade secara terpisah dari library inti
• Agar semua versi library dapat membaca semua file, F3 menyematkan implementasi decoder dalam bentuk biner WebAssembly(Wasm) ke dalam file itu sendiri
  • Artinya, setiap file F3 berisi data sekaligus kode untuk membaca data tersebut
• API F3 tidak memerlukan implementasi terpisah untuk kode native dan versi Wasm; kode yang sama dapat dikompilasi ke kedua target tanpa perubahan
• Desain ini membuat F3 tahan masa depan, menghindari masalah yang dijelaskan sebelumnya, dan memungkinkan evolusi lebih cepat daripada solusi yang ada
  • Pengembang dapat mendistribusikan metode encoding masa depan ke sistem produksi dengan menyertakan kode Wasm di dalam file, tanpa khawatir harus meng-upgrade versi library di seluruh fleet
  • Overhead penyimpanan biner Wasm sangat kecil (tingkat kilobyte), dan penurunan performa decoding Wasm dibanding implementasi native juga minimum (10~30%)

Kesimpulan

• F3 adalah format file kolumnar generasi berikutnya yang mencapai interoperabilitas, ekstensibilitas, dan efisiensi secara bersamaan
• Desain layout file yang efisien mengatasi inefisiensi pada format yang ada
• API decoding berbasis plugin dan embedding Wasm menyediakan mekanisme future-proof yang memungkinkan semua file dibaca tanpa bergantung pada versi library
• Hasil evaluasi prototipe membuktikan efisiensi desain layout dan kepraktisan mekanisme Wasm
• Overhead Wasm berada pada kisaran yang dapat diterima: penyimpanan tingkat kilobyte dan penurunan performa 10~30%

[GN⁺]

Komentar Hacker News

• Setelah melihat sekilas, tampaknya banyak kekurangan Parquet yang diperbaiki, jadi ekspektasinya besar

  • Metadata Parquet berbasis Thrift, tetapi hanya memiliki catatan semacam "kalau field ini ada maka field itu juga wajib ada" tanpa logika validasi nyata, jadi saya merasa kalau Thrift yang salah dimasukkan, pembacanya bisa rusak

  • Metadata Parquet harus diparse, sehingga alokasi buffer dan alokasi dinamis untuk parsing metadata terus berulang dan menimbulkan terlalu banyak alokasi heap. Format kali ini yang mengadopsi pendekatan Flatbuffers bisa langsung menafsirkan byte Flatbuffer, jadi masalah ini teratasi

  • Encoding-nya terasa jauh lebih kuat. Sepertinya encoding yang ringan dan dapat dikombinasikan, yang sudah lama didorong oleh industri database, akhirnya menjadi mungkin. Format lama seperti BtrBlocks dan FastLanes lebih unggul daripada Parquet, dan bagus melihat ide-ide baik mereka diteruskan

  • Saya tidak suka record-shredding Dremel di Parquet karena terlalu rumit, jadi syukurlah kali ini itu hilang

  • Di Parquet, jumlah row di dalam DataPage berbeda-beda sehingga untuk menemukan row yang diinginkan harus memindai seluruh ColumnChunk, tetapi format ini bisa langsung lompat ke DataPage(IOUnit) yang diinginkan

  • Kompresi berat dihapus dan hanya menyisakan Delta/Dictionary/RLE. Kompresi berat tidak memberi keuntungan nyata, implementasinya merepotkan, dan dependensi eksternalnya juga banyak

  • Secara keseluruhan ini perkembangan yang luar biasa. Saya berharap format ini mendominasi industri analitik data

  • Kalau yang dimaksud kompresi berat itu zstd atau brotli, itu justru sangat berguna untuk kolom string dengan sedikit pengulangan

    • Dalam praktiknya, karena sebagian besar ASCII dan banyak substring yang sama, saya pernah melihat rasio kompresi sampai 1%

  • Kalau compiler wasm ikut masuk, justru bisa menambah lebih banyak dependensi dibanding kompresi ‘heavy’

    • Dulu sumber daya CPU relatif lebih banyak dibanding bandwidth jaringan atau disk, jadi kompresi berat lebih masuk akal, tetapi sekarang selisih itu tidak sebesar dulu

  • Diskusi StackOverflow tentang menambahkan kolom ke file Parquet

  • Akhir-akhir ini metode kompresi tampaknya sudah menetap ke zstd?

  • Parquet ternyata cukup rumit. Untuk memakainya secara efisien dengan benar, kita harus memahami banyak detail yang tidak nyaman dan kurang terdokumentasi, jadi tidak mudah

• Wes McKinney

  • Bagi yang belum tahu Wes McKinney, dia adalah pencipta Pandas, pustaka analisis tabular yang paling banyak dipakai di Python

  • Format yang dia buat bisa mendapat kepercayaan pasar sejak awal rilis, dan karena dia sudah lama menaruh perhatian pada masalah ini, wawasannya dianggap sangat penting

  • Andy Pavlo juga layak disebut

    • Dia pakar di bidang database, dan terkenal menjalani hidup yang sangat berpusat pada data
    • Jika merujuk pada dua makalahnya yang berjudul "What goes around comes around", kita bisa melihat masa lalu dan masa depan bidang database dengan mudah
    • CMU Seminar Series juga luar biasa, dan keterlibatannya membuat saya makin antusias
    • Saya tidak terlalu tahu soal rekan penulis dari Tiongkok, dan merasa agak sungkan soal itu, tetapi saya berencana menandai makalah ini lalu membacanya dengan saksama

  • Sebagai penggemar, saya setuju soal pengaruh Pandas, tetapi secara teknis saya rasa format data Arrow memberi dampak yang lebih besar ke seluruh ekosistem data (misalnya DataFusion)

    • Sekarang saya ingin melihat sebenarnya F3 itu seperti apa (berkat Anda saya jadi mengeklik tautannya)

  • Wes McKinney juga pencipta Apache Arrow

    • Ini adalah komponen inti dalam analitik data modern

  • Saya justru merasa pekerjaannya di Parquet memberi rasa percaya yang lebih besar

  • Mencampur data dan kode adalah kesalahan keamanan klasik

    • Keterlibatan figur terkenal pun tidak menghilangkan kemungkinan salah

• Sepertinya ini tidak akan diterapkan di masa depan para fisikawan

  • Selama 20 tahun ke depan, data berskala exabyte yang dihasilkan Large Hadron Collider milik CERN akan memakai format yang dikembangkan sendiri oleh CERN

  • Materi terkait format data CERN

  • CERN sudah jauh lebih lama menangani data skala besar dibanding kebanyakan orang di bidang ini

    • Materi historis tentang format Zebra

• Mohon dimaklumi kalau saya belum benar-benar memahami perbedaannya dengan penyimpanan berorientasi kolom

  • Saya penasaran kenapa ini dianggap inovatif, dan bertanya, "apakah intinya adalah mengirim database embedding vektor kecil bersama sandbox?"

  • Dari makalahnya saya merasa ini bisa menjadi fondasi baru, dan dari nama proyeknya saya juga menangkap aura Prancis(?)

  • Saya sendiri tidak paham sebagian besar isinya, tetapi ilustrasi dan warnanya terasa indah dan berani. Dari posisi saya yang mudah diyakinkan, saya angkat dua jempol

  • Kuncinya adalah lapisan kompatibilitas

    • Misalnya, ORCv2 pernah mencoba membuat versi format baru dan meluncurkan fitur secara bertahap, tetapi akhirnya tidak pernah dirilis
    • Jika encoding float baru bisa didistribusikan bersama shim WASM di dalam file, format baru bisa disalurkan dengan mudah tanpa pembaruan perangkat lunak pembaca atau masalah kompatibilitas
    • Saat diperlukan rekombinasi kompleks seperti tipe variant di Spark, mengirimkannya sebagai bytecode alih-alih interpreter juga jauh lebih mudah
    • Secara pribadi, saya bangga karena setelah begadang menyetel ORC, hasil benchmark-nya tetap sangat baik

  • Keunggulan nyata penyimpanan kolom adalah skema nested yang kompleks bisa dipecah dan disimpan sebagai nilai primitive

    • Kita bisa langsung membaca nilai leaf sehingga efisiensi IO dan parsing meningkat drastis
    • Format-format ini dipartisi pada level teratas berdasarkan kelompok row
    • Format ini memungkinkan buffer Apache Arrow diterima langsung dari data page (melalui WASM atau decoder native)
    • Parquet saat ini sangat rumit. Ia memakai encoding Dremel untuk menyimpan nilai primitive bersama dua stream integer (repetition/definition level), sehingga sulit diparse oleh orang biasa
    • Terutama karena bit-packing+RLE bercampur, dan hanya kode bit-packing pada implementasi referensinya saja mencapai 74 ribu baris
    • Mengubahnya menjadi buffer Arrow membutuhkan pekerjaan yang besar. Dengan F3, itu akan jauh lebih mudah dan kompatibilitas masa depannya juga lebih baik
    • Selain itu, kemampuan random access pada metadata juga sangat penting
    • Sebagai contoh, saat memakai GeoParquet, tanpa indeks SQLite satu query spasial bisa memakan rata-rata 10 menit, dan parsing footer dari 500 file membutuhkan parsing Thrift sebesar 150MB
    • Pemilihan Flatbuffers cukup mengejutkan. Masalah keamanan memori di Flatbuffers sudah dikenal(catatan terkait)
    • Saya malah merasa mungkin lebih baik memasukkan database SQLite saja

  • Keuntungan sesungguhnya dari penyimpanan berorientasi kolom adalah seluruh column bisa dipindai sangat cepat sekaligus

    • Ini memungkinkan pemakaian buffer OS dengan sangat efisien. Misalnya query select a where b = 'x' menjadi sangat cepat

• Cukup disayangkan bahwa decoder wasm 10-30% lebih lambat dibanding native

  • Artinya sejak awal kita menerima penurunan performa 10-30%, dan juga secara permanen melepaskan peluang untuk terus meningkatkan decoder ke depan

  • Fitur decoding lanjutan selain "decode seluruh blok & simpan ke memori" juga jadi tidak bisa dipakai

  • Saya benar-benar tidak mengerti kenapa harus dibuat seperti ini

  • Kalau kecepatan itu penting, wasm bukan jawabannya, dan kalau kecepatan tidak terlalu penting, lebih baik pakai encoding yang sudah dikenal

  • WASM disediakan sebagai cadangan

    • Jika decoder native (misalnya crate) terpasang, itu yang dipakai lebih dulu, dan kalau tidak ada maka fallback ke WASM
    • Posisi mereka adalah lebih baik menerima kerugian 10-30% daripada sama sekali tidak bisa membaca file

  • Ada bagian yang saya setujui, tetapi ceritanya sedikit lebih rumit

    • Situasi serupa sebenarnya sudah berulang saat memakai berbagai metode kompresi
    • Misalnya setiap kali mengganti metode bitpack atau kompresi, perlu "transcoding", yaitu menulis ulang file
    • Setelah WASM diperkenalkan pun, tetap saja perlu menulis ulang file
    • Saya ragu apakah nilai future-proofing itu sepadan. Pada sistem berskala exabyte, re-encoding data benar-benar berat

• Saya tidak benar-benar memahami hubungan Vortex dan F3

  • Keduanya sama-sama berbicara tentang visi "memungkinkan penambahan metode encoding dengan mudah tanpa harus membuat format baru"

  • Di tulisan pengenalan disebutkan bahwa mereka memakai implementasi encoding milik Vortex, tetapi juga ditulis bahwa sistem tipenya berbeda

  • Latar belakang proyek ini cukup rumit

    • Pada awalnya, CMU, Tsinghua, Meta, CWI, VoltronData, Nvidia, dan SpiralDB membentuk konsorsium untuk menyatukan satu format file
    • Namun rencana itu gagal karena isu pengacara CMU terkait NDA Meta
    • Akibatnya semua pihak merilis format file masing-masing
      • Nimble dari Meta
      • FastLanes dari CWI
      • Vortex dari SpiralDB
      • F3 dari CMU+Tsinghua
    • Dari sisi riset, CMU+Tsinghua lebih fokus pada penyisipan WASM daripada pengembangan encoder
    • Hannes dari DuckDB yang pertama kali mengusulkan ide ini kepada Wes McKinney
    • Karena implementasi encoding Vortex berbasis Rust, dengan sedikit penyesuaian sebagian besar bisa dikompilasi ke WASM
    • Vortex adalah proyek independen yang terpisah dari F3, dan F3 saat ini merupakan prototipe akademik
    • Di Jerman tahun ini juga dirilis format terpisah yang memanfaatkan WASM: format AnyBlox (seluruh file dijadikan WASM; F3 hanya di level kelompok kolom)

• Jadi ikut menantikan pengumuman F4 tahun depan

• Saya cukup lama mencari di mana source code-nya, dan ternyata dipublikasikan di sini

• Karena untuk membaca data wajib menjalankan webassembly, saya rasa ini kurang cocok untuk lingkungan yang ingin mengurangi dependensi atau bloat

  • wasm itu sederhana

    • Itu terpisah dari "web"
    • Seperti yang dikatakan orang lain, wasm itu cadangan
    • Jika menyediakan binding native, performanya akan lebih baik

  • Kalau ada decoder native, tidak perlu memakai WASM

    • Hal ini juga dinyatakan jelas di ringkasan

• Sepertinya ini salah satu format file pertama yang menyematkan modul WebAssembly

  • Saya tertarik terutama dari sisi kompresi. Menurut saya, jika preprocessor WASM dirancang dengan baik, rasio kompresi bisa meningkat besar

  • Saya sendiri juga sedang membuat format file dengan konsep ini

  • Alan Kay pernah menjelaskan sistem penyimpanan berbasis tape yang diduga dibuat seorang programmer pada tahun 60-an sebagai ‘sistem berorientasi objek pertama’

    • Format tape tersebut menyertakan sekumpulan rutin baca dan tulis untuk posisi tertentu
    • Jadi ada preseden sebelumnya
    • Tautan makalah terkait (halaman 4)