Bagaimana Roblox Mengurangi Biaya Kueri Gabungan Spark dengan Filter Bloom yang Dioptimalkan oleh Pembelajaran Mesin

Ringkasan

Setiap hari di Roblox, 70 juta pengguna berinteraksi dengan jutaan pengalaman, dengan total 16 miliar jam per kuartal. Interaksi ini menghasilkan data lake berskala petabyte, yang diperkaya untuk keperluan analitik dan pembelajaran mesin (ML). Menggabungkan tabel fakta dan dimensi di data lake kami membutuhkan sumber daya yang besar, sehingga untuk mengoptimalkan hal ini dan mengurangi pengacakan data, kami menggunakan Learned Bloom Filters [1]—struktur data cerdas yang menggunakan ML. Dengan memprediksi keberadaan, filter ini secara signifikan memangkas data gabungan, meningkatkan efisiensi, dan mengurangi biaya. Dalam prosesnya, kami juga meningkatkan arsitektur model kami dan menunjukkan manfaat substansial yang ditawarkannya untuk mengurangi penggunaan memori dan waktu CPU untuk pemrosesan, serta meningkatkan stabilitas operasional.

Pendahuluan

Di data lake kami, tabel fakta dan kubus data dipartisi secara temporal untuk akses yang efisien, sementara tabel dimensi tidak memiliki partisi semacam itu, dan menggabungkannya dengan tabel fakta selama pembaruan memakan banyak sumber daya. Ruang kunci penggabungan ditentukan oleh partisi temporal dari tabel fakta yang digabungkan. Entitas dimensi yang terdapat dalam partisi waktu tersebut hanyalah subset kecil dari yang terdapat dalam dataset dimensi secara keseluruhan. Akibatnya, sebagian besar data dimensi yang di-shuffle dalam penggabungan ini akhirnya dibuang. Untuk mengoptimalkan proses ini dan mengurangi pengacakan yang tidak perlu, kami mempertimbangkan penggunaan Bloom Filter pada kunci penggabungan yang unik, namun menghadapi masalah ukuran filter dan jejak memori.

Untuk mengatasinya, kami mengeksplorasi Learned Bloom Filters, solusi berbasis ML yang mengurangi ukuran Bloom Filter sambil mempertahankan tingkat false positive yang rendah. Inovasi ini meningkatkan efisiensi operasi join dengan mengurangi biaya komputasi dan meningkatkan stabilitas sistem. Skema berikut menggambarkan proses join konvensional dan yang dioptimalkan dalam lingkungan komputasi terdistribusi kami.

Meningkatkan Efisiensi Gabungan dengan Filter Bloom yang Dipelajari

Untuk mengoptimalkan penggabungan antara tabel fakta dan dimensi, kami mengadopsi implementasi Filter Bloom yang Dipelajari. Kami membangun indeks dari kunci yang ada di tabel fakta dan kemudian menerapkan indeks tersebut untuk menyaring data dimensi terlebih dahulu sebelum operasi penggabungan. 

Evolusi dari Filter Bloom Tradisional ke Filter Bloom yang Dipelajari

Meskipun Bloom Filter tradisional efisien, ia menambah 15-25% memori tambahan per node pekerja yang perlu memuatnya untuk mencapai tingkat false positive yang diinginkan. Namun, dengan memanfaatkan Learned Bloom Filters, kami berhasil mengurangi ukuran indeks secara signifikan sambil mempertahankan tingkat false positive yang sama. Hal ini disebabkan oleh transformasi Bloom Filter menjadi masalah klasifikasi biner. Label positif menandakan adanya nilai dalam indeks, sementara label negatif berarti nilai tersebut tidak ada.

Penggunaan model ML memfasilitasi pemeriksaan awal terhadap nilai-nilai, diikuti oleh Bloom Filter cadangan untuk menghilangkan false negative. Ukuran yang berkurang berasal dari representasi terkompresi model dan berkurangnya jumlah kunci yang dibutuhkan oleh Bloom Filter cadangan. Hal ini membedakannya dari pendekatan Bloom Filter konvensional. 

Sebagai bagian dari pekerjaan ini, kami menetapkan dua metrik untuk mengevaluasi pendekatan Learned Bloom Filter kami: ukuran objek serialisasi akhir indeks dan konsumsi CPU selama pelaksanaan kueri gabungan. 

Mengatasi Tantangan Implementasi

Tantangan awal kami adalah menangani dataset pelatihan yang sangat bias dengan sedikit kunci tabel dimensi di tabel fakta. Dalam hal ini, kami mengamati tumpang tindih sekitar satu dari tiga kunci antara tabel-tabel tersebut. Untuk mengatasi hal ini, kami memanfaatkan pendekatan Sandwich Learned Bloom Filter [2]. Pendekatan ini mengintegrasikan Bloom Filter tradisional awal untuk menyeimbangkan distribusi dataset dengan menghapus sebagian besar kunci yang hilang dari tabel fakta, secara efektif menghilangkan sampel negatif dari dataset. Selanjutnya, hanya kunci yang termasuk dalam Bloom Filter awal, bersama dengan false positive, yang diteruskan ke model ML, yang sering disebut sebagai "learned oracle." Pendekatan ini menghasilkan dataset pelatihan yang seimbang untuk learned oracle, sehingga mengatasi masalah bias secara efektif.

Tantangan kedua berpusat pada arsitektur model dan fitur pelatihan. Berbeda dengan masalah klasik URL phishing [1], kunci gabungan kami (yang dalam kebanyakan kasus merupakan pengidentifikasi unik untuk pengguna/pengalaman) tidak secara inheren informatif. Hal ini mendorong kami untuk mengeksplorasi atribut dimensi sebagai fitur model potensial yang dapat membantu memprediksi apakah entitas dimensi terdapat dalam tabel fakta. Misalnya, bayangkan sebuah tabel fakta yang berisi informasi sesi pengguna untuk pengalaman dalam bahasa tertentu. Lokasi geografis atau atribut preferensi bahasa dari dimensi pengguna akan menjadi indikator yang baik untuk mengetahui apakah seorang pengguna individu ada dalam tabel fakta atau tidak.

Tantangan ketiga—latensi inferensi—membutuhkan model yang meminimalkan false negative sekaligus memberikan respons yang cepat. Model pohon yang didorong gradien adalah pilihan optimal untuk metrik utama ini, dan kami memangkas kumpulan fiturnya untuk menyeimbangkan presisi dan kecepatan.

Kueri gabungan kami yang telah diperbarui menggunakan Bloom Filters yang dipelajari ditampilkan di bawah ini:

Hasil

Berikut adalah hasil eksperimen kami dengan Learned Bloom filters di data lake kami. Kami mengintegrasikannya ke dalam lima beban kerja produksi, yang masing-masing memiliki karakteristik data yang berbeda. Bagian yang paling memakan sumber daya komputasi dari beban kerja ini adalah penggabungan antara tabel fakta dan tabel dimensi. Ruang kunci tabel fakta sekitar 30% dari tabel dimensi. Pertama-tama, kami membahas bagaimana Learned Bloom Filter mengungguli Bloom Filter tradisional dalam hal ukuran objek serialisasi akhir. Selanjutnya, kami menunjukkan peningkatan kinerja yang kami amati dengan mengintegrasikan Learned Bloom Filter ke dalam pipa pemrosesan beban kerja kami.

Perbandingan Ukuran Learned Bloom Filter

Seperti yang ditunjukkan di bawah ini, ketika melihat tingkat false positive tertentu, kedua varian Learned Bloom Filter meningkatkan ukuran objek total antara 17-42% jika dibandingkan dengan Bloom Filter tradisional.

Selain itu, dengan menggunakan subset fitur yang lebih kecil dalam model pohon gradient boosted kami, kami hanya kehilangan sebagian kecil optimasi sambil mempercepat proses inferensi.

Hasil Penggunaan Bloom Filter 

Pada bagian ini, kami membandingkan kinerja penggabungan berbasis Bloom Filter dengan penggabungan biasa berdasarkan beberapa metrik. 

Tabel di bawah ini membandingkan kinerja beban kerja dengan dan tanpa penggunaan Learned Bloom Filter. Sebuah Learned Bloom Filter dengan probabilitas false positive total sebesar 1% menunjukkan perbandingan di bawah ini sambil mempertahankan konfigurasi kluster yang sama untuk kedua jenis join. 

Pertama, kami menemukan bahwa implementasi Bloom Filter mengungguli join biasa hingga 60% dalam hal jam CPU. Kami melihat peningkatan penggunaan CPU pada langkah pemindaian untuk pendekatan Learned Bloom Filter karena komputasi tambahan yang digunakan dalam mengevaluasi Bloom Filter. Namun, penyaringan awal yang dilakukan pada langkah ini mengurangi ukuran data yang diacak, yang membantu mengurangi CPU yang digunakan oleh langkah-langkah hilir, sehingga mengurangi total jam CPU.

Kedua, Learned Bloom Filter memiliki ukuran data total sekitar 80% lebih kecil dan byte pengacakan total yang ditulis sekitar 80% lebih sedikit dibandingkan join biasa. Hal ini menghasilkan kinerja join yang lebih stabil seperti yang dibahas di bawah ini. 

Kami juga melihat pengurangan penggunaan sumber daya pada beban kerja produksi lainnya yang sedang diuji coba. Selama periode dua minggu di seluruh lima beban kerja, pendekatan Learned Bloom Filter menghasilkan penghematan biaya harian rata-rata sebesar 25%, yang juga mencakup pelatihan model dan pembuatan indeks.

Karena berkurangnya jumlah data yang di-shuffle saat melakukan join, kami dapat secara signifikan mengurangi biaya operasional pipa analitik kami sekaligus membuatnya lebih stabil. Grafik berikut menunjukkan variabilitas (menggunakan koefisien variasi) dalam durasi eksekusi (waktu jam dinding) untuk beban kerja join biasa dan beban kerja berbasis Learned Bloom Filter selama periode dua minggu untuk lima beban kerja yang kami uji. Eksekusi yang menggunakan Learned Bloom Filter lebih stabil—lebih konsisten dalam durasinya—yang membuka kemungkinan untuk memindahkannya ke sumber daya komputasi sementara yang lebih murah dan tidak dapat diandalkan. 

Referensi

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean, dan N. Polyzotis. The Case for Learned Index Structures. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Optimizing Learned Bloom Filters by Sandwiching. 

https://arxiv.org/abs/1803.01474, 2018.

¹Per 3 bulan yang berakhir pada 30 Juni 2023

²Per 3 bulan yang berakhir pada 30 Juni 2023