The Lock Manager

SQL Server can lock data using several different modes. For example, read operations acquire shared locks and write operations acquire exclusive locks. Update locks are acquired during the initial portion of an update operation when the data is read. The SQL Server lock manager acquires and releases these locks. It also manages compatibility between lock modes, resolves deadlocks, and escalates locks if necessary. It controls locks on tables, on the pages of a table, on index keys, and on individual rows of data. Locks can also be held on system data—data that's private to the database system, such as page headers and indexes.

The lock manager provides two separate locking systems. The first system affects all fully shared data and provides row locks, page locks, and table locks for tables, data pages, text pages, and leaf-level index pages. The second system is used internally for index concurrency control, controlling access to internal data structures, and retrieving individual rows of data pages. This second system uses latches, which are less resource intensive than locks and provide performance optimization. You could use full-blown locks for all locking, but because of their complexity, they would slow down the system if they were used for all internal needs. If you examine locks using the sp_lock system stored procedure or a similar mechanism that gets information from the syslockinfo table, you cannot see latches—you see only information about locks for fully shared data.

Another way to look at the difference between locks and latches is that locks ensure the logical consistency of the data and latches ensure the physical consistency. Latching happens when you place a row physically on a page or move data in other ways, such as compressing the space on a page. SQL Server must guarantee that this data movement can happen without interference.

The Lock Manager and Isolation Levels

SQL Server supports all four transaction isolation levels specified by ANSI and ISO: Serializable, Repeatable Read, Read Committed, and Read Uncommitted. (See Chapter 3 and Chapter 12 for details.) To achieve the Serializable isolation level, you must prevent phantoms because the transaction's behavior must be identical to what would have occurred had the transaction run on a single-user system. SQL Server provides serializability, which you can set using SET TRANSACTION ISOLATION LEVEL SERIALIZABLE. To support serializability, SQL Server locks index ranges using a special type of lock called a key-range lock. Such locks are held until the end of the transaction in order to prevent phantoms. If no index exists, the lock manager uses a table lock to guarantee serializability.

The lock manager provides fairly standard two-phase locking services. Although the names are similar, two-phase locking (2PL) and the two-phase commit (2PC) protocol are not directly related other than by the obvious fact that 2PC must use 2PL services. In 2PL, a transaction has a "growing" phase, during which it acquires locks, and a "shrinking" phase, during which it releases locks. To achieve serializability, all acquired locks are held until the end of the transaction and then are dropped all at once.

For a lower isolation level, such as Committed Read, locks can be released sooner—when the use of the object is completed. For example, if a range of data is being queried in the table, there will probably be shared locks outstanding. With Committed Read isolation, a shared lock is released as soon as the scan moves off one piece of data and onto the next. Exclusive locks, on the other hand, are always held until the end of the transaction so that the transaction can be rolled back if necessary.

With Serializable or Repeatable Read isolation, shared locks must be held until the end of the transaction to guarantee that the data that was read will not change or that new rows meeting the criteria of the query cannot be added while the transaction is in progress. Like shared locks, latches are not tied to the boundaries of a transaction because they are used to provide mutual exclusion (mutex) functionality rather than to directly lock data. For example, during a row insert in a table with a clustered index, the nearby index page is latched to prevent other inserts from colliding. The latches are needed to provide mutual exclusion only during long periods of time (that is, periods with more than a few instruction cycles).

Spinlocks

For shorter-term needs, SQL Server achieves mutual exclusion using a latch implemented with a spinlock. Spinlocks are used purely for mutual exclusion and never to lock user data. They are even more lightweight than latches, which are lighter than the full locks used for data and index leaf pages. The spinlock is the only functionality in SQL Server in which processor-specific assembly language is used. A spinlock is implemented in a few lines of assembly language specific to each processor type (such as x86/Pentium or Alpha). The requester of a spinlock repeats its request if the lock is not immediately available. (That is, the requester "spins" on the lock until it is free.)

Spinlocks are often used as mutexes within SQL Server when a resource is usually not busy. If a resource is busy, the duration of a spinlock is short enough that retrying is better than waiting and then being rescheduled by the operating system, which results in context switching between threads. The savings in context switches more than offsets the cost of spinning as long as you don't have to spin too long. Spinlocks are used for situations in which the wait for a resource is expected to be brief (or if no wait is expected).

Deadlocks

A deadlock occurs when two processes are waiting for a resource and neither process can advance because the other process prevents it from getting the resource. A true deadlock is a catch-22 in which, without intervention, neither process can ever progress. When a deadlock occurs, SQL Server intervenes automatically.

NOTE

---

A simple wait for a lock is not a deadlock. When the process that's holding the lock completes, the waiting process gets the lock. Lock waits are normal, expected, and necessary in multiple-user systems.

In SQL Server, two main types of deadlocks can occur: a cycle deadlock and a conversion deadlock. Figure 14-1 shows an example of a cycle deadlock. Process A starts a transaction, acquires an exclusive table lock on the authors table, and requests an exclusive table lock on the publishers table. Simultaneously, process B starts a transaction, acquires an exclusive lock on the publishers table, and requests an exclusive lock on the authors table. The two processes become deadlocked—caught in a "deadly embrace." Each process holds a resource needed by the other process. Neither can progress, and, without intervention, both would be stuck in deadlock forever. You can actually generate the deadlock using the SQL Query Analyzer, as follows:

1. Open a query window, and change your database context to the pubs database. Execute the following batch for process A:

    BEGIN TRAN UPDATE authors SET contract = 0 GO 

2. Open a second window, and execute this batch for process B:

    BEGIN TRAN UPDATE publishers SET city = 'Redmond', state = 'WA' GO 

3. Go back to the first window, and execute this update statement:

    UPDATE publishers SET city = 'New Orleans', state = 'LA' GO 

   At this point, the query should block. It is not deadlocked yet, however. It is waiting for a lock on the publishers table, and there is no reason to suspect that it won't eventually get that lock.

4. Go back to the second window, and execute this update statement:

    UPDATE authors SET contract = 1 GO 

   At this point, a deadlock occurs. The first connection will never get its requested lock on the publishers table because the second connection will not give it up until it gets a lock on the authors table. Since the first connection already has the lock on the authors table, we have a deadlock. One of the processes received the following error message. (Of course, the actual process ID reported will probably be different.)

    Server: Msg 1205, Level 13, State 1, Line 1 Transaction (Process ID 55) was deadlocked on {lock} resources with another process and has been chosen as the deadlock victim. Rerun the transaction. 

Figure 14-2 shows an example of a conversion deadlock. Process A and process B each hold a shared lock on the same page within a transaction. Each process wants to promote its shared lock to an exclusive lock but cannot do so because of the other process's lock. Again, intervention is required.

Figure 14-1. A cycle deadlock resulting from each of two processes holding a resource needed by the other.

Figure 14-2. A conversion deadlock resulting from two processes wanting to promote their locks on the same resource within a transaction.

SQL Server automatically detects deadlocks and intervenes through the lock manager, which provides deadlock detection for regular locks. In SQL Server 2000, deadlocks can also involve resources other than locks. For example, if process A is holding a lock on Table1 and is waiting for memory to become available and process B has some memory it can't release until it acquires a lock on Table1, the processes will deadlock. Threads and communication buffers can also be involved in deadlocks. Latches are not involved in deadlock detection because SQL Server uses deadlock-proof algorithms when it acquires latches. When SQL Server detects a deadlock, it terminates one process's batch, rolling back the active transaction and releasing all that process's locks to resolve the deadlock.

In SQL Server 2000, a separate thread called LOCK_MONITOR checks the system for deadlocks every 5 seconds. The lock monitor also uses an internal counter called a deadlock detection counter to determine whether to check the system for deadlocks more often. The deadlock detection counter starts at a value of 3 and is reset to 3 if a deadlock occurs. If the LOCK_MONITOR thread finds no deadlocks when it checks at the end of its 5-second cycle, it decrements the deadlock detection counter. If the counter has a value greater than 0, the lock manager requests that the lock monitor also check all the locks for a deadlock cycle if a process requests a lock resource and is blocked. Thus, after 20 seconds of not finding any deadlocks, the deadlock detection counter is 0 and the lock manager stops requesting deadlock detection every time a process blocks on a lock. The deadlock detection counter stays at 0 most of the time and the checking for deadlocks happens only at the 5-second intervals of the lock monitor.

This LOCK_MONITOR thread checks for deadlocks by inspecting the list of waiting locks for any cycles, which indicate a circular relationship between processes holding locks and processes waiting for locks. SQL Server attempts to choose as the victim the process that would be the least expensive to roll back, considering the amount of work the process has already done. However, certain operations are marked as golden, or unkillable, and cannot be chosen as the deadlock victim. For example, a process involved in rolling back a transaction cannot be chosen as a deadlock victim because the changes being rolled back could be left in an indeterminate state, causing data corruption.

Using the SET DEADLOCK_PRIORITY LOW | NORMAL statement, you can make a process sacrifice itself as the victim if a deadlock is detected. If a process has a deadlock priority of LOW, it terminates when a deadlock is detected even if it is not the process that closed the loop. However, there is no counterpart SET option to set a deadlock priority to HIGH. As much as you might want your own processes to always come out the winner in a deadlock situation, this feature has not yet been implemented in SQL Server.

NOTE

---

The lightweight latches and spinlocks used internally do not have deadlock detection services. Instead, deadlocks on latches and spinlocks are avoided rather than resolved. Avoidance is achieved via strict programming guidelines used by the SQL Server development team. These lightweight locks must be acquired in a hierarchy, and a process must not have to wait for a regular lock while holding a latch or spinlock. For example, one coding rule is that a process holding a spinlock must never directly wait for a lock or call another service that might have to wait for a lock, and a request can never be made for a spinlock that is higher in the acquisition hierarchy. By establishing similar guidelines for your development team for the order in which SQL Server objects are accessed, you can go a long way toward avoiding deadlocks in the first place.

In the example in Figure 14-1, the cycle deadlock could have been avoided if the processes had decided on a protocol beforehand—for example, if they had decided to always access the authors table first and the publishers table second. Then one of the processes would get the initial exclusive lock on the table being accessed first, and the other process would wait for the lock to be released. One process waiting for a lock is normal and natural. Remember, waiting is not a deadlock.

You should always try to have a standard protocol for the order in which processes access tables. If you know that the processes might need to update the row after reading it, they should initially request an update lock, not a shared lock. If both processes request an update lock rather than a shared lock, the process that is granted an update lock is assured that the lock can later be promoted to an exclusive lock. The other process requesting an update lock has to wait. The use of an update lock serializes the requests for an exclusive lock. Other processes needing only to read the data can still get their shared locks and read. Since the holder of the update lock is guaranteed an exclusive lock, the deadlock is avoided. We'll look in more detail at the compatibility of locks later in this chapter; additional information on deadlocks is presented in Chapter 16.

By the way, the time that your process holds locks should be minimal so other processes don't wait too long for locks to be released. Although you don't usually invoke locking directly, you can influence locking by keeping transactions as short as possible. For example, don't ask for user input in the middle of a transaction. Instead, get the input first and then quickly perform the transaction.