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 Layout(db *h.DagBuilderHelper) (ipld.Node, error)

Functions

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 |
  +=========+   +=========+   + - - - - +