- Rezervuar örnekleme, verinin boyutu bilinmediğinde adil bir rastgele örnek seçmek için kullanılan benzersiz ve verimli bir tekniktir
- Geleneksel yöntemlerle desteklenmeyen durumları verimli biçimde çözebilmesi sayesinde gerçek zamanlı log toplama gibi çeşitli alanlarda kullanılır
- Temel fikir, her yeni öğe geldiğinde 1/n olasılıkla depolama alanını güncelleyerek tüm öğelere eşit seçilme şansı vermektir
- Birden fazla örnek seçilecekse olasılık k/n olarak genişletilir ve bu olasılığa göre mevcut örneklerden biri rastgele değiştirilir
- Bu algoritma, az bellek kullanımıyla bile adil örnekleme garantisi verir ve gerçek zamanlı işlemenin verimliliğini ve güvenilirliğini artırır
Rezervuar örneklemenin kavramı ve gerekliliği
- Rezervuar örnekleme, toplam boyutu bilinmeyen veri kümelerinden adil biçimde örnek seçmeye yarayan verimli bir tekniktir
- Genel durumda, verinin boyutu biliniyorsa rastgele indeks seçme yöntemi etkilidir; ancak boyut bilinmiyorsa bu yöntem uygulanamaz
- Doğrusal biçimde gelen büyük hacimli veride (ör. log akışı) bellek kullanımını sınırlamak gerekir; aynı zamanda her verinin eşit olasılıkla seçilmesi de istenir
Boyutu bilinen durumda örnekleme
- Sınırlı boyuttaki bir kümede (ör. 10 kart) tüm öğeleri karıştırıp baştan istenen kadarını seçmeye dayanan shuffle yöntemi, adilliği garanti etmek için uygundur
- Bilgisayarın array yapısı kullanıldığında, doğrudan rastgele indeks seçerek hızlı biçimde örnek çıkarılabilir
- Ancak gerçekte milyonlarca veri ya da boyutu bilinmeyen akışlarda bu yaklaşım verimsizdir
Boyutu bilinmeyen durumda örnekleme: sorunlar ve gereklilik
- Veriyi tek tek sıralı olarak alırken yalnızca 1 öğe saklayabildiğiniz ve geçmiş veriye geri dönemediğiniz durumlar pratikte sık görülür
- Log toplama sistemlerinde ani trafik artışları yaşanabilir; bu nedenle sunucu aşırı yükünü önlemek için verinin yalnızca bir kısmını örnekleyip göndermek gerekebilir
- Rastgele ilk birkaç öğeyi seçmek, tüm öğelere eşit fırsat vermediği için adillik sorununa yol açar
Rezervuar örnekleme algoritmasının prensibi
- Her veri geldiğinde o ana kadar alınan toplam sayı n hesaplanır ve yeni verinin 1/n olasılıkla seçilmesi sağlanır
- İlk veri kesin olarak seçilir; sonraki her yeni veri ise giderek azalan olasılıkla mevcut verinin yerini alarak eşit seçilme olasılığını korur
- Sonunda bellekte kalan verinin toplam içindeki hangi öğe olduğu fark etmeksizin olasılık eşit olur
- Yazı tura atmak yerine 1/n olasılığı kullanmak, tüm verilere adil fırsat tanınmasını sağlar
Matematiksel sezgi (kart örneğiyle açıklama)
-
- veri: kesin olarak seçilir (olasılık 1/1'dir)
-
- veri: 1/2 olasılıkla seçilir, mevcut veri ise yalnızca %50 olasılıkla kalır
-
- veri: yeni veri 1/3 olasılıkla seçilir, mevcut verilerin hayatta kalma olasılığı ise bunun tamamlayıcısı kadar birikir
- Genelleştirildiğinde, n'inci veriye kadar her veri her zaman 1/n olasılığa sahiptir
Birden fazla örnek seçmeye genişletme (k-out-of-n)
- k adet örnek seçmek için yeni veri k/n olasılıkla seçilir; seçildiğinde şu anda saklanan öğelerden biri rastgele değiştirilir
- Bu yöntemle de saklanan tüm öğeler örnek içinde aynı olasılıkla kalır
- Sabit bellekle (yalnızca k kadar) çalışarak büyük veri akışlarında bile adil şekilde birden fazla örnek seçmek mümkündür
Log toplama hizmetlerinde rezervuar örnekleme kullanımı
- Her saniye gelen loglar arasından en fazla k tanesi (ör. 5 tane) rezervuar örnekleme ile seçilir ve yalnızca bu örnekler sunucuya gönderilir
- Veri az olduğunda tüm loglar gönderilir ve kayıp yaşanmaz; trafik patladığında ise k'den fazla gönderim yapılmadığı için hizmet kararlılığı korunabilir
- Örnekleri belirli aralıklarla göndermek gerçek zamanlılık açısından küçük bir gecikme yaratsa da genel olarak kararlılık ve maliyet verimliliği sağlar
Ek uygulamalar ve referans materyaller
- Bazı veriler (ör. hata logları) daha önemliyse ağırlıklı rezervuar örnekleme (Weighted Reservoir Sampling) varyantı kullanılabilir
- Daha ileri kavramlar Wikipedia gibi dış kaynaklarda yer alsa da temel prensip adilliği korumaktır
Sonuç
- Rezervuar örnekleme, boyutu bilinmeyen veri akışlarında bellek açısından verimli ve adil örnekleme yapabilen son derece zarif ve pratik bir algoritmadır
- Gerçek zamanlı veri işlemede hız, tutarlılık ve düşük kaynak kullanımı gibi avantajları sayesinde birçok alanda yüksek kullanım değerine sahiptir
1 yorum
Hacker News görüşleri
Çocukken kırsalda yaşadığımız dönemde babamın bir arkadaşının her yıl işi gereği dağdaki ptarmigan (kar tavuğu) popülasyonunu ölçmesi gerekiyordu
Belirlenmiş bir rotayı izleyip belli aralıklarla kuşları ürkütüp havalandırarak sayım yapıyordu
Bu sayıları ilgili ofise gönderiyor, ofis de toplam popülasyonu tahmin ediyordu
Bir yıl bu arkadaş yurtdışındaydı, bu yüzden yöntemi başka bir arkadaşına ayrıntılı biçimde anlatıp işi ona bıraktı
Ama gerçek sayım günü geldiğinde o arkadaş bunu tamamen unutmuş ve uğraşmamak için kulağa makul gelen bazı sayılar uydurup göndermiş
Ertesi yıl yerel gazetenin birinci sayfasında “ptarmigan popülasyonunda rekor artış” başlığı çıktı
Bu kadar ani bir değişimin haber olmasının nedeni, bu sayının av ruhsatlarını belirlemek için kullanılmasıydı. Arkadaşı bunu düşünmemişti
Daha önce büyük bir kayak merkezi rezervasyon sistemi üzerinde çalışırken resmi istatistik raporunu bitirmem gerekmişti (misafir-gece gibi devlete sunulan veriler)
Zaman çok dardı ve gece boyunca çalışıyordum; o yılın istatistik verileri gerçek değerlerden oldukça farklıydı
Merhaba! o/
Bu yazının yazarı benim. Sorulara ve geri bildirimlere açığım
Tüm yazılardaki kodlar https://github.com/samwho/visualisations adresinde MIT lisansıyla mevcut. Rahatça kullanabilirsiniz
Bence çok iyi bir yazı
Reservoir sampling’i optimize etmenin başka bir yönü de, her öğede değiştirip değiştirmeyeceğine bakmak için rastgele sayı çekmek yerine Geometric dağılımdan bir atlama uzunluğu çekmek
Tape drive gibi art arda çok sayıda öğeyi ucuza atlayabildiğiniz durumlarda ilginç oluyor (teyp uzunluğunu önceden bilmiyorsunuz ama atlama sırasında sistemin büyük kısmını uyku modunda tutabilirsiniz)
n öğeden k örnek seçmek için yaklaşık O(k * log(n/k)) kez örnekleme ve atlama yeterli oluyor
Benim sevdiğim bir başka fikir de, her kart geldiğinde ona rastgele bir öncelik atayıp en yüksek k taneyi elde tutmak
Bununla ilişkili bir başka problem ise, uzunluğu bilinmeyen bir akıştan yalnızca en iyi k öğeyi O(n) zaman ve O(k) alanla seçmek
Her şeyi boyutu 2*k olan sırasız bir tampona koyup, dolduğunda randomized quickselect veya median-of-medians kullanarak sadece en iyi k taneyi bırakıyorsunuz
Bu işlemi n öğe boyunca sürdürünce O(n) zaman gerekiyor
İlgili bir başka teknik olarak rendezvous hashing de ilginç
Ayrıca alias method için https://www.keithschwarz.com/darts-dice-coins/ yazısı faydalı olabilir
Bunun iç içe kullanılıp kullanılamayacağını merak ediyorum
Örneğin benim servisimin reservoir sampling yapması, log toplayıcı servisinin de reservoir sampling yapması durumunda, bunun yalnızca log toplayıcının bir kez reservoir sampling yapmasına eşdeğer olup olmadığını soruyorum
Özellikle animasyonlar ve anlatım çok hoşuma gitti
Özellikle grafikte 100 kez karıştırma gibi farklı etkileşimler etkileyiciydi
Başta 10 karttan ya da 436,234 karttan 3 kart seçmekten söz ederken bir anda yalnızca tek tek kartlara bakıp 1 kart seçme örneğine geçince biraz kafam karıştı
“Şimdi işin içine eğriler katacağız!” kısmında bir bölüm ayracı olsa anlaması daha kolay olurdu gibi geldi.
Artık elinizde yalnızca 1 kart tuttuğunuzu ve destenin boyutunu da bilmediğinizi varsayıyoruz
Site tasarımını özellikle beğendim
Etkileşimler, köpek karakteri, yazı tipi ve renkler, genel yerleşim; hepsi çok iyi olmuş
Blogun tamamı tam bir hazine sandığı gibi
Onu keşfettiğime sevindim
Grafikler çok hoşuma gitti
Yalnız bu yöntemin istatistiksel olarak tamamen sağlam olup olmadığından emin değilim. Belirli bir zaman aralığındaki tüm loglar eşit olasılıkla seçiliyor ama “yavaş dönemlerde” oluşan logların toplam istatistikte olduğundan fazla temsil edilmesinden endişe ediyorum
Örneğin tüm sistemde hangi endpoint’in en çok CPU kullandığını bulup optimize etmek istiyorsanız, trafiği kısa süreli patlayan endpoint’lerin logları olduğundan az temsil edilip gerçekte en çok kullanılan endpoint’leri doğru değerlendirememenize yol açmaz mı diye soruyorum
Ya da servis bazlı kapasite planlamasında da burst trafiği olan servisler az temsil edilecek gibi duruyor
Reservoir sampling’in hangi kullanım alanlarına uygun olduğunu ve bu yöntemle ne tür istatistiksel analizlerin yapılabileceğini merak ediyorum
Çok iyi bir yazı; matematik ya da istatistik böyle öğretilse öğrenmesi gerçekten eğlenceli olurdu
Bana https://distill.pub/ hissi verdi
“Sometimes the hand of fate must be forced” ifadesi aklımda kaldı
Etkileşimli anlatım tarzını özellikle sevdim
Site tasarımı ve öğretme biçimi gerçekten çok güzel. Teşekkürler
Blogda RSS akışı olup olmadığını merak ediyorum
Çok açık ve iyi görselleştirilmiş bir yazı
Daha ileri seviye bir genişletme olarak, temel yöntem yerine bir seferde kaç öğe atlanacağını hesaplayan algoritmalar da var
Daha ayrıntılı açıklama için https://richardstartin.github.io/posts/reservoir-sampling faydalı olabilir
Güzel yazı ve açıklama
Gerçek log toplamada son çare olarak adillik (fairness) kullanmadan önce çeşitli başka yöntemlerin denenmesini öneririm
Örneğin loglara öncelik verip, önceliği düşük olanları (verbosity’si yüksek olanları) önce atabilirsiniz
Anlamsal olarak tek bir etkinliği oluşturan loglarda, ortadaki tekrarları azaltıp yalnızca başlangıç, bitiş ve önemli durum değişikliklerini saklayabilirsiniz
Benzer/tekrarlı logları toplulaştırıp özet halinde kaydetmek hem toplam hacmi azaltır hem de eğilimleri görmek için daha faydalı olur
Son zamanlarda observability konusunda epey şey öğreniyorum; bahsedilen yöntem head/tail sampling karışımı
İlgili açıklamalar için https://docs.honeycomb.io/manage-data-volume/sample/ adresine bakılabilir
Yazı da bu noktaya değiniyor
Aslında tüm low priority logları atmak yerine onları bir “bütçe” kavramıyla sınırlamak önemli
Toplam log sayısı da ayrıca daha üst düzey bir bütçeyle sınırlandırılabilir
Reservoir sampling bu tür kısıtları da iyi şekilde ele alabiliyor
Güzel yazı ve açıklama
Vitter’in makalesinde “Algorithm R” anlatılıyor; bu bir reservoir sampling yöntemi.
https://www.cs.umd.edu/~samir/498/vitter.pdf adresine bakabilirsiniz
Vitter’in daha eski makalesi https://dl.acm.org/doi/10.1145/358105.893, Knuth’un TAOCP 2. cildine atıf yapıyor ama Knuth’ta da açık bir kaynak yok
Çok iyi derlenmiş; weighted reservoir sampling ile ilgileniyorsanız https://gregable.com/2007/10/reservoir-sampling.html adresinde açıklanıyor
Bunu dağıtık ortamda map-reduce ile kolayca uygulamanın bir yolu da var; ayrıca çok basit bir yöntem olarak her öğeye rastgele bir değer eşleyip Top N’i koruyabilirsiniz
Her öğe için POW(RANDOM(), 1.0 / weight) ile bir öncelik üretip Top N’i seçen temel yöntem, ağırlık (weight) çok büyük ya da çok küçük olduğunda sayısal kararlılığını kaybedebiliyor
Ayrıca ortaya çıkan örneklem, özgün ana kitlenin dağılımını yeterince iyi yansıtmayabilir. Özellikle toplam weight az sayıdaki öğede yoğunlaştığında bu eğilim daha da belirginleşir
Yine de çoğu durumda yeterince iyi bir yaklaşım sayılır
Ayrıntılar için https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html yazısı açıklayıcı
Bu yazıyı okuyunca Müttefiklerin 2. Dünya Savaşı sırasında Alman tankı üretim miktarını seri numaralarından tahmin etme yöntemi aklıma geldi
O dönemde sahadaki personel gerçek üretimi yaklaşık 5 kat fazla tahmin etmişti ama seri numarası yöntemi %90’ın üzerinde doğruluk sağlamıştı
Harika bir gönderi ve görselleştirmeler gerçekten müthiş
Gerçek bir hizmette benzer bir varyant kullanarak çok büyük akışlarda değişen percentile değerlerini gerçek zamanlı tahmin ediyoruz
Percentile değeri ara sıra değişiyor ama çoğu zaman çok sayıda yineleme boyunca sabit kalıyor. Alttaki veri quasi-stationary
Bunu bir splay tree ile yedeklerseniz, diğer yöntemlere göre RAM kullanımına kıyasla hata payı daha geniş olsa da amortized O(1) zamanda tahmin edebiliyorsunuz
Değiştirme olasılığını ayarlayarak verinin “half-life”ını da düşürebilir, yani tahmini daha yeni verilere doğru yanlı hale getirebilirsiniz
Veri bilimi açısından bakınca, veri miktarının kendisi de önemli bilgi taşıdığı için örnekleme oranının mutlaka birlikte kaydedilmesi gerektiğini düşünüyorum
Örneğin örnekleme oranı %10 ise her örnek için 10 değerini kaydedip toplam sayıları, toplamları, ortalamaları vb. doğru biçimde geri kurabilir ve tahmin edebilirsiniz
Bu yazı telemetry (trace, log, metric) toplamanın içerdiği ödünleşimleri çok iyi gösteriyor
Bu veri analizi alanının giriş eşiği yüksek ve birçok geliştiricinin gözden kaçırdığı bir konu
Aynı görünen veriler bile hangi yöntemle örneklendiğine bağlı olarak gözlenen grafikte tamamen farklı görünebilir ve birçok kişi bunu gözden kaçırıyor