I made this configurable so unit tests should not fail if they hit serial errors. We are not doing much concurrency in our tests, and if we are hitting these failures, we should understand them better and solve them case by case.

We can change this if we get too many flakes.

This is the fix. Everything else is just tests

I don't think the build ID is needed.

I didn't try and change the query too much beyond the seq scan.

It looks like it was never used at all:

It might be faster to use wb.build_number, since the query planner has access to the workspace_builds_workspace_id_build_number_key index. That could be why it's having to do the

              ->  Sort  (cost=22.66..22.66 rows=2 width=44)
"                    Sort Key: wb.workspace_id, wb.created_at DESC"

I wondered about that too. I had a specific goal and did not want to start mutating the query too much to solicit feedback on different things.

Can I throw this up in another PR?

yeah, that works

Looks like it's still doing a Seq scan on workspaces

                          ->  Seq Scan on workspaces workspaces_1  (cost=0.00..13.12 rows=1 width=16)
                                Filter: (owner_id = 'b4ed5c8a-725e-482d-b5a7-368a1dd7cd77'::uuid)

Doesn't that mean any update to the workspaces table will still cause a serialization error?

However! I think the query planner takes into account cardinality of the columns relative to the rows in the table, so it might make a different plan in a "real" deployment.

Yes, we still do a seq scan on the workspaces.

To guarantee true serializability PostgreSQL uses predicate locking, which means that it keeps locks which allow it to determine when a write would have had an impact on the result of a previous read from a concurrent transaction, had it run first.

The serializable lock only affects tables (rows) that it written to. The CommitQuota transaction only writes to workspace_builds. I have a test case that writes to the workspaces table, and it does not cause a serialization error.

How do you square this with the observation that a Seq Scan on workspace_builds caused a serialization error? I think the PG docs say Seq Scan locks the entire relation.

Maybe it depends on the number of workspaces and the assumed cardinality.

Experimentally, I am running this:

1. Begin TX
2. GetQuotaConsumedForUser(user, org)
3. UpdateWorkspaceBuildCostByID(workspace, 10)

The TX mode that is important here is SIReadLock.

Predicate locks in PostgreSQL, like in most other database systems, are based on data actually accessed by a transaction. These will show up in the pg_locks system view with a mode of SIReadLock.

What I see my change doing is GetQuotaConsumedForUser used to do:

992-<nil> [granted] workspace_builds/relation/SIReadLock: 
992-<nil> [granted] workspace_builds_pkey/page/SIReadLock: page=1
992-<nil> [granted] workspaces/relation/SIReadLock: 
992-<nil> [granted] workspaces_owner_id_lower_idx/page/SIReadLock: page=1

And now does:

929-<nil> [granted] workspace_builds_pkey/page/SIReadLock: page=1
929-<nil> [granted] workspace_builds_workspace_id_build_number_key/page/SIReadLock: page=1
929-<nil> [granted] workspaces/relation/SIReadLock: 
929-<nil> [granted] workspaces_owner_id_lower_idx/page/SIReadLock: page=1

So we went from a full relation lock on the table to one on the pkey (was there before too) and build number.

The workspaces table still has the same locks, and would be improved by your index suggestions. For this specific error mode, we insert into the workspace_builds table though, so I was honestly not even looking at other tables at this point.

930-<nil> [granted] <nil>/virtualxid/ExclusiveLock: waiting to acquire virtual tx id lock
929- 3848 [granted] <nil>/transactionid/ExclusiveLock: ???
929-<nil> [granted] <nil>/virtualxid/ExclusiveLock: waiting to acquire virtual tx id lock
930-<nil> [granted] pg_locks/relation/AccessShareLock: 
929-<nil> [granted] workspace_builds/relation/AccessShareLock: 
929-<nil> [granted] workspace_builds/relation/RowExclusiveLock: 
929-<nil> [granted] workspace_builds_job_id_key/relation/AccessShareLock: 
929-<nil> [granted] workspace_builds_job_id_key/relation/RowExclusiveLock: 
929-<nil> [granted] workspace_builds_pkey/relation/RowExclusiveLock: 
929-<nil> [granted] workspace_builds_pkey/relation/AccessShareLock: 
929-<nil> [granted] workspace_builds_pkey/page/SIReadLock: page=1
929-<nil> [granted] workspace_builds_workspace_id_build_number_key/relation/RowExclusiveLock: 
929-<nil> [granted] workspace_builds_workspace_id_build_number_key/relation/AccessShareLock: 
929-<nil> [granted] workspace_builds_workspace_id_build_number_key/page/SIReadLock: page=1
929-<nil> [granted] workspaces/relation/AccessShareLock: 
929-<nil> [granted] workspaces/relation/SIReadLock: 
929-<nil> [granted] workspaces_owner_id_lower_idx/relation/AccessShareLock: 
929-<nil> [granted] workspaces_owner_id_lower_idx/page/SIReadLock: page=1
929-<nil> [granted] workspaces_pkey/relation/AccessShareLock: 

993-<nil> [granted] <nil>/virtualxid/ExclusiveLock: waiting to acquire virtual tx id lock
992- 4039 [granted] <nil>/transactionid/ExclusiveLock: ???
992-<nil> [granted] <nil>/virtualxid/ExclusiveLock: waiting to acquire virtual tx id lock
993-<nil> [granted] pg_locks/relation/AccessShareLock: 
992-<nil> [granted] workspace_builds/relation/AccessShareLock: 
992-<nil> [granted] workspace_builds/relation/SIReadLock: 
992-<nil> [granted] workspace_builds/relation/RowExclusiveLock: 
992-<nil> [granted] workspace_builds_job_id_key/relation/AccessShareLock: 
992-<nil> [granted] workspace_builds_job_id_key/relation/RowExclusiveLock: 
992-<nil> [granted] workspace_builds_pkey/relation/RowExclusiveLock: 
992-<nil> [granted] workspace_builds_pkey/relation/AccessShareLock: 
992-<nil> [granted] workspace_builds_pkey/page/SIReadLock: page=1
992-<nil> [granted] workspace_builds_workspace_id_build_number_key/relation/RowExclusiveLock: 
992-<nil> [granted] workspace_builds_workspace_id_build_number_key/relation/AccessShareLock: 
992-<nil> [granted] workspaces/relation/AccessShareLock: 
992-<nil> [granted] workspaces/relation/SIReadLock: 
992-<nil> [granted] workspaces_owner_id_lower_idx/relation/AccessShareLock: 
992-<nil> [granted] workspaces_owner_id_lower_idx/page/SIReadLock: page=1
992-<nil> [granted] workspaces_pkey/relation/AccessShareLock: 

Disclaimer: I recognize the docs suggest these lock patterns can change with table size and memory availability. This is a very small dataset.

Interesting that serializable transactions only interfere with other serializable transactions --- OK for now, but I feel like this puts us on shaky ground.

Today we insert new builds with repeatable read isolation, but do not set the daily_cost. If we ever started setting the cost but didn't up the isolation to serializable, we'd start seeing quota anomalies.

Or, if we ever introduce a new update query on workspaces that runs at serializable isolation, it will start interfering with every quota transaction.

Not necessarily for this PR, but I think we should still aim to remove the Seq Scan on workspaces.

Or, if we ever introduce a new update query on workspaces that runs at serializable isolation, it will start interfering with every quota transaction.

Yes.

Not necessarily for this PR, but I think we should still aim to remove the Seq Scan on workspaces.

I agree. I will make a follow up PR (or issue if it takes to long) to address all these extra concerns.

In this PR I did disable retries, so a unit test is more likely to fail if we hit this (would be a valid flake).

I do not see a way to implement forward thinking protections if someone adds a new serializable TX. So you are correct, a change in the future can break things further, especially because the seq scan on the workspaces.

Interesting that serializable transactions only interfere with other serializable transactions --- OK for now, but I feel like this puts us on shaky ground.

Just to clarify, I specifically meant the error pq: could not serialize access due to read/write dependencies among transactions, which was reported.

There is another error you can get that is not between 2 serializable transactions.

pq: could not serialize access due to concurrent update

Ok, so in the query plan you have now, it's doing this nested loop where it finds the workspace IDs, then for each workspace ID it's doing this bitmap query:

                          ->  Bitmap Heap Scan on workspace_builds wb  (cost=4.16..9.50 rows=2 width=28)
                                Recheck Cond: (workspace_id = workspaces_1.id)
                                ->  Bitmap Index Scan on workspace_builds_workspace_id_build_number_key  (cost=0.00..4.16 rows=2 width=0)
                                      Index Cond: (workspace_id = workspaces_1.id)

That is, it first scans the index to find the pages to load, then scans the pages with the Recheck Cond.

Do you know whether this results in page locks for the transaction, or tuple locks (I'm assuming these are row-level locks)? Page locks have a greater likelihood of catching unrelated transactions.

And, some suggestions:

1. Can we just move the daily_cost directly to the workspace table? We only ever do computations with the most recent cost. If we really needed to keep it on the workspace_build for compatibility or querying history, we could put it in both places, and have this query only look at workspaces. That would remove a join as well. If we built an index of (org_id, owner_id) then we'd also be very unlikely to ever need to Seq scan the workspaces table for quotas.

2. If we don't want to go that far, we could add an index ON workspace_builds (workspace_id, build_number, daily_cost) that would allow the quota query to compute the results right from the index, so it'd never have to a bitmap scan and read whole pages.

The particular locks acquired during execution of a query will depend on the plan used by the query, and multiple finer-grained locks (e.g., tuple locks) may be combined into fewer coarser-grained locks (e.g., page locks) during the course of the transaction to prevent exhaustion of the memory used to track the locks.

I was under the impression it was row-level locks, but I admit that was a result of my experiments with very few rows. The docs seem to imply it could take out larger locks.

Can we just move the daily_cost directly to the workspace table? We only ever do computations with the most recent cost. If we really needed to keep it on the workspace_build for compatibility or querying history, we could put it in both places, and have this query only look at workspaces. That would remove a join as well. If we built an index of (org_id, owner_id) then we'd also be very unlikely to ever need to Seq scan the workspaces table for quotas.

Originally there was a suspicion we were getting this error from different transactions interring with CommitQuota. But the error reported can only occur between 2 serializable transactions, meaning it is CommitQuota interfering with itself.

I thought about moving daily_cost to it's own table entirely, but I'm not sure that would actually improve much.

I think this index + sorting by build number would be a large win: workspace_builds (workspace_id, build_number, daily_cost)

As I look at this query more, I don't see why we need to inner join workspaces again. All the information can be pulled from the latest_build subquery.

If we add the index (org_id, owner_id) on workspaces as well that is another win here.

According to the quote I pulled though, is the goal just to reduce the number of rows touched to prevent the lock from having to go more "coarse" to the page lock? The text implies the behavior depends on the memory availability.

I agree that we don't need to join to workspaces twice.

And yeah, my understanding is that with page locks, updating quota for an unrelated user could cause a serialization error if the builds happen to share a page. So it's undesirable to use page locks if we could get away with finer grained locking.

I realize that postgres can use page locks for memory reasons, and maybe there isn't anything we can do about that, but I'm also wondering whether it automatically uses page locks when it does a bitmap query, rather than tuple locks if we were able to use the index.

I'm pretty sure the query planner uses the cardinality of different columns relative to the table size to determine how to run its query. That means to get reasonable assurance about whether different transactions interfere, we need a realistic number of organizations, users, workspaces, and workspace builds.

PG Docs have this to say

Predicate locks in PostgreSQL, like in most other database systems, are based on data actually accessed by a transaction. These will show up in the pg_locks system view with a mode of SIReadLock. The particular locks acquired during execution of a query will depend on the plan used by the query, and multiple finer-grained locks (e.g., tuple locks) may be combined into fewer coarser-grained locks (e.g., page locks) during the course of the transaction to prevent exhaustion of the memory used to track the locks.

If any page locks are held by our transactions, either as a result of bitmap scans (if that's a thing), or as a result of coalescing finer grained locks, then whether or not transactions serialize without errors could depend on factors not controlled by this test (PostgreSQL config, version, insert timing, etc). That is to say, flaky.

Really, what we want is a realistic amount of data, and then to run repeated transactions, with overlapping pairs chosen randomly, and then to gather statistics on how many pairs interfered with one another. I don't think it makes sense to run these on every CI run. We could even extend to an arbitrary number of simultaneous transactions on different workspaces --- since as deployments grow in size the number of simultaneous builds increases.

You are right. So this does not put anything to bed, however this is a step in the right direction. I would prefer to iterate on this with more PRs.

I added metrics to track and log serialization failures: #15215

So at the very least, in the next release we can begin collecting better frequency metrics on these events.

I can spin up some larger datasets. I think we should take the easy index optimizations you pointed out above.