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

There are a couple of problems with the intentionally-buggy CompareAndSwap stored procedure I published yesterday. Let’s take another look:

up_CompareAndSwap

/* 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
    declare @currentValue int
    select @currentValue = Value
    from KeyValuePairs
    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
    update KeyValuePairs
    set [Value] = @p_value
    where [Key] = @p_key

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

What’s wrong with this stored procedure?

The Problem: Atomicity

If we compare the naïve CompareAndSwap stored procedure above to a typical CAS operation, the glaring shortfall is that a true CAS operation is Atomic; to the extent that it is actually implemented by a single compare-exchange instruction at the CPU level.

The naïve CompareAndSwap stored procedure, on the other hand, has a distinct read-modify-write flow, and despite being enclosed in a SQL Transaction, there are no guarantees of atomicity (at the default READ COMMITTED transaction isolation level).

The read operation will acquire a Shared lock on the particular row of the KeyValuePairs table only for the duration of the select statement. After this statement is complete the lock is relinquished, leaving other transactions (including a concurrently executing instance of the same stored procedure!) free to read and modify this row before the update statement has executed.

Unfortunately this undermines the correctness of this procedure, which was to “make sure that nobody else has changed the value while you were busy transforming it”. If two processes execute the stored procedure simultaneously, both select statements will succeed, and then second update statement to execute will immediately overwrite the value stored by the first.

You can convince yourself of this by adding an artificially long delay between the select and subsequent update statement…

if (@p_slow = 1)
    waitfor delay '00:00:10'

…and then executing concurrent queries targeting the same key.

This is bad! We need some way to bring atomicity to the CompareAndSave stored procedure.

Read on in Compare-and-Swap in SQL: Part 3.