How can you ensure order of execution in concurrent tasks?

Here is what I am specifically doing:

  1. I have a thread-safe queue
  2. One ‘write’ thread constantly writes to the queue with data that comes from another service
  3. Multiple ‘read’ threads take from the queue, each thread taking several items at once and doing some processing with them
  4. Once each ‘read’ thread processes its current batch of items taken from the queue, it is written to a database

The problem is that items need to be written to the database in step 4 in the same order that they come in step 1.

So for instance if I am processing some events, this rare case could happen:

  1. ‘Entity 1 Created’ event is added to the queue.
  2. Some other events are added to the queue.
  3. ‘Entity 1 Deleted’ event is added to the queue.
  4. Read thread #1 takes its next batch which includes ‘Entity 1 Created’ and a few others
  5. Read thread #2 takes its next batch which includes ‘Entity 1 Deleted’ and a few others
  6. If for any reason read thread #2 reaches the database request sooner than Read thread #1, then the database will get the request for ‘Entity 1 Deleted’ first and since it doesn’t exist yet, it will do nothing, then it will get the ‘Entity 1 Created’ request and it will add an entity and it will remain undeleted.

Is there any way to prevent the problem at step 6. without completely destroying performance.
I could limit the ‘read’ threads to 1, but I am looking for ways to have multiple read threads.