Improvement in minimizing lockhash key collisions in SQL Server 2008R2 and its impact on concurrency

Improvement in minimizing lockhash key collisions in SQL Server 2008R2 and its impact on concurrency

Rate This
  • Comments 4

Another improved functionality in SQL Server 2008 R2

I am posting this on behalf of Juergen Thomas who has been with SQL Server PM team from 12+ years and is an expert in SAP. 

Juergen>> In this article I’d like to talk about another improvement we made to SQL Server 2008 R2. The improvement pretty much is not noticed since it is buried deep into the SQL Server Engine. There also is nothing to tune about it.  It is about the hash key algorithm which is used by SQL Server in its Lock Manager. So let’s step and explain what SQL Server does and what impact this change in SQL Server 2008 R2 has.

How does the locking work in SQL Server?

Unlike some other database vendors, there is a logical component to SQL Server’s Lock Manager. SQL Server uses a lockhash value to represent a lock on the lock structure in the SQL Server Lock Manager instead of using the physical description to a row, page or a table. The lockhash value then is kept in memory. This design was driven by major considerations like:

·         No locking information to be stored on the page containing the resource. This eliminates additional IO or any space penalty on the page due to locking.

·         Since the key to a row could be as large as 900 bytes, using the real key values would have inflicted larger memory consumption. Especially with applications running long transactions and holding hundreds of thousands of locks. Therefore one needed to seek for a possibility to have a lock value which would not exceed a few bytes and fixed in size for better memory management

The solution to this problem was found when designing SQL server 7.0 in 1996 and 1997 by using the key of the row and apply a hash algorithm to it which then results in a 6 byte long lockhash value. This value is stored as resource description. Added to this is HoBT ID (B-Tree ID). If an another row in the same B-Tree needs to be locked, the hash value for the key of the row gets calculated and then compared to the hash values already stored as granted or waiting locks in order to see whether a lock on this row already exists.  This mechanism worked sufficiently well for many years

Issues appearing on the horizon

Using a hash algorithm to calculate a value out of keys  does have one small disadvantage:

·         Depending upon the # of rows, structure of the primary key, the data distribution and the complexity of the hashing algorithm, one can get hash collisions. For example,  one calculated lockhash value can lock more than one row within a B-Tree.

 

How can we see what the hash key value for a lock held on a key is?

Let’s demonstrate this with an example.

CREATE TABLE test

(a VARCHAR(3) NOT NULL, b VARCHAR(8) NOT NULL, c VARCHAR(5) NOT NULL,

d integer NOT NULL)

GO

 

CREATE UNIQUE CLUSTERED INDEX ucl ON test(a,b,c)

GO

 

begin transaction

INSERT test VALUES('150','00001082','00345',1)

 

Now let’s perform this query:

select resource_type,resource_database_id, resource_description, resource_associated_entity_id,request_mode, request_type, request_status from sys.dm_tran_locks where resource_type = 'KEY'

 

The result will look like:

resource_type

resource_database_id

resource_description

resource_associated_entity_id

request_mode

request_type

request_status

KEY

5

(5c017ccf0cbf)   

72057594038976512

X

LOCK

GRANT

 

As resource_description you can see the value our hash key algorithm did calculate out of the input of the three key values ‘150’, ‘00001082’ and ‘00345’. The column ‘resource_associated_entity_id’ is the id of the B-Tree. It also finds usage in the system views sys.partitions and sys.allocation_units and can be used to get to the object_id or the name of the table the B-Tree belongs to.

Now let’s insert another row into the very same table with another Query Window. We’ll try to insert with this command:

begin transaction

INSERT test VALUES('150','00024855','00012',4)

 

To our surprise the insert of this row seems to be blocked and doesn’t come back (please note that the transaction of the first Query Window with the first row inserted still is open). Executing the same query against sys.dm_tran_locks gives us this result:

resource_type

resource_database_id

resource_description

resource_associated_entity_id

request_mode

request_type

request_status

KEY

5

(5c017ccf0cbf)   

72057594038845440

X

LOCK

GRANT

KEY

5

(5c017ccf0cbf)    

72057594038845440

X

LOCK

WAIT

 

As this shows we are basically blocked with inserting the second row. The X-Lock could not be acquired because the hash algorithm used did calculate the very same hash value for the 3 key column values of the second row to be inserted.

This issue demonstrates an undesired side effect of using hash algorithms to calculate lock values. However fortunately in most customer workloads, we rarely encountered this issue with customers. One of the reasons certainly is that the row colliding under the same hash value usually are far apart. E.g. if we lock a row of a general ledger table out of the current month in the company code of the corporation and there is a collision with a row of last year in the company code of one of the small subsidiaries, there will be no practical effect of such a hash collision. However, where we encountered a negative side effect of this was in large data loads. There it is all about getting tables of sometimes Terabyte in size loaded as fast as possible. Therefore one often splits up the loads in the export phase already. Importing those packages now in parallel (sometimes up to two dozen packages against one table) we did encounter blocking locks as well as deadlocks between those load streams.

 

How does SQL Server 2008 R2 resolve this issue?

In SQL Server 2008 R2, the hashing algorithm calculating the lockhash value was rewritten. The goals to make it more complex on the one side to avoid collisions without compromising the performance. We analyzed a lot of ISV customer database plus some other other customer databases to come up with a hash algorithm which used comparable CPU cycles but produced a better distribution of hashed values. In all the cases that we tested,  we found a dramatic reduction of hash key collisions. For example,   in 3 billion row tables where we had more than hundred thousand collisions with the old algorithm. Also, in many cases, we eliminated the hash collisions completely. With all the test data we used, the probability to get hash collisions is further lowered by a factor of 15,000 using the new hashing algorithm. After more than extensive tests for months and months, the new hash algorithm got released with the November CTP of SQL Server 2008 R2. For the example  above, we don’t see any hash collision anymore with SQL Server 2008 R2 as the table below proves. This is not to say that collision will not occur but it will be very unlikely.

Result of running of performing this query against scenario described above:

select resource_type,resource_database_id, resource_description, resource_associated_entity_id,request_mode, request_type, request_status from sys.dm_tran_locks where resource_type = 'KEY'

 

resource_type

resource_database_id

resource_description

resource_associated_entity_id

request_mode

request_type

request_status

KEY

5

(4b729e3b9a50)                                                                                                                                                                                                                                                 

72057594038845440

X

LOCK

GRANT

KEY

5

(7bd75c434bae)                                                                                                                                                                                                                                                 

72057594038845440

X

LOCK

GRANT

 

As one can see, in the case of SQL Server 2008 R2 (November CTP) the second insert didn’t get blocked anymore since the lockhash value in the column resource_description differs.

Leave a Comment
  • Please add 1 and 7 and type the answer here:
  • Post
  • With Simple  example I'm able to understang the concept easily.

    Thanks

  • This should be a real benefit to improving concurrency in many workloads.

  • We are still witnessing some bogus collisions during our batch imports. Couldn't you use chaining to resolve these hash collisions properly, e.g. when they occur examine the full keys?

  • From Dev

    No hashing algorithm is collision free, crc64 only reduces the probability of collisions.

    As for the suggestion to fallback to a full key comparison - Although the suggestion makes logical sense, there would be performance and design implications to implemented it in practice. The lock manager is unaware of the actual entity it is locking, hence wants each lockresource to be represented using a unique lockres structure. We could augment this lockres structure to contain the actual set of keys, but this will

    1. Increase the amount of memory consumed by the lockmanager 2. Looking up whether a transaction has a particular lock or not involves comparing all these key columns, hence making it slow 3. The lock manage would need to have the knowledge (or contain callback methods) to enable it to compare these key columns. (Type, collation information etc will all be needed to do the comparison)

Page 1 of 1 (4 items)