Serializable range deadlocks

Question

Help required on an inherited deadlock problem!

The code given below appears to have been written some time back, in an attempt to address contention issues around the assigning of new ID values on a much larger/fatter [IDs] parent table, by first creating the identity values in a smaller [ID_Stub] table. However, the presence of continued deadlocks indicates that this code appears to be causing more problems than it is solving.

We frequently experience deadlocks around an INSERT statement on the following table (table and column names have been obfuscated). The table has no triggers or foreign key dependencies, but has a clustered and a non-clustered index as follows.

CREATE TABLE dbo.ID_Stub (
ID int IDENTITY(1,1) NOT NULL,
IDReference nchar(25) NULL,
AdditionalID int NULL,
CreatedBy int NOT NULL,
CreatedOn datetime NOT NULL,
CONSTRAINT PK_ID_Stub PRIMARY KEY CLUSTERED (ID) WITH 
(
    PAD_INDEX = OFF, 
    STATISTICS_NORECOMPUTE = OFF, 
    SORT_IN_TEMPDB = OFF, 
    IGNORE_DUP_KEY = OFF, 
    ONLINE = OFF, 
    ALLOW_ROW_LOCKS = ON, 
    ALLOW_PAGE_LOCKS = ON, 
    FILLFACTOR = 90
)
);
GO

CREATE NONCLUSTERED INDEX idx_IDReference ON dbo.ID_Stub (IDReference) WITH 
(
    PAD_INDEX = OFF, 
    STATISTICS_NORECOMPUTE = OFF, 
    SORT_IN_TEMPDB = OFF, 
    DROP_EXISTING = OFF, 
    ONLINE = OFF, 
    ALLOW_ROW_LOCKS = ON, 
    ALLOW_PAGE_LOCKS = ON, 
    FILLFACTOR = 70
);
GO

The table contains an average of around 70,000 rows at any one time (a process runs to trim the number of records nightly).

The default instance transaction isolation level is READ COMMITTED, however this is overridden (in the stored procedure where the deadlocks occur) to SERIALIZABLE, along with an implicit transaction. Unfortunately, we cannot consider moving to an optimising locking strategy such as RCSI at this stage.

The whole implicit transaction has been given below for completeness, but the deadlocks are occurring around the final INSERT statement on ID_Stub towards the end.

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN TRANSACTION

-- If a reference has been provided...
IF ISNULL(@IDReference, '') > ''
BEGIN
    IF @ID IS NULL
    BEGIN
        -- Attempt to locate record based on provided reference.
        SELECT @ID = MAX(ID)
        FROM dbo.IDs I
        WHERE I.IDReference = LTRIM(RTRIM(@IDReference))
        AND I.CreatedBy = @CreatedBy
        AND I.AdditionalID = @AdditionalID

        IF @ID IS NULL
        BEGIN
            -- If there is no corresponding record, the subsequent ID creation after the stub failed.
            SET @OriginallyCreated = 
            (
                SELECT MAX(CreatedOn) 
                FROM dbo.ID_Stub IDS 
                WHERE IDS.IDReference = LTRIM(RTRIM(@IDReference))
                AND IDS.CreatedBy = @CreatedBy
                AND IDS.AdditionalID = @AdditionalID
            );

            -- Delete the stub record if created more than 90 seconds ago.
            IF @OriginallyCreated IS NOT NULL
            BEGIN
                IF DATEDIFF(s, @OriginallyCreated, GETDATE()) < 90
                    SELECT @FailureMessage = 'The ID for reference ' + RTRIM(@IDReference) + ' is still being processed.  Please try later.';
                ELSE
                    DELETE dbo.ID_Stub
                    WHERE IDReference = LTRIM(RTRIM(@IDReference))
                    AND CreatedBy = @CreatedBy
                    AND AdditionalID = @AdditionalID;
            END
        END
    END
    ELSE
    BEGIN
        IF NOT EXISTS 
        (
            SELECT ID
            FROM dbo.IDs I
            WHERE I.ID = @ID
            AND I.CreatedBy = @CreatedBy
        )
            SELECT @FailureMessage = 'You have no record stored against the supplied ID (' + RTRIM(CONVERT(Char, @ID)) + ')';
        ELSE
            IF NOT EXISTS 
            (
                SELECT ID
                FROM dbo.IDs I
                WHERE I.ID = @ID
                AND I.IDReference = @IDReference
                AND I.CreatedBy = @CreatedBy
            )
                SELECT @FailureMessage = 'The ID does not match the reference you supplied.';
        END
END
ELSE -- No ID Reference provided.
BEGIN
    IF @ID IS NOT NULL
    BEGIN
        IF NOT EXISTS 
        (
            SELECT ID
            FROM dbo.IDs I
            WHERE I.ID = @ID
            AND I.CreatedBy = @CreatedBy
        )
            SELECT @FailureMessage = 'You have no record stored against the supplied ID (' + RTRIM(CONVERT(Char, @ID)) + ').';
    END
END

IF @FailureMessage <> ''
BEGIN
    ROLLBACK;
    RETURN 1;
END

-- If it's a new submission, create a stub for it.
IF @ID IS NULL
BEGIN
    INSERT dbo.ID_Stub (IDReference, AdditionalID, CreatedBy, CreatedOn)
        VALUES (@IDReference, @AdditionalID, @CreatedBy, GETDATE());

    SELECT @ID = SCOPE_IDENTITY();
END

COMMIT
SET TRANSACTION ISOLATION LEVEL READ COMMITTED;

The XML deadlock report is as follows.

<deadlock>
    <victim-list>
        <victimProcess id="process1e7fd5d8108"/>
    </victim-list>
    <process-list>
        <process id="process1e7fd5d8108" taskpriority="0" logused="336" waitresource="KEY: 30:72057596372844544 (4f8ff66d381b)" waittime="4265" ownerId="1879373839" transactionname="user_transaction" lasttranstarted="2018-12-29T22:19:51.357" XDES="0x1dfe81c9538" lockMode="RangeI-N" schedulerid="6" kpid="2084" status="suspended" spid="182" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2018-12-29T22:19:51.307" lastbatchcompleted="2018-12-29T22:19:51.293" lastattention="1900-01-01T00:00:00.293" clientapp=".Net SqlClient Data Provider" hostname="<obfuscated>" hostpid="3648" loginname="<obfuscated>" isolationlevel="serializable (4)" xactid="1879373839" currentdb="30" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
            <executionStack>
                <frame procname="<obfuscated>" line="640" stmtstart="68006" stmtend="68296" sqlhandle="0x03001e002acd7f07eca57a012ea9000001000000000000000000000000000000000000000000000000000000">  INSERT dbo.ID_Stub (IDReference, AdditionalID, CreatedBy, CreatedOn)       VALUES (@IDReference, @AdditionalID, @CreatedBy, GETDATE();    </frame>
            </executionStack>
            <inputbuf>  Proc [Database Id = 30 Object Id = 125816106]   </inputbuf>
        </process>
        <process id="process1fd327c7c28" taskpriority="0" logused="336" waitresource="KEY: 30:72057596372844544 (4f8ff66d381b)" waittime="4265" ownerId="1879373837" transactionname="user_transaction" lasttranstarted="2018-12-29T22:19:51.357" XDES="0x1e76d97ebd8" lockMode="RangeI-N" schedulerid="3" kpid="9084" status="suspended" spid="208" sbid="0" ecid="0" priority="0" trancount="2" lastbatchstarted="2018-12-29T22:19:51.300" lastbatchcompleted="2018-12-29T22:19:51.293" lastattention="1900-01-01T00:00:00.293" clientapp=".Net SqlClient Data Provider" hostname="<obfuscated>" hostpid="3648" loginname="<obfuscated>" isolationlevel="serializable (4)" xactid="1879373837" currentdb="30" lockTimeout="4294967295" clientoption1="671088672" clientoption2="128056">
            <executionStack>
                <frame procname="<obfuscated>" line="640" stmtstart="68006" stmtend="68296" sqlhandle="0x03001e002acd7f07eca57a012ea9000001000000000000000000000000000000000000000000000000000000">  INSERT dbo.ID_Stub (IDReference, AdditionalID, CreatedBy, CreatedOn)       VALUES (@IDReference, @AdditionalID, @CreatedBy, GETDATE();    </frame>
            </executionStack>
            <inputbuf>  Proc [Database Id = 30 Object Id = 125816106]   </inputbuf>
        </process>
    </process-list>
    <resource-list>
        <keylock hobtid="72057596372844544" dbid="30" objectname="<obfuscated>.<obfuscated>.ID_Stub" indexname="idx_IDReference" id="lock1e566d4a380" mode="RangeS-S" associatedObjectId="72057596372844544">
            <owner-list>
                <owner id="process1fd327c7c28" mode="RangeS-S"/>
                <owner id="process1fd327c7c28" mode="RangeI-N" requestType="convert"/>
            </owner-list>
            <waiter-list>
                <waiter id="process1e7fd5d8108" mode="RangeI-N" requestType="convert"/>
            </waiter-list>
        </keylock>
        <keylock hobtid="72057596372844544" dbid="30" objectname="<obfuscated>.<obfuscated>.ID_Stub" indexname="idx_IDReference" id="lock1e566d4a380" mode="RangeS-S" associatedObjectId="72057596372844544">
            <owner-list>
                <owner id="process1e7fd5d8108" mode="RangeS-S"/>
                <owner id="process1e7fd5d8108" mode="RangeI-N" requestType="convert"/>
            </owner-list>
            <waiter-list>
                <waiter id="process1fd327c7c28" mode="RangeI-N" requestType="convert"/>
            </waiter-list>
        </keylock>
    </resource-list>
</deadlock>  

The query plan for the first statement can be found at the link below.

https://www.brentozar.com/pastetheplan/?id=BkVfC8qbN

Any tips or advice on how best to tackle these deadlocks would be greatly appreciated.

Answer 1

We frequently experience deadlocks around an INSERT statement on the following table ... the stored procedure where the deadlocks occur [uses] SERIALIZABLE

Yes. That is the expected behavior of the SERIALIZABLE isolation level. It's not widely understood, but deadlocks are how SERIALIZABLE enforces the isolation level. It doesn't prevent concurrent sessions from attempting to write conflicting changes; if two sessions read data and then both attempt conflicting changes, a deadlock occurs, and only one write succeeds.

So if you don't want to deal with deadlocks, you're using the wrong concurrency model.

If you simply want to prevent concurrent execution of this transaction, forcing sessions to execute it one-at-a-time, the simplest way is to use an application lock:

BEGIN TRANSACTION
exec sp_getapplock @Resource = 'MyTransaction',  @LockMode = 'Exclusive';
. . .

Answer 2

You have two queries on the deadlock-affected table that have very similar WHERE clauses. This one:

SELECT MAX(CreatedOn) 
FROM dbo.ID_Stub IDS 
WHERE IDS.IDReference = LTRIM(RTRIM(@IDReference))
AND IDS.CreatedBy = @CreatedBy
AND IDS.AdditionalID = @AdditionalID

And this one:

DELETE dbo.ID_Stub
WHERE IDReference = LTRIM(RTRIM(@IDReference))
AND CreatedBy = @CreatedBy
AND AdditionalID = @AdditionalID;

Depending on the data in dbo.ID_Stub, you may be able to reduce the amount of range-locking going on (which is there due to the SERIALIZABLE isolation level, as you mentioned) by adding those other two fields to your nonclustered index key.

CREATE NONCLUSTERED INDEX idx_IDReference 
ON dbo.ID_Stub (IDReference, CreatedBy, AdditionalID) 
WITH 
(
    ...all your other options
);

If you can't address the underlying problem of having to use the SERIALIZABLE isolation level (David Browne has makes a great suggestion with the getapplock procedure), then this could mitigate the problem at least.

You can do before and after testing with those specific queries on their own, checking the locks taken with sp_WhoIsActive @get_locks = 1;) to see if you get different locks taken with the wider index.