UPDATE query periodically is slower by factor of 5000x
Since your server is under heavy load try to increase its mysql thread concurrency.

Try to set:

innodb_thread_concurrency at 0 (infinite)

innodb_read_io_threads at 64 (Maximum)

innodb_write_io_threads at 64 (Maximum)

Sources:

https://dba.stackexchange.com/a/2948/33029

http://dev.mysql.com/doc/refman/5.5/en/innodb-parameters.html#sysvar_innodb_thread_concurrency