Deleting large amounts of cascading records with minimal locking
I had the same issue.  Deleting in batches helps, but still tends to lock up my Percona cluster because of the delay in replicating the delete to other nodes.

In my case, most of the cascaded deletes did not exist in practice - there could in theory be records in those tables, but in practice there weren't for most of the tables.  So what I did was query the schema to find which tables the cascade could affect, then for each item to delete:


SET FOREIGN_KEY_CHECKS=0;
Query the affected tables to find if there were any affected records; if so, delete them.
Delete the main record.
SET FOREIGN_KEY_CHECKS=1;


This meant that the actual locking was very much reduced.  In my case this enabled me to delete about an order of magnitude faster.

This approach is not atomic, but won't leave the tables in a bad state if there's a crash.