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