Reconsidering AsyncLoader local vs remote loading logic

[hannahhoward]

As we look forward to further evolution of the protocol, I'd like to reconsider the logic around whether we load blocks locally or remotely on the side making a request.

The high level summary of the current logic is as follows:

1. attempt to load remotely
   • if the remote has sent us a block, use that
   • if the remote has already said it doesn't have the block, error (results in a traversal.SkipMe)
2. if the remote has not sent us a block but hasn't said it doesn't have it, attempt to load locally
   • if we have a local block, use that
   • if we don't have a local block, return that we have neither a remote or local block yet. If the request is ongoing, it will simply defer the load till more responses arrive. If the remote has already sent a final response code, it will fail the load as we don't have it locally and there are no further remote blocks coming

This approach correctly handles the following cases:

• Remote traverses the same link twice and doesn't send us the block the second time (second time reads the block locally)
• Fails loads when remote is missing block so traversal can continue (in most cases -- see below)
• Allows traversal to finish early if you have all the remaining blocks locally for some reason.

However, there are some problematic cases, most of which are hidden in Filecoin by the fact that each transfer happens in a different blockstore:

• Remote is missing block, but the local has some or all of the tree underneath (it would be more ideal to return all the local data if we have it)
• Remotes metadata diverges from the local traversal -- we should able to detect and fail the response immediately at this point, before we absorb more block data (this is also a potential DOS vector)
• There's a rare potential issue -- local traversal attempts to load a block it happens to have locally BEFORE remote says it's missing the block. You're now in a portion of the tree where you can only load locally but you don't know it. The net result is if the local is missing any blocks in the subtree, essentially the traversal will hang until all the responses are received (and we go to not setting aside loads for later)

I'd like to propose the following new logic to go with our new metadata structure:

• maintain a list of local only paths for this request
• for each link loaded:
  • check if it falls under a local only traversal path
  • if it doesn't fall under a local only path ("remote mode"):
    • When we load a link, we wait for the metadata to arrive about that link
      • if no metadata yet receive for link, defer load until more metadata arrives
    • when we receive metadata:
      • if metadata diverges from the local traversal, fail the traversal (this is effectively a malicious peer sending the wrong traversal order)
      • for Present, load the block from the response or error if not present (results in a traversal.SkipMe)
      • for DuplicateBlock, attempt to load the block from local storage. return local block or error (results in a traversal.SkipMe)
      • for Missing or DuplicateTree, attempt local load. if local load succeeds, add the current path as a local only path. return local block or error (results in a traversal.SkipMe)
  • if it does fall under a local only path ("local mode"):
    • attempt local load
    • return error if no block present (results in a traversal.SkipMe)
• when final response code received, add root path as local only

This approach correctly handles

• Remote traverses the same link twice and doesn't send us the block the second time (second time reads the block locally)
• Remote is missing block, but the local has some or all of the tree underneath (returns all local data we have)
• Remote and local are missing block -- returns error so traversal can continue
• Remotes metadata diverges from the local traversal -- detects and fails the response
• No issue of ending up in a local load area so responses get buffered

This approach has the following downsides:

• Does not allow traversal to finish early if you have all the remaining blocks locally for some reason.

This issue can be averted in a couple ways:

• First this new logic makes it easier to add a "do not even fire remote request until we're missing any block locally" -- using DoNotSendFirstBlocks extension
• We could theoretically extend the algorithm to include a "we're in an ahead of remote traversal path", and if were here, we'd have to verify remote metadata retroactively

We also need to do some thinking around processing DuplicateTree on the local level, understanding that as selector traversals evolve, the local and remote may have different capabilities for detecting duplicate trees. We may want to expose the ability to configure DuplicateTree traversal on a per request or per GraphSync instance basis.

[willscott]

I feel like this still going to potentially be a bit brittle around work stealing approaches where some sub-trees have been carved off for another peer to fetch. It may now be local from that other peer, but the remote peer may believe it's still should traverse the sub-tree. Figuring out those edge cases seems like it's going to be fiddly.

[hannahhoward]

@willscott yes but, that is a tomorrow problem when we support multi-peer requests. I have no doubt that both of these logics suffer problems for that scenario. Currently our logic today has issues for single peer requests.

[hannahhoward]

I do see how this is problematic if we assume graphsync requests across peers occur at a higher level of coordination.