3 of 4 added 2055 characters in body; edited title

In the following inventory system, is it possible to force row locks to avoid deadlock and ensure it works as intended?

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:

SET [Count] = [Count] + @QuantityToReserve
WHERE [ObjectID] = @ObjectID

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

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.

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).