Elimizde bir örnek ile başlamak daha anlaşılır olacaktır. Problemimiz log dosyalarından okunan IP verilerinin distinct count işleminin yapılması, diğer bir tabir ile unique ip’lerin sayılması olsun.
Bu problem oluşturur mu diye sorabilirsiniz. Eğer onlarca sunucunuz var ve onların loglarından bu değeri olmaya kalkarsanız, burada yüz milyonlarca satır logdan bahsediyorum, her bir IP değerini tek tek elinizdeki distinct olarak tutuğunuz IP listeniz ile karşılaştıracaksınız demektir. Bu unique ip listesinin bir üst sınırı var mıdır? Varsa ne kadardır?
Şimdi elimizde olan unique ip listesinin üst sınırını bulamasak da ne kadar hafızaya mal olabileceğini tahmin etmeye çalışalım. Örneğin 100M unique ip listesi oluşturabiliyoruz diyelim günde. Ve iki durumda bu ip değerini sakladığımı varsayalım; birincisi ip değerlerini STRING olsun, diğeri ise INTEGER olsun. Eğer STRING olarak saklayacak ise her ip değeri için “4x3 + 3” maximum karakter , “4x1 + 3” ise alabileceği minimum karakter sayısı olacaktır. Biz maximum değer üzerinden gidersek, bize her ip değeri için 15 karakter yani 15 byte değerinde hafızada yere mal olacaktır.
100.000.000 x 15 = 1.5 x 10^9 byte edecektir. Bu da yaklaşık 1,40 GB hafıza alnına denk gelecektir.
Tabii bunların arasında bir ip değeri için 100M luk liste içinde var mıdır diye her defasında kontrol etmek ise ek olarak bir CPU maliyeti olarak karşınıza çıkacaktır.
Şimdi bir de her ip değerinin INTEGER olarak karşılığını bulduğumuzu ve onu kıyaslamak için sakladığımızı varsayalım. Burada integer 32-bit değerden oluşuyor ise 4 bytelık bir yer kaplayacaktır.
Buna göre bir ip adresi mininum veya maximumu gözetmeye gerek kalmadan 4 bytelık bir alanı kaplayacağını da söyleyebiliriz. String olarak saklamaktan daha iyi olduğu aşikar.
100.000.000 x 4 = 4 x 10^8 byte edecektir. Bu da 372 MB yer kaplayacak demek olacaktır. Şimdiden 3/4 oranında yerden kazandık. Ve CPU maliyetine de String değerine göre azalmış varsayabiliriz.
Şimdi bunlar ilk akla gelen çözümler ve bu çözümlerin problemi üst sınırlarının kestirilememesi. Bu şu an bizim için bir problem oluşturmayabilir. Ama yinede işin içine daha zarif bir çözüm sokmak güzel olacaktır.
Üçüncü olarak ise BITMAP çözümüyle yapmaya çalışalım. Önce bunu nasıl yapacağız açıklayayım; elimizde hafıza alanı olsun ve bu hafıza alanına yalnızca 0 veya 1 değerleri yazabilelim. Yani sadece bir bit yazma hakkımız olsun. Ve bu hafıza alanını istediğimiz gibi genişletebilelim de. Şimdi ip lerin integer değerlerini hafıza alanındaki dizide sıra numarası gibi kullanalım. Ve o sıranumarasına denk gelen alanı 1 yapalım. Hepsi bu kadar. Elimizde her unique ip değeri için 1 bit artan bir şey olacaktır artık.
Şimdi eğer aynı ip adresi elimizde var mı diye kontrol etmek de basitleşecektir. Eğer ip nin integer değeri sıra noyu (offset) gösteriyorsa, o sıra nodaki bit 1 ise var demektir. Yok ise 1 yapmamız yeterlidir. Ancak bunu kontrol etmemize bile gerek yok. Direk ve her seferinde 1 yapmak yeterli olacaktır. Bu CPU maliyetini de en aza indirecektir.
Sonrasında ise unique ip sayısı elimizde 1 olan bitlerin sayısı kadar olacaktır. Hepsi bu kadar.
Burada sınır integer değeri olacaktır. en büyük ip değeri “255.255.255.255” olacaktır. Onun integer değeri ise 4294967295 dir ve 4294967295 adet bit demektir. Bu yaklaşık 500 MB hafıza demektir. Bundan daha fazla hafıza alanına ihtiyacınız olmayacaktır.
Yani sitenizin trafiğinden bağımsız olarak, distinct count almak için 500MB bir ortak hafıza alanından
daha büyük bir yere ihtiyaç olmadan böyle bir sayımı gerçekleştirebileceğiz.
Detaylar yine kullanıma göre değişecektir. Mesela bu değeri günlük tutarsanız, 500 MB / gün şeklinde bir yere ihtiyacınız olacaktır. Bu öngörülebilir bir değerdir.
Java’da bu konuda yardım edebilecek bir sınıf ise mevcut. Adı ise Bitset . Burada bitset nesnesinde bir offset değerini yani sıranolu alanı 1 ya da 0 yapabilirsiniz. Sonrasonda ise cardinality() fonsiyonunu çağırdığınızda ise size 1 olan alanların sayısını yani istediğiniz sayıyı verecektir.
Burada ip değeri değilde herhangi bir metriği ölçebilirdik. Peki nasıl yapabilirdik bunu? Bir nesneye atadığımız bu değerin unique hashcode üretmesini ve her aynı değer için aynı hashcode değerini vermesini sağlayabilirsek, herhangi bir metriği distinct count yapabiliriz en az zahmet ve maliyetle…
NOT:
-------
Ayrıca doküman olarak da
buradan görüntüleyebilir veya indirebilirsiniz.
Kaynaklar:
———————
1- http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html
2- http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/
3- http://docs.oracle.com/javase/7/docs/api/java/util/BitSet.html
