cc @VladLazar I cannot think about a better way to fix it other than hacking somewhere. Please help take a look, thanks :)

7414 tests run: 7063 passed, 0 failed, 351 skipped (full report)

Code coverage* (full report)

• functions: 33.3% (8491 of 25495 functions)
• lines: 49.1% (71411 of 145539 lines)

* collected from Rust tests only

I think semantically, the issue is that bottommost-comapction aka gc_compaction isn't integrated with the latest_gc_cutoff_lsn RCU machinery, right? Can we make it integrated with it instead of adding a new lock? All we'd need to do is lock out the gc task while doing gc_compaction (?)

It's kind-of integrated. Gc-compaction only compact data below the cutoff lsn.

@VladLazar I did a little experiment and I don't think using latest_gc_cutoff would work. The constraint I would like to achieve with the locks is that (1) all ongoing reads should finish before we update the gc-compaction layer map (2) all pending reads should block before we update the gc-compaction layer map (3) pending reads should only proceed after we finish update the layer map. Rcu can only achieve (2) but cannot do (1) and (3). Furthermore, gc-compaction doesn't update latest_gc_cutoff at all, so I feel like doing locking around latest_gc_cutoff is more like mocking a RwLock...

I've updated the code with the two scenarios I'm thinking about and also the constraints I want to enforce during gc-compaction. Let me know if you have any ideas to make this simpler. Otherwise I'd like to get this patch merged first to see whether this resolves the "key not found" issue and we have fixed all existing gc-compaction bugs. We can optimize this lock away later with layer map refactors or using better methods. Note that if gc-compaction doesn't run at all, no tasks will be blocked on the newly-added rwlock.

This prevented gc from kicking in and removing layers while the read is ongoing.

This prevents gc from kicking in but didn't prevent gc removing layers while read is ongoing. Note that gc only holds the Rcu write guard for a small amount of time when updating the cutoff, and then it proceeds without holding the lock.

The reason why it doesn't trigger race condition in the current codebase: gc only removes layers that are fully covered by image layers. In other words, gc only removes layers that won't be accessed by the read path. We know that the read path stops at the image layer.

However, gc-compaction will rewrite layers that can be accessed by the read path. In case (1) described in the code comment, we could do something like update the layer map to add image layers, sleep for a few seconds, and then update the layer map to remove stale delta layers. However, in case (2), where gc-compaction operates on a branch, it has to rewrite layers that are accessible on the read path, and I think we will have fix the problem on the read path in the end.

An alternative idea is to hack the Rcu and add a new functionality that first waits for all reads to finish, then allows user to run some code (i.e., update layer map), and then unblocks reads. However, note that the update layer map code is async, and RcuGuard is not Send.

(1) all ongoing reads should finish before we update the gc-compaction layer map

The Rcu satisfies this as far as I can tell. RcuWriteGuard::store_and_unlock followed by RcuWaitList::wait will wait until all the ongoing reads are done since each read holds one RcuReadGuard.

(2) all pending reads should block before we update the gc-compaction layer map

The layer map rw lock gives you this property. If we are updating, the layer map, we can't get a read lock and begin traversal.

(3) pending reads should only proceed after we finish update the layer map

Again, layer map lock covers this.

This prevented gc from kicking in and removing layers while the read is ongoing.

This prevents gc from kicking in but didn't prevent gc removing layers while read is ongoing. Note that gc only holds the Rcu write guard for a small amount of time when updating the cutoff, and then it proceeds without holding the lock.

The important bit there is not the write guard, but the RcuWaitList::wait call. That's where the waiting happens.

Okay I'll merge this patch first and let's have a call at some point :)

Had a call with Vlad and we agreed that this is the only way to quickly fix it; in the long term we need to make layer map copy-on-write.