CS352 Lecture - ConcurrencyLast revised 11/16/06Objectives:1. To introduce locking as a means of preserving the serializability of concurrent schedules.2. To briefly introduce other approaches to this problem (timestamps, validation, multi-version schemes)3. To introduce other important issues (phenomena related to insert/delete; weak levels of consistency; concurrency issues with index structures)I. IntroductionA. We have previously considered the notion of a transaction, and noted that, if properly formed transactions are executed serially, with one completing before the next starts, we are guaranteed to preserve consistency in the database. In particular, a SERIAL SCHEDULE composed of consistent transactions always preserves database consistency.B. There are many practical reasons for not wanting to be restricted to serial execution, thus allowing two or more transactions to be processed in parallel. (The individual steps are still done serially, but steps of one transaction can be interwoven with steps of another.)1. Better use of system resources through overlapping IO and computational activities.a) Being able to perform useful computation on the CPU while waiting for a disk access to complete.b) If the system has multiple disks, then being able to do multiple disk accesses in parallel, given that better than 90% of the time consumed in a disk access is spent on head movement and rotational latency.2. Support for access to the database by multiple users simultaneously.3. If a transaction is interactive, and there is some delay while a human responds to some aspect of it, we do not want the system to be totally idle.4. Not making the database totally inaccessible while procesing a long-running transaction (e.g. posting interest to all savings accounts.)1C. We have seen that we can permit concurrency and still preserve consistency provided that we schedule overlapping transactions in a way that is SERIALIZABLE - i.e. equivalent to a serial schedule, and if we ensure that any schedule we produce is RECOVERABLE - i.e. does not allow a transaction to fully commit until any transaction whose data it has read has already fully committed.D. In this lecture, we look at various strategies that might be used to ensure serializability. (Some also deal with recoverability).II. Ensuring serializability by the use of locksA. Thus far, we have discussed methods for testing a schedule to see if it is serializable. Since a concurrent system seldom "knows" ahead of time what sequence of transactions it will receive, a more useful goal is the development of a set of rules that ensures that any schedule that develops over time is serializable. One way to do this is by using a LOCKING PROTOCOL of some sort.1. We extend the DBMS primatives beyond the basic read and write to include primatives lock and unlock. Basically, a lock operation excludes other transactions from certain kinds of access to a data item, and an unlock operation releases that hold.2. These primatives do not appear as explicit DML statements, however. Instead, certain kinds of database operations result in appropriate locks being acquired as part of their implementation. Example: a SQL UPDATE involving a computation on some column will lock the column value at least from before it reads it to after it writes the updated value (and perhaps longer).Note: DBMS locking differs from the kind of locking we have met in Java, where the programmer is responsible to explicitly request it by using the keyword synchronized. DBMS locking is managed automatically as operations that require locks are executed.3. In particular, locking is tied in with the notion of transactions, in the sense that sometimes locks acquired during a transaction will need to be held until the transaction is fully committed, as we shall see.4. In the discussion below, we will show locking / unlocking operations explicitly. But this is only for pedagogical purposes - in reality, locking is done by the DBMS when an operation that requires a lock is started, and unlocking is done by the DBMS at the end of a transaction (or sometimes earlier)2B. Granularity of locks1. One important issue in any locking system is the GRANULARITY of the locks - i.e. what size objects can be locked.a) The coarsest granularity is locking at the file level - any transaction wishing to access the file must lock the entire file. This is seldom an adequate solution.b) More desireable is locking at the logical record level. Either an entire record can be locked, or possibly just some fields of a record. (Record locking is usually fine enough, though, and involves much less overhead.)c) However, since data is usually read and written in physical blocks or pages, not by logical records, locking is often implemented at the block or page level. Thus, a transaction wishing to lock a particular record will, in fact, end up locking the entire page on which it is stored. This granularity works well with crash control schemes based on shadow paging. A transaction that wishes to modify a page may work with its current copy, but must also lock the shadow copy until it commits to prevent lost updates from a second process also making a copy of the page.2. Some systems allow multiple lock granularities - e.g. the possibility of locking an entire file, or just one record. This can be useful if, for example, a transaction is performing some update operation on most or all of the records in a file - in which case locking the entire file is more efficient than locking the records one by one (especially if consistency requires that all the records remain locked until the transaction completes.)C. Locking protocols are generally based on two kinds of locks:1. A SHARED lock is used when a transaction wants to read an item, but does not want to change it. It allows other transactions to also obtain shared locks, so they can read the item, provided they too do not change it. The transaction obtaining a shared lock on an item must hold it as long as it wants to be sure that the item is not altered.We will use the notation lock-s(item)Example: A transaction that simply prints a user's current balance on some one account need not hold a lock on that balance after it has read it.3We will show this as:lock-s(balance)read(balance)unlock(balance)Example: A transaction to print the total balance of all accounts held by a given user must hold a shared lock on each individual balance until