Delete race in ARC cache

[Stebalien]

Steps:

1. Call Put & Delete on the same block at the same time.
2. After finishing step 1, call Put on the block.

After step 1, the block may or may not be in the blockstore depending on how the operations serialize. However, after step 2, the block must be in the datastore.

Unfortunately, there's a race:

1. Put 1: put the block.
2. Delete 1: Delete the block.
3. Delete 1: Cache that we don't have the block.
4. Put 1: Cache that we have the block.
5. Put 2: Check the cache, see that we should have the block, and walk away.

There's also a similar race between get & delete and get & put.

Fix: add striped (by CID) locking.
Impact:

1. Put & Delete: data loss (in go-ipfs, requires GC)
2. Get & Delete: data loss (in go-ipfs, requires GC)
3. Get & Put: Inability to retrieve a block from the datastore (until restarting).

[Stebalien]

Note: this is not an issue for the bloom cache because we only add "might haves" to the cache (never remove from it unless we rebuild).

[Stebalien]

Notes:

1. This will need to be fixed in the 1.0 branch then backported.
2. Locking. See below.

Unfortunately locking the entire blockstore while we put/get will significantly impact performance. We have two options:

1. Per-CID locking: Basically, we keep a map of CIDs to locks (where the map is also guarded by a lock). This is the simple solution but may have allocation overhead.
2. Striped locking: We can (generally) assume that the last byte of a CID is random and can use it as a key in a [256]sync.Mutex slice. This gives us a fair amount of parallelism, but isn't quite as simple/nice as per-cid locking.

I'd implement both options and benchmark them:

1. Benchmark one thread.
2. Benchmark 16 threads.
3. Benchmark 500 threads.

(recording allocation information at the same time https://golang.org/pkg/testing/#B.ReportAllocs)

[frrist]

I've filed a PR to add benchmarking to the arc_cache here: #65. It serves as the base for the following drafts:

1. fix(arc): Per-CID locking. Map CID to lock. #66. Per-CID locking with a map of CID's and their locks. The map is guarded by an RWMutex.
2. fix(arc): striped locking on last byte of CID #67. Striped locking on the last byte of the CID.
3. fix(arc): Per-CID locking. Sync Map to CID lock #68. Per-CID locking with a sync.Map, as an alternative to 1 -- removes the requirement of locking before accessing the map
4. fix(arc): Per-CID locking. KeyMutex #69. Per-CID locking with KMutex package: github.com/gammazero/kmutex

I'll share benchmarks in the description of each PR

[Stebalien]

@warpfork could you pick this up? Compare the benchmarks, review, etc.

[warpfork]

I have low context on this, so I mostly just come up with questions. I'll share those questions, but if folks with higher context think these are silly, feel free to ignore.

• Was there a user encounter that caused us to notice this?

  • How often does it actually produce a problem? Are we sure our synthetic benchmarks are going to relate to real user stories?
  • (Normally I'd say "race conditions bad" is a truism, but... I'm of the general impression that using our system in the face of concurrent GC is just generally not very safe, so I don't completely grok the envelope of concern here and am interested in probing that because I wonder if a holistic examination will change the solution path.)
  • Has this been here for a long time? If so, did something make its apparent priority rise substantially recently?

• Is this API actually correct? What's the scale of locking that is actually needed to make logically correct operations always available to a user story that's building on top of this API?

  • It comes to mind that (iiuc) adding and pinning are two separate steps at present, and pinning follows add. (And at present, it must be in this order, because pinning starts at the root of a tree, so the whole tree must be added first.) Which means... running GC in during an add (while it's mid-tree, and thus before a pin) will still cause incorrect behavior at a higher level than this API. (GC may not be the only thing that drives this API, but it seems to me it's probably one of the larger users of it, and it's also just a generally good example of how the higher level story may matter to determining what form of locking API is actually important.) Do I misunderstand, and is this somehow not a problem? If it is a problem, are the ways people are solving it making this more fine-grained race (and its fix) irrelevant in practice?
  • ISTM that a lot of times I've looked at APIs like this in other projects over the years, a key design element is some kind of generation number or sequencing number (or just CAS token, etc) that allows the ordering discussion to involve the caller in predictable ways. I'm not sure if we need this here, but my spider senses are tingling. Has this been considered?

[Stebalien]

I'm happy to answer questions, but it's a potential dataloss issue in our happy path so whether or not we fix it is a forgone conclusion.

Was there a user encounter that caused us to notice this?

We don't know. But it's a dataloss issue and we do ocasonally get complaints about dataloss. On the other hand, most users don't use GC.

How often does it actually produce a problem? Are we sure our synthetic benchmarks are going to relate to real user stories?

The benchmarks are trying to emulate fetching multiple blocks in parallel, which we do. Unfortunately, our parallelism varies depending on the workload. Most users will have 10-32 parallelism, but a gateway will fetch 1000s of nodes at a time.

Normally I'd say "race conditions bad" is a truism, but... I'm of the general impression that using our system in the face of concurrent GC is just generally not very safe, so I don't completely grok the envelope of concern here and am interested in probing that because I wonder if a holistic examination will change the solution path.

Our system is pretty safe in that regard. Unfortunately, this bug also affects concurrent reads and GC. For example, a network peer might read a block that's about to be deleted which will force our cache into an incorrect state.

Has this been here for a long time? If so, did something make its apparent priority rise substantially recently?

It has been an issue for a while, but:

1. We investigated this because a user reported a dataloss issue (although that user wasn't using GC so that shouldn't be the case here).
2. We've had several proposals for improved GC. If/when GC is more widely enabled/supported, this will become a larger issue.

Is this API actually correct? What's the scale of locking that is actually needed to make logically correct operations always available to a user story that's building on top of this API?

Yes. The invariant being enforced here is simply: the cache remains consistent with the underlying blockstore. That's it.

The wider question of the pinset being valid, etc, is enforced at a higher layer. This higher layer is responsible for calling delete and ensures that no pin operation overlaps with delete operations.

[mvdan]

I wrote a new benchmark in #70, following what has previously been said on this thread. It's on top of master, as I understand that's the latest v1.0 development.

While I wait for reviews there, the plan was to get benchmark numbers comparing master to the four proposed fixes. However, I'm struggling because each of those four fix PRs are built on v1.0.0, which a year behind master at this point, which contains v1.0.3. In particular, I keep running into conflicts when I try rebasing the four PRs on master.

@frrist is there a particular reason you built your fixes on an older v1.0 version?

I'll try to backport the benchmark to v1.0.0 and use that as a baseline for benchmark comparison, but I assume that's not helpful. We want the benchmark numbers for master, since presumably that would become another release like v1.0.4.

[mvdan]

Here are the benchmark results. This is all on v1.0.0, and with the benchmark from #70 running with 4k blocks and 1, 64, and 1028 concurrent goroutines.

$ benchstat old new-66
name                                  old time/op    new time/op    delta
ARCCacheConcurrentOps/PutDelete         1.10µs ± 2%    1.31µs ± 1%  +19.89%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64      1.26µs ± 1%    1.52µs ± 2%  +20.80%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-1028    1.40µs ± 2%    1.81µs ± 1%  +29.10%  (p=0.004 n=6+5)
ARCCacheConcurrentOps/GetDelete          427ns ± 0%     485ns ± 0%  +13.66%  (p=0.008 n=5+5)
ARCCacheConcurrentOps/GetDelete-64       604ns ± 1%     645ns ± 2%   +6.70%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028     644ns ± 0%     703ns ± 1%   +9.16%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut            1.04µs ± 1%    1.26µs ± 1%  +21.04%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64         1.11µs ± 0%    1.19µs ± 1%   +6.99%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/GetPut-1028       1.23µs ± 1%    1.40µs ± 1%  +13.32%  (p=0.002 n=6+6)

name                                  old alloc/op   new alloc/op   delta
ARCCacheConcurrentOps/PutDelete           309B ± 0%      328B ± 0%   +5.99%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64        309B ± 0%      328B ± 0%   +6.15%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/PutDelete-1028      315B ± 0%      336B ± 0%   +6.67%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete           113B ± 0%      121B ± 0%   +7.08%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-64        113B ± 0%      122B ± 0%   +7.96%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028      117B ± 0%      125B ± 0%   +6.84%  (p=0.004 n=6+5)
ARCCacheConcurrentOps/GetPut              313B ± 0%      338B ± 0%   +7.99%  (p=0.004 n=6+5)
ARCCacheConcurrentOps/GetPut-64           313B ± 0%      338B ± 0%   +7.87%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-1028         319B ± 0%      345B ± 0%   +8.04%  (p=0.002 n=6+6)

name                                  old allocs/op  new allocs/op  delta
ARCCacheConcurrentOps/PutDelete           7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64        7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-1028      7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete           3.00 ± 0%      4.00 ± 0%  +33.33%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-64        3.00 ± 0%      4.00 ± 0%  +33.33%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028      3.00 ± 0%      4.00 ± 0%  +33.33%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut              7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64           7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-1028         7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)


$ benchstat old new-67
name                                  old time/op    new time/op    delta
ARCCacheConcurrentOps/PutDelete         1.10µs ± 2%    1.24µs ± 1%  +12.63%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64      1.26µs ± 1%    1.32µs ± 1%   +5.10%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-1028    1.40µs ± 2%    1.57µs ± 1%  +12.08%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete          427ns ± 0%     425ns ± 3%     ~     (p=0.329 n=5+6)
ARCCacheConcurrentOps/GetDelete-64       604ns ± 1%     607ns ± 1%     ~     (p=0.260 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028     644ns ± 0%     646ns ± 2%     ~     (p=0.223 n=6+6)
ARCCacheConcurrentOps/GetPut            1.04µs ± 1%    1.19µs ± 1%  +14.18%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64         1.11µs ± 0%    1.16µs ± 0%   +4.59%  (p=0.008 n=5+5)
ARCCacheConcurrentOps/GetPut-1028       1.23µs ± 1%    1.41µs ± 2%  +14.66%  (p=0.002 n=6+6)

name                                  old alloc/op   new alloc/op   delta
ARCCacheConcurrentOps/PutDelete           309B ± 0%      405B ± 0%  +31.07%  (p=0.004 n=6+5)
ARCCacheConcurrentOps/PutDelete-64        309B ± 0%      406B ± 0%  +31.28%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/PutDelete-1028      315B ± 0%      411B ± 0%  +30.48%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete           113B ± 0%      113B ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-64        113B ± 0%      114B ± 0%   +0.88%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028      117B ± 0%      118B ± 0%   +0.85%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut              313B ± 0%      410B ± 0%  +30.83%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64           313B ± 0%      410B ± 0%  +30.74%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-1028         319B ± 0%      417B ± 0%  +30.58%  (p=0.010 n=6+4)

name                                  old allocs/op  new allocs/op  delta
ARCCacheConcurrentOps/PutDelete           7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64        7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-1028      7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete           3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-64        3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-1028      3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetPut              7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64           7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-1028         7.00 ± 0%      9.00 ± 0%  +28.57%  (p=0.002 n=6+6)


$ benchstat old new-68
name                                  old time/op    new time/op    delta
ARCCacheConcurrentOps/PutDelete         1.10µs ± 2%    1.48µs ± 2%  +34.58%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64      1.26µs ± 1%    1.38µs ± 1%  +10.10%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-1028    1.40µs ± 2%    1.60µs ± 2%  +14.21%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete          427ns ± 0%     506ns ± 2%  +18.44%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/GetDelete-64       604ns ± 1%     638ns ± 1%   +5.56%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028     644ns ± 0%     711ns ± 0%  +10.40%  (p=0.004 n=6+5)
ARCCacheConcurrentOps/GetPut            1.04µs ± 1%    1.30µs ± 1%  +25.13%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64         1.11µs ± 0%    1.20µs ± 2%   +7.99%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/GetPut-1028       1.23µs ± 1%    1.41µs ± 1%  +14.05%  (p=0.002 n=6+6)

name                                  old alloc/op   new alloc/op   delta
ARCCacheConcurrentOps/PutDelete           309B ± 0%      332B ± 0%   +7.34%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64        309B ± 0%      331B ± 0%   +7.12%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/PutDelete-1028      315B ± 0%      337B ± 0%   +7.09%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete           113B ± 0%      114B ± 0%   +0.88%  (p=0.004 n=6+5)
ARCCacheConcurrentOps/GetDelete-64        113B ± 0%      114B ± 0%   +0.88%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028      117B ± 0%      118B ± 0%   +0.85%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut              313B ± 0%      331B ± 0%   +5.75%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64           313B ± 0%      331B ± 0%   +5.64%  (p=0.004 n=6+5)
ARCCacheConcurrentOps/GetPut-1028         319B ± 0%      338B ± 0%   +5.85%  (p=0.004 n=6+5)

name                                  old allocs/op  new allocs/op  delta
ARCCacheConcurrentOps/PutDelete           7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64        7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-1028      7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete           3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-64        3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-1028      3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetPut              7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64           7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-1028         7.00 ± 0%      8.00 ± 0%  +14.29%  (p=0.002 n=6+6)


$ benchstat old new-69
name                                  old time/op    new time/op    delta
ARCCacheConcurrentOps/PutDelete         1.10µs ± 2%    1.24µs ± 1%  +13.07%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64      1.26µs ± 1%    1.37µs ± 2%   +8.78%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-1028    1.40µs ± 2%    1.68µs ± 1%  +20.14%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete          427ns ± 0%     430ns ± 1%     ~     (p=0.052 n=5+6)
ARCCacheConcurrentOps/GetDelete-64       604ns ± 1%     613ns ± 2%   +1.51%  (p=0.004 n=6+6)
ARCCacheConcurrentOps/GetDelete-1028     644ns ± 0%     652ns ± 1%   +1.33%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut            1.04µs ± 1%    1.16µs ± 1%  +11.55%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64         1.11µs ± 0%    1.18µs ± 1%   +6.39%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/GetPut-1028       1.23µs ± 1%    1.46µs ± 1%  +18.58%  (p=0.002 n=6+6)

name                                  old alloc/op   new alloc/op   delta
ARCCacheConcurrentOps/PutDelete           309B ± 0%      317B ± 0%   +2.59%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/PutDelete-64        309B ± 0%      317B ± 0%   +2.70%  (p=0.004 n=5+6)
ARCCacheConcurrentOps/PutDelete-1028      315B ± 0%      325B ± 0%   +3.07%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetDelete           113B ± 0%      113B ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-64        113B ± 0%      113B ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-1028      117B ± 0%      117B ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetPut              313B ± 0%      321B ± 0%   +2.56%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-64           313B ± 0%      322B ± 0%   +2.77%  (p=0.002 n=6+6)
ARCCacheConcurrentOps/GetPut-1028         319B ± 0%      329B ± 0%   +3.03%  (p=0.002 n=6+6)

name                                  old allocs/op  new allocs/op  delta
ARCCacheConcurrentOps/PutDelete           7.00 ± 0%      7.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/PutDelete-64        7.00 ± 0%      7.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/PutDelete-1028      7.00 ± 0%      7.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete           3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-64        3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetDelete-1028      3.00 ± 0%      3.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetPut              7.00 ± 0%      7.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetPut-64           7.00 ± 0%      7.00 ± 0%     ~     (all equal)
ARCCacheConcurrentOps/GetPut-1028         7.00 ± 0%      7.00 ± 0%     ~     (all equal)

[mvdan]

As a summary:

#66 is a hit of between 10% and 30% in perf, especially with more goroutines. I think it should be discarded, as it's the one that performs the worst.

#67 is fairly low overhead, with a modest hit of only 12-14% with many goroutines.

#68 is fairly similar to #66, being better in some cases and worse in others. Overall the performance isn't great either.

#69 has decent performance, but still a bit worse than #67, topping at 18-20% overhead with many goroutines.

So I think #67, striped locking, is the winner in terms of overhead, especially with lots of concurrency. This aligns with what @Stebalien said earlier:

Striped locking: We can (generally) assume that the last byte of a CID is random and can use it as a key in a [256]sync.Mutex slice. This gives us a fair amount of parallelism, but isn't quite as simple/nice as per-cid locking.

[frrist]

@mvdan I based my branches on v1.0 due to the note from Steven above:

This will need to be fixed in the 1.0 branch then backported.

I'm sorry that I misunderstood this (I assumed 1.0 meant v1.0.0). I can rebase the branches onto v1.0.3 if that would be helpful?

[mvdan]

I think that would be helpful :) If you can rebase on master without including your benchmark that would be best, because then it's trivial to rebase that on top of either benchmark to get numbers.

I still think the numbers above are useful, though. If we think they might drastically change on master, I can get new numbers after the rebases.

[frrist]

All branches have been rebased onto master.

[Stebalien]

Thanks! Sorry, by "1.0" I meant "v1" versus "v0" (we maintain two versions).

[Stebalien]

@mvdan thanks for doing that investigation! And yeah, you're right. It sounds like #67 is the way to go.

[Stebalien]

Note: We haven't backported to the v0 branch, but this shouldn't be necessary anymore as we've picked up the blockstore migration project again.

[BigLep]

I believe ipfs/kubo#6815 captures the "blockstore migration project".