The precise root cause was Postgres statistics on a given table were completely off. This caused, as you well pointed out, that a frequent query that normally takes 1-2ms started timing out (timeout is 15s). This caused an error spike and slow down across most of the read-only replicas.
There's correlation with the reindex operation, which affected the index that provided the necessary speedup on the operation, and the incident.
The reindex creates a concurrent index on the table and drops the old index afterwards. How it precisely affected the statistics is not determined yet.
There's more information on the incident issue. FYI: https://gitlab.com/gitlab-com/gl-infra/production/-/issues/2...
Update: the cause seems to be determined by the fact that the index was a functional index. In this case, table statistics are not applicable and the index requires its own statistics, which can only be generated via ANALYZE (manual or via autovacuum, ofc).
Disclaimer: I work at OnGres, and we help GitLab with PostgreSQL Support.