Deadlock due to keylock involving 3 processes

Question

I'm trying to determine how this deadlock occurred and what fix I need to do to prevent it from happening again.

I've attached deadlock graph image from SSMS, resolution provided by SSMS image is not good, I apologize.

What is going on here is 3 processes are locked in a cycle, all waiting for the lock on the primary key for the table SecurityObject to be released.

The primary key for this table is clustered and is a composite key containing four columns.

The statement that each process is running is shown below. It is a delete command, deleting all records from table that match on a single column. The column is a GUID identifier that is one of the four columns in the composite clustered primary key.

DELETE FROM SecurityObject WHERE col1 = @val1

Where col1 is one of the four columns in the primary key.

I'm struggling to understand is how this scenario could have happened? How can there be a deadlock scenario for a primary key lock?

Below is the deadlock xml graph:

<deadlock>
    <victim-list>
        <victimProcess id="processaeabf84108"/>
    </victim-list>
    <process-list>
        <process id="processaeabf84108" taskpriority="0" logused="0" waitresource="KEY: 14:72057594041925632 (00f78314b62e)" waittime="1754" ownerId="6629325" transactionname="user_transaction" lasttranstarted="2017-08-04T15:16:55.747" XDES="0xaea526f498" lockMode="X" schedulerid="2" kpid="16620" status="suspended" spid="73" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2017-08-04T15:16:55.747" lastbatchcompleted="2017-08-04T15:16:55.747" lastattention="1900-01-01T00:00:00.747" clientapp=".Net SqlClient Data Provider" hostname="RDXP0165C9JAWIE" hostpid="19084" loginname="REDMOND\RDXP0165C9JAWIE$" isolationlevel="read committed (2)" xactid="6629325" currentdb="14" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
            <executionStack>
                <frame procname="SecurityAuthorization.DB.dbo.spDeleteAllSecurityObjects" line="5" stmtstart="342" stmtend="474" sqlhandle="0x03000e00b56a9938f8fcba00c3a7000001000000000000000000000000000000000000000000000000000000">  DELETE FROM [SecurityObject] WHERE [EnvironmentId] = @EnvironmentI    </frame>
            </executionStack>
            <inputbuf>  Proc [Database Id = 14 Object Id = 949578421]   </inputbuf>
        </process>
        <process id="processaea64a9468" taskpriority="0" logused="0" waitresource="KEY: 14:72057594041925632 (e0caa7da41f0)" waittime="3981" ownerId="6629329" transactionname="user_transaction" lasttranstarted="2017-08-04T15:16:55.750" XDES="0xaea9602408" lockMode="X" schedulerid="1" kpid="14152" status="suspended" spid="76" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2017-08-04T15:16:55.750" lastbatchcompleted="2017-08-04T15:16:55.750" lastattention="1900-01-01T00:00:00.750" clientapp=".Net SqlClient Data Provider" hostname="RDXP0165C9JAWIE" hostpid="19084" loginname="REDMOND\RDXP0165C9JAWIE$" isolationlevel="read committed (2)" xactid="6629329" currentdb="14" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
            <executionStack>
                <frame procname="SecurityAuthorization.DB.dbo.spDeleteAllSecurityObjects" line="5" stmtstart="342" stmtend="474" sqlhandle="0x03000e00b56a9938f8fcba00c3a7000001000000000000000000000000000000000000000000000000000000">  DELETE FROM [SecurityObject] WHERE [EnvironmentId] = @EnvironmentI    </frame>
            </executionStack>
            <inputbuf>  Proc [Database Id = 14 Object Id = 949578421]   </inputbuf>
        </process>
        <process id="processaea686fc28" taskpriority="0" logused="884" waitresource="KEY: 14:72057594041925632 (e0caa7da41f0)" waittime="2105" ownerId="6638253" transactionname="user_transaction" lasttranstarted="2017-08-04T15:16:57.627" XDES="0xaea9460e58" lockMode="X" schedulerid="2" kpid="6528" status="suspended" spid="79" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2017-08-04T15:16:57.627" lastbatchcompleted="2017-08-04T15:16:57.627" lastattention="1900-01-01T00:00:00.627" clientapp=".Net SqlClient Data Provider" hostname="RDXP0165C9JAWIE" hostpid="19084" loginname="REDMOND\RDXP0165C9JAWIE$" isolationlevel="read committed (2)" xactid="6638253" currentdb="14" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
            <executionStack>
                <frame procname="SecurityAuthorization.DB.dbo.spDeleteAllSecurityObjects" line="5" stmtstart="342" stmtend="474" sqlhandle="0x03000e00b56a9938f8fcba00c3a7000001000000000000000000000000000000000000000000000000000000">  DELETE FROM [SecurityObject] WHERE [EnvironmentId] = @EnvironmentI    </frame>
            </executionStack>
            <inputbuf>  Proc [Database Id = 14 Object Id = 949578421]   </inputbuf>
        </process>
    </process-list>
    <resource-list>
        <keylock hobtid="72057594041925632" dbid="14" objectname="SecurityAuthorization.DB.dbo.SecurityObject" indexname="PK__Security__185B78FE57F79F91" id="lockaead1a0680" mode="X" associatedObjectId="72057594041925632">
            <owner-list>
                <owner id="processaea686fc28" mode="X"/>
            </owner-list>
            <waiter-list>
                <waiter id="processaeabf84108" mode="X" requestType="wait"/>
            </waiter-list>
        </keylock>
        <keylock hobtid="72057594041925632" dbid="14" objectname="SecurityAuthorization.DB.dbo.SecurityObject" indexname="PK__Security__185B78FE57F79F91" id="lockae6d468f80" mode="X" associatedObjectId="72057594041925632">
            <owner-list>
                <owner id="processaeabf84108" mode="X"/>
            </owner-list>
            <waiter-list>
                <waiter id="processaea64a9468" mode="X" requestType="wait"/>
            </waiter-list>
        </keylock>
        <keylock hobtid="72057594041925632" dbid="14" objectname="SecurityAuthorization.DB.dbo.SecurityObject" indexname="PK__Security__185B78FE57F79F91" id="lockae6d468f80" mode="X" associatedObjectId="72057594041925632">
            <owner-list>
                <owner id="processaea64a9468" mode="X" requestType="wait"/>
            </owner-list>
            <waiter-list>
                <waiter id="processaea686fc28" mode="X" requestType="wait"/>
            </waiter-list>
        </keylock>
    </resource-list>
</deadlock>  

Here is execution plan of stored procedure:

Answer 1

After further testing, I've managed to isolate the root cause of deadlock scenario to be concurrent calls to both DeleteAll (delete subset of records in table) and Insert (inserts a record that matches the criteria of the DeleteAll).

The exact sequence of events that leads to the deadlock scenario remains unclear, but the issue is solved by setting isolation level to serializable.

It is an acceptable side effect that it will hurt performance (for my scenario, we do not care about this operations performance because these operations are not being waited on, it is a fire and forget process).