CUCKOO vs BLOOM filtri, Gopher nuqtai nazaridan

Ushbu maqolada, men kuku filtrining gul filtri ustidan samaradorligini sinab ko'rishga harakat qilaman. (Chord DHT-dagi oldingi xabarni o'qing, Golangda taqsimlangan xesh jadvalini o'qing)

Kirish

Ehtimol ma'lumotlar tuzilmalari juda foydali, ayniqsa katta ma'lumotlar to'plamlarini qayta ishlashda. Ko'pincha narsalarning ma'lumotlar tomonida ishlayotganda, real vaqtda ma'lumotlarni qayta ishlash paytida "mavjud emas" yoki "allaqachon mavjud bo'lgan" so'rovini oddiy bajarishni istashadi. Agar so'rovlarga real vaqt rejimida javob berishni xohlasangiz, masalan, noyob ipslar soni, eng tez-tez uchraydigan ovozlar, agar reklama allaqachon foydalanuvchiga taqdim etilgan bo'lsa, ehtimol ma'lumotlarning tuzilmalaridan foydalanib, ushbu savollarga javob berish uchun bo'sh joyni taqdim eting. Bunday so'rovlarga odatiy yondoshish HashMap yoki HashTable-dan foydalanish yoki uni tashqi kesh (redis kabi) saqlash bo'lishi mumkin, ammo muammo katta ma'lumotlar to'plamida bo'lsa, ushbu oddiy ma'lumotlar tuzilmalari xotiraga sig'maydi. Bu erda ehtimoliy ma'lumotlar tuzilmalari makon va vaqtning afzalliklari tufayli paydo bo'ladi.

Misol foydalanish holatlari

  • Google Bigtable, Apache HBase va Apache Cassandra va Postgresql Bloom filtrlaridan foydalanib, mavjud bo'lmagan qatorlar yoki ustunlar uchun disklarni qidirishni qisqartiradilar. Diskning qimmatbaho ko'rinishini oldini olish ma'lumotlar bazasi so'rovining ishlashini sezilarli darajada oshiradi.
  • Medium foydalanuvchiga maqola allaqachon tavsiya etilganligini tekshirish uchun Bloom filtrlaridan foydalanadi
  • Ethereum Ethereum blockchain-da jurnallarni tezda topish uchun Bloom filtrlaridan foydalanadi
  • Google Chrome veb-brauzeri zararli URLlarni aniqlash uchun Bloom filtridan foydalangan. Har qanday URL avval mahalliy Bloom filtri bilan tekshirildi va agar Bloom filtri ijobiy natijani bergan bo'lsa, bajarilgan URL to'liq tekshirilishi kerak edi (va agar foydalanuvchi ijobiy natija bergan bo'lsa ham ogohlantirgan)

"Kaku" nima o'zi?

Biz ma'lumotlar platformasida bunday so'rovlarga javob berish uchun ko'p joylarda gul filtrlaridan foydalanganmiz. Yaqinda men ushbu qog'ozni Cuckoo filtrida ko'rib chiqdim, bu mening qiziqishimni uyg'otdi. Sarlavhaning o'zi shunday deydi: "Kuku filtri: gullashdan ko'ra yaxshiroq", shuning uchun men uni tekshirishga qaror qildim.

Kuku filtrlari gul filtrini yaxshilaydi, yo'q qilish, cheklangan hisoblash va chegaralangan soxta ijobiy ehtimollikni taklif etadi, shu bilan birga kosmik murakkablikni saqlaydi. Ular to'qnashuvlarni hal qilish uchun kuku xeshlaridan foydalanadilar va aslida ixcham kuku xesh jadvali hisoblanadi.

Kuku va gul filtrlari ikkalasi ham asl ma'lumotlarning hajmi katta bo'lganda testlarni o'tkazish uchun foydalidir. Ikkalasi ham bitta kirish uchun atigi 7 bitdan foydalanadilar. Ular, shuningdek, ma'lum bir a'zolik sinovidan oldin qimmat operatsiyani oldini olish mumkin bo'lgan hollarda foydalidir. Masalan, ma'lumotlar bazasiga murojaat qilishdan oldin, kerakli ob'ekt hatto ma'lumotlar bazasida mavjudligini tekshirish uchun o'rnatilgan a'zolik testini o'tkazish mumkin.

Algoritm

Filtr parametrlari:
1. Ikki hash funktsiyasi: h1 va h2
2. n paqirli B qatori. I-chi chelak B [i] deb nomlanadi

Kirish: L, kuku filtriga kiritilishi kerak bo'lgan elementlar ro'yxati.

Algoritm:
L bo'sh bo'lmasa ham:
    X ro'yxatdagi birinchi element bo'lsin. L ni x ro'yxatidan olib tashlang.
    Agar B [h1 (x)] bo'sh bo'lsa:
        x ni B ga joylashtiring [h1 (x)]
    Boshqa holda, agar B [h2 (x) bo'sh bo'lsa]:
        x ni B ga joylashtiring [h2 (x)]
    Boshqa:
        Y B nuqtada element bo'lsin (h2 (x)].
        Y ni L gacha oldinga suring
        x ni B ga joylashtiring [h2 (x)]

Amalga oshirish

Amalga oshirish juda sodda ko'rinadi, shuning uchun men uni ko'rib chiqishga qaror qildim va makon / vaqtni unumdor filtr bilan taqqoslashni taqqosladim. Cuckoo filtri qo'shilgan narsalarning "barmoq izlari" ni saqlaydigan Cuckoo xesh jadvalidan iborat. Elementning barmoq izi - bu elementning xeshidan olingan ozgina ip. Cuckoo hash jadvali bir nechta chelakdan iborat bo'lib, unda ikkita xash funktsiyasi asosida joylashtiriladigan element ikkita mumkin bo'lgan chelak bilan taqqoslanadi. Har bir chelak o'zgaruvchan miqdordagi barmoq izlarini saqlash uchun sozlanishi. Odatda Cuckoo filtri barmoq izlari va chelak o'lchamlari bilan aniqlanadi. Masalan, (2,4) Cuckoo filtri 2 bit uzunlikdagi barmoq izlarini saqlaydi va Cuckoo xesh jadvalidagi har bir chelakda 4 tagacha barmoq izlari saqlanishi mumkin.

Qo'shish

Algoritm:

f = barmoq izi (x);
i1 = hash (x);
i2 = i1 ⊕ xash (f);
agar chelak [i1] yoki [i2] chelak bo'sh bo'lsa
   bu chelakka f qo'shing;
   return Bajarildi;
// mavjud elementlarni boshqa joyga ko'chirish kerak;
i = tasodifiy i1 yoki i2 ni tanlang;
n = 0 uchun; n 
// Hashtable to'liq deb hisoblanadi;
qaytish muvaffaqiyatsizligi;

Kod:

Qidirmoq

Algoritm:

f = barmoq izi (x);
i1 = hash (x);
i2 = i1 ⊕ xash (f);
agar chelak [i1] yoki [i2] chelakda f bo'lsa
    return True;
return False;

Kod:

Yo'q qilish

Algoritm:

f = barmoq izi (x);
i1 = hash (x);
i2 = i1 ⊕ xash (f);
agar chelak [i1] yoki [i2] chelakda f bo'lsa
   ushbu chelakdan f nusxasini olib tashlang;
   return True;
return False;

Kod:

Ishlash sinovi

Bloom filtrida test o'tkazish uchun Uill Fitsjerald kutubxonasidan foydalanganman. Kuku filtri uchun olingan FPP (noto'g'ri ijobiy ehtimollik) nisbati 0,001 ni tashkil qiladi

Kosmik murakkablik

Kuku va gul filtrlariga kelsak, ular har xil soxta ijobiy ehtimolliklarda turlicha ishlaydi. Filtrning soxta ijobiy ehtimolligi 3% dan kam yoki teng bo'lsa, kuku filtri bitta kirish uchun kamroq bitga ega. U balandroq bo'lganda, gul filtrida har kirish uchun kamroq bit mavjud.

Vaqt murakkabligi

Kuku xeshida, elementni kiritish O (1) bilan eng yomon holatda ko'rinadi, chunki to'qnashuv paytida ko'plab holatlar bo'lishi mumkin, bu erda biz hozirgi qiymatga ega bo'lish uchun qiymatni olib tashlashimiz kerak. Bundan tashqari, agar tsikl bo'lsa, unda butun jadvalni qayta tiklash kerak.

Vaqtni tahlil qilish ikkala filtr quyidagi natijalarni beradi:

Ushbu tajriba davomida (kodimni yodda tutgan holda, to'liq optimallashtirilmasligi mumkin), Bloom filtrlari kosmik murakkablikda juda yaxshi ishlaydi va juda ko'p sonli elementlarga kam joy egallaydi. Kuku filtri ko'p sonli buyumlarni kiritishda yaxshiroq ishlayotganday tuyuladi, ammo ularni amalga oshirish tufayli qidirish (qidirish vaqtlari) biroz sekinlashadi.

Ilova

Men, albatta, qaysi filtrni tavsiya etadigan tomonini tanlamayman, deb o'ylayman, ikkalasida ham ularning foydalanish holatlari mavjud. Bloom filtrlari o'chirishni qo'llab-quvvatlamaydi, chunki hashing yo'qotiladi va qaytarib bo'lmaydi. Bug'langan filtrlarni hisoblash ushbu muammoni hal qilsa ham, Cuckoo filtrlari siz o'chirishni talab qiladigan holatlarda foydalidir. Albatta, Cuckoo filtrlari filtr to'liq bo'lganda xatolikka yo'l qo'yadi va bu o'zining afzalliklariga ega, Bloom filtrida esa sig'im ustidan nazorat mavjud emas, u mavjud bit massasini qayta tiklaydi.

Kod

Adabiyotlar

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

P.S Agar siz testlar / o'tkazishda biron bir noto'g'ri narsani topsangiz, iltimos o'z taklif va mulohazalaringizni qoldiring.