Общее для всех mysql:
Проверить какой запрос отрабатывает система если replace то плохо если update или insert on duplicate key update - то ок.
Если в action_history есть индексы кроме примари кей то их скорее всего стоит убрать т.к. вероятно запросы ( сортировки или агрегации) по этим полям будут приводить в любом случае к фулскану и индекс не будет иметь смысла, а при апдейте перестройка будет постоянно всё класть.
Для Maria: убедиться, что в Maria XtraDB не сломана построчная блокировка (всё таки опыт продакшена у марии неё вялый ). Потом вызывает опасение реализация внешнего индекса в таблицах разного типа, возможно это как то может ломать построчную блокировку. Если у вас лок всей таблицы разберитесь откуда, так не должно быть
В общем и целом, поразмышлять что INSERT DELAYED VALUES (1,2,3),(..,..,..),(N,N,N) для записи всех действий будет работать заметно веселее особенно без индексов и в одном потоке, а после некоторых шаманств с агрегацией по крону ещё не будет деградировать от распухания. Что можно про крону парсить access.log (понимать что он не рилтайм), в этом случае будет одна пачка апдейтов допустим раз в минуту и user_id будет заапдейчен только один раз, это будет пожалуй самой простой реализацией задачи упорядочивания и фильтрации потока апдейтов к mysql. Парсинг лога можно заменить на RabbitMQ, или написать своего демона который будет висеть на соке и рулить.
Но смотрите если у вас задача в стиле показать последние 10 пользователей сделавших, что то, то это решается сильно иначе.