regression, deadlock in high frequency single-row UPDATE

Hi,

I've discussed this problem on irc a couple of times and think I've
found a regression that plagues our application, introduced in some
version newer than 9.1.9, and still present in 9.3.5.

Multiple instances of the *exact* same single row update:

UPDATE
"z8z6px927zu6qzzbnb5ntgghxg"."access_grants" ag
SET
last_issued=DEFAULT
FROM
"z8z6px927zu6qzzbnb5ntgghxg"."oauth_clients" oc
WHERE
oc.id = ag.client_id
AND ag.entity_name = 'user'
AND ag.entity_id = 129
AND oc.client_id = '3hp45h9d4f9wwtx7cvpus6rdb4s5kb9f'
RETURNING
ag.id
;

if performed with sufficient concurrency will produce a deadlock.

I've attached a snippet of logs, all uncommented lines from
postgresql.conf, and the table definitions of the involved
tables. This first instance of the deadlock appears in line 142; I
left a bunch of lead-in in case it's relevant.

I think this is a regression as we only see the behavior under
postgres 9.3.x (reproduced locally on 9.3.4 and 9.3.5 in a VMWare VM
running Ubuntu 11.04, but also evident in 9.3.3 on Amazon RDS). I am
unable to reproduce in the earlier versions I've been able to test against
(9.0.something and 9.1.9).

To reproduce the problem, I have to fork about 100 api calls against
our application, with the results you see in the logs. The queries in
the log are the *only* activity in the application and database at the
time and I have not filtered the logs at all, other than snipping to a
reasonable window around the problem. I can produce more extensive
logs if needed, but there really is nothing else.

I have not been able to reproduce the deadlock by making concurrent
UPDATEs via what amounts to a bash fork-bomb w/ psql, but I suspect my
methodology might be too crude there. The application is able to spin
up a large number of lightweight threads fairly quickly and presumably
attain the needed level of concurrency.

Thanks,

A