-4

I want to atomically reserve inventory for N objects for M users.

I have two inventory tracking tables, one for global inventory and one for personal inventory.

  • Global Inventory Table Columns: ObjectID uniqueidentifier, Count int
  • Personal Inventory Table Columns: UserID nvarchar(64), ObjectID uniqueidentifier, Count int

There are two tables, because I have to enforce maximum allowed reservations for each object in general as well as per user. For example, an object may be restricted to have 1000 reserved overall, with a maximum of 10 of that object per user.

The global inventory table is uniquely keyed on [ObjectID], and the personal inventory table is uniquely keyed on [UserID, ObjectID].

  • The primary key is the only index on each table, so locks are only taken on the rows and never some other index key.
  • The global inventory table will always reside on a single database.
  • The personal inventory table may be sharded across multiple databases, so the transaction that updates the global and one or more personal tables may be distributed.
  • This "reserve inventory" transaction is the only transaction that will ever be performed on these tables.

A sample request to reserve inventory for 3 objects looks like this. Some objects have restrictions, while others do not.

[
    {ObjectID: 'A', QuantityToReserve: 1},
    {ObjectID: 'C', QuantityToReserve: 2, GlobalMax: 1000, PersonalMax: 10},
    {ObjectID: 'B', QuantityToReserve: 5}
]
  • Such a request to reserve inventory for multiple objects has to be completed atomically, and must succeed for all objects.
  • A complete set of locks is always taken out on the global table before attempting to take any on the personal table.

Atomic reservation is achieved by starting a transaction, and then updating rows in the global inventory table first, for all object ids, in ascending order.

An update statement for an object without restrictions looks like this:

UPDATE [GlobalInventory] WITH (ROWLOCK, XLOCK, HOLDLOCK)
SET [Count] = [Count] + @QuantityToReserve
WHERE [ObjectID] = @ObjectID

An update statement for an object with a restriction looks like this:

UPDATE [GlobalInventory] WITH (ROWLOCK, XLOCK, HOLDLOCK)
SET [Count] = [Count] + @QuantityToReserve
WHERE [ObjectID] = @ObjectID AND ([Count] + QuantityToReserve) < @GlobalMax

Similar update statements are later used to update and lock rows in the personal inventory table, with the addition of [UserID] in the predicate (specifically, a join with a UserIDs table).

Updating the rows in order (by object id) effectively takes out exclusive row locks on the records in that order, which are then held for the remainder of the transaction (I believe this happens, even without the HOLDLOCK hint for update statements). Other concurrent transactions will block waiting for the transaction to commit the updated rows before the others can obtain the locks required to update those rows. Because the row locks are taken out in ascending order, once all locks in the set have been acquired, that guarantees that no other transaction holds any of those exclusive locks. This is a well established fact. Locking order matters (and unlocking order does not). Just ask Linus: https://yarchive.net/comp/linux/lock_ordering.html

My first question is, will these update statements work as intended? This question has multiple parts, such as will the predicate identify the rows to update and will the predicate hold true by the time the exclusive row lock is held (i.e. just before the rows are updated)? Do I have the correct lock hints?

Since we've established that no other transaction holds any of the locks the current one holds, it logically follows that no other transaction would be attempting to update or lock any of the records with those same object ids in the personal inventory table.

At this point, I think I need to force the database engine to use row level locks when updating the personal inventory rows as well. The reason is, if it escalates to a page lock, it could inadvertently lock records that happen to be on that page, but don't belong to the set of object ids the transaction is working with.

For example, suppose a concurrent transaction locks global record 'D', so it seems totally unrelated to the first transaction working with records for objects A, B, and C. None of the global or personal inventory records should overlap, so there should be no lock contention in the personal inventory records each is working with either. However, if this concurrent transaction takes out page-level locks in the personal inventory table, and some of those pages for D happen to contain records for object B, transaction D could inadvertently hold page locks for records belonging to both D and B. Likewise, the first transaction may also hold page-level locks that contain some records for B and D, and neither transaction can proceed because each one has locked pages that the other is waiting for. In other words, page-level locks destroy the established locking order, by locking unrelated records in an arbitrary order.

Updating records in the personal inventory table is a bit more complex, because it has to update multiple rows. The update statements will still run for one object id at a time, but it will be joined with a temporary table that establishes the set of user ids.

UPDATE pi WITH (ROWLOCK, XLOCK, HOLDLOCK)
SET [Count] = [Count] + @QuantityToReserve
FROM PersonalInventory pi
INNER JOIN @UserIDs uids on pi.UserID = uids.UserID
WHERE [ObjectID] = @ObjectID AND ([Count] + QuantityToReserve) < @PersonalMax

My second question is, will this update statement with a join to a UserIDs table, take the right exclusive row locks, only the records actually updated as a result of satisfying the predicate?

It's critical to the correct functioning of this system that this is the case, so if it's not, I'd like to know, and I'd like to know why. If the expected locks aren't held, what locks are held. Please assume that I have DISABLED lock escalation on the table.

Other Notes

I was concerned with whether forcing such row-level locks was even possible, but then I discovered there's a table option to disable lock escalation. I'm concerned more about correctness than performance here. Using database row locks is going to be many orders of magnitude faster than any other locking solution that involves multiple round trips to the server. Using sp_getapplock also will not work, because it would redundantly perform the same function that the locks on the global inventory table achieve, while simultaneously doing nothing to prevent the page-lock creep I just mentioned. By using database, row-level locks, multiple concurrent transactions can complete quickly, simultaneously, with minimal lock contention. This will result in atomic, high-throughput inventory reservations, without having to worry about managing transactions at the application-level, which ultimately would be more complex and less reliable.

Page locks would be acceptable if there was a way to force one part of a composite key to reside on different data pages, but I don't think that's possible. For example, if I keyed the personal table on {ObjectID, UserID} I'd have to ensure each page contains records for at most a single object id (and many users).

  • 1
    Comments are not for extended discussion; this conversation has been moved to chat. – Paul White says GoFundMonica Sep 4 at 7:59
  • The question isn't too broad. Too detailed, perhaps, but not broad. It's specifically asking about whether a "single update statement" works as intended, which happens to depend on implementation details of SQL Server locks, hence this requires an expert. The example (which you often insist we have) adds a lot of context, but it doesn't make the question broad. The entire question could have been answered with a single statement that I identified in an answer below. – Triynko Sep 5 at 15:53
12

My first question is, will these update statements work as intended?

Very likely, but not certain.

SQL Server guarantees it will honour the semantics of the query, and the level of ACID compliance determined by the effective isolation level. Beyond that, all is implementation detail (including what type(s) of locks are taken, when, and for how long they are held).

It is certainly likely that the optimizer will choose a singleton-seek trivial plan for the given statements and schema description. During execution, the storage engine will most probably acquire very similar locks to those intended, but there are no guarantees.

will the predicate identify the rows to update

That is the semantic of the statement, so yes.

will the predicate hold true by the time the exclusive row lock is held (i.e. just before the rows are updated)?

Exactly when the exclusive lock is acquired depends on implementation details, and can be affected by hints and plan shape. SQL Server does guarantee that once a particular row is identified as qualifying for an update, it will remain unmodified by other concurrent transactions until the current transaction completes. Both example update statements identify a single row, so questions around set membership and race conditions in the face of concurrent update activity do not arise.

Do I have the correct lock hints?

  • ROWLOCK: This hint (not 'directive'), combined with disabling lock escalation for the table, ought to produce row level locking in all circumstances I can think of. Note in passing that locks are never escalated to the page level. SQL Server would almost certainly choose row locking for the given statements and schema without this hint.

  • XLOCK: SQL Server normally takes update locks on the access method identifying rows to update, converting to exclusive just before the modification (if necessary). Taking update locks (instead of shared) is a defence against a common cause of conversion deadlock. Update locks are compatible with shared locks, but not other update locks. For a single-operator update, the engine normally takes an exclusive lock straight away. The XLOCK hint does not seem to perform a useful function in this scenario, but may be harmless.

  • HOLDLOCK: This is a synonym for the SERIALIZABLE isolation level table hint. It does not affect how long locks are held per se. The object with this hint will be accessed using serializable isolation semantics, regardless of the otherwise effective current isolation level. The impact of this on physical locking can be complex, especially when combined with other isolation-relevant hints like XLOCK. For example, an update might take Range S-U without the XLOCK hint, but Range X-X with it. Exclusively locking the half-open range below the key of interest may reduce concurrency more than the shared lock would, in general. As an aside: Attempting to reserve inventory for a non-existent ObjectID seems like an odd operation, but serializable isolation would protect the surrounding range with Range X-X locks anyway.

The extra hints seem to have little justification to my mind. Running the simple updates unhinted with a serializable transaction appears to provide as many guarantees as are available. Accessing each row in a consistent order on the same access method should provide adequate protection from deadlocks on the global inventory table.

My second question is, will this update statement with a join to a UserIDs table, take the right exclusive row locks, only the records actually updated as a result of satisfying the predicate?

This is much less certain, and hard to assess fully. The optimizer has real choices to make about the execution plan for this statement. For example, it may choose between hash, merge, or nested loops joins, scans or seeks, as well as deciding whether to invoke parallelism, semi join reduction via bitmap filtering, nested loops prefetching and batch sort...among many possibilities. Not all internal details are reflected in the execution plan representation visible to end users.

Note in particular that even if the optimizer chooses the sort of iterative execution plan implicit in the question text, it may choose either table as the driver. Perhaps the most obvious cause of 'problems' would be the optimizer choosing to fully scan the personal inventory table, and seek into the table variable.

It would be possible to constrain the optimizer further using yet more hints (e.g. LOOP JOIN, FORCE ORDER, FORCESEEK and so on), but not every possibility can be covered this way. I would choose an alternate approach.

8

Since we've established that no other transaction holds any of the locks the current one holds, it logically follows that no other transaction would be attempting to update or lock any of the records with those same object ids in the personal inventory table.

You should know that this:

no other transaction holds any of the locks the current one holds

is technically not established.

In some cases, more than one row lock can be taken for a single update of one value.

Even if every key/row value is unique.

For overhead reasons, SQL Server hashes the rows to lock. The 6-byte hash value for each row can be exposed using the undocumented %%lockres%% function.

Depending upon the # of rows, structure of the primary key, the data distribution and the complexity of the hashing algorithm, one can get hash collisions. For example, one calculated lockhash value can lock more than one row within a B-Tree

Source

Hash collisions are possible. When? it depends™.

More information on the probability of %%lockres%% collisions can be found in an article by Remus Rusanu.

An important part of this excellent article:

So the SQL %%lockres%% hash will produce two records with the same hash, with a 50% probability, out of the table, any table, of only 16,777,215 records

In other words, when SQL Server identifies a row to lock, it doesn't lock the physical row, rather it enters the hash value corresponding to that row in an internal table of locks. Because other rows could have that same hash value, those other, unrelated rows, are effectively locked, because they share the same lock hash and would therefore appear locked by another transaction.

An example that illustrates these hash collisions:

SET NOCOUNT ON;

CREATE TABLE #HashCollision(ID UNIQUEIDENTIFIER  PRIMARY KEY NOT NULL);


DECLARE @i int = 1
WHILE @i <= 33
BEGIN
INSERT INTO #HashCollision WITH(TABLOCK)
(ID)
SELECT TOP(1000000)  1M
NEWID()
FROM master..spt_values spt1
CROSS APPLY master..spt_values spt2
SET @i+=1;
END

--33m rows

SELECT %%lockres%% as lockress
INTO #temp
FROM #HashCollision;


select COUNT(DISTINCT lockress)
from #temp;
--when I tested, the count was 32999999. 
--Looks like it fluctuates between 32999999 and 32999998 on additional tests

SELECT lockress FROM 
#temp
group by lockress
having COUNT(*)  > 1;

When I ran this example, I had one duplicate lockres value: (45642dc72eae)

The uniqueidentifier values that had the same %%lockres%% hash value are

51300BD6-EE42-435F-92D3-A23AB965C6D6 & A9FEFC2E-3BA9-4C56-8F32-A69811C95092

On a second check, I inserted the values in an actual table, found another lockres value, (a006f9bf8d84) and tried to update this table in two query windows with the two hash values returned:

Transaction 1

BEGIN TRAN
UPDATE dbo.HashCollision
SET ID = NEWID() 
WHERE ID = 'D616D1C1-D609-448F-A1F4-5F959AB344F3';

Transaction 2 (blocked)

BEGIN TRAN
UPDATE dbo.HashCollision
SET ID = NEWID() 
WHERE ID = '0B6846D9-3E47-4B75-9F7B-89CA0B090524';

until transaction #1 was rolled back or committed.

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