# Data Transfer Stack Design

### Background

#### Problem Definition

A data transfer stack coordinates finding and downloading free or paid content that is hosted one or more locations which support one or more transport protocols.

We have already built several low-level components that make up the data transfer stack. This includes two transport protocols (Bitswap/Graphsync), various content routing mechanisms (Bitswap Want-Have Protocol, IPFS DHT, in progress Filecoin indexer), a control protocol for managing transfers (go-data-transfer), and an initial payment and fair exchange system (go-fil-markets retrieval market/estuary fil-client). We believe we will build more of these components in the future and improve upon existing components.

This document is focused building an extensible architecture for coordinating all these components so users can express high level requests for content and our software can determine the best way to get it. The content may be ultimately be retrieved through one or more individual underlying transfers over one or more protocols from one or more providers.

This is document is designed to help us align on high level vision for the long term. We expect that data transfer stacks we build in the short term will not immediately align with this high level vision, but will move towards this over time.

#### Sample Use Cases

These are some sample scenarios we might encounter retrieving content on the DWeb. The intent here is to think about desired outcomes.

Assume for all of these use cases that the client does not know ahead of time where any of the data they are downloading is hosted.

1. Downloading a large, free, public data set stored in multiple sectors across multiple miners in a Filecoin.
- Goals: A user should be able to download the whole DAG across via multiple requests to multiple miners automatically with manually initiating each individual request
2. Downloading a file from a large, HAMT shared directory. The directory listing in available in IPFS but the file itself is stored only in Filecoin. Client knows the path and file name they are looking for but not the CID of the file, only the directory.
- Goals: A user be able to switch from an IPFS to a Filecoin retrieval automatically without manual intervention
3. Downloading a file that is already partially already stored in a client's local datastore, with a range of bytes m-n that are missing. Missing bytes are available from one or more local peers in swarm that serve both Graphsync and Bitswap
- Goals: A user should receive their desired content quickly because the software is able to efficiently determine what content is not already in the local datastore, request content from local peers without going through an expensive content discovery process, and prioritize downloading from the fastest peers using the fastest transport mechanisms.
4. Downloading a file that is only available via paid retrieval from a Filecoin provider.
- Goals: A user should receive their desired content quickly because no chain operations are performed to facilitate payment. This means we avoid setting up a direct payment channel between client and provider if one does not already exist, most likely by using intermediaries (i.e. payment hubs)
5. Downloading a file that is available for free from a very slow IPFS peer, and available paid from a very fast Filecoin provider
- Goals: User should be able to configure priorities regarding cost vs speed at coarse (overall across operations) and fine grained levels (a single retrieval), and the software should choose content providers based on these priorities
6. A new indexer of content appears that indexes content stored locally in Africa. Downloading a file from a spotty internet connection will only succeed if we download it from a peer discovered on this indexer that is geographically proximal.
- Goals: A user should be able to configure the software to add indexes or other content routing solutions. These solutions do not need to be known a compile time.
7. Downloading content from a provider is being paid to host and serve quickly. The provider is paid by a third party based on number of downloads.
- Goals:
- the user is able to download the content for free
- the provider should be paid by the third party for the transfer
- the third party should be able to verify its content was served
- none of the parties should have to trust each other
8. Downloading content from within a web browser
- Goals: a browser user should be able to download content via standard web2 networking protocols
9. Downloading content that is requires an expensive upfront operation from the provider like unsealing in order to serve
- Goals: providers should have ways to be compensated for an expensive upfront operation and clients should have assurances they won't pay for an expensive operation in which they don't receive content.

#### Prior Art

- The closest thing to a coordination layer we've built so far are Bitswap sessions, which coordinate DHT routing requests, local routing requests (via Bitswap want have protocol), and distributing Bitswap requests among peers. In combination with the BlockService and DAGService, this consitutes a data transfer stack that allows the user to express high level requests for content and the software identifies the best way to get it. The most significant limitations of this stack are:
1. It's locked into the Bitswap protocol
2. It has no current support for payment or access control.
3. It currently has hard-coded discovery mechanisms
4. It is unable to plan out fetching strategies at a level above individual blocks.

- `go-data-transfer`, despite its name, is NOT an orchestration layer of the type we're discussing here. `go-data-transfer` is fundamentally a *control protocol* that sits on top of a transport -- it performs access control logic, restarts, pauses and resumes, and implementing hooks to do payment and exchange. It is not an orchestration layer.

#### Terminology

TODO: Choose a single term for each of these

**Client** or **Requestor**- person requesting content
**Provider** or **Responder** - person making content available
**Transport** or **Transport Protocol** - A single mechanism for transferring content (ex: Bitswap / Graphsync / HTTP)
**Transfer** - a single request over a single transport protocol between a single client and a single provider
**Control Protocol** - An abstract protocol that sits on top of a transport to manage the control flow of a transfer -- authorizing requests, pausing and resuming, restarting, and communicating with an exchange protocol. The current implementation of a control protocol is go-data-transfer (poorly named)
**Exchange Protocol** - an abstract protocol that sits on top of a control protocol to manage the fair exchange of data for payment. (current implementation is go-fil-markets retrieval protocol, retrieval client implementation in Estuary)
**Content Request** or **Retrieval Request** -- a high level request to find content in the network, choose which protocols and peers to retrieve it with, and retrieve it through one or more transfers

### Design And Scoping

#### Top Level Interface

A user downloading content can do the following:
- Request a single block matching a CID
- Request a whole or partial DAG matching a CID + Selector
- Create a session to make multiple seperate block and DAG requests for related content

All of these operations effectively compress down to a single operation. A request for a single block is effectively a request for a DAG matching matching a CID and a selector that matches only the first block. And a request for a single CID + selector is effectively creating a session with a single request.

Each operation can take additional parameters to modify policy decisions about where to retrieve content from (i.e. pricing, geography, etc)

#### Core Agreements

These are some core design principles for the data transfer stack. They define the approach and scope of the core problem we're trying to address.

- Data transfer stack must be modular and configurable. We assume we will expand its functionality over time, and all pieces of functionality will not be built by PL.
- All data is content addressed (scope limit: no non-IPLD data)
- All transfer protocols must send responses in a format that is incrementally viable in reasonable chunks (scope limit: incrementally verifiable protocols)
- Providers serve data on as many transport protocols as possible, but indicate preference for certain protocols for their own performance optimization.
- We don't assume an association between type of provider & protocol (i.e. IPFS/Bitswap vs Filecoin/Graphsync). Clients must determine which protocols each provider supports and be able to choose among protocols to enable the fastest download
- We aim to support Web2 networking protocols as well as Libp2p.
- The framework has no direct knowledge of local caching. However, a local cache can be a source of content routing and a transport

#### Three core operations in retrieval of content

Ultimately serving a content request consists of three basic operations:

1. Content routing - given a desired unit of content, determine who has that content, and how they are making it available
2. Policy - given a desired unit of content, and a set of providers making that content available over various transport protocols, determine one or more providers and protocols via which to request the content
3. Transfer - given a desired unit of content, a provider who has that content, and a protocol the provider is making that content available over, transfer the content from provider to client. Use the control protocol to manage the transfer as if neccesary, an exchange protocol to perform financial transactions so the provider is compensated for transfer. (either by client or third party)

#### Asynchronous Operation Flow

The complexity of content retrieval emerges from two places:
1. Each of the core operations are complex, and asynchronous. Each produces a stream of results over time. As a result, the input to each operation that flows from a previous operation is essentially an asynchronous stream of inputs.
2. In a basic sense, the flow of operations is sequential:

flowchart LR
    Start --Requested Content--> CR[Content Routing] -- Peers Who Have Content --> Policy -- Requests to Peers For Content --> Transfer --Results--> Finish

However, in practice, the results of later operations flow back into previous operations. A typical content request may require several iterations of finding content, choosing peers, and transfering.

flowchart LR
    Start --Requested Content--> CR[Content Routing] -- Peers Who Have Content --> Policy -- Requests to Peers For Content --> Transfer --Results--> Finish;
    Policy --More Content To Find--> CR
    Transfer --More Content To Request--> Policy

### Content Routing

Inputs:
- Stream of CID / CID + Selector user requests plus possible additional parameters for desired content (price / geography / provider speed / preferred transports / etc)
- Stream of transfers initiated
- Stream of transfer results

Outputs:
- Stream of peers who have all or part of the content. Each peer should tell us:
1. What part of the content they have
2. What transport protocols it's available on
3. What exchange protocols are available and pricing if the content is not free

Content routing is the processing of find content through a set of disperate routing mechanisms.

Even in today's go-ipfs data transfer stack we look for content in several places:
- the local data store
- local peers (bitswap want-have protocols)
- optimized local peers (bitswap want-have with session peers)
- the IPFS

Places to look for content tend to sit on a spectrum from "very fast but not a lot of content" to "very slow but lots of content":

<iframe width="100%" height="418" frameborder="0"
src="https://observablehq.com/embed/@hannahhoward/universal-web-3-retrieval?cells=currentRouting"></iframe>

Going forward, we can only imagine more places to look for content:

<iframe width="100%" height="418" frameborder="0"
src="https://observablehq.com/embed/@hannahhoward/universal-web-3-retrieval?cells=futureRouting"></iframe>

It's an open question if all the places we want to find content will eventually use our future [Routing Language](https://github.com/libp2p/go-routing-language/blob/master/spec/language_spec.txt), but it's likely we will need to support lots of legacy protocols for some time.

Since there may be a non zero cost to a content routing query, we may want to sequence requests to prioritize places that are likely to respond faster:

<iframe width="100%" height="251" frameborder="0"
src="https://observablehq.com/embed/@hannahhoward/universal-web-3-retrieval?cells=overlappingSequencing"></iframe>

#### Content Routing Coordination vs Content Routing Requests

Content routing really involves two layers operation:
1. Content Routing Coordination - coordinating what content to look from a list of possible content routing sources over time
2. Content Routing Requests - executing a single request to find a single piece of content from a single content routing source

When we think about extensibility, we likely want to provide mechanisms to substitute third party implementations at both layers:
1. As a third party, I may want to provide an additional content source to the default coordination software, so that I can make my own content available.
2. As a third party, I many want to replace the content routing coordination so that I can experiment with different ways of ranking potential content sources and looking for data.

### Policy
Inputs:
- Stream of peers who have all or part of the content. Each peer should tell us:
1. What part of the content they have
2. What transport protocols it's available on
3. What exchange protocols are available and pricing if the content is not free
- Stream of results of previous transfers

Outputs:
- Stream of transfer requests to specific peers. Each request should specify:
1. what peer to transfer with
2. what protocol to use
3. what data we're requesting
4. what payment mechanism if any we're using

### Transfer
Inputs:
- Stream of transfer requests to specific peers. Each request should specify:
1. what peer to transfer with
2. what protocol to use
3. what data we're requesting
4. what payment mechanism if any we're using

Outputs:
- Stream of results of transfers. Each result should contain:
1. outcome (success/fail/partial response)
2. what was received
3. what content was missing

#### Units Of Transfer

The core units for a single transfer are:

1. Block: A single CID
2. DAG : A single CID + IPLD Selector

When retrieving a block, providers should send a complete response.
When retrieving a DAG, providers may send only a partial response.

### Architectural Kernel

A full data transfer stack will have lots of different components performing all or part of the three core operations involved in retrieving content. Some of these components may need to live out of process or even on another machine. We want these components generally to be pluggable and replacable.

Perhaps the most important design question is how we orchestrate all of these components, and allow them to be pluggable.

#### Traditional Golang coordination primitives and extensibility mechanisms are insufficient

Golang provides the following mechanisms for coordination among parallel operations:

1. Channels (a "share data by communicating" tool)
2. Mutexes and other "communicate by sharing data" tools

Golang's primary mechanism of extensibility is interfaces. Interfaces can wrap HTTP APIs to support out of process calls. But they require explicit configuration.

We have used these tools extensively throughout our stack to try to coordinate many parallel processes and components involved in retrieval. Generally they have proven difficult to manage, inflexible to modify or extend, and racy. Most critically, we have no way to insure a single order of operations for a complicated stack of communication between transfer components. Even when we carefully manage synchronization in a single component, we often encounter ordering errors across components.

Finally, channels are golang specific.

#### Proposal

The core data primitive for the transfer stack should be a per-session single threaded event bus with total producer-consumer ordering.

The most important reason for using an event bus is decoupling producers of events from their consumers. Currently, we implement some extensibility informally in via interfaces, registered hooks, and occasionally HTTP APIs. An event bus bakes extensibility into the architecture.

At the same time, while not a property of all event buses, certain event buses can gaurantee a single ordering of events among components. To avoid races, we want total producer-consumer ordering: everyone receives and consumes events in the exact same order.

We have built a prototype interface for such a bus here: https://github.com/protocol/hack-the-bus (implementation still in progress)

In the proposed bus, components can:
1. Publish Events that are processed asynchronously
2. Publish Events that are processed synchronously, meaning that no consumers can consume additional events until all interested consumers have consume the synchronous event. (this goes beyond traditional event bus architectures for cases where we need tight synchronization in certain parts of the system)
3. Subscribe to events and read ahead events without consuming them, up to a synchronous event.
4. Mark events as consumed.

#### Proposed Event Types

The following initial events would enable all three core operations, as well as provide mechanisms for payment in transfer across multiple protocols.

1. User Content Routing Request
a. Parameters: CID / Selector / policy preferences
b. Producer: Top Level Interface
c. Consumer: Content Routing Coordinator

2. Source Specific Content Routing Request
a. Parameters: CID / Selector / policy preferences & a specific content source
b. Producer: Content Routing Coordinator
c. Consumer: Request Executor for Content Routing Source

3. Content Routing Result
a. Parameters: Peer / Content found / Protocols Supported / Exchange Mechanisms Supported
b. Producer: Request Executor for Content Routing Source
c. Consumer: Policy Engine, Content Routing Coordinator (important for planning requests to other sources)

4. Transfer Request
a. Parameters: peer / transport protocol / data requested / payment mechanism and parameters
b. Producer: Policy Engine
c. Consumer: Control protocol implementation (see go-data-transfer), Content Routing Coordinator (important to know what has already been requested)

5. Initial Voucher Request
a. Parameters: peer / data requested / payment mechanism and parameters
b. Producer: Control protocol implementation
c. Consumer: Exchange protocol / Wallet

6. Initial Voucher
a. Parameters: payment voucher
b. Producer: Exchange protocol / Wallet
c. Consumer: Control protocol implementation

7. Initiate Transfer
a. Parameters: peer / data requested / payment voucher
b. Producer: Control protocol implementation
c. Consumer: Transport implementation

8. Followup Voucher Request
a. Parameters: peer / data requested / data received, payment mechanism and parameters
b. Producer: Control protocol implementation
c. Consumer: Exchange protocol / Wallet

9. Followup Voucher
a. Parameters: payment voucher
b. Producer: Exchange protocol / Wallet
c. Consumer: Control protocol implementation

10. Send voucher and resume
a. Parameters: peer / data requested / followup payment voucher
b. Producer: Control protocol implementation
c. Consumer: Transport implementation

11. Transfer result
a. Parameters: success / failure / partial success (with information about what was retrieved)
b. Producer: Transport implementation
c. Consumer: Policy engine, Content Routing coordinator

### Miscellaneous Concerns

#### Identifying Peers

We need a way to identify peers in this framework. We should pass information in a form that can help us identify both libp2p peers and traditional HTTP peers

Some possible formats include:
- peer IDs
- multiaddrs

See authenticated records: https://github.com/libp2p/specs/pull/217

#### Identifying protocols

We need to define a format for identifying protocols:

/libp2p/bitswap
/libp2p/graphsync

Strings? Multicodec? Something else?

#### Bitswap vs Graphsync

Figuring out how graphsync and bitswap interact and are prioritized is a whole large seperate discussion, that merits its own product review.

- Should we keep local peer group content routing components in bitswap & graphsync or move them to a seperate protocol?

#### Miscellaneous Improvement needs

- Faster traversals (not just depth first single thread)
- Disk prefetching
- Graphsync modification requests?
- Better hints about next content to request (i.e. what selector remains at a missing CID?)
- Is Bitswap too chatty?

#### Optimization Scenarios

- Client retrieving tons of data (i.e. IPFS gateway, miners accepting lots of storage deals)
- Provider sending tons of data (i.e. Estuary deals with miners)

#### Payment mechanisms To Figure Out

These are "out of band" problems (they are the implementation problems of additional exchange protocol providers) but still worth mentioning.

- Subscription based payment (i.e. Netflix style)
- 3rd party payments (i.e. CDN style - content provider provides payment)