A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.
4 edited tags
| link
    Post Closed as "Needs more focus" by Laurenz Albe, John Eisbrener, Marcello Miorelli, Marco, Colin 't Hart
    Mod Moved Comments To Chat
3 added 2055 characters in body; edited title
source | link

Is In the following inventory system, is it necessarypossible to force row locks to avoid deadlock in this scenarioand ensure it works as intended?

Suppose 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 inventory restrictionsallowed reservations for aneach object globally,in general as well as per-user (i.e user. max of 1000 ofFor example, an object Amay be restricted to have 1000 reserved overall, and maxwith a maximum of 10 of that object A reserved per user).

The global inventory table is uniquely keyed on {ObjectID}[ObjectID], and the personal inventory table is uniquely keyed on {UserID[UserID, ObjectID}. The primary key is the only index on each tableObjectID]. (I think that's important for exclusive row-level locks

  • 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 be correctly functioning). The personalreserve inventory table may also be sharded onto another databasefor 3 objects looks like this. Some objects have restrictions, so the transaction may be distributed with the global inventory table on one database and the personal inventory table on another databasewhile others do not.

Global[
 Inventory Table:  {ObjectID}: 'A', CountQuantityToReserve: 1},
Personal Inventory Table:  {UserIDObjectID: 'C', ObjectIDQuantityToReserve: 2, GlobalMax: 1000, PersonalMax: 10}, 
 Count   {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.

Suppose a request arrives to reserveAtomic reservation is achieved by starting a quantity of 1 for objects B, Atransaction, and C. This will be a two-step transaction where all relevant recordsthen updating rows in the global inventory table are updated first, andfor all relevant recordsobject ids, in the personal inventory table are updated afterwardsascending order.

First, I begin a transaction.An update statement for an object without restrictions looks like this:

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

Next, I sort theAn update statement for an object IDs to ensure row-level locks are taken out in the same order by concurrent operations, so deadlock cannot occur.with a restriction looks like this:

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

Step 1: Lock/update desired Similar update statements are later used to update and lock rows in the globalpersonal inventory table. For each ordered object ID, I'm lockingwith the corresponding recordaddition of [UserID] in the global inventorypredicate (specifically, a join with a UserIDs table by running an update statement to increment its count by the desired quantity to reserve). Because a transaction is active, an

Updating the rows in order (by object id) effectively takes out exclusive lock is takenrow locks on those rows andthe records in that order, which are then held throughfor the endremainder of the transaction (I believe this happens, so othereven without the HOLDLOCK hint for update statements). Other concurrent transactions will block waiting for the first transaction to commit the updated rows before theythe others can obtain a lockthe locks required to update thethose rows.

Assuming that's all correct, at this point in Because the transaction, exclusive row locks should be held for records A, B, and C in the global inventory table.

Step 2: I want to update records in the personal inventory table. The hope here is that because no other transaction should be holding locks to global records A, B, and C, and all global locks are taken out before any personalin ascending order, once all locks are taken in this transactionthe set have been acquired, we can infer that guarantees that no other transaction should hold locks to the personal inventory records ofholds any user for objects A, B, and C. We infer that's the case, because they would have first had to take out theof those exclusive locks for the global records, which we just. This is a well established cannot be the case for any other transactionfact. Locking order matters (and unlocking order does not). Just ask Linus: https://yarchive.net/comp/linux/lock_ordering.html

My first question is, in order for that last paragraph to hold true, must I force the database engine to take out row-level locks to ensure its correctness and avoid potential deadlockwill these update statements work as intended?

To avoid deadlock 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 to be surethe correct lock hints?

Since we've established that no other concurrent transaction hasholds any of the personal inventory rows locked that I intend to update, and in order to guarantee thatlocks the current one holds, I have to ensureit logically follows that no other transaction has inadvertently locked thosewould 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 the only wayI need to guarantee that isforce the database engine to ensure onlyuse row-level level locks are taken outwhen updating the personal inventory rows as well. The reason is, becauseif it escalates to a page-level lock in another transaction, it could inadvertently lock records I intendthat happen to updatebe 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'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. This second transaction enters in the phase where it updates personal inventory records for 1000 different users for records associatedeach is working with object Deither. However, if itthis 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.

My main concern are whether forcing such row In other words, page-level locks is even possibledestroy the established locking order, especially at scale if I'mby locking thousands of rows (eunrelated records in an arbitrary order.g

Updating records in the personal inventory table is a bit more complex, because it has to update multiple rows. reserving quantities for 4 objectsThe update statements will still run for eachone object id at a time, but it will be joined with a temporary table that establishes the set of 1000 users)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, which would hold 4000 distinctso 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 andany 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, one after anothersimultaneously, with minimal lock contention. This will result in transactionalatomic, high-throughput inventory reservations, without having to worry about managing transactions at the application-level, which ultimately would be more complex and less reliable.

A follow up question mightPage locks would be, acceptable if forcing row-level locks will not perform well, is there was a way to force an index to put different partsone part of a composite key to reside on different data pages, but I don't think that's possible. For example, if I instead keyed the personal table on ({ObjectID, UserID), is there any way to force SQL Server} I'd have to ensure pages are fragmented so each page contains datarecords for at most a single ObjectIDobject id (and many users)?.

Is it necessary to force row locks to avoid deadlock in this scenario?

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

I have two inventory tables, one for global inventory and one for personal inventory, because I have to enforce maximum inventory restrictions for an object globally, as well as per-user (i.e. max of 1000 of object A reserved overall, and max of 10 of object A reserved per user).

The global inventory table is keyed on {ObjectID} and the personal inventory table is keyed on {UserID, ObjectID}. The primary key is the only index on each table. (I think that's important for exclusive row-level locks to be correctly functioning). The personal inventory table may also be sharded onto another database, so the transaction may be distributed with the global inventory table on one database and the personal inventory table on another database.

Global Inventory Table: {ObjectID}, Count
Personal Inventory Table: {UserID, ObjectID}, Count

Suppose a request arrives to reserve a quantity of 1 for objects B, A, and C. This will be a two-step transaction where all relevant records in the global inventory table are updated first, and all relevant records in the personal inventory table are updated afterwards.

First, I begin a transaction.

Next, I sort the object IDs to ensure row-level locks are taken out in the same order by concurrent operations, so deadlock cannot occur.

Step 1: Lock/update desired rows in the global inventory table. For each ordered object ID, I'm locking the corresponding record in the global inventory table by running an update statement to increment its count by the desired quantity to reserve. Because a transaction is active, an exclusive lock is taken on those rows and held through the end of the transaction, so other concurrent transactions will block waiting for the first transaction to commit the updated rows before they can obtain a lock to update the rows.

Assuming that's all correct, at this point in the transaction, exclusive row locks should be held for records A, B, and C in the global inventory table.

Step 2: I want to update records in the personal inventory table. The hope here is that because no other transaction should be holding locks to global records A, B, and C, and all global locks are taken out before any personal locks are taken in this transaction, we can infer that no other transaction should hold locks to the personal inventory records of any user for objects A, B, and C. We infer that's the case, because they would have first had to take out the locks for the global records, which we just established cannot be the case for any other transaction.

My question is, in order for that last paragraph to hold true, must I force the database engine to take out row-level locks to ensure its correctness and avoid potential deadlock?

To avoid deadlock, I have to be sure no other concurrent transaction has any of the personal inventory rows locked that I intend to update, and in order to guarantee that, I have to ensure that no other transaction has inadvertently locked those records. I think the only way to guarantee that is to ensure only row-level locks are taken out, because a page-level lock in another transaction could inadvertently lock records I intend to update.  

For example, suppose a concurrent transaction locks global record D, so it seems totally unrelated to the first transaction working with A, B, and C. None of the global or personal inventory records should overlap, so there should be no lock contention. This second transaction enters the phase where it updates personal inventory records for 1000 different users for records associated with object D. However, if it 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 records for B and D, and neither transaction can proceed because each one has locked pages that the other is waiting for.

My main concern are whether forcing such row-level locks is even possible, especially at scale if I'm locking thousands of rows (e.g. reserving quantities for 4 objects for each of 1000 users), which would hold 4000 distinct row-level locks. I'm concerned more about correctness than performance here. Using database row locks is going to be many orders of magnitude faster than and other locking solution that involves multiple round trips to the server. By using database locks, multiple concurrent transactions can complete quickly, one after another, with minimal lock contention. This will result in transactional, high-throughput reservations, without having to worry about managing transactions at the application-level, which ultimately would be more complex and less reliable.

A follow up question might be, if forcing row-level locks will not perform well, is there a way to force an index to put different parts of a composite key on different data pages. For example, if I instead keyed the personal table on (ObjectID, UserID), is there any way to force SQL Server to ensure pages are fragmented so each page contains data for at most a single ObjectID (and many users)?

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:

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

2 deleted 3 characters in body
source | link

A follow up question might be, if forcing row-level locks will not perform well, is there a way to force an index to put different parts of a composite key on different data pages. For example, if I instead keyed the personal table on (ObjectID, UserID), is there any way to force SQL Server to ensure pages are fragmented by so each page contains data for at most a single ObjectID (and many users)?

A follow up question might be, if forcing row-level locks will not perform well, is there a way to force an index to put different parts of a composite key on different data pages. For example, if I instead keyed the personal table on (ObjectID, UserID), is there any way to force SQL Server to ensure pages are fragmented by so each page contains data for at most a single ObjectID (and many users)?

A follow up question might be, if forcing row-level locks will not perform well, is there a way to force an index to put different parts of a composite key on different data pages. For example, if I instead keyed the personal table on (ObjectID, UserID), is there any way to force SQL Server to ensure pages are fragmented so each page contains data for at most a single ObjectID (and many users)?

1
source | link