Roblox, Makine Öğrenimi ile Optimize Edilmiş Bloom Filtreleri Kullanılarak Spark Join Sorgu Maliyetlerini Nasıl Azaltıyor?
Özet
Roblox'ta her gün 70 milyon kullanıcı milyonlarca deneyime katılıyor ve bu, üç aylık toplamda 16 milyar saate ulaşıyor. Bu etkileşim, analitik ve makine öğrenimi (ML) amaçları için zenginleştirilmiş, petabayt ölçeğinde bir veri gölü oluşturuyor. Veri gölümüzdeki gerçek ve boyut tablolarını birleştirmek kaynak açısından yoğun bir işlemdir; bu nedenle, bunu optimize etmek ve veri karıştırmayı azaltmak için ML kullanan akıllı veri yapıları olan Learned Bloom Filters [1]'ı benimsedik. Bu filtreler, varlığı tahmin ederek birleştirme verilerini önemli ölçüde azaltır, verimliliği artırır ve maliyetleri düşürür. Bu süreçte, model mimarilerimizi de geliştirdik ve bunların işleme için gereken bellek ve CPU saatlerini azaltmanın yanı sıra operasyonel istikrarı artırmada sağladığı önemli faydaları gösterdik.
Giriş
Veri gölümüzde, verimli erişim için gerçek tabloları ve veri küpleri zamansal olarak bölümlere ayrılırken, boyut tablolarında bu tür bölümler bulunmaz ve güncellemeler sırasında bunları gerçek tablolarıyla birleştirmek kaynak yoğun bir işlemdir. Birleştirmenin anahtarı, birleştirilen gerçek tablosunun zamansal bölümüdür. Bu zamansal bölümde bulunan boyut varlıkları, tüm boyut veri kümesinde bulunanların küçük bir alt kümesidir. Sonuç olarak, bu birleştirmelerdeki karıştırılmış boyut verilerinin çoğu sonunda atılır. Bu süreci optimize etmek ve gereksiz karıştırmayı azaltmak için, farklı birleştirme anahtarlarında Bloom Filtreleri kullanmayı düşündük, ancak filtre boyutu ve bellek ayak izi sorunlarıyla karşılaştık.
Bu sorunları çözmek için, düşük yanlış pozitif oranlarını korurken Bloom Filtresi boyutunu azaltan, makine öğrenimi tabanlı bir çözüm olan Öğrenilmiş Bloom Filtrelerini araştırdık. Bu yenilik, hesaplama maliyetlerini azaltarak ve sistem kararlılığını artırarak birleştirme işlemlerinin verimliliğini artırır. Aşağıdaki şema, dağıtık hesaplama ortamımızdaki geleneksel ve optimize edilmiş birleştirme süreçlerini göstermektedir.
Öğrenilmiş Bloom Filtreleri ile Birleştirme Verimliliğini Artırma
Gerçek ve boyut tabloları arasındaki birleştirmeyi optimize etmek için, Öğrenilmiş Bloom Filtresi uygulamasını benimsedik. Gerçek tablosunda bulunan anahtarlardan bir dizin oluşturduk ve ardından birleştirme işleminden önce boyut verilerini önceden filtrelemek için bu dizini devreye aldık.
Geleneksel Bloom Filtrelerinden Öğrenilmiş Bloom Filtrelerine Evrim
Geleneksel Bloom Filtresi verimli olmakla birlikte, istenen yanlış pozitif oranına ulaşmak için onu yüklemesi gereken her işçi düğümü başına %15-25 oranında ek bellek ekler. Ancak Öğrenilmiş Bloom Filtrelerinden yararlanarak, aynı yanlış pozitif oranını korurken dizin boyutunu önemli ölçüde azalttık. Bunun nedeni, Bloom Filtresinin ikili sınıflandırma sorununa dönüştürülmesidir. Pozitif etiketler dizinde değerlerin varlığını gösterirken, negatif etiketler bunların yokluğunu ifade eder.
Bir ML modelinin kullanılması, değerlerin ilk kontrolünü kolaylaştırır ve ardından yanlış negatifleri ortadan kaldırmak için bir yedek Bloom Filtresi devreye girer. Boyutun küçülmesi, modelin sıkıştırılmış temsilinden ve yedek Bloom Filtresinin gerektirdiği anahtar sayısının azalmasından kaynaklanmaktadır. Bu, onu geleneksel Bloom Filtresi yaklaşımından ayırır.
Bu çalışmanın bir parçası olarak, Öğrenilmiş Bloom Filtresi yaklaşımımızı değerlendirmek için iki ölçüt belirledik: dizinin nihai serileştirilmiş nesne boyutu ve birleştirme sorgularının yürütülmesi sırasında CPU tüketimi.
Uygulama Zorluklarının Üstesinden Gelmek
İlk zorluğumuz, gerçek tablosunda çok az boyut tablosu anahtarı bulunan, oldukça önyargılı bir eğitim veri kümesini ele almaktı. Bunu yaparken, tablolar arasında yaklaşık üç anahtardan birinin çakıştığını gözlemledik. Bunu çözmek için, Sandwich Öğrenilmiş Bloom Filtresi yaklaşımını [2] kullandık. Bu yaklaşım, gerçek tablosunda eksik olan anahtarların çoğunu kaldırarak veri kümesi dağılımını yeniden dengelemek için ilk geleneksel Bloom Filtresini entegre eder ve veri kümesinden negatif örnekleri etkili bir şekilde ortadan kaldırır. Ardından, yalnızca ilk Bloom Filtresinde yer alan anahtarlar ve yanlış pozitifler, genellikle "öğrenilmiş oracle" olarak adlandırılan ML modeline iletildi. Bu yaklaşım, öğrenilmiş oracle için dengeli bir eğitim veri seti oluşturarak önyargı sorununu etkili bir şekilde ortadan kaldırdı.
İkinci zorluk, model mimarisi ve eğitim özellikleri üzerinde yoğunlaşıyordu. Klasik kimlik avı URL'leri sorunundan [1] farklı olarak, birleştirme anahtarlarımız (çoğu durumda kullanıcılar/deneyimler için benzersiz tanımlayıcılardır) doğası gereği bilgilendirici değildi. Bu durum, bir boyut varlığının gerçek tablosunda mevcut olup olmadığını tahmin etmeye yardımcı olabilecek potansiyel model özellikleri olarak boyut özniteliklerini araştırmamıza yol açtı. Örneğin, belirli bir dildeki deneyimlere ait kullanıcı oturum bilgilerini içeren bir gerçek tablosu düşünün. Kullanıcı boyutunun coğrafi konumu veya dil tercihi özniteliği, bireysel bir kullanıcının gerçek tablosunda mevcut olup olmadığını gösteren iyi göstergeler olacaktır.
Üçüncü zorluk olan çıkarım gecikmesi, hem yanlış negatifleri en aza indiren hem de hızlı yanıtlar sağlayan modeller gerektiriyordu. Gradyan destekli ağaç modeli, bu temel metrikler için en uygun seçimdi ve biz de doğruluk ile hız arasında denge sağlamak için modelin özellik kümesini sadeleştirdik.
Öğrenilmiş Bloom Filtrelerini kullanan güncellenmiş birleştirme sorgumuz aşağıda gösterilmiştir:
Sonuçlar
İşte veri gölümüzde Learned Bloom filtreleri ile yaptığımız deneylerin sonuçları. Bunları, her biri farklı veri özelliklerine sahip beş üretim iş yüküne entegre ettik. Bu iş yüklerinin hesaplama açısından en maliyetli kısmı, gerçek tablosu ile boyut tablosu arasındaki birleştirmedir. Gerçek tablolarının anahtar alanı, boyut tablosunun yaklaşık %30'u kadardır. Öncelikle, öğrenilmiş Bloom filtresinin nihai serileştirilmiş nesne boyutu açısından geleneksel Bloom filtrelerinden nasıl daha iyi performans gösterdiğini tartışacağız. Ardından, öğrenilmiş Bloom filtrelerini iş yükü işleme boru hatlarımıza entegre ederek gözlemlediğimiz performans iyileştirmelerini göstereceğiz.
Öğrenilmiş Bloom Filtresi Boyut Karşılaştırması
Aşağıda gösterildiği gibi, belirli bir yanlış pozitif oranına bakıldığında, öğrenilmiş Bloom Filtresinin iki varyantı, geleneksel Bloom Filtrelerine kıyasla toplam nesne boyutunu %17-42 oranında iyileştirir.
Ayrıca, gradyan destekli ağaç tabanlı modelimizde daha küçük bir özellik alt kümesi kullanarak, optimizasyondan sadece küçük bir oranda kayıp yaşarken, çıkarım sürecini hızlandırdık.
Bloom Filtresi Kullanım Sonuçları
Bu bölümde, Bloom Filtresi tabanlı birleşimlerin performansını çeşitli metrikler açısından normal birleşimlerin performansıyla karşılaştırıyoruz.
Aşağıdaki tablo, öğrenilmiş Bloom Filtreleri kullanılan ve kullanılmayan iş yüklerinin performansını karşılaştırmaktadır. Toplam yanlış pozitif olasılığı %1 olan bir öğrenilmiş Bloom Filtresi, her iki birleştirme türü için de aynı küme yapılandırmasını korurken aşağıdaki karşılaştırmayı göstermektedir.
İlk olarak, Bloom Filtresi uygulamasının CPU saatleri açısından normal birleştirme işleminden %60 daha iyi performans gösterdiğini tespit ettik. Bloom Filtresini değerlendirmek için harcanan ek hesaplama gücü nedeniyle, Öğrenilmiş Bloom Filtresi yaklaşımında tarama adımının CPU kullanımında bir artış gözlemledik. Ancak, bu adımda yapılan ön filtreleme, karıştırılan verilerin boyutunu azalttı; bu da sonraki adımlarda kullanılan CPU'yu azaltmaya yardımcı oldu ve böylece toplam CPU saatlerini düşürdü.
İkinci olarak, öğrenilmiş Bloom Filtreleri, normal birleştirmeye kıyasla yaklaşık %80 daha az toplam veri boyutuna ve yaklaşık %80 daha az toplam karıştırma baytına sahiptir. Bu, aşağıda tartışıldığı gibi daha istikrarlı bir birleştirme performansına yol açar.
Ayrıca, deneme aşamasındaki diğer üretim iş yüklerimizde de kaynak kullanımında azalma gördük. Beş iş yükünün tümünde iki haftalık bir süre boyunca, Learned Bloom Filter yaklaşımı, model eğitimi ve dizin oluşturmayı da hesaba katarak ortalama %25'lik bir günlük maliyet tasarrufu sağladı.
Birleştirme işlemi sırasında karıştırılan veri miktarının azalması sayesinde, analitik boru hattımızın operasyonel maliyetlerini önemli ölçüde düşürürken, aynı zamanda daha istikrarlı hale getirebildik. Aşağıdaki grafik, deneme yaptığımız beş iş yükü için iki haftalık bir süre boyunca normal birleştirme iş yükü ile Öğrenilmiş Bloom Filtresi tabanlı iş yükünün çalışma sürelerindeki (duvar saati süresi) değişkenliği (varyasyon katsayısı kullanılarak) göstermektedir. Öğrenilmiş Bloom Filtreleri kullanılan çalıştırmalar daha kararlıydı (süre açısından daha tutarlıydı), bu da bunları daha ucuz, geçici ve güvenilmez hesaplama kaynaklarına taşıma olasılığını ortaya çıkardı.
Kaynakça
[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean ve N. Polyzotis. Öğrenilmiş Dizin Yapılarının Avantajları. https://arxiv.org/abs/1712.01208, 2017.
[2] M. Mitzenmacher. Sandwiching ile Öğrenilmiş Bloom Filtrelerinin Optimize Edilmesi.
https://arxiv.org/abs/1803.01474, 2018.
¹30 Haziran 2023 tarihinde sona eren 3 aylık dönem itibarıyla
²30 Haziran 2023 tarihinde sona eren 3 aylık dönem itibarıyla
