dag

package module
v0.2.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 4, 2021 License: MIT Imports: 10 Imported by: 7

README

dag

-- import "github.com/qri-io/dag"

Package dag is the base of a family of packages for working with directed acyclic graphs (DAGs) most (if not all) use cases assume the dag is a merkle-tree https://en.wikipedia.org/wiki/Merkle_tree

Usage

type Completion
type Completion []uint16

Completion tracks the presence of blocks described in a manifest Completion can be used to store transfer progress, or be stored as a record of which blocks in a DAG are missing each element in the slice represents the index a block in a manifest.Nodes field, which contains the hash of a block needed to complete a manifest the element in the progress slice represents the transmission completion of that block locally. It must be a number from 0-100, 0 = nothing locally, 100 = block is local. note that progress is not necessarily linear. for example the following is 50% complete progress:

manifest.Nodes: ["QmA", "QmB", "QmC", "QmD"] progress: [0, 100, 0, 100]

func NewCompletion
func NewCompletion(mfst, missing *Manifest) Completion

NewCompletion constructs a progress from

func (Completion) Complete
func (p Completion) Complete() bool

Complete returns weather progress is finished

func (Completion) CompletedBlocks
func (p Completion) CompletedBlocks() (count int)

CompletedBlocks returns the number of blocks that are completed

func (Completion) Percentage
func (p Completion) Percentage() (pct float32)

Percentage expressess the completion as a floating point number betwen 0.0 and 1.0

type Info
type Info struct {
	// Info is built upon a manifest
	Manifest *Manifest      `json:"manifest"`
	Paths    map[string]int `json:"paths,omitempty"` // sections are lists of logical sub-DAGs by positions in the nodes list
	Sizes    []uint64       `json:"sizes,omitempty"` // sizes of nodes in bytes
}

Info is os.FileInfo for dags: a struct that describes important details about a graph. Info builds on a manifest

when being sent over the network, the contents of Info should be considered gossip, as Info's are not deterministic. This has important implications Info should contain application-specific info about a datset

func NewInfo
func NewInfo(ctx context.Context, ng ipld.NodeGetter, id cid.Cid) (*Info, error)

NewInfo creates a

type Manifest
type Manifest struct {
	Links [][2]int `json:"links"` // links between nodes
	Nodes []string `json:"nodes"` // list if CIDS contained in the DAG
}

Manifest is a determinsitc description of a complete directed acyclic graph. Analogous to bittorrent .magnet files, manifests contain no content, only a description of the structure of a graph (nodes and links)

Manifests are built around a flat list of node identifiers (usually hashes) and a list of links. A link element is a tuple of [from,to] where from and to are indexes in the nodes list

Manifests always describe the FULL graph, a root node and all it's descendants

A valid manifest has the following properties: * supplying the same dag to the manifest function must be deterministic:

manifest_of_dag = manifest(dag)
hash(manifest_of_dag) == hash(manifest(dag))

  • In order to generate a manifest, you need the full DAG * The list of nodes MUST be sorted by number of descendants. When two nodes

    have the same number of descenants, they MUST be sorted lexographically by node ID. The means the root of the DAG will always be the first index

Manifests are intentionally limited in scope to make them easier to prove, faster to calculate, hard requirement the list of nodes can be used as a base other structures can be built upon. by keeping manifests at a minimum they are easier to verify, forming a foundation for

func Missing
func Missing(ctx context.Context, ng ipld.NodeGetter, m *Manifest) (missing *Manifest, err error)

Missing returns a manifest describing blocks that are not in this node for a given manifest

func NewManifest
func NewManifest(ctx context.Context, ng ipld.NodeGetter, id cid.Cid) (*Manifest, error)

NewManifest generates a manifest from an ipld node

func UnmarshalCBORManifest
func UnmarshalCBORManifest(data []byte) (m *Manifest, err error)

UnmarshalCBORManifest decodes a manifest from a byte slice

func (*Manifest) MarshalCBOR
func (m *Manifest) MarshalCBOR() (data []byte, err error)

MarshalCBOR encodes this manifest as CBOR data

type Node
type Node interface {
	// pulled from blocks.Block format
	Cid() cid.Cid
	// Links is a helper function that returns all links within this object
	Links() []*ipld.Link
	// Size returns the size in bytes of the serialized object
	Size() (uint64, error)
}

Node is a subset of the ipld ipld.Node interface, defining just the necessary bits the dag package works with

type NodeGetter
type NodeGetter struct {
	Dag coreiface.DagAPI
}

NodeGetter wraps the go-ipfs DagAPI to satistfy the IPLD NodeGetter interface

func (*NodeGetter) Get
func (ng *NodeGetter) Get(ctx context.Context, id cid.Cid) (ipld.Node, error)

Get retrieves nodes by CID. Depending on the NodeGetter implementation, this may involve fetching the Node from a remote machine; consider setting a deadline in the context.

func (*NodeGetter) GetMany
func (ng *NodeGetter) GetMany(ctx context.Context, cids []cid.Cid) <-chan *ipld.NodeOption

GetMany returns a channel of NodeOptions given a set of CIDs.

Documentation

Overview

Package dag is the base of a family of packages for working with directed acyclic graphs (DAGs) most (if not all) use cases assume the dag is a merkle-tree https://en.wikipedia.org/wiki/Merkle_tree

dag package has two external dependencies that are worth developing an understanding of:

  • cid - github.com/ipfs/go-cid, github.com/ipld/specs "Content IDentifiers" is a hashing technique that embeds additional info about the hash in question
  • ipld - github.com/ipfs/go-ipld-format, github.com/ipld/specs ipld is a linked-data format for content-addressed data

def check those out. dag package attempts to interoperate with these interfaces wherever & whenever possible, in the name of compatibility

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrIndexOutOfRange indicates the index given is out of range of the Manifest
	ErrIndexOutOfRange = fmt.Errorf("index out of range")

	// ErrIDNotFound indicates the id given is not found in the Manifest
	ErrIDNotFound = fmt.Errorf("id not found in Manifest")
)
View Source 
var ErrInfoNotFound = fmt.Errorf("Info: not found")

ErrInfoNotFound should be returned by all implementations of DAGInfoStore when a DAG isn't found

Functions

This section is empty.

Types

type Completion 

type Completion []uint16

Completion tracks the presence of blocks described in a manifest Completion can be used to store transfer progress, or be stored as a record of which blocks in a DAG are missing each element in the slice represents the index a block in a manifest.Nodes field, which contains the hash of a block needed to complete a manifest the element in the progress slice represents the transmission completion of that block locally. It must be a number from 0-100, 0 = nothing locally, 100 = block is local. note that progress is not necessarily linear. for example the following is 50% complete progress:

manifest.Nodes: ["QmA", "QmB", "QmC", "QmD"] progress: [0, 100, 0, 100]

func NewCompletion 

func NewCompletion(mfst, missing *Manifest) Completion

NewCompletion constructs a progress from

func (Completion) Complete 

func (p Completion) Complete() bool

Complete returns weather progress is finished

func (Completion) CompletedBlocks 

func (p Completion) CompletedBlocks() (count int)

CompletedBlocks returns the number of blocks that are completed

func (Completion) Percentage 

func (p Completion) Percentage() (pct float32)

Percentage expressess the completion as a floating point number betwen 0.0 and 1.0

type Info 

type Info struct {
	// Info is built upon a manifest
	Manifest *Manifest      `json:"manifest"`
	Labels   map[string]int `json:"labels,omitempty"` // sections are lists of logical sub-DAGs by positions in the nodes list
	Sizes    []uint64       `json:"sizes,omitempty"`  // sizes of nodes in bytes
}

Info is os.FileInfo for dags: a struct that describes important details about a graph. Info builds on a manifest.

when being sent over the network, the contents of Info should be considered gossip, as Info's are *not* deterministic. This has important implications Info should contain application-specific info about a datset

func NewInfo 

func NewInfo(ctx context.Context, ng ipld.NodeGetter, id cid.Cid) (*Info, error)

NewInfo creates an info with an underlying manifest

func UnmarshalCBORDagInfo added in v0.2.0 

func UnmarshalCBORDagInfo(data []byte) (i *Info, err error)

UnmarshalCBORDagInfo decodes an Info from a byte slice

func (*Info) AddLabel 

func (i *Info) AddLabel(label string, index int) error

AddLabel adds a label to the list of Info.Labels it returns an error if the index is out of bounds

func (*Info) AddLabelByID 

func (i *Info) AddLabelByID(label, id string) error

AddLabelByID adds a label to the list of Info.Labels it returns an error if the id is not part of the DAG

func (*Info) InfoAtID 

func (i *Info) InfoAtID(id string) (*Info, error)

InfoAtID returns a sub-Info, the DAG, sizes, and labels, with the given id as root of the DAG

func (*Info) InfoAtIndex 

func (i *Info) InfoAtIndex(idx int) (*Info, error)

InfoAtIndex returns a sub-Info, the DAG, sizes, and labels, with the given index as root of the DAG

func (*Info) InfoAtLabel 

func (i *Info) InfoAtLabel(label string) (*Info, error)

InfoAtLabel returns a sub-Info, the DAG, sizes, and labels, with the given label as root of the DAG

func (*Info) MarshalCBOR added in v0.2.0 

func (i *Info) MarshalCBOR() (data []byte, err error)

MarshalCBOR encodes a dag.Info as CBOR data

func (*Info) RootCID 

func (i *Info) RootCID() cid.Cid

RootCID proxies the manifest RootCID method, protecting against situations where the underlying manifest doesn't exist

type InfoStore 

type InfoStore interface {
	// store an Info struct at the key, overwriting any previous entry.
	// The most Common way to use this is keying by the RootCID. eg:
	// store.PutDAGInfo(ctx, di.RootCID().String(), di)
	// implementations must support arbitrary keys
	PutDAGInfo(ctx context.Context, key string, di *Info) error
	// get dag information stored at key, return ErrInfoNotFound when
	// a key isn't present in the store
	DAGInfo(ctx context.Context, key string) (di *Info, err error)
	// Remove an info stored at key. Deletes for keys that don't exist should not
	// return an error, deleted returns true if a value was present before the call
	DeleteDAGInfo(ctx context.Context, key string) (deleted bool, err error)
}

InfoStore is the interface for a key-value store DAG information, keyed by id strings by convention the id stored should match the root id of the DAG being described

func NewMemInfoStore 

func NewMemInfoStore() InfoStore

NewMemInfoStore creates an in-memory InfoStore

type Manifest 

type Manifest struct {
	Links [][2]int `json:"links"` // links between nodes
	Nodes []string `json:"nodes"` // list if CIDS contained in the DAG
}

Manifest is a determinsitc description of a complete directed acyclic graph. Analogous to bittorrent .magnet files, manifests contain no content, only a description of the structure of a graph (nodes and links)

Manifests are built around a flat list of node identifiers (usually hashes) and a list of links. A link element is a tuple of [from,to] where from and to are indexes in the nodes list

Manifests always describe the FULL graph, a root node and all it's descendants

A valid manifest has the following properties:

  • supplying the same dag to the manifest function must be deterministic: manifest_of_dag = manifest(dag) hash(manifest_of_dag) == hash(manifest(dag))
  • In order to generate a manifest, you need the full DAG
  • The list of nodes MUST be sorted by number of descendants. When two nodes have the same number of descenants, they MUST be sorted lexographically by node ID. The means the root of the DAG will always be the first index

Manifests are intentionally limited in scope to make them easier to prove, faster to calculate, hard requirement the list of nodes can be used as a base other structures can be built upon. by keeping manifests at a minimum they are easier to verify, forming a foundation for

func Missing 

func Missing(ctx context.Context, ng ipld.NodeGetter, m *Manifest) (missing *Manifest, err error)

Missing returns a manifest describing blocks that are not in this node for a given manifest

func NewManifest 

func NewManifest(ctx context.Context, ng ipld.NodeGetter, id cid.Cid) (*Manifest, error)

NewManifest generates a manifest from an ipld node

func UnmarshalCBORManifest 

func UnmarshalCBORManifest(data []byte) (m *Manifest, err error)

UnmarshalCBORManifest decodes a manifest from a byte slice

func (*Manifest) IDIndex 

func (m *Manifest) IDIndex(id string) int

IDIndex returns the node index of the id

func (*Manifest) MarshalCBOR 

func (m *Manifest) MarshalCBOR() (data []byte, err error)

MarshalCBOR encodes this manifest as CBOR data

func (*Manifest) RootCID 

func (m *Manifest) RootCID() cid.Cid

RootCID returns the root node as a CID. If for some reason the manifest is empty or the root hash isn't a valid CID, RootCID returns cid.Undef

type MemInfoStore 

type MemInfoStore struct {
	// contains filtered or unexported fields
}

MemInfoStore is an implementation of InfoStore that uses an in-memory map

func (*MemInfoStore) DAGInfo 

func (s *MemInfoStore) DAGInfo(_ context.Context, id string) (di *Info, err error)

DAGInfo gets dag information stored at key, return ErrInfoNotFound when a key isn't present in the store

func (*MemInfoStore) DeleteDAGInfo 

func (s *MemInfoStore) DeleteDAGInfo(_ context.Context, id string) (deleted bool, err error)

DeleteDAGInfo removes the info at key from the store

func (*MemInfoStore) PutDAGInfo 

func (s *MemInfoStore) PutDAGInfo(_ context.Context, id string, di *Info) error

PutDAGInfo stores an Info struct at the key id, overwriting any previous entry

type Node 

type Node interface {
	// pulled from blocks.Block format
	Cid() cid.Cid
	// Links is a helper function that returns all links within this object
	Links() []*ipld.Link
	// Size returns the size in bytes of the serialized object
	Size() (uint64, error)
}

Node is a subset of the ipld ipld.Node interface, defining just the necessary bits the dag package works with

type NodeGetter 

type NodeGetter struct {
	Dag ipld.DAGService
}

NodeGetter wraps the go-ipfs DagAPI to satistfy the IPLD NodeGetter interface

func NewNodeGetter 

func NewNodeGetter(dsvc ipld.DAGService) *NodeGetter

NewNodeGetter returns a new NodeGetter from an IPFS core API

func (*NodeGetter) Get 

func (ng *NodeGetter) Get(ctx context.Context, id cid.Cid) (ipld.Node, error)

Get retrieves nodes by CID. Depending on the NodeGetter implementation, this may involve fetching the Node from a remote machine; consider setting a deadline in the context.

func (*NodeGetter) GetMany 

func (ng *NodeGetter) GetMany(ctx context.Context, cids []cid.Cid) <-chan *ipld.NodeOption

GetMany returns a channel of NodeOptions given a set of CIDs.

Source Files

View all Source files

Directories

Path Synopsis
Package dsync implements point-to-point merkle-DAG-syncing between a local instance and remote source.
 Package dsync implements point-to-point merkle-DAG-syncing between a local instance and remote source.
dsync_ipfs_plugin
DsyncPlugin is an ipfs deamon plugin for embedding dsync functionality directly into IPFS https://github.com/ipfs/go-ipfs-example-plugin
 DsyncPlugin is an ipfs deamon plugin for embedding dsync functionality directly into IPFS https://github.com/ipfs/go-ipfs-example-plugin
dsync_ipfs_plugin/cli
p2putil

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.