Hints for debugging MySQL InnoDB deadlocks
Deadlocks only occur if two transactions in separate threads compete for the same rows in the database. They usually (but not necessarily) only happen when trying to update or otherwise lock several rows in different order.
Solving deadlocks is potentially complicated, so here are a few pointers:
MySQL should always detect the deadlock right when it happens, and will throw an error to one of the offending threads. This error states the SQL statement that this thread was currently waiting for, and that tried to acquire one of the competing locks.
First, always go through the exception backtrace of your application, and look out for code that might operate on data it actually shouldn't. Chances are, you are not properly scoping something.
To get a rough idea what was actually going on, you can run
SHOW ENGINE INNODB STATUS
This will show you the most recent deadlock, including the two competing queries and a list of the locks held by both transactions. The output is cryptic, though.
If you still cannot see what actually happened, you might need to get better acquainted with MySQLs locking model. While it keeps out of your way usually, it's actually pretty complex. The relevant section of the official manual is pretty good.
MySQL might lock many more rows that you might expect, especially when you do not have proper database indexes for the relevant statement. For updates without indexes, every row in a table gets locked, for example.