ທຸລະກໍາແລະກົນໄກການຄວບຄຸມຂອງພວກເຂົາ

ການເຮັດທຸລະ ກຳ

ທຸລະກໍາແມ່ນລໍາດັບຂອງການດໍາເນີນງານກ່ຽວກັບຂໍ້ມູນທີ່ມີຈຸດເລີ່ມຕົ້ນແລະຈຸດສິ້ນສຸດ.

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

ທຸລະກຳຕ້ອງຕອບສະໜອງຄຸນສົມບັດ ACID

ປະລໍາມະນູ. ການເຮັດທຸລະກໍາແມ່ນສໍາເລັດສົມບູນຫຼືບໍ່ທັງຫມົດ.

ຄວາມສອດຄ່ອງ. ເມື່ອສໍາເລັດການເຮັດທຸລະກໍາ, ຂໍ້ຈໍາກັດທີ່ວາງໄວ້ໃນຂໍ້ມູນ (ຕົວຢ່າງ, ຂໍ້ຈໍາກັດໃນຖານຂໍ້ມູນ) ຈະບໍ່ຖືກລະເມີດ. ຄວາມສອດຄ່ອງ ໝາຍ ຄວາມວ່າລະບົບຈະຖືກໂອນຈາກລັດທີ່ຖືກຕ້ອງໄປຫາອີກລັດທີ່ຖືກຕ້ອງ.

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

ຄວາມຍືນຍົງ. ເມື່ອສັນຍາ, ການປ່ຽນແປງບໍ່ຄວນສູນເສຍ.

ບັນທຶກການເຮັດທຸລະກໍາ

ບັນທຶກເກັບຮັກສາການປ່ຽນແປງທີ່ເຮັດໂດຍການເຮັດທຸລະກໍາ, ຮັບປະກັນຄວາມຫມັ້ນຄົງແລະຄວາມຫມັ້ນຄົງຂອງຂໍ້ມູນໃນກໍລະນີທີ່ລະບົບລົ້ມເຫລວ

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

ພຽງແຕ່ປະຕິບັດການເຮັດທຸລະກໍາທີ່ລົ້ມເຫລວຄືນໃຫມ່ແມ່ນບໍ່ພຽງພໍສໍາລັບການຟື້ນຕົວ.

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

ລະດັບ insulation

ອ່ານຄໍາຫມັ້ນສັນຍາ

ບັນຫາ Dirty Read ແມ່ນວ່າການເຮັດທຸລະກໍາສາມາດອ່ານຜົນໄດ້ຮັບລະດັບປານກາງຂອງທຸລະກໍາອື່ນ.

ຕົວຢ່າງ. ມູນຄ່າຍອດຄົງເຫຼືອເບື້ອງຕົ້ນແມ່ນ $0. T1 ເພີ່ມ $50 ໃສ່ຍອດເງິນຂອງທ່ານ. T2 ອ່ານມູນຄ່າຍອດຄົງເຫຼືອ ($50). T1 ຍົກເລີກການປ່ຽນແປງ ແລະອອກ. T2 ສືບຕໍ່ປະຕິບັດດ້ວຍຂໍ້ມູນຍອດເງິນທີ່ບໍ່ຖືກຕ້ອງ.

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

ອ່ານຊ້ຳໄດ້

ການສູນເສຍການປັບປຸງບັນຫາ. T1 ບັນທຶກການປ່ຽນແປງຢູ່ເທິງສຸດຂອງການປ່ຽນແປງຂອງ T2.

ຕົວຢ່າງ. ມູນ​ຄ່າ​ຍອດ​ເງິນ​ເບື້ອງ​ຕົ້ນ​ແມ່ນ $0 ແລະ​ສອງ​ທຸ​ລະ​ກໍາ​ພ້ອມ​ກັນ​ການ​ຕື່ມ​ຂໍ້​ມູນ​ໃສ່​ຍອດ​ເງິນ​. T1 ແລະ T2 ອ່ານຍອດເງິນຂອງ $0. T2 ຫຼັງຈາກນັ້ນເພີ່ມ $200 ເປັນ $0 ແລະບັນທຶກຜົນໄດ້ຮັບ. T1 ເພີ່ມ $100 ເປັນ $0 ແລະບັນທຶກຜົນໄດ້ຮັບ. ຜົນໄດ້ຮັບສຸດທ້າຍແມ່ນ $100 ແທນ $300.

ບັນຫາການອ່ານທີ່ບໍ່ຊ້ໍາກັນ. ການອ່ານຂໍ້ມູນດຽວກັນຊ້ຳໆຈະສົ່ງຄ່າທີ່ແຕກຕ່າງກັນ.

ຕົວຢ່າງ. T1 ອ່ານມູນຄ່າຍອດເງິນຂອງ $0. T2 ຫຼັງຈາກນັ້ນຕື່ມ $50 ກັບຍອດເງິນແລະສິ້ນສຸດ. T1 ອ່ານຂໍ້ມູນອີກເທື່ອຫນຶ່ງແລະຊອກຫາຄວາມແຕກຕ່າງກັບຜົນໄດ້ຮັບທີ່ຜ່ານມາ.

Repeatable Read ຮັບປະກັນວ່າການອ່ານເທື່ອທີສອງຈະໃຫ້ຜົນໄດ້ຮັບຄືກັນ. ຂໍ້​ມູນ​ທີ່​ອ່ານ​ໂດຍ​ການ​ໂອນ​ຫນຶ່ງ​ບໍ່​ສາ​ມາດ​ໄດ້​ຮັບ​ການ​ປ່ຽນ​ແປງ​ໃນ​ຄົນ​ອື່ນ​ຈົນ​ກ​່​ວາ​ການ​ເຮັດ​ທຸ​ລະ​ກໍາ​ສໍາ​ເລັດ​. ຖ້າທຸລະກໍາ A ໄດ້ອ່ານຊຸດຂໍ້ມູນທີ່ແນ່ນອນ, ຫຼັງຈາກນັ້ນການເຮັດທຸລະກໍາ B, ເມື່ອເຂົ້າເຖິງຂໍ້ມູນນີ້, ຖືກບັງຄັບໃຫ້ລໍຖ້າການເຮັດທຸລະກໍາ A ສໍາເລັດ.

ການ​ອ່ານ​ຄໍາ​ສັ່ງ (Serializable​)

Phantom Reads ບັນຫາ. ສອງຄໍາຖາມທີ່ເລືອກຂໍ້ມູນໂດຍອີງໃສ່ເງື່ອນໄຂສະເພາະໃດຫນຶ່ງສົ່ງຄືນຄ່າທີ່ແຕກຕ່າງກັນ.

ຕົວຢ່າງ. T1 ຮ້ອງຂໍຈໍານວນຜູ້ໃຊ້ທັງຫມົດທີ່ຍອດເງິນຫຼາຍກວ່າ $0 ແຕ່ຫນ້ອຍກວ່າ $100. T2 ຫັກ $1 ຈາກຜູ້ໃຊ້ທີ່ມີຍອດເຫຼືອ $101. T1 ອອກຄໍາຮ້ອງຂໍຄືນໃຫມ່.

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

ຜູ້ຈັດຕາຕະລາງ

ກໍານົດຄໍາສັ່ງທີ່ການດໍາເນີນງານຄວນຈະຖືກປະຕິບັດໃນລະຫວ່າງການເຮັດທຸລະກໍາຂະຫນານ.

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

ກົນໄກການຄວບຄຸມວຽກຂະຫນານ (Concurrency Control)

ແງ່ດີແມ່ນອີງໃສ່ການກວດສອບແລະແກ້ໄຂຂໍ້ຂັດແຍ່ງ, ແງ່ດີແມ່ນອີງໃສ່ການປ້ອງກັນຄວາມຂັດແຍ້ງທີ່ເກີດຂື້ນ.

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

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

ລັອກ

ຖ້າທຸລະກໍາຫນຶ່ງມີຂໍ້ມູນທີ່ຖືກລັອກ, ການເຮັດທຸລະກໍາອື່ນໆຕ້ອງລໍຖ້າຈົນກ່ວາມັນຖືກປົດລັອກເມື່ອເຂົ້າເຖິງຂໍ້ມູນ.

ບລັອກສາມາດຖືກວາງເທິງຖານຂໍ້ມູນ, ຕາຕະລາງ, ແຖວ, ຫຼືຄຸນລັກສະນະ. Shared Lock ສາມາດຖືກບັງຄັບໃຫ້ຂໍ້ມູນດຽວກັນໂດຍການເຮັດທຸລະກໍາຫຼາຍ, ອະນຸຍາດໃຫ້ທຸລະກໍາທັງຫມົດ (ລວມທັງຫນຶ່ງທີ່ imposed ມັນ) ອ່ານ, ຫ້າມການດັດແກ້ແລະການຈັບພາບສະເພາະ. Exclusive Lock ສາມາດຖືກບັງຄັບໂດຍພຽງແຕ່ຫນຶ່ງທຸລະກໍາ, ອະນຸຍາດໃຫ້ດໍາເນີນການໃດໆຂອງທຸລະກໍາ imposing, ຫ້າມການດໍາເນີນການໃດໆໂດຍຜູ້ອື່ນ.

Deadlock ແມ່ນສະຖານະການທີ່ການເຮັດທຸລະກໍາສິ້ນສຸດລົງຢູ່ໃນສະຖານະທີ່ຍັງຄ້າງຢູ່ຕະຫຼອດໄລຍະເວລາທີ່ບໍ່ມີກໍານົດ.

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

ການແກ້ໄຂ optimistic ກັບບັນຫາ deadlock ອະນຸຍາດໃຫ້ deadlock ເກີດຂຶ້ນ, ແຕ່ຫຼັງຈາກນັ້ນ recovers ລະບົບໂດຍການ rolling ກັບຄືນໄປບ່ອນຫນຶ່ງໃນທຸລະກໍາທີ່ກ່ຽວຂ້ອງກັບ deadlock.

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

ທຸກໆທຸລະກໍາ T ກຳນົດເວລາໃຫ້ TS ປະກອບມີເວລາເລີ່ມຕົ້ນຂອງທຸລະກໍາ.

ລໍຖ້າ-ຕາຍ.

ຖ້າຫາກວ່າ TS(Ti) < TS(Tj), ຫຼັງຈາກນັ້ນ, Ti ລໍຖ້າ, ຖ້າບໍ່ດັ່ງນັ້ນ Ti ມ້ວນກັບຄືນແລະເລີ່ມຕົ້ນອີກເທື່ອຫນຶ່ງດ້ວຍການປະທັບຕາເວລາດຽວກັນ.

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

ບາດແຜລໍຖ້າ.

ຖ້າຫາກວ່າ TS(Ti) < TS(Tj), ຫຼັງຈາກນັ້ນ, Tj ມ້ວນກັບຄືນແລະເລີ່ມຕົ້ນອີກເທື່ອຫນຶ່ງດ້ວຍການປະທັບຕາເວລາດຽວກັນ, ຖ້າບໍ່ດັ່ງນັ້ນ Ti ລໍຖ້າ.

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

ການແກ້ໄຂບັນຫາທີ່ໜ້າເສຍດາຍຕໍ່ກັບບັນຫາ deadlock ບໍ່ອະນຸຍາດໃຫ້ທຸລະກຳເລີ່ມປະຕິບັດໄດ້ ຖ້າມີຄວາມສ່ຽງຕໍ່ການເກີດການລັອກ.

ເພື່ອກວດຫາການຢຸດຊະງັກ, ກຣາຟຖືກສ້າງຂຶ້ນ (ກາຟລໍຖ້າ, ຕາຕະລາງລໍຖ້າ), ຈຸດຍອດຂອງການເຮັດທຸລະກໍາ, ແລະຂອບແມ່ນມຸ້ງມາຈາກການເຮັດທຸລະກໍາລໍຖ້າການປ່ອຍຂໍ້ມູນໄປຫາທຸລະກໍາທີ່ໄດ້ເກັບກໍາຂໍ້ມູນນີ້. ການຢຸດຊະງັກແມ່ນຖືວ່າເກີດຂຶ້ນຖ້າກຣາຟມີ loop. ການສ້າງຕາຕະລາງລໍຖ້າ, ໂດຍສະເພາະໃນຖານຂໍ້ມູນທີ່ແຈກຢາຍ, ແມ່ນຂັ້ນຕອນທີ່ມີລາຄາແພງ.

ການລັອກສອງເຟດ - ປ້ອງກັນການປິດທ້າຍໂດຍການຍຶດເອົາຊັບພະຍາກອນທັງຫມົດທີ່ໃຊ້ໂດຍການເຮັດທຸລະກໍາໃນຕອນເລີ່ມຕົ້ນຂອງທຸລະກໍາແລະປ່ອຍພວກມັນໃນທ້າຍ.

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

ຄໍາຫມັ້ນສັນຍາສອງໄລຍະຮັບປະກັນວ່າຄໍາຫມັ້ນສັນຍາຖືກປະຕິບັດຢູ່ໃນທຸກຖານຂໍ້ມູນ replicas

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

ວິທີການສະແຕມເວລາ

ທຸລະກຳທີ່ເກົ່າກວ່າຈະຖືກມ້ວນຄືນເມື່ອພະຍາຍາມເຂົ້າເຖິງຂໍ້ມູນທີ່ກ່ຽວຂ້ອງກັບທຸລະກຳທີ່ໜຸ່ມກວ່າ

ແຕ່ລະທຸລະກໍາຖືກມອບຫມາຍເວລາ TS ທີ່ສອດຄ້ອງກັນກັບເວລາເລີ່ມຕົ້ນຂອງການປະຕິບັດ. ຖ້າ Ti ເກົ່າກວ່າເກົ່າ Tj, ຫຼັງຈາກນັ້ນ, TS(Ti) < TS(Tj).

ເມື່ອທຸລະກໍາຖືກມ້ວນຄືນ, ມັນຖືກມອບຫມາຍເວລາໃຫມ່. ແຕ່ລະວັດຖຸຂໍ້ມູນ Q ມີສ່ວນຮ່ວມໃນການເຮັດທຸລະກໍາຖືກຫມາຍດ້ວຍສອງປ້າຍ. W-TS(Q) — ສະແຕມເວລາຂອງທຸລະກຳທີ່ນ້ອຍທີ່ສຸດທີ່ເຮັດສຳເລັດການບັນທຶກ Q. R-TS(Q) — ສະແຕມເວລາຂອງທຸລະກໍາທີ່ນ້ອຍທີ່ສຸດທີ່ເຮັດການບັນທຶກການອ່ານ Q.

ເມື່ອທຸລະກໍາ T ຮ້ອງຂໍໃຫ້ອ່ານຂໍ້ມູນ Q ມີສອງທາງເລືອກ.

ຖ້າຫາກວ່າ TS(T) < W-TS(Q), ນັ້ນແມ່ນ, ຂໍ້ມູນໄດ້ຖືກປັບປຸງໂດຍການເຮັດທຸລະກໍາທີ່ອ່ອນກວ່າ, ຫຼັງຈາກນັ້ນການເຮັດທຸລະກໍາ T ມ້ວນຄືນ.

ຖ້າຫາກວ່າ TS(T) >= W-TS(Q), ຫຼັງຈາກນັ້ນການອ່ານແມ່ນປະຕິບັດແລະ R-TS(Q) ກໍາລັງກາຍເປັນ MAX(R-TS(Q), TS(T)).

ເມື່ອທຸລະກໍາ T ຮ້ອງຂໍການປ່ຽນແປງຂໍ້ມູນ Q ມີສອງທາງເລືອກ.

ຖ້າຫາກວ່າ TS(T) < R-TS(Q), ນັ້ນແມ່ນ, ຂໍ້ມູນໄດ້ຖືກອ່ານແລ້ວໂດຍການເຮັດທຸລະກໍາທີ່ອ່ອນກວ່າແລະຖ້າມີການປ່ຽນແປງ, ຄວາມຂັດແຍ້ງຈະເກີດຂື້ນ. ທຸລະກໍາ T ມ້ວນຄືນ.

ຖ້າຫາກວ່າ TS(T) < W-TS(Q), ນັ້ນແມ່ນ, ການເຮັດທຸລະກໍາພະຍາຍາມຂຽນທັບມູນຄ່າໃຫມ່ກວ່າ, ການເຮັດທຸລະກໍາ T ຖືກມ້ວນຄືນ. ໃນກໍລະນີອື່ນໆ, ການປ່ຽນແປງແມ່ນດໍາເນີນແລະ W-TS(Q) ກາຍ​ເປັນ​ເທົ່າ​ທຽມ​ກັນ​ TS(T).

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

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

Thomas ຂຽນກົດລະບຽບ - ການປ່ຽນແປງຂອງວິທີການກໍານົດເວລາທີ່ຂໍ້ມູນທີ່ປັບປຸງໂດຍການເຮັດທຸລະກໍາທີ່ມີອາຍຸນ້ອຍແມ່ນຫ້າມບໍ່ໃຫ້ຂຽນທັບໂດຍຜູ້ສູງອາຍຸ.

ທຸລະກໍາ T ຮ້ອງຂໍການປ່ຽນແປງຂໍ້ມູນ Q. ຖ້າ TS(T) < W-TS(Q), ນັ້ນແມ່ນ, ການເຮັດທຸລະກໍາພະຍາຍາມຂຽນທັບມູນຄ່າໃຫມ່ກວ່າ, ການເຮັດທຸລະກໍາ T ບໍ່ໄດ້ຖືກມ້ວນຄືນຄືກັບວິທີການເວລາ.

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