LOCKING and CONCURRENCY CONTROL2

Information about LOCKING and CONCURRENCY CONTROL2

Published on July 15, 2014

Author: indranisen2003

Source: authorstream.com

Content

LOCKING and CONCURRENCY CONTROL: LOCKING and CONCURRENCY CONTROL PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE LOCKING techniques: : LOCKING techniques: A lock guarantees exclusive use of a data item to a current transaction. In other words transaction T1 does not have any access to a data item that is currently used by T2. A transaction acquires a lock prior to the data access. The lock is released when the transaction is completed, so that another transaction can lock the data item for exclusive use. Most multiuser DBMS automatically initiate and enforce locking procedures. All lock information is managed by a lock manager which is responsible for assigning the locks to the transactions. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE TWO PHASE LOCKING Protocol: : The two-phase locking protocol (2PL) compels the transaction to acquire all the locks on the data item before it unlocks them. It has two phases, (1) Growing phase where locks are acquired on resources and (2) Shrinking phase where locks are released. The two-phase locking protocol is based on two rules. Rule 1: A data object has to be locked by Exclusive or Shared lock before it can be accessed by a transaction. Rule 2: As soon as a transaction unlocks its first data object, it cannot acquire any further locks (shrinking phase). Consider the following schedules which are following Two phase Locking based on the same set of Transaction T1 and T2 Prof Indrani Sen ,MCA,MPhil Computer Science TWO PHASE LOCKING Protocol: PowerPoint Presentation: Prof Indrani Sen ,MCA,MPhil Computer Science T1 T2 Stored value Request Read_Lock(A01208,Balance) (ALLOWED) Read(A01208,Balance) 45,000 Request Read_Lock (A01208,Balance) (ALLOWED) Read(A01208,Balance) 45,000 Balance=Balance-20,000 Request Write_Lock(A01208,Balance) (DENIED) Balance=Balance+15000 Request Write_Lock (A01208,Balance) (DENIED) PowerPoint Presentation: In the above schedule if the Transactions T1 and T2 have acquired a Shared lock (read lock) on a single data item, they cannot acquire a Exclusive lock on the same. So to acquire an Exclusive lock they both have to release the locks. According to Two Phase locking, once the Transaction releases a lock, it cannot acquire a lock again. So the LOST UPDATE problem does not incur in this case. Prof Indrani Sen ,MCA,MPhil Computer Science PowerPoint Presentation: PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE T1 T2 Stored value Request Exclusive_Lock (A01208,Balance) (ALLOWED) Read(A01208,Balance) 45,000 Balance=Balance+15000 Write(A01208,Balance) 60,000 Request Shared_Lock (A01208,Balance) (DENIED) WAIT(T2) 60,000 UNLOCK(A01208,Balance) Request Exclusive_Lock (A01208,Balance) (ALLOWED) Read(A01208, Balance) Balance=Balance-20000 Write(A01208,Balance) UNLOCK(A01208,Balance) COMMIT 40,000 ROLLBACK(T1) Interleaved Schedule with 2PL: PowerPoint Presentation: Consider the above figure which indicates that Transaction T1 requests for the Shared Lock, Reads the data and then acquires a consecutive Exclusive lock to update the Balance. But the Transaction T1 is then rolled back and the change is undone. In the mean time if Transaction T2 request for the shared lock it is denied access because T1 has a Exclusive Write lock acquired on the data. So T2 has to wait unless and until Transaction T1 releases the Exclusive Write Lock and then T2 can update the data Prof Indrani Sen ,MCA,MPhil Computer Science Ensuring serializability in 2PL : Ensuring serializability in 2PL The two phase locking protocol ensures serialisability as when T1 is accessing an Item T2 cannot access it and T1 cannot unlock the data item and access it again after T2 because according to 2PL, if the transaction releases a lock it cannot acquire it again. So a cycle is never formed in the precedence graph ensuring serializability. The above schedule shown, guarantees serializability but does not prevent cascading rollback. It is because if a transaction obtains an exclusive lock on the data item and unlocks it before getting committed, there is still a chance of reading uncommitted data by another transaction or Dirty read. In this situation if the first transaction is aborted or rollback then the second transaction also has to be forced to abort causing cascading rollback. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: In Strict 2 Phase Locking Protocol first the read locks are released and then only after the transaction is Committed or rollback all write locks are released. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: T1 T2 Stored value Request Exclusive_Lock (A01208,Balance) (ALLOWED) Read(A01208,Balance) 45,000 Balance=Balance+15000 Write(A01208,Balance) 60,000 Request Shared_Lock(A01208,Balance) (DENIED) WAIT(T2) ROLLBACK(T1) 45,000 UNLOCK(A01208,Balance) Request Exclusive_Lock (A01208,Balance) (ALLOWED) Read(A01208, Balance) Balance=Balance-20000 Write(A01208,Balance) UNLOCK(A01208,Balance) COMMIT 25,000 PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE rigorous 2PL: rigorous 2PL In rigorous 2PL the transaction holds all locks exclusive as well as shared until completion after which all locks are released. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE GRANULARITY WITH LOCKS : GRANULARITY WITH LOCKS Locking can take place at any levels like database level, page level, table level, row level or field level. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Database Level Locking: : Database Level Locking: In the Database level lock, the entire database is locked preventing the use of any tables in the database at the same time. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: This level of locking is undesirable for online and real time transaction processing as the transactions have to wait even if they want to access a different table from the same database. Imposing a lock at the database level will prevent any other Transaction like T2 shown in the diagram below while a Transaction T1 is already accessing it. It is not an efficient locking system as it will prevent thousand of other Transactions to access database even if they want to access a different relation concurrently. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Table Level Locking: : Table Level Locking: In a table level lock, the entire table is locked preventing any other transaction to access the same table at the same time. Multiple transactions can access several different tables but two transactions cannot access the same table at the same time. Table level locks are less restrictive that the database locks and are suitable for multiuser DBMS. As shown in the diagram below while T1 is accessing the Account table T2 cannot access the same. At the same time T3 can access a different relation like Transaction. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Page level Lock: : Page level Lock: In a page level lock the DBMS will lock the entire disk page. A disk page is equivalent to a disk block which can be described as a referenced section of a disk. A table may span several pages or one page can consist of the rows of multiple tables. Page level locks are the most commonly used locking method in practice. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Shown in the figure below Account and Branch relation exists in the same page while Transaction and Customer relation shares a different page. While T1 is already accessing the Account table if T2 request for access to the Branch table, T2 is denied access as the lock is imposed at the page level. At the same time T3 can access a relation located in another page concurrently. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Row Level Lock: : Row Level Lock: The row level lock is much restrictive in nature. The DBMS allows concurrent transactions to access different rows of the same table even if the rows are located on the same page. Although row level locking approach makes more data available to the user at the same time, it is difficult to manage because of the overhead required to manage multiple locks each one corresponding to each row of a table. For example, T2 can update the balance of Account with AcNo A01208 while at the same time T1 is updating the balance of AcNo A00987. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Field Level Lock: : Field Level Lock: A field level lock allows concurrent transactions to access the same row provided they access different columns within that row. For example transaction T2 can access the Balance of the Account number A01208 in the Account relation while T1 accesses the BranchID field. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Binary Locks: : Binary Locks: A binary lock can have two states or values either locked or unlocked. A separate unique lock is associated with individual data items . If the value of binary lock on data item LOCK (A) is 1 then no other transaction will be able to access that lock. If the LOCK (A) =0 then the data item is available to be accessed and the transaction can lock that data item and use it when requested . PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE The following are the rules of Binary Locks:- : The following are the rules of Binary Locks:- A transaction must issue the operation LOCK (A) before any READ (A) or WRITE (A) operations are performed with data item A. A transaction must issue the operation UNLOCK (A) after all READ (A) and WRITE (A) Operations completed. A transaction cannot issue a LOCK (A) operation if it already holds the lock on Item A. A transaction cannot issue an UNLOCK (A) operation unless LOCK(A)=1 One transaction at the maximum can hold the lock on a particular item. Two transactions cannot access the same item concurrently. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Disadvantages of Binary Locks : Disadvantages of Binary Locks Transactions are forced to wait even if it wants to read a data item which generally does not cause any conflicts. Thus, binary locking scheme is too restrictive for database items, as they fail to exploit the benefits of concurrent access and is not preferable to be used in a multiprocessing environment. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Lock Conversions : Lock Conversions Change of a lock is called lock conversion and the lock may be upgraded (lock upgrade) or downgraded (lock downgrade ). When a transaction request the conversion of a read or shared lock to an Exclusive or Write lock it is known as upgrading a lock. When a transaction wants to request conversion from a Write lock to Read or Shared lock it is known as downgrading a lock. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE TIMESTAMP BASED CONCURRENCY CONTROL: : TIMESTAMP BASED CONCURRENCY CONTROL: Locking scheme suffers from problems like Deadlock and low levels of concurrency. Timestamp systems can be implemented as an alternative to locking . In case of the Centralized Timestamp methods, each copy of a data item contains two Timestamp values, the Read Timestamp and the Write Timestamp. A serial order is created among the concurrent Transactions by assigning each Transaction an Unique positive number. The Timestamp value assigned by the DBMS is such that it determines the serialisability order of the Transactions . A Transaction with a smaller Timestamp value is considered to be an older transaction and a Transaction with a higher Timestamp value is considered to be younger. The value assigned is actually the System clock value at the time of the Transaction and hence the name Timestamp. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: A conflict is said to occur when an older transaction tries to read a value written by a younger transaction or an older Transaction attempts modifying a value already read or written by a younger Transaction. The attempts show that the older Transaction was late in processing its operations. The contention problem in the Timestamp ordering system can be resolved by rolling back one of the conflicting Transactions. A Transaction T1 with a Timestamp value ts1 does not read or write a value that was already read by a younger transaction T1 which has a Timestamp value ts2 where ts2>ts1 . If the Write Timestamp of the data item to be read is more than the value ts1, then the Transaction T1 has to be aborted and restarted. When a transaction aborts, it must restart with a new (larger) time stamp. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: T1(User 1) T2 (User 2) Timestamp value Stored Data Request Write(A) (A is not written currently by any transaction) Balance_A = Balance_A -X Write(A) Timestamp_value(T1):ts1 Timestamp_value(A):<rA,wA> Balance_A-X Request Write(B) (B is not written currently by any transaction Balance_B = Balance_B -Y Write(B) Timestamp_value(T2):ts2 Timestamp_value(B):<rB,wB> Balance_B-Y Request Write(B) ts1<ts2 and wB>ts1 (DENIED WRITE, B is written by a newer Transaction) Rollback(T1) Balance_A-X+X=Balance_A (Change undone due to rollback) Request Write(A) ts1<ts2 and wA<ts2 (ALLOWED WRITE,A is written by an older Transaction) Write(B) COMMIT Timestamp_value (T2):ts2 Timestamp_value (A):< rA,wA > Balance_A+Y PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Thomas write rule : Thomas write rule In computer science, particularly the field of databases, the  Thomas Write rule  is a rule in timestamp-based concurrency control. It can be summarized as  ignore outdated writes . It states that, if a more recent transaction has already written the value of an object, then a less recent transaction does not need perform its own write since it will eventually be overwritten by the more recent one. The Thomas Write rule is applied in situations where a predefined  logical  order is assigned to transactions when they start. For example a transactions might be assigned a monotonically increasing timestamp when it is created. The rule prevents changes in the order in which the transactions are executed from creating different outputs: The outputs will always be consistent with the predefined logical order. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Optimistic Concurrency Control:: Optimistic Concurrency Control: The concurrency is known as Pessimistic concurrency control when a single resource before being concurrently accessed by multiple transactions, you assume a conflict and lock the resource. It is called "pessimistic" because the system assumes the worst . The locks are placed as soon as any piece of the row is accessed, making it impossible for two or more users to update the row at the same time depending on the lock mode (shared or exclusive). PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE disadvantage: disadvantage While the locking system is otherwise safe, it has some serious disadvantages: Starvation: An application user selects a record for update, and then is idle or doing some other task without completing or aborting the transaction. All other users that need to update that record are forced to wait until the user returns and completes the transaction, or until the Database Administrator kills the transaction manually and releases the lock. The Deadlock: User1 and User2 are both updating the database at the same time. User1 locks a record and then request a resource held by User2 who is waiting to obtain a lock held by User1. Both transactions go into an infinite wait state called deadlock. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Optimistic concurrency control considers the fact that although conflicts are possible, they are very rare in occurrence. So instead of locking every record each time while a Transaction is using it, the system tries to find out whether two users are actually attempting to access the same record at the same time. If the assumption is found to be correct then the update of one Transaction is discarded and the user is informed. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Some DBMSs uses multiversioning for implementing Optimistic concurrency control. Each time that the transaction T1 reads a record to update it, the DBMS makes a copy of the version number of the record and stores that copy for later reference. When the Transaction is committed and the data is to be written back to the disk the DBMS compares the version number which it read with the version number that it contains currently. If the version numbers are the same, it indicates that no other transaction has changed the record and the system can write the updated value to the disk. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: If the originally read value and the current value on the disk are not the same, then the current operation is probably out-of-date which will result in LOST UPDATE problem. Thus the system discards the version of the data and gives the user an error message. Each time a record is updated, the version number is updated as well. In practice there are a number of different way of achieving this, but the most common is the use of a Modification time-stamp. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: This way the data that each user sees is consistent throughout the transaction, and users are able to concurrently access the database. Sometimes the optimistic concurrency control mechanism is called optimistic locking, but it is not a true locking scheme and the system does not place any locks when optimistic concurrency control is used. T1: Withdraw X from Account A T2: Withdraw Y from Account A PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: T1(User 1) T2 (User 2) Version Stored Data Request Read(A) (ALLOWED) Read(A) Read Version(A)=V1 Request Read(A) (ALLOWED) Read(A) Read Version(A)=V1 Version(A)=VA1 Balance_A Request Write(A) Balance_A = Balance_A -X Write(A) Update version(A ) V2 Version(A)=VA2 Balance_A -X Request Write(A) Balance_A = Balance_A -Y If (VA1 <> VA2) (DENIED WRITE,VA1 is an outdated version) PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Phases in optimistic Concurrency Control: Phases in optimistic Concurrency Control In this technique only at the time of commit serializability is checked and transactions are aborted in case of non- serializable schedules. Three phases: Read phase Validation phase Write phase PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Read phase:: Read phase : PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE A transaction can read values of committed data items. However, updates are applied only to local copies (versions) of the data items (in database cache). Database Concurrency Control: Database Concurrency Control Validation phase : Serializability is checked before transactions write their updates to the database. This phase for T1 checks that, for each transaction T2 that is either committed or is in its validation phase, one of the following conditions holds : PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Condition 1: Condition 1 T1 completes its write phase before T2 starts its read phase. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Condition 1: Condition 1 Condition 1 states that T1 actually completes before T 2 starts , i.e. they execute completely in serial order R V W R V W T1 T2 Condition 2: Condition 2 T2 starts its write phase after T1 completes its write phase, But the reading of T1 and Writing of T2 can take place concurrently. But the read_set of T1 has no items in common with the write_set of T2 PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Condition 2: Condition 2 R(A) V1 W(A) T1 R(B) V1 W(A) T2 CONDITION 3: CONDITION 3 Condition 3 is similar to Condition 2 but does not require that T1 finish writing before T2 starts writing; Both the read_set and write_set of T1 have no items in common with the write_set of T2, This condition allows T1 and T2 to write objects at the same time, but there is no overlapping for the sets written by these two transactions. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Condition 3: Condition 3 R(B) V W(B) R(A) V W(A) PowerPoint Presentation: When validating T1, the first condition is checked first for each transaction T2, since (1) is the simplest condition to check. If (1) is false then (2) is checked and if (2) is false then (3 ) is checked. If none of these conditions holds, the validation fails and T1 is aborted. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Database Concurrency Control: Database Concurrency Control Validation (Optimistic) Concurrency Control Schemes 3. Write phase : On a successful validation transactions’ updates are applied to the database; otherwise, transactions are restarted. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Pessimistic Concurrency Control Optimistic Concurrency Control Involves creating shared or Exclusive Locks. Does not involve any Lock creation. Requires a Lock Manager for the management of Locks. Does not require any Lock Manager. Assumes a conflict before a conflict actually occurs during concurrent execution of a Transaction. Assumes that there will be no conflict during the concurrent execution of Transactions. Can cause a Deadlock which may require the aborting of any one of the Transactions involved. Does not cause a Deadlock. Does not require saving copies of multiple versions of the data item. Requires saving multiple versions of the data resource involved in concurrent access. The Transaction requesting for concurrent access may have to wait unless the Transaction accessing the item concerned releases the Lock. The Transaction requesting for concurrent access does not have to wait. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE DATA RECOVERY : DATA RECOVERY Data recovery which in the simplest terms, refers to the process of recovering data, is very essential for any organization which have or have not implemented Database Management Systems. A storage device can be of varied kinds like hard disk, removable disk, flash memory or any other type of electronic storage. There can be many reasons for the loss of data, like deletion of files accidentally, formatting storage, operating system crash or simply a system becoming inaccessible due to a forgotten password. Sometimes disaster strikes and a storage device might physically be unusable, such as in the case of a breakout of fire, flood or any other natural disasters. When the data is no longer accessible via normal regular means, the various processes for Data recovery can be enforced to regain safe and reliable access to that data. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE FAILURES AND ITS TYPES: : FAILURES AND ITS TYPES: Failures can cause disasters in the field of information storage. It can result in the loss of critical information and may lead to serious financial and business loss. There can be different types of failures, some of which are listed below: PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Transaction failure:: Transaction failure: Transaction fails due to some kinds of errors Syntactic or Runtime exceptions which may cause the transactions to terminate. The errors may include, typing a wrong input format, no memory or disk space, trying to access a tuple which no more exists and so on. Another common reason for transaction failure is deadlock which forces one Transaction to terminate and roll back its actions. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE System failure:: System failure: Due to some reasons there can be a system malfunction or operating system failure which causes a loss of information in the volatile storage or RAM which may cause loss of temporary information. It can be due to sudden power cut off. It can also be due to the unauthorized invasion of the System by virus or malwares. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Disk failure:: Disk failure: There can be loss of critical information from the secondary storage due to hard disk crash, segmentation faults, bad sectors etc. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE TYPES OF DATA RECOVERY: : TYPES OF DATA RECOVERY: The data recovery process becomes easy if the organization replicates its critical data to a safe location. The data recovery process also involves repairing any electrical or physical damage that may be preventing the media from accessing the data. Then the data is analyzed to be sure it is intact and usable, then provide a report of the results of the recovery like what data was recovered, what was the cause of the data loss, etc. Finally the data is restored on the media of your choice as soon as possible. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Database backup: Database backup Database backups are required for faster and easier data recovery in case failures. The backup can be either physical or logical. Physical backups, involve creating a copy of the physical files in a secured storage media. In contrast, logical backups contain logical data such as tables and stored procedures from which the Database can be rebuilt. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Logging Facilities: : Logging Facilities: One of features the DBMS provides is that the transactions use log files very often. Log is a special table which is created inside database and could be later used for other purposes. It could be used by DBMS in order to recover old data or for administration purposes. In the field of Computer Science, a transaction log is a history of actions executed by a database management system to retain ACID properties of a Transaction during crashes or hardware failures. Physically, a log is a file of updates done to the database, and is stored in persistent storage or secondary memory. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: If, after a successful connect, the database is found in an inconsistent state or not been shut down properly, the database management system reviews the database logs for uncommitted transactions and rolls back the changes made by these transactions. Additionally, all transactions that are already committed but whose changes were not yet materialized in the database are redone. Both are done to ensure atomicity and durability of transactions. The log is a sequence of records, which maintains an archive of update activities on the database. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: when transaction T1 starts, it registers itself by writing a <T1 start> log record. Before T1 executes write(X), a log record <T1, X_old , X_new > is written, where, X_old is the value of X before the write, and X_new is the value after X is updated. When T1 completes execution of its last statement, the log record <T1 commit> is written onto the stable storage. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Deferred Database Modification: : Deferred Database Modification: In this case writing the log records on to the stable secondary storage is delayed till the last statement of the Transaction is committed. During recovery after a crash, a transaction needs to be redone if and only if both <Ti start> and <Ti commit> are there in the log file as a record. Redoing a transaction T1 (redo Ti) will set the value of all data items updated by the transaction to the new values. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Time Interval Transaction Operation Log Volatile Storage/Main Memory (Account. Balance) Stable Storage (Account. Balance) 1 T1 Read Balance <T1 START> 45000 45000 2 T1 Balance = Balance + 15000 3 T1 Write Balance(Partially committed) <T1, Balance, 60000> 60000 (Delayed write) 45000 4 T1 <T1 COMMIT> 5 CRASH 6 T1 Aborted 7 T1 REDO(T1) <T1, Balance, 60000> 60000 PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: The partial commit of the Transaction occurs when the last statement of the transaction is executed successfully after the partial commit, the log record is updated with the entry <T1 Commit> confirming the successful execution of the transaction. The old value of the data item is not needed for this scheme. The write is not performed on the Balance immediately in the stable persistent storage. It is deferred. Crashes can occur while the transaction is executing the original updates, or during recovery. In case of a recovery after crash, the log record is checked and if both <T1 START> and <T1 COMMIT> is present, the transaction is redone and the stable storage is updated with the new value of the Balance. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Immediate Database Modification: : Immediate Database Modification: This scheme allows database updates of an uncommitted transaction to be made after the statements are executed successfully. But if the Transaction is rolled back, reversing the effects of the transaction may be needed, so update logs must have both old value and new value. The Update log record must be written before database item is written. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Recovery procedure consists of two operations: UNDO: It restores the value of all data items updated by the Transaction to their old values. REDO: It sets the value of all data items updated by a Transaction to its new values, on the basis of the log record of the transaction. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Time Interval Transaction Operation Log Volatile Storage/Main Memory (Account. Balance) Stable Storage (Account. Balance) 1 T1 Read Balance <T1 START> 45,000 45,000 2 T1 Balance= Balance+ 15000 3 T1 Write Balance <T1, Balance, 45000, 60000> 60,000 4 60,000 5 T1 CRASH 6 T1 UNDO <T1, Balance, 45000, 60000> 45,000 PowerPoint Presentation: there is a system failure before <T1 COMMIT> is written on to the log . In case the log for Transaction T1 contains the entry of <T1 START> and does not contain <T1 COMMIT>, during recovery, the Transaction is undone and the database is restored to its previous state. The value of the item is restored from the log entry which consists of the old as well as the new value for the Balance. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Time Interval Transaction Operation Log File Volatile Storage/Main Memory (Account. Balance) Stable Storage (Account. Balance) 1 T1 Read Balance <T1 START> 45,000 45,000 2 T1 Balance = Balance + 15000 3 T1 Write Balance <T1, Balance, 45000, 60000> 60,000 4 T1 60,000 5 T1 <T1 COMMIT> 6 T1 CRASH 6 T1 REDO <T1, Balance, 45000, 60000> 60000 PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Features of Immediate database modification: : Features of Immediate database modification: Both UNDO and REDO operations must be idempotent which is needed because the operations may get re-executed during recovery. When recovering after failure a Transaction needs to be undone if the log contains the record <Ti START>, but does not contain the record <Ti COMMIT>. When recovering after failure a Transaction needs to be redone if the log contains both the record <Ti START> and the record <Ti COMMIT>. Undo operations are performed before redo operations. The log record is written directly to stable storage. Order in which data is written on to the stable storage can be different from the order in which they are written to the main memory. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Checkpoint facility:: Checkpoint facility: A Checkpoint is similar to a snapshot of the DBMS state. By taking checkpoints, the DBMS can reduce the amount of work to be performed when the System crashes. The basic idea behind checkpoint-recovery is the saving of the current state of the DBMS in the persistent storage i.e. Hard Disk and restoration of system state in case of failures. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE CHECKPOINTING: CHECKPOINTING When a system is check pointed, the state of the entire system is saved to non-volatile storage. Typically this is accomplished by pausing the operation of the process whose state is to be saved, and copying the memory pages into non-volatile storage. The cost of a checkpoint will vary with the amount of state required to be saved and the bandwidth available to the storage mechanism being used to save the state. In the event of a system failure, the internal state of the DBMS can be restored, and it can continue its working from the point at which it was last saved. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Write-Ahead Transaction Log : Write-Ahead Transaction Log Write-Ahead Log guarantees that no updating of data takes place in the hard disk before a log record is written to the disk. When Transaction updates a data item in a Database it write into the buffer cache which holds the data to be modified. When the transaction reads the data item with an intention to write it copies the data pages to be modified from the disk to the buffer cache. When the data is modified, updated data is written onto the buffer cache and no modification is done directly to the disk. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: The modification is not written to disk until a checkpoint occurs in the database, or new data is required to be read into the buffer cache. Writing a modified data page from the buffer cache to disk is called flushing the page. A page modified in the cache, but not yet written to disk, is called a dirty page. When an update to a data item occurs in a buffer cache, the modification is recorded as a log record which must be written to the disk before the data from the buffer is flushed. Log records are written to disk when the transactions are committed. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Aries: Aries A steal, no-force approach Steal: if a frame is dirty and chosen for replacement, the page it contains is written to disk even if the modifying transaction is still active. No-force: Pages in the buffer pool that are modified by a transaction are not forced to disk when the transaction commits. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: After a crash, the recovery manager is invoked. Proceed in three phases. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Analysis: identify dirty pages in buffer pool (i.e., changes not yet written to disk), and identify active transactions at time of crash. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Redo: repeats all actions, starting from proper point in log, thus restoring the DB state to what is was at time of crash. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: Undo: undo actions of transactions that didn’t commit --> DB reflects only committed transactions.   PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE ARIES - the main principles : ARIES - the main principles   Write-ahead logging: any change to DB element is first recorded in log. The log record is written to stable storage before DB’s element change is written to disk. Repeating History During Redo: On restart following crash, retrace all actions of DBMS before crash so system is back to the exact state it was at crash time. Then undo (abort) transactions still active at time of crash. Logging Changes During Undo: Changes to DB while undoing a transaction are logged to ensure such an action is not repeated in the event of repeated restarts (from repeated failures).   PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE Dirty Pages Table : Dirty Pages Table This table is used to represent information about dirty buffer pages during normal processing. It is also used during restart recovery. It is implemented using hashing or via the deferred- writes queue mechanism. Each entry in the table consists of 2 fields : PageID and RecLSN PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: During normal processing , when a non-dirty page is being fixed in the buffers with the intention to modify , the buffer manager records in the buffer pool (BP) dirty-pages table , as RecLSN , the current end-of-log LSN , which will be the LSN of the next log record to be written. The value of RecLSN indicates from what point in the log there may be updates. Whenever pages are written back to nonvolatile storage , the corresponding entries in the BP dirty-page table are removed. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE PowerPoint Presentation: The contents of this table are included in the checkpoint record that is written during normal processing. The restart dirty-pages table is initialized from the latest checkpoint's record and is modified during the analysis of the other records during the analysis pass. The minimum RecLSN value in the table gives the starting point for the redo pass during restart recovery. PROF. INDRANI SEN,MCA ,MPHIL COMPUTER SCIENCE

Related presentations


Other presentations created by indranisen2003

TRANSACTIONS2
15. 07. 2014
0 views

TRANSACTIONS2

Functional dependancy2
15. 07. 2014
0 views

Functional dependancy2