Linear Counting: Benzersiz Değerlerin Sayısı Nasıl Tahmin Edilir

Elimizde gerçekten çok büyük bir veri kümesi varsa, içindeki benzersiz değerlerin sayısını nasıl hesaplayabiliriz? Örneğin büyük bir sitedeki, hatta koskoca bir .com/.org/.whatever alan adındaki benzersiz kullanıcıların sayısını ölçen bir servisimiz olabilir.

Naif Yaklaşım

Tamam, bunda düşünülecek ne var ki: verilerin üzerinden geçeriz ve her değeri uygun bir veri yapısında tam bir kez saklarız. Python’da şöyle yazabiliriz (kod gereksiz yere uzun, bunu bilerek yaptım):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Çalışıyor. Peki ya veriler 36 karakterlik benzersiz v4 kimlikleri (UUID) olsaydı ve bu benzersiz kimliklerden on milyon tane olsaydı? Program yine doğru değeri hesaplar, ama ne kadar bellek tutar? Hesaplayabiliriz. Basit olsun diye UUID’yi gerçekten 36 karakterlik bir string olarak sakladığımızı varsayalım. Bir UUID 36 bayt yer kaplar, on milyon kimlik ise 360 MB tutar.

İtiraf edelim, bu az bir şey değil. Benzersiz kimlik sayısı yüz milyon olsaydı, kaplanan bellek gigabaytlarla ölçülürdü. Üstelik burada sadece verinin kendi kapladığı yeri sayıyoruz. Python/JavaScript’in getirdiği ek yükü (overhead) de eklersen, on milyon kimlikle bile gigabaytlara ulaşabilirsin:

Bunu istemezsin. Peki bundan nasıl kurtuluruz?

Kimlikleri daha verimli saklamayı deneyebiliriz, Python yerine C kullanıp bellek ihtiyacını ciddi biçimde azaltabiliriz, ama yine de istediğimiz gibi olmaz ve böyle bir program hâlâ inanılmaz miktarda yer kaplar. Geriye şu soruyu sormak kalıyor: benzersiz değerlerin sayısının tam olarak 9.563.618 olup olmadığını gerçekten bir tekine kadar bilmemiz gerekiyor mu? Sayı 9.547.666 olsaydı bir şey değişir miydi? Cevabın “evet, değişir, tam sayıyı istiyorum” ise buyur, öyle yap. Aksi hâlde, bir veri kümesindeki benzersiz değerlerin sayısını olabildiğince doğru, hızlı ve çok az bellekle tahmin etmenin yollarına bakalım.

Özet Fonksiyonu — Kurtarıcımız

Girdi olarak bir string alıp çıktı olarak n bitlik bir sayı döndüren bir özet fonksiyonu (hash fonksiyonu) düşünelim. Sen daha çok “string döndüren” özet fonksiyonlarına alışkınsan, o string’in de ayrıca bir sayıya dönüştürüldüğünü düşün; bunda bir zorluk yok. Bit sayısı, sayının ne kadar büyük olabileceğini belirler. 8 bitlik bir fonksiyon sekiz bitlik bir sayı döndürür ve sekiz bitte 2⁸ farklı değer saklanabilir; genellikle 0’dan 255’e kadar tam sayılar. Bundan sonra 24 bitlik bir özet fonksiyonuyla çalışacağız. Böyle bir fonksiyon 2²⁴ farklı değer döndürür, yani 16.777.216 tane.

Değerlerin kendisini saklamak yerine onların 24 bitlik özetlerini saklayacağız. On milyon adet 24 bitlik özeti saklamak için 30 MB yeterli. Bu, önceki 360 MB’a göre bir mertebe daha iyi. Kod şöyle olabilir:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

hash fonksiyonu Python’un yerleşik fonksiyonudur ve bir tam sayı döndürür. nhash fonksiyonu ise n bitlik bir özet fonksiyonunun naif bir uygulamasını gösterir; nasıl çalıştığını anlaman önemli değil, çünkü zaten doğru çalışmıyor — fonksiyonun sonucu 24 bit yer kaplamıyor, ama şimdilik fark etmez, buradaki amacım ilkeyi göstermek.

Sonra sıra, benzersiz değerleri sayan count_unique_using_nhash fonksiyonuna geliyor. Tüm değerlerin üzerinden geçer, özetlerini hesaplar ve o değer daha önce yoksa özeti found değişkenine kaydeder.

Bu yaklaşımın sorunu, özet fonksiyonunun farklı string’ler için aynı sağlama toplamını (checksum) döndürebilmesidir — bir çakışma olabilir. Ne kadar çok çakışma olursa sonuç o kadar hatalı çıkar. count_unique_using_nhash fonksiyonu neredeyse her zaman gerçek benzersiz değer sayısından daha küçük bir sayı döndürür.

Peki hangi özet fonksiyonunu seçmeliyiz? Bu o kadar önemli değil, ama genel olarak MurmurHash’in bir çeşidi önerilir.

Bit Eşlemler

C programlama dersinde dikkatli dinledin mi? Dinlediysen bit eşlemleri biliyorsun. Bunları nasıl kullanabiliriz?

Fikri bir dizi üzerinde anlatalım. Hesapladığımız sağlama toplamlarını saklamak zorunda değiliz; uzunluğu 2²⁴ olan bir dizi oluşturup tüm elemanlarını sıfırla başlatabiliriz. Sonra bir sağlama toplamıyla karşılaştığımızda — ki o bir sayıdır! — dizide checksum indisine bir yazarız. Böylece bu sağlama toplamını daha önce bulduğumuzu işaretlemiş oluruz. Benzersiz eleman sayısı da yaklaşık olarak bu dizideki birlerin sayısına eşit olur. Kod şöyle olabilir:

def count_unique_using_array(values):
    # 2^24 uzunluğunda, tamamı sıfırla başlatılmış liste
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Ancak burada dizi kullanmak bellek açısından çok pahalıdır, çünkü her hücreye ya bir ya da sıfır yazmamız gerekiyor. Bunun yerine bit dizisi kullanabiliriz. Anlaman için: bir tam sayı (integer) örneğin 32 bitte saklanabilir. 354 sayısını ikilik sisteme çevirirsek 101100010 elde ederiz. 354 sayısı bilgisayarda 32 bitlik bir integer olarak şöyle saklanır (ayrıntıları boş ver, tamam mı?):

00000000 00000000 00000001 01100010

Bu oldukça hoş bir biçim ve işimize yarayabilir, değil mi? Çünkü fonksiyonumuzda yalnızca birleri ve sıfırları saklamak istiyoruz ve şimdi sıradan bir sayının aslında bir yığın sıfır ve birden başka bir şey olmadığını gördük (bilgisayardaki her şey gibi…). Kısacası bit düzeyindeki operatörler sayesinde 1’i gerçekten tek bit yer kaplayacak şekilde saklayabiliriz.

Diziyi kullanan fonksiyonumuza dönelim. Bunu bit dizilerine çevirsek, 24 bitlik özet fonksiyonu için 2²⁴ bitlik bir bit dizisi yeter; bu da 2 MiB eder. Bu hiç fena bir iyileştirme değil!

2³² farklı çıktı değeri olan, yani 4.294.967.296 değer üretebilen 32 bitlik bir özet fonksiyonu kullansaydık, yarım gigabaytlık bir bit dizisine ihtiyacımız olurdu. Bu hiç de kötü sayılmaz, çünkü milyarlara kadar benzersiz değeri sayabiliyoruz.

Linear Counting

Özet fonksiyonu kullanınca benzersiz değerlerin sayısı için yalnızca bir tahmin elde ettiğimizi söylemiştim. Benzersiz değerlerin sayısı, özet fonksiyonunun farklı çıktı sayısına yaklaştıkça bu tahmin daha da hatalı olur. Veri kümesinde beş milyar benzersiz değer varsa bunu 24 bitlik bir özet fonksiyonuyla sayamayacağımız açık.

Yine de özet fonksiyonlarıyla hesapladığımız tahmin daha da iyileştirilebilir. Bunun için basit bir fikir kullanılır: veri kümesinde ne kadar çok benzersiz değer varsa zamanla çakışmaların oluşması o kadar olasıdır. (Çakışma = iki farklı girdinin özet fonksiyonundan aynı çıktıyı, aynı sağlama toplamını alması.) Şimdi biraz hesap yapacağız, o yüzden birkaç değişken tanımlayalım:

• n bitlik bir h özet fonksiyonuyla çalışacağız.
• h fonksiyonunun tüm olası çıktılarının sayısı böylece 2n olur. Bu sayıyı m harfiyle gösterelim, yani m=2n.
• Hangi sağlama toplamlarını bulduğumuzu sakladığımız bit dizisini büyük A harfiyle gösterelim. A dizisinin uzunluğu m’dir.
• Algoritmamızla tüm veri kümesinin üzerinden geçtikten sonra bit dizisindeki bazı değerler sıfır, bazıları bir olacak. Bizi asıl ilgilendiren “sıfırların sayısı bölü dizinin uzunluğu” oranı; bu, bit dizisindeki sıfırların göreli payını verir. Başta bu oran 1’dir, çünkü dizi baştan sona sıfırlarla başlatılmıştır. Yarı yarıya olsaydı oran yarım olurdu, vb. Bu değeri Z ile gösterelim ve Z = sıfırların sayısı / m olarak hesaplayalım.

Bu noktada Z değeri ne kadar yüksekse, benzersiz değer tahminimizin doğru olduğundan o kadar emin oluruz. Örneğin boş bir veri kümesinden geçersek bit dizisinde yalnızca sıfırlar kalır ve Z değeri bire eşit olur — böylece veri kümemizde bit dizisindeki birlerin sayısı kadar, yani sıfır tane benzersiz eleman olduğundan tamamen emin oluruz.

Z değeri 0,99 ise bit dizisinin yüzde birinin birlerle dolu olduğu anlamına gelir. Dizinin %99’u sıfırlardan oluşur. Bu hâlâ iyidir; hesap sırasında çok fazla çakışma olmamış olması muhtemeldir ve belki hiç ya da çok küçük bir düzeltme gerekir. Ama Z değeri 0,05 ise dizinin yalnızca %5’i sıfır olarak kalmıştır ve hesap sırasında büyük ihtimalle çok sayıda çakışmayla karşılaştık — büyük bir düzeltme gerekecek.

Peki bu düzeltmeyi nasıl hesaplayacağız? Bize logaritma yardım edecek; grafiği şöyle olan bir fonksiyon:

Bizi grafiğin (0, 1] aralığındaki kırmızı kısmı ilgilendiriyor. x ekseninde Z değerini gösterirsek, Z ne kadar büyükse y değeri o kadar sıfıra yaklaşır. Tersine, Z ne kadar küçükse y değeri o kadar küçük olur. Sonuçta tahmini, bu sayıyı -m ile çarparak buluruz. Dikkat et: yeterince küçük bir Z değeri için -1’den bile küçük bir sayı elde ederiz ve bu değeri -m ile çarparsak m’den büyük bir tahmin buluruz: yani benzersiz değerlerin sayısının, h özet fonksiyonundan çıkabilecek tüm sağlama toplamlarının sayısından büyük olduğunu tahmin etmiş oluruz.

Benzersiz değerlerin sayısı p için tam formül şöyle olur:

$$p=-m\cdot \ln Z$$

Uygulama (bit dizisi olmadan, yalnızca sıradan dizilerle) şöyle olabilir:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log burada e tabanlı doğal logaritmadır
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

linear_counting fonksiyonunda önce, n bitlik özet fonksiyonu kullanan önceki algoritmayla ilk tahmini hesaplarız. Sonra dizideki sıfırların oranını hesaplar ve formüle göre düzeltmeyi yaparız. Koddaki logaritma doğal logaritmadır. nonunique_values değişkeni number_of_unique_values kadar benzersiz string içerir; bu örnekte nonunique_values listesinde on bin benzersiz değer vardır. Altıncı satırdaki o tuhaf kod, listede aynı değerlerden birden fazla bulunmasını sağlar: listenin sonuna aynı listeyi ekleriz, böylece her değer listede iki kez yer alır. Sonra hesaplamaya başlarız. İdeal olarak fonksiyonun, listenin on bin benzersiz değer içerdiğini döndürmesi gerekir. Çıktı:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Her seferinde farklı bir nonunique_values listesi üretildiği için sonuçlar her çalıştırmada değişecektir. 16 bitlik bir özet fonksiyonu kullandık. count_unique_using_array fonksiyonunun ilk tahmininin, listenin 9.289 benzersiz değer içerdiği yönünde olduğunu görüyoruz. Bu tahmini düzeltmeyle 10.017’ye yaklaştırdık; bu oldukça iyi: tahminimiz yalnızca %0,17 büyük, daha önce ise %7,11 küçüktü — bu epey fazla.

Daha “büyük” bir özet fonksiyonu, örneğin 24 bitlik bir fonksiyon alsaydık daha doğru bir sonuç elde ederdik:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

İlk tahminin kendisi zaten iyiydi, düzeltmeyle tam on bine ulaştı. Gösterim için bir milyon benzersiz kimlik de deneyebiliriz, yani number_of_unique_values = 1000000. 24 bitlik özet fonksiyonuyla şu sonuçlara ulaşırız:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Fena değil. Üstelik bunu bit dizisi olarak uygularsak dizi yalnızca bahsettiğimiz iki megabaytı (+ dilin kendi tükettiğini) yiyecek. Bence oldukça iyi. But we can do better! Much better. Ama onu bir sonraki yazıya bırakalım.

Bu arada A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF] makalesini okuyabilirsin. Ya da serinin bir sonraki yazısına geçebilirsin: Min Value algoritması.