ການກັ່ນຕອງ CUCKOO vs BLOOM, ຈາກມຸມມອງຂອງ Gopher

ໃນບົດຂຽນນີ້, ຂ້າພະເຈົ້າ ກຳ ລັງພະຍາຍາມຈັດຕັ້ງປະຕິບັດແລະທົດສອບປະສິດທິພາບຂອງຕົວກອງ cuckoo ຫຼາຍກວ່າຕົວກອງດອກໄຟ. (ອ່ານບົດຂຽນກ່ອນ ໜ້າ ນີ້ກ່ຽວກັບ Chord DHT, ຈັດຕັ້ງປະຕິບັດຕາຕະລາງທີ່ແຈກຢາຍຢູ່ Golang)

ການແນະ ນຳ

ໂຄງສ້າງຂໍ້ມູນຄວາມເປັນໄປໄດ້ແມ່ນມີປະໂຫຍດຫຼາຍ, ໂດຍສະເພາະໃນເວລາທີ່ປະມວນຜົນຂໍ້ມູນຊຸດໃຫຍ່. ເວລາສ່ວນໃຫຍ່, ໃນຂະນະທີ່ເຮັດວຽກຢູ່ດ້ານຂໍ້ມູນຂອງສິ່ງຕ່າງໆ, ທ່ານຕ້ອງການເຮັດແບບງ່າຍໆ“ ແມ່ນລາຍການທີ່ບໍ່ມີຢູ່” ຫຼື“ ແມ່ນລາຍການທີ່ມີຢູ່ແລ້ວ” ໃນຂະນະທີ່ປະມວນຜົນຂໍ້ມູນໃນເວລາຈິງ. ບອກວ່າທ່ານຕ້ອງການຕອບແບບສອບຖາມໃນເວລາຈິງ, ຄືກັບ ຈຳ ນວນ ຈຳ ນວນທີ່ບໍ່ຊ້ ຳ ກັນ, ເລື້ອຍໆ, ຖ້າໂຄສະນາໄດ້ຮັບໃຊ້ ສຳ ລັບຜູ້ໃຊ້ແລ້ວ, ການ ນຳ ໃຊ້ໂຄງສ້າງຂໍ້ມູນຄວາມເປັນໄປໄດ້ສະ ໜອງ ວິທີການທີ່ມີປະສິດທິພາບໃນການຕອບ ຄຳ ຖາມເຫຼົ່ານີ້. ວິທີການແບບປົກກະຕິ ສຳ ລັບການສອບຖາມດັ່ງກ່າວແມ່ນການໃຊ້ HashMap ຫຼື HashTable, ຫຼືເກັບຮັກສາມັນເປັນຖານຂໍ້ມູນພາຍນອກບາງຢ່າງ (ເຊັ່ນວ່າ redis), ແຕ່ບັນຫາແມ່ນຢູ່ໃນຊຸດຂໍ້ມູນທີ່ໃຫຍ່, ໂຄງສ້າງຂໍ້ມູນງ່າຍໆເຫຼົ່ານີ້ບໍ່ສາມາດເຂົ້າກັບຄວາມ ຈຳ ໄດ້. ນີ້ແມ່ນບ່ອນທີ່ໂຄງສ້າງຂໍ້ມູນຄວາມເປັນໄປໄດ້ເນື່ອງມາຈາກຂໍ້ດີຂອງພື້ນທີ່ແລະເວລາ.

ກໍລະນີໃຊ້ຕົວຢ່າງ

  • Google Bigtable, Apache HBase ແລະ Apache Cassandra, ແລະ Postgresql ໃຊ້ຕົວກອງ Bloom ເພື່ອຫຼຸດຜ່ອນການຊອກຫາແຜ່ນ ສຳ ລັບແຖວຫລືຖັນທີ່ບໍ່ມີຢູ່. ການຫລີກລ້ຽງການຊອກຫາແຜ່ນທີ່ມີລາຄາຖືກຄວນຈະຊ່ວຍເພີ່ມປະສິດທິພາບຂອງການເຮັດວຽກຂອງການສອບຖາມຖານຂໍ້ມູນ.
  • ສື່ກາງໃຊ້ການກັ່ນຕອງ Bloom ເພື່ອກວດເບິ່ງວ່າບົດຂຽນໄດ້ຖືກແນະ ນຳ ໃຫ້ຜູ້ໃຊ້ແລ້ວ
  • Ethereum ໃຊ້ຕົວກອງ Bloom ສຳ ລັບການຊອກຫາບັນທຶກໃນ Ethereum blockchain ຢ່າງໄວວາ
  • ຕົວທ່ອງເວັບຂອງ Google Chrome ໃຊ້ໃນການໃຊ້ຕົວກອງ Bloom ເພື່ອລະບຸ URL ທີ່ເປັນອັນຕະລາຍ. URL ໃດໆຈະຖືກກວດສອບ ທຳ ອິດຕໍ່ກັບຕົວກອງ Bloom, ແລະຖ້າວ່າຕົວກອງ Bloom ສົ່ງຜົນໄດ້ຮັບໃນທາງບວກແມ່ນການກວດສອບ URL ທີ່ປະຕິບັດຢ່າງເຕັມທີ່ (ແລະຜູ້ໃຊ້ໄດ້ເຕືອນ, ຖ້າວ່າມັນຈະສົ່ງຜົນໄດ້ຮັບໃນທາງບວກ)

ມີຫຍັງຢູ່ໃນ "Cuckoo"?

ພວກເຮົາໄດ້ໃຊ້ຕົວກັ່ນຕອງດອກໄຟໃນຫຼາຍບ່ອນເພື່ອຕອບ ຄຳ ຖາມດັ່ງກ່າວໃນເວທີຂໍ້ມູນ. ເມື່ອບໍ່ດົນມານີ້ຂ້າພະເຈົ້າໄດ້ເຂົ້າເບິ່ງເອກະສານນີ້ກ່ຽວກັບຕົວກອງ Cuckoo ເຊິ່ງເຮັດໃຫ້ຂ້າພະເຈົ້າສົນໃຈ. ຫົວຂໍ້ຕົວມັນເອງເວົ້າວ່າ, "ກອງ Cuckoo: ປະຕິບັດໄດ້ດີກ່ວາດອກໄມ້", ສະນັ້ນຂ້ອຍໄດ້ຕັດສິນໃຈກວດເບິ່ງມັນ.

ຕົວກັ່ນຕອງ Cuckoo ປັບປຸງຕາມການອອກແບບຂອງຕົວກອງດອກໄມ້ໂດຍການສະ ເໜີ ລຶບ, ຈຳ ນວນ ຈຳ ກັດແລະຄວາມເປັນໄປໃນທາງບວກທີ່ບໍ່ຖືກຕ້ອງ, ໃນຂະນະທີ່ຍັງຮັກສາຄວາມສັບສົນໃນພື້ນທີ່ຄ້າຍຄືກັນ. ພວກເຂົາໃຊ້ຂີ້ເຫຍື່ອ cuckoo ເພື່ອແກ້ໄຂບັນຫາການປະທະກັນແລະເປັນສິ່ງ ຈຳ ເປັນຕາຕະລາງທີ່ມີຄວາມຫນາແຫນ້ນຂອງ cuckoo.

ຕົວກັ່ນຕອງ Cuckoo ແລະດອກໄມ້ທັງສອງແມ່ນມີປະໂຫຍດ ສຳ ລັບການທົດສອບສະມາຊິກເມື່ອມີຂະ ໜາດ ຂອງຂໍ້ມູນຕົ້ນສະບັບ. ພວກເຂົາທັງສອງໃຊ້ພຽງແຕ່ 7 ບິດຕໍ່ເຂົ້າ. ມັນຍັງເປັນປະໂຫຍດເມື່ອການປະຕິບັດງານທີ່ລາຄາແພງສາມາດຫລີກລ້ຽງໄດ້ກ່ອນການປະຕິບັດໂດຍການທົດສອບສະມາຊິກທີ່ ກຳ ນົດໄວ້. ຍົກຕົວຢ່າງ, ກ່ອນທີ່ຈະສອບຖາມຖານຂໍ້ມູນ, ການທົດສອບສະມາຊິກທີ່ ກຳ ນົດໄວ້ສາມາດເຮັດໄດ້ເພື່ອເບິ່ງວ່າວັດຖຸທີ່ຕ້ອງການແມ່ນຢູ່ໃນຖານຂໍ້ມູນ.

ສູດການຄິດໄລ່

ພາລາມິເຕີຂອງຕົວກອງ:
1. ຟັງຊັນສອງ Hash: h1 ແລະ h2
2. ຂບວນ B ທີ່ມີຖັງ n. ຖັງ i-th ຈະຖືກເອີ້ນວ່າ B [i]

ການປ້ອນຂໍ້ມູນ: L, ລາຍຊື່ຂອງອົງປະກອບທີ່ຈະຖືກໃສ່ເຂົ້າໃນຕົວກອງ cuckoo.

ສູດການຄິດໄລ່:
ໃນຂະນະທີ່ L ບໍ່ໄດ້ເປົ່າຫວ່າງ:
    ໃຫ້ x ເປັນສິ່ງ ທຳ ອິດໃນລາຍການ L. ເອົາ x ອອກຈາກລາຍຊື່.
    ຖ້າ B [h1 (x)] ຫວ່າງຢູ່:
        ສະຖານທີ່ x ໃນ B [h1 (x)]
    ອີກຢ່າງ ໜຶ່ງ, ຖ້າ B [h2 (x) ຫວ່າງເປົ່າ]:
        ສະຖານທີ່ x ໃນ B [h2 (x)]
    ອື່ນ:
        ໃຫ້ y ເປັນສ່ວນປະກອບໃນ B [h2 (x)].
        ຈ່າຍຄ່າ y ໃຫ້ L
        ສະຖານທີ່ x ໃນ B [h2 (x)]

ການຈັດຕັ້ງປະຕິບັດ

ການຈັດຕັ້ງປະຕິບັດເບິ່ງຄືວ່າກົງໄປກົງມາ, ສະນັ້ນຂ້າພະເຈົ້າໄດ້ຕັດສິນໃຈທີ່ຈະມີມັນແລະປຽບທຽບວ່າພື້ນທີ່ / ເວລາມີປະສິດທິພາບແນວໃດຖ້າທຽບໃສ່ຕົວກອງດອກໄຟ. ຕົວກອງ Cuckoo ປະກອບດ້ວຍໂຕະ Cuckoo hash ທີ່ເກັບຮັກສາ 'ລາຍນິ້ວມື' ຂອງລາຍການທີ່ຖືກໃສ່ລົງ. ນີ້ວມືຂອງລາຍການແມ່ນສະຕິງເລັກນ້ອຍທີ່ມາຈາກຈຸດຂອງລາຍການນັ້ນ. ຕາຕະລາງ hash cuckoo ປະກອບດ້ວຍຖັງບັນຈຸບ່ອນທີ່ລາຍການທີ່ຕ້ອງໃສ່ແມ່ນຖືກວາງໃສ່ສອງຖັງທີ່ເປັນໄປໄດ້ໂດຍອີງໃສ່ສອງ ໜ້າ ທີ່ hash. ແຕ່ລະຖັງສາມາດໄດ້ຮັບການຕັ້ງຄ່າເພື່ອເກັບ ຈຳ ນວນລາຍນິ້ວມື. ໂດຍປົກກະຕິ, ຕົວກອງ Cuckoo ແມ່ນຖືກລະບຸໂດຍຂະ ໜາດ ນິ້ວມືແລະຄຸຂອງມັນ. ຍົກຕົວຢ່າງ, ເຄື່ອງກັ່ນຕອງ Cuckoo (2,4) ເກັບຮັກສາລາຍນິ້ວມືທີ່ມີຄວາມຍາວ 2 ບິດແລະແຕ່ລະຖັງໃນຕາຕະລາງ Cuckoo hash ສາມາດເກັບລາຍນິ້ວມືໄດ້ເຖິງ 4.

ແຊກ

ສູດການຄິດໄລ່:

f = ນີ້ວມື (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
ຖ້າຖັງ [i1] ຫລືຖັງ [i2] ມີສິ່ງທີ່ຂາເຂົ້າເປົ່າແລ້ວ
   ຕື່ມ f ໃສ່ຖັງນັ້ນ;
   return Done;
// ຕ້ອງຍົກຍ້າຍສິ່ງຂອງທີ່ມີຢູ່ແລ້ວ;
i = ເລືອກເອົາແບບ i1 ຫລື i2 ໂດຍບັງເອີນ;
ສຳ ລັບ n = 0; n 
// Hashtable ແມ່ນຖືວ່າເຕັມ;
ກັບຄືນຄວາມລົ້ມເຫຼວ;

ລະຫັດ:

ຄົ້ນຫາ

ສູດການຄິດໄລ່:

f = ນີ້ວມື (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
ຖ້າຖັງ [i1] ຫລືຖັງ [i2] ມີ f ແລ້ວ
    return True;
return ບໍ່ຖືກຕ້ອງ;

ລະຫັດ:

ລົບ

ສູດການຄິດໄລ່:

f = ນີ້ວມື (x);
i1 = hash (x);
i2 = i1 ⊕ hash (f);
ຖ້າຖັງ [i1] ຫລືຖັງ [i2] ມີ f ແລ້ວ
   ເອົາ ສຳ ເນົາ f ຈາກຖັງນີ້ອອກ;
   return True;
return ບໍ່ຖືກຕ້ອງ;

ລະຫັດ:

ການທົດສອບການປະຕິບັດ

ຂ້ອຍໄດ້ໃຊ້ຫ້ອງສະ ໝຸດ Will Fitzgerald ສຳ ລັບການທົດສອບໃນຕົວກັ່ນຕອງດອກໄມ້. ອັດຕາສ່ວນຂອງ FPP (False Positive Probability) ທີ່ຖືກປະຕິບັດ ສຳ ລັບຕົວກອງ cuckoo ແມ່ນ 0,001

ຄວາມສັບສົນໃນອະວະກາດ

ກ່ຽວກັບການກັ່ນຕອງ cuckoo ແລະເບີກບານ, ພວກເຂົາປະຕິບັດທີ່ແຕກຕ່າງກັນໃນຄວາມເປັນໄປໄດ້ໃນທາງບວກທີ່ບໍ່ຖືກຕ້ອງ. ໃນເວລາທີ່ຄວາມເປັນໄປໄດ້ໃນທາງບວກທີ່ບໍ່ຖືກຕ້ອງຂອງຕົວກອງແມ່ນຫນ້ອຍກ່ວາຫຼືເທົ່າກັບ 3%, ຕົວກອງ cuckoo ມີສ່ວນ ໜ້ອຍ ໃນແຕ່ລະຄັ້ງ. ໃນເວລາທີ່ມັນສູງຂຶ້ນ, ຕົວກອງດອກໄມ້ມີສອງສ່ວນຫນ້ອຍຕໍ່ການເຂົ້າ.

ຄວາມສັບສົນເວລາ

ໃນ cuckoo hashing, ການໃສ່ອົງປະກອບເບິ່ງຄືວ່າຮ້າຍແຮງກວ່າ O (1) ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດເພາະວ່າມັນອາດຈະມີຫຼາຍໆກໍລະນີໃນລະຫວ່າງການປະທະກັນ, ບ່ອນທີ່ພວກເຮົາຕ້ອງໄດ້ເອົາຄ່າອອກມາເພື່ອເຮັດໃຫ້ຫ້ອງມີຄ່າໃນປະຈຸບັນ. ຍິ່ງໄປກວ່ານັ້ນ, ຖ້າມີວົງຈອນແລ້ວຕາຕະລາງທັງ ໝົດ ຕ້ອງໄດ້ຖືກປັບປຸງ ໃໝ່.

ເຮັດການວິເຄາະເວລາຂອງທັງສອງຕົວກອງໃຫ້ຜົນໄດ້ຮັບຕໍ່ໄປນີ້:

ຕະຫຼອດການທົດລອງນີ້ (ຈື່ລະຫັດຂອງຂ້ອຍອາດຈະບໍ່ໄດ້ຮັບການເພີ່ມປະສິດຕິພາບຢ່າງເຕັມທີ່), ຕົວກອງດອກໄມ້ເບິ່ງຄືວ່າຈະປະຕິບັດໄດ້ດີໃນສະລັບສັບຊ້ອນໃນອະວະກາດ, ຍຶດເອົາພື້ນທີ່ ໜ້ອຍ ລົງ ສຳ ລັບສິນຄ້າທີ່ມີ ຈຳ ນວນຫລາຍ. ການກັ່ນຕອງ Cuckoo ເບິ່ງຄືວ່າຈະປະຕິບັດໄດ້ດີກວ່າໃນການແຊກຂອງບັນດາລາຍການທີ່ມີ ຈຳ ນວນຫຼາຍ, ແຕ່ການຊອກຫາທີ່ຊ້າລົງ (ເວລາຄົ້ນຫາ) ຍ້ອນການປະຕິບັດມັນ.

ຄວາມເຂົ້າໃຈ

ຂ້າພະເຈົ້າຈະບໍ່ເວົ້າເຖິງຕົວກອງໃດທີ່ຈະແນະ ນຳ, ຂ້າພະເຈົ້າຄິດວ່າພວກເຂົາທັງສອງມີຄະດີການ ນຳ ໃຊ້ຂອງພວກເຂົາເອງ. ການກັ່ນຕອງດອກໄມ້ບໍ່ຮອງຮັບການລຶບເພາະວ່າ hashing ແມ່ນການສູນເສຍແລະບໍ່ປ່ຽນແປງໄດ້. ເຖິງແມ່ນວ່າການນັບການກັ່ນຕອງດອກໄມ້ສາມາດແກ້ໄຂບັນຫາດັ່ງກ່າວໄດ້, ຕົວກອງ Cuckoo ແມ່ນເປັນປະໂຫຍດໃນກໍລະນີທີ່ທ່ານຈະຕ້ອງການລຶບ. ແນ່ນອນການກັ່ນຕອງ Cuckoo ໃຫ້ຂໍ້ຜິດພາດເມື່ອການກັ່ນຕອງເຕັມແລະມັນມີຂໍ້ດີຂອງມັນເອງ, ໃນຂະນະທີ່ຕົວກັ່ນຕອງດອກເບິ້ນ, ບໍ່ມີການຄວບຄຸມຄວາມສາມາດ, ມັນພຽງແຕ່ປ່ຽນ ໃໝ່ ກັບຂີດທີ່ມີຢູ່ແລ້ວ.

ລະຫັດ

ເອກະສານອ້າງອີງ

  • 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 ຖ້າທ່ານພົບເຫັນສິ່ງທີ່ບໍ່ຖືກຕ້ອງກັບການທົດສອບ / ການຈັດຕັ້ງປະຕິບັດ, ກະລຸນາອອກຈາກ ຄຳ ແນະ ນຳ / ຄຳ ເຫັນຂອງທ່ານ.