Insert only deadlocks

I'm answering my own question here because we finally figured out the problem.

Short Version: We added a third column to the nonclustered index. Deadlocks disappeared.

Long Version:

First, check out James Rowland-Jones' dynamite blog post about lock hashing collision (My explanation will be nowhere close to the quality of his).

From the blog post:

When SQL Server needs to lock a row it creates a hash value that is based on the key values of the table. It is this hash value that is used by the lock manager and means it has a single value to look at when checking to see if a row is already locked.

The lock hash collision occurs when duplicate hash values are generated.

After doing some deeper analysis of many deadlock graphs we noticed that a lot of the WAITRESOURCE Key hash values (the values between the parenthesis) were the same. I started making a short list to keep track:

waitresource="KEY: 5:72057594043629568 (a27543d90a1a)
waitresource="KEY: 5:72057594043629568 (a27543d90a1a)
waitresource="KEY: 5:72057594043629568 (8328314847df)
waitresource="KEY: 5:72057594043629568 (bb0d06c12baa)
waitresource="KEY: 5:72057594043629568 (a27543d90a1a)
waitresource="KEY: 5:72057594043629568 (bb0d06c12baa)
waitresource="KEY: 5:72057594043629568 (8328314847df)
waitresource="KEY: 5:72057594043629568 (bb0d06c12baa)
waitresource="KEY: 5:72057594043629568 (a27543d90a1a)
waitresource="KEY: 5:72057594043629568 (5b39284eef16)
waitresource="KEY: 5:72057594043629568 (a27543d90a1a)
waitresource="KEY: 5:72057594043629568 (8328314847df)
waitresource="KEY: 5:72057594043629568 (5b39284eef16)

Sure enough, we were getting a lot of duplicate hash values from different deadlock graphs. I decided to look into the data in the two columns (col2 & col1) of the unique_index index (where the deadlocks were occurring). All of the table DDL is up above in the question.

The col2 column is always going to have a value of 1-6 for a single value in the col1 column. So this started to make sense. There was a limited variety of data available for SQL to generate hash values from - which explains why we were getting duplicate hash values.

One of the fixes JRJ mentioned in the blog was to add an additional column to the index. This adds some diversity to the data and gives more options for the hashing algorithm. Luckily, we were able to add a create_timestamp column to the index and maintain the same uniqueness we had with the two columns. BOOM! After adding the third column to the index, the deadlocks disappeared.

Sidenote: One of the comments on the blog suggested disabling row locking on the index. We tried this first. It DID get rid of the deadlocks, but led to more locking and cut the overall throughput down by about 40-50% so we didn't like this option for our system. However, on a database with lighter workload, this might work fine.

Hopefully this all makes sense.