Bloom Filters — nədir?
Bu yazıda hamı tərəfindən çox bilinən və istifadə olunan Set, Map və s. kimi data strukturlarından daha fərqli bir strukturdan — Bloom Filters haqqında danışacam.
Bloom Filters — Hər hansısa bir elementlər bazasında konkret bir elementin olub olmadığını sizə deyən və “ehtimala əsaslanan” (probabilistic) data strukturudur.
Nəyə görə ehtimala əsaslanan? Çünki bloom filterdən hər hansısa sorğulanan məlumata görə geriyə yalnız “Hə” və ya “Yox” cavabı qayıda bilər, hansı ki, əgər yox cavabı qayıdırsa deməli həmin məlumatın bazada olmadığı dəqiqdir. Ancaq “Hə” cavabı qayıdırsa bu o deməkdir ki, məlumat bazada ola bilər/olmaya da bilər və bu zaman biz həmin məlumatı bazadan sorğulamalıyıq.
Daha dəqiq desək, bloom filterlər “false positive” cavablar verə bilər amma biz bu ehtimalın əvəzində var olmayan bir datanı boş yerə sorğulamamaqla zaman qazanmış oluruq.
İş prinsipi
Ümumi mənada bloom filterlər sadəcə 1 və 0-lardan ibarət olan, müəyyən ölçülü array-dir və ilkin halda arraydaki bütün elementlər 0 olur:
Daha sonra əlavə edəcəyimiz hər bir məlumatı 3 (və ya digər sayda) fərqli hash funksiyasından keçiririk:
hash1(“Foo”) => 1
hash2(“Foo”) => 5
hash3(“Foo”) => 7
və beləliklə “Foo” məlumatı arraydaki 1, 5 və 7-ci indeksləri 0-dan 1-ə dəyişir. Hər hansısa digər bir element əlavə etsək:
Bu gedişlə əsas bazadakı bütün məlumatları bloom filterdən keçiririk və nəticədə 1 və 0-lardan ibarət bir sturkturumuz yaranmış olur.
Oxuma əməliyyatında isə axtarılan məlumat yazma zamanı istifadə olunan hash funkasiyalardan bir daha keçirilir və alınan nəticələrin dəyərlərinin arrayda 1 və ya 0 olması yoxlanılır. Məsələn “Apple” sözünü axtarsaq:
Əgər axtarılan məlumata görə arraydakı elementlərdən ən azı biri 0 dəyəri qaytarırsa bu zaman bloom filter bizə “yox” cavabını qaytarır və biz əmin ola bilərik ki, “Apple” sözü əsas bazada yoxdur.
Maraqlısı isə odur ki, baxılan indekslərdəki bütün dəyərlər 1-dirsə deməli axtarılan məlumat bazada ola bilər.
Bəs nəyə görə “ola bilər”? Belə bir hala baxaq:
Tutaq ki, biz bu dəfə “Cat” sözünü axtarırıq və istifadə etdiyimiz hash funskiyalar aşağıdakı nəticəni verir:
hash1(“Cat”) => 1
hash2(“Cat”) => 4
hash3(“Cat”) => 5
“Cat” sözünün hash nəticələri (1,4,5) “Foo” (1,5,7) və “Bar” (3,4,8) sözlərinin nəticələri ilə üst-üstə düşdüyündən indiki halda da bütün indekslər üçün 1 dəyərini almış oluruq və buna görə də pozitiv cavab qaytarırıq, hansı ki, “Cat” sözü bazaya heç vaxt daxil edilməyib.
Bütün bu nümunələri əsas götürərək bloom filterlərin aşağıdakı kimi müsbət və mənfi cəhətlərini çıxara bilərik:
Müsbət:
- Var olmayan bir məlumata görə boş yerə sorğu göndərmiş olmuruq.
- Bloom filterlər bu axtarışı daha optimal yaddaşda və sabit zamanda yerinə yetirir.
Mənfi:
- Bloom filterlərdən məlumat silinməsi mümkün deyil.
- Bloom filterlərdən datanın özünü də oxumaq mümkün deyil.
- “false positive” ehtimalı heç vaxt sıfır olmur.
Fikir verdiksə bloom filterlər əslində hər yeni element əlavə olunduqca “false positive” qaytarmaq ehtimalını artıran bir data strukturudur. Buna görə də ilkin arrayın ölçüsü və hash funksiyaların sayı təxmin etidiyimiz elementlərin sayına uyğun seçilməlidir. Məsələn milyonluq data üçün biz 100 uzunluqlu array seçsək arrayın bütün elementləri təbii olaraq 1 olacaq və bütün sorğularımıza pozitiv cavab qayıdacaq ki, burda da bloom filter tədbiq etməyin heç bir mənası qalmır.
Tətbiq sahələri
Bir müddət öncə belə bir problemlə bağlı sual eşitmişdim, təsəvvür edin ki, çox böyük bir verilənlər bazasının önündə keş istifadə edirsiniz və bir çox sorğular zamanı axtarılan məlumat keşdə olmur, bu halda sorğu verilənlər bazasının özünə yönəldilir və məlumatı orda axtarmağa cəhd olunur və bu zaman həmin məlumat bazada da yoxdursa sorğu uzun müddət sadəcə boş cavab qaytarmaq üçün gözləyir, hansı ki, bu ssenari üçün bloom filters tətbiq etmək mümkün olan digər həll yollarından biri ola bilər.
Digər real tətbiq sahələri:
- https://www.linkedin.com/pulse/saving-unnecessary-network-calls-bloom-filter-wehkamp-tech-hub
- Təhlükəsizlik tədbirləri — Google bəd niyyətli (malicious) veb saytların, zəif şifrələrin axtarışı üçün istifadə edir.
- Verilənlər bazası — PostgreSQL, Cassandra və s. kimi verilənlər bazaları disk sorğulamalarının qarşısını almaq üçün bloom filterlər tətbiq edir.
Bonus
Aşağıdakı linkdə bloom filterlərin vizuallaşdırılmış forması ilə müəyyən testlər edə bilərsiniz:
