1

I have two tables. One table serves as the queue from which multiple users simultaneously dequeue items one at a time, by flagging the item's row. The other table is joined and used for ordering. It is required that no two users will get the same item from the queue and the queue will not block users, so if user a is busy getting the top item, user b should be able to get the next available item.

The problem is, and i can reproduce, simultaneous dequeue will result in exactly one user to succeed; the others are left empty handed. This happens even when there are multiple candidate items in the queue, so the queue is not empty.

If i remove the order by clause, everything works fine, users can simultaneously dequeue, without blocking each other.

How can i solve the problem, i need the ordering and i need the queue to be non-blocking.

Following are the two tables:

CREATE TABLE DBO.QUEUE 
( 
  QUEUEID    INT IDENTITY(1, 1) NOT NULL PRIMARY KEY, 
  SOMEACTION VARCHAR(100)
);
GO 

DECLARE  @counter INT 
SELECT   @counter = 1 
WHILE (@counter <= 10) 
BEGIN 
    INSERT INTO DBO.QUEUE (SOMEACTION) 
    SELECT 'some action ' + CAST(@counter AS VARCHAR);
    SELECT @counter = @counter + 1 
END

CREATE TABLE DBO.QUEUE_ORDERING 
( 
    QUEUEID    INT IDENTITY(1, 1) NOT NULL PRIMARY KEY, 
    ORDERING_COLUMN INT
);
GO 

DECLARE  @counter INT 
SELECT   @counter = 1 
WHILE (@counter <= 10) 
BEGIN 
    INSERT INTO DBO.QUEUE_ORDERING (ORDERING_COLUMN) 
    SELECT @counter;
    SELECT @counter = @counter + 1 
END

And the testing script is as follows , running them from multiple sessions will reproduce my problem:

BEGIN TRAN TRAN1
DECLARE @QUEUEID INT;
;WITH QUEUE_CTE AS 
(
    SELECT   TOP(1) Q.QUEUEID, Q.SOMEACTION
    FROM     DBO.QUEUE Q WITH (ROWLOCK,READPAST, UPDLOCK)
    JOIN     DBO.QUEUE_ORDERING QR WITH (NOLOCK) 
    ON       QR.QUEUEID = Q.QUEUEID
    ORDER BY QR.ORDERING_COLUMN DESC
)

SELECT @QUEUEID = QUEUEID FROM QUEUE_CTE
PRINT 'processing item # ' + CAST(@QUEUEID AS VARCHAR) 

WAITFOR DELAY '00:00:05' 
COMMIT

Edit:

I've traced down the issue to indices. If i order by the column that is part of the clustered index, then only the relevant row is locked. Otherwise, all rows are locked. I still don't have any idea how to resolve the issue. I need the ordering to be on a column that can not be part of the clustered index. The first image shows the problematic one, you can see that all the rows are locked. In the second one, below, only one row gets locked; order by is on the clustered index column.

This is the problematic version, where all the rows are locked

This is the working one, ordering on clustered index column, only one row gets locked

  • Presumably the test script should have a command that removes a dequeued item from the queue? Also, presumably actual processing takes more than 5 seconds? What happens if an item is dequeued by a user, and processing does not get run? does that impact other actions in the queue? – RDFozz Mar 14 '17 at 14:25
  • @RDFozz In the actual setup, yeah it removes the item from the queue by UPDATE'ing the CTE and setting a status column to flag the row as being dequeued. But the above setup is also valid and demonstrates my problem, if you run the test script from multiple sessions you will see that only one session is able to get a QUEUEID. The actual processing is less than 5 seconds actually, and that's why i don't experience the issue very frequently. However under heavy load of users constantly trying to dequeue from the system, the problem arises. – Selçuk Cihan Mar 15 '17 at 5:59
  • So what i am looking for is a way to be able to concurrently dequeue from a table, based on the ordering on another table's column. In my current setup, concurrent dequeueing does not work and only one of the sessions can dequeue, while all others are unable. – Selçuk Cihan Mar 15 '17 at 6:02
  • So - If the processing does need to be in strict order, the processing for task 2 shouldn't be done until the processing for task 1 is complete. On the other hand, if it's OK for processing of task 1 to fail somehow, with processing for tasks 2, 3, and 4 to proceed anyway, then you want two transactions: One to dequeue, and a second one to process (and, potentially, on failure, to requeue). There would still be an extremely short period of time when the first task would be getting dequeued when others wouldn't be able to get the next task, but that's basically necessary to enforce the order. – RDFozz Mar 15 '17 at 14:29
  • Also - I assume the fact that QUEUEID is an IDENTITY column in both tables is a convenience for testing; It's not generally a good idea to simply assume that identity columns in two different tables will remain in sync with each other. – RDFozz Mar 15 '17 at 14:48
1

It seems that preventing the locking of candidate rows is impossible with an ordering on a column not part of the clustered index.

I came up with a workaround, that seems to solve the problem on the minimal example i provided. I'll do some tests to make sure if it solves the actual production problem.

The idea is to split dequeue operation into two steps. First step respects the ordering and selects a small candidate set; second step ignores any orderings and works on this small set. Thus preventing locking of all the rows.

  • Select more than one rows to be dequeued, without removing the original order by clause. In my case, i changed the CTE to select top(50) rows. And also changed (ROWLOCK, READPAST, UPDLOCK) to read (NOLOCK) as i don't intend to dequeue all these rows, these are all just candidates for the one row i am willing to dqueue. These rows are stored in a table variable, to be joined in the second step, which follows below.

  • Create a new (second) CTE, this time joining with the table variable (which contains at most 50 rows), where clauses will be repeated here to prevent an unwanted row appearing in the result set. The ordering this time is removed from the new CTE to prevent the locking.

Although not critical for my specific needs, there are a couple of issues with this approach:

  • If more than 50 users simultaneously try to dequeue, only the lucky 50 of them will succeed, while others will not be able to get an item.
  • Granularity of the ordering is lost, each item in the candidate list of 50 are treated equally.
  • Again on the ordering, it might be the case that a user dequeues an item which was not in the top 50, but this won't be a totally off target miss; it will be close to the top 50. This is due to the two step approach: things might change and new items might arrive that have higher priority, from the time first CTE runs until the second CTE which performs the actual update. Anyways, it is highly likely that the item dequeued is within the first 50 items.

Test script for the new approach is as follows:

BEGIN TRAN TRAN1
DECLARE @QUEUEID INT;

DECLARE @CANDIDATE_TABLE TABLE (
    QUEUEID INT NOT NULL
);

;WITH CANDIDATE_CTE AS 
(
    SELECT   TOP(50) Q.QUEUEID
    FROM     DBO.QUEUE Q WITH (NOLOCK)
    JOIN     DBO.QUEUE_ORDERING QR WITH (NOLOCK) 
    ON       QR.QUEUEID = Q.QUEUEID
    ORDER BY QR.ORDERING_COLUMN DESC
)
INSERT INTO @CANDIDATE_TABLE (QUEUEID)
SELECT QUEUEID FROM CANDIDATE_CTE;

;WITH QUEUE_CTE AS
(
    SELECT   TOP(1) Q.QUEUEID
    FROM     DBO.QUEUE Q WITH (ROWLOCK, READPAST, UPDLOCK)
    JOIN     @CANDIDATE_TABLE CT
    ON       CT.QUEUEID = Q.QUEUEID
)
SELECT @QUEUEID = QUEUEID FROM QUEUE_CTE
PRINT 'processing item # ' + CAST(@QUEUEID AS VARCHAR) 

WAITFOR DELAY '00:00:05' 
COMMIT

The outputs of two simultaneous sessions are:

(10 row(s) affected)

processing item # 10


(10 row(s) affected)

processing item # 9

  • You might consider the following: From your earlier analysis, if you used columns from the clustered index of the original table, then you got the behavior you wanted, without the blocking. Now, you're writing data to an intermediate table (currently a table variable). What if you used a temporary table instead of a table variable; moreover, what if you made sure that the temporary table included the column from the second table that you are sorting on. You can have a clustered index on a temporary table. I wonder if, doing that way, you could regain the desired ordering in the temp table. – RDFozz Mar 16 '17 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.