ແມວຂອງ Schrödinger ໂດຍບໍ່ມີກ່ອງ: ບັນຫາຂອງການເປັນເອກະສັນກັນໃນລະບົບແຈກຢາຍ

ດັ່ງນັ້ນ, ໃຫ້ຈິນຕະນາການ. ມີແມວ 5 ໂຕຖືກລັອກຢູ່ໃນຫ້ອງ, ແລະເພື່ອໄປປຸກເຈົ້າຂອງ, ພວກເຂົາທັງຫມົດຈໍາເປັນຕ້ອງໄດ້ຕົກລົງກັນກ່ຽວກັບເລື່ອງນີ້, ເພາະວ່າພວກເຂົາພຽງແຕ່ສາມາດເປີດປະຕູໄດ້ໂດຍມີ XNUMX ໂຕນອນຢູ່ເທິງມັນ. ຖ້າແມວໂຕໜຶ່ງເປັນແມວຂອງ Schrödinger, ແລະແມວໂຕອື່ນບໍ່ຮູ້ເຖິງການຕັດສິນໃຈຂອງລາວ, ຄຳຖາມຈະເກີດຂື້ນວ່າ: "ພວກມັນເຮັດໄດ້ແນວໃດ?"

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

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

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

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

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

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

ຮູບ​ພາບ​ເບົາ​ບາງ​ທີ່​ຈະ​ໄດ້​ຮັບ​ການ​ປຶກ​ສາ​ຫາ​ລື​ຕໍ່​ໄປ​ນີ້​: ວຽກ​ງານ​ຂອງ​ສອງ​ນາຍ​ພົນ​ລອງເບິ່ງການອຸ່ນເຄື່ອງ ວຽກ​ງານ​ຂອງ​ສອງ​ນາຍ​ພົນ​.

ພວກເຮົາມີສອງກອງທັບ - ສີແດງແລະສີຂາວ. ທະຫານສີຂາວ ຢູ່ໃນເມືອງທີ່ຖືກປິດລ້ອມ. ກອງທັບ​ແດງ​ທີ່​ນຳພາ​ໂດຍ​ນາຍ​ພົນ A1 ​ແລະ A2 ​ແມ່ນ​ຕັ້ງ​ຢູ່​ສອງ​ຝັ່ງ​ຂອງ​ເມືອງ. ວຽກງານຂອງ redheads ແມ່ນເພື່ອໂຈມຕີເມືອງສີຂາວແລະຊະນະ. ຢ່າງໃດກໍຕາມ, ກອງທັບຂອງນາຍພົນສີແດງແຕ່ລະຄົນມີຂະຫນາດນ້ອຍກວ່າກອງທັບສີຂາວ.

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

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

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

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

ບັນຫາທົ່ວໄປສອງແມ່ນເປັນຕົວຢ່າງທີ່ຍິ່ງໃຫຍ່ຂອງລະບົບການແຈກຢາຍທີ່ງ່າຍດາຍຫຼາຍທີ່ມີສອງ nodes ທີ່ມີການສື່ສານທີ່ບໍ່ຫນ້າເຊື່ອຖື. ນີ້ຫມາຍຄວາມວ່າພວກເຮົາບໍ່ມີການຮັບປະກັນ 100% ວ່າພວກມັນຖືກ synchronized. ບັນຫາທີ່ຄ້າຍຄືກັນໄດ້ຖືກປຶກສາຫາລືພຽງແຕ່ໃນຂະຫນາດໃຫຍ່ຕໍ່ມາໃນບົດຄວາມ.

ພວກເຮົາແນະນໍາແນວຄວາມຄິດຂອງລະບົບແຈກຢາຍ

ລະບົບການແຈກຢາຍແມ່ນກຸ່ມຄອມພິວເຕີ (ຕໍ່ໄປນີ້ພວກເຮົາຈະໂທຫາພວກເຂົາ nodes) ທີ່ສາມາດແລກປ່ຽນຂໍ້ຄວາມໄດ້. ແຕ່ລະ node ສ່ວນບຸກຄົນແມ່ນບາງປະເພດຂອງ autonomous entity. node ສາມາດປະມວນຜົນວຽກງານດ້ວຍຕົວມັນເອງ, ແຕ່ເພື່ອຕິດຕໍ່ສື່ສານກັບ nodes ອື່ນໆ, ມັນຈໍາເປັນຕ້ອງໄດ້ສົ່ງແລະຮັບຂໍ້ຄວາມ.

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

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

ຄຸນລັກສະນະຂອງລະບົບແຈກຢາຍ

1. Concurrency - ຄວາມ​ເປັນ​ໄປ​ໄດ້​ຂອງ​ເຫດ​ການ​ພ້ອມ​ກັນ​ຫຼື​ພ້ອມ​ກັນ​ທີ່​ເກີດ​ຂຶ້ນ​ໃນ​ລະ​ບົບ​. ຍິ່ງໄປກວ່ານັ້ນ, ພວກເຮົາຈະພິຈາລະນາເຫດການທີ່ເກີດຂື້ນໃນສອງໂຫນດທີ່ແຕກຕ່າງກັນທີ່ຈະມີຄວາມສອດຄ່ອງກັນຕາບໃດທີ່ພວກເຮົາບໍ່ມີຄໍາສັ່ງທີ່ຊັດເຈນຂອງເຫດການເຫຼົ່ານີ້. ແຕ່, ຕາມກົດລະບຽບ, ພວກເຮົາບໍ່ມີມັນ.
2. ບໍ່ມີໂມງທົ່ວໂລກ. ພວກເຮົາບໍ່ມີການຈັດລໍາດັບເຫດການທີ່ຊັດເຈນເນື່ອງຈາກການຂາດໂມງທົ່ວໂລກ. ໃນ​ໂລກ​ປະ​ຊຸມ​ສະ​ໄຫມ​ຂອງ​ປະ​ຊາ​ຊົນ​, ພວກ​ເຮົາ​ແມ່ນ​ເຮັດ​ໃຫ້​ເຄຍ​ຊີນ​ກັບ​ຄວາມ​ຈິງ​ທີ່​ວ່າ​ພວກ​ເຮົາ​ມີ​ໂມງ​ແລະ​ເວ​ລາ​ຢ່າງ​ແທ້​ຈິງ​. ທຸກສິ່ງທຸກຢ່າງປ່ຽນແປງເມື່ອມັນມາກັບລະບົບແຈກຢາຍ. ແມ່ນແຕ່ໂມງປະລໍາມະນູທີ່ຊັດເຈນທີ່ສຸດກໍມີການລອຍ, ແລະອາດມີສະຖານະການທີ່ພວກເຮົາບໍ່ສາມາດບອກໄດ້ວ່າສອງເຫດການໃດເກີດຂຶ້ນກ່ອນ. ເພາະສະນັ້ນ, ພວກເຮົາບໍ່ສາມາດອີງໃສ່ເວລາ.
3. ຄວາມລົ້ມເຫຼວທີ່ເປັນເອກະລາດຂອງ nodes ລະບົບ. ມີບັນຫາອີກຢ່າງຫນຶ່ງ: ບາງສິ່ງບາງຢ່າງອາດຈະຜິດພາດພຽງແຕ່ເນື່ອງຈາກວ່າ nodes ຂອງພວກເຮົາບໍ່ໄດ້ຢູ່ຕະຫຼອດໄປ. ຮາດດິດອາດຈະລົ້ມເຫລວ, ເຄື່ອງ virtual ຢູ່ໃນຄລາວອາດຈະປິດເປີດໃຫມ່, ເຄືອຂ່າຍອາດຈະກະພິບແລະຂໍ້ຄວາມຈະສູນເສຍ. ຍິ່ງໄປກວ່ານັ້ນ, ອາດຈະມີສະຖານະການທີ່ nodes ເຮັດວຽກ, ແຕ່ໃນເວລາດຽວກັນເຮັດວຽກຕໍ່ຕ້ານລະບົບ. ຫ້ອງຮຽນສຸດທ້າຍຂອງບັນຫາເຖິງແມ່ນວ່າໄດ້ຮັບຊື່ແຍກຕ່າງຫາກ: ບັນຫາ ນາຍພົນ Byzantine. ຕົວຢ່າງທີ່ນິຍົມທີ່ສຸດຂອງລະບົບແຈກຢາຍທີ່ມີບັນຫານີ້ແມ່ນ Blockchain. ແຕ່ມື້ນີ້ພວກເຮົາຈະບໍ່ພິຈາລະນາຫ້ອງຮຽນພິເສດຂອງບັນຫານີ້. ພວກເຮົາຈະສົນໃຈສະຖານະການທີ່ພຽງແຕ່ຫນຶ່ງຫຼືຫຼາຍ nodes ອາດຈະລົ້ມເຫລວ.
4. ຮູບແບບການສື່ສານ (ແບບຈໍາລອງການສົ່ງຂໍ້ຄວາມ) ລະຫວ່າງ nodes. ພວກເຮົາໄດ້ສ້າງຕັ້ງແລ້ວວ່າ nodes ຕິດຕໍ່ສື່ສານໂດຍການແລກປ່ຽນຂໍ້ຄວາມ. ມີສອງຮູບແບບການສົ່ງຂໍ້ຄວາມທີ່ມີຊື່ສຽງ: synchronous ແລະ asynchronous.

ແບບຈໍາລອງຂອງການສື່ສານລະຫວ່າງ nodes ໃນລະບົບແຈກຢາຍ

ແບບ synchronous – ພວກ​ເຮົາ​ຮູ້​ຢ່າງ​ແນ່​ໃຈວ່​າ​ມີ delta ທີ່​ຮູ້​ຈັກ​ຈໍາ​ກັດ​ຂອງ​ທີ່​ໃຊ້​ເວ​ລາ​ໃນ​ໄລ​ຍະ​ທີ່​ຂໍ້​ຄວາມ​ໄດ້​ຮັບ​ການ​ຮັບ​ປະ​ກັນ​ທີ່​ຈະ​ໄປ​ເຖິງ​ຈາກ node ຫນຶ່ງ​ໄປ​ອີກ​. ຖ້າເວລານີ້ຜ່ານໄປແລະຂໍ້ຄວາມບໍ່ມາຮອດ, ພວກເຮົາສາມາດເວົ້າໄດ້ຢ່າງປອດໄພວ່າ node ລົ້ມເຫລວ. ໃນຮູບແບບນີ້ພວກເຮົາມີເວລາລໍຖ້າທີ່ຄາດເດົາໄດ້.

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

ແນວຄວາມຄິດຂອງການເປັນເອກະສັນກັນໃນລະບົບແຈກຢາຍ

ກ່ອນທີ່ຈະກໍານົດແນວຄວາມຄິດຂອງການເປັນເອກະສັນກັນຢ່າງເປັນທາງການ, ໃຫ້ພິຈາລະນາຕົວຢ່າງຂອງສະຖານະການທີ່ພວກເຮົາຕ້ອງການ, ຄື - ການຈຳລອງເຄື່ອງຂອງລັດ.

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

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

ຢ່າງເປັນທາງການຫຼາຍ, ພວກເຮົາສາມາດກໍານົດວິທີການ consensus algorithm (ຫຼືພຽງແຕ່ເປັນ consensus algorithm) ເປັນຫນ້າທີ່ສະເພາະໃດຫນຶ່ງທີ່ໂອນລະບົບການແຈກຢາຍຈາກລັດ A ກັບລັດ B. ນອກຈາກນັ້ນ, ລັດນີ້ໄດ້ຮັບການຍອມຮັບໂດຍທຸກ nodes, ແລະ nodes ທັງຫມົດສາມາດຢືນຢັນມັນໄດ້. ຍ້ອນວ່າມັນຫັນອອກ, ວຽກງານນີ້ບໍ່ແມ່ນຢູ່ໃນທັງຫມົດເປັນ trivial ຍ້ອນວ່າມັນເບິ່ງຄືວ່າຢູ່ glance ທໍາອິດ.

ຄຸນສົມບັດຂອງລະບົບຄວາມເຫັນດີເຫັນພ້ອມ

ຂັ້ນຕອນການເປັນເອກະສັນກັນຕ້ອງມີຄຸນສົມບັດສາມຢ່າງເພື່ອໃຫ້ລະບົບສືບຕໍ່ມີຢູ່ ແລະມີຄວາມຄືບໜ້າບາງຢ່າງໃນການເຄື່ອນຍ້າຍຈາກລັດໄປສູ່ລັດ:

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

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

2. ຄວາມສົມບູນ — ຖ້າທຸກໂຫນດເຮັດວຽກຢ່າງຖືກຕ້ອງໃຫ້ຄ່າດຽວກັນ v, ຊຶ່ງຫມາຍຄວາມວ່າທຸກ node ທີ່ເຮັດວຽກທີ່ຖືກຕ້ອງຕ້ອງຍອມຮັບຄ່ານີ້ v.
3. ການສິ້ນສຸດ - ທຸກໆຂໍ້ປະຕິບັດການທີ່ຖືກຕ້ອງໃນທີ່ສຸດກໍຈະເອົາຄ່າທີ່ແນ່ນອນ (ຄຸນສົມບັດການມີຊີວິດຊີວາ), ເຊິ່ງອະນຸຍາດໃຫ້ algorithm ມີຄວາມຄືບໜ້າໃນລະບົບ. ແຕ່ລະໂຫນດປະຕິບັດການຢ່າງຖືກຕ້ອງຈະຕ້ອງບໍ່ຊ້າຫຼືຫຼັງຈາກນັ້ນຍອມຮັບຄ່າສຸດທ້າຍແລະຢືນຢັນມັນ: "ສໍາລັບຂ້ອຍ, ຄ່ານີ້ແມ່ນຄວາມຈິງ, ຂ້ອຍເຫັນດີກັບລະບົບທັງຫມົດ."

ຕົວຢ່າງຂອງວິທີການເຮັດວຽກເປັນເອກະສັນກັນ

ໃນຂະນະທີ່ຄຸນສົມບັດຂອງ algorithm ອາດຈະບໍ່ຊັດເຈນທັງຫມົດ. ດັ່ງນັ້ນ, ພວກເຮົາຈະຍົກຕົວຢ່າງກ່ຽວກັບຂັ້ນຕອນຂອງຂັ້ນຕອນການເປັນເອກະສັນກັນທີ່ງ່າຍດາຍທີ່ສຸດໃນລະບົບທີ່ມີຮູບແບບການສົ່ງຂໍ້ຄວາມແບບ synchronous, ເຊິ່ງທຸກ nodes ເຮັດວຽກຕາມທີ່ຄາດໄວ້, ຂໍ້ຄວາມບໍ່ໄດ້ສູນເສຍແລະບໍ່ມີຫຍັງແຕກ (ນີ້ກໍ່ເກີດຂຶ້ນບໍ?).

1. ມັນທັງຫມົດເລີ່ມຕົ້ນດ້ວຍການສະເຫນີການແຕ່ງງານ (Propose). ໃຫ້ສົມມຸດວ່າລູກຄ້າເຊື່ອມຕໍ່ກັບ node ທີ່ເອີ້ນວ່າ "Node 1" ແລະເລີ່ມຕົ້ນການເຮັດທຸລະກໍາ, ສົ່ງຄ່າໃຫມ່ໄປຫາ node - O. ຈາກນີ້ໄປ, ພວກເຮົາຈະໂທຫາ "Node 1" ສະ ເໜີ. ໃນຖານະເປັນຜູ້ສະເຫນີ, "Node 1" ຕອນນີ້ຕ້ອງແຈ້ງໃຫ້ລະບົບທັງຫມົດວ່າມັນມີຂໍ້ມູນສົດ, ແລະມັນສົ່ງຂໍ້ຄວາມໄປຫາ nodes ອື່ນໆທັງຫມົດ: "ເບິ່ງ! ຄວາມໝາຍ “ໂອ” ມາຫາຂ້ອຍ ແລະຢາກຂຽນມັນລົງ! ກະລຸນາຢືນຢັນວ່າທ່ານຈະບັນທຶກ “O” ໃນບັນທຶກຂອງເຈົ້ານຳ.

   

2. ຂັ້ນຕອນຕໍ່ໄປແມ່ນການລົງຄະແນນສຽງສໍາລັບມູນຄ່າທີ່ສະເຫນີ (Voting). ມັນແມ່ນຫຍັງ? ມັນອາດຈະເກີດຂື້ນວ່າ nodes ອື່ນໆໄດ້ຮັບຂໍ້ມູນທີ່ຜ່ານມາຫຼາຍ, ແລະພວກເຂົາມີຂໍ້ມູນໃນທຸລະກໍາດຽວກັນ.

   
   
   ເມື່ອ node "Node 1" ສົ່ງຂໍ້ສະເຫນີຂອງມັນ, nodes ອື່ນໆກວດເບິ່ງບັນທຶກຂອງເຂົາເຈົ້າສໍາລັບຂໍ້ມູນກ່ຽວກັບເຫດການນີ້. ຖ້າບໍ່ມີຂໍ້ຂັດແຍ້ງ, ຂໍ້ຄວາມປະກາດວ່າ: "ແມ່ນແລ້ວ, ຂ້ອຍບໍ່ມີຂໍ້ມູນອື່ນສໍາລັບເຫດການນີ້. ຄ່າ “O” ແມ່ນຂໍ້ມູນຫຼ້າສຸດທີ່ພວກເຮົາສົມຄວນໄດ້ຮັບ.”

   ໃນກໍລະນີອື່ນໆ, nodes ສາມາດຕອບສະຫນອງຕໍ່ "Node 1": "ຟັງ! ຂ້ອຍມີຂໍ້ມູນຫຼ້າສຸດກ່ຽວກັບການເຮັດທຸລະກໍານີ້. ບໍ່ແມ່ນ 'O', ແຕ່ບາງສິ່ງບາງຢ່າງທີ່ດີກວ່າ."

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

3. ຖ້າຮອບການລົງຄະແນນສຽງປະສົບຜົນສໍາເລັດແລະທຸກຄົນໄດ້ຮັບຄວາມໂປດປານ, ຫຼັງຈາກນັ້ນລະບົບຈະຍ້າຍໄປຂັ້ນຕອນໃຫມ່ - ການຍອມຮັບມູນຄ່າ. “Node 1” ລວບລວມຄຳຕອບທັງໝົດຈາກ nodes ແລະລາຍງານອື່ນໆ: “ທຸກຄົນເຫັນດີກັບຄ່າ “O”! ໃນປັດຈຸບັນຂ້າພະເຈົ້າປະກາດຢ່າງເປັນທາງການວ່າ "O" ແມ່ນຄວາມຫມາຍໃຫມ່ຂອງພວກເຮົາ, ຄືກັນສໍາລັບທຸກຄົນ! ຂຽນມັນໄວ້ໃນປື້ມນ້ອຍໆຂອງເຈົ້າ, ຢ່າລືມ. ຂຽນມັນລົງໃນບັນທຶກຂອງເຈົ້າ!"

   

4. ຂໍ້ທີ່ຍັງເຫຼືອສົ່ງການຢືນຢັນ (ຍອມຮັບ) ວ່າພວກເຂົາໄດ້ຂຽນລົງ "O"; ບໍ່ມີຫຍັງໃຫມ່ມາຮອດໃນເວລານີ້ (ປະເພດຂອງຄໍາຫມັ້ນສັນຍາສອງໄລຍະ). ຫຼັງຈາກເຫດການທີ່ສໍາຄັນນີ້, ພວກເຮົາພິຈາລະນາວ່າທຸລະກໍາທີ່ແຈກຢາຍໄດ້ສໍາເລັດ.
   

ດັ່ງນັ້ນ, ຂັ້ນຕອນການເປັນເອກະສັນກັນໃນກໍລະນີງ່າຍດາຍປະກອບດ້ວຍສີ່ຂັ້ນຕອນ: ສະເຫນີ, ລົງຄະແນນສຽງ (ລົງຄະແນນສຽງ), ຍອມຮັບ (ຍອມຮັບ), ຢືນຢັນການຍອມຮັບ (ຍອມຮັບ).

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

ສູດການຄິດໄລ່ເປັນເອກະສັນກັນໃນລະບົບບໍ່ຊິ້ງ

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

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

ຄໍາຕອບທີ່ຖືກຕ້ອງແລະເຫດຜົນແມ່ນຢູ່ເບື້ອງຫຼັງ spoiler.ຄໍາຕອບທີ່ຖືກຕ້ອງແມ່ນ: 0. ຖ້າແມ້ແຕ່ຫນຶ່ງ node ໃນລະບົບ asynchronous ລົ້ມເຫລວ, ລະບົບຈະບໍ່ສາມາດບັນລຸຄວາມເຫັນດີນໍາ. ຄໍາຖະແຫຼງການນີ້ໄດ້ຖືກພິສູດໃນທິດສະດີ FLP, ເປັນທີ່ຮູ້ຈັກກັນດີໃນບາງວົງການ (1985, Fischer, Lynch, Paterson, ເຊື່ອມຕໍ່ກັບຕົ້ນສະບັບໃນຕອນທ້າຍຂອງບົດຄວາມ): "ເປັນໄປບໍ່ໄດ້ທີ່ຈະບັນລຸຄວາມເຫັນດີນໍາທີ່ແຈກຢາຍຖ້າຫາກວ່າຢ່າງຫນ້ອຍຫນຶ່ງ node ລົ້ມເຫລວ. .”

Guys, ຫຼັງຈາກນັ້ນພວກເຮົາມີບັນຫາ, ພວກເຮົາຖືກນໍາໃຊ້ກັບທຸກສິ່ງທຸກຢ່າງເປັນ asynchronous. ແລະໃນທີ່ນີ້ມັນແມ່ນ. ສືບຕໍ່ດໍາລົງຊີວິດແນວໃດ?

ພວກເຮົາພຽງແຕ່ເວົ້າກ່ຽວກັບທິດສະດີ, ກ່ຽວກັບຄະນິດສາດ. "ຄວາມເຫັນດີບໍ່ສາມາດບັນລຸໄດ້" ຫມາຍຄວາມວ່າແນວໃດ, ການແປຈາກພາສາຄະນິດສາດເຂົ້າໄປໃນຂອງພວກເຮົາ - ວິສະວະກໍາ? ນີ້ຫມາຍຄວາມວ່າ "ບໍ່ສາມາດບັນລຸໄດ້ສະເຫມີ", i.e. ມີກໍລະນີທີ່ຄວາມເຫັນດີບໍ່ສາມາດບັນລຸໄດ້. ນີ້ແມ່ນກໍລະນີປະເພດໃດ?

ນີ້ແມ່ນການລະເມີດຊັບສິນທີ່ມີຊີວິດຊີວາທີ່ອະທິບາຍຂ້າງເທິງ. ພວກເຮົາບໍ່ມີຂໍ້ຕົກລົງທົ່ວໄປ, ແລະລະບົບບໍ່ສາມາດມີຄວາມຄືບຫນ້າ (ບໍ່ສາມາດສໍາເລັດໃນເວລາກໍານົດ) ໃນກໍລະນີທີ່ພວກເຮົາບໍ່ມີການຕອບສະຫນອງຈາກທຸກ nodes. ເນື່ອງຈາກວ່າໃນລະບົບ asynchronous ພວກເຮົາບໍ່ມີເວລາຕອບໂຕ້ທີ່ຄາດເດົາໄດ້ແລະພວກເຮົາບໍ່ສາມາດຮູ້ໄດ້ວ່າ node ໄດ້ crash ຫຼືພຽງແຕ່ໃຊ້ເວລາດົນໃນການຕອບສະຫນອງ.

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

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

ຊ່ວງເວລານີ້ອາດຈະບໍ່ມາເປັນເວລາດົນປານໃດ, ແຕ່ຕ້ອງມາໃນມື້ໜຶ່ງ. ໂມງປຸກ virtual ຈະດັງ, ແລະຈາກເວລານັ້ນພວກເຮົາສາມາດຄາດຄະເນເວລາ delta ສໍາລັບຂໍ້ຄວາມທີ່ຈະມາຮອດ. ຈາກປັດຈຸບັນນີ້, ລະບົບຈະປ່ຽນຈາກ asynchronous ເປັນ synchronous. ໃນທາງປະຕິບັດ, ພວກເຮົາຈັດການກັບລະບົບດັ່ງກ່າວຢ່າງແນ່ນອນ.

ສູດການຄິດໄລ່ Paxos ແກ້ໄຂບັນຫາຄວາມເຫັນດີເຫັນພ້ອມ

ປາໂກສ ແມ່ນຄອບຄົວຂອງສູດການຄິດໄລ່ທີ່ແກ້ໄຂບັນຫາການເປັນເອກະສັນກັນສໍາລັບລະບົບ synchronous ບາງສ່ວນ, ຂຶ້ນກັບຄວາມເປັນໄປໄດ້ທີ່ບາງ nodes ອາດຈະລົ້ມເຫລວ. ຜູ້ຂຽນຂອງ Paxos ແມ່ນ Leslie Lamport. ລາວ​ໄດ້​ສະ​ເໜີ​ຫຼັກ​ຖານ​ຢ່າງ​ເປັນ​ທາງ​ການ​ກ່ຽວ​ກັບ​ການ​ມີ​ຢູ່​ແລະ​ຄວາມ​ຖືກ​ຕ້ອງ​ຂອງ​ວິ​ທີ​ການ​ໃນ​ປີ 1989.

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

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

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

ບົດບາດຂອງ Paxos

Paxos algorithm ມີແນວຄວາມຄິດຂອງພາລະບົດບາດ. ຂໍ​ໃຫ້​ພິຈາລະນາ​ສາມ​ອັນ​ຕົ້ນ​ຕໍ (ມີ​ການ​ດັດ​ແກ້​ທີ່​ມີ​ບົດບາດ​ເພີ່ມ​ເຕີມ):

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

ໂຫນດດຽວສາມາດສົມທົບຫຼາຍບົດບາດໃນສະຖານະການທີ່ແຕກຕ່າງກັນ.

ແນວຄວາມຄິດຂອງກຸ່ມ

ພວກເຮົາສົມມຸດວ່າພວກເຮົາມີລະບົບຂອງ N nodes ແລະຂອງພວກເຂົາສູງສຸດ F nodes ອາດຈະລົ້ມເຫລວ. ຖ້າ F nodes ລົ້ມເຫລວ, ພວກເຮົາຕ້ອງມີຢ່າງຫນ້ອຍ 2F+1 ຂໍ້ຍອມຮັບ.

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

ຄວາມຄິດທົ່ວໄປກ່ຽວກັບວິທີ Paxos consensus algorithm ເຮັດວຽກ

ສູດການຄິດໄລ່ Paxos ປະກອບມີສອງໄລຍະໃຫຍ່, ເຊິ່ງໃນນັ້ນແບ່ງອອກເປັນສອງຂັ້ນຕອນໃນແຕ່ລະ:

1. ໄລຍະທີ 1a: ກະກຽມ. ໃນໄລຍະການກະກຽມ, ຜູ້ນໍາ (ຜູ້ສະເຫນີ) ແຈ້ງໃຫ້ທຸກ nodes: "ພວກເຮົາກໍາລັງເລີ່ມຕົ້ນການລົງຄະແນນສຽງໃຫມ່. ພວກເຮົາມີຮອບໃຫມ່. ຈໍານວນຂອງຮອບນີ້ແມ່ນ n. ດຽວນີ້ພວກເຮົາຈະເລີ່ມລົງຄະແນນສຽງ." ສໍາລັບໃນປັດຈຸບັນ, ມັນພຽງແຕ່ລາຍງານການເລີ່ມຕົ້ນຂອງວົງຈອນໃຫມ່, ແຕ່ບໍ່ໄດ້ລາຍງານມູນຄ່າໃຫມ່. ວຽກງານຂອງຂັ້ນຕອນນີ້ແມ່ນເພື່ອລິເລີ່ມຮອບໃຫມ່ແລະແຈ້ງໃຫ້ທຸກຄົນຂອງຈໍານວນເປັນເອກະລັກຂອງຕົນ. ຕົວເລກຮອບແມ່ນສໍາຄັນ, ມັນຕ້ອງເປັນມູນຄ່າຫຼາຍກວ່າຕົວເລກລົງຄະແນນສຽງທີ່ຜ່ານມາຈາກຜູ້ນໍາທັງຫມົດທີ່ຜ່ານມາ. ເນື່ອງຈາກວ່າມັນເປັນການຂອບໃຈກັບຕົວເລກຮອບທີ່ nodes ອື່ນໆໃນລະບົບຈະເຂົ້າໃຈວ່າຂໍ້ມູນຂອງຜູ້ນໍາບໍ່ດົນມານີ້ຫຼາຍປານໃດ. ມັນເປັນໄປໄດ້ວ່າຂໍ້ອື່ນໆມີຜົນການລົງຄະແນນສຽງແລ້ວຈາກຮອບຕໍ່ມາຫຼາຍ ແລະພຽງແຕ່ຈະບອກຜູ້ນໍາວ່າລາວຢູ່ຫລັງເວລາ.
2. ໄລຍະທີ 1b: ສັນຍາ. ເມື່ອໂຫມດຜູ້ຍອມຮັບໄດ້ຮັບຈໍານວນຂັ້ນຕອນການລົງຄະແນນສຽງໃຫມ່, ສອງຜົນໄດ້ຮັບທີ່ເປັນໄປໄດ້:
   • ຈໍານວນ n ຂອງການລົງຄະແນນສຽງໃຫມ່ແມ່ນຫຼາຍກວ່າຈໍານວນການລົງຄະແນນສຽງທີ່ຜ່ານມາທີ່ຜູ້ຍອມຮັບເຂົ້າຮ່ວມ. ຫຼັງຈາກນັ້ນ, ຜູ້ຮັບໄດ້ສົ່ງຄໍາສັນຍາກັບຜູ້ນໍາວ່າຈະບໍ່ເຂົ້າຮ່ວມໃນຄະແນນສຽງເພີ່ມເຕີມທີ່ມີຈໍານວນຕ່ໍາກວ່າ n. ຖ້າຜູ້ຍອມຮັບໄດ້ລົງຄະແນນສຽງສໍາລັບບາງສິ່ງບາງຢ່າງ (ນັ້ນແມ່ນ, ມັນໄດ້ຍອມຮັບແລ້ວບາງມູນຄ່າໃນໄລຍະທີສອງ), ຫຼັງຈາກນັ້ນມັນຍຶດເອົາມູນຄ່າທີ່ຍອມຮັບແລະຈໍານວນການລົງຄະແນນສຽງທີ່ມັນເຂົ້າຮ່ວມກັບຄໍາສັນຍາຂອງມັນ.
   • ຖ້າບໍ່ດັ່ງນັ້ນ, ຖ້າຜູ້ຍອມຮັບຮູ້ແລ້ວກ່ຽວກັບການລົງຄະແນນສຽງທີ່ມີຈໍານວນສູງກວ່າ, ມັນພຽງແຕ່ສາມາດລະເລີຍຂັ້ນຕອນການກະກຽມແລະບໍ່ຕອບສະຫນອງຕໍ່ຜູ້ນໍາ.
3. ໄລຍະ 2a: ຍອມຮັບ. ຜູ້ນໍາຈໍາເປັນຕ້ອງລໍຖ້າການຕອບສະຫນອງຈາກກຸ່ມ (ສ່ວນຫຼາຍຂອງ nodes ໃນລະບົບ) ແລະ, ຖ້າຈໍານວນການຕອບສະຫນອງທີ່ຕ້ອງການ, ຫຼັງຈາກນັ້ນລາວມີສອງທາງເລືອກສໍາລັບການພັດທະນາເຫດການ:
   • ບາງຄົນທີ່ຍອມຮັບໄດ້ສົ່ງຄຸນຄ່າທີ່ພວກເຂົາໄດ້ລົງຄະແນນສຽງແລ້ວ. ໃນກໍລະນີນີ້, ຜູ້ນໍາເລືອກມູນຄ່າຈາກການລົງຄະແນນສຽງທີ່ມີຈໍານວນສູງສຸດ. ໃຫ້ໂທຫາຄ່ານີ້ x, ແລະມັນຈະສົ່ງຂໍ້ຄວາມໄປຫາທຸກ nodes ເຊັ່ນ: "ຍອມຮັບ (n, x)", ເຊິ່ງຄ່າທໍາອິດແມ່ນຕົວເລກການລົງຄະແນນສຽງຈາກຂັ້ນຕອນ Propose ຂອງມັນເອງ, ແລະຄ່າທີສອງແມ່ນສິ່ງທີ່ທຸກຄົນລວບລວມສໍາລັບ, i.e. ມູນຄ່າທີ່ພວກເຮົາລົງຄະແນນສຽງຕົວຈິງ.
   • ຖ້າບໍ່ມີຜູ້ຍອມຮັບໃດໆທີ່ສົ່ງຄ່າໃດໆ, ແຕ່ພວກເຂົາພຽງແຕ່ສັນຍາວ່າຈະລົງຄະແນນສຽງໃນຮອບນີ້, ຜູ້ນໍາສາມາດເຊື້ອເຊີນໃຫ້ພວກເຂົາລົງຄະແນນສຽງສໍາລັບມູນຄ່າຂອງພວກເຂົາ, ມູນຄ່າທີ່ລາວກາຍເປັນຜູ້ນໍາໃນຄັ້ງທໍາອິດ. ໃຫ້ເອີ້ນມັນວ່າ y. ມັນສົ່ງຂໍ້ຄວາມໄປຫາທຸກໂຫນດເຊັ່ນ: "ຍອມຮັບ (n, y)", ຄ້າຍຄືກັບຜົນໄດ້ຮັບທີ່ຜ່ານມາ.
4. ໄລຍະ 2b: ຍອມຮັບ. ນອກຈາກນັ້ນ, ໂຫນດຜູ້ຮັບ, ເມື່ອໄດ້ຮັບຂໍ້ຄວາມ "ຍອມຮັບ (...)" ຈາກຜູ້ນໍາ, ຕົກລົງເຫັນດີກັບມັນ (ສົ່ງການຢືນຢັນກັບທຸກໂຫມດທີ່ພວກເຂົາຕົກລົງກັບຄ່າໃຫມ່) ພຽງແຕ່ຖ້າພວກເຂົາບໍ່ໄດ້ສັນຍາບາງຢ່າງ (ອື່ນໆ) ) ຜູ້ນໍາເພື່ອເຂົ້າຮ່ວມການລົງຄະແນນສຽງດ້ວຍຈໍານວນຮອບ n' > ນ, ຖ້າບໍ່ດັ່ງນັ້ນພວກເຂົາບໍ່ສົນໃຈຄໍາຮ້ອງຂໍການຢືນຢັນ.

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

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

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

ການ​ເຊື່ອມ​ຕໍ່​ກັບ​ເອ​ກະ​ສານ​ສໍາ​ລັບ​ການ​ສຶກ​ສາ​ເພີ່ມ​ເຕີມ​

ລະດັບເລີ່ມຕົ້ນ:

• ຄວາມເຫັນດີເຫັນພ້ອມແບບແຈກຢາຍເຮັດວຽກແນວໃດ?, Preethi Kasireddy, ບົດຄວາມ blog ກ່ຽວກັບ Medium
• Paxos ເຮັດງ່າຍດາຍ. ສໍາລັບທີ່ແທ້ຈິງ, Adi Kancherla, ບົດຄວາມ blog ກ່ຽວກັບ Medium
• ຄວາມຄິດແບບກະຈາຍ, Ittai Abraham, blog
• Synchrony, Asynchrony ແລະ synchrony ບາງສ່ວນ, Ittai Abraham, ບົດຄວາມ blog

ລະດັບ Leslie Lamport:

• ຄວາມ​ເປັນ​ໄປ​ໄດ້​ຂອງ​ຄວາມ​ເຫັນ​ດີ​ທີ່​ແຈກ​ຢາຍ​ກັບ​ຂະ​ບວນ​ການ​ຫນຶ່ງ​ທີ່​ຜິດ​ພາດ (FLP impossibility​), Fischer, Lynch ແລະ Paterson, ເອກະສານການຄົ້ນຄວ້າ, 1985
• ລັດຖະສະພາ Part-Time, Leslie Lamport, ເອກະສານການຄົ້ນຄວ້າ, 1998
• Paxos ເຮັດງ່າຍດາຍ, Leslie Lamport, ເອກະສານການຄົ້ນຄວ້າ, 2001

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