Consulta Simple UPDATE com (algumas vezes) longos tempos de consulta

Question

Eu corro um servidor MySQL dedicado (2 núcleos, 16GB de RAM) que atende 100-200 pedidos por segundo. Está ficando lento durante o tráfego de pico e eu tenho dificuldade em otimizar o servidor. Então, estou procurando algumas ideias agora que fiz muitos ajustes de Innodb com o "TUNING PRIMER"

A consulta que agora gera a maioria das consultas lentas é a seguinte (veja o resultado do mysqldumpslow):

Count: 433  Time=3.40s (1470s)  Lock=0.00s (0s)  Rows=0.0 (0),
  UPDATE user_sessions SET tid='S' WHERE idsession='S'

Estou muito surpreso por ter tantas consultas longas para uma consulta tão simples sem bloqueio. Fyi, a tabela é InnoDB e tem 14.000 linhas. Ele contém todas as sessões ativas no site com aproximadamente 10 UPDATE e SELECT por segundo. Aqui está a sua estrutura:

CREATE TABLE 'user_sessions' (
 'personid' mediumint(9) NOT NULL DEFAULT '0',
 'ip' varchar(18) COLLATE utf8_unicode_ci NOT NULL,
 'idsession' varchar(32) COLLATE utf8_unicode_ci NOT NULL,
 'datum' date NOT NULL DEFAULT '0000-00-00',
 'tid' time NOT NULL DEFAULT '00:00:00',
 'status' tinyint(4) NOT NULL DEFAULT '0',
 KEY 'personid' ('personid'),
 KEY 'idsession' ('idsession'),
 KEY 'datum' ('datum')
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

Alguma idéia?

EDITAR

Aqui está o que eu recebo quando ativo o perfil nessa consulta:

Status               Duration
starting             0.000049
checking permissions 0.000009
Opening tables       0.000028
System lock          0.000010
init                 0.000079
Updating             0.030386
end                  0.000007
Waiting for query cache lock 0.000005
end                  0.002654
query end            0.000035
closing tables       0.000012
freeing items        0.000022
logging slow query   0.000005
cleaning up          0.000005