ဒီတခေါက်မှာတော့ သိပ်မကြာသေးခင်ကမှ ဖတ်ထားတဲ့ Bloom filters ဆိုတဲ့ data structure ဘယ်လို အလုပ်လုပ်လဲ ဘယ်လိုနေရာတွေမှာ သုံးလေ့ရှိလဲဆိုတာ ပြောပြပါမယ်။

False Positive and False Negative

ဒီ data structure အကြောင်းမပြောခင်မှာ ပြောချင်တဲ့ တခုကတော့ “False Positive” နဲ့ “False Negative” အကြောင်းပါ။

ဥပမာ ကိုယ်က ရောဂါတခုခု (ဥပမာ Covid) ရှိမရှိ ဆေးစစ်ကြည့်တယ်ပဲ ဆိုပါတော့

• False Positive ဆိုတာ ဆေးစစ်လို့ ရလာတဲ့ result က ရောဂါတွေ့တယ်လို့ ပြောပေမယ့် ကိုယ့်မှာ တကယ်မရှိတာကို ပြောတာပါ။
• False Negative ကတော့ result က မရှိဘူး ပြောပေမယ့် ကိုယ့်မှာ ရှိနေတဲ့ အခြေအနေကို ပြောပါတယ်။

ဒီနှစ်ခု အကြောင်း တခြား example တွေနဲ့ ဒီ post မှာ ရှင်းပြထားပါတယ်။

Hashing

နောက်တခု ထပ်ပြောချင်တာတော့ hash function ပါ။ hashing လုပ်တယ်ဆိုတာ အကြမ်းဖျည်းအားဖြင့် item တခုခုထည့်လိုက်ရင် Maths formula တခုခုနဲ့ ဒီ item ရဲ့ identifier ကို ပြန်ပေးတဲ့ formula ပါ။ ဥပမာ "Maung Wa" ကို MD5 လို့ ခေါ်တဲ့ hash function နဲ့ hash လုပ်တယ်ဆိုရင် ca4bf781bee1949e054502c40b1f3deb လို့ အမြဲတမ်း ပြန်ပေးပါတယ်။

နောက်အရေးကြီးတဲ့အချက်တခုကတော့ Hash function တွေ one way ပဲ ရပါတယ်။ ca4bf781bee1949e054502c40b1f3deb ကို ယူပြီး "Maung Wa" လို့ ပြန်ရအောင် reverse လုပ်လို့မရပါဘူး။ အဲဒါအတွက်ကြောင့် လက်တွေ့မှာ hash function တွေကို နေရာအတော်များများမှာ သုံးပါတယ်။

E-commerce application တခုပဲဆိုပါတော့ အဲမှာ ကိုယ့်ရဲ့ app သုံးတဲ့သူတွေ login / sign up လုပ်တဲ့အခါမှာ password တွေကို အများအားဖြင့် plain text အနေနဲ့ မသိမ်းပဲနဲ့ password ကို bcrypt လို့ ‌ခေါ်တဲ့ password hash function နဲ့ လုပ်ပြီး ရလာတဲ့ string တွေကိုပဲ သိမ်းထားလေ့ ရှိပါတယ်။ အဲတော့ နောက်တခါ user က password ရိုက်ထည့်လိုက်တယ်ဆိုရင် password ကို hash လုပ် ပြီးရင် သိမ်းထားတဲ့ string နဲ့ တူမတူကို စစ်လိုက်ရုံနဲ့ password က မှန်လား မမှန်လားကို စစ်ကြည့်လို့ရပါတယ်။

အဲတော့ Bloom Filter ဆိုတာ ဘာလဲ

Bloom filter ဆိုတာ set တခုမှာ item တခု ရှိနေလားမရှိနေလားကို မြန်မြန်ဆန်ဆန်နဲ့ memory သိပ်မသုံးပဲ စစ်ပေးနိုင်ပါတယ်။ သူဘယ်လို အလုပ်လုပ်လဲ ကြည့်ကြည့်ရအောင်

အစဦးဆုံး item ၁၀ ခု ရှိတဲ့ bucket တခုနဲ့ hash function သုံးခု ရှိတယ်ပဲ ဆိုပါတော့

hash_1()
hash_2()
hash_3()

+---+---+---+---+---+---+---+---+---+----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+----+
|   |   |   |   |   |   |   |   |   |    |
+---+---+---+---+---+---+---+---+---+----+

ဒီ bucket ထဲကို Cat ဆိုတဲ့ string ကို hash function သုံးခုနဲ့ hashလုပ်ပြီး ထည့်ရင် 1, 3, 8 ရတယ်ပဲ ဆိုပါတော့

+---+---+---+---+---+---+---+---+---+----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+----+
| C |   | C |   | C |   |   |   |   |    |
+---+---+---+---+---+---+---+---+---+----+

နောက်တခါ Dog ဆိုတဲ့ string ကို hash လုပ်တယ်ဆိုရင် 4, 7, 8 ရတယ်ပဲ ထားပါတော့ အဲဒါကိုပဲ bucket ထဲမှာ ဖြည့်ကြည့်မယ်။

+---+---+---+---+---+---+---+---+---+----+
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
+---+---+---+---+---+---+---+---+---+----+
| C |   | C | D | C |   | D | D |   |    |
+---+---+---+---+---+---+---+---+---+----+

(C တို့ D တို့ဆိုတာ ဘယ်ဟာက ဘယ် နေရာမှာဆိုတာ မြင်သာအောင် ပြထားတာပါ။ တကယ့်လက်တွေ့မှာတော့ default ကို 0 ပဲ ထားပြီးတော့ ဖြည့်လိုက်တဲ့နေရာကို 1 လို့ပဲ သက်မှတ်လေ့ ရှိပါတယ်။)

အခုလက်ရှိအခြေအနေမှာ “Cat” ဆိုတာ ရှိလားမရှိလားဆိုတာကို စစ်ချင်တယ်ဆိုရင် “Cat” ကိုပဲ hash function သုံးခုနဲ့ hash လုပ်ပြီး ရလာတဲ့ result တွေဖြစ်တဲ့ 1, 3 နဲ့ 8 နေရာကို စစ်ကြည့်ပါတယ်။ အဲမှာ bucket ထဲက 1, 3 နဲ့ 8 နေရာမှာ value တခုခု ရှိနေတဲ့အတွက် ဒီ bucket ထဲမှာ Cat ရှိတယ်လို့ အသေအချာ ပြောနိုင်ပါတယ်။

ပြီးတော့ Mouse ဆိုတာ ရှိလားမရှိလားစစ်ကြည့်ရအောင်။ “Mouse” ဆို hash လုပ်တယ်ဆိုရင် 2, 5, 7 ရတယ်ပဲ ထားပါတော့။ bucket ထဲမှာ စစ်ကြည့်တဲ့အခါမှာ 2 ကတော့ ဘာမှ မရှိပေမယ့် 5 နဲံ 7 နေရာမှာ ပြည့်နေ့တာကို တွေ့နိုင်ပါတယ်။ တကယ်လို့သာ “Mouse” ဆိုတာ ရှိတယ်ဆိုရင် 2 နေရာမှာ တခုခု ရှိနေရမှာ ဖြစ်တယ်ဆိုတဲ့အတွက် ဒီ bucket ထဲမှာ “Mouse” မရှိဘူးလို့ ပြောနိုင်ပါတယ်။

အစမှာ ပြောခဲ့တဲ့ False Positive case တွေ ဘယ်လို ဖြစ်နိုင်လဲဆိုတာ ဆက်ကြည့်ရအောင်။

နောက်ဆုံးအနေနဲ့ “Elephant” ဆိုတာ ရှိလားမရှိလား စစ်ကြည့်ပါမယ်။ “Elephant” ကို hash လုပ်တယ်ဆိုရင် 4, 5, 7 ရတယ်ပဲ ထားပါတော့။ bucket ထဲမှာ စစ်ကြည့်တဲ့အခါမှာ 4, 5, 7 နေရာမှာ ပြည့်နေတာကို တွေ့နိုင်ပါတယ်။ အဲတော့ “Elephant” ဆိုတာ တကယ်မရှိပေမယ့်လဲ ရှိနေတယ်လို့ ပြန်ပြောနိုင်တဲ့ အခြေအနေတွေ ရှိပါတယ်။ ဒီလို ဖြစ်တဲ့အခြေအနေကို false positive ဖြစ်တယ်လို့ ခေါ်ပါတယ်။

ဒီဟာကို ကြည့်ချင်းအားဖြင့် Bloom filter ထဲမှာ ဘယ်ဟာတွေ ရှိနေလဲဆိုတာကို အတိအကျ ပြောရခက်ပါတယ်။ တဖက်က ကြည့်ရင်တော့ “Mouse” ဆိုတာကို စစ်တဲ့အခါမှ မရှိတာကို မရှိဘူး တန်းပြောနိုင်တဲ့အတွက် False Negative (မရှိတာကို ရှိတယ်ပြောတာ) case တွေကို သေချာပေါက် ပြောနိုင်ပါတယ်။

False Positive case တွေကို နည်းသွားစေချင်ရင်တော့ ကိုယ့်ရဲ့ bucket size ကို ကြီးကြီး လုပ်လို့ရပါတယ်။ space များလေလေ false positive rate နည်းသွားလေလေ ဖြစ်ပါတယ်။ Hash Function တွေကိုလည်း သုံးခုမက ပိုသုံးလို့လည်း ရပါတယ်။ သုံးတဲ့ function များလေလေ bucket ထဲကို ထည့်တာ နှေးလေလေတော့ ဖြစ်ပါလိမ့်မယ်။ နည်းတယ်ဆိုရင်လည်း false positive rate က များနိုင်ပါတယ်။ အဲတော့ ကိုယ်ရဲ့ use case ပေါ်မူတည်ပြီး adjust လုပ်ပေးရမှာပါ။

Algorithmic Complexity အနေနဲ့ ကြည့်တယ်ဆိုရင်တော့ ကိုယ်သုံးတဲ့ hash function အရေအတွက် k ပေါ်မူတည်ပြီး insert လုပ်တာပဲဖြစ်ဖြစ် အထဲမှာရှိတာ မရှိတာပဲဖြစ်ဖြစ် တွက်တဲ့ operation တွေက O(k) ဖြစ်နေမှာပါ။ Space အရကြည့်ရင်တော့ ကိုယ့်ရဲ့ false positive rate ကို မူတည်ပြီး ပြောရမှာဖြစ်တဲ့အတွက် အတိအကျ ပြောရခက်ပါတယ်။ ဒါပေမယ့် ပုံမှန် Hash table လို data structure မျိုနဲ့ ယှဥ်ကြည့်တယ်ဆိုရင်တော့ Bloom filter က ထည့်လိုက်တဲ့ item ကို မသိမ်းပဲနဲ့ hash ကိုပဲ သိမ်းတဲ့အတွက် space အရ ပိုပြီး efficient ဖြစ်ပါတယ်။

တကယ့်လက်တွေ့မှာအားဖြင့် သုံးလေ့ရှိတဲ့ နေရာတွေကတော့ username တခုက sign up လုပ်ပြီးလား မလုပ်ပြီးပြီလားဆိုတာ စစ်ချင်တယ်ဆိုရင် database ထဲမှာ သွားစစ်တာထက်စာရင် ရှိပြီးသား username တွေကို bloom filter ထဲထည့် ပြီးရင် အဲထဲကမှ ရှိမရှိကို စစ်ကြည့် ရှိတဲ့ဆိုရင်တော့ false positive မဖြစ်ရအောင် database ထဲမှာ သွားစစ်ကြည့်လို့ရပါတယ်။ မရှိဘူးဆိုရင်တော့ database ကိုတောင် သွားပြီး စစ်စရာမလိုတော့ပါဘူး။ sign up လုပ်တိုင်းမှာတော့ database ထဲကို ထည့်တဲ့အပြင် bloom filter ထဲကိုလည်း ထည့်ရပါလိမ့်မယ်။

နောက်ပိုင်း Redis မှာလည်း bloom filter အတွက် RedisBloom လို့ ခေါ်တဲ့ module ပါလာပါတယ်။

ဒီလောက်ဆိုရင်တော့ bloom filter အကြောင်းကို နည်းနည်း သိလောက်ပြီ ထင်ပါတယ်။

References :

1. Bloom filters
2. Bloom filters by example
3. What are Bloom filters