HyperLogLog, benzersiz ziyaretçileri tek tek saklamadan nasıl sayıyor?

Bir makaleyi kaç kişinin okuduğunu bilmek, ilk bakışta basit bir iş gibi görünür. Oysa sayfanın kaç kez açıldığını saymakla kaç farklı kişinin okuduğunu saymak aynı şey değildir. HyperLogLog algoritması, bu ikinci soruyu kesin sonuç yerine gerçeğe yakın bir tahminle ve çok az bellekle yanıtlayan yöntemlerden biri.

Görüntüleme sayısı ile okuyucu sayısı neden farklı?

Görüntüleme sayısını tutmak için tek bir sayaç yeterlidir. Biri sayfayı her açtığında sayaç bir artar ve bu işlem neredeyse hiç bellek istemez. Ancak sabah kahvaltıda okumaya başladığı makaleye öğleden sonra yeniden dönen bir kişi, basit sayaçta iki kez sayılır.

Benzersiz ziyaretçiyi kesin olarak bulmak ise başka bir yük getirir. Sitenin her ziyaretçinin kimliğini kaydetmesi ve gelen kişinin daha önce uğrayıp uğramadığını kontrol etmesi gerekir. Yani tek bir sayı yerine ziyaretçi sayısı kadar kimlik bilgisi saklanır. Bu işlem her makale, her sosyal medya paylaşımı ve her reklam için ayrı ayrı yapılınca, yalnızca “Bunu kaç kişi gördü?” sorusu için devasa bir veri yığını oluşur.

Yazı tura deneyinden çıkan fikir

Algoritmanın temelinde zarif bir olasılık gözlemi var. Bir madeni paranın ilk kez tura gelene kadar atıldığını ve bu deneyin birçok kez tekrarlandığını düşünelim. Tüm sonuçları saklamak yerine yalnızca ilk turadan önce art arda en çok kaç kez yazı geldiği not edilsin.

Adil bir paranın her atışta yazı gelme olasılığı 1/2'dir. Art arda iki yazının olasılığı 1/4, üç yazının olasılığı 1/8 olur. Art arda 10 yazı geldiyse bu olasılık 1/1024'e iner; yani yaklaşık her 1.000 denemeden birinde böyle bir seri beklenir. Dolayısıyla en uzun yazı serisi, deneyin yaklaşık kaç kez tekrarlandığı hakkında ipucu verir.

HyperLogLog bu mantığı ziyaretçilere uyarlar. Her ziyaretçinin değişmeyen bir yazı tura dizisi olduğunu varsayar. Site dizilerin hiçbirini saklamaz; yalnızca karşılaştığı en uzun başlangıç serisinin uzunluğunu tutar. Örneğin 10 ziyaretçi arasında en uzun seri üç yazıysa algoritma yalnızca 3 sayısını saklar ve ziyaretçi sayısının yaklaşık 8 olabileceğini tahmin eder. Sonradan dört yazıyla başlayan bir dizi gelirse kayıtlı sayı güncellenir. Eski bir ziyaretçi geri dönerse hiçbir şey değişmez, çünkü o kişi her seferinde aynı diziyi üretir.

Bellek tasarrufu, ziyaretçi sayısı büyüdükçe belirginleşir. Yaklaşık 1.000 ziyaretçi için en uzun başlangıç dizisi 10 civarındayken, bir milyar ziyaretçide bu değer 30 civarına çıkar. Yani ziyaretçi sayısı muazzam biçimde artsa da saklanacak sayı çok küçük kalır.

Gerçek yazı tura yok, hash var

Bu yöntemin iki sorunu vardır. Ziyaretçilere gerçekten yazı tura attırmak mümkün değildir. Ayrıca şans eseri ortaya çıkan aşırı uzun bir dizi, tahmini ciddi biçimde bozabilir.

İlk sorunu hash (özetleme) fonksiyonları çözer. Bu fonksiyonlar bir girdiyi kurallara göre başka bir değere çevirir ve iyi tasarlandıklarında çıktıları rastgele görünür. Buna rağmen belirlenimcidirler: aynı girdi her zaman aynı çıktıyı verir. Örneğin user_8675309 kimliği, 01100101000100101000 gibi bir ikili diziye dönüşebilir. Algoritma sıfırları yazı, biri tura sayar. Böylece her kullanıcı rastgele görünen ama sabit bir diziye kavuşur.

Arka plan

Bir kümedeki farklı öğelerin sayısını tahmin etme problemi, bilgisayar biliminde uzun süredir üzerinde çalışılan bir konu. Kesin sayım, öğe sayısıyla orantılı bellek ister. Veri akışının hızlı ve çok büyük olduğu sistemlerde bu çoğu zaman pratik değildir. Bu yüzden olasılıksal veri yapıları, küçük bir hata payını kabul edip belleği ciddi ölçüde azaltmayı hedefler.

Kaynak metin ikinci sorunun çözümünü aktarmadan bitiyor; ancak yaygın uygulamalarda aşırı uzun bir dizinin etkisini azaltmak için ziyaretçiler çok sayıda gruba ayrılır. Her grubun en uzun dizisi ayrı tutulur ve sonuçlar bir ortalama yöntemiyle birleştirilir. Böylece tek bir şanslı dizi tahmini tek başına belirlemez.

Neden önemli?

HyperLogLog'un önemi, kullanım alanının genişliğinden geliyor. Google Analytics ziyaretçi metriklerini tahmin ederken algoritmanın geliştirilmiş bir sürümünden yararlanıyor. Algoritma genom araştırmalarından siber güvenliğe kadar farklı alanlarda da kullanılıyor.

Bir diğer boyut da gizlilikle ilgili. Ziyaretçi kimliklerini tek tek tutmak yerine yalnızca küçük bir özet saklamak, veri depolama yükünü azaltır. bu, algoritmanın tek başına gizlilik güvencesi olduğu anlamına gelmez; asıl kazanç bellek ve hız tarafındadır. Karşılığında ödenen bedel ise sonucun kesin değil, yaklaşık olmasıdır. Reklam gösterimi ya da paylaşım erişimi gibi büyük ölçekli sayımlarda küçük bir sapma çoğu zaman kabul edilebilir bir ödünleşimdir.