Why does this query result in deadlock?
The FOREIGN KEY user_chat_messages_user_chat_id_foreign is the cause of your deadlock, in this situation.

Fortunately, this is easy to reproduce given the information you've provided.

Setup

CREATE DATABASE dba210949;
USE dba210949;

CREATE TABLE user_chats
(
    id INT(10) unsigned PRIMARY KEY NOT NULL AUTO_INCREMENT,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL
);

CREATE TABLE user_chat_messages
(
    id INT(10) unsigned PRIMARY KEY NOT NULL AUTO_INCREMENT,
    user_chat_id INT(10) unsigned NOT NULL,
    from_user_id INT(10) unsigned NOT NULL,
    content VARCHAR(500) NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
    CONSTRAINT user_chat_messages_user_chat_id_foreign FOREIGN KEY (user_chat_id) REFERENCES user_chats (id)
);

insert into user_chats (id,updated_at) values (1,NOW());


Note that I removed the user_chat_messages_from_user_id_foreign foreign key as it references the users table, which we don't have in our example. It is not important for reproducing the problem.

Reproducing the deadlock

Connection 1

USE dba210949;
START TRANSACTION;
insert into `user_chat_messages` (`user_chat_id`, `from_user_id`, `content`) values (1, 2, 'dfasfdfk');


Connection 2

USE dba210949;
START TRANSACTION;
insert into `user_chat_messages` (`user_chat_id`, `from_user_id`, `content`) values (1, 2, 'dfasfdfk');


Connection 1

update `user_chats` set `updated_at` = '2018-06-28 08:33:14' where `id` = 1;


At this point, Connection 1 is waiting.

Connection 2

update `user_chats` set `updated_at` = '2018-06-28 08:33:14' where `id` = 1;


Here, Connection 2 throws a deadlock


  ERROR 1213 (40001): Deadlock found when trying to get lock; try
  restarting transaction


Retrying without the foreign key

Let's repeat the same steps, but with the following table structures. The only difference this time around is the removal of the user_chat_messages_user_chat_id_foreign foreign key.

CREATE DATABASE dba210949;
USE dba210949;

CREATE TABLE user_chats
(
    id INT(10) unsigned PRIMARY KEY NOT NULL AUTO_INCREMENT,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL
);

CREATE TABLE user_chat_messages
(
    id INT(10) unsigned PRIMARY KEY NOT NULL AUTO_INCREMENT,
    user_chat_id INT(10) unsigned NOT NULL,
    from_user_id INT(10) unsigned NOT NULL,
    content VARCHAR(500) NOT NULL,
    created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL,
    updated_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP NOT NULL
);

insert into user_chats (id,updated_at) values (1,NOW());


Reproducing the same steps as before

Connection 1

USE dba210949;
START TRANSACTION;
insert into `user_chat_messages` (`user_chat_id`, `from_user_id`, `content`) values (1, 2, 'dfasfdfk');


Connection 2

USE dba210949;
START TRANSACTION;
insert into `user_chat_messages` (`user_chat_id`, `from_user_id`, `content`) values (1, 2, 'dfasfdfk');


Connection 1

update `user_chats` set `updated_at` = '2018-06-28 08:33:14' where `id` = 1;


At this point, Connection 1 executes, instead of waiting like before.

Connection 2

update `user_chats` set `updated_at` = '2018-06-28 08:33:14' where `id` = 1;


Connection 2 now is the one waiting now, but it has not deadlocked.

Connection 1

commit;


Connection 2 now stops waiting and executes its command.

Connection 2

commit;


Done, with no deadlock.

Why?

Let's look at the output of SHOW ENGINE INNODB STATUS

------------------------
LATEST DETECTED DEADLOCK
------------------------
2018-07-04 10:38:31 0x7fad84161700
*** (1) TRANSACTION:
TRANSACTION 42061, ACTIVE 55 sec starting index read
mysql tables in use 1, locked 1
LOCK WAIT 5 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
MySQL thread id 2, OS thread handle 140383222380288, query id 81 localhost root updating
update `user_chats` set `updated_at` = '2018-06-28 08:33:14' where `id` = 1
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 3711 page no 3 n bits 72 index PRIMARY of table `dba210949`.`user_chats` trx id 42061 lock_mode X locks rec but not gap waiting
Record lock, heap no 2 PHYSICAL RECORD: n_fields 5; compact format; info bits 0
 0: len 4; hex 00000001; asc     ;;
 1: len 6; hex 00000000a44b; asc      K;;
 2: len 7; hex b90000012d0110; asc     -  ;;
 3: len 4; hex 5b3ca335; asc [&lt; 5;;
 4: len 4; hex 5b3ca335; asc [&lt; 5;;

*** (2) TRANSACTION:
TRANSACTION 42062, ACTIVE 46 sec starting index read
mysql tables in use 1, locked 1
5 lock struct(s), heap size 1136, 2 row lock(s), undo log entries 1
MySQL thread id 3, OS thread handle 140383222109952, query id 82 localhost root updating
update `user_chats` set `updated_at` = '2018-06-28 08:33:14' where `id` = 1
*** (2) HOLDS THE LOCK(S):
RECORD LOCKS space id 3711 page no 3 n bits 72 index PRIMARY of table `dba210949`.`user_chats` trx id 42062 lock mode S locks rec but not gap
Record lock, heap no 2 PHYSICAL RECORD: n_fields 5; compact format; info bits 0
 0: len 4; hex 00000001; asc     ;;
 1: len 6; hex 00000000a44b; asc      K;;
 2: len 7; hex b90000012d0110; asc     -  ;;
 3: len 4; hex 5b3ca335; asc [&lt; 5;;
 4: len 4; hex 5b3ca335; asc [&lt; 5;;

*** (2) WAITING FOR THIS LOCK TO BE GRANTED:
RECORD LOCKS space id 3711 page no 3 n bits 72 index PRIMARY of table `dba210949`.`user_chats` trx id 42062 lock_mode X locks rec but not gap waiting
Record lock, heap no 2 PHYSICAL RECORD: n_fields 5; compact format; info bits 0
 0: len 4; hex 00000001; asc     ;;
 1: len 6; hex 00000000a44b; asc      K;;
 2: len 7; hex b90000012d0110; asc     -  ;;
 3: len 4; hex 5b3ca335; asc [&lt; 5;;
 4: len 4; hex 5b3ca335; asc [&lt; 5;;

*** WE ROLL BACK TRANSACTION (2)


You can see that transaction 1 has a lock_mode X on the PRIMARY key of user_chats, while transaction 2 has lock_mode S, and is waiting for lock_mode X. That is a result of it obtaining a shared lock first (from our INSERT statement), and then an exclusive lock (from our UPDATE).

So, what is happening is Connection 1 grabs the shared lock first, and then Connection 2 grabs a shared lock on the same record. That's fine, for now, as they are both shared locks.

Connection 1 then tries to upgrade to an exclusive lock to perform the UPDATE, only to find that connection 2 has a lock already. Shared and exclusive locks don't mix well, as you can probably deduce by their name. That is why it waits after the UPDATE command on Connection 1. 

Then Connection 2 tries to UPDATE, which requires an exclusive lock, and InnoDB goes "whelp, I'm never going to be able to fix this situation on my own", and declares a deadlock. It kills off Connection 2, releases the shared lock that Connection 2 was holding, and allows Connection 1 to complete normally.

Solution(s)

At this point, you are probably ready to stop with the yap yap yap and want a solution. Here are the my suggestions, in order of my personal preference.

1. Avoid the update altogether

Don't bother with the updated_at column in the user_chats table at all. Instead, add a composite index on user_chat_messages for the columns (user_chat_id,created_at).

ALTER TABLE user_chat_messages
ADD INDEX `latest_message_for_user_chat` (`user_chat_id`,`created_at`)


Then, you can obtain the most recent updated time with the following query.

SELECT MAX(created_at) AS created_at FROM user_chat_messages WHERE user_chat_id = 1


This query will execute extremely quickly due to the index, and doesn't require you to store the latest updated_at time in the user_chats table as well. This helps avoid data duplication, which is why it is my preferred solution.

Make sure to dynamically set the id to the $message-&gt;getUserChatId() value, and not hard coded to 1, as in my example.

This is essentially what Rick James is suggesting.

2. Lock the tables to serialize requests

SELECT id FROM user_chats WHERE id=1 FOR UPDATE


Add this SELECT ... FOR UPDATE to the start of your transaction, and it will serialize your requests. As before, make sure to dynamically set the id to the $message-&gt;getUserChatId() value, and not hard coded to 1, as in my example.

This is what Gerard H. Pille is suggesting.

3. Drop the foreign key

Sometimes, it is just easier to remove the source of the deadlock. Just drop the user_chat_messages_user_chat_id_foreign foreign key, and problem solved.

I don't particularly like this solution in general, as I love data integrity (which the foreign key provides), but sometimes you need to make trade offs.

4. Retry the command after deadlock

This is the recommended solution for deadlocks in general. Just catch the error, and retry the entire request. However, it is easiest to implement if you prepared for it from the start, and updating legacy code may be difficult. Given the fact that there are easier solutions (like 1 and 2 above) is why this is my least recommended solution for your situation.