(See Compare-and-Swap in SQL: Part 1 and Part 2 to set the context for this post.)

So we’ve concluded that the naïve implementation of up_CompareAndSwap is woefully inadequate in achieving its main goal: performing an atomic compare-and-swap operation.

The Succinct Solution: Fancy Update Statements

One way to resolve this is to make our implementation more succinct. The programmatic CAS operation is implemented by a single compare-exchange instruction at the CPU level; maybe we can implement the core of up_CompareAndSwap with a single compare-update SQL statement?

This would mean combining the select-check-update stages of the original stored procedure into a single update statement. Something along these lines:

update KeyValuePairs
set [Value] = @p_value
where [Key] = @p_key
    and [Value] = @p_comparand

Then we can test @@ROWCOUNT to find out if the row was updated or not, but sadly this is not enough. Even in this simple scenario, we need more information to fulfil the return codes contract:

-- RETURNS: 0 if KeyValuePairs was updated;
--          1 if KeyValuePairs was not updated;
--          2 if the specified p_key was not found.

If @@ROWCOUNT is 0 we can’t know if this was because the Key comparison failed (in which case we should return 2) or if it was because the Value part of the comparison failed (in which case we should return 1). There isn’t enough information.

Fortunately it turns out that the set clause can do a lot more than just assign values to columns. We can go ahead and extract the current value of the column before we update it, right in the set clause:

-- Optimistically update KeyValuePairs
update KeyValuePairs
set @currentValue = [Value],
    [Value] = @p_value
where [Key] = @p_key

Instead of checking the current value against @p_comparand in the where clause, we go ahead and update it optimistically.

Now we know that if @@ROWCOUNT is 0, it must be because that Key was not found in the table, so we can return 2:

if (@@ROWCOUNT != 1)
begin
    raiserror('Key <%s> was not found.', 16, 0, @p_key)
    commit transaction
    return 2
end

If the Key was found, and we did update a row, we can retrospectively validate the previous value against @p_comparand:

-- Validate the old value against p_comparand and rollback if necessary
if (@previousValue != @p_comparand)
begin
    print 'Comparand does not match. Value was not updated.'
    rollback transaction
    return 1
end

If the values don’t match, we undo our update by rolling back the transaction, and return 1 to signal that the entry was not updated.

One downside to this approach is that our optimistic update may be visible to readers using READ UNCOMMITTED isolation (e.g. via the NOLOCK hint) before being rolled back. Such readers could observe a phantom value “that never was”, but then again, that is exactly what you bargain for when you start to ignore transaction isolation boundaries.

The Explicit Solution: Locking Hints

My final variant on this stored procedure is to explicitly decorate the initial select statement with a locking hint. Our problem before was that the select statement only acquires a ‘Shared’ lock for the duration of the statement, and then releases this lock and leaves the row open to change.

We can use the HOLDLOCK hint to ensure that the ‘Shared’ lock is held until the end of the transaction. This protects us from having someone else update the row after we’ve read it and before we’ve updated it. However, this is not enough: Another instance of this same procedure could run concurrently and read the current, unchanged, value. Its validation would pass, and it would attempt to update the value, only then would it be blocked and wait for the ‘Shared’ lock to be released. After we write our new value, this concurrently executing instance would immediately overwrite it with its new value! That’s no good.

So we need something stronger. The XLOCK hint will force our ‘Shared’ lock to be upgraded to an ‘Exclusive’ lock, which will prevent anyone else from reading the value. This solves the problem noted above, but is a little too restrictive. We don’t have any problem with anyone reading the value, so long as they’re not reading it with the intent of later updating it.

SQL Server has another lock mode called ‘Update’, which communicates this exact intent of “reading with an intent to update”. We can use the UPDLOCK hint to acquire this ‘Update’ lock as part of the select statement. This will prevent anyone else acquiring an ‘Exclusive’ or ‘Update’ lock in the interim between our select and update statements. (A concurrently executing instance of the same procedure would attempt to acquire an ‘Update’ lock when reading the data, and will therefore be blocked on its select statement until our transaction is complete.) Any other read-only process, however, is still free to read the current value during this time. Once we reach the update statement the ‘Update’ lock will automatically be upgraded to an ‘Exclusive’ lock, and at this point both readers and writers would be blocked from accessing that row until the transaction completes.

If we want to ensure that this ‘Update’ lock is only acquired on the unique row in question, rather than an entire data page from the table, we can additionally use the ROWLOCK hint. This will ensure that if there is high contention for updating the KeyValuePairs table we won’t be needlessly serialising updates to separate rows.

/* Procedure up_CompareAndSwap

 Compares the value stored for p_key in the KeyValuePairs table
 against the p_comparand value.
   * If they match, the new p_value is stored in KeyValuePairs.
   * If they do not match, KeyValuePairs is not updated.

 Returns: 0 if KeyValuePairs was updated;
          1 if KeyValuePairs was not updated;
          2 if the specified p_key was not found.
*/
create procedure up_CompareAndSwap 
    @p_key nvarchar(50),
    @p_value int,
    @p_comparand int
as
begin
    begin transaction

    -- Read current value and hold on to an Update lock on the row
    declare @currentValue int
    select @currentValue = Value
    from KeyValuePairs with (UPDLOCK, ROWLOCK)
    where [Key] = @p_key
    
    if (@@ROWCOUNT != 1)
    begin
        raiserror('Key <%s> was not found.', 16, 0, @p_key)
        commit transaction
        return 2
    end

    -- Compare to the expected value (and return if they don't match)
    if (@currentValue != @p_comparand)
    begin
        print 'Comparand does not match. Value was not updated.'
        commit transaction
        return 1
    end

    -- Update to the new value
    -- We hold an Update lock on this row, so it couldn't have changed
    -- since we read it. The Update lock will be upgraded to 'Exclusive'
    update KeyValuePairs
    set [Value] = @p_value
    where [Key] = @p_key

    print 'Value was updated successfully.'
    commit transaction
    return 0
end
GO

This solution has the advantage of being simpler to implement, and simpler to retrofit to the an existing procedure — all I had to change was the locking hints for the initial select statement. It also feels cleaner to have done the necessary checks before updating the row, rather than optimistically updating it ahead of the checks, and potentially rolling it back subsequently.

The End

I hope you’ve enjoyed learning a little bit about SQL Server with me. As you can probably tell, I’m a bit of a novice when it comes to this subject matter. If there are any mistakes in what I’ve said above (or in the previous posts in this series), please let me know in the comments. Thanks!