Two Major Issues of Lock Usage.Waysof acquiringlocks:Minimizing network bandwidth:Minimizing overhead of waiting for locks:Maintaining a constant # of remote memory accesses per lockacquisition.Locksinconcurrencycontrol·Minimizing oreliminating unnecessary usage of locks·Minimizing execution and access latency inside critical section· Minimizing the size of the data structure to be locked·Maximizing scalability subject to serialized execution
Two Major Issues of Lock Usage • Ways of acquiring locks • Minimizing network bandwidth • Minimizing overhead of waiting for locks • Maintaining a constant # of remote memory accesses per lock acquisition • Locks in concurrency control • Minimizing or eliminating unnecessary usage of locks • Minimizing execution and access latency inside critical section • Minimizing the size of the data structure to be locked • Maximizing scalability subject to serialized execution 6
Distributed locks in production systemsFor each lock acquisition ina distributed system1. Entering the queue waiting for the lock (a remote access)2. Local spin to wait without consuming network bandwidth3. The process is informed for its turn (a remote access)4. Acquiring the lock entering the critical section (a remoteaccess).Constant number of remote accesses perlock acguisition:Network contention is minimized
Distributed locks in production systems For each lock acquisition in a distributed system 1. Entering the queue waiting for the lock (a remote access) 2. Local spin to wait without consuming network bandwidth 3. The process is informed for its turn (a remote access) 4. Acquiring the lock entering the critical section (a remote access) • Constant number of remote accesses per lock acquisition • Network contention is minimized 7
Two Phase Locking (2PL)·DBMsmustlockatuplebeforeatransactionreadsorwritesto it: Two types of locks: shared lock (read) & exclusive lock (write):Phase1:growingphase.Transaction can obtainlocksbut cannotreleaselocks.Phase2:Shrinkingphase.Transactioncanreleaselocksbutcannotobtainlocks.Variants of 2PL (based on how to avoid deadlocks):2PL-deadlockdetecfion:Abortsatransactionwhendeadlockhappens2PL-waitanddie.Oldtransactioncanwaityoungtransaction,notviceversa.2PL-woundwait:Immediatelyaborts atransactionifitslockingreguestis denied
Two Phase Locking (2PL) • DBMS must lock a tuple before a transaction reads or writes to it • Two types of locks: shared lock (read) & exclusive lock (write) • Phase 1: growing phase • Transaction can obtain locks but cannot release locks • Phase 2: Shrinking phase • Transaction can release locks but cannot obtain locks • Variants of 2PL (based on how to avoid deadlocks) • 2PL - deadlock detection • Aborts a transaction when deadlock happens • 2PL - wait and die • Old transaction can wait young transaction, not vice versa • 2PL – wound wait • Immediately aborts a transaction if its locking request is denied 8
Concurrency Control (CC).CC ensurescorrectresultsforconcurrentoperations·AbasiccomponentinOs,Ds,multiprocessors,databases,PL:Ensures serializability of data accesses to the shared data sets.Get results fast for high throughput and scalability·Optimistic Concurrency Control (OCC, Kung and Johnson,1981) has been used in several production systems: E.g., Microsoft Hekaton, Google App Engine, CoucDB, Silo,
Concurrency Control (CC) • CC ensures correct results for concurrent operations • A basic component in OS, DS, multiprocessors, databases, PL, . • Ensures serializability of data accesses to the shared data sets • Get results fast for high throughput and scalability • Optimistic Concurrency Control (OCC, Kung and Johnson, 1981) has been used in several production systems • E.g., Microsoft Hekaton, Google App Engine, CoucDB, Silo, . 9
Occ: How It Works.OCC executes g transaction in three phases:.Phase1:concurrentlocalprocessing:Reads tuples into aread set.Buffers writes into a write set.Phase 2:Validation in critical section.Validates whether serializability is guaranteed:Has any tuple in the read set been modified?.Phase 3:Commit the results in critical section or abort:Aborts: aborts the transaction if validationfails. Commits: installs the write set and commits thetransaction10
• OCC executes a transaction in three phases: • Phase 1: concurrent local processing • Reads tuples into a read set • Buffers writes into a write set • Phase 2: Validation in critical section • Validates whether serializability is guaranteed: Has any tuple in the read set been modified? • Phase 3: Commit the results in critical section or abort • Aborts: aborts the transaction if validation fails • Commits: installs the write set and commits the transaction OCC: How It Works 10