[nexus] Audit transactions which may have incorrect serialization assumptions

[smklein]

As highlighted by #6229 (comment) , the following situation may be a problem with CockroachDB:

• Interactive transaction starts, issues a SELECT for one or more rows from the database
• The value of that row is accessed and considered, somehow
• Concurrently, that row is modified by another operation (concurrent transaction, CTE, UPDATE, DELETE, etc).
• The original transaction commits without updating the original row, but assuming it has not been changed.
• No error is returned, the transaction completes "successfully", even though the assumption of immutability of that row has been violated.

In this scenario, a row was read by a transaction, and modified before the transaction committed. According to Cockroachdb's documentation, this is legal:

“CockroachDB doesn’t allow stale reads”... “No stale reads” means that, once a write transaction committed, every read transaction starting afterwards will see it.

Note that in this situation, the read transaction started before the subsequent write transaction, so the read was not considered stale. That being said, the value read by the transaction did get modified before it was committed.

This issue tracks taking a look at our usage of interactive transactions, for the following pattern:

1. A SELECT statement is issued without a corresponding FOR UPDATE lock
2. The result of that SELECT statement influences the rest of the transaction, in some way. Examples could be: Influencing a conditional in Rust code, using the result to populate a subsequent UPDATE or INSERT, etc.
3. The original rows being SELECT-ed are not themselves modified by the transaction.
4. If the transaction makes the assumption that the SELECT-ed rows must not be modified before the transaction calls COMMIT, then this is a potential problem.

An example of this issue was that highlighted within #6229, where we had roughly the following problem:

• In a Transaction: SELECT the latest blueprint target, confirms it is equal to value X. Perform a database modification, assuming that the SELECT-ed blueprint target has not been modified.
• Concurrently, another operation may occur, which modified the "latest target blueprint".

In this example, the following may occur:

• Txn: SELECT the blueprint target, sees value "X"
• Another operation modified the blueprint target to "X + 1"
• Txn: Modify the DB, issue COMMIT. No error is observed, it is not known that the target changed mid-operation.

[smklein]

Address Lot deletion uses a transaction to read from address_lot_rsvd_block before updating other tables. It seems possible that another row could be inserted into address_lot_rsvd_block while the transaction is currently running, which could result in address_lot_rsvd_block entries existing while the address_lot entry is soft deleted and address_lot_block are hard-deleted.

[smklein]

BGP configuration deletion uses a transaction to check for entries in the sps_bgp_peer_config table before deciding to soft delete an entry in the bgp_config table.

If it's possible for entries to be added to sps_bgp_peer_config concurrently with this transaction, then an old value could be read (indicating it's not in use, when it actually is).

[smklein]

BGP announce set creation and update both perform the following sequence of updates in a transaction:

• Read from bgp_announce_set
• Insert into bgp_announce_set if and only if the set doesn't already exist
• Perform many modifications of bgp_announcement

In the case where bgp_announce_set already exists, this transaction will read that row, but not attempt to lock nor modify it. It seems plausible that a concurrent writer could delete bgp_announce_set before these transactions commit, which would result in bgp_announcement being populated for a bgp_announce_set that has been removed.

[smklein]

Blueprint deletion performs the following operations:

• SELECT from the bp_target table, check that blueprint_id doesn't match
• Then update a bunch of tables other than bp_target

It seems possible that a blueprint is made the active blueprint (by updating bp_target ) after our initial SELECT. Even though we read a stale value -- and rely on the assumption that blueprint_id is not the current target -- this assumption may not be valid, but we'll proceed with deletion anyway.

[smklein]

Updating DNS seems to use a pattern of:

• SELECT the latest version from the DNS group
• Check that it equals our "last known version"
• INSERT a new version as a separate row in this table

There's even a comment about a TOCTTOU not being an issue on "read before write" because of the SERIALIZABLE level:

       // This looks like a time-of-check-to-time-of-use race, but this
       // approach works because we're inside a transaction and the
       // isolation level is SERIALIZABLE.

I've tried to repro this with two CockroachDB shells:

# Shell 1:
CREATE TABLE versions (id UUID PRIMARY KEY, n integer, name TEXT);
INSERT INTO VERSIONS (id, n, name) values (gen_random_uuid(), 1, 'first');
INSERT INTO VERSIONS (id, n, name) values (gen_random_uuid(), 2, 'second');

# Shell 2:
BEGIN;
SELECT * FROM VERSIONS ORDER BY n DESC LIMIT 1;

# Shell 1:
INSERT INTO VERSIONS (id, n, name) values (gen_random_uuid(), 3, 'outside txn');

# Shell 2:
INSERT INTO VERSIONS (id, n, name) values (gen_random_uuid(), 3, 'inside txn');
COMMIT;

I am seeing this result in a serialization error, so I think this transaction is actually working as-is. I think this may be due to us INSERT-ing into the same table we SELECT-ed from?

EDIT: I also tried writing a unit test for this case, and am not observing a serialization error, there, which indicates this TOCTTOU could be possible? But I'm not sure why the unit test and two CRDB shells are exhibiting different behavior here.

[smklein]

Instance Update Network Interface seems to do the following operations:

• SELECT from the instance, and only proceed if there is a propolis ID and the state is stopped
• SELECT from instance_network_interface to get the primary interface
• If the primary interface is not the target, update network_interface
• Finally update the target network_interface

I think in this case, the instance record returned by the instance_query may change arbitrarily in the middle of this transaction. For example, I think it's possible that this could actually update the primary interface of an instance that is not stopped, because no write lock is taken on the instance_query.

EDIT: This also applies to the other variant where a primary is not being updated -- there's still a check on the result of SELECT FROM instance, even though that might be stale:

omicron/nexus/db-queries/src/db/datastore/network_interface.rs

Line 799 in 9fb967d

self.transaction_retry_wrapper("instance_update_network_interface")

[smklein]

Physical Disk Adoption checks that a Sled is "in service" before inserting a disk and zpool. The guard here is intended to verify that the Sled hasn't been expunged, but it's possible that this sled becomes expunged mid-transaction, and the physical disk adoption happens anyway.

[smklein]

Silo Group Deletion does the following:

• SELECT from silo_group_memberships
• bail early if !group_memberships.is_empty()
• Soft DELETE from silo_group if silo_group_memberships is not empty

Auditing this, I was concerned that a concurrent writer could add an entry to silo_group_membership and deletion would proceed anyway:

CREATE TABLE membership (id UUID PRIMARY KEY, group_id UUID);
CREATE TABLE groups (id UUID PRIMARY KEY, name TEXT);
INSERT INTO groups (id, name) VALUES ('e7cb922d-fab0-4d05-9132-9c38386dc4e0', 'hello');

# Shell 1
BEGIN;
SELECT * FROM membership WHERE group_id='e7cb922d-fab0-4d05-9132-9c38386dc4e0';

# Shell 2
INSERT INTO membership (id, group_id) VALUES (gen_random_uuid(), 'e7cb922d-fab0-4d05-9132-9c38386dc4e0');

# Shell 1
DELETE FROM groups WHERE id='e7cb922d-fab0-4d05-9132-9c38386dc4e0';
COMMIT;

However, this does seem to throw a serialization error as expected

[smklein]

Loopback Address Creation does the following:

• It SELECTs from address_lot_block to ensure a lot exists with the requested address
• It SELECTs from address_lot_rsvd_block to ensure that the address isn't already taken
• It INSERTS into address_lot_rsvd_block to mark it as in-use
• Finally, it INSERTS into loopback_address

This problem looks like it might appear if the read from address_lot_block could be made stale before the subsequent writes?

[davepacheco]

After spending some quality time with various docs and blog posts, I think we misunderstood the behavior here. Going back to the example that kicked all this off:

An example of this issue was that highlighted within #6229, where we had roughly the following problem:

• In a Transaction: SELECT the latest blueprint target, confirms it is equal to value X. Perform a database modification, assuming that the SELECT-ed blueprint target has not been modified.
• Concurrently, another operation may occur, which modified the "latest target blueprint".

In this example, the following may occur:

• Txn: SELECT the blueprint target, sees value "X"
• Another operation modified the blueprint target to "X + 1"
• Txn: Modify the DB, issue COMMIT. No error is observed, it is not known that the target changed mid-operation.

Let's call txn1 the transaction that checks the current target blueprint and writes more data iff it matches what's expected.
Let's call txn2 the transaction that changes the target blueprint.

I believe we were wrong in inferring that the behavior described above violates our application-level invariant.

We've been operating from the idea that: "we only want to write these records if the current target blueprint is what we think it is". Equivalently, "we want to avoid writing these records if the current target blueprint has changed from what we think it is". But this isn't sufficiently precise because in an MVCC world (like pretty much any modern relational database), there isn't really an objective truth about which blueprint is the target at a given point in time -- there's only the question of what value a particular transaction would see. Instead of talking about whether "the blueprint has changed during this transaction", we need to phrase the invariant in terms of what another observer might see. The behavior we're really trying to avoid is that some other transaction txn3 sees the new target blueprint (txn2's write) and not txn1's writes, and then subsequently txn3 does see txn1's writes. The behavior observed above does not show that happening. As far as I can tell, CockroachDB does promise that can't happen. I wrote a tool to help play around with this and I tried a few different interleavings. I saw that:

• If txn3 arrives after txn2 completes and before txn1 has written any data, then txn3 sees blueprint "X + 1" and txn1 will fail with a serializability error. That's because there's no way for txn1 to complete and preserve serializability. It already saw blueprint "X", so it must happen before txn2. But txn3 already completed and didn't see txn1's write, so txn1 has to be after txn3. But txn3 saw txn2's write, so txn3 is after txn2. There's no ordering that works, so txn1 has to fail.
• If txn3 arrives after txn2 completes and after txn1 has written the data, then txn3 blocks until txn1 completes and in the end all three transactions complete successfully with the logical ordering being: txn2, txn1, txn3.

All of this is consistent with the application-level invariant we're trying to uphold: at no point was an observer able to see blueprint "X + 1" and not the data that txn1 wrote and then later see the data that txn1 wrote.

Another way to phrase all this: what we observed here was CockroachDB re-ordering things so that the transaction that set the target blueprint, although it completed first in wall-clock time, was logically after the transaction that checked the blueprint state and wrote the data. And there's nothing wrong with that.

---

Using sqldance, I also went through the example in #6712. That example is trying to show a case where the DNS update code would be broken by another transaction arriving and changing the DNS generation in the middle of the transaction that normally tries to update it. The end result in the test does violate the assumed invariant that there can only be one version. But that's because of the the transaction that inserts a new version without checking the current one first. If I instead change the sqldance example to do what the real DNS update code does, which is to read the current DNS version and then try to update it, then one of the two attempted updates always fails. So I think that in the end the DNS update code is correct, and for the reason mentioned in the comment about the transactions being serializable.

---

I know we all (myself included) have been confused at various points in the last few days and I'd love someone to verify this reasoning and it'd also be good to work through any other examples that we've found confusing. But from the cases I've looked at, the code we have seems correct and the concurrency model is as strong as we've been assuming.

[andrewjstone]

Dave, I spent a while this weekend going through this as well and I came up with essentially the same answer as you. I'm going to write my thinking down, not because I don't think you realize this but to confirm we are on the same page and to provide some additional notes for others.

I think you made a mistake in this line here though, which you correct in prose below that:

If txn3 arrives after txn2 completes and after txn1 has written the data, then txn3 blocks until txn1 completes and in the end all three transactions complete successfully with the logical ordering being: txn2, txn1, txn3.

The above states the physical time of transaction completion, but the logical serialization schedule is txn1, txn2, txn3. This is because txn1 read X first, and txn2 wrote X+1, therefore txn1 must be ordered logically before txn2. The other data being written by txn1 is unrelated to the any data in txn2, and so this is what allows the logical serial order of these two transactions to operate concurrently and then commit independently.

I think the introduction of txn3 shows what a conflict looks like and when txn1 would abort, but it's not strictly necessary to infer the ordering of txn1 and txn2based on serializability. CRDB runs txn1 and txn2 in parallel (via MVCC) for performance reasons, and txn1 reads X before txn2 commits. MVCC importantly allows the "writer to not block the reader". Therefore, for concurrent transactions, as long as there are not other conflicts, a read and write of the same value (X in this case) allows both transactions to commit independently. This is because the logical serialization order is not the same as the commit time. There is no "real-time" component to serializability in principle, although in practice CRDB limits how long transactions can run without a retry error. But you could imagine a hypothetical database where txn1 and txn2 are the only two transactions that ever run and they start concurrently. The operate such that txn1 reads val=X and txn2 writes val=X+1. txn2 commits. Then txn1 performs a computation that takes 2 years and computes Y. Eventually, it writes the output to val2 = Y and commits. txn1 is still logically ordered before transaction 2, even though it committed 2 years later. This is allowed by serializability, whereas it wouldn't be allowed by linearizability or stict serializability.

Now, on the other hand if 2 years later, txn2 tried to write val=Y (our original variable) it would abort, since it read a value, and another value got written in the meantime to the same location before that node tried to write. There's no serial order that would allow that.

Now coming back to your example with txn3. Let's assume that both txn1 and txn2 commit (because of the reasons above), and then we start txn3. txn1 will indeed still write the extra data. Then when txn3 starts it will read X+1 and the extra data written when the target was still X. This is actually the same behavior as txn1 committing, then txn2 starting and committing, and then txn3 running. If it is ok for txn3 to see X+1 and the extra data (as long as there is no point where txn3 doesn't see the extra data and then it suddenly becomes available, then I agree with your conclusion.

FWIW, the CMU intro to db lectures are very good and cover concurrency control well. Starting here and continuing for the next few lectures as needed may help us all.

[davepacheco]

I think you made a mistake in this line here though, which you correct in prose below that:

If txn3 arrives after txn2 completes and after txn1 has written the data, then txn3 blocks until txn1 completes and in the end all three transactions complete successfully with the logical ordering being: txn2, txn1, txn3.

The above states the physical time of transaction completion, but the logical serialization schedule is txn1, txn2, txn3.

Agreed!

[smklein]

Just to hammer this home, I figured I'd draw out the serialization conflicts via a graph for the blueprint case within sqldance's recent-exmaples.txt

Looking specifically for "RW, WR, or WW" conflicts, using the lens @andrewjstone mentioned from the notes on DB concurrency control:

c1: BEGIN;
c1: SELECT * from bp_target ORDER BY gen DESC LIMIT 1;
c2:                       BEGIN;
c2:                       SELECT * from bp_target ORDER BY gen DESC LIMIT 1;
c2:                       INSERT INTO bp_target (gen) VALUES (2);
c2:                       COMMIT;
c1: INSERT INTO data VALUES (1);
c1: COMMIT;

c1	c2
R(bp_target)
	R(bp_target)
	W(bp_target)
W(data)

There is a dependency between the two transactions, but no cycles, so according to conflict serializability, it's valid for both of these transactions to commit.

c1: BEGIN;
c1: SELECT * from bp_target ORDER BY gen DESC LIMIT 1;
c2:                       BEGIN;
c2:                       SELECT * from bp_target ORDER BY gen DESC LIMIT 1;
c2:                       INSERT INTO bp_target (gen) VALUES (2);
c2:                       COMMIT;
# This is the point where we could conceivably see generation 2 but missing data
# from generation 1.
c3: SELECT * from bp_target;
c3: SELECT * from data WHERE x = 2;
c1: INSERT INTO data VALUES (1);
c1: COMMIT;

c1	c2	c3
R(bp_target)
	R(bp_target)
	W(bp_target)
		R(bp_target)
		R(data)
W(data)

A cycle exists here, which explains the serializability error -- there is no ordering of transactions that is valid where we don't violate RW/WR semantics.

Finally, for the blocking case:

c1: BEGIN;
c1: SELECT * from bp_target ORDER BY gen DESC LIMIT 1;
c2:                       BEGIN;
c2:                       SELECT * from bp_target ORDER BY gen DESC LIMIT 1;
c2:                       INSERT INTO bp_target (gen) VALUES (2);
c2:                       COMMIT;
c1: INSERT INTO data VALUES (1);
c3: SELECT * from bp_target;
# This operation blocks
c3: SELECT * from data WHERE x = 2;

c1	c2	c3
R(bp_target)
	R(bp_target)
	W(bp_target)
W(data)
		R(bp_target)
		R(data)

From the graph (dotted line showing a dependency that only emerges if we actually try the c3: SELECT * FROM DATA line) we can see that the ordering must be C1 -> C2 -> C3.

From a data-dependency point of view, it's clear that C3's read of data is dependent on C1's transaction completing -- it has a pending write to data -- but it's interesting that CockroachDB chooses to block here, rather than force a retry of C3.