TL;DR: ສີ່ປີກ່ອນຫນ້ານີ້ຂ້າພະເຈົ້າໄດ້ອອກຈາກ Google ດ້ວຍຄວາມຄິດສໍາລັບເຄື່ອງມືກວດສອບເຄື່ອງແມ່ຂ່າຍໃຫມ່. ແນວຄວາມຄິດນີ້ແມ່ນເພື່ອສົມທົບການທໍາງານທີ່ໂດດດ່ຽວໂດຍປົກກະຕິເຂົ້າໄປໃນການບໍລິການຫນຶ່ງ ການເກັບກໍາ ແລະ​ການ​ວິ​ເຄາະ​ບັນ​ທຶກ​ການ​ເກັບ​ກໍາ​ຕົວ​ຊີ້​ວັດ​, ແຈ້ງເຕືອນ ແລະ dashboards. ຫນຶ່ງໃນຫຼັກການແມ່ນວ່າການບໍລິການຕ້ອງມີຢ່າງແທ້ຈິງ ໄວ, ສະຫນອງ devops ກັບປະສົບການທີ່ງ່າຍ, ມີການໂຕ້ຕອບ, ມີຄວາມສຸກ. ອັນນີ້ຮຽກຮ້ອງໃຫ້ມີການປະມວນຜົນຊຸດຂໍ້ມູນຫຼາຍກິກາໄບເປັນແຕ່ສ່ວນໜຶ່ງຂອງວິນາທີໃນຂະນະທີ່ຢູ່ໃນງົບປະມານ. ເຄື່ອງມືການຈັດການບັນທຶກທີ່ມີຢູ່ແລ້ວແມ່ນມັກຈະຊ້າແລະ clunky, ດັ່ງນັ້ນພວກເຮົາໄດ້ປະເຊີນກັບສິ່ງທ້າທາຍທີ່ດີ: smartly ການອອກແບບເຄື່ອງມືເພື່ອໃຫ້ຜູ້ໃຊ້ປະສົບການໃຫມ່.

ບົດຄວາມນີ້ອະທິບາຍວິທີທີ່ພວກເຮົາຢູ່ Scalyr ແກ້ໄຂບັນຫານີ້ໂດຍການນໍາໃຊ້ວິທີການໂຮງຮຽນເກົ່າ, ວິທີການບັງຄັບໃຊ້ brute, ກໍາຈັດຊັ້ນທີ່ບໍ່ຈໍາເປັນແລະຫຼີກເວັ້ນໂຄງສ້າງຂໍ້ມູນທີ່ສັບສົນ. ທ່ານສາມາດນໍາໃຊ້ບົດຮຽນເຫຼົ່ານີ້ກັບບັນຫາວິສະວະກໍາຂອງທ່ານເອງ.

ໂຮງຮຽນເກົ່າ

ການວິເຄາະບັນທຶກມັກຈະເລີ່ມຕົ້ນດ້ວຍການຄົ້ນຫາ: ຊອກຫາຂໍ້ຄວາມທັງຫມົດທີ່ກົງກັບຮູບແບບທີ່ແນ່ນອນ. ໃນ Scalyr, ເຫຼົ່ານີ້ແມ່ນສິບຫຼືຫຼາຍຮ້ອຍ gigabytes ຂອງບັນທຶກຈາກເຄື່ອງແມ່ຂ່າຍຈໍານວນຫຼາຍ. ວິທີການທີ່ທັນສະໄຫມ, ຕາມກົດລະບຽບ, ກ່ຽວຂ້ອງກັບການກໍ່ສ້າງໂຄງສ້າງຂໍ້ມູນທີ່ສັບສົນບາງຢ່າງທີ່ເຫມາະສໍາລັບການຄົ້ນຫາ. ຂ້າພະເຈົ້າແນ່ນອນເຫັນອັນນີ້ຢູ່ໃນ Google, ບ່ອນທີ່ພວກເຂົາດີຢູ່ໃນປະເພດນີ້. ແຕ່ພວກເຮົາໄດ້ຕົກລົງໃນວິທີການ cruder ຫຼາຍ: ການສະແກນເສັ້ນຊື່ຂອງບັນທຶກ. ແລະມັນເຮັດວຽກ - ພວກເຮົາສະຫນອງການໂຕ້ຕອບທີ່ສາມາດຄົ້ນຫາໄດ້ທີ່ຄໍາສັ່ງຂອງຂະຫນາດໄວກວ່າຄູ່ແຂ່ງຂອງພວກເຮົາ (ເບິ່ງພາບເຄື່ອນໄຫວໃນຕອນທ້າຍ).

ຄວາມເຂົ້າໃຈທີ່ສໍາຄັນແມ່ນວ່າໂປເຊດເຊີທີ່ທັນສະໄຫມແມ່ນໄວຫຼາຍໃນການດໍາເນີນງານງ່າຍດາຍ, ກົງໄປກົງມາ. ອັນນີ້ເປັນເລື່ອງງ່າຍທີ່ຈະພາດໃນລະບົບຫຼາຍຊັ້ນທີ່ຊັບຊ້ອນທີ່ອີງໃສ່ຄວາມໄວ I/O ແລະການເຮັດວຽກຂອງເຄືອຂ່າຍ, ແລະລະບົບດັ່ງກ່າວມີທົ່ວໄປຫຼາຍໃນທຸກມື້ນີ້. ດັ່ງນັ້ນພວກເຮົາໄດ້ພັດທະນາການອອກແບບທີ່ຫຼຸດຜ່ອນຊັ້ນແລະສິ່ງເສດເຫຼືອເກີນ. ດ້ວຍໂປເຊດເຊີແລະເຊີບເວີຫຼາຍຕົວຂະຫນານ, ຄວາມໄວໃນການຄົ້ນຫາໄດ້ເຖິງ 1 TB ຕໍ່ວິນາທີ.

ເອົາ​ໃຈ​ໃສ່​ທີ່​ສໍາ​ຄັນ​ຈາກ​ບົດ​ຄວາມ​ນີ້​:

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

(ບົດຄວາມນີ້ອະທິບາຍການຊອກຫາຂໍ້ມູນໃນຫນ່ວຍຄວາມຈໍາ. ໃນກໍລະນີຫຼາຍທີ່ສຸດ, ເມື່ອຜູ້ໃຊ້ດໍາເນີນການຄົ້ນຫາບັນທຶກ, ເຊີບເວີ Scalyr ໄດ້ cache ມັນແລ້ວ. ບົດຄວາມຕໍ່ໄປຈະປຶກສາຫາລືກ່ຽວກັບການຊອກຫາບັນທຶກທີ່ບໍ່ໄດ້ເກັບໄວ້. ຫຼັກການດຽວກັນນໍາໃຊ້: ລະຫັດປະສິດທິພາບ, brute force. ກັບຊັບພະຍາກອນຄອມພິວເຕີຂະຫນາດໃຫຍ່).

ວິທີການບັງຄັບ Brute

ຕາມປະເພນີ, ຊຸດຂໍ້ມູນຂະຫນາດໃຫຍ່ຖືກຄົ້ນຫາໂດຍໃຊ້ດັດສະນີຄໍາສໍາຄັນ. ເມື່ອນໍາໃຊ້ກັບບັນທຶກຂອງເຊີຟເວີ, ນີ້ຫມາຍເຖິງການຊອກຫາທຸກໆຄໍາທີ່ເປັນເອກະລັກໃນບັນທຶກ. ສໍາລັບແຕ່ລະຄໍາ, ທ່ານຈໍາເປັນຕ້ອງເຮັດບັນຊີລາຍຊື່ຂອງການລວມທັງຫມົດ. ນີ້ເຮັດໃຫ້ມັນງ່າຍຕໍ່ການຊອກຫາຂໍ້ຄວາມທັງຫມົດທີ່ມີຄໍານີ້, ຕົວຢ່າງ 'error', 'firefox' ຫຼື "transaction_16851951" - ພຽງແຕ່ເບິ່ງຢູ່ໃນດັດຊະນີ.

ຂ້ອຍໃຊ້ວິທີການນີ້ຢູ່ Google ແລະມັນເຮັດວຽກໄດ້ດີ. ແຕ່ໃນ Scalyr ພວກເຮົາຄົ້ນຫາບັນທຶກ byte byte.

ເປັນຫຍັງ? ຈາກມຸມເບິ່ງ algorithmic abstract, ດັດສະນີຄໍາຫລັກແມ່ນມີປະສິດທິພາບຫຼາຍກ່ວາການຊອກຫາແບບບັງຄັບ. ຢ່າງໃດກໍຕາມ, ພວກເຮົາບໍ່ຂາຍ algorithms, ພວກເຮົາຂາຍປະສິດທິພາບ. ແລະການປະຕິບັດແມ່ນບໍ່ພຽງແຕ່ກ່ຽວກັບ algorithms, ແຕ່ຍັງກ່ຽວກັບວິສະວະກໍາລະບົບ. ພວກເຮົາຕ້ອງພິຈາລະນາທຸກຢ່າງ: ປະລິມານຂໍ້ມູນ, ປະເພດຂອງການຄົ້ນຫາ, ຮາດແວແລະຊອບແວທີ່ມີຢູ່. ພວກເຮົາໄດ້ຕັດສິນໃຈວ່າສໍາລັບບັນຫາສະເພາະຂອງພວກເຮົາ, ບາງສິ່ງບາງຢ່າງເຊັ່ນ 'grep' ແມ່ນເຫມາະສົມດີກ່ວາດັດສະນີ.

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

ຄວາມຫຍຸ້ງຍາກທີ່ແທ້ຈິງມາໃນເວລາທີ່ທ່ານບໍ່ໄດ້ຊອກຫາຄໍາສັບຕ່າງໆ. ໃຫ້ເວົ້າວ່າທ່ານຕ້ອງການເບິ່ງວ່າການຈະລາຈອນມາຈາກ bots ຫຼາຍເທົ່າໃດ. ຄວາມຄິດທໍາອິດແມ່ນການຄົ້ນຫາບັນທຶກສໍາລັບຄໍາວ່າ 'bot'. ນີ້ແມ່ນວິທີທີ່ເຈົ້າຈະພົບເຫັນບາງ bots: Googlebot, Bingbot ແລະອື່ນໆຈໍານວນຫຼາຍ. ແຕ່ໃນທີ່ນີ້ 'bot' ບໍ່ແມ່ນຄໍາສັບ, ແຕ່ເປັນສ່ວນຫນຶ່ງຂອງມັນ. ຖ້າພວກເຮົາຄົ້ນຫາ 'bot' ໃນດັດຊະນີ, ພວກເຮົາຈະບໍ່ພົບຂໍ້ຄວາມໃດໆທີ່ມີຄໍາວ່າ 'Googlebot'. ຖ້າທ່ານກວດເບິ່ງທຸກໆຄໍາໃນດັດສະນີແລະຫຼັງຈາກນັ້ນສະແກນດັດສະນີສໍາລັບຄໍາທີ່ພົບເຫັນ, ການຄົ້ນຫາຈະຊ້າລົງຢ່າງຫຼວງຫຼາຍ. ດັ່ງນັ້ນ, ບາງໂປຼແກຼມບັນທຶກບໍ່ອະນຸຍາດໃຫ້ຄົ້ນຫາຄໍາບາງສ່ວນຫຼື (ດີທີ່ສຸດ) ອະນຸຍາດໃຫ້ syntax ພິເສດທີ່ມີການປະຕິບັດຕ່ໍາ. ພວກເຮົາຕ້ອງການທີ່ຈະຫຼີກເວັ້ນການນີ້.

ບັນຫາອື່ນແມ່ນເຄື່ອງໝາຍວັກຕອນ. ທ່ານຕ້ອງການຊອກຫາຄໍາຮ້ອງຂໍທັງຫມົດຈາກ 50.168.29.7? ຈະເປັນແນວໃດກ່ຽວກັບການ debugging ບັນທຶກທີ່ມີ [error]? ຕົວໜັງສືຍ່ອຍມັກຈະຂ້າມເຄື່ອງໝາຍວັກຕອນ.

ສຸດທ້າຍ, ວິສະວະກອນມັກເຄື່ອງມືທີ່ມີປະສິດທິພາບ, ແລະບາງຄັ້ງບັນຫາສາມາດແກ້ໄຂໄດ້ດ້ວຍການສະແດງອອກເປັນປົກກະຕິ. ດັດຊະນີຄໍາຫລັກບໍ່ເຫມາະສົມຫຼາຍສໍາລັບການນີ້.

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

ດັດສະນີຄໍາສໍາຄັນຍັງໃຊ້ພື້ນທີ່ຫຼາຍ, ແລະການເກັບຮັກສາເປັນຄ່າໃຊ້ຈ່າຍທີ່ສໍາຄັນໃນລະບົບການຄຸ້ມຄອງບັນທຶກ.

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

Brute force ເຮັດວຽກຖ້າທ່ານມີບັນຫາ brute (ແລະແຮງຫຼາຍ)

Brute force ເຮັດວຽກທີ່ດີທີ່ສຸດກ່ຽວກັບບັນຫາງ່າຍດາຍທີ່ມີ loops ພາຍໃນຂະຫນາດນ້ອຍ. ເລື້ອຍໆທ່ານສາມາດປັບປຸງ loop ພາຍໃນເພື່ອແລ່ນດ້ວຍຄວາມໄວສູງຫຼາຍ. ຖ້າລະຫັດສັບສົນ, ມັນຍາກທີ່ຈະເພີ່ມປະສິດທິພາບມັນ.

ລະຫັດຄົ້ນຫາຂອງພວກເຮົາໃນເບື້ອງຕົ້ນມີ loop ພາຍໃນຂະຫນາດໃຫຍ່ພໍສົມຄວນ. ພວກເຮົາເກັບຮັກສາຂໍ້ຄວາມໃນຫນ້າເວັບຕ່າງໆຢູ່ທີ່ 4K; ແຕ່ລະຫນ້າມີບາງຂໍ້ຄວາມ (ໃນ UTF-8) ແລະ metadata ສໍາລັບແຕ່ລະຂໍ້ຄວາມ. Metadata ແມ່ນໂຄງສ້າງທີ່ເຂົ້າລະຫັດຄວາມຍາວຂອງຄ່າ, ID ຂໍ້ຄວາມພາຍໃນ, ແລະຊ່ອງຂໍ້ມູນອື່ນໆ. ວົງ​ຈອນ​ການ​ຊອກ​ຫາ​ເບິ່ງ​ຄື​ນີ້​:

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

(ທ່ານອາດຈະຖາມວ່າເປັນຫຍັງພວກເຮົາເກັບຮັກສາຂໍ້ຄວາມໃນຮູບແບບນີ້ດ້ວຍຫນ້າ 4K, ຂໍ້ຄວາມແລະ metadata, ແທນທີ່ຈະເຮັດວຽກກັບບັນທຶກໂດຍກົງ. ມີຫຼາຍເຫດຜົນ, ເຊິ່ງເຮັດໃຫ້ຄວາມຈິງທີ່ວ່າພາຍໃນເຄື່ອງຈັກ Scalyr ແມ່ນຄ້າຍຄືຖານຂໍ້ມູນທີ່ແຈກຢາຍຫຼາຍກ່ວາ. ລະບົບໄຟລ໌. ການຄົ້ນຫາຂໍ້ຄວາມມັກຈະຖືກລວມເຂົ້າກັບຕົວກອງແບບ DBMS ຢູ່ໃນຂອບຫຼັງຈາກການວິເຄາະບັນທຶກ. ພວກເຮົາສາມາດຄົ້ນຫາບັນທຶກໄດ້ຫຼາຍພັນເທື່ອໃນເວລາດຽວກັນ, ແລະໄຟລ໌ຂໍ້ຄວາມທີ່ງ່າຍດາຍແມ່ນບໍ່ເຫມາະສົມສໍາລັບການເຮັດທຸລະກໍາ, ສໍາເນົາ, ການຈັດການຂໍ້ມູນແຈກຢາຍຂອງພວກເຮົາ).

ໃນເບື້ອງຕົ້ນ, ມັນເບິ່ງຄືວ່າລະຫັດດັ່ງກ່າວບໍ່ເຫມາະສົມຫຼາຍສໍາລັບການເພີ່ມປະສິດທິພາບຂອງ brute force. "ການເຮັດວຽກທີ່ແທ້ຈິງ" ໃນ String.indexOf() ບໍ່ໄດ້ຄອບງໍາໂປຣໄຟລ໌ CPU. ນັ້ນແມ່ນ, ການເພີ່ມປະສິດທິພາບວິທີການນີ້ຢ່າງດຽວຈະບໍ່ນໍາເອົາຜົນກະທົບທີ່ສໍາຄັນ.

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

ສະບັບນີ້ເຮັດວຽກໂດຍກົງໃນມຸມເບິ່ງ raw byte[] ແລະຊອກຫາຂໍ້ຄວາມທັງໝົດໃນເວລາດຽວກັນໃນທົ່ວໜ້າ 4K.

ນີ້ແມ່ນງ່າຍຂຶ້ນຫຼາຍທີ່ຈະເພີ່ມປະສິດທິພາບສໍາລັບວິທີການບັງຄັບ brute. loop ຄົ້ນຫາພາຍໃນແມ່ນເອີ້ນວ່າພ້ອມໆກັນສໍາລັບຫນ້າ 4K ທັງຫມົດ, ແທນທີ່ຈະແຍກຕ່າງຫາກໃນແຕ່ລະໂພດ. ບໍ່ມີການຄັດລອກຂໍ້ມູນ, ບໍ່ມີການຈັດສັນວັດຖຸ. ແລະການດໍາເນີນການ metadata ສະລັບສັບຊ້ອນຫຼາຍແມ່ນເອີ້ນວ່າພຽງແຕ່ໃນເວລາທີ່ຜົນໄດ້ຮັບໃນທາງບວກ, ແລະບໍ່ແມ່ນຢູ່ໃນທຸກຂໍ້ຄວາມ. ວິທີນີ້ພວກເຮົາໄດ້ລົບລ້າງໂຕນຂອງ overhead, ແລະສ່ວນທີ່ເຫຼືອຂອງການໂຫຼດແມ່ນສຸມໃສ່ການ loop ຄົ້ນຫາພາຍໃນຂະຫນາດນ້ອຍ, ເຊິ່ງເຫມາະສົມດີສໍາລັບການເພີ່ມປະສິດທິພາບຕື່ມອີກ.

ສູດການຄິດໄລ່ການຊອກຫາຕົວຈິງຂອງພວກເຮົາແມ່ນອີງໃສ່ ຄວາມຄິດທີ່ຍິ່ງໃຫຍ່ຂອງ Leonid Volnitsky. ມັນຄ້າຍຄືກັນກັບ Boyer-Moore algorithm, ຂ້າມປະມານຄວາມຍາວຂອງສາຍຄົ້ນຫາໃນແຕ່ລະຂັ້ນຕອນ. ຄວາມແຕກຕ່າງຕົ້ນຕໍແມ່ນວ່າມັນກວດເບິ່ງສອງໄບຕ໌ໃນເວລາດຽວເພື່ອຫຼຸດຜ່ອນການຈັບຄູ່ທີ່ບໍ່ຖືກຕ້ອງ.

ການປະຕິບັດຂອງພວກເຮົາຮຽກຮ້ອງໃຫ້ມີການສ້າງຕາຕະລາງການຊອກຫາ 64K ສໍາລັບແຕ່ລະການຄົ້ນຫາ, ແຕ່ນັ້ນບໍ່ມີຫຍັງທຽບກັບ gigabytes ຂອງຂໍ້ມູນທີ່ພວກເຮົາກໍາລັງຊອກຫາຜ່ານ. loop ພາຍໃນປະມວນຜົນຫຼາຍ gigabytes ຕໍ່ວິນາທີໃນແກນດຽວ. ໃນການປະຕິບັດ, ການປະຕິບັດທີ່ຫມັ້ນຄົງແມ່ນປະມານ 1,25 GB ຕໍ່ວິນາທີໃນແຕ່ລະຫຼັກ, ແລະມີບ່ອນຫວ່າງສໍາລັບການປັບປຸງ. ມັນເປັນໄປໄດ້ທີ່ຈະກໍາຈັດບາງສ່ວນຂອງ overhead ຢູ່ນອກ loop ພາຍໃນ, ແລະພວກເຮົາວາງແຜນທີ່ຈະທົດລອງກັບ loop ພາຍໃນໃນ C ແທນທີ່ຈະເປັນ Java.

ພວກເຮົາໃຊ້ກໍາລັງ

ພວກເຮົາໄດ້ປຶກສາຫາລືວ່າການຄົ້ນຫາບັນທຶກສາມາດປະຕິບັດໄດ້ "ປະມານ", ແຕ່ວ່າພວກເຮົາມີ "ພະລັງງານ" ຫຼາຍປານໃດ? ຂ້ອນຂ້າງຫຼາຍ.

1 ຫຼັກ: ເມື່ອຖືກນໍາໃຊ້ຢ່າງຖືກຕ້ອງ, ແກນດຽວຂອງໂປເຊດເຊີທີ່ທັນສະໄຫມແມ່ນຂ້ອນຂ້າງມີອໍານາດໃນສິດທິຂອງຕົນເອງ.

8 ແກນ: ພວກເຮົາກຳລັງແລ່ນຢູ່ໃນເຊີບເວີ Amazon hi1.4xlarge ແລະ i2.4xlarge SSD, ແຕ່ລະອັນມີ 8 cores (16 threads). ດັ່ງທີ່ໄດ້ກ່າວມາຂ້າງເທິງ, ຫຼັກເຫຼົ່ານີ້ປົກກະຕິແລ້ວແມ່ນຄ່ອຍມີເວລາກັບການດໍາເນີນງານພື້ນຖານ. ເມື່ອຜູ້ໃຊ້ດໍາເນີນການຄົ້ນຫາ, ການດໍາເນີນງານໃນພື້ນຫລັງຖືກລະງັບ, ປົດປ່ອຍທັງຫມົດ 8 cores ສໍາລັບການຊອກຫາ. ການຄົ້ນຫາປົກກະຕິແລ້ວສໍາເລັດໃນການແບ່ງປັນທີສອງ, ຫຼັງຈາກນັ້ນການເຮັດວຽກຂອງພື້ນຫລັງຈະກັບຄືນມາ (ໂຄງການ throttling ຮັບປະກັນວ່າ barrage ຂອງຄໍາຖາມຄົ້ນຫາບໍ່ແຊກແຊງວຽກງານພື້ນຖານທີ່ສໍາຄັນ).

16 ແກນ: ສໍາລັບຄວາມຫນ້າເຊື່ອຖື, ພວກເຮົາຈັດເຄື່ອງແມ່ຂ່າຍເຂົ້າໄປໃນກຸ່ມແມ່ບົດ / slave. ແມ່ບົດແຕ່ລະຄົນມີຫນຶ່ງ SSD ແລະຫນຶ່ງເຄື່ອງແມ່ຂ່າຍ EBS ພາຍໃຕ້ຄໍາສັ່ງຂອງລາວ. ຖ້າເຄື່ອງແມ່ຂ່າຍຕົ້ນຕໍຂັດຂ້ອງ, ເຄື່ອງແມ່ຂ່າຍ SSD ທັນທີທັນໃດ. ເກືອບຕະຫຼອດເວລາ, ແມ່ບົດແລະທາດເຮັດວຽກດີ, ດັ່ງນັ້ນແຕ່ລະບລັອກຂໍ້ມູນສາມາດຄົ້ນຫາໄດ້ໃນສອງເຄື່ອງແມ່ຂ່າຍທີ່ແຕກຕ່າງກັນ (ເຄື່ອງແມ່ຂ່າຍຂອງທາດ EBS ມີໂປເຊດເຊີທີ່ອ່ອນແອ, ດັ່ງນັ້ນພວກເຮົາບໍ່ໄດ້ພິຈາລະນາມັນ). ພວກເຮົາແບ່ງວຽກງານລະຫວ່າງພວກເຂົາ, ດັ່ງນັ້ນພວກເຮົາມີຈໍານວນທັງຫມົດ 16 ຫຼັກທີ່ມີຢູ່.

ຫຼັກຫຼາຍ: ໃນອະນາຄົດອັນໃກ້ນີ້, ພວກເຮົາຈະແຈກຢາຍຂໍ້ມູນທົ່ວເຊີບເວີໃນລັກສະນະທີ່ພວກມັນທັງຫມົດມີສ່ວນຮ່ວມໃນການປະມວນຜົນທຸກໆຄໍາຮ້ອງຂໍທີ່ບໍ່ແມ່ນເລື່ອງເລັກນ້ອຍ. ທຸກໆຫຼັກຈະເຮັດວຽກ. [ຫມາຍ​ເຫດ​: ພວກ​ເຮົາ​ໄດ້​ປະ​ຕິ​ບັດ​ແຜນ​ການ​ແລະ​ເພີ່ມ​ຄວາມ​ໄວ​ການ​ຊອກ​ຫາ​ເປັນ 1 TB/s​, ເບິ່ງ​ບັນ​ທຶກ​ໃນ​ຕອນ​ທ້າຍ​ຂອງ​ບົດ​ຄວາມ​].

ຄວາມງ່າຍດາຍຮັບປະກັນຄວາມຫນ້າເຊື່ອຖື

ປະໂຫຍດອີກອັນຫນຶ່ງຂອງວິທີການບັງຄັບ brute ແມ່ນການປະຕິບັດທີ່ສອດຄ່ອງພໍສົມຄວນ. ໂດຍປົກກະຕິ, ການຄົ້ນຫາບໍ່ມີຄວາມອ່ອນໄຫວຫຼາຍຕໍ່ລາຍລະອຽດຂອງບັນຫາແລະຊຸດຂໍ້ມູນ (ຂ້ອຍເດົາວ່າມັນເປັນເຫດຜົນທີ່ເອີ້ນວ່າ "ຫຍາບ").

ບາງຄັ້ງດັດສະນີຄໍາສໍາຄັນເຮັດໃຫ້ຜົນໄດ້ຮັບໄວຢ່າງບໍ່ຫນ້າເຊື່ອ, ແລະເວລາອື່ນໆມັນບໍ່ໄດ້. ສົມມຸດວ່າທ່ານມີບັນທຶກ 50 GB ເຊິ່ງຄໍາວ່າ 'customer_5987235982' ປາກົດສາມເທື່ອ. ການຄົ້ນຫາສໍາລັບຄໍານີ້ນັບສາມສະຖານທີ່ໂດຍກົງຈາກດັດຊະນີແລະຈະສໍາເລັດທັນທີ. ແຕ່ການຄົ້ນຫາ wildcard ສະລັບສັບຊ້ອນສາມາດສະແກນຫລາຍພັນຄໍາແລະໃຊ້ເວລາດົນ.

ໃນທາງກົງກັນຂ້າມ, ການຄົ້ນຫາຜົນບັງຄັບໃຊ້ brute ປະຕິບັດດ້ວຍຄວາມໄວຫຼາຍຫຼືຫນ້ອຍດຽວກັນສໍາລັບການສອບຖາມໃດໆ. ການຊອກຫາຄຳສັບຍາວແມ່ນດີກວ່າ, ແຕ່ເຖິງແມ່ນການຊອກຫາຕົວອັກສອນຕົວດຽວກໍຂ້ອນຂ້າງໄວ.

ຄວາມງ່າຍດາຍຂອງວິທີການບັງຄັບ brute ຫມາຍຄວາມວ່າປະສິດທິພາບຂອງມັນແມ່ນຢູ່ໃກ້ກັບສູງສຸດທິດສະດີຂອງຕົນ. ມີທາງເລືອກຫນ້ອຍສໍາລັບການ overloads ແຜ່ນທີ່ບໍ່ຄາດຄິດ, ການຂັດແຍ້ງກ່ຽວກັບການລັອກ, ການແລ່ນຕົວຊີ້, ແລະຫລາຍພັນເຫດຜົນອື່ນໆສໍາລັບຄວາມລົ້ມເຫຼວ. ຂ້າພະເຈົ້າພຽງແຕ່ເບິ່ງຄໍາຮ້ອງຂໍທີ່ເຮັດໂດຍຜູ້ໃຊ້ Scalyr ໃນອາທິດທີ່ຜ່ານມາໃນເຄື່ອງແມ່ຂ່າຍທີ່ຫຍຸ້ງທີ່ສຸດຂອງພວກເຮົາ. ມີ 14 ຄໍາຮ້ອງຂໍ. ແນ່ນອນວ່າແປດຂອງພວກເຂົາໃຊ້ເວລາຫຼາຍກວ່າຫນຶ່ງວິນາທີ; 000% ສໍາເລັດພາຍໃນ 99 milliseconds (ຖ້າທ່ານບໍ່ໄດ້ໃຊ້ເຄື່ອງມືການວິເຄາະບັນທຶກ, ເຊື່ອຂ້ອຍ: ມັນໄວ).

ການປະຕິບັດທີ່ຫມັ້ນຄົງ, ເຊື່ອຖືໄດ້ເປັນສິ່ງສໍາຄັນເພື່ອຄວາມສະດວກໃນການນໍາໃຊ້ການບໍລິການ. ຖ້າມັນຊັກຊ້າເປັນໄລຍະ, ຜູ້ໃຊ້ຈະຮັບຮູ້ວ່າມັນບໍ່ຫນ້າເຊື່ອຖືແລະລັງເລທີ່ຈະໃຊ້ມັນ.

ບັນທຶກການຄົ້ນຫາໃນການປະຕິບັດ

ນີ້ແມ່ນພາບເຄື່ອນໄຫວສັ້ນທີ່ສະແດງໃຫ້ເຫັນການຊອກຫາ Scalyr ໃນການປະຕິບັດ. ພວກເຮົາມີບັນຊີຕົວຢ່າງທີ່ພວກເຮົານໍາເຂົ້າທຸກໆເຫດການໃນທຸກບ່ອນເກັບມ້ຽນ Github ສາທາລະນະ. ໃນການສາທິດນີ້, ຂ້າພະເຈົ້າກວດເບິ່ງມູນຄ່າຂອງຂໍ້ມູນຕໍ່ອາທິດ: ປະມານ 600 MB ຂອງບັນທຶກດິບ.

ວິດີໂອໄດ້ຖືກບັນທຶກສົດ, ໂດຍບໍ່ມີການກະກຽມພິເສດ, ໃນ desktop ຂອງຂ້ອຍ (ປະມານ 5000 ກິໂລແມັດຈາກເຄື່ອງແມ່ຂ່າຍ). ປະສິດທິພາບທີ່ເຈົ້າຈະເຫັນສ່ວນໃຫຍ່ແມ່ນຍ້ອນ ການເພີ່ມປະສິດທິພາບລູກຄ້າເວັບ, ເຊັ່ນດຽວກັນກັບ backend ໄວແລະເຊື່ອຖືໄດ້. ເມື່ອໃດກໍ່ຕາມທີ່ມີການຢຸດຊົ່ວຄາວໂດຍບໍ່ມີຕົວຊີ້ວັດ 'ການໂຫຼດ', ມັນແມ່ນຂ້ອຍຢຸດຊົ່ວຄາວເພື່ອໃຫ້ເຈົ້າສາມາດອ່ານສິ່ງທີ່ຂ້ອຍກໍາລັງຈະກົດ.

ໃນການສະຫລຸບ

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

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

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

ແກ້ໄຂ: ຫົວຂໍ້ແລະຂໍ້ຄວາມໄດ້ປ່ຽນຈາກ "ຄົ້ນຫາທີ່ 20 GB ຕໍ່ວິນາທີ" ເປັນ "ຄົ້ນຫາທີ່ 1 TB ຕໍ່ວິນາທີ" ເພື່ອສະທ້ອນເຖິງການປະຕິບັດທີ່ເພີ່ມຂຶ້ນໃນສອງສາມປີຜ່ານມາ. ຄວາມໄວເພີ່ມຂຶ້ນນີ້ຕົ້ນຕໍແມ່ນຍ້ອນການປ່ຽນແປງຂອງປະເພດແລະຈໍານວນຂອງເຄື່ອງແມ່ຂ່າຍ EC2 ທີ່ພວກເຮົາກໍາລັງວາງໄວ້ໃນມື້ນີ້ເພື່ອຮັບໃຊ້ຖານລູກຄ້າທີ່ເພີ່ມຂຶ້ນຂອງພວກເຮົາ. ມີການປ່ຽນແປງໃນໄວໆນີ້ທີ່ຈະໃຫ້ປະສິດທິພາບໃນການດໍາເນີນງານຢ່າງຫຼວງຫຼາຍ, ແລະພວກເຮົາບໍ່ສາມາດລໍຖ້າທີ່ຈະແບ່ງປັນໃຫ້ເຂົາເຈົ້າ.

ແຫຼ່ງຂໍ້ມູນ: www.habr.com