Chapter 4.pdf

Chapter Four Concurrency Control Techniques Chapter Four: Concurrency Control 1  Outlines At the end of the session the students will be able to:- Define the concept of Concurrency control Understand different concurrency control te...

Chapter Four Concurrency Control Techniques Chapter Four: Concurrency Control 1  Outlines At the end of the session the students will be able to:- Define the concept of Concurrency control Understand different concurrency control techniques Differentiate the Granularity Level Discuss different types of Locking Discuss what does mean the concurrency control Timestamp Ordering Discuss what does mean the Multi-version Concurrency control Chapter Four: Concurrency Control 2  Introduction ❖Concurrency Control in Database Management System is a procedure of managing simultaneous operations without conflicting with each other. ❖It ensures that Database transactions are performed concurrently and accurately to produce correct results without violating data integrity of the respective Database. ❖Advantage of using concurrency ✓Increased performance for CPU and storage ✓Increase Resource utilization ✓Decrease waiting time Chapter Four: Concurrency Control 3  Cont… ❑Concurrency control techniques are those techniques used to ensure the isolation property of concurrently executing transactions. ❑Most of the techniques ensure serializability of schedules by using protocols that guarantees serializability. ❑Some of the main techniques used to control concurrent execution of transactions are based on the concept of locking data items. ❑Concurrency control coordinates the simultaneous execution of transactions. ❑The concurrent execution of transactions can result in three main problems: ✓lost updates ✓uncommitted data, ✓and inconsistent retrievals. Chapter Four: Concurrency Control 4  Cont… ❖The scheduler is responsible for establishing the order in which the concurrent transaction operations are executed. ❖The transaction execution order is critical and ensures database integrity in multiuser database systems. ❖If transactions are being executed by two or more different users there should be concurrency control mechanism to ensure the isolation and consistency of the given transaction. ❖The three fundamental techniques(protocols) used to control the concurrency of the transactions. ✓Locking ✓Time stamp techniques ✓Multi-version 5 Chapter Four: Concurrency Control  Locking the data item Ensure the isolation property of concurrently executing transactions the data used during the execution of a transaction cannot be used by a second transaction until the first one is completed. A lock is a variable associated with a data item that describes the status of the item with respect to possible operations that can be applied to it. Each data item in the database is associated with one lock. A transaction acquires a lock prior to data access; the lock is released (unlocked) when the transaction is completed so that another transaction can lock the data item for its exclusive use. Chapter Four: Concurrency Control 6  Lock Granularity ❖Indicates the portions of the database objects to be locked ❖Database Level locking ✓The entire database is locked, thus preventing the use of any tables in the database by transaction T2 while transaction Tl is being executed. ✓This level of locking is unsuitable for multiuser DBMSs ✓Slow data access time ✓Even if the transactions are referring different tables T2 cannot access the database item until transaction one completes its execution. Chapter Four: Concurrency Control 7 Chapter Four: Concurrency Control 8  Lock Granularity Table Level Lock The entire table is locked Prevent access to any row by transaction T2 while transaction T1 is using the table. T2 must wait until T1 unlocks the table. Two transactions can access the same database as long as they access different tables. Better access time than DBL(Database level) but still it is not suitable in multiuser DB environment as it can cause the traffic jam when many transactions are in a waiting state. Chapter Four: Concurrency Control 9 Chapter Four: Concurrency Control 10  Lock Granularity Page Level lock:-The DBMS will lock an entire disk page Disk page a directly addressable section of a disk Currently the most frequently used multiuser DBMS locking method Chapter Four: Concurrency Control 11  Lock Granularity Row Level:-A row-level lock is much less restrictive than other lock ✓The DBMS allows concurrent transactions to access different rows of the same table even when the rows are located on the same page. ✓Although the row-level locking approach improves the availability of data, its management requires high overhead because a lock exists for each row in a table of the database involved in a conflicting transaction. ✓Modern DBMSs automatically changes a lock from a row-level to a page-level lock when the application session requests multiple locks on the same page. Chapter Four: Concurrency Control 12 Row Level Lock Chapter Four: Concurrency Control 13  Types of locking protocol Simple locking Two phase locking ✓Simple 2 phase locking ✓Conservative 2 phase locking ✓Strict 2 phase locking ✓Regressive 2 phase locking Graph based locking Chapter Four: Concurrency Control 14  Simple Types of Locks Binary Locks:-Has only two states/values: locked (1) or unlocked (0) ✓If an object that is, a database, table, page, or row is locked by a transaction, no other transaction can use that object. ✓If an object is unlocked, any transaction can lock the object for its use Two operations, lock_item and unlock_item, are used with binary locking. ✓A transaction requests access to an item X(either for reading or writing) by first issuing a lock_item(X) operation. ✓If LOCK(X) =1, the transaction is forced to wait. If LOCK(X) = 0, it is set to 1 (the transaction locks the item) and the transaction is allowed to access item X. ✓When the transaction completed using the item, it issues an unlock_item(X) operation, which sets LOCK(X) back to 0 (unlocks the item) so that X may be accessed by other transactions. Chapter Four: Concurrency Control 15  Shared/Exclusive Locks (Read/Write Locks) The labels “shared” and “exclusive” indicate the nature of the lock An exclusive lock exists when access is reserved specifically for the transaction that locked the object. A shared lock exists when concurrent transactions are granted read access on the basis of a common lock A shared lock produces no conflict as long as all the concurrent transactions are read-only. There are three locking operations: read_lock(X), write_lock(X), and unlock(X). A read-locked item is also called share-locked because other transactions are allowed to read the item, whereas a write-locked item is called exclusive-locked because a single transaction exclusively holds the lock on the item. Chapter Four: Concurrency Control 16  Cont.… The exclusive lock is granted if and only if no other locks are held on the data item. Upgrading:-Convert the lock from shared to exclusive by issuing write_lock(X) after its read_lock(X). The transaction must be the only one has the read lock or it must wait. Downgrading: -Convert the lock from exclusive to shared by issuing read_lock(X) after the write_lock(X). ❑Locks Prevent Data Inconsistencies, But They Can Lead To Two Major Problems: ✓The resulting transaction schedule might not be serializable. ✓The schedule might create deadlocks. (A deadlock occurs when two transactions wait indefinitely for each other to unlock data. ) Chapter Four: Concurrency Control 17  Two-Phase Locking (2PL) to Ensure Serializability If every transaction in a schedule follows the two phase locking protocol, the schedule is guaranteed to be serializable A transaction is said to follow the 2PL protocol if all locking operations comes before the first unlock operation of the transaction. The transaction is divided into two phases: ✓Growing or Expanding phase:- where new locks can be issued and none can be released. Once all locks have been acquired, the transaction is in its locked point. ✓Shrinking phase:-where existing locks can be released and cannot obtain any new lock. Chapter Four: Concurrency Control 18  T1 T2 read_lock(Y); read_lock(X); read_item(Y); read_item(X); write_lock(X); write_lock(Y); unlock(Y); unlock(X); read_item(X); read_item(Y); X:=X+Y; Y:=X+Y; write_item(X); write_item(Y); unlock(X): unlock(Y); Chapter Four: Concurrency Control 19  Cont… Conservative 2PL: ✓Requires a transaction to lock all the items it accesses before the transaction begins execution Strict 2PL ✓It requires that a transaction T does not release any of its exclusive locks until it commits or aborts. Rigorous 2PL ✓It requires that a transaction T does not release any of its locks (shared or exclusive) until it commits or aborts. Deadlock:-occurs when two transactions wait indefinitely for each other to unlock data. ✓ T1 = access data items X and Y ✓ T2 = access data items Y and X Chapter Four: Concurrency Control 20  Cont.. ❖A deadlocks are possible only when one of the transactions wants to obtain an exclusive lock on a data item; no deadlock condition can exist among shared locks. ❖The three basic techniques to control deadlocks ✓ Deadlock Prevention Protocols. ✓ Deadlock Detection Protocols. ✓ Timeouts. Deadlock Prevention Protocols ✓ Using the conservative 2PL :-locking all the data items before starting the execution ✓ Using the concept of transaction Timestamps ✓ No waiting Protocols (NW) ✓ Cautious waiting Protocol. Chapter Four: Concurrency Control 21  Deadlock Prevention Protocols Transaction Timestamps It is used to decide if the transaction involved in a deadlock situation should wait, abort or preempt(block) another transaction. The timestamp of a transaction T is TS(T) which is a unique identifier assigned to the transaction T and is based on the order in which the transaction T is started. If T1 started before T2, then TS(T1) < TS(T2) Wound-Wait: If TS(Ti) < TS(Tj), then abort Tj (Ti wounds Tj ) and restart it later with the same timestamp; otherwise Ti is allowed to wait abort wait T1 T1 1 2 3 4 5... 1 2 3 4 5... T2 1 2 3 4 5... T2 1 2 3 4 5... Chapter Four: Concurrency Control 22  Continued ❑Wait-Die: If TS(Ti) < TS(Tj), then Ti is allowed to wait; otherwise abort Ti (Ti dies) and restart it later with the same timestamp. T1 1 2 3 4 5... T1 1 2 3 4 5... wait T2 abort 1 2 3 4 5... T2 1 2 3 4 5... Chapter Four: Concurrency Control 23  Deadlock Prevention Protocols No Waiting If a transaction is unable to obtain a lock, it is immediately aborted and then restarted after a certain time delay without checking if a deadlock will actually occur or not. The protocol can cause transactions to abort and restart needlessly cautious waiting It has been proposed to reduce the number of needless aborts/restarts. If Tj is not blocked (not waiting for some other locked item), then Ti is blocked and allowed to wait; otherwise abort Ti. Chapter Four: Concurrency Control 24  Deadlock Detection ❖ The DBMS periodically tests the database for deadlocks. ❖ If a deadlock is found, one of the transactions (the “victim m”) is aborted (rolled back and restarted) and the other transaction continues. ❖ The concept is to not enforce any restrictions on executing the transactions, but check if a deadlock actually exists. ❖ Wait-for graph is used to detect the state of deadlock Wait for graph: ❖ One node for each currently executing transaction. ❖ If Ti is waiting to lock an item X that is currently locked by Tj, a directed edge from Ti to Tj is created. ❖ If Tj releases the lock of item that Ti was waiting for, the directed edge is dropped from the graph. ✓ If the graph has a cycle, the state of the deadlock exists. ✓ Selecting a transaction to be aborted is known as Victim Selection. 25 Chapter Four: Concurrency Control  Timeouts ❖The technique used to kill the session based up on the system defined times. ❖This method is practical because of its low overhead and simplicity. ❖ In this method, if a transaction waits for a period longer than a system-defined timeout period, the system assumes that the transaction may be deadlocked and aborts it regardless of whether a deadlock actually exists or not. ❖ In Addition to serializability and deadlock problem Starvation may also occur when implementing lock operations. Chapter Four: Concurrency Control 26  Concurrency Control Based on Timestamp Ordering Timestamp: A monotonically increasing variable indicating the age of an operation or a transaction. A different approach that guarantees serializability involves using transaction timestamps to order transaction execution for an equivalent serial schedule. Timestamp of transaction T, TS(T) is a unique identifier created by the DBMS to identify a transaction. Timestamp values are assigned in the order in which the transactions are submitted to the system, so a timestamp can be thought of as the transaction start time. Concurrency control techniques based on timestamp ordering do not use locks; hence, deadlocks cannot occur. Chapter Four: Concurrency Control 27  Continued ❖Timestamps can be generated in several ways. Two possible ways are listed below: ❖Using a counter timestamp: ❖A counter that is incremented each time its value is assigned to a transaction and are numbered 1, 2, 3,... in this scheme. ❖A computer counter has a finite maximum value, so the system must periodically reset the counter to zero. ❖Using date timestamps: ❖The current date/time value of the system clock and ensure that no two timestamp values are generated during the same tick of the clock. Chapter Four: Concurrency Control 28  The Timestamp Ordering Algorithm The idea for this scheme is to order the transactions based on their timestamps. timestamp ordering (TO) is a schedule in which the transactions participate is then serializable, and the only equivalent serial schedule permitted has the transactions in order of their timestamp values. The algorithm must ensure that, for each item accessed by conflicting operations in the schedule, the order in which the item is accessed does not violate the timestamp order. To do this, the algorithm associates with each database item X two timestamp (TS) values: RTS(X): The read timestamp of item X, which is the largest timestamp among all the timestamps of transactions that have successfully read item X that is, RTS(X) = TS(T), where T is the youngest transaction that has read X successfully. The Timestamp on which object X was last read by some transaction Ti. i.e., RTS(X):=TS(Ti) Chapter Four: Concurrency Control 29  Cont… WTS(X): The write timestamp of item X, which is the largest of all the timestamps of transactions that have successfully written item X that is, WTS(X) = TS(T) where T is the youngest transaction that has written X successfully. The Timestamp on which object X was last written by some transaction Tj. i.e WTS(X)=TS(Tj). Chapter Four: Concurrency Control 30  Basic Timestamp Ordering (TO) ✓Utilizes Timestamps to guarantee serializability of concurrent transactions. ✓Whenever a transaction T attempts to perform some action (read/write) on data item X on timestamp TS(T). ✓Basic Timestamp ordering decides whether T has to be aborted or T can continue execution. ❑The concurrency control algorithm must check whether conflicting operations violate the timestamp ordering in the following two cases: Case 1 (Read): Transaction T issues a read(X) operation ❑ If TS(T) < WTS(X), then read(X) is rejected (as the TO rule is violated). T has to abort and be rejected. ❑If WTS(X)