Bloom filter — elementning to‘plamda bo‘lishi mumkinligini xotira jihatidan tejamkor tekshiradigan ehtimollik ma’lumot tuzilmasidir. U “element aniq yo‘q” yoki “ehtimol bor” javobini beradi. To‘g‘ri qurilgan oddiy Bloom filter mavjud element uchun manfiy javob bermaydi, biroq mavjud bo‘lmagan elementni ba’zan mavjud deb ko‘rsatishi mumkin. Bunday holat false positive deb ataladi.
Tuzilishi va amallar
Filtr m bitdan iborat, dastlab nolga teng massiv va k ta xesh hisoblash usulidan tuziladi. Element qo‘shilganda xeshlar k ta bit pozitsiyasini aniqlaydi va shu bitlar birga o‘rnatiladi. Tekshirishda ayni pozitsiyalarning barchasi ko‘riladi. Ulardan bittasi nol bo‘lsa, element kiritilmagan. Barchasi bir bo‘lsa, element mavjud bo‘lishi mumkin, chunki bitlarni boshqa elementlar ham o‘rnatgan bo‘lishi ehtimoli bor.
Masalan, uch xeshli filtrda kalit uchun pozitsiyalar 7, 31 va 44 chiqsa, qo‘shish shu uch bitni yoqadi. Keyin boshqa kalit ayni uch pozitsiyaning bir qismini ishlatishi mumkin. Filtr kalitning qiymatini yoki o‘zini saqlamaydi; shu sababli ijobiy javobdan keyin asl indeks yoki faylda aniq tekshiruv baribir bajariladi.
Xato ehtimoli va o‘lcham
False positive ehtimoli bitlar soni, kiritilgan elementlar soni va xeshlar soniga bog‘liq. Keng tarqalgan yaqinlashuv quyidagicha:
p ≈ (1 - e^(-k n / m))^k
Bu yerda n — elementlar soni, m — bitlar soni, k — xeshlar soni. Belgilangan n va m uchun xeshlar sonini haddan tashqari oshirish foydali emas: ko‘proq protsessor sarflanadi va bitlar tezroq to‘ladi. Taxminiy optimal qiymat k ≈ (m/n) ln 2 atrofida bo‘ladi.
Filtr rejalashtirilgan sig‘imdan ancha ko‘p element qabul qilsa, birlarning ulushi oshib, ijobiy javoblarning katta qismi yolg‘on bo‘lib qoladi. Shuning uchun tizim kutilgan kalitlar soni va qabul qilinadigan xato ehtimoli asosida bit budjetini oldindan belgilaydi.
Saqlash tizimlaridagi qo‘llanishi
LSM asosidagi bazada bitta kalitni topish uchun bir nechta SSTable tekshirilishi mumkin. Har fayl uchun Bloom filter bo‘lsa, kalit aniq yo‘q bo‘lgan fayllarda qimmat disk qidiruvi o‘tkazilmaydi. False positive faqat ortiqcha fayl tekshiruviga olib keladi; noto‘g‘ri qiymat qaytarilmaydi, chunki yakuniy qaror SSTabledagi haqiqiy indeks va ma’lumot orqali beriladi.
Filtr blok, fayl yoki kalit prefiksi darajasida qurilishi mumkin. Nuqtaviy qidiruvda u ayniqsa samarali. Katta range scan esa ko‘plab kalitlarni ketma-ket o‘qigani uchun filtrdan kamroq foyda ko‘radi. Compaction yangi SSTable yaratganda uning filtrini ham qayta quradi.
Cheklovlar va variantlar
Oddiy Bloom filter elementni xavfsiz o‘chira olmaydi. Bitta bitni nolga qaytarish shu bitdan foydalangan boshqa elementlar uchun false negative yaratishi mumkin. Counting Bloom filter har pozitsiyada hisoblagich saqlab, o‘chirishni qo‘llaydi, ammo ko‘proq xotira talab qiladi. Scalable Bloom filter esa sig‘im oshganda yangi qatlamlar qo‘shadi.
Xeshlar bir tekis taqsimlanishi va filtr fayl bilan izchil versiyalanishi kerak. Buzilgan yoki boshqa kalit to‘plamiga tegishli filtrni ishlatish xavfli. Bundan tashqari, filtr maxfiylik yoki kirishni nazorat qilish vositasi emas: u a’zolik haqida taxminiy signal beradi va raqib tanlagan kalitlar bilan xesh to‘qnashuvlariga nisbatan alohida himoya talab qilishi mumkin.
Bog‘liq tushunchalar
Ehtimollik ma’lumot tuzilmasi, Xesh funksiya, False positive, SSTable, Log-Structured Merge-tree, Bit array, Cuckoo filter