Problems arising from mandatory selector-based retrieval mechanisms

At present lotus (and other fil-markets-compatible implementations) operate all retrievals strictly through the use of selectors. Specifically the "unit of exchange" between the API/CLI and fil-markets is this structure:

// Params are the parameters requested for a retrieval deal proposal
type Params struct {
    Selector                *cbg.Deferred // V1
    PieceCID                *cid.Cid
    PricePerByte            abi.TokenAmount
    PaymentInterval         uint64 // when to request payment
    PaymentIntervalIncrease uint64
    UnsealPrice             abi.TokenAmount
}

This makes it impossible to utilize filecoin for storage of incomplete DAGs that could not possibly fit into a 64GiB sector (a good example of this is the filecoin-discover blockchain data).

It poses an additional problem of non-deterministic car-files imported via the offline deal flow. Such data can be imported into filecoin and succesfully sealed, but can never be retrieved even if the client is willing to traverse the .car container using their own software. Examples of this are:

as above, car-files with incomplete graphs
car-files produced by something other than the default go-ipfs traversal mechanism

Potential workarounds for the above discussed in the comment section.

An additional complication I missed above, is that selectors require flawless link traversal. This implies that in order to retrieve a DAG from a sealed piece the storage miner, the retrieval miner and the client must all have complete support for every codec in the entire DAG, in order for all blocks to be correctly graphsynced over. This (arbitrary codec support) is already a problem for the filecoin discover blockchain data and will grow to become prohibitively expensive long term.

We weren’t aware of this constraint until very recently, we had assumed this whole time that you’d have some way to get the raw CAR file data without a selector. But since there is no other way I can see to do incremental payments without this constraint, it makes sense and I think that we should embrace it. However, this does have some immediate impact and means we need to shift around a few priorities.

I’ll try and break down what this means in the short, mid, and long term.

We need “skip CIDs” support in retrievals ASAP

Without support for “skip CIDs” in retrievals we don’t have any way to do retrievals of partial graphs. The most obvious and concerning effect this has is that we won’t be able to do retrievals on the Bitcoin CAR files we’ve prepared for launch.
- This feature is already in Graphsync, it just isn’t used/exposed in the retrieval protocol.
- I’ve already started writing code we can run on Lambda to look at all of our Bitcoin CAR files to find the CID we’d need to skip in each file, so we’ll be ready to use this feature as soon as it’s available.

Reading data from Filecoin is going to be constrained by the available codecs miners include

The most immediate concern is that our Go Bitcoin codec is out of date with the latest schema (which is what we’ve used for the CAR files we produced for launch). I’ll need to shift around some resources to make sure this can be updated soon but I need someone to let me know what date we need to hit for this to be included for launch.
How do we plan to update miners with new codecs in the future? Do we have any way to ensure or even expose the codecs a miner has?
In the mid-term, we need to accelerate work we had considered much farther out for safe dynamic codec loading.
- Based on the last round of research we did, this will probably be a set of Rust tools for authoring codecs that compile to WASM. We then will maintain a verified DAG that points codec identifiers at WASM implementations. This could be used by miners to load codecs they don’t already ship with.

Codec proliferation isn’t going away, it’s only going to get worse. We’ve already been doing work in our multiformat implementations to untangle this and move beyond a model that assumes implementations ship with every codec ever, but that work isn’t complete and will need to be accelerated since this is going to limit the utility of any new codec to Filecoin until it’s resolved.

Another thing we need to accelerate is an incremental improvement to CAR files and Selectors that would allow us to embed the selector that generated a CAR file in the CAR file itself and then be able to craft a query that calls the embedded selector query. As things are now, it’s not possible to do retrievals of partial graphs without out-of-band information about every CAR file and this would make that much simpler. Not a launch priority, but something we’ll want to look at right after.

Ok, I underestimated how partial each slice of the Bitcoin chain is. The first slice of the graph is complete, as expected, the second slice has ~140K links to blocks in the prior slice, the number is only going to up from there in future slices. There’s not a realistic way to construct a query with any of our current tools (skip CIDs or existing selector language) so the only way we’re going to be able to read this data is going to be with something that just sends the raw CAR file and doesn’t use selectors/graphsync.

TLDR; I don’t see a way for us to retrieve the partial graphs we have without a new, or considerably altered, retrieval protocol.

I’m going to try and break down the impact of this constraint and the consequences I’ve been able to work through so far. I’ll then refer to this comment in a few issues I plan to log for feature requests.

Retrievals use Graphsync which uses IPLD Selectors. IPLD Selectors can be extended to handle additional use cases. Graphsync can be extended to handle some use cases. The retrieval protocol in Lotus can be extended to handle some cases.

However, if you look at the data we currently have, no part of this retrieval strategy can be extended to handle the partial graphs we have and would like to store and retrieve. I don’t think we have complete information here, I think there are plenty of use cases we’ll see in the future that will benefit from improvements to each of these standards/protocols and I’ll be logging some issues to consider after launch that do just that. But I want to be clear, this strategy won’t work for the partial graphs we have today.

Complete Graphs

The majority of use cases we see today in IPFS operate on complete graphs. IPFS does not have a sector size limit, so there’s no constraint that would keep it from being able to access an entire graph. IPFS’ native data structures also split quite nicely into complete graphs of their own which you can stitch together later, so even when you factor in the sector size limit we have a number of strategies we can use for working around this constraint. We’ve already done so in the dumbo drop project, breaking up large files into 1GB slices that are in their own CAR files.

It’s also not possible right now to add anything other than a complete graph into a single sector in Lotus using the regular deal flow. The only way you could get a partial graph into Lotus would be to use the offline deal flow.

As such, it’s probably not a blocker for launch that this constraint is in place.

Incomplete Graphs

The problem is pretty simple. Once you have a data structure that is larger than the sector limit you have to break it up into parts that live in different sectors. You can’t do a retrieval over multiple sectors or even over multiple pieces, you MUST do a retrieval against a single payload ID for a CAR file in a single sector, so the maximum amount of complete graph data you can add is limited by the sector size.

If you look at the data we know about, the blockchains we’ve currently parsed and put into CAR files, there is no feature you could add to the protocols that would allow us to query the data in any single CAR file except the first CAR file for the chain (which is a complete graph).

As an example, the second 1GB CAR file we have for the bitcoin chain references almost 140K blocks found in the prior CAR file. That number will only increase over time as the chain continues to refer back to itself.

You could craft a query that simply excluded these links, but you’d also end up skipping over data that is actually in the CAR file and there would be some data in every CAR file you’d never be able to access once you store it.

Passing a “skip CIDs” list of 140K puts the query over our max block size, and again, that’s the smallest number of missing CID’s we’re going to see in this set.

There just isn’t a selector based solution to this problem.

“raw” retrieval

I think the only viable solution here is to not use selectors/graphsync. We need a retrieval protocol that just sends the raw CAR file data to the client. The client can then validate the data is correct by calculating commp.

This might sound trivial, but it’s not. Implementing it may be relatively simple compared to our current retrieval protocol but the whole reason we’re using selectors/graphsync is for incremental payments which solves other hard problems. This retrieval method wouldn’t allow for incremental payments and that means we’re back to solving the problems that incremental payments solved.

I’ll be following up with a new issue specifically for tracking “raw retrievals.”

Future

Long term, we need to figure out how retrievals/queries could work across sectors/miners.

A fundamental aspect of DAG’s is deduplication. As you can see from some of the data structures we already have, this feature being leveraged freely makes splitting a data structure into parts highly problematic.

We haven’t put a lot of time into figuring this out, and it’s something we’ll definitely need to figure out in the long term. It would be nice if, by the end of the year, we had a clear understanding of how this is going to work, even if the implementation is years out, because there may be changes and improvements we have to make at lower layers like the CAR file format or even CIDs depending on the approach.

filecoin-project / go-fil-markets