Aggresive indexes lead to lock times Using sp_blitzindex from Brent Ozar, I found this particular problem.

The table(s) - (there are many of them, about 80, per business object) - are simple:


User id
Primary key of business object (if PK is composite, there are several columns)


During a particular task, all records of a given user are DELETED and new records are inserted.

delete from OrderTrackingTable where USR_ID = @UsrID


The delete command is created as dynamic SQL inside a stored procedure and executed.

This leads to masive lock wait times on those tables and timeouts.

Has anyone encountered similar problems and anyone has idea for solutions?

sp_blitzindex reports:


  dba.OrderTrackingTable.PK__OrderTrackingTable__BBFBFF17660BA3C2 (1): Page lock waits: 43; total duration: 42 minutes; avg duration: 58 seconds; Lock escalation attempts: 252,312; Actual Escalations: 6.
  Reads: 2,000 (1,960 seek 40 scan) Writes:1,960


DML:

 create table OrderTrackingTable (
    USR_ID      smallint,
    ORDER_ID    int,
    ORDER_ID2   int,
    PRIMARY KEY ( [USR_ID], [ORDER_ID], [ORDER_ID2] )
    )


EDIT

about 2 000 000 records are deleted and inserted
Let's start by looking at the results of sp_blitzindex:

Lock escalation attempts: 252,312; Actual Escalations: 6

What is lock escalation? The first sentence from that page explains it pretty well:

Lock escalation is the process of converting many fine-grain locks into fewer coarse-grain locks, reducing system overhead while increasing the probability of concurrency contention.

Here are a few other important quotes:

The Database Engine does not escalate row or key-range locks to page locks, but escalates them directly to table locks. Similarly, page locks are always escalated to table locks.
When the Database Engine checks for possible escalations at every 1250 newly acquired locks, a lock escalation will occur if and only if a Transact-SQL statement has acquired at least 5000 locks on a single reference of a table.

You're deleting 2 million records so I'm not surprised that you're getting over 5000 locks during your deletes. Less than 0.003% of your lock escalation attempts were successful for this object so there appears to be a lot of concurrent access. It's important to think about what blocking represents for your workload. Blocking can be good if it prevents an end user from getting incomplete or inaccurate results. I'm going to break down the blocking behavior into two categories: it occurs during a maintenance window (end users not on the system) or it occurs outside of a maintenance window.
If it occurs during a maintenance window that's good news for you. You just need to adjust your code and won't need to make difficult decisions about the end user experience. If you have multiple processes all issuing deletes on many tables you have at least the following options:

Delete in small batches instead of doing one large delete. You can delete the top X rows until there aren't any more rows to delete. This performs very well if you are deleting based on the clustered key (you are in your example). As long as your batch size is small enough to avoid
Prevent more than one process from accessing the same table. This could be accomplished through sp_getapplock, by only running one process (may not be practical for your maintenance window), or through some other method.
Partition by user id. This is a bit of a nuclear option but you can use partition switching to load the new data in very quickly with minimal locking. Tinyint has a range up to 32767 and SQL Server only supports up to 15000 partitions per table so this may not work for you. Partitioning has a lot of other side effects so consider making this change very carefully.

If this blocking is occurring while end users are accessing the system and you cannot defer the updates to your data until your maintenance window then I recommend approaching the problem based on what your end users should experience. I get the impression that you're deleting data from many different tables for a user id. What should happen if an end user runs a query after the delete but before the insert has completed? Is it acceptable to show partial data?  What should happen if some of the tables in the query have been updated with the new data but not all? Is it better to make them wait until all of the data has been loaded or to show them the previous data?
I can't answer those questions so some combination of the techniques listed above may work for you. Another one worth considering is to defer doing the deletes. Instead of doing deletes you could do inserts instead. You could add a version column to all of your primary keys and load in new data as needed. You could also have a metadata table that lists the version of the data that should be used for each user id as well (that can be helpful if you want an end user to wait until all data has been loaded). During a maintenance window you can delete the old rows. Of course, this will require you to rewrite many, if not all, of your queries and to recreate the primary keys on all of your tables.
Hopefully that gets you on the right track. Resolving your issue may be as simple as deleting in smaller chunks to avoid escalating locks to the table level but I urge you to think carefully about what data end users will see as a result of doing that.