recovery

README

IPFS Recovery

The project was originally started as a submission for the HackFS hackathon and became Top-10 Finalist 🏆. Also check-out our presentation.

Building a way for content to persist permanently despite any damage to data and the network by
bringing data recovery algorithms into IPFS protocol.

Table of Contents

• Background
• Implementation
• Algorithms
• Related Work
• Future Work
• Tryout
• Contributors
• License

Background

The IPFS project, at its core, tries to upgrade the Internet to make it better in multiple ways. One of the goals is to make the Web permanent. This IPFS characteristic is very promising, but still not in the state of the art form and requires more RnD in that vector. On the other side, Computer Science, for many years of existence, has plenty of research related to data and the ways to make it persistent against multiple data-loss factors within mostly centralized systems. On the way to permanency, those inventions can apply to IPFS protocol taking the most out of them, and then newer innovations might take place instead after gathering all the experience. Further work in this avenue can also ensure integrity even in doomsday scenarios where large portions of the network can go down, allowing content to still be recovered. Though there are multiple discussions in the IPFS ecosystem regarding the data persevering mechanisms, like erasure codings, none of them were actually implemented.

The IPFS Recovery project brings data recovery algorithms into IPFS with the above aim. It does so by creating new IPLD data structures able to do self-recovery in case some of the nodes are lost and can't be found on the network due to node churn, network issues, or physical storage damage.

Implementation

The Recovery currently points to the main IPFS implementation in Golang and follows all its development guidelines and best practices. The Golang Recovery implementation is a fully modular library with clean API boundaries that aims to provide convenient use and excellent abstraction for all current and future implementations.

Algorithms

Reed-Solomon

For the initial version, the project started with industry-standard Reed-Solomon coding.

Alpha Entanglements

As a next step, novel Alpha Entanglements schema has been chosen. It provides better performance and higher recovery ratio comparing with the former algorithm. In particular, entanglements are interesting as they provide the ability to create self-healing networks.

Related Work

IPFS Fork

As Recovery follows IPFS ecosystem modularity best practises, its fork is integrated in a just a few small changes.

First, it covers DAG sessions with custom NodeGetter that can recover nodes on the fly if content is requested but not found. Furthermore, fork adds additional functionality to IPFS CLI extending it with recovery command group. Currently, it is only capable for encoding DAGs with Reed Solomon recoverability using encode, but later CLI will be extended with full featured management for Recovery, like re-encoding, manual recovery and algorithm choices.

Testground Plans

IPFS ecosystem recently launched new project aimed to test p2p system on large scale to simulate real world behavior. Using it for benchmarking and testing Recovery is a must, as it goals to improve IPFS protocol.

Future Work

• Upgrade to more complex Alpha Entanglement parity lattice to reach better performance.

• IPLD specs formalization through active discussions and feedback processing.

• Implementations for latest go IPLD version and for js as well.

• Extensive Testground simulation to gather real-world resiliency benchmarks and to examine various other erasure codes

Tryout

1. Build forked IPFS
2. Encode ANY IPFS content: ipfs recovery encode <path>
3. List all the blocks encoded content consist of: ipfs refs <enc_cid> -r
4. Remove any random blocks yourself from the given list: ipfs block rm ...<cid>
5. Be amazed after seeing that it is still possible to get your content back: ipfs get <enc_cid>

Contributors

• @Wondertan
• @govi218
• @avalonche

License

MIT © Hlib Kanunnikov

Documentation

Index

• func EncodeDAG(ctx context.Context, dag format.NodeGetter, e Encoder, nd format.Node, ...) (format.Node, error)
• func NewDagSession(ctx context.Context, r Recoverer, ex exchange.Interface, ...) format.NodeGetter
• type Encoder
• type Node
• type Recoverability
• type Recoverer
• type Strategy
  • func (s Strategy) All() bool
  • func (s Strategy) Data() bool
  • func (s Strategy) Requested() bool

Functions

func EncodeDAG

func EncodeDAG(ctx context.Context, dag format.NodeGetter, e Encoder, nd format.Node, r Recoverability) (format.Node, error)

EncodeDAG encodes whole DAG under the given node with given Encoder and recoverability.

func NewDagSession

func NewDagSession(ctx context.Context, r Recoverer, ex exchange.Interface, bs blockstore.Blockstore) format.NodeGetter

Types

type Encoder

type Encoder interface {

	// Encodes Node to a recovery Node.
	// Bigger recoverability - higher storage usage.
	Encode(context.Context, format.Node, Recoverability) (Node, error)
}

type Node

type Node interface {
	format.Node

	// Recoverability of the Node.
	Recoverability() Recoverability

	// RecoveryLinks lists links to all recovery Nodes.
	RecoveryLinks() []*format.Link

	// FIXME This is awful, but there is no workaround fot that. IPFS is very strict about using only ProtoNode
	//  in multiple cases.
	Proto() *merkledag.ProtoNode
}

Node wraps IPLD Node with an ability to recover lost linked Nodes.

type Recoverability

type Recoverability = int

Recoverability param defines max amount of Data Nodes that can be lost preserving recoverability.

type Recoverer

type Recoverer interface {

	// Recovers Nodes by ids from the recovery Node.
	Recover(context.Context, Node, ...cid.Cid) (<-chan *format.NodeOption, error)
}

type Strategy

type Strategy string

Strategy defines verbosity level for Node recovery. Higher verbosity potentially uses more storage space.

const (

	// Recover all the Nodes possible. Redundant and Data Nodes altogether.
	// Most storage usage.
	All Strategy = "all"

	// Recover only Data Nodes. Only user data, ignores Redundant Nodes.
	Data Strategy = "data"

	// Recover only requested Nodes. Actual Nodes user asked for, might be just small portion of all the Data.
	Requested Strategy = "requested"
)

func (Strategy) All

func (s Strategy) All() bool

func (Strategy) Data

func (s Strategy) Data() bool

func (Strategy) Requested

func (s Strategy) Requested() bool