Bloqueio inesperado para mesa com chave primária e chave exclusiva

O problema que você está enfrentando acontece porque o MySQL não apenas bloqueia a linha da tabela para um valor que você vai inserir, ele bloqueia todos os valores possíveis entre o id anterior e o próximo id em ordem, então, reutilizando seu exemplo abaixo:

DROP TABLE IF EXISTS foo;
CREATE TABLE `foo` (
  `i` INT(11) NOT NULL,
  `j` INT(11) DEFAULT NULL,
  PRIMARY KEY (`i`),
  UNIQUE KEY `jk` (`j`) 
) ENGINE=InnoDB DEFAULT CHARSET=latin1 ;
INSERT INTO foo VALUES (5,5), (8,8), (11,11);

Suponha que você comece com a transação TX1:

START TRANSACTION;
REPLACE INTO foo VALUES(8,8);

Então, se você iniciar uma transação TX2 , qualquer que seja INSERT ou REPLACE usando um id entre 5 e 11 será bloqueado:

START TRANSACTION;
REPLACE INTO foo VALUES(11,11);

Parece que o MySQL usa esse tipo de bloqueio para evitar o "problema fantasma" descrito aqui:http://dev.mysql.com/doc/refman/5.0/en/innodb-next-key-locking.html , o MySQL usa um "bloqueio de próxima chave", que combina bloqueio de linha de índice com bloqueio de lacuna, isso significa para nós que ele bloqueará muitos ids possíveis entre os ids anteriores e próximos, e bloqueará os ids anteriores e seguintes também .

Para evitar isso tente criar um algoritmo de servidor que insira seus registros para que os registros inseridos em diferentes transações não se sobreponham, ou pelo menos não execute todas as suas transações ao mesmo tempo para que o TX não tem que esperar um ao outro.