资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level, Dennis Shasha, Philippe Bonnet 2001,*, Dennis Shasha, Philippe Bonnet 2001,Lock Tuning, Dennis Shasha, Philippe Bonnet 2001,Concurrency Control Goals,Performance goals,Reduce blocking,One transaction waits for another to release its locks,Avoid deadlocks,Transactions are waiting for each other to release their locks,Correctness goals,Serializability: each transaction appears to execute in isolation,The programmer ensures that serial execution is correct.,Trade-off between correctness and concurrency, Dennis Shasha, Philippe Bonnet 2001,Ideal Transaction,Acquires few locks and favors shared locks over exclusive locks,Reduce the number of conflicts,- conflicts are due to exclusive locks,Acquires locks with,fine granularity,Reduce the scope of each conflict,Holds locks for a short time,Reduce waiting,Lock Tuning,1. Use special system facilities for long reads.,2. Eliminate locking when it is unnecessary.,3. Take advantage of transactional context to chop transactions into small pieces.,4. Weaken isolation guarantees when the application allows it.,5. Select the appropriate granularity of locking.,6. Change your data description data during quiet periods only. (Data Definition Language statements are considered harmful.),7. Think about partitioning.,8. Circumvent hot spots.,9. Tune the deadlock interval., Dennis Shasha, Philippe Bonnet 2001,Use facilities for long reads,Oracle provides,snapshot isolation,whereby read-only queries hold no locks yet appear to execute serializably,A read-only transaction,R reads the database as the database appeared when R began, Dennis Shasha, Philippe Bonnet 2001,Snapshot isolation,Read-only queries suffer no locking overhead.,Read-only queries can execute in parallel and on the same data as short update transactions without causing blocking or deadlocks.,When extended to read/write transactions, snapshot isolation does,not guarantee correctness,For example: T,1,: x := y T,2,: y := x,The lesson is: use snapshot isolation for read-only transactions, Dennis Shasha, Philippe Bonnet 2001,Eliminate unnecessary locking,Locking is unnecessary in two cases.,1. When,only one transaction runs at a time, for example, when loading the database,2. When all transactions are,read-only, for example, when doing decision support queries on archival databases, Dennis Shasha, Philippe Bonnet 2001,Make your transaction short,How long should a transaction be?,The more locks a transaction requests, the more likely it is that it will have to wait for some other transaction to release a lock.,The longer a transaction,T executes, the more time another transaction will have,to wait if it is blocked by,T., Dennis Shasha, Philippe Bonnet 2001, Dennis Shasha, Philippe Bonnet 2001,Example: Simple Purchases,Purchase item I for price P,If cash 50. It is.,P2 checks that cash 75. It is.,P1 completes. Cash = 50.,P2 completes. Cash = - 25., Dennis Shasha, Philippe Bonnet 2001,Example: Simple Purchases,Orthodox solution,Make whole program a single transaction,Cash becomes a bottleneck!,Chopping solution,Find a way to rearrange and then chop up the transactions without violating serializable isolation level., Dennis Shasha, Philippe Bonnet 2001,Example: Simple Purchases,Chopping solution:,If Cash 50. Cash := 50.,P21: 75 50. Rollback.,P12: inventory := inventory + 50., Dennis Shasha, Philippe Bonnet 2001,Transaction Chopping,Execution rules:,When pieces execute, they follow the partial order defined by the transactions.,If a piece is aborted because of a conflict, it will be resubmitted until it commits,If a piece is aborted because of an abort, no other pieces for that transaction will execute., Dennis Shasha, Philippe Bonnet 2001,Transaction Chopping,Let T1, T2, , Tn be a set of transactions. A chopping partitions each Ti into pieces ci1, ci2, , cik.,A chopping of T is rollback-safe if (a)T does not contain any abort commands or (b) if the abort commands are in the first piece., Dennis Shasha, Philippe Bonnet 2001,Correct Chopping,Chopping graph (variation of the serialization graph):,Nodes are pieces,Edges:,C-edges: C stands for conflict. There is a C-edge between two pieces from different transactions if they contain operations that access the same data item and one operation is a write.,S-edges: S stands for siblings. There is an S-edge between two pieces, iff they come from the same transaction.,A chopping graph contains an S-C cycle if it contains a cycle that includes at least one S-edge and one C-edge., Dennis Shasha, Philippe Bonnet 2001,Correct Chopping,A chopping is correct if it is,rollback safe,and,its chopping graph contains no SC-cycle.,T1: r(x) w(x) r(y) w(y),T2: r(x) w(x),T3: r(y) w(y),T1,T2,T3,T11: r(x) w(x),T12: r(y) w(y),T11,T12,T3,T2,S,C,C,T11: r(x) T12: w(x)T13: r(y) w(y),T12,T13,T3,T2,S,C,C,T11,S,C,CORRECT,NOT CORRECT,S, Dennis Shasha, Philippe Bonnet 2001,Chopping Example,T1: RW(A) RW (B),T2: RW(D) RW(B),T3: RW(E) RW(C),T4: R(F),T5: R(E),T6: R(A) R(F) R(D) R(B) R(E) R(G) R(C), Dennis Shasha, Philippe Bonnet 2001,Chopping Example,T1,T2,T4,T5,T3,T62,T61,T61: R(A) R(F) R(D) R(B),T62: R(E) R(G) R(C),C,C,C,C,C,S, Dennis Shasha, Philippe Bonnet 2001,Finest Chopping,A private chopping of transaction Ti, denoted private(Ti) is a set of pieces ci1, ci2, , cik such that:,ci1, ci2, , cik is a rollback safe chopping,There is no SC-cycle in the graph whose nodes are T1, , Ti-1, ci1, ci2, , cik, Ti+1, Tn,The chopping consisting of private(T1), private(T2), , private(T2) is rollback-safe and has no SC-cycles., Dennis Shasha, Philippe Bonnet 2001,Finest Chopping,In: T, T1, . Tn-1,Initialization,If there are abort commands,then p_1 := all writes of T (and all non swappable reads)that may occur before or concurrently with any abort command in T,else p_1 := first database access,P := x | x is a database operation not in p_1,P := P,p_1, Dennis Shasha, Philippe Bonnet 2001,Finest Chopping,Merging pieces,Construct the connected components of the graph induced by C edges alone on all transactions T1, , Tn-1 and on the pieces in P.,Update P based on the following rule:,If p_j and p_k are in the same connected component and j k, then,add the accesses from p_k to p_j,delete p_k from P, Dennis Shasha, Philippe Bonnet 2001,Sacrificing Isolation for Performance,A transaction that holds locks during a screen interaction is an invitation to bottlenecks,Airline Reservation,Retrieve list of seats available,Talk with customer regarding availability,Secure seat,Single transaction is intolerable, because each customer would hold lock on seats available.,Keep user interaction outside a transactional context,Problem:,ask for a seat but then find its unavailable. More tolerable., Dennis Shasha, Philippe Bonnet 2001,Isolation Levels,Read Uncomitted (No lost update),Exclusive locks for write operations are held for the duration of the transactions,Lock for writes until commit time. No locks for reads,Read Committed (,No inconsistent retrieval,),Lock for writes until commit time.,Shared locks are released as soon as the read operation terminates.,Repeatable Read (no unrepeatable reads),Strict two phase locking: lock for writes and reads until commit time.,Serializable (no phantoms),Table locking or index locking to avoid phantoms, Dennis Shasha, Philippe Bonnet 2001,Value of Serializability - Data,Settings:,accounts,(,number, branchnum, balance);,create clustered index c on accounts(number);,100000 rows,Cold buffer; same buffer size on all systems.,Row level locking,Isolation level (SERIALIZABLE or READ COMMITTED),SQL Server 7, DB2 v7.1 and Oracle 8i on Windows 2000,Dual Xeon (550MHz,512Kb), 1Gb RAM, Internal RAID controller from Adaptec (80Mb), 4x18Gb drives (10000RPM), Windows 2000., Dennis Shasha, Philippe Bonnet 2001,Value of Serializability - transactions,Concurrent Transactions:,T1: summation query 1 thread,select sum(balance) from accounts;,T2: swap balance between two account numbers (in order of scan to avoid deadlocks) N threads,valX:=select balance from accounts where number=X;valY:=select balance from accounts where number=Y;update accounts set balance=valX where number=Y;update accounts set balance=valY where number=X;,2 - Tuning the Guts, Dennis Shasha, Philippe Bonnet 2001,26,Value of Serializability - results,With SQL Server and DB2 the scan returns incorrect answers if the read committed isolation level is used (default setting),With Oracle correct answers are returned (snapshot isolation), but beware of swapping,2 - Tuning the Guts, Dennis Shasha, Philippe Bonnet 2001,27,Cost of Serializability,Because the update conflicts with the scan, correct answers are obtained at the cost of decreased concurrency and thus decreased throughput.,Weaken isolation guarantees carefully,Begin with the highest degree of isolation (serializable in relational systems).,If a given transaction (usually a long one) either suffers extensive deadlocks or causes significant blocking, consider weakening the degree of isolation, but do so with the awareness that the answers may be off slightly., Dennis Shasha, Philippe Bonnet 2001,Control the granularity of locking,DBMS offers different granularities of locks,Record/row-level, table-level, page-level,Intuitively, Record-level locking is better, since it permit two different transactions to access different records on the same page.,However, in real DBMS,row lock is rarely more expensive than table lock, since the recovery overhead dominate the overall overhead,Sql server and DB2 provide,lock escalation,Automatically upgrades row-level locks into a single table-level lock when the number f row-level locks reaches a predefined threshold,Escalation may lead to deadlock,The lesson is :Long transactions should use table locks mostly to avoid deadlocks, and short transactions should use record locks to enhance concurrency,a long transaction is one that accesses nearly all the pages of the table, Dennis Shasha, Philippe Bonnet 2001, Dennis Shasha, Philippe Bonnet 2001,A,If object not found in hash table, it is unlocked,Lock info for A,A,.,.,H,Lock Table, Dennis Shasha, Philippe Bonnet 2001,Locking in SQL Server 7,syslockinfo,dbid,objid,lock granularity,lock owner,lock waiter,lockmode,1,117,RID,X,1 117 PAG IX,1 117 TAB IX,1 118 RID S,LO1,LO1,LO1,LO2, LO3,LW2,LW3,spid,10,10,10,10,Lock 32 bytes,Lock owner block 32 bytesLock waiter block 32 bytes,LW1, LW4, Dennis Shasha, Philippe Bonnet 2001,Locking in Oracle 8i,Data page,row,Interested transaction list,(fixed array - INITRANS MAXTRANS),T1,T1 lock,Enqueue resource structure,(fixed array default 4 entries per transaction),T1,Enqueued locks array,T2 lock,Enqueue wait (time out 3sec),Process,T3 lock,Deadlock detection,H, Dennis Shasha, Philippe Bonnet 2001,Locking Overhead - data,Settings:,accounts,(,number, branchnum, balance);,create clustered index c on accounts(number);,100000 rows,Cold buffer,SQL Server 7, DB2 v7.1 and Oracle 8i on Windows 2000,No lock escalation on Oracle; Parameter set so that there is no lock escalation on DB2; no control on SQL Server.,Dual Xeon (550MHz,512Kb), 1Gb RAM, Internal RAID controller from Adaptec (80Mb), 4x18Gb drives (10000RPM), Windows 2000., Dennis Shasha, Philippe Bonnet 2001,Locking Overhead - transactions,No Concurrent Transactions:,Update 10 000 updates,update accounts set balance = Val;,Insert 10 000 inserts, e.g. typical one:,insert into accounts values(664366,72255,2296.12);,2 - Tuning the Guts, Dennis Shasha, Philippe Bonnet 2001,35,Locking Overhead,Row locking is barely more expensive than table locking,because recovery overhead is higher than locking overhead,Exception is updates on DB2 where table locking is distinctly less expensive than row locking. (DB2 use logical logging, which logs the operation that caused change instead of image of changed data),Data definition language (DDL) statementsare considered harmful,DDL is the language used to access and manipulate catalog or metadata,The catalog can easily become a,hot spot,and therefore a bottleneck,The lesson is: avoid updates to the system catalog during heavy system activity, especially if you are using dynamic SQL, Dennis Shasha, Philippe Bonnet 2001,Think about partitioning,Problem: insert a collection records into history file or security file, or log file,Time dependent insertion,Last page of the file may become a concurrency bottleneck,Solution: partition insertions to the file across different pages and possibly different disks,Set up many insertion points and insert into them randomly,Set up a clustering index based on some attribute that is not correlated with the time of insertion.,Hash the time of insertion and use that as the clustering key., Dennis Shasha, Philippe Bonnet 2001,Multiple insertion points and page locking,“sequential a clustered index defined on an attribute whose value increases (or even decreases) with time,“Nonsequential denotes that independent of time, Dennis Shasha, Philippe Bonnet 2001,Multiple insertion points and row locking,Row locking avoids contention between successive insertions, Dennis Shasha, Philippe Bonnet 2001,Circumventing hot spots,A,hot spot is a piece of data that is accessed by many transactions and is updated by,some.,Hot spots cause,bottlenecks,because each updating transaction must complete before any other transaction can obtain a lock on the hot data item.,Solution,Use partitioning to eliminate it,Access the hot spot as late as possible in the transaction,Use special database management facilities, Dennis Shasha, Philippe Bonnet 2001,2 - Tuning the Guts, Dennis Shasha, Philippe Bonnet 2001,41,Logical Bottleneck: Sequential Key generation,Consider an application in which one needs a,sequential number,to act as a key in a table, e.g. invoice numbers for bills.,Ad hoc approach: a separate table holding the last invoice number. Fetch and update that number on each insert transaction.,The last invoice number becomes a bottleneck due to two-phase locking,Counter approach: use facility such as Sequence (Oracle)/Identity(SQL Server)., Dennis Shasha, Philippe Bonnet 2001,Latches and Locks,Locks are used for concurrency control,Is held until commit the transaction,Requests for locks are queued,Priority queue,Lock data structure,Locking mode, lock granularity, transaction id.,Lock table,Latches are used for mutual exclusion,A latch is released immediately after access,Requests for latch succeeds or fails,Active wait (spinning) on latches on multiple CPU.,Single location in memory,Test and set for latch manipulation, Dennis Shasha, Philippe Bonnet 2001,Counter Facility - data,Settings:,default isolation level: READ COMMITTED; Empty tables,Dual Xeon (550MHz,512Kb), 1Gb RAM, Internal RAID controller from Adaptec (80Mb), 4x18Gb drives (10000RPM), Windows 2000.,accounts,(,number, branchnum, balance);,create clustered index c on accounts(number);,counter,(,nextkey,);,insert into counter values (1);, Dennis Shasha, Philippe Bonnet 2001,Counter Facility - transactions,No Concurrent Transactions:,System 100 000 inserts, N threads,SQL Server 7 (uses Identity column),insert into accounts values (94496,2789);,Oracle 8i,insert into accounts values (seq.nextval,94496,2789);,Ad-hoc 100 000 inserts, N threads,begin transaction,NextKey:=select nextkey from counter; update counter set nextkey = NextKey+1;commit transactionbegin transaction insert into accounts values(NextKey,?,?);commit transaction, Dennis Shasha, Philippe Bonnet 2001,Avoid Bottlenecks: Counters,System generated counter (system) much better than a counter managed as an attribute value within a table (ad hoc).,Counters may miss ids, however which is tolerable in many real apps,
展开阅读全文