Bloom Filter'lar: H\u0131zl\u0131 ve Haf\u0131za Verimli \u00dcyelik Kontrol\u00fc<\/p>\n
Veri yap\u0131lar\u0131 d\u00fcnyas\u0131nda, b\u00fcy\u00fck veri k\u00fcmelerinde h\u0131zl\u0131 bir \u015fekilde \u00fcyelik kontrol\u00fc yapmak \u00f6nemli bir ihtiya\u00e7t\u0131r. Bu i\u015flem, bir \u00f6\u011fenin bir koleksiyonda bulunup bulunmad\u0131\u011f\u0131n\u0131 belirlemeyi gerektirir. Klasik yakla\u015f\u0131mlar\u0131n dezavantajlar\u0131 g\u00f6z \u00f6n\u00fcne al\u0131nd\u0131\u011f\u0131nda, Bloom filtreleri, bu g\u00f6revi y\u00fcksek h\u0131z ve d\u00fc\u015f\u00fck bellek t\u00fcketimiyle ger\u00e7ekle\u015ftiren etkili bir \u00e7\u00f6z\u00fcm sunar. Bu makalede, Bloom filtrelerini temel seviyeden ileri seviyeye kadar detayl\u0131 bir \u015fekilde ele alaca\u011f\u0131z, ger\u00e7ek d\u00fcnya senaryolar\u0131n\u0131 inceleyecek ve performans\u0131n\u0131 de\u011ferlendirece\u011fiz.<\/p>\n
Bloom filtreleri, olas\u0131l\u0131kl\u0131 veri yap\u0131lar\u0131d\u0131r. Ba\u015fka bir deyi\u015fle, %100 kesinlik yerine, y\u00fcksek olas\u0131l\u0131kla do\u011fru bir sonu\u00e7 verirler. Bu veri yap\u0131s\u0131, bir dizi bit dizisi (genellikle bir bit dizisi) ve birden fazla ba\u011f\u0131ms\u0131z hash fonksiyonu kullan\u0131r. Bir \u00f6\u011fe eklendi\u011finde, hash fonksiyonlar\u0131 \u00f6\u011fenin hash de\u011ferini hesaplar ve bu de\u011ferlere kar\u015f\u0131l\u0131k gelen bit dizisindeki bitler 1 olarak i\u015faretlenir. Bir \u00f6\u011fenin \u00fcyeli\u011fi kontrol edilirken, yine ayn\u0131 hash fonksiyonlar\u0131 kullan\u0131l\u0131r ve kar\u015f\u0131l\u0131k gelen bitler kontrol edilir. E\u011fer t\u00fcm bitler 1 ise, \u00f6\u011fenin koleksiyonda oldu\u011fu *olas\u0131l\u0131kla* s\u00f6ylenir. Ancak, baz\u0131 durumlarda yanl\u0131\u015f pozitifler (false positives) olu\u015fabilir; yani, asl\u0131nda koleksiyonda olmayan bir \u00f6\u011fenin koleksiyonda oldu\u011fu \u015feklinde yanl\u0131\u015f bir sonu\u00e7 al\u0131nabilir. Yanl\u0131\u015f negatifler (false negatives) ise asla olu\u015fmaz; koleksiyonda olan bir \u00f6\u011fenin koleksiyonda olmad\u0131\u011f\u0131 \u015feklinde bir sonu\u00e7 asla verilmez. Yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131n\u0131 minimize etmek i\u00e7in, bit dizisinin boyutu ve hash fonksiyonlar\u0131n\u0131n say\u0131s\u0131 dikkatlice se\u00e7ilmelidir.<\/p>\n
Bloom filtrelerinin etkinli\u011fi, kullan\u0131lan hash fonksiyonlar\u0131n\u0131n kalitesine do\u011frudan ba\u011fl\u0131d\u0131r. Ideal bir hash fonksiyonu, girdi uzay\u0131n\u0131 e\u015fit olas\u0131l\u0131kla \u00e7\u0131kt\u0131 uzay\u0131na da\u011f\u0131tmal\u0131d\u0131r. Y\u00fcksek kaliteli hash fonksiyonlar\u0131 kullanmak, yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131n\u0131 d\u00fc\u015f\u00fcr\u00fcr. Yayg\u0131n olarak kullan\u0131lan hash fonksiyonlar\u0131 aras\u0131nda MurmurHash, CityHash ve FNV hash fonksiyonlar\u0131 bulunur. Se\u00e7im, uygulaman\u0131n belirli gereksinimlerine ve performans kriterlerine ba\u011fl\u0131d\u0131r. \u00d6rne\u011fin, kriptografik g\u00fcvenlik gerektiren uygulamalar i\u00e7in kriptografik hash fonksiyonlar\u0131 tercih edilmelidir. Ancak, genel ama\u00e7l\u0131 uygulamalar i\u00e7in daha h\u0131zl\u0131 ve daha az kaynak t\u00fcketen hash fonksiyonlar\u0131 daha uygun olabilir. Hash fonksiyonunun se\u00e7iminde, \u00e7ak\u0131\u015fma olas\u0131l\u0131\u011f\u0131n\u0131 minimize etmek ve e\u015fit da\u011f\u0131l\u0131m\u0131 sa\u011flamak hedeflenir.<\/p>\n
Bloom filtrelerinin ger\u00e7ek d\u00fcnyada nas\u0131l kullan\u0131ld\u0131\u011f\u0131n\u0131 anlamak i\u00e7in bir \u00f6rnek verelim: \u0130nternet taray\u0131c\u0131s\u0131 \u00f6n belle\u011fi. Taray\u0131c\u0131, ziyaret edilen web sayfalar\u0131n\u0131n ve kaynaklar\u0131n\u0131n bir \u00f6n belle\u011fini tutar. Bir sayfa yeniden ziyaret edildi\u011finde, taray\u0131c\u0131 \u00f6nce \u00f6n bellekte olup olmad\u0131\u011f\u0131n\u0131 kontrol eder. Bu kontrol, milyonlarca sayfay\u0131 i\u00e7eren bir veri k\u00fcmesinde yap\u0131l\u0131r. Lineer arama gibi basit y\u00f6ntemler \u00e7ok yava\u015f olurdu. Bloom filtreleri, bu durumda \u00e7ok etkilidir. Taray\u0131c\u0131, ziyaret edilen her sayfa i\u00e7in bir hash hesaplar ve Bloom filtresindeki ilgili bitleri i\u015faretler. Bir sayfa yeniden ziyaret edildi\u011finde, taray\u0131c\u0131n\u0131n yapmas\u0131 gereken tek \u015fey, Bloom filtresini kontrol etmektir. E\u011fer ilgili bitler 1 ise, sayfa \u00f6n bellekte *olas\u0131l\u0131kla* bulunur ve do\u011frudan eri\u015filir. E\u011fer bitler 0 ise, sayfa \u00f6n bellekte bulunmaz. Yanl\u0131\u015f pozitif sonu\u00e7lar nadirdir ve bu durumda sadece bir disk okuma i\u015flemine yol a\u00e7ar; b\u00fcy\u00fck bir performans kayb\u0131 yaratmaz.<\/p>\n
Bloom filtrelerinin performans\u0131, bit dizisinin boyutu (m) ve kullan\u0131lan hash fonksiyonlar\u0131n\u0131n say\u0131s\u0131 (k) ile do\u011frudan ilgilidir. Daha b\u00fcy\u00fck bir bit dizisi, daha d\u00fc\u015f\u00fck yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131 anlam\u0131na gelir ancak daha fazla bellek t\u00fcketimi gerektirir. Benzer \u015fekilde, daha fazla hash fonksiyonu, daha d\u00fc\u015f\u00fck yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131 sa\u011flar ancak daha fazla i\u015flem s\u00fcresi gerektirir. Bu nedenle, m ve k de\u011ferlerinin optimal \u015fekilde se\u00e7ilmesi \u00f6nemlidir. Optimal de\u011ferler, beklenen \u00f6\u011fe say\u0131s\u0131 (n) ve kabul edilebilir yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131 (p) ile belirlenir. Farkl\u0131 m ve k kombinasyonlar\u0131n\u0131n kar\u015f\u0131la\u015ft\u0131r\u0131lmas\u0131 i\u00e7in performans testleri yap\u0131labilir. Genellikle, Bloom filtreleri, bir\u00e7ok avantaj sunar. \u00d6ncelikle, \u00e7ok h\u0131zl\u0131d\u0131rlar. \u00dcyelik kontrol\u00fc i\u015flemi, sabit zaman karma\u015f\u0131kl\u0131\u011f\u0131na sahiptir (O(k)), yani veri k\u00fcmesinin boyutu ne olursa olsun i\u015flem s\u00fcresi hemen hemen ayn\u0131 kal\u0131r. Ayr\u0131ca, bellek verimlidirler. Bir \u00f6\u011fenin saklanmas\u0131 i\u00e7in sadece birka\u00e7 bit gerekir. Bu \u00f6zellik, b\u00fcy\u00fck veri k\u00fcmeleri i\u00e7in olduk\u00e7a \u00f6nemlidir. Dezavantaj\u0131 ise olas\u0131l\u0131kl\u0131 do\u011fas\u0131d\u0131r. Yanl\u0131\u015f pozitifler olu\u015fabilir, ancak yanl\u0131\u015f negatifler olu\u015fmaz. Uygulama ba\u011flam\u0131na ba\u011fl\u0131 olarak, bu yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131 kabul edilebilir bir d\u00fczeyde tutulabilir. \u00d6rne\u011fin, bir spam filtresi i\u00e7in d\u00fc\u015f\u00fck bir yanl\u0131\u015f pozitif oran\u0131 kritik \u00f6nem ta\u015f\u0131rken, bir web taray\u0131c\u0131s\u0131 \u00f6n belle\u011fi i\u00e7in daha y\u00fcksek bir oran kabul edilebilir olabilir.<\/p>\n Bloom filtrelerinin performans\u0131n\u0131 optimize etmek i\u00e7in birka\u00e7 y\u00f6ntem kullan\u0131labilir. \u0130lk olarak, uygun hash fonksiyonlar\u0131n\u0131n se\u00e7imi olduk\u00e7a \u00f6nemlidir. H\u0131zl\u0131 ve e\u015fit da\u011f\u0131l\u0131ml\u0131 hash fonksiyonlar\u0131 tercih edilmelidir. \u0130kinci olarak, bit dizisinin boyutu ve hash fonksiyonu say\u0131s\u0131 dikkatlice se\u00e7ilmelidir. Yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131n\u0131 kabul edilebilir bir d\u00fczeye indirmek i\u00e7in, bu parametreler uygulamaya \u00f6zel olarak ayarlanmal\u0131d\u0131r. \u00dc\u00e7\u00fcnc\u00fc olarak, paralel i\u015flem yeteneklerinden yararlan\u0131labilir. Hash fonksiyonlar\u0131, \u00e7ok \u00e7ekirdekli i\u015flemcilerde paralel olarak \u00e7al\u0131\u015ft\u0131r\u0131labilir, b\u00f6ylece i\u015flem s\u00fcresi azalt\u0131labilir. D\u00f6rd\u00fcnc\u00fc olarak, baz\u0131 durumlarda, birden fazla Bloom filtresini kullanarak yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131n\u0131 daha da d\u00fc\u015f\u00fcrmek m\u00fcmk\u00fcnd\u00fcr. Her bir filtre farkl\u0131 bir hash fonksiyonu k\u00fcmesi kullanarak \u00e7al\u0131\u015f\u0131r ve sonu\u00e7lar\u0131n t\u00fcm filtreler taraf\u0131ndan do\u011frulanmas\u0131 gerekir. Bu y\u00f6ntem, yanl\u0131\u015f pozitif oran\u0131n\u0131 \u00f6nemli \u00f6l\u00e7\u00fcde azalt\u0131r, ancak bellek kullan\u0131m\u0131 artar. Son olarak, uygulaman\u0131n gereksinimlerine g\u00f6re \u00f6zelle\u015ftirilmi\u015f Bloom filtreleri tasarlanabilir. \u00d6rne\u011fin, s\u0131ral\u0131 veya hiyerar\u015fik Bloom filtreleri, \u00f6zel gereksinimlere g\u00f6re daha iyi performans sa\u011flayabilir. Daha fazla bilgi i\u00e7in (https:\/\/fatihsoysal.com) inceleyebilirsiniz.<\/p>\n Bloom filtrelerinin temel uygulamas\u0131n\u0131n \u00f6tesinde, daha geli\u015fmi\u015f varyasyonlar mevcuttur. K\u00fc\u00e7\u00fck Bloom filtreleri, bellek t\u00fcketimini daha da azaltmak i\u00e7in geli\u015ftirilmi\u015ftir. Bu filtreler, sabit boyutlu bir bit dizisi kullanmak yerine, dinamik olarak boyutlar\u0131n\u0131 ayarlayabilirler. \u00d6\u011feler eklendik\u00e7e veya silindik\u00e7e, bit dizisi gerekti\u011fi gibi b\u00fcy\u00fct\u00fcl\u00fcr veya k\u00fc\u00e7\u00fclt\u00fcl\u00fcr. Dinamik Bloom filtreleri, statik Bloom filtrelerine g\u00f6re daha esnektir ancak daha karma\u015f\u0131kt\u0131r. Ancak, de\u011fi\u015fen veri k\u00fcmesi b\u00fcy\u00fckl\u00fcklerine uyum sa\u011flamada daha avantajl\u0131d\u0131rlar. Bu y\u00f6ntemlerde, bellek y\u00f6netimi ve yeniden boyutland\u0131rma i\u015flemlerinin performans\u0131n\u0131 etkilememesi olduk\u00e7a \u00f6nemlidir. Bu konularda daha detayl\u0131 ara\u015ft\u0131rma yapmak, geli\u015fmi\u015f uygulamalar i\u00e7in \u00f6nemlidir.<\/p>\n Bloom filtreleri, b\u00fcy\u00fck veri k\u00fcmelerinde \u00fcyelik kontrol\u00fc i\u00e7in h\u0131zl\u0131 ve bellek verimli bir \u00e7\u00f6z\u00fcm sunar. Yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131n\u0131 kabul edilebilir bir d\u00fczeye indirmek i\u00e7in, bit dizisinin boyutu ve hash fonksiyonu say\u0131s\u0131 dikkatlice se\u00e7ilmelidir. Uygulamaya \u00f6zel optimizasyonlar, performans\u0131 daha da iyile\u015ftirebilir. Bloom filtreleri, bir\u00e7ok farkl\u0131 uygulamada, \u00f6zellikle b\u00fcy\u00fck veri analiti\u011fi ve a\u011f sistemleri gibi alanlarda, b\u00fcy\u00fck bir potansiyel sunmaktad\u0131r.<\/p>\n Yazar: Fatih Soysal<\/p>\n<\/pre>\n <\/code><\/p>\n","protected":false},"excerpt":{"rendered":"Bloom Filter'lar: H\u0131zl\u0131 ve Haf\u0131za Verimli \u00dcyelik Kontrol\u00fc Veri yap\u0131lar\u0131 d\u00fcnyas\u0131nda, b\u00fcy\u00fck veri k\u00fcmelerinde h\u0131zl\u0131 bir \u015fekilde \u00fcyelik…","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"csco_page_header_type":"","csco_page_load_nextpost":"","csco_page_subscribe_form":"","csco_page_contact_form":"","footnotes":""},"categories":[1],"tags":[],"class_list":{"0":"post-29139","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-genel","7":"cs-entry","8":"cs-video-wrap"},"yoast_head":"\nk = (m\/n) * ln(2)<\/code> form\u00fcl\u00fc kullanarak optimal k de\u011feri bulunabilir. Bu form\u00fcl, yanl\u0131\u015f pozitif olas\u0131l\u0131\u011f\u0131n\u0131 minimize etmek i\u00e7in kullan\u0131l\u0131r. Daha detayl\u0131 bilgi i\u00e7in ilgili akademik kaynaklar\u0131 inceleyebilirsiniz. Ayr\u0131ca, yanl\u0131\u015f pozitif oran\u0131n\u0131 d\u00fc\u015f\u00fcr\u00fcrken bellek t\u00fcketimini optimize etmek i\u00e7in farkl\u0131 hash fonksiyonlar\u0131 deneme ve performans kar\u015f\u0131la\u015ft\u0131rma \u00e7al\u0131\u015fmalar\u0131 yapabilirsiniz. Bu optimizasyonlar, uygulamaya \u00f6zel ince ayarlar gerektirir.<\/p>\nBloom Filtrelerinin Avantajlar\u0131 ve Dezavantajlar\u0131<\/h2>\n
Bloom Filtreleri Nas\u0131l Optimize Edilir?<\/h3>\n
\u0130leri D\u00fczey Konular: K\u00fc\u00e7\u00fck Bloom Filtreleri ve Dinamik Bloom Filtreleri<\/h2>\n
Sonu\u00e7<\/h2>\n
S\u0131k\u00e7a Sorulan Sorular<\/h3>\n
\n