Concurrency Control Techniques PDF

Chapter Three: Concurrency Control Techniques  Concurrency Control is the process of managing simultaneous operations on the database without having them interfere with one another.  Prevents interference when two or more users are accessing database simultaneously an...

Chapter Three: Concurrency Control Techniques  Concurrency Control is the process of managing simultaneous operations on the database without having them interfere with one another.  Prevents interference when two or more users are accessing database simultaneously and at least one is updating data.  Although two transactions may be correct in themselves, interleaving of operations may produce an incorrect result.  Three basic concurrency control techniques:  Locking methods  Time stamping  Optimistic 1 Concurrency Control Techniques 12/30/2024 Cont.  Locking and Time stamping are pessimistic approaches since they delay transactions.  Both Locking and Time stamping are conservative approaches: delay transactions in case they conflict with other transactions.  The optimistic approach allows us to proceed and check conflicts at the end.  Optimistic methods assume conflict is rare and only check for conflicts at commit. 2 Concurrency Control Techniques 12/30/2024 Locking Method  The locking method is a mechanism for preventing simultaneous access on a shared resource for a critical operation  A LOCK is a mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution.  Locks are one way of enforcing concurrency control policies.  Transaction uses locks to deny access to other transactions and so prevent incorrect updates.  Lock prevents another transaction from modifying item or even reading it, in the case of a write lock. 3 Concurrency Control Techniques 12/30/2024 Cont..  Lock (X): If a transaction T1 applies Lock on data item X, then X is locked and it is not available to any other transaction.  Unlock (X): T1 Unlocks X. X is available to other transactions. 4 Concurrency Control Techniques 12/30/2024  Types of lock  Shared lock: A Read operation does not change the value of a data item. Hence a data item can be read by two different transactions simultaneously under share lock mode. So only to read a data item T1 will do: Share lock (X), then Read (X), and finally Unlock (X).  Exclusive lock: A write operation changes the value of the data item. Hence two write operations from two different transactions or a write from T1 and a read from T2 are not allowed. A data item can be modified only under Exclusive lock. To modify a data item T1 will do: Exclusive lock (X), then Write (X) and finally Unlock (X). 5 Concurrency Control Techniques 12/30/2024 Cont.  When these locks are applied, then a transaction must behave in a special way.  This special behavior of a transaction is referred to as well-formed.  Well-formed: A transaction is well- formed if it does not lock a locked data item and it does not try to unlock an unlocked data item.  Locking - Basic Rules  If transaction has a shared lock on an item, it can read but not update the item. 6 Concurrency Control Techniques 12/30/2024 Locking - Basic Rules….  If a transaction has an exclusive lock on an item, it can both read and update the item.  Reads cannot conflict, so more than one transaction can hold shared lock simultaneously on same item. 7 Concurrency Control Techniques 12/30/2024 Cont.  Exclusive lock gives transaction exclusive access to that item.  Some systems allow transaction to upgrade a shared lock to an exclusive lock, or vice-versa.  Examples: T1 and T2 are two transactions. They are executed under locking as follows. T1 locks A in exclusive mode. When T2 want s to lock A, it finds it locked by T1 so T2 waits for Unlock on A by T1. When A is released then T2 locks A and begins execution.  Suppose a lock on a data item is applied, the data item is processed and it is unlocked immediately after reading/writing is completed as follows.  Initial values of A = 10 and B = 20. 8 Concurrency Control Techniques 12/30/2024 9 Concurrency Control Techniques 12/30/2024 Cont.  The final result of the two transactions using the two types of transaction execution (serial and concurrent) is not the same.  This indicates that the above method of locking and unlocking is not correct.  This is because although such kind of locking and unlocking data items increases the concurrency of execution it violates the isolation and atomicity of transactions.  Immediate unlocking is not trustworthy.  Thus, to preserve consistency we have to use another approach to locking, two-phase locking scheme. 10 Concurrency Control Techniques 12/30/2024 Two-Phase Locking (2PL)  A transaction follows 2PL protocol if all locking operations precede the first unlock operation in the transaction.  The 2PL protocol demands locking and unlocking of a transaction to have two phases.  Growing phase - acquires all locks but cannot release any locks. Upgrading of shared lock to exclusive locks is done here if allowed.  Shrinking phase - releases locks but cannot acquire any new locks. Down grading of exclusive locks to shared lock is done here if allowed.  Hence the 2PL protocol allows avoiding the three problems of concurrent execution.  11 Concurrency Control Techniques 12/30/2024 Cont.  Locking methods: problems  Deadlock: A deadlock that may result when two (or more) transactions are each waiting for locks held by the other to be released.  Deadlock - possible solutions  Only one way to break deadlock: abort one or more of the transactions in the deadlock.  Deadlock should be transparent to user, so DBMS should restart transaction(s).  Two general techniques for handling deadlock:  Deadlock prevention. 12 Concurrency Control Techniques 12/30/2024 Cont.  Deadlock detection and recovery.  Timeout  The deadlock detection could be done using the technique of TIMEOUT.  Every transaction will be given a time to wait in case of deadlock.  If a transaction waits for the predefined period of time in idle mode, the DBMS will assume that deadlock occurred and it will abort and restart the transaction. 13 Concurrency Control Techniques 12/30/2024 Time-stamping Method  Timestamp: a unique identifier created by DBMS that indicates relative starting time of a transaction.  Can be generated by:  using system clock at the time transaction started, or  Incrementing a logical counter every time a new transaction starts.  Time-stamping  a concurrency control protocol that orders transactions in such a way that older transactions, transactions with smaller time stamps, get priority in the event of conflict.  Transactions ordered globally base do their timestamp so that older transactions, transactions with earlier timestamps, get priority in the event of conflict. 14 Concurrency Control Techniques 12/30/2024 Cont.  Conflict is resolved by rolling back and restarting transaction.  Since there is no need to use lock there will be No Deadlock.  In timestamp ordering, the schedule is equivalent to the particular serial order that corresponds to the order of the transaction timestamps.  To implement this scheme, every transaction will be given a timestamp which is a unique identifier of a transaction.  If Ti came to processing prior to Tj then TS of Tj will be larger than TS of Ti.  Again each data item will have a timestamp for Read and Write. 15 Concurrency Control Techniques 12/30/2024 Cont.  WTS(A) which denotes the largest timestamp of any transaction that successfully executed Write(A)  RTS(A) which denotes the largest timestamp of any transaction that successfully executed Read(A)  These timestamps are updated whenever a new Read (A) or Write (A) instruction is executed.  The timestamp ordering protocol ensures that any conflicting read and write operations are executed in the timestamp order.  The protocol manages concurrent execution such that the time-stamps determine the serializability order. 16 Concurrency Control Techniques 12/30/2024 Rules for permitting execution of operations in Time-stamping Method  Suppose that Transaction Ti issues Read(A)  If TS(Ti) < WTS(A): this implies that Ti needs to read a value of A which was already overwritten. Hence the read operation must be rejected and Ti is rolled back.  If TS(Ti) >= WTS(A): then the read is executed and RTS(A) is set to the maximum of RTS(A) and TS(Ti).  Suppose that Transaction Ti issues Write(A)  If TS(Ti) < RTS(A): then this implies that the value of A that Ti is producing was previously needed and it was assumed that it would never be produced.  Hence, the Write operation must be rejcted and Ti is rolled back. 17 Concurrency Control Techniques 12/30/2024 Cont.  If TS(Ti) < WTS(A): then this implies that Ti is attempting to Write an object value of A. hence, this write operation can be ignored.  Otherwise the Write operation is executed and WTS(A) is set to the maximum of WTS(A) or TS(Ti).  A transaction that is rolled back due to conflict will be restarted and be given a new timestamp. 18 Concurrency Control Techniques 12/30/2024  Optimistic Technique  Locking and assigning and checking timestamp values may be unnecessary for some transactions  Assumes that conflict is rare.  When transaction reaches the level of executing commit, a check is performed to determine whether conflict has occurred. If there is a conflict, transaction is rolled back and restarted.  Based on assumption that conflict is rare and more efficient to let transactions proceed without delays to ensure serializability.  At commit, check is made to determine whether conflict has occurred.  If there is a conflict, transaction must be rolled back and restarted.  Potentially allows greater concurrency than traditional protocols. 19 Concurrency Control Techniques 12/30/2024 Cont.  Three phases:  Read  Validation  Write  Optimistic Techniques - Read Phase  Extends from start until immediately before commit.  Transaction reads values from database and stores them in local variables. Updates are applied to a local copy of the data. 20 Concurrency Control Techniques 12/30/2024 Cont.  Optimistic Techniques - Validation Phase  Follows the read phase.  For read-only transaction, checks that data read are still current values. If no interference, transaction is committed, else aborted and restarted.  For update transaction, checks transaction leaves database in a consistent state, with serializability maintained.  Optimistic Techniques - Write Phase  Follows successful validation phase for update transactions.  Updates made to local copy are applied to the database. 21 Concurrency Control Techniques 12/30/2024  Granularity of data items  Granularity is the size of the data items chosen as the unit of protection by a concurrency control protocol.  It could be:  The entire database  A file  A page (a section of physical disk in which relations are stored)(sometimes also called a block)  A record  A field value of a record 22 Concurrency Control Techniques 12/30/2024 Cont.  The granularity has effect on the performance of the system.  As locking will prevent access to the data, the size of the data required to be locked will prevent other transactions from having access.  If the entire database is locked, then consistency will be highly maintained but less performance of the system will be witnessed.  Is a single data item is locked; consistency maybe at risk but concurrent processing and performance will be enhanced.  Thus, as one go from the entire database to a single value, performance and concurrent processing will be enhanced but consistency will be at risk and needs good concurrency control mechanism and strategy. 23 Concurrency Control Techniques 12/30/2024 24 Concurrency Control Techniques 12/30/2024  Transaction Subsystem  Transaction Subsystem  Transaction manager  Scheduler  Recovery manager  Buffer manager  Transaction Manager in DBMS coordinates transactions on behalf of application programs. Communicates with scheduler (lock manager) which is responsible for implementing a strategy for concurrency control.  The Scheduler in the DBMS ensures that the individual steps of different transactions preserve consistency. 25 Concurrency Control Techniques 12/30/2024 Cont.  Recovery Manager: Ensures that database is restored to the original state in case failure occurs.  Buffer Manager: responsible for transfer of data between disk storage and main memory. 26 Concurrency Control Techniques 12/30/2024 Using locks for concurrency control indexes  Two-phase locking can also be applied to indexes ,where the nodes of an index correspond to disk pages.  However, holding locks on index pages until the shrinking phase of 2PL could cause an undue amount of transaction blocking because searching an index always starts at the root.  Therefore, if a transaction wants to insert a record (write operation), the root would be locked in exclusive mode, so all other conflicting lock requests for the index must wait until the transaction enters its shrinking phase.  This blocks all other transactions from accessing the index, so in practice other approaches to locking an index must be used. 27 Concurrency Control Techniques 12/30/2024 28 Concurrency Control Techniques 12/30/2024 Cont.  The tree structure of the index can be taken advantage of when developing a concurrency control scheme.  For example, when an index search (read operation) is being executed, a path in the tree is traversed from the root to a leaf.  Once a lower level node in the path has been accessed, the higher-level nodes in that path will not be used again.  So once a read lock on a child node is obtained, the lock on the parent can be released. 29 Concurrency Control Techniques 12/30/2024 Cont.  When an insertion is being applied to a leaf node (that is, when a key and a pointer are inserted), then a specific leaf node must be locked in exclusive mode.  However, if that node is not full, the insertion will not cause changes to higher-level index nodes, which implies that they need not be locked exclusively.  A conservative approach for insertions would be to lock the root node in exclusive mode and then to access the appropriate child node of the root.  If the child node is not full, then the lock on the root node can be released. 30 Concurrency Control Techniques 12/30/2024  Thank You!!! 31 Concurrency Control Techniques 12/30/2024