Наверно можно и без очередей:
1) Кладете проверку на существование записи и вставку в одну транзакцию;
2) Вначале транзакции вешаете блокировку на чтение\запись таблицы или строки;
3) Снимаете блокировку когда все сделаете.
Таким образом при наличии блокировки потенциальная конкурентная вставка не выполнится параллельно, правда не знаю что касается производительности, быстрым поиском я не нашел есть ли в Mysql именованные блокировки, которые бы действовали только в рамках блокировок с таким же именем, надо поискать, но можно вешать блокировку на строку, этого может быть достаточно.
Материалы:
https://habrahabr.ru/post/46542/
https://stackoverflow.com/questions/6621303/how-do...