PostgreSQL “tuple already updated by self”

Our database seems to be broken, normally it uses about 1-2% of cpu, but if
we run some additional backend services making UPDATE and INSERT queries
for 10M rows table (about 1 query per 3 second) everything is going to hell
(including CPU increase from 2% to 98% usage).

We have decided to debug what's going on, run VACUUM and ANALYZE to learn
what's wrong with db but...

production=# ANALYZE VERBOSE users_user;
INFO: analyzing "public.users_user"
INFO: "users_user": scanned 280 of 280 pages, containing 23889 live
rows and 57 dead rows; 23889 rows in sample, 23889 estimated total
rows
INFO: analyzing "public.users_user"
INFO: "users_user": scanned 280 of 280 pages, containing 23889 live
rows and 57 dead rows; 23889 rows in sample, 23889 estimated total
rows
ERROR: tuple already updated by self

we are not able to finish ANALYZE on ANY of the tables and could not find
any information about this issue. Any suggestions what can be wrong?

PostgreSQL 9.6.8 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.5
20150623 (Red Hat 4.8.5-16), 64-bit

Stackoverflow thread:
https://stackoverflow.com/questions/50450162/postgresql-tuple-already-updated-by-self?noredirect=1#comment87937347_50450162