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.