Editorial Ilmu Komputer & AI
Open AccessOA2026
TreeRedux: Memisahkan Concern dalam Agregasi Pohon Terdistribusi Spark
Operasi finalize terminal yang menjaga state agregasi besar tetap di luar driver, memungkinkan kuantil eksak dan sketsa heavy-hitter pada skala yang belum pernah terjadi sebelumnya
David A. G. Harrison; Ivan Cao· 2026· DOI 10.48550/arXiv.2609.06982
Masalah inti
Primitif agregasi pohon Apache Spark adalah landasan pemrosesan data terdistribusi, tetapi desain bawaannya menempatkan akar pohon di driver. Ini memaksa driver untuk berpartisipasi dalam komputasi agregasi yang sama atas state agregasi antara seperti halnya node executor. Untuk agregat besar, koordinator tunggal dapat menghadapi kebutuhan komputasi dan memori yang substansial. Versi Spark terbaru secara opsional memindahkan akar ke executor, namun agregat yang selesai tetap harus dikembalikan dan dimaterialisasi di driver. Penulis menunjukkan batasan ini menggunakan komputasi kuantil eksak dan identifikasi heavy-hitter, di mana state agregasi antara dapat jauh lebih besar daripada hasil akhir yang diinginkan. Mereka mengusulkan TreeRedux, ekstensi minimal yang menambahkan operasi finalize terminal yang dijalankan di executor, memetakan state agregasi ke hasil ringkas , sehingga alih-alih yang berpotensi besar dimaterialisasi di driver.
Inovasi
Penulis melakukan eksperimen untuk mengevaluasi TreeRedux terhadap implementasi baseline. Implementasi GK Select bawaan mengalami error out-of-memory driver pada 2,5 miliar elemen. Opsi agregasi akhir di sisi executor Spark memperluas batas ini menjadi sekitar 16-18 miliar elemen tetapi tetap mengharuskan state agregasi akhir dimaterialisasi di driver. Sebaliknya, Redux Select, versi yang ditingkatkan TreeRedux, menyelesaikan hingga 28 miliar elemen tanpa error out-of-memory driver. Lebih lanjut, TreeRedux memungkinkan sketsa Space-Saving dengan kapasitas hingga 32x lipat konfigurasi terbesar yang mematerialisasi sketsa penuh di driver. Hasil ini menunjukkan peningkatan signifikan dalam skalabilitas dan efisiensi memori.
Primitif agregasi pohon Apache Spark adalah landasan pemrosesan data terdistribusi, tetapi desain bawaannya menempatkan akar pohon di driver. Ini memaksa driver untuk berpartisipasi dalam komputasi agregasi yang sama atas state agregasi antara seperti halnya node executor. Untuk agregat besar, koordinator tunggal dapat menghadapi kebutuhan komputasi dan memori yang substansial. Versi Spark terbaru secara opsional memindahkan akar ke executor, namun agregat yang selesai tetap harus dikembalikan dan dimaterialisasi di driver. Penulis menunjukkan batasan ini menggunakan komputasi kuantil eksak dan identifikasi heavy-hitter, di mana state agregasi antara dapat jauh lebih besar daripada hasil akhir yang diinginkan. Mereka mengusulkan TreeRedux, ekstensi minimal yang menambahkan operasi finalize terminal yang dijalankan di executor, memetakan state agregasi ke hasil ringkas , sehingga alih-alih yang berpotensi besar dimaterialisasi di driver.
TreeRedux memperkenalkan operasi finalize terminal yang berjalan di executor setelah agregasi pohon selesai. Secara formal, misalkan menyatakan state agregasi antara dan hasil akhir yang ringkas. Fungsi finalize diterapkan di executor, memastikan hanya yang ditransfer ke dan dimaterialisasi di driver. Pemisahan concern ini memisahkan komputasi agregasi dari materialisasi hasil akhir.
Mengapa penting
Hasil ini menyoroti efektivitas pemisahan langkah finalisasi dari komputasi agregasi. Dengan memindahkan operasi finalize ke executor, TreeRedux menghapus suku memori epsilon-n driver untuk komputasi kuantil eksak, mengurangi kebutuhan memori driver ke orde asimtotik yang sama dengan GK Sketch milik Spark. Ini sangat penting untuk pemrosesan data skala besar di mana state agregasi antara dapat beberapa orde lebih besar daripada hasil akhir. Kemampuan menggunakan sketsa Space-Saving dengan kapasitas 32x lipat lebih lanjut menegaskan manfaat praktisnya. TreeRedux adalah ekstensi minimal, sehingga mudah diadopsi dalam aplikasi Spark yang ada. Penulis mencatat bahwa meskipun versi Spark terbaru secara opsional memindahkan akar ke executor, agregat yang selesai tetap harus dikembalikan dan dimaterialisasi di driver; TreeRedux mengatasi bottleneck yang tersisa ini. Pekerjaan selanjutnya dapat mengeksplorasi penerapan TreeRedux pada primitif agregasi lain dan mengoptimalkan fungsi finalize untuk berbagai tipe data.
Siapa yang sebaiknya membaca
Praktisi dan peneliti ilmu komputer
Membuka konten member…