balanced

Documentation

Overview

Package balanced provides methods to build balanced DAGs, which are generalistic DAGs in which all leaves (nodes representing chunks of data) are at the same distance from the root. Nodes can have only a maximum number of children; to be able to store more leaf data nodes balanced DAGs are extended by increasing its depth (and having more intermediary nodes).

Internal nodes are always represented by UnixFS nodes (of type `File`) encoded inside DAG nodes (see the `go-unixfs` package for details of UnixFS). In contrast, leaf nodes with data have multiple possible representations: UnixFS nodes as above, raw nodes with just the file data (no format) and Filestore nodes (that directly link to the file on disk using a format stored on a raw node, see the `go-ipfs/filestore` package for details of Filestore.)

In the case the entire file fits into just one node it will be formatted as a (single) leaf node (without parent) with the possible representations already mentioned. This is the only scenario where the root can be of a type different that the UnixFS node.

Notes:

1. In the implementation. `FSNodeOverDag` structure is used for representing the UnixFS node encoded inside the DAG node. (see https://github.com/ipfs/go-ipfs/pull/5118.)

2. `TFile` is used for backwards-compatibility. It was a bug causing the leaf nodes to be generated with this type instead of `TRaw`. The former one should be used (like the trickle builder does). (See https://github.com/ipfs/go-ipfs/pull/5120.)

   +-------------+ | Root 4 | +-------------+ | +--------------------------+----------------------------+ | | +-------------+ +-------------+ | Node 2 | | Node 5 | +-------------+ +-------------+ | | +-------------+-------------+ +-------------+ | | | +-------------+ +-------------+ +-------------+ | Node 1 | | Node 3 | | Node 6 | +-------------+ +-------------+ +-------------+ | | | +------+------+ +------+------+ +------+ | | | | | +=========+ +=========+ +=========+ +=========+ +=========+ | Chunk 1 | | Chunk 2 | | Chunk 3 | | Chunk 4 | | Chunk 5 | +=========+ +=========+ +=========+ +=========+ +=========+

Index

• func Append(ctx context.Context, baseiNode ipld.Node, db *h.DagBuilderHelper) (out ipld.Node, errOut error)
• func BalancedDagDepth(ctx context.Context, root *h.FSNodeOverDag, dserv ipld.DAGService) (int, error)
• func BuildMetadataDag(db *h.DagBuilderHelper) (ipld.Node, error)
• func BuildNewMetaDataDag(mdb *h.MetaDagBuilderHelper) (ipld.Node, error)
• func Layout(db *h.DagBuilderHelper) (ipld.Node, error)
• func VerifyBalancedDagStructure(nd ipld.Node, p VerifyParamsForBalanced) error
• type VerifyParamsForBalanced

Functions

func Append

func Append(ctx context.Context, baseiNode ipld.Node, db *h.DagBuilderHelper) (out ipld.Node, errOut error)

Append appends the data in `db` to the balanced format dag. The given `baseiNode` should include TFile or TTokenMeta FSNode. Case #1: The given `baseiNode` is the root & leaf of a DAG of depth 0. It has UnixFS data in it. Case #2: `baseiNode` is the root of a DAG of depth 1. Case #3: A DAG of depth > 1

func BalancedDagDepth

func BalancedDagDepth(ctx context.Context, root *h.FSNodeOverDag, dserv ipld.DAGService) (int, error)

func BuildMetadataDag

func BuildMetadataDag(db *h.DagBuilderHelper) (ipld.Node, error)

BuildMetadataDag builds a DAG for the given db.TokenMetadata byte array and sets the root node to db.metaDagRoot.

func BuildNewMetaDataDag

func BuildNewMetaDataDag(mdb *h.MetaDagBuilderHelper) (ipld.Node, error)

BuildNewMetaDataDag builds a metadata DAG and sets up the MetaDagBuilderHelper's meta Dag root with the new DAG root. A precondition is to set mdb.db.spl with SetSpl() from the caller.

func Layout

func Layout(db *h.DagBuilderHelper) (ipld.Node, error)

Layout builds a balanced DAG layout. In a balanced DAG of depth 1, leaf nodes with data are added to a single `root` until the maximum number of links is reached. Then, to continue adding more data leaf nodes, a `newRoot` is created pointing to the old `root` (which will now become and intermediary node), increasing the depth of the DAG to 2. This will increase the maximum number of data leaf nodes the DAG can have (`Maxlinks() ^ depth`). The `fillNodeRec` function will add more intermediary child nodes to `newRoot` (which already has `root` as child) that in turn will have leaf nodes with data added to them. After that process is completed (the maximum number of links is reached), `fillNodeRec` will return and the loop will be repeated: the `newRoot` created will become the old `root` and a new root will be created again to increase the depth of the DAG. The process is repeated until there is no more data to add (i.e. the DagBuilderHelper’s Done() function returns true).

The nodes are filled recursively, so the DAG is built from the bottom up. Leaf nodes are created first using the chunked file data and its size. The size is then bubbled up to the parent (internal) node, which aggregates all the sizes of its children and bubbles that combined size up to its parent, and so on up to the root. This way, a balanced DAG acts like a B-tree when seeking to a byte offset in the file the graph represents: each internal node uses the file size of its children as an index when seeking.

`Layout` creates a root and hands it off to be filled:

       +-------------+
       |   Root 1    |
       +-------------+
              |
 ( fillNodeRec fills in the )
 ( chunks on the root.      )
              |
       +------+------+
       |             |
  + - - - - +   + - - - - +
  | Chunk 1 |   | Chunk 2 |
  + - - - - +   + - - - - +

                     ↓
When the root is full but there's more data...
                     ↓

       +-------------+
       |   Root 1    |
       +-------------+
              |
       +------+------+
       |             |
  +=========+   +=========+   + - - - - +
  | Chunk 1 |   | Chunk 2 |   | Chunk 3 |
  +=========+   +=========+   + - - - - +

                     ↓
...Layout's job is to create a new root.
                     ↓

                      +-------------+
                      |   Root 2    |
                      +-------------+
                            |
              +-------------+ - - - - - - - - +
              |                               |
       +-------------+            ( fillNodeRec creates the )
       |   Node 1    |            ( branch that connects    )
       +-------------+            ( "Root 2" to "Chunk 3."  )
              |                               |
       +------+------+             + - - - - -+
       |             |             |
  +=========+   +=========+   + - - - - +
  | Chunk 1 |   | Chunk 2 |   | Chunk 3 |
  +=========+   +=========+   + - - - - +

func VerifyBalancedDagStructure

func VerifyBalancedDagStructure(nd ipld.Node, p VerifyParamsForBalanced) error

VerifyBalancedDagStructure checks that the given dag matches exactly the balanced dag datastructure layout

Types

type VerifyParamsForBalanced

type VerifyParamsForBalanced struct {
	Getter    ipld.NodeGetter
	Ctx       context.Context
	MaxLinks  int
	TreeDepth int
	Prefix    *cid.Prefix
	RawLeaves bool
	Metadata  bool
}

VerifyParams is used by VerifyBalancedDagStructure