Rutgers University – CS 417: Distributed Systems V3.3 ©1999-2009 Paul Krzyzanowski! ! 1 Lectures on distributed systems Concurrency Control Paul Krzyzanowski Introduction When!discussing!transac tions,!we!alluded !to!schedules,!or!valid!orders!of!execution.!We!can! play!it!safe!and!use!mu tual! exclusion!on!a!transaction!level!to !ensure!that!only !one!transaction!is!ex ecuting!at!any!ti me.!However,!this!is!usually!overkill!a nd!does! not!allow!us!take!advantage!of!the!concur rency!that!we!may!get!in!distributed!systems.!What! we!would!re ally!like!is!to !allo w!multiple!transactions!to!execute!simultaneously!but!keep!them!out!of!each!other’s!way!and!ensure!serializability.!This!is!called!concurre ncy(control.!!Locking One!mechanism!that!we!can! use!to!seriali ze!transactio ns!is!the!excl usive!lock!on!a!resource.!A!process!will!lock!any!dat a!that!is!about!to!be!used!on!behalf!of!the!transacti on.!Reso urce!locking!in!a!distributed!system!can!be!im plemented!with!a!lock*manag er.!T his!is!the!same!as!the!cen tralized!implementation!for!mutual!e xclusion.!One!process!serves!as!a!lock!manager.!Processes!request!a!lock!for!a!resource!(e.g.,!a!file!or!a!shared! data !object)!and!then !they!either!are!granted!a!lock!or! wait !for!it!to!be!grante d!when!another!process!releases!it.!!This!for m!of!locking!is!clearly!suboptimal :!the re!is !nothing!wrong!with! havi ng!sever al!transactions!read!the!same!object!concurr ently!as!long!as!none!of!them!modify!it.!Locking!can!be!optimized!to!yield!better!resource!usage!by!distinguishing!read*locks!from!write*locks.!If!a!proces s!imposes!a!read!lock!on! a!resour ce,!other!processes!will!still!be!able!to !request!read!locks!on!that!resour ce.!However,!a!request!for!a!write!lock!would!fail!(or!be!blocked)1.!If!a!process!impose s!a!write!lock!on!a!re source,!then!neither!read!nor!write!locks!will!be!granted!until !that!process!releases!the!resource.!Another!consideration!in!resourc e!locking!is!the!granularity!of!the!lock.!Quite!often,!there!is!no!need!to!lock!an!enti re!file.!More! parallelism!may!!!ach ieved!with!a! finer!granularity!of!locking!(a !span!of! byte s!or!a!record).!This!is!parti cularly!important!with!databases,!where!a!transac tion!is!better !off!obtaining!locks!for!the!rec ords!it!is!manipu latin g!rather!than!the !enti re!database.!!Getting!and!releasing!locks!precisely!can!be!tricky .!Done!improperly,!it!can!lead!to!inconsistency!and /or!deadlocks.!We!need!t o!en sure!that !a!transaction!can!always!commit!without!violating!the !seri alizability!invaria nt.!F or!transactions!to!be!serial,!all!access!to!data!must !be!serialized!with!respect! to!accesses!by!other!transacti ons.!To!ensu re!that!confli cting!operati ons!of!multiple!transactions!are!executed!in!the!same!order,!a!restriction!is!imposed:!a *transaction* is*not*allowed*to*obtain*new*l ocks*once*it*has*r eleased*a*lock.!Th is!re stric tion!is!called!two,phase(locking.!The!first!pha se!is !known!as!the!growing!phase, !in!which!a!transaction!acquires!all!the!locks!it!needs.!The!second!phase!is! known!as!the!shrinking!phase,!where! the!process!releases!the!l ocks.!If!a!process!fails!to!a cquire!all!the!locks!during!the!firs t!phase,!then !it!is!obligated!to!release!all!of!them,!wait,!and! start!over.!It!has!been!proved!(Eswaren,!et!al.,!1976)!that!if!all!trans actions!use!two‐phase!locking,!then!all!schedules!formed!by!interleaving!them!are!serializable.!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1!This!is!similar!to!DFS!and!its!use !of!tokens!in!granting!file!access! permissions.!Concurrency Control Rutgers University – CS 417: Distributed Systems V3.3 ©1999-2009 Paul Krzyzanowski ! 2 To!ensure!that!a!transaction! not!access!data!until!anot her!transacti on!that!was!man ipulating!the! data !has!either!committed!or!aborted,!locks!may!be!held!until!t he!transaction!commits!or!aborts .!This!is!known!as!strict( two,phase(l ocking.!This!is!similar!to!two‐phase!locking!except!that!in!t his!case,!the!shrinking!phase!takes!place!during!the!commit!or!abo rt.!O ne!effect !of!strict!two‐phase!locking!is! that!by!placing!the!second!ph ase!at!the!end!of!a!transaction,!all!lock!acquisitions!and!releases!can!be!han dled !by!t he!system!without!th e!transaction's!knowledge.!!Optimistic concurrency control Locking!is!not!without!problems.!Locks!have!an!overhead!associated!with! maintaining!and!checking!them.!They!may!induce!dead lock!in!a!system!and!locking!also!may!reduce!concurrency!in!a!syst em!by!having!t ransactions!hold!on!t o!locks!longer!than!n eeded!(as!in! strict!two‐phase!locking).!An!alternative!proposed!by!Kung!and!Robinson!in!19 81!is!optimistic(concurrency(contro l,!which!tells!the! transaction!to!just!go !ahead!and!do!what!it!has!to!do!witho ut!worrying!about!w hat!someone!else!is!doing.!In!most!applications,!the!chance! of!two!transactions!accessing !the! same!data!is!low,!so!why!induce!overhead?!W hen! a!conflict!does!arise,!then !the! system!will!have!to!deal!with!it.!!Optimistic!concurrency!control!requires!t ransactions!to!operate!in!a!private!workspace ,!so!their!modifications!ar e!no t!visible!to!other! until!they!commi t.!When!a!transaction!is!ready!to!commit,!a!validation!is!performed!on!all!the!data!items!t o!see!whether!th e!data!conflicts!with!operations!of!other!transactions.!If!the!validation!fails,!then! the!transacti on!will!have! to!be!aborted!and!restart ed!later!(again,!opti mist ically!hoping!for!no!conflicts). !Optimistic!control!is!clearly!dead lock!free!(no!locking!or!waiting!on!resources)!and!allows!for!maximum!parallel ism! (since!no!process!has!to!wait !for!a!loc k,!all!can!execute!in!paral lel).!!Timestamps Another!approach!to!concurrency!control!is!the!use!of!timestamp( ordering,!developed!by!Reed!in!1983.!In!this!algorithm,!we!assign!a!ti mestamp!to!a!transaction!wh en!it !beg ins.!The! timestamp!has!to!be!unique!with!respect!to!the!timesta mps !of!other!transactions!(this!is!easily!ac com plished;!for!example,!Lamport's! algorithm!can!be !used).!E very!file!(obj ect)! in!the!system!has!a!re ad!and!a !write!timestamp!associated!wi th!it!(two!timestamps!per!object)! telling!w hich!committed!transaction!last!read!it!and!which!committed!transaction!l ast!wrote!it.!Normally,!when!a!process!tries!to !access!a!file, !the! file's!rea d!an d!write!t imestamps!will!be!older!than!the!curr ent!transaction's.!Thi s!im plies!good*ordering.!If!this!i s!not!the!case,!and!the!ordering!is !incorrect,!th