Bagaimana Roblox Mengurangi Biaya Kueri Spark Join Dengan Filter Bloom yang Dioptimalkan Pembelajaran Mesin - Blog Roblox

Bagaimana Roblox Mengurangi Biaya Kueri Spark Join Dengan Filter Bloom yang Dioptimalkan Pembelajaran Mesin – Blog Roblox

Stempel Waktu: 28 November 2023 12
Node Sumber: 2983061

Abstrak

Setiap hari di Roblox, 65.5 juta pengguna terlibat dengan jutaan pengalaman, dengan total 14.0 miliar jam setiap triwulan. Interaksi ini menghasilkan data lake berskala petabyte, yang diperkaya untuk tujuan analitik dan pembelajaran mesin (ML). Menggabungkan tabel fakta dan dimensi dalam data lake membutuhkan banyak sumber daya, jadi untuk mengoptimalkan hal ini dan mengurangi pengacakan data, kami menerapkan Filter Bloom yang Dipelajari [1]—struktur data cerdas menggunakan ML. Dengan memprediksi keberadaan, filter ini memangkas data gabungan secara signifikan, sehingga meningkatkan efisiensi dan mengurangi biaya. Dalam prosesnya, kami juga menyempurnakan arsitektur model kami dan mendemonstrasikan manfaat besar yang ditawarkannya dalam mengurangi jam memori dan CPU untuk pemrosesan, serta meningkatkan stabilitas operasional.

Pengantar

Di data lake kami, tabel fakta dan kubus data dipartisi sementara untuk akses yang efisien, sedangkan tabel dimensi tidak memiliki partisi tersebut, dan menggabungkannya dengan tabel fakta selama pembaruan membutuhkan banyak sumber daya. Ruang kunci dari gabungan didorong oleh partisi temporal dari tabel fakta yang digabungkan. Entitas dimensi yang ada dalam partisi temporal tersebut adalah sebagian kecil dari entitas yang ada di seluruh kumpulan data dimensi. Akibatnya, sebagian besar data dimensi yang diacak dalam gabungan ini pada akhirnya akan dibuang. Untuk mengoptimalkan proses ini dan mengurangi pengocokan yang tidak perlu, kami mempertimbangkan untuk menggunakan Filter Mekar pada kunci gabungan yang berbeda tetapi menghadapi masalah ukuran filter dan jejak memori.

Untuk mengatasinya, kami melakukan eksplorasi Filter Bloom yang Dipelajari, solusi berbasis ML yang mengurangi ukuran Filter Bloom sekaligus mempertahankan tingkat positif palsu yang rendah. Inovasi ini meningkatkan efisiensi operasi gabungan dengan mengurangi biaya komputasi dan meningkatkan stabilitas sistem. Skema berikut mengilustrasikan proses penggabungan konvensional dan optimal dalam lingkungan komputasi terdistribusi kami.

Meningkatkan Efisiensi Gabungan dengan Filter Bloom yang Dipelajari

Untuk mengoptimalkan penggabungan antara tabel fakta dan tabel dimensi, kami mengadopsi implementasi Learned Bloom Filter. Kami membuat indeks dari kunci yang ada di tabel fakta dan kemudian menerapkan indeks tersebut ke pra-filter data dimensi sebelum operasi penggabungan. 

Evolusi dari Filter Bloom Tradisional ke Filter Bloom yang Dipelajari

Meskipun Filter Bloom tradisional efisien, ia menambahkan 15-25% memori tambahan per node pekerja yang perlu memuatnya untuk mencapai tingkat positif palsu yang kami inginkan. Namun dengan memanfaatkan Filter Bloom yang Dipelajari, kami mencapai pengurangan ukuran indeks secara signifikan sambil mempertahankan tingkat positif palsu yang sama. Hal ini karena transformasi Filter Bloom menjadi masalah klasifikasi biner. Label positif menunjukkan adanya nilai dalam indeks, sedangkan label negatif berarti tidak ada nilai.

Pengenalan model ML memfasilitasi pemeriksaan nilai awal, diikuti dengan Filter Bloom cadangan untuk menghilangkan negatif palsu. Pengurangan ukuran berasal dari representasi terkompresi model dan pengurangan jumlah kunci yang diperlukan oleh Filter Bloom cadangan. Hal ini membedakannya dari pendekatan Bloom Filter konvensional. 

Sebagai bagian dari pekerjaan ini, kami menetapkan dua metrik untuk mengevaluasi pendekatan Filter Bloom yang Dipelajari: ukuran objek serial akhir indeks dan konsumsi CPU selama eksekusi kueri gabungan. 

Menavigasi Tantangan Implementasi

Tantangan awal kami adalah mengatasi kumpulan data pelatihan yang sangat bias dengan sedikit kunci tabel dimensi di tabel fakta. Saat melakukan hal ini, kami mengamati adanya tumpang tindih sekitar satu dari tiga kunci di antara tabel. Untuk mengatasi hal ini, kami memanfaatkan pendekatan Sandwich Learned Bloom Filter [2]. Ini mengintegrasikan Filter Bloom tradisional awal untuk menyeimbangkan kembali distribusi kumpulan data dengan menghapus sebagian besar kunci yang hilang dari tabel fakta, sehingga secara efektif menghilangkan sampel negatif dari kumpulan data. Selanjutnya, hanya kunci yang disertakan dalam Filter Bloom awal, bersama dengan positif palsu, yang diteruskan ke model ML, yang sering disebut sebagai “oracle yang dipelajari”. Pendekatan ini menghasilkan kumpulan data pelatihan yang seimbang untuk oracle yang dipelajari, 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 banyak kasus merupakan pengidentifikasi unik untuk pengguna/pengalaman) pada dasarnya tidak informatif. Hal ini mengarahkan kami untuk mengeksplorasi atribut dimensi sebagai fitur model potensial yang dapat membantu memprediksi apakah entitas dimensi ada dalam tabel fakta. Misalnya, bayangkan tabel fakta yang berisi informasi sesi pengguna untuk pengalaman dalam bahasa tertentu. Lokasi geografis atau atribut preferensi bahasa pada dimensi pengguna akan menjadi indikator yang baik untuk mengetahui apakah masing-masing pengguna ada dalam tabel fakta atau tidak.

Tantangan ketiga—latensi inferensi—membutuhkan model yang meminimalkan kesalahan negatif dan memberikan respons cepat. Model pohon dengan peningkatan gradien adalah pilihan optimal untuk metrik utama ini, dan kami memangkas rangkaian fiturnya untuk menyeimbangkan presisi dan kecepatan.

Kueri gabungan kami yang diperbarui menggunakan Filter Bloom yang dipelajari adalah seperti yang ditunjukkan di bawah ini:

Hasil

Berikut adalah hasil percobaan kami dengan filter Learned Bloom di data lake kami. Kami mengintegrasikannya ke dalam lima beban kerja produksi, yang masing-masing memiliki karakteristik data berbeda. Bagian yang paling mahal secara komputasi dari beban kerja ini adalah penggabungan antara tabel fakta dan tabel dimensi. Ruang kunci tabel fakta kira-kira 30% dari tabel dimensi. Untuk memulainya, kita membahas bagaimana Filter Bloom yang Dipelajari mengungguli Filter Bloom tradisional dalam hal ukuran objek serial akhir. Selanjutnya, kami menunjukkan peningkatan kinerja yang kami amati dengan mengintegrasikan Filter Bloom yang Dipelajari ke dalam alur pemrosesan beban kerja kami.

Perbandingan Ukuran Filter Bloom yang Dipelajari

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

Selain itu, dengan menggunakan subkumpulan fitur yang lebih kecil dalam model berbasis pohon yang ditingkatkan gradien, kami hanya kehilangan sebagian kecil pengoptimalan sekaligus membuat inferensi lebih cepat.

Hasil Penggunaan Filter Bloom yang Dipelajari 

Di bagian ini, kami membandingkan performa gabungan berbasis Filter Bloom dengan gabungan reguler di beberapa metrik. 

Tabel di bawah ini membandingkan performa beban kerja dengan dan tanpa penggunaan Filter Learned Bloom. Filter Bloom yang Dipelajari dengan total probabilitas positif palsu 1% menunjukkan perbandingan di bawah ini sambil mempertahankan konfigurasi cluster yang sama untuk kedua jenis gabungan. 

Pertama, kami menemukan bahwa implementasi Bloom Filter mengungguli penggabungan reguler sebanyak 60% dalam jam CPU. Kami melihat peningkatan penggunaan CPU pada langkah pemindaian untuk pendekatan Filter Bloom yang Dipelajari karena komputasi tambahan yang dikeluarkan dalam mengevaluasi Filter Bloom. Namun, pemfilteran awal yang dilakukan pada langkah ini mengurangi ukuran data yang diacak, sehingga membantu mengurangi penggunaan CPU pada langkah hilir, sehingga mengurangi total jam kerja CPU.

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

Kami juga melihat berkurangnya penggunaan sumber daya pada beban kerja produksi lainnya yang sedang diuji. Selama periode dua minggu di kelima beban kerja, pendekatan Learned Bloom Filter menghasilkan rata-rata penghematan biaya harian of 25%, yang juga memperhitungkan pelatihan model dan pembuatan indeks.

Karena berkurangnya jumlah data yang diacak saat melakukan penggabungan, kami dapat secara signifikan mengurangi biaya operasional saluran analitik kami sekaligus membuatnya lebih stabil. Bagan berikut menunjukkan variabilitas (menggunakan koefisien variasi) dalam durasi proses (dinding waktu jam) untuk beban kerja gabungan reguler dan beban kerja berbasis Filter Bloom yang Dipelajari selama periode dua minggu untuk lima beban kerja yang kami uji. Proses yang menggunakan Filter Bloom yang Dipelajari lebih stabil—durasinya lebih konsisten—yang membuka kemungkinan untuk memindahkannya ke sumber daya komputasi sementara yang tidak dapat diandalkan dan lebih murah. 

Referensi

[1] T. Kraska, A. Beutel, EH Chi, J. Dean, dan N. Polyzotis. Kasus Struktur Indeks yang Dipelajari. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. Mengoptimalkan Filter Bloom yang Dipelajari dengan Sandwiching. 

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

¹Pada 3 bulan yang berakhir pada tanggal 30 Juni 2023

²Pada 3 bulan yang berakhir pada tanggal 30 Juni 2023

Stempel Waktu:

Lebih dari roblox