Sorry for getting back late. The algorithm used for deadlock detection is rather simple. I am not sure if it has a name (please let me know if you know!), but I’ll try to describe it.

It needs two simple data structures, a writers table, and a lookup table. The writers table contains the writer threads that have successfully owned/locked a resource. The lookup table contains information about which operations are blocked on others. It is only populated if resources can be acquired instantly.

The writers table is used as follows: every writer that successfully acquires a resource is entered into an internal writers table. When a writer releases a resource, it is removed from that writers table.

The lookup table is used as follows: whenever either a reader or a writer cannot instantly acquire a resource, it will be entered into another lookup table, together with the id of the writer that blocks it. If that lookup table is otherwise empty nothing more will happen, and once the writer that blocks is finished, the waiting operations can proceed. If however the lookup table is not empty, we’ll check if the writer we’re waiting for is itself blocked by other operations. That is done recursively until we either find a cycle (then it’s a deadlock situation) or are done (in this case it’s not a deadlock and eventually there’ll be progress).

Example scenario: we have two threads T1 and T2 which want to perform operations on resources R1 and R2 in this chronological order:

1) T1 write-locks R1
2) T2 write-locks R2
3) T1 wants to read-lock R2
4) T2 wants to read-lock R1

In this scenario T1 would block at 3) because it waits for T2, and T2 would block at 4) because it waits for T1.

With the above algorithm that would result in
1) T1 is entered into writers table for R1
2) T2 is entered into writers table for R2
3) T1 is entered into lookup table for R2, waiting for T2 (the writer that currently owns R2). lookup table is recursively traversed starting at T2. T2 itself does not block on anything else, so everything’s still fine
4) T2 is entered into lookup table for R1, waiting for T1 (the writer that currently owns R1). lookup table is recursively traversed starting at T1. this lookup will find that T1 is itself blocked on T2 (which is ourselves). So we have a cycle and a deadlock!

That should also work with more that two concurrent operations.

To answer the second question: whenever a deadlock is detected using the above algorithm, the transaction that detects the deadlock is getting rolled back.

I hope this helps.

Right. However, even with document-level locks you will be able to produce deadlocks when transactions run concurrently and want to modify the same documents in different order. Easy to reproduce with row-level locking engines such as InnoDB, and unavoidable if you really want to run transactions in parallel and have consistency. An alternative is of course to always abort a transaction that cannot get a (document-level) lock instantly and let the client retry.